This patch introduces a highly-shareable version of AVL trees both for RTL usage...
authorSir Richard <sir_richard@svn.reactos.org>
Thu, 22 Jul 2010 01:41:45 +0000 (01:41 +0000)
committerSir Richard <sir_richard@svn.reactos.org>
Thu, 22 Jul 2010 01:41:45 +0000 (01:41 +0000)
[RTL]: Uncouple generic table from AVL table implementation into its own avltable.c
[RTL]: Get rid of "Austin" and fix prototypes of AVL table functions.
[RTL]: Re-implement AVL table functions, sharing as much code as possible with the SPLAY tree implementation which is pretty decent. Lookup, insert, enumeration are implemented, but not delete.
[RTL]: Make large part of the RTL AVL package into its own "support" file that can work both with MMADDRESS_NODE and RTL_BALANCED_LINKS structures. The former is used by ARM3 for VADs.
[NTOS]: Implement basic VAD AVL tree routines (Insert, LookupEmpty, GetPrevious, CheckForConflict, Locate). This is enough to insert VADs, find a free address range, and locate a VAD by address. No delete yet
Thanks to Timo Kreuzer for some clever definitions, Knuth for his genius, several online C implementations for ideas, the HPI kernel blog for insight on how Windows does it, and others.

svn path=/trunk/; revision=48173

14 files changed:
reactos/lib/rtl/austin/avl.c [deleted file]
reactos/lib/rtl/austin/avl.h [deleted file]
reactos/lib/rtl/austin/macros.h [deleted file]
reactos/lib/rtl/austin/tree.c [deleted file]
reactos/lib/rtl/austin/tree.h [deleted file]
reactos/lib/rtl/austin/udict.h [deleted file]
reactos/lib/rtl/avlsupp.c [new file with mode: 0644]
reactos/lib/rtl/avltable.c [new file with mode: 0644]
reactos/lib/rtl/generictable.c
reactos/lib/rtl/rtl.rbuild
reactos/lib/rtl/rtlavl.h [new file with mode: 0644]
reactos/ntoskrnl/mm/ARM3/miavl.h [new file with mode: 0644]
reactos/ntoskrnl/mm/ARM3/vadnode.c [new file with mode: 0644]
reactos/ntoskrnl/ntoskrnl-generic.rbuild

diff --git a/reactos/lib/rtl/austin/avl.c b/reactos/lib/rtl/austin/avl.c
deleted file mode 100644 (file)
index 27bf054..0000000
+++ /dev/null
@@ -1,434 +0,0 @@
-/*
- * Austin---Astonishing Universal Search Tree Interface Novelty
- * Copyright (C) 2000 Kaz Kylheku <kaz@ashi.footprints.net>
- * Copyright (C) 2000 Carl van Tast <vanTast@netway.at>
- *
- * Free Software License:
- *
- * All rights are reserved by the author, with the following exceptions:
- * Permission is granted to freely reproduce and distribute this software,
- * possibly in exchange for a fee, provided that this copyright notice appears
- * intact. Permission is also granted to adapt this software to produce
- * derivative works, as long as the modified versions carry this copyright
- * notice and additional notices stating that the work has been modified.
- * This source code may be translated into executable form and incorporated
- * into proprietary software; there is no requirement for such software to
- * contain a copyright notice related to this source.
- *
- * $Id: avl.c,v 1.3 2000/01/12 02:37:02 kaz Exp $
- * $Name: austin_0_2 $
- */
-/*
- * Modified for use in ReactOS by arty
- */
-#include "rtl.h"
-#include "udict.h"
-#include "tree.h"
-#include "macros.h"
-
-#define balance Balance
-#define BALANCED udict_balanced
-#define LEFTHEAVY udict_leftheavy
-#define RIGHTHEAVY udict_rightheavy
-#define EQUAL GenericEqual
-#define LESS GenericLessThan
-#define GREATER GenericGreaterThan
-
-int print_node(udict_t *ud, udict_node_t *node, int indent)
-{
-       int i, rh = 0, lh = 0;
-       char buf[100];
-       udict_node_t *nil = ud->BalancedRoot.Parent;
-
-       for( i = 0; i < indent; i++ ) buf[i] = ' ';
-       if( node == ud->BalancedRoot.Parent ) {
-               sprintf(buf+i, "Nil\n");
-               DbgPrint("%s", buf);
-               return 0;
-       } else {
-               sprintf(buf+i, "Node %p (parent %p: balance %d)\n", node, node->parent, node->Balance);
-               DbgPrint("%s", buf);
-               if( node->LeftChild != nil ) {
-                       sprintf(buf+i, "--> Left\n");
-                       DbgPrint("%s", buf);
-                       lh = print_node(ud, node->LeftChild, indent+1);
-               }
-               if( node->RightChild != nil ) {
-                       sprintf(buf+i, "--> Right\n");
-                       DbgPrint("%s", buf);
-                       rh = print_node(ud, node->RightChild, indent+1);
-               }
-               if (indent)
-               {
-                       if (rh < lh - 1 || lh < rh - 1)
-                       {
-                               sprintf(buf+i, "warning: tree is too unbalanced %d vs %d\n",
-                                               lh, rh);
-                               DbgPrint("%s", buf);
-                       }
-                       if (rh != lh && node->Balance == BALANCED)
-                       {
-                               sprintf(buf+i, "warning: tree says balanced, but %d vs %d\n", 
-                                               lh, rh);
-                               DbgPrint("%s", buf);
-                       }
-                       else if (lh <= rh && node->Balance == LEFTHEAVY)
-                       {
-                               sprintf(buf+i, "warning: tree says leftheavy but %d vs %d\n",
-                                               lh, rh);
-                               DbgPrint("%s", buf);
-                       }
-                       else if (lh >= rh && node->Balance == RIGHTHEAVY)
-                       {
-                               sprintf(buf+i, "warning: tree says rightheavy but %d vs %d\n",
-                                               lh, rh);
-                               DbgPrint("%s", buf);
-                       }
-               }
-               if (rh > lh) return 1+rh;
-               else return 1+lh;
-       }
-}
-
-void print_tree(udict_t *ud)
-{
-       DbgPrint("TREE %x (Nil %x)\n", ud, ud->BalancedRoot.Parent);
-       print_node(ud, &ud->BalancedRoot, 0);
-}
-
-void avl_init(udict_t *ud)
-{
-       ud->BalancedRoot.left = ud->BalancedRoot.right =
-       ud->BalancedRoot.parent = (udict_node_t*)
-               ud->AllocateRoutine(ud, sizeof(udict_node_t));
-       ud->BalancedRoot.parent->left = ud->BalancedRoot.parent->right =
-               ud->BalancedRoot.parent->parent = ud->BalancedRoot.parent;
-}
-
-void avl_deinit(udict_t *ud)
-{
-       ud->FreeRoutine(ud, ud->BalancedRoot.parent);
-}
-
-static void RotateLeft(udict_node_t **top)
-{
-       udict_node_t *parent = *top;
-       udict_node_t *child = parent->right;
-
-       child->parent = parent->parent;
-       parent->right = child->left;
-       parent->right->parent = parent;     /* may change sentinel.parent */
-       child->left = parent;
-       parent->parent = child;
-       *top = child;
-}/*RotateLeft*/
-
-static void RotateRight(udict_node_t **top)
-{
-       udict_node_t *parent = *top;
-       udict_node_t *child = parent->left;
-
-       child->parent = parent->parent;
-       parent->left = child->right;
-       parent->left->parent = parent;     /* may change sentinel.parent */
-       child->right = parent;
-       parent->parent = child;
-       *top = child;
-}/*RotateRight*/
-
-static void FixBalance(udict_node_t **pnode, udict_avl_balance_t bal)
-{
-       udict_node_t *node = *pnode;
-       udict_node_t *child;
-       udict_node_t *grandchild;
-
-       if (node->balance == BALANCED) {
-               node->balance = bal;
-       }/*if*/
-       else if (node->balance != bal) {
-               node->balance = BALANCED;
-       }/*elsif*/
-       else {
-               assert (node->balance == bal);
-
-               if (bal == LEFTHEAVY) {
-                       child = node->left;
-                       if (child->balance == LEFTHEAVY) {
-                               node->balance = BALANCED;
-                               child->balance = BALANCED;
-                               RotateRight(pnode);
-                       }/*if*/
-                       else if (child->balance == BALANCED) {
-                               /* only possible after delete */
-                               node->balance = LEFTHEAVY;
-                               child->balance = RIGHTHEAVY;
-                               RotateRight(pnode);
-                       }/*elsif*/
-                       else {
-                               assert (child->balance == RIGHTHEAVY);
-
-                               grandchild = child->right;
-                               if (grandchild->balance == LEFTHEAVY) {
-                                       node->balance = RIGHTHEAVY;
-                                       child->balance = BALANCED;
-                               }/*if*/
-                               else if (grandchild->balance == RIGHTHEAVY) {
-                                       node->balance = BALANCED;
-                                       child->balance = LEFTHEAVY;
-                               }/*elsif*/
-                               else {
-                                       node->balance = BALANCED;
-                                       child->balance = BALANCED;
-                               }/*else*/
-                               grandchild->balance = BALANCED;
-                               RotateLeft(&node->left);
-                               RotateRight(pnode);
-                       }/*else*/
-               }/*if*/
-               else {
-                       assert (bal == RIGHTHEAVY);
-
-                       child = node->right;
-                       if (child->balance == RIGHTHEAVY) {
-                               node->balance = BALANCED;
-                               child->balance = BALANCED;
-                               RotateLeft(pnode);
-                       }/*if*/
-                       else if (child->balance == BALANCED) {
-                               /* only possible after delete */
-                               node->balance = RIGHTHEAVY;
-                               child->balance = LEFTHEAVY;
-                               RotateLeft(pnode);
-                       }/*elsif*/
-                       else {
-                               assert (child->balance == LEFTHEAVY);
-
-                               grandchild = child->left;
-                               if (grandchild->balance == RIGHTHEAVY) {
-                                       node->balance = LEFTHEAVY;
-                                       child->balance = BALANCED;
-                               }/*if*/
-                               else if (grandchild->balance == LEFTHEAVY) {
-                                       node->balance = BALANCED;
-                                       child->balance = RIGHTHEAVY;
-                               }/*elsif*/
-                               else {
-                                       node->balance = BALANCED;
-                                       child->balance = BALANCED;
-                               }/*else*/
-                               grandchild->balance = BALANCED;
-                               RotateRight(&node->right);
-                               RotateLeft(pnode);
-                       }/*else*/
-               }/*else*/
-       }/*else*/
-}/*FixBalance*/
-
-static int Insert(udict_t *ud, udict_node_t *what, udict_node_t **where, udict_node_t *parent)
-{
-       udict_node_t *here = *where;
-       int result;
-
-       if (here == tree_null_priv(ud)) {
-               *where = what;
-               what->parent = parent;
-               return 1;                       /* higher than before */
-       }/*if*/
-       else {
-               result = ud->compare(ud, key(what), key(here));
-
-               assert (result != GenericEqual);
-
-               if (result == LESS) {
-                       if (Insert(ud, what, &here->left, here)) {
-                               /*
-                               ** now left side is higher than before
-                               */
-                               FixBalance(where, LEFTHEAVY);
-                               return ((*where)->balance != BALANCED);
-                       }/*if*/
-               }/*if*/
-               else {
-                       if (Insert(ud, what, &here->right, here)) {
-                               /*
-                               ** now right side is higher than before
-                               */
-                               FixBalance(where, RIGHTHEAVY);
-                               return ((*where)->balance != BALANCED);
-                       }/*if*/
-               }/*else*/
-       }/*else*/
-       return 0;                           /* height not changed */
-}/*Insert*/
-
-void avl_insert_node(udict_t *ud, udict_node_t *node)
-{
-       udict_node_t *nil = tree_null_priv(ud);
-
-       node->left = nil;
-       node->right = nil;
-       node->balance = BALANCED;
-
-       if (Insert(ud, node, &ud->BalancedRoot.left, nil)) {
-               nil->balance = LEFTHEAVY;
-       }/*if*/
-
-       if (ud->BalancedRoot.left == node) {
-               node->parent = &ud->BalancedRoot;
-               ud->BalancedRoot.balance = LEFTHEAVY;
-       }
-
-       ud->nodecount++;
-}
-
-void avl_delete_node(udict_t *ud, udict_node_t *node)
-{
-       udict_node_t *nil = tree_null_priv(ud);
-       udict_node_t *swap;
-       udict_node_t *child;
-       udict_node_t *parent;
-
-       udict_tree_delete(ud, node, &swap, &child);
-
-#ifndef NDEBUG
-       if (swap == node) {
-               /*
-               ** node had 0 or 1 child,
-               ** child moved up to node's place
-               */
-               if (child != nil) {
-                       assert ((child->left == nil) && (child->right == nil));
-                       assert (child->balance == BALANCED);
-               }/*if*/
-       }/*if*/
-       else {
-               /*
-               ** node had 2 children,
-               ** swap was node's successor (in node's right subtree),
-               ** swap has been inserted in node's place,
-               ** child was swap->right,
-               ** child has been moved to swap's place
-               */
-               if (child != nil) {
-                       assert ((child->left == nil) && (child->right == nil));
-                       assert (child->balance == BALANCED);
-               }/*if*/
-       }/*else*/
-#endif
-       swap->balance = node->balance;
-
-       /*
-       ** In either case, child has been moved to the next higher level.
-       ** So the balance of its new parent has to be checked.
-       ** Note, that child->parent points to the node we are interested in,
-       ** even if child == nil.
-       */
-
-       parent = child->parent;
-
-       if (parent == nil) {
-               /* root has been deleted */
-               if (child == nil) {
-                       parent->balance = BALANCED;
-                       ud->BalancedRoot.left = nil;
-               }/*if*/
-       }/*if*/
-
-       while (parent != &ud->BalancedRoot) {
-               if ((parent->left == nil) && (parent->right == nil)) {
-                       assert (child == nil);
-                       parent->balance = BALANCED;
-                       /* propagate height reduction to upper level */
-               }/*if*/
-               else {
-                       udict_node_t **pparent;
-                       if (parent == parent->parent->left)
-                               pparent = &parent->parent->left;
-                       else
-                               pparent = &parent->parent->right;
-
-                       if (child == parent->left) {
-                               /* reduce parent's left height */
-                               FixBalance(pparent, RIGHTHEAVY);
-                       }/*if*/
-                       else {
-                               assert (child == parent->right);
-                               /* reduce parent's right height */
-                               FixBalance(pparent, LEFTHEAVY);
-                       }/*else*/
-
-                       /*
-                       ** parent and child are not valid now,
-                       ** pparent may point to new root of subtree
-                       */
-                       parent = *pparent;
-               }/*else*/
-
-               /* if subtree is balanced, then height is less than before */
-               if (parent->balance == BALANCED) {
-                       child = parent;
-                       parent = child->parent;
-               }/*if*/
-               else
-                       break;
-       }/*while*/
-}/*avl_delete_node*/
-
-void *avl_get_data(udict_node_t *here) {
-       return data(here);
-}
-
-int avl_search(udict_t *ud, void *_key, udict_node_t *here, udict_node_t **where)
-{
-       int result;
-
-       if (avl_is_nil(ud, here))
-               return TableInsertAsLeft;
-
-       result = ud->compare(ud, _key, key(here));
-
-       if (result == EQUAL) {
-               *where = here;
-               return TableFoundNode;
-       }
-
-       if (result == LESS) {
-               if( here->left == tree_null_priv(ud) ) {
-                       *where = here;
-                       return TableInsertAsLeft;
-               }
-               return avl_search(ud, _key, here->left, where);
-       }/*if*/
-       else {
-               if( here->right == tree_null_priv(ud) ) {
-                       *where = here;
-                       return TableInsertAsRight;
-               }
-               return avl_search(ud, _key, here->right, where);
-       }/*else*/
-}
-
-int avl_is_nil(udict_t *ud, udict_node_t *node)
-{
-       return  tree_null_priv(ud) == node ||
-               &ud->BalancedRoot == node;
-}
-
-udict_node_t *avl_first(udict_t *ud)
-{
-       return udict_tree_first(ud);
-}
-
-udict_node_t *avl_last(udict_t *ud)
-{
-       return udict_tree_last(ud);
-}
-
-udict_node_t *avl_next(udict_t *ud, udict_node_t *prev)
-{
-       udict_node_t *node = udict_tree_next(ud, prev);
-       if( node == tree_null_priv(ud) || node == &ud->BalancedRoot )
-               return NULL;
-       else
-               return node;
-}
diff --git a/reactos/lib/rtl/austin/avl.h b/reactos/lib/rtl/austin/avl.h
deleted file mode 100644 (file)
index 575fb44..0000000
+++ /dev/null
@@ -1,26 +0,0 @@
-/*
- * COPYRIGHT:       See COPYING in the top level directory
- * PROJECT:         ReactOS System Libraries
- * FILE:            lib/rtl/austin/avl.h
- * PURPOSE:         Run-Time Libary Header (interface to austin AVL tree)
- * PROGRAMMER:      arty
- */
-
-#pragma once
-
-#define avl_data(x) ((void*)(&(x)[1]))
-
-void avl_init(PRTL_AVL_TABLE table);
-void avl_deinit(PRTL_AVL_TABLE table);
-void avl_insert_node(PRTL_AVL_TABLE table, PRTL_BALANCED_LINKS node);
-void avl_delete_node(PRTL_AVL_TABLE table, PRTL_BALANCED_LINKS node);
-int  avl_is_nil(PRTL_AVL_TABLE table, PRTL_BALANCED_LINKS node);
-PRTL_BALANCED_LINKS avl_first(PRTL_AVL_TABLE table);
-PRTL_BALANCED_LINKS avl_last(PRTL_AVL_TABLE table);
-PRTL_BALANCED_LINKS avl_next(PRTL_AVL_TABLE table, PRTL_BALANCED_LINKS node);
-
-int  avl_search
-(PRTL_AVL_TABLE table,
- PVOID _key,
- PRTL_BALANCED_LINKS node,
- PRTL_BALANCED_LINKS *where);
diff --git a/reactos/lib/rtl/austin/macros.h b/reactos/lib/rtl/austin/macros.h
deleted file mode 100644 (file)
index 2aaade9..0000000
+++ /dev/null
@@ -1,51 +0,0 @@
-/*
- * Austin---Astonishing Universal Search Tree Interface Novelty
- * Copyright (C) 2000 Kaz Kylheku <kaz@ashi.footprints.net>
- *
- * Free Software License:
- *
- * All rights are reserved by the author, with the following exceptions:
- * Permission is granted to freely reproduce and distribute this software,
- * possibly in exchange for a fee, provided that this copyright notice appears
- * intact. Permission is also granted to adapt this software to produce
- * derivative works, as long as the modified versions carry this copyright
- * notice and additional notices stating that the work has been modified.
- * This source code may be translated into executable form and incorporated
- * into proprietary software; there is no requirement for such software to
- * contain a copyright notice related to this source.
- *
- * $Id: macros.h,v 1.1 1999/11/26 05:59:49 kaz Exp $
- * $Name: austin_0_2 $
- */
-/*
- * Modified for use in ReactOS by arty
- */
-
-/*
- * Macros which give short, convenient internal names to public structure
- * members. These members have prefixed names to reduce the possiblity of
- * clashes with foreign macros.
- */
-
-#define left LeftChild
-#define right RightChild
-#define parent Parent
-#define next RightChild
-#define prev LeftChild
-#define data(x) ((void *)&((x)[1]))
-#define key(x) ((void *)&((x)[1]))
-#define rb_color udict_rb_color
-#define algo_specific udict_algo_specific
-
-#define optable udict_optable
-#define nodecount NumberGenericTableElements
-#define maxcount udict_maxcount
-#define dupes_allowed udict_dupes_allowed
-#define sentinel BalancedRoot
-#define compare CompareRoutine
-#define nodealloc AllocateRoutine
-#define nodefree FreeRoutine
-#define context TableContext
-
-#define assert(x) { if(!(x)) { RtlAssert(#x, __FILE__, __LINE__, NULL); } }
-
diff --git a/reactos/lib/rtl/austin/tree.c b/reactos/lib/rtl/austin/tree.c
deleted file mode 100644 (file)
index 57cc5b4..0000000
+++ /dev/null
@@ -1,292 +0,0 @@
-/*
- * Austin---Astonishing Universal Search Tree Interface Novelty
- * Copyright (C) 2000 Kaz Kylheku <kaz@ashi.footprints.net>
- *
- * Free Software License:
- *
- * All rights are reserved by the author, with the following exceptions:
- * Permission is granted to freely reproduce and distribute this software,
- * possibly in exchange for a fee, provided that this copyright notice appears
- * intact. Permission is also granted to adapt this software to produce
- * derivative works, as long as the modified versions carry this copyright
- * notice and additional notices stating that the work has been modified.
- * This source code may be translated into executable form and incorporated
- * into proprietary software; there is no requirement for such software to
- * contain a copyright notice related to this source.
- *
- * $Id: tree.c,v 1.8 1999/12/09 05:38:52 kaz Exp $
- * $Name: austin_0_2 $
- */
-/*
- * Modified for use in ReactOS by arty
- */
-#include "rtl.h"
-#include "udict.h"
-#include "tree.h"
-#include "macros.h"
-
-void udict_tree_delete(udict_t *ud, udict_node_t *node, udict_node_t **pswap, udict_node_t **pchild)
-{
-    udict_node_t *nil = tree_null_priv(ud), *child, *delparent = node->parent;
-    udict_node_t *next = node, *nextparent;
-
-    if( tree_root_priv(ud) == node )
-       delparent = &ud->BalancedRoot;
-
-    if (node->left != nil && node->right != nil) {
-       next = udict_tree_next(ud, node);
-       nextparent = next->parent;
-
-       if( tree_root_priv(ud) == next )
-           nextparent = &ud->BalancedRoot;
-
-       assert (next != nil);
-       assert (next->parent != nil);
-       assert (next->left == nil);
-
-       /*
-        * First, splice out the successor from the tree completely, by
-        * moving up its right child into its place.
-        */
-
-       child = next->right;
-       child->parent = nextparent;
-
-       if (nextparent->left == next) {
-           nextparent->left = child;
-       } else {
-           assert (nextparent->right == next);
-           nextparent->right = child;
-       }
-
-       /*
-        * Now that the successor has been extricated from the tree, install it
-        * in place of the node that we want deleted.
-        */
-
-       next->parent = delparent;
-       next->left = node->left;
-       next->right = node->right;
-       next->left->parent = next;
-       next->right->parent = next;
-
-       if (delparent->left == node) {
-           delparent->left = next;
-       } else {
-           assert (delparent->right == node);
-           delparent->right = next;
-       }
-
-    } else {
-       assert (node != nil);
-       assert (node->left == nil || node->right == nil);
-
-       child = (node->left != nil) ? node->left : node->right;
-       child->parent = delparent = node->parent;
-
-       if (node == delparent->left) {
-           delparent->left = child;
-       } else {
-           assert (node == delparent->right);
-           delparent->right = child;
-       }
-    }
-
-    node->parent = nil;
-    node->right = nil;
-    node->left = nil;
-
-    ud->nodecount--;
-
-    *pswap = next;
-    *pchild = child;
-}
-
-udict_node_t *udict_tree_lookup(udict_t *ud, const void *_key)
-{
-    udict_node_t *root = tree_root_priv(ud);
-    udict_node_t *nil = tree_null_priv(ud);
-    int result;
-
-    /* simple binary search adapted for trees that contain duplicate keys */
-
-    while (root != nil) {
-       result = ud->compare(ud, (void *)_key, key(root));
-       if (result < 0)
-           root = root->left;
-       else if (result > 0)
-           root = root->right;
-       else {
-           return root;
-       }
-    }
-
-    return 0;
-}
-
-udict_node_t *udict_tree_lower_bound(udict_t *ud, const void *_key)
-{
-    udict_node_t *root = tree_root_priv(ud);
-    udict_node_t *nil = tree_null_priv(ud);
-    udict_node_t *tentative = 0;
-
-    while (root != nil) {
-       int result = ud->compare(ud, (void *)_key, key(root));
-
-       if (result > 0) {
-           root = root->right;
-       } else if (result < 0) {
-           tentative = root;
-           root = root->left;
-       } else {
-           return root;
-       }
-    }
-
-    return tentative;
-}
-
-udict_node_t *udict_tree_upper_bound(udict_t *ud, const void *_key)
-{
-    udict_node_t *root = tree_root_priv(ud);
-    udict_node_t *nil = tree_null_priv(ud);
-    udict_node_t *tentative = 0;
-
-    while (root != nil) {
-       int result = ud->compare(ud, (void *)_key, key(root));
-
-       if (result < 0) {
-           root = root->left;
-       } else if (result > 0) {
-           tentative = root;
-           root = root->right;
-       } else {
-           return root;
-       }
-    }
-
-    return tentative;
-}
-
-udict_node_t *udict_tree_first(udict_t *ud)
-{
-    udict_node_t *nil = tree_null_priv(ud), *root = tree_root_priv(ud), *left;
-
-    if (root != nil)
-       while ((left = root->left) != nil)
-           root = left;
-
-    return (root == nil) ? 0 : root;
-}
-
-udict_node_t *udict_tree_last(udict_t *ud)
-{
-    udict_node_t *nil = tree_null_priv(ud), *root = tree_root_priv(ud), *right;
-
-    if (root != nil)
-       while ((right = root->right) != nil)
-           root = right;
-
-    return (root == nil) ? 0 : root;
-}
-
-udict_node_t *udict_tree_next(udict_t *ud, udict_node_t *curr)
-{
-    udict_node_t *nil = tree_null_priv(ud), *parent, *left;
-
-    if (curr->right != nil) {
-       curr = curr->right;
-       while ((left = curr->left) != nil)
-           curr = left;
-       return curr;
-    }
-
-    parent = curr->parent;
-
-    while (parent != nil && curr == parent->right) {
-       curr = parent;
-       parent = curr->parent;
-    }
-
-    return (parent == nil) ? 0 : parent;
-}
-
-udict_node_t *udict_tree_prev(udict_t *ud, udict_node_t *curr)
-{
-    udict_node_t *nil = tree_null_priv(ud), *parent, *right;
-
-    if (curr->left != nil) {
-       curr = curr->left;
-       while ((right = curr->right) != nil)
-           curr = right;
-       return curr;
-    }
-
-    parent = curr->parent;
-
-    while (parent != nil && curr == parent->left) {
-       curr = parent;
-       parent = curr->parent;
-    }
-
-    return (parent == nil) ? 0 : parent;
-}
-
-/*
- * Perform a ``left rotation'' adjustment on the tree.  The given parent node P
- * and its right child C are rearranged so that the P instead becomes the left
- * child of C.   The left subtree of C is inherited as the new right subtree
- * for P.  The ordering of the keys within the tree is thus preserved.
- */
-
-void udict_tree_rotate_left(udict_node_t *child, udict_node_t *parent)
-{
-    udict_node_t *leftgrandchild, *grandpa;
-
-    assert (parent->right == child);
-
-    child = parent->right;
-    parent->right = leftgrandchild = child->left;
-    leftgrandchild->parent = parent;
-
-    child->parent = grandpa = parent->parent;
-
-    if (parent == grandpa->left) {
-       grandpa->left = child;
-    } else {
-       assert (parent == grandpa->right);
-       grandpa->right = child;
-    }
-
-    child->left = parent;
-    parent->parent = child;
-}
-
-
-/*
- * This operation is the ``mirror'' image of rotate_left. It is
- * the same procedure, but with left and right interchanged.
- */
-
-void udict_tree_rotate_right(udict_node_t *child, udict_node_t *parent)
-{
-    udict_node_t *rightgrandchild, *grandpa;
-
-    assert (parent->left == child);
-
-    parent->left = rightgrandchild = child->right;
-    rightgrandchild->parent = parent;
-
-    child->parent = grandpa = parent->parent;
-
-    if (parent == grandpa->right) {
-       grandpa->right = child;
-    } else {
-       assert (parent == grandpa->left);
-       grandpa->left = child;
-    }
-
-    child->right = parent;
-    parent->parent = child;
-}
-
diff --git a/reactos/lib/rtl/austin/tree.h b/reactos/lib/rtl/austin/tree.h
deleted file mode 100644 (file)
index b729d23..0000000
+++ /dev/null
@@ -1,41 +0,0 @@
-/*
- * Austin---Astonishing Universal Search Tree Interface Novelty
- * Copyright (C) 2000 Kaz Kylheku <kaz@ashi.footprints.net>
- *
- * Free Software License:
- *
- * All rights are reserved by the author, with the following exceptions:
- * Permission is granted to freely reproduce and distribute this software,
- * possibly in exchange for a fee, provided that this copyright notice appears
- * intact. Permission is also granted to adapt this software to produce
- * derivative works, as long as the modified versions carry this copyright
- * notice and additional notices stating that the work has been modified.
- * This source code may be translated into executable form and incorporated
- * into proprietary software; there is no requirement for such software to
- * contain a copyright notice related to this source.
- *
- * $Id: tree.h,v 1.5 1999/12/09 05:38:52 kaz Exp $
- * $Name: austin_0_2 $
- */
-/*
- * Modified for use in ReactOS by arty
- */
-
-void udict_tree_init(udict_t *ud);
-void udict_tree_insert(udict_t *ud, udict_node_t *node, const void *key);
-void udict_tree_delete(udict_t *, udict_node_t *, udict_node_t **, udict_node_t **);
-udict_node_t *udict_tree_lookup(udict_t *, const void *);
-udict_node_t *udict_tree_lower_bound(udict_t *, const void *);
-udict_node_t *udict_tree_upper_bound(udict_t *, const void *);
-udict_node_t *udict_tree_first(udict_t *);
-udict_node_t *udict_tree_last(udict_t *);
-udict_node_t *udict_tree_next(udict_t *, udict_node_t *);
-udict_node_t *udict_tree_prev(udict_t *, udict_node_t *);
-void udict_tree_convert_to_list(udict_t *);
-void udict_tree_convert_from_list(udict_t *);
-void udict_tree_rotate_left(udict_node_t *, udict_node_t *);
-void udict_tree_rotate_right(udict_node_t *, udict_node_t *);
-
-#define tree_root_priv(T) ((T)->BalancedRoot.left)
-#define tree_null_priv(L) ((L)->BalancedRoot.parent)
-#define TREE_DEPTH_MAX 64
diff --git a/reactos/lib/rtl/austin/udict.h b/reactos/lib/rtl/austin/udict.h
deleted file mode 100644 (file)
index 47bb56f..0000000
+++ /dev/null
@@ -1,123 +0,0 @@
-/*
- * Austin---Astonishing Universal Search Tree Interface Novelty
- * Copyright (C) 2000 Kaz Kylheku <kaz@ashi.footprints.net>
- *
- * Free Software License:
- *
- * All rights are reserved by the author, with the following exceptions:
- * Permission is granted to freely reproduce and distribute this software,
- * possibly in exchange for a fee, provided that this copyright notice appears
- * intact. Permission is also granted to adapt this software to produce
- * derivative works, as long as the modified versions carry this copyright
- * notice and additional notices stating that the work has been modified.
- * This source code may be translated into executable form and incorporated
- * into proprietary software; there is no requirement for such software to
- * contain a copyright notice related to this source.
- *
- * $Id: udict.h,v 1.6 1999/12/09 07:32:48 kaz Exp $
- * $Name: austin_0_2 $
- */
-/*
- * Modified for use in ReactOS by arty
- */
-
-#pragma once
-
-#include <limits.h>
-
-#define WIN32_NO_STATUS
-#define _INC_SWPRINTF_INL_
-
-#include <windows.h>
-#include <ndk/ntndk.h>
-#include "avl.h"
-
-#define UDICT_COUNT_T_MAX ULONG_MAX
-typedef unsigned long udict_count_t;
-
-typedef unsigned int udict_alg_id_t;
-
-#define UDICT_LIST     0
-#define UDICT_BST      1
-#define UDICT_REDBLACK 2
-#define UDICT_SPLAY    3
-#define UDICT_AVL      4
-
-typedef enum {
-    udict_bst,
-    udict_list,
-    udict_other
-} udict_algkind_t;
-
-typedef enum {
-    udict_red,
-    udict_black
-} udict_rb_color_t;
-
-typedef enum {
-    udict_balanced = 0,
-    udict_leftheavy = 1,
-    udict_rightheavy = 2
-} udict_avl_balance_t;
-
-typedef union {
-    int udict_dummy;
-    udict_rb_color_t udict_rb_color;
-    udict_avl_balance_t udict_avl_balance;
-} udict_algdata_t;
-
-typedef struct _RTL_BALANCED_LINKS udict_node_t;
-
-typedef int (*udict_compare_t)(const void *, const void *);
-typedef udict_node_t *(*udict_nodealloc_t)(void *);
-typedef void (*udict_nodefree_t)(void *, udict_node_t *);
-
-typedef struct _RTL_AVL_TABLE udict_t;
-
-typedef struct udict_operations {
-    void (*udict_init)(udict_t *);
-    void (*udict_insert)(udict_t *, udict_node_t *, const void *);
-    void (*udict_delete)(udict_t *, udict_node_t *);
-    udict_node_t *(*udict_lookup)(udict_t *, const void *);
-    udict_node_t *(*udict_lower_bound)(udict_t *, const void *);
-    udict_node_t *(*udict_upper_bound)(udict_t *, const void *);
-    udict_node_t *(*udict_first)(udict_t *);
-    udict_node_t *(*udict_last)(udict_t *);
-    udict_node_t *(*udict_next)(udict_t *, udict_node_t *);
-    udict_node_t *(*udict_prev)(udict_t *, udict_node_t *);
-    void (*udict_convert_to_list)(udict_t *);
-    void (*udict_convert_from_list)(udict_t *);
-    udict_algkind_t udict_kind;
-} udict_operations_t;
-
-/* non-virtual dict methods */
-void udict_init(udict_t *, int, udict_count_t, udict_compare_t);
-udict_t *udict_create(int, udict_count_t, udict_compare_t);
-void udict_destroy(udict_t *);
-void udict_convert_to(udict_t *, int);
-udict_count_t udict_count(udict_t *);
-int udict_isempty(udict_t *);
-int udict_isfull(udict_t *);
-int udict_alloc_insert(udict_t *, const void *, void *);
-void udict_delete_free(udict_t *, udict_node_t *);
-void udict_set_allocator(udict_t *, udict_nodealloc_t, udict_nodefree_t, void *);
-void udict_allow_dupes(udict_t *);
-
-/* non-virtual node methods */
-void udict_node_init(udict_node_t *, void *);
-udict_node_t *udict_node_create(void *);
-void udict_node_destroy(udict_node_t *);
-void *udict_node_getdata(udict_node_t *);
-void udict_node_setdata(udict_node_t *, void *);
-const void *udict_node_getkey(udict_node_t *);
-
-/* virtual dict method wrappers */
-void udict_insert(udict_t *, udict_node_t *, const void *);
-void udict_delete(udict_t *, udict_node_t *);
-udict_node_t *udict_lookup(udict_t *, const void *);
-udict_node_t *udict_lower_bound(udict_t *, const void *);
-udict_node_t *udict_upper_bound(udict_t *, const void *);
-udict_node_t *udict_first(udict_t *);
-udict_node_t *udict_last(udict_t *);
-udict_node_t *udict_next(udict_t *, udict_node_t *);
-udict_node_t *udict_prev(udict_t *, udict_node_t *);
diff --git a/reactos/lib/rtl/avlsupp.c b/reactos/lib/rtl/avlsupp.c
new file mode 100644 (file)
index 0000000..b5546b7
--- /dev/null
@@ -0,0 +1,295 @@
+/*
+ * PROJECT:         ReactOS Runtime Library
+ * LICENSE:         BSD - See COPYING.ARM in the top level directory
+ * FILE:            lib/rtl/avlsupp.c
+ * PURPOSE:         AVL Tree Internal Support Routines/Main Algorithms
+ * PROGRAMMERS:     ReactOS Portable Systems Group
+ */
+
+/* INCLUDES ******************************************************************/
+
+/* Internal header for table entries */
+typedef struct _TABLE_ENTRY_HEADER
+{
+    RTL_BALANCED_LINKS BalancedLinks;
+    LIST_ENTRY ListEntry;
+    LONGLONG UserData;
+} TABLE_ENTRY_HEADER, *PTABLE_ENTRY_HEADER;
+
+typedef enum _RTL_AVL_BALANCE_FACTOR
+{
+    RtlUnbalancedAvlTree = -2,
+    RtlLeftHeavyAvlTree,
+    RtlBalancedAvlTree,
+    RtlRightHeavyAvlTree,
+} RTL_AVL_BALANCE_FACTOR;
+
+C_ASSERT(RtlBalancedAvlTree == 0);
+
+/* FUNCTIONS ******************************************************************/
+
+TABLE_SEARCH_RESULT
+FORCEINLINE
+RtlpFindAvlTableNodeOrParent(IN PRTL_AVL_TABLE Table,
+                             IN PVOID Buffer,
+                             OUT PRTL_BALANCED_LINKS *NodeOrParent)
+{
+    PRTL_BALANCED_LINKS CurrentNode, ChildNode;
+    RTL_GENERIC_COMPARE_RESULTS Result;
+
+    /* Quick check to see if the table is empty */
+    if (!Table->NumberGenericTableElements) return TableEmptyTree;
+
+    /* Set the current node */
+    CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
+
+    /* Start compare loop */
+    while (TRUE)
+    {
+        /* Compare which side is greater */
+        Result = RtlpAvlCompareRoutine(Table,
+                                       Buffer,
+                                       &((PTABLE_ENTRY_HEADER)CurrentNode)->
+                                       UserData);
+        if (Result == GenericLessThan)
+        {
+            /* We're less, check if this is the left child */
+            ChildNode = RtlLeftChildAvl(CurrentNode);
+            if (ChildNode)
+            {
+                /* Continue searching from this node */
+                CurrentNode = ChildNode;
+            }
+            else
+            {
+                /* Otherwise, the element isn't in this tree */
+                *NodeOrParent = CurrentNode;
+                return TableInsertAsLeft;
+            }
+        }
+        else if (Result == GenericGreaterThan)
+        {
+            /* We're more, check if this is the right child */
+            ChildNode = RtlRightChildAvl(CurrentNode);
+            if (ChildNode)
+            {
+                /* Continue searching from this node */
+                CurrentNode = ChildNode;
+            }
+            else
+            {
+                /* Otherwise, the element isn't in this tree */
+                *NodeOrParent = CurrentNode;
+                return TableInsertAsRight;
+            }
+        }
+        else
+        {
+            /* We should've found the node */
+            ASSERT(Result == GenericEqual);
+
+            /* Return node found */
+            *NodeOrParent = CurrentNode;
+            return TableFoundNode;
+        }
+    }
+}
+
+VOID
+FORCEINLINE
+RtlPromoteAvlTreeNode(IN PRTL_BALANCED_LINKS Node)
+{
+    PRTL_BALANCED_LINKS ParentNode, SuperParentNode;
+    PRTL_BALANCED_LINKS *SwapNode1, *SwapNode2;
+
+    /* Grab parents up to 2 levels high */
+    ParentNode = RtlParentAvl(Node);
+    SuperParentNode = RtlParentAvl(ParentNode);
+
+    /* Pick which nodes will be rotated */
+    SwapNode1 = RtlIsLeftChildAvl(Node) ? &ParentNode->LeftChild : &ParentNode->RightChild;
+    SwapNode2 = RtlIsLeftChildAvl(Node) ? &Node->RightChild : &Node->LeftChild;
+
+    /* Do the rotate, and update the parent and super-parent as needed */
+    *SwapNode1 = *SwapNode2;
+    if (*SwapNode1) RtlSetParent(*SwapNode1, ParentNode);
+    *SwapNode2 = ParentNode;
+    RtlSetParent(ParentNode, Node);
+
+    /* Now update the super-parent child link, and make it parent of the node*/
+    SwapNode1 = (RtlLeftChildAvl(SuperParentNode) == ParentNode) ?
+                 &SuperParentNode->LeftChild: &SuperParentNode->RightChild;
+    *SwapNode1 = Node;
+    RtlSetParent(Node, SuperParentNode);
+}
+
+BOOLEAN
+FORCEINLINE
+RtlpRebalanceAvlTreeNode(IN PRTL_BALANCED_LINKS Node)
+{
+    PRTL_BALANCED_LINKS ChildNode, SubChildNode;
+    CHAR Balance;
+    ASSERT(RtlParentAvl(Node) != Node);
+
+    /* Get the balance, and figure out which child node to go down on */
+    Balance = RtlBalance(Node);
+    ChildNode = (Balance == RtlRightHeavyAvlTree) ?
+                 RtlRightChildAvl(Node) : RtlLeftChildAvl(Node);
+
+    /* The child and node have the same balance, promote the child upwards */
+    if (RtlBalance(ChildNode) == Balance)
+    {
+        /* This performs the rotation described in Knuth A8-A10 for Case 1 */
+        RtlPromoteAvlTreeNode(ChildNode);
+        
+        /* The nodes are now balanced */
+        RtlSetBalance(ChildNode, RtlBalancedAvlTree);
+        RtlSetBalance(Node, RtlBalancedAvlTree);
+        return FALSE;
+    }
+
+    /* The child has the opposite balance, a double promotion of the child's child must happen */
+    if (RtlBalance(ChildNode) == -Balance)
+    {
+        /* Pick which sub-child to use based on the balance */
+        SubChildNode = (Balance == RtlRightHeavyAvlTree) ?
+                        RtlLeftChildAvl(ChildNode) : RtlRightChildAvl(ChildNode);
+
+        /* Do the double-rotation described in Knuth A8-A10 for Case 2 */
+        RtlPromoteAvlTreeNode(SubChildNode);
+        RtlPromoteAvlTreeNode(SubChildNode);
+
+        /* Was the sub-child sharing the same balance as the node? */
+        if (RtlBalance(SubChildNode) == Balance)
+        {
+            /* Then the subchild is now balanced, and the node's weight is inversed */
+            RtlSetBalance(ChildNode, RtlBalancedAvlTree);
+            RtlSetBalance(Node, -Balance);
+        }
+        else if (RtlBalance(SubChildNode) == -Balance)
+        {
+            /*
+             * In this case, the sub-child weight was the inverse of the node, so
+             * the child now shares the node's balance original weight, while the
+             * node becomes balanced.
+             */
+            RtlSetBalance(ChildNode, Balance);
+            RtlSetBalance(Node, RtlBalancedAvlTree);
+        }
+        else
+        {
+            /*
+             * Otherwise, the sub-child was unbalanced, so both the child and node
+             * now become balanced.
+             */
+            RtlSetBalance(ChildNode, RtlBalancedAvlTree);
+            RtlSetBalance(Node, RtlBalancedAvlTree);
+        }
+
+        /* In all cases, the sub-child is now balanced */
+        RtlSetBalance(SubChildNode, RtlBalancedAvlTree);
+        return FALSE;
+    }
+    
+    /*
+     * The case that remains is that the child was already balanced, so this is
+     * This is the rotation required for Case 3 in Knuth A8-A10
+     */
+    RtlPromoteAvlTreeNode(ChildNode);
+    
+    /* Now the child has the opposite weight of the node */
+    RtlSetBalance(ChildNode, -Balance);
+    
+    /* This only happens on deletion, so we return TRUE to terminate the delete */
+    return TRUE;
+}
+
+VOID
+FORCEINLINE
+RtlpInsertAvlTreeNode(IN PRTL_AVL_TABLE Table,
+                      IN PRTL_BALANCED_LINKS NewNode,
+                      IN OUT PVOID NodeOrParent,
+                      IN OUT TABLE_SEARCH_RESULT SearchResult)
+{
+    CHAR Balance;
+    
+    /* Initialize the new inserted element */
+    MI_ASSERT(SearchResult != TableFoundNode);
+    NewNode->LeftChild = NewNode->RightChild = NULL;
+
+    /* Increase element count */
+    Table->NumberGenericTableElements++;
+
+    /* Check where we should insert the entry */
+    if (SearchResult == TableEmptyTree)
+    {
+        /* This is the new root node */
+        RtlInsertAsRightChildAvl(&Table->BalancedRoot, NewNode);
+        MI_ASSERT(RtlBalance(NewNode) == RtlBalancedAvlTree);
+        
+        /* On AVL trees, we also update the depth */
+        ASSERT(Table->DepthOfTree == 0);
+        Table->DepthOfTree = 1;
+        return;
+    }
+    else if (SearchResult == TableInsertAsLeft)
+    {
+        /* Insert it left */
+        RtlInsertAsLeftChildAvl(NodeOrParent, NewNode);
+    }
+    else
+    {
+        /* Right node */
+        RtlInsertAsRightChildAvl(NodeOrParent, NewNode);
+    }
+
+    /* Little cheat to save on loop processing, taken from Timo */
+    MI_ASSERT(RtlBalance(NewNode) == RtlBalancedAvlTree);
+    RtlSetBalance(&Table->BalancedRoot, RtlLeftHeavyAvlTree);
+
+    /*
+     * This implements A6-A7 from Knuth based on http://coding.derkeiler.com
+     * /pdf/Archive/C_CPP/comp.lang.c/2004-01/1812.pdf, however the algorithm
+     * is slightly modified to follow the tree based on the Parent Node such
+     * as the Windows algorithm does it, instead of following the nodes down.
+     */
+    while (TRUE)
+    {
+        /* Calculate which side to balance on */
+        Balance = RtlIsLeftChildAvl(NewNode) ? RtlLeftHeavyAvlTree : RtlRightHeavyAvlTree;
+        
+        /* Check if the parent node was balanced */
+        if (RtlBalance(NodeOrParent) == RtlBalancedAvlTree)
+        {
+            /* It's not balanced anymore (heavy on one side) */
+            RtlSetBalance(NodeOrParent, Balance);
+            
+            /* Move up */
+            NewNode = NodeOrParent;
+            NodeOrParent = RtlParentAvl(NodeOrParent);
+        }
+        else if (RtlBalance(NodeOrParent) != Balance)
+        {
+            /* The parent's balance is opposite, so the tree is balanced now */
+            RtlSetBalance(NodeOrParent, RtlBalancedAvlTree);
+            
+            /* Check if this is the root (the cheat applied earlier gets us here) */
+            if (RtlBalance(&Table->BalancedRoot) == RtlBalancedAvlTree)
+            {
+                /* The depth has thus increased */
+                Table->DepthOfTree++;
+            }
+            
+            /* We reached the root or a balanced node, so we're done */
+            break;
+        }
+        else
+        {
+            /* The tree is now unbalanced, so AVL rebalancing must happen */
+            RtlpRebalanceAvlTreeNode(NodeOrParent);
+            break;
+        }
+    }
+}
+
+/* EOF */
diff --git a/reactos/lib/rtl/avltable.c b/reactos/lib/rtl/avltable.c
new file mode 100644 (file)
index 0000000..f85025b
--- /dev/null
@@ -0,0 +1,303 @@
+/*
+* PROJECT:         ReactOS Runtime Library
+* LICENSE:         BSD - See COPYING.ARM in the top level directory
+* FILE:            lib/rtl/avltable.c
+* PURPOSE:         AVL Tree Generic Table Implementation
+* PROGRAMMERS:     ReactOS Portable Systems Group
+*/
+
+/* INCLUDES ******************************************************************/
+
+#include <rtl.h>
+#define NDEBUG
+#include <debug.h>
+
+/* Include RTL version of AVL support */
+#include "rtlavl.h"
+#include "avlsupp.c"
+
+/* AVL FUNCTIONS *************************************************************/
+
+/*
+ * @implemented
+ */
+VOID
+NTAPI
+RtlInitializeGenericTableAvl(IN OUT PRTL_AVL_TABLE Table,
+                             IN PRTL_AVL_COMPARE_ROUTINE CompareRoutine,
+                             IN PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine,
+                             IN PRTL_AVL_FREE_ROUTINE FreeRoutine,
+                             IN PVOID TableContext)
+{
+    /* Setup the table */
+    RtlZeroMemory(Table, sizeof(RTL_AVL_TABLE));
+    Table->BalancedRoot.Parent = &Table->BalancedRoot;
+    Table->CompareRoutine = CompareRoutine;
+    Table->AllocateRoutine = AllocateRoutine;
+    Table->FreeRoutine = FreeRoutine;
+    Table->TableContext = TableContext;
+}
+
+/*
+ * @implemented
+ */
+PVOID
+NTAPI
+RtlInsertElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table,
+                                    IN PVOID Buffer,
+                                    IN ULONG BufferSize,
+                                    OUT PBOOLEAN NewElement OPTIONAL,
+                                    IN OUT PVOID NodeOrParent,
+                                    IN OUT TABLE_SEARCH_RESULT SearchResult)
+{
+    PRTL_BALANCED_LINKS NewNode;
+    PVOID UserData;
+
+    /* Check if the entry wasn't already found */
+    if (SearchResult != TableFoundNode)
+    {
+        /* We're doing an allocation, sanity check */
+        ASSERT(Table->NumberGenericTableElements != (MAXULONG - 1));
+
+        /* Allocate a node */
+        NewNode = Table->AllocateRoutine(Table,
+                                         BufferSize +
+                                         FIELD_OFFSET(TABLE_ENTRY_HEADER,
+                                                      UserData));
+        if (!NewNode)
+        {
+            /* No memory or other allocation error, fail */
+            if (NewElement) *NewElement = FALSE;
+            return NULL;
+        }
+        
+        /* Data to return to user */
+        UserData = &((PTABLE_ENTRY_HEADER)NewNode)->UserData;
+
+        /* Insert the node in the tree */
+        RtlpInsertAvlTreeNode(Table, NewNode, NodeOrParent, SearchResult);
+
+        /* Copy user buffer */
+        RtlCopyMemory(UserData, Buffer, BufferSize);
+    }
+    else
+    {
+        /* Return the node we already found */
+        NewNode = NodeOrParent;
+        UserData = &((PTABLE_ENTRY_HEADER)NewNode)->UserData;
+    }
+
+    /* Return status */
+    if (NewElement) *NewElement = (SearchResult == TableFoundNode);
+
+    /* Return pointer to user data */
+    return UserData;
+}
+
+/*
+ * @implemented
+ */
+PVOID
+NTAPI
+RtlInsertElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
+                                IN PVOID Buffer,
+                                IN ULONG BufferSize,
+                                OUT PBOOLEAN NewElement OPTIONAL)
+{
+    PRTL_BALANCED_LINKS NodeOrParent = NULL;
+    TABLE_SEARCH_RESULT Result;
+
+    /* Get the balanced links and table search result immediately */
+    Result = RtlpFindAvlTableNodeOrParent(Table, Buffer, &NodeOrParent);
+
+    /* Now call the routine to do the full insert */
+    return RtlInsertElementGenericTableFullAvl(Table,
+                                               Buffer,
+                                               BufferSize,
+                                               NewElement,
+                                               NodeOrParent,
+                                               Result);
+}
+
+/*
+ * @implemented
+ */
+BOOLEAN
+NTAPI
+RtlIsGenericTableEmptyAvl(IN PRTL_AVL_TABLE Table)
+{
+    /* If there's no elements, the table is empty */
+    return Table->NumberGenericTableElements == 0;
+}
+
+/*
+ * @implemented
+ */
+ULONG
+NTAPI
+RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table)
+{
+    /* Return the element count */
+    return Table->NumberGenericTableElements;
+}
+
+/*
+ * @implemented
+ */
+PVOID
+NTAPI
+RtlLookupElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table,
+                                    IN PVOID Buffer,
+                                    IN OUT PVOID *NodeOrParent,
+                                    IN OUT TABLE_SEARCH_RESULT *SearchResult)
+{
+    /* Find the node */
+    *SearchResult = RtlpFindAvlTableNodeOrParent(Table,
+                                                 Buffer,
+                                                 (PRTL_BALANCED_LINKS*)NodeOrParent);
+    if (*SearchResult != TableFoundNode) return NULL;
+
+    /* Node found, return the user data */
+    return &((PTABLE_ENTRY_HEADER)*NodeOrParent)->UserData;
+}
+
+/*
+ * @implemented
+ */
+PVOID
+NTAPI
+RtlLookupElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
+                                IN PVOID Buffer)
+{
+    PRTL_BALANCED_LINKS NodeOrParent;
+    TABLE_SEARCH_RESULT Lookup;
+
+    /* Call the full function */
+    return RtlLookupElementGenericTableFullAvl(Table,
+                                               Buffer,
+                                               (PVOID*)&NodeOrParent,
+                                               &Lookup);
+}
+
+/*
+ * @implemented
+ */
+PVOID
+NTAPI
+RtlEnumerateGenericTableAvl(IN PRTL_AVL_TABLE Table,
+                            IN BOOLEAN Restart)
+{
+    /* Reset the restart key if needed */
+    if (Restart) Table->RestartKey = NULL;
+
+    /* Call the full function */
+    return RtlEnumerateGenericTableWithoutSplayingAvl(Table,
+                                                      (PVOID*)&Table->RestartKey);
+}
+
+/*
+* @implemented
+*/
+PVOID
+NTAPI
+RtlLookupFirstMatchingElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
+                                             IN PVOID Buffer,
+                                             OUT PVOID *RestartKey)
+{
+    PRTL_BALANCED_LINKS Node, PreviousNode;
+    TABLE_SEARCH_RESULT SearchResult;
+    RTL_GENERIC_COMPARE_RESULTS Result = GenericEqual;
+
+    /* Assume failure */
+    *RestartKey = NULL;
+
+    /* Find the node */
+    SearchResult = RtlpFindAvlTableNodeOrParent(Table, Buffer, &Node);
+    if (SearchResult != TableFoundNode) return NULL;
+
+    /* Scan each predecessor until a match is found */
+    PreviousNode = Node;
+    while (Result == GenericEqual)
+    {
+        /* Save the node */
+        Node = PreviousNode;
+
+        /* Get the predecessor */
+        PreviousNode = RtlRealPredecessorAvl(Node);
+        if ((!PreviousNode) || (RtlParentAvl(PreviousNode) == PreviousNode)) break;
+
+        /* Check if this node matches */
+        Result = RtlpAvlCompareRoutine(Table,
+                                       Buffer,
+                                       &((PTABLE_ENTRY_HEADER)PreviousNode)->
+                                       UserData);
+    }
+
+    /* Save the node as the restart key, and return its data */
+    *RestartKey = Node;
+    return &((PTABLE_ENTRY_HEADER)Node)->UserData;
+}
+
+/*
+ * @unimplemented
+ */
+PVOID
+NTAPI
+RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table,
+                                           IN OUT PVOID *RestartKey)
+{
+    PRTL_BALANCED_LINKS CurrentNode;
+     
+    /* Skip an empty tree */
+    if (RtlIsGenericTableEmptyAvl(Table)) return NULL;
+
+    /* Check if we have a starting point */
+    if (!*RestartKey)
+    {
+        /* We'll have to find it, keep going until the leftmost child */
+        for (CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
+             RtlLeftChildAvl(CurrentNode);
+             CurrentNode = RtlLeftChildAvl(CurrentNode));
+
+        /* Found it */
+        *RestartKey = CurrentNode;
+    }
+    else
+    {
+        /* We already had a child, keep going by getting its successor */
+        CurrentNode = RtlRealSuccessorAvl(*RestartKey);
+
+        /* If there was one, update the restart key */
+        if (CurrentNode) *RestartKey = CurrentNode;
+    }
+    
+    /* Return the node's data if it was found, otherwise return NULL */
+    if (CurrentNode) return &((PTABLE_ENTRY_HEADER)CurrentNode)->UserData;
+    return NULL;
+}
+
+/*
+ * @unimplemented
+ */
+PVOID
+NTAPI
+RtlGetElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
+                             IN ULONG I)
+{
+    UNIMPLEMENTED;
+       return NULL;
+}
+
+/*
+ * @implemented
+ */
+BOOLEAN
+NTAPI
+RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
+                                IN PVOID Buffer)
+{
+    UNIMPLEMENTED;
+       return FALSE;
+}
+
+/* EOF */
index 272182d..dee9cf1 100644 (file)
@@ -1,16 +1,14 @@
 /*
-* PROJECT:         ReactOS Kernel
+* PROJECT:         ReactOS Runtime Library
 * LICENSE:         GPL - See COPYING in the top level directory
 * FILE:            lib/rtl/generictable.c
-* PURPOSE:         Splay Tree and AVL Tree Generic Table Implementation
+* PURPOSE:         Splay Tree Generic Table Implementation
 * PROGRAMMERS:     Alex Ionescu (alex.ionescu@reactos.org)
-*                  Art Yerks (ayerkes@speakeasy.net)
 */
 
 /* INCLUDES ******************************************************************/
 
 #include <rtl.h>
-#include "austin/avl.h"
 #define NDEBUG
 #include <debug.h>
 
@@ -508,261 +506,4 @@ RtlGetElementGenericTable(IN PRTL_GENERIC_TABLE Table,
                                                     ListEntry))->UserData;
 }
 
-/* AVL FUNCTIONS *************************************************************/
-
-/*
- * @implemented
- */
-PVOID
-NTAPI
-RtlLookupElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table,
-                                    IN PVOID Buffer,
-                                    IN OUT PVOID *NodeOrParent,
-                                    IN OUT TABLE_SEARCH_RESULT *SearchResult)
-{
-       PRTL_BALANCED_LINKS OurNodeOrParent;
-       TABLE_SEARCH_RESULT OurSearchResult;
-
-       if( !Table->NumberGenericTableElements )
-       {
-               *SearchResult = TableEmptyTree;
-               *NodeOrParent = NULL;
-               return NULL;
-       }
-
-       OurSearchResult = avl_search
-               (Table, Buffer,
-                Table->BalancedRoot.LeftChild, &OurNodeOrParent);
-
-       if(SearchResult) *SearchResult = OurSearchResult;
-       if(NodeOrParent) *NodeOrParent = OurNodeOrParent;
-
-       if(OurSearchResult == TableFoundNode)
-               return avl_data(OurNodeOrParent);
-       else
-               return NULL;
-}
-
-/*
- * @implemented
- */
-PVOID
-NTAPI
-RtlLookupElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
-                                IN PVOID Buffer)
-{
-       PRTL_BALANCED_LINKS OurNodeOrParent;
-       TABLE_SEARCH_RESULT OurSearchResult;
-       return RtlLookupElementGenericTableFullAvl
-       (Table, Buffer, (PVOID *)&OurNodeOrParent, &OurSearchResult);
-}
-
-/*
- * @implemented
- */
-BOOLEAN
-NTAPI
-RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
-                                IN PVOID Buffer)
-{
-       TABLE_SEARCH_RESULT Result;
-       PRTL_BALANCED_LINKS Node;
-
-       RtlLookupElementGenericTableFullAvl
-               ( Table, Buffer, (PVOID *)&Node, &Result );
-
-       if( Result == TableFoundNode )
-       {
-               avl_delete_node(Table, Node);
-               Table->FreeRoutine(Table, Node);
-               if( Table->NumberGenericTableElements == 0 )
-                       avl_deinit(Table);
-               return TRUE;
-       }
-       else
-       {
-               return FALSE;
-       }
-}
-
-/*
- * @implemented
- */
-PVOID
-NTAPI
-RtlEnumerateGenericTableAvl(IN PRTL_AVL_TABLE Table,
-                            IN BOOLEAN Restart)
-{
-       if( Table->NumberGenericTableElements == 0 )
-               return NULL;
-
-       if( Restart )
-       {
-               Table->RestartKey = avl_first(Table);
-       }
-       else
-       {
-               Table->RestartKey = avl_next(Table, Table->RestartKey);
-       }
-       if( !Table->RestartKey )
-               return NULL;
-       else
-               return avl_data(Table->RestartKey);
-}
-
-/*
- * @implemented
- */
-PVOID
-NTAPI
-RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table,
-                                           IN OUT PVOID *RestartKey)
-{
-    /* FIXME! */
-       return NULL;
-}
-
-/*
- * @implemented
- */
-PVOID
-NTAPI
-RtlGetElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
-                             IN ULONG I)
-{
-       PRTL_BALANCED_LINKS Node;
-
-       if( I >= Table->NumberGenericTableElements ) return NULL;
-       else
-       {
-               Node = avl_first(Table);
-               while(I--) Node = avl_next(Table, Node);
-               return avl_data(Node);
-       }
-}
-
-/*
- * @implemented
- */
-VOID
-NTAPI
-RtlInitializeGenericTableAvl(IN OUT PRTL_AVL_TABLE Table,
-                             IN PRTL_AVL_COMPARE_ROUTINE CompareRoutine,
-                             IN PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine,
-                             IN PRTL_AVL_FREE_ROUTINE FreeRoutine,
-                             IN PVOID TableContext)
-{
-    RtlZeroMemory(Table, sizeof(RTL_AVL_TABLE));
-    Table->BalancedRoot.Parent = &Table->BalancedRoot;
-    Table->CompareRoutine = CompareRoutine;
-    Table->AllocateRoutine = AllocateRoutine;
-    Table->FreeRoutine = FreeRoutine;
-    Table->TableContext = TableContext;
-}
-
-/*
- * @implemented
- */
-PVOID
-NTAPI
-RtlInsertElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table,
-                                    IN PVOID Buffer,
-                                    IN ULONG BufferSize,
-                                    OUT PBOOLEAN NewElement OPTIONAL,
-                                    IN OUT PVOID *NodeOrParent,
-                                    IN OUT TABLE_SEARCH_RESULT *SearchResult)
-{
-       PRTL_BALANCED_LINKS OurNodeOrParent;
-       TABLE_SEARCH_RESULT OurSearchResult;
-
-       if(Table->NumberGenericTableElements == 0) {
-               avl_init(Table);
-       }
-
-       if(NewElement)
-               *NewElement = FALSE;
-
-       OurSearchResult = avl_search
-               (Table, Buffer,
-                Table->BalancedRoot.LeftChild, &OurNodeOrParent);
-
-       if(NodeOrParent) *NodeOrParent = OurNodeOrParent;
-       if(SearchResult) *SearchResult = OurSearchResult;
-
-       if(OurSearchResult == TableFoundNode)
-       {
-               RtlDeleteElementGenericTableAvl(Table, Buffer);
-               return RtlInsertElementGenericTableFullAvl
-                       (Table, Buffer, BufferSize,
-                        NewElement, NodeOrParent, SearchResult);
-       }
-       else
-       {
-               PRTL_BALANCED_LINKS NewNode =
-                       Table->AllocateRoutine
-                       (Table,
-                        BufferSize + sizeof(RTL_BALANCED_LINKS) + BufferSize);
-
-               if( !NewNode ) return NULL;
-
-               NewNode->Balance = 0;
-               RtlCopyMemory(avl_data(NewNode), Buffer, BufferSize);
-
-               OurNodeOrParent = NewNode;
-
-               avl_insert_node(Table, NewNode);
-               return avl_data(NewNode);
-       }
-}
-
-/*
- * @implemented
- */
-PVOID
-NTAPI
-RtlInsertElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
-                                IN PVOID Buffer,
-                                IN ULONG BufferSize,
-                                OUT PBOOLEAN NewElement OPTIONAL)
-{
-       PVOID NodeOrParent;
-       TABLE_SEARCH_RESULT SearchResult;
-
-       return RtlInsertElementGenericTableFullAvl
-       (Table, Buffer, BufferSize, NewElement, &NodeOrParent, &SearchResult);
-}
-
-/*
- * @implemented
- */
-BOOLEAN
-NTAPI
-RtlIsGenericTableEmptyAvl(PRTL_AVL_TABLE Table)
-{
-    return Table->NumberGenericTableElements == 0;
-}
-
-/*
- * @implemented
- */
-ULONG
-NTAPI
-RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table)
-{
-    return Table->NumberGenericTableElements;
-}
-
-/*
-* @unimplemented
-*/
-PVOID
-NTAPI
-RtlLookupFirstMatchingElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
-                                             IN PVOID Buffer,
-                                             OUT PVOID *RestartKey)
-{
-    UNIMPLEMENTED;
-    return NULL;
-}
-
 /* EOF */
index 5627f5f..3f58ac0 100644 (file)
                <file>mem.c</file>
                <file>memgen.c</file>
        </if>
-       <directory name="austin">
-               <file>avl.c</file>
-               <file>tree.c</file>
-       </directory>
-
        <file>access.c</file>
        <file>acl.c</file>
        <file>actctx.c</file>
        <file>assert.c</file>
        <file>atom.c</file>
+       <file>avltable.c</file>
        <file>bitmap.c</file>
        <file>bootdata.c</file>
        <file>compress.c</file>
diff --git a/reactos/lib/rtl/rtlavl.h b/reactos/lib/rtl/rtlavl.h
new file mode 100644 (file)
index 0000000..b320ad4
--- /dev/null
@@ -0,0 +1,62 @@
+/*
+ * PROJECT:         ReactOS Runtime Library
+ * LICENSE:         BSD - See COPYING.ARM in the top level directory
+ * FILE:            lib/rtl/rtlavl.h
+ * PURPOSE:         RTL AVL Glue
+ * PROGRAMMERS:     ReactOS Portable Systems Group
+ */
+
+/* INCLUDES ******************************************************************/
+
+/*
+ * This is the glue code for the AVL package in the RTL meant for external callers.
+ * It's not very exciting, it just uses the RTL-defined fields without any magic,
+ * unlike the Mm version which has special handling for balances and parents, and
+ * does not implement custom comparison callbacks.
+ */
+#define MI_ASSERT(x)
+#define RtlLeftChildAvl(x)          (PRTL_BALANCED_LINKS)(RtlLeftChild(x))
+#define RtlRightChildAvl(x)         (PRTL_BALANCED_LINKS)(RtlRightChild(x))
+#define RtlParentAvl(x)             (PRTL_BALANCED_LINKS)(RtlParent(x))
+#define RtlRealPredecessorAvl(x)    (PRTL_BALANCED_LINKS)(RtlRealPredecessor((PRTL_SPLAY_LINKS)(x)))
+#define RtlRealSuccessorAvl(x)      (PRTL_BALANCED_LINKS)(RtlRealSuccessor((PRTL_SPLAY_LINKS)(x)))
+#define RtlInsertAsRightChildAvl    RtlInsertAsRightChild
+#define RtlInsertAsLeftChildAvl     RtlInsertAsLeftChild
+#define RtlIsLeftChildAvl           RtlIsLeftChild
+
+RTL_GENERIC_COMPARE_RESULTS
+FORCEINLINE
+RtlpAvlCompareRoutine(IN PRTL_AVL_TABLE Table,
+                      IN PVOID Buffer,
+                      IN PVOID UserData)
+{
+    /* Do the compare */
+    return Table->CompareRoutine(Table,
+                                 Buffer,
+                                 UserData);
+}
+
+VOID
+FORCEINLINE
+RtlSetParent(IN PRTL_BALANCED_LINKS Node,
+             IN PRTL_BALANCED_LINKS Parent)
+{
+    Node->Parent = Parent;
+}
+
+VOID
+FORCEINLINE
+RtlSetBalance(IN PRTL_BALANCED_LINKS Node,
+              IN CHAR Balance)
+{
+    Node->Balance = Balance;
+}
+
+CHAR
+FORCEINLINE
+RtlBalance(IN PRTL_BALANCED_LINKS Node)
+{
+    return Node->Balance;
+}
+
+/* EOF */
diff --git a/reactos/ntoskrnl/mm/ARM3/miavl.h b/reactos/ntoskrnl/mm/ARM3/miavl.h
new file mode 100644 (file)
index 0000000..e32d00a
--- /dev/null
@@ -0,0 +1,136 @@
+/*
+ * PROJECT:         ReactOS Kernel
+ * LICENSE:         BSD - See COPYING.ARM in the top level directory
+ * FILE:            ntoskrnl/mm/ARM3/miavl.h
+ * PURPOSE:         ARM Memory Manager VAD Node Algorithms
+ * PROGRAMMERS:     ReactOS Portable Systems Group
+ */
+
+/* INCLUDES ******************************************************************/
+
+/*
+ * This is the glue code for the Memory Manager version of AVL Trees that is used
+ * to store the MM_AVL_TABLE for Virtual Address Descriptors (VAD) in the VadRoot
+ * field in EPROCESS.
+ *
+ * In this version of the package, the balance and parent pointers are stored in
+ * the same field as a union (since we know the parent will be at least 8-byte
+ * aligned), saving some space, but requiring special logic to handle setting and
+ * querying the parent and balance.
+ *
+ * The other difference is that the AVL package for Rtl has custom callbacks for
+ * comparison purposes (which would access some internal, opaque, user data) while
+ * the Mm package stores the user-data inline as StartingVpn and EndingVpn. So 
+ * when a compare is being made, RtlpAvlCompareRoutine is called, which will either
+ * perform the Mm work, or call the user-specified callback in the Rtl case.
+ */
+#define PRTL_AVL_TABLE              PMM_AVL_TABLE
+#define PRTL_BALANCED_LINKS         PMMADDRESS_NODE
+#define MI_ASSERT(x)                ASSERT(x)
+
+RTL_GENERIC_COMPARE_RESULTS
+FORCEINLINE
+RtlpAvlCompareRoutine(IN PRTL_AVL_TABLE Table,
+                      IN PVOID Buffer,
+                      IN PVOID UserData)
+{
+    PRTL_BALANCED_LINKS CurrentNode = (PVOID)((ULONG_PTR)UserData - sizeof(LIST_ENTRY) - sizeof(RTL_BALANCED_LINKS));
+    ULONG_PTR StartingVpn = (ULONG_PTR)Buffer;
+    if (StartingVpn < CurrentNode->StartingVpn)
+    {
+        return GenericLessThan;
+    }
+    else if (StartingVpn <= CurrentNode->EndingVpn)
+    {
+        return GenericEqual;
+    }
+    else 
+    {
+        return GenericGreaterThan;
+    }
+}
+
+VOID
+FORCEINLINE
+RtlSetParent(IN PRTL_BALANCED_LINKS Node,
+             IN PRTL_BALANCED_LINKS Parent)
+{
+    Node->u1.Parent = (PRTL_BALANCED_LINKS)((ULONG_PTR)Parent | (Node->u1.Balance & 0x3));
+}
+
+VOID
+FORCEINLINE
+RtlSetBalance(IN PRTL_BALANCED_LINKS Node,
+              IN SCHAR Balance)
+{
+    Node->u1.Balance = Balance;
+}
+
+SCHAR
+FORCEINLINE
+RtlBalance(IN PRTL_BALANCED_LINKS Node)
+{
+    return Node->u1.Balance;
+}
+
+PRTL_BALANCED_LINKS
+FORCEINLINE
+RtlParentAvl(IN PRTL_BALANCED_LINKS Node)
+{
+    return (PRTL_BALANCED_LINKS)((ULONG_PTR)Node->u1.Parent & ~3);
+}
+
+BOOLEAN
+FORCEINLINE
+RtlIsRootAvl(IN PRTL_BALANCED_LINKS Node)
+{
+   return (RtlParentAvl(Node) == Node);
+}
+
+PRTL_BALANCED_LINKS
+FORCEINLINE
+RtlRightChildAvl(IN PRTL_BALANCED_LINKS Node)
+{
+    return Node->RightChild;
+}
+
+PRTL_BALANCED_LINKS
+FORCEINLINE
+RtlLeftChildAvl(IN PRTL_BALANCED_LINKS Node)
+{
+    return Node->LeftChild;
+}
+
+BOOLEAN
+FORCEINLINE
+RtlIsLeftChildAvl(IN PRTL_BALANCED_LINKS Node)
+{
+   return (RtlLeftChildAvl(RtlParentAvl(Node)) == Node);
+}
+
+BOOLEAN
+FORCEINLINE
+RtlIsRightChildAvl(IN PRTL_BALANCED_LINKS Node)
+{
+   return (RtlRightChildAvl(RtlParentAvl(Node)) == Node);
+}
+
+VOID
+FORCEINLINE
+RtlInsertAsLeftChildAvl(IN PRTL_BALANCED_LINKS Parent,
+                        IN PRTL_BALANCED_LINKS Node)
+{
+    Parent->LeftChild = Node;
+    RtlSetParent(Node, Parent);
+}
+
+VOID
+FORCEINLINE
+RtlInsertAsRightChildAvl(IN PRTL_BALANCED_LINKS Parent,
+                         IN PRTL_BALANCED_LINKS Node)
+{
+    Parent->RightChild = Node;
+    RtlSetParent(Node, Parent);
+}
+
+/* EOF */
diff --git a/reactos/ntoskrnl/mm/ARM3/vadnode.c b/reactos/ntoskrnl/mm/ARM3/vadnode.c
new file mode 100644 (file)
index 0000000..f87c585
--- /dev/null
@@ -0,0 +1,268 @@
+/*
+ * PROJECT:         ReactOS Kernel
+ * LICENSE:         BSD - See COPYING.ARM in the top level directory
+ * FILE:            ntoskrnl/mm/ARM3/vadnode.c
+ * PURPOSE:         ARM Memory Manager VAD Node Algorithms
+ * PROGRAMMERS:     ReactOS Portable Systems Group
+ */
+
+/* INCLUDES *******************************************************************/
+
+#include <ntoskrnl.h>
+#define NDEBUG
+#include <debug.h>
+
+#line 15 "ARMĀ³::VADNODE"
+#define MODULE_INVOLVED_IN_ARM3
+#include "../ARM3/miarm.h"
+
+/* Include Mm version of AVL support */
+#include "../ARM3/miavl.h"
+#include "../../../lib/rtl/avlsupp.c"
+
+/* FUNCTIONS ******************************************************************/
+
+PMMVAD
+NTAPI
+MiLocateAddress(IN PVOID VirtualAddress)
+{
+    PMMVAD FoundVad;
+    ULONG_PTR Vpn;
+    PMM_AVL_TABLE Table = &PsGetCurrentProcess()->VadRoot;
+    TABLE_SEARCH_RESULT SearchResult;
+
+    /* Start with the the hint */
+    FoundVad = (PMMVAD)Table->NodeHint;
+    if (!FoundVad) return NULL;
+
+    /* Check if this VPN is in the hint, if so, use it */
+    Vpn = (ULONG_PTR)VirtualAddress >> PAGE_SHIFT;
+    if ((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn)) return FoundVad;
+
+    /* VAD hint didn't work, go look for it */
+    SearchResult = RtlpFindAvlTableNodeOrParent(Table,
+                                                (PVOID)Vpn,
+                                                (PMMADDRESS_NODE*)&FoundVad);
+    if (SearchResult != TableFoundNode) return NULL;
+
+    /* We found it, update the hint */
+    ASSERT(FoundVad != NULL);
+    ASSERT((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn));
+    Table->NodeHint = FoundVad;
+    return FoundVad;
+}
+
+PMMADDRESS_NODE
+NTAPI
+MiCheckForConflictingNode(IN ULONG_PTR StartVpn,
+                          IN ULONG_PTR EndVpn,
+                          IN PMM_AVL_TABLE Table)
+{
+    PMMADDRESS_NODE CurrentNode;
+
+    /* If the tree is empty, there is no conflict */
+    if (!Table->NumberGenericTableElements) return NULL;
+
+    /* Start looping from the right */
+    CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
+    ASSERT(CurrentNode != NULL);
+    while (CurrentNode)
+    {
+        /* This address comes after */
+        if (StartVpn > CurrentNode->EndingVpn)
+        {
+            /* Keep searching on the right */
+            CurrentNode = RtlRightChildAvl(CurrentNode);
+        }
+        else if (EndVpn < CurrentNode->StartingVpn)
+        {
+            /* This address ends before the node starts, search on the left */
+            CurrentNode = RtlLeftChildAvl(CurrentNode);
+        }
+        else
+        {
+            /* This address is part of this node, return it */
+            break;
+        }
+    }
+    
+    /* Return either the conflicting node, or no node at all */
+    return CurrentNode;
+}
+
+VOID
+NTAPI
+MiInsertNode(IN PMMADDRESS_NODE NewNode,
+             IN PMM_AVL_TABLE Table)
+{
+    PMMADDRESS_NODE NodeOrParent = NULL;
+    TABLE_SEARCH_RESULT Result;
+
+    /* Find the node's parent, and where to insert this node */
+    Result = RtlpFindAvlTableNodeOrParent(Table,
+                                          (PVOID)NewNode->StartingVpn,
+                                          &NodeOrParent);
+    
+    /* Insert it into the tree */
+    RtlpInsertAvlTreeNode(Table, NewNode, NodeOrParent, Result);
+}
+
+PMMADDRESS_NODE
+NTAPI
+MiGetPreviousNode(IN PMMADDRESS_NODE Node)
+{
+    PMMADDRESS_NODE Parent;
+
+    /* Get the left child */
+    if (RtlLeftChildAvl(Node))
+    {
+        /* Get right-most child */
+        Node = RtlLeftChildAvl(Node);
+        while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
+        return Node;
+    }
+
+    Parent = RtlParentAvl(Node);
+    ASSERT(Parent != NULL);
+    while (Parent != Node)
+    {
+        /* The parent should be a right child, return the real predecessor */
+        if (RtlIsRightChildAvl(Node))
+        {
+            /* Return it unless it's the root */
+            if (Parent == RtlParentAvl(Parent)) Parent = NULL;
+            return Parent;
+        }
+        
+        /* Keep lopping until we find our parent */
+        Node = Parent;
+        Parent = RtlParentAvl(Node);
+    }
+    
+    /* Nothing found */
+    return NULL;
+}
+
+NTSTATUS
+NTAPI
+MiFindEmptyAddressRangeDownTree(IN SIZE_T Length,
+                                IN ULONG_PTR BoundaryAddress,
+                                IN ULONG_PTR Alignment,
+                                IN PMM_AVL_TABLE Table,
+                                OUT PULONG_PTR Base)
+{
+    PMMADDRESS_NODE Node, PreviousNode;
+    ULONG_PTR CandidateAddress, EndAddress;
+    ULONG AlignEndVpn, CandidateVpn, BoundaryVpn, LowestVpn, StartVpn, EndVpn;
+    PFN_NUMBER PageCount;
+
+    /* Sanity checks */
+    ASSERT(BoundaryAddress);
+    ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1));
+    
+    /* Compute page length, make sure the boundary address is valid */
+    Length = PAGE_ROUND_UP(Length);
+    if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY;
+    
+    /* Compute the highest address to start at */
+    CandidateAddress = ROUND_UP(BoundaryAddress + 1 - Length, Alignment);
+
+    /* Check if the table is empty */
+    if (!Table->NumberGenericTableElements)
+    {
+        /* Tree is empty, the candidate address is already the best one */
+        *Base = CandidateAddress;
+        return STATUS_SUCCESS;
+    }
+
+    /* Starting from the root, go down until the right-most child */
+    Node = RtlRightChildAvl(&Table->BalancedRoot);
+    while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
+
+    /* Get the aligned ending address of this VPN */
+    EndAddress = ROUND_UP((Node->EndingVpn << PAGE_SHIFT) | (PAGE_SIZE - 1),
+                          Alignment);
+
+    /* Can we fit the address without overflowing into the node? */
+    if ((EndAddress < BoundaryAddress) &&
+        ((BoundaryAddress - EndAddress) > Length))
+    {
+        /* There is enough space to add our address */
+        *Base = ROUND_UP(BoundaryAddress - Length, Alignment);
+        return STATUS_SUCCESS;
+    }
+    
+    PageCount = Length >> PAGE_SHIFT;
+    CandidateVpn = CandidateAddress >> PAGE_SHIFT;
+    BoundaryVpn = BoundaryAddress >> PAGE_SHIFT;
+    LowestVpn = (ULONG_PTR)MI_LOWEST_VAD_ADDRESS >> PAGE_SHIFT;
+         
+    PreviousNode = MiGetPreviousNode(Node);
+         
+    StartVpn = Node->StartingVpn;
+    EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0;
+    AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
+         
+    /* Loop until a gap is found */
+    for (PageCount = Length >> PAGE_SHIFT,
+         CandidateVpn = CandidateAddress >> PAGE_SHIFT,
+         BoundaryVpn = BoundaryAddress >> PAGE_SHIFT,
+         LowestVpn = (ULONG_PTR)MI_LOWEST_VAD_ADDRESS >> PAGE_SHIFT,
+         PreviousNode = MiGetPreviousNode(Node),
+         StartVpn = Node->StartingVpn,
+         EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0,
+         AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
+         PreviousNode;
+         Node = PreviousNode,
+         PreviousNode = MiGetPreviousNode(Node),
+         StartVpn = Node->StartingVpn,
+         EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0,
+         AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT))
+    {
+        /* Can we fit the address without overflowing into the node? */
+        if ((StartVpn < CandidateVpn) && ((StartVpn - AlignEndVpn) >= PageCount))
+        {
+            /* Check if we can get our candidate address */
+            if ((CandidateVpn > EndVpn) && (BoundaryVpn < StartVpn))
+            {
+                /* Use it */
+                *Base = CandidateAddress;
+                return STATUS_SUCCESS;
+            }
+            
+            /* Otherwise, can we fit it by changing the start address? */
+            if (StartVpn > AlignEndVpn)
+            {
+                /* It'll fit, compute the new base address for that to work */
+                *Base = ROUND_UP((StartVpn << PAGE_SHIFT) - Length, Alignment);
+                return STATUS_SUCCESS;
+            }
+        }
+        
+        PreviousNode = MiGetPreviousNode(Node);
+        StartVpn = Node->StartingVpn;
+        EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0;
+        AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
+    }
+
+    /* See if we could squeeze into the last descriptor */
+    if ((StartVpn > LowestVpn) && ((StartVpn - LowestVpn) >= PageCount))
+    {
+        /* Check if we can try our candidate address */
+        if (BoundaryVpn < StartVpn)
+        {
+            /* Use it */
+            *Base = CandidateAddress;
+            return STATUS_SUCCESS;
+        }
+
+        /* Otherwise, change the base address to what's needed to fit in */
+        *Base = ROUND_UP((StartVpn << PAGE_SHIFT) - Length, Alignment);
+        return STATUS_SUCCESS;
+    }
+        
+    /* No address space left at all */
+    return STATUS_NO_MEMORY;
+}
+
+/* EOF */
index fb21892..03ce565 100644 (file)
                        <file>procsup.c</file>
                        <file>sysldr.c</file>
                        <file>syspte.c</file>
+                       <file>vadnode.c</file>
                        <file>virtual.c</file>
                </directory>
                <file>anonmem.c</file>