[arty] 24482: Added 'austin' AVL implementation and provide a binding for the AVL functions in generictable. Not tested, (but nothing relies on it yet). Austin is Copyright (C) 2000 Kaz Kylheku <[e-mail]> Copyright (C) 2000 Carl van Tast <[e-mail]> Copying, reuse and modification are permitted on liberal terms.

Author: arty
Date: Tue Oct 10 16:31:16 2006
New Revision: 24482

URL: http://svn.reactos.org/svn/reactos?rev=24482&view=rev
Log:
Added 'austin' AVL implementation and provide a binding for the AVL functions
in generictable.

Not tested, (but nothing relies on it yet).

Austin is
 Copyright (C) 2000 Kaz Kylheku <kaz(a)ashi.footprints.net>
 Copyright (C) 2000 Carl van Tast <vanTast(a)netway.at>

Copying, reuse and modification are permitted on liberal terms.

Added:
    trunk/reactos/lib/rtl/austin/
    trunk/reactos/lib/rtl/austin/avl.c
    trunk/reactos/lib/rtl/austin/avl.h
    trunk/reactos/lib/rtl/austin/macros.h
    trunk/reactos/lib/rtl/austin/tree.c
    trunk/reactos/lib/rtl/austin/tree.h
    trunk/reactos/lib/rtl/austin/udict.h
Modified:
    trunk/reactos/lib/rtl/generictable.c
    trunk/reactos/lib/rtl/rtl.rbuild

Added: trunk/reactos/lib/rtl/austin/avl.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/austin/avl.c?rev=2…
==============================================================================
--- trunk/reactos/lib/rtl/austin/avl.c (added)
+++ trunk/reactos/lib/rtl/austin/avl.c Tue Oct 10 16:31:16 2006
@@ -1,0 +1,345 @@
+/*
+ * Austin---Astonishing Universal Search Tree Interface Novelty
+ * Copyright (C) 2000 Kaz Kylheku <kaz(a)ashi.footprints.net>
+ * Copyright (C) 2000 Carl van Tast <vanTast(a)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 "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
+
+void avl_init(udict_t *ud)
+{
+	ud->sentinel.left = ud->sentinel.right = ud->sentinel.parent = 
+		&ud->sentinel;
+}
+
+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*/
+
+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*/
+
+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*/
+
+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));	
+
+		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, &nil->left, nil)) {
+		nil->balance = LEFTHEAVY;
+	}/*if*/
+
+	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;
+		}/*if*/
+	}/*if*/
+
+	while (parent != nil) {
+		if ((parent->left == nil) && (parent->right == nil)) {
+			assert (child == nil);
+			assert (parent->balance != BALANCED);
+			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*/
+
+int avl_search(udict_t *ud, void *_key, udict_node_t *here, udict_node_t **where)
+{
+	int result;
+
+	result = ud->compare(ud, _key, key(here));	
+
+	if (result == EQUAL) {
+		*where = here;
+		return TableFoundNode;
+	}
+
+	if (result == LESS) {
+		if( here->left == &ud->sentinel ) {
+			*where = here;
+			return TableInsertAsLeft;
+		}
+		return avl_search(ud, _key, here->left, where);
+	}/*if*/
+	else {
+		if( here->right == &ud->sentinel ) {
+			*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 &ud->sentinel == 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)
+{
+	return udict_tree_next(ud, prev);
+}

Added: trunk/reactos/lib/rtl/austin/avl.h
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/austin/avl.h?rev=2…
==============================================================================
--- trunk/reactos/lib/rtl/austin/avl.h (added)
+++ trunk/reactos/lib/rtl/austin/avl.h Tue Oct 10 16:31:16 2006
@@ -1,0 +1,29 @@
+/*
+ * 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
+ */
+
+#ifndef _REACTOS_RTL_LIB_AUSTIN_AVL_H
+#define _REACTOS_RTL_LIB_AUSTIN_AVL_H
+
+#define avl_data(x) ((void*)(&(x)[1]))
+
+void avl_init(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);
+
+
+#endif/*_REACTOS_RTL_LIB_AUSTIN_AVL_H*/

Added: trunk/reactos/lib/rtl/austin/macros.h
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/austin/macros.h?re…
==============================================================================
--- trunk/reactos/lib/rtl/austin/macros.h (added)
+++ trunk/reactos/lib/rtl/austin/macros.h Tue Oct 10 16:31:16 2006
@@ -1,0 +1,51 @@
+/*
+ * Austin---Astonishing Universal Search Tree Interface Novelty
+ * Copyright (C) 2000 Kaz Kylheku <kaz(a)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); } }
+

Added: trunk/reactos/lib/rtl/austin/tree.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/austin/tree.c?rev=…
==============================================================================
--- trunk/reactos/lib/rtl/austin/tree.c (added)
+++ trunk/reactos/lib/rtl/austin/tree.c Tue Oct 10 16:31:16 2006
@@ -1,0 +1,287 @@
+/*
+ * Austin---Astonishing Universal Search Tree Interface Novelty
+ * Copyright (C) 2000 Kaz Kylheku <kaz(a)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 "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 (node->left != nil && node->right != nil) {
+	next = udict_tree_next(ud, node);
+	nextparent = next->parent;
+
+	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 = 0;
+    node->right = 0;
+    node->left = 0;
+
+    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;
+}
+

Added: trunk/reactos/lib/rtl/austin/tree.h
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/austin/tree.h?rev=…
==============================================================================
--- trunk/reactos/lib/rtl/austin/tree.h (added)
+++ trunk/reactos/lib/rtl/austin/tree.h Tue Oct 10 16:31:16 2006
@@ -1,0 +1,41 @@
+/*
+ * Austin---Astonishing Universal Search Tree Interface Novelty
+ * Copyright (C) 2000 Kaz Kylheku &lt;kaz(a)ashi.footprints.net&gt;
+ *
+ * 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)->sentinel.left)
+#define tree_null_priv(L) (&(L)->sentinel)
+#define TREE_DEPTH_MAX 64

Added: trunk/reactos/lib/rtl/austin/udict.h
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/austin/udict.h?rev…
==============================================================================
--- trunk/reactos/lib/rtl/austin/udict.h (added)
+++ trunk/reactos/lib/rtl/austin/udict.h Tue Oct 10 16:31:16 2006
@@ -1,0 +1,126 @@
+/*
+ * Austin---Astonishing Universal Search Tree Interface Novelty
+ * Copyright (C) 2000 Kaz Kylheku &lt;kaz(a)ashi.footprints.net&gt;
+ *
+ * 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
+ */
+
+#ifndef UDICT_H
+#define UDICT_H
+
+#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,
+    udict_leftheavy,
+    udict_rightheavy
+} 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 *);
+
+#endif

Modified: trunk/reactos/lib/rtl/generictable.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/generictable.c?rev…
==============================================================================
--- trunk/reactos/lib/rtl/generictable.c (original)
+++ trunk/reactos/lib/rtl/generictable.c Tue Oct 10 16:31:16 2006
@@ -2,12 +2,13 @@
  * PROJECT:         ReactOS system libraries
  * PURPOSE:         Generic Table Implementation
  * FILE:            lib/rtl/genertictbl.c
- * PROGRAMMERS:     
+ * PROGRAMMERS:     arty
  */
 
 /* INCLUDES *****************************************************************/
 
 #include <rtl.h>
+#include "austin/avl.h"
 
 #define NDEBUG
 #include <debug.h>
@@ -17,6 +18,88 @@
 /*
 * @unimplemented
 */
+PVOID
+NTAPI
+RtlLookupElementGenericTable (
+	PRTL_GENERIC_TABLE Table,
+	PVOID Buffer
+	)
+{
+	UNIMPLEMENTED;
+	return 0;
+}
+
+/*
+* @unimplemented
+*/
+PVOID
+NTAPI
+RtlLookupElementGenericTableFull (
+	PRTL_GENERIC_TABLE Table,
+	PVOID Buffer,
+	OUT PVOID *NodeOrParent,
+	OUT TABLE_SEARCH_RESULT *SearchResult
+	)
+{
+	UNIMPLEMENTED;
+	return 0;
+}
+
+/*
+* @implemented
+*/
+PVOID
+NTAPI
+RtlLookupElementGenericTableFullAvl (
+	PRTL_AVL_TABLE Table,
+	PVOID Buffer,
+	OUT PVOID *NodeOrParent,
+	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, &OurNodeOrParent);
+
+	if(SearchResult) *SearchResult = OurSearchResult;
+	if(NodeOrParent) *NodeOrParent = OurNodeOrParent;
+
+	if(OurSearchResult == TableFoundNode)
+		return avl_data(OurNodeOrParent);
+	else
+		return NULL;
+}
+
+
+/*
+* @implemented
+*/
+PVOID
+NTAPI
+RtlLookupElementGenericTableAvl (
+	PRTL_AVL_TABLE Table,
+	PVOID Buffer
+	)
+{
+	PRTL_BALANCED_LINKS OurNodeOrParent;
+	TABLE_SEARCH_RESULT OurSearchResult;
+	return RtlLookupElementGenericTableFullAvl 
+	(Table, Buffer, (PVOID *)&OurNodeOrParent, &OurSearchResult);
+}
+
+
+/*
+* @unimplemented
+*/
 BOOLEAN
 NTAPI
 RtlDeleteElementGenericTable (
@@ -29,7 +112,7 @@
 }
 
 /*
-* @unimplemented
+* @implemented
 */
 BOOLEAN
 NTAPI
@@ -38,8 +121,22 @@
 	PVOID Buffer
 	)
 {
-	UNIMPLEMENTED;
-	return FALSE;
+	TABLE_SEARCH_RESULT Result;
+	PRTL_BALANCED_LINKS Node;
+
+	RtlLookupElementGenericTableFullAvl
+		( Table, Buffer, (PVOID *)&Node, &Result );
+
+	if( Result == TableFoundNode ) 
+	{
+		avl_delete_node(Table, Buffer);
+		Table->FreeRoutine(Table, Node);
+		return TRUE;
+	}
+	else
+	{
+		return FALSE;
+	}
 }
 
 /*
@@ -57,7 +154,7 @@
 }
 
 /*
-* @unimplemented
+* @implemented
 */
 PVOID
 NTAPI
@@ -66,7 +163,23 @@
 	BOOLEAN Restart
 	)
 {
-	UNIMPLEMENTED;
+	if( Table->NumberGenericTableElements == 0 )
+		return NULL;
+
+	if( Restart )
+	{
+		Table->RestartKey = avl_first(Table);
+		return avl_data(Table->RestartKey);
+	}
+	else
+	{
+		Table->RestartKey = avl_next(Table, Table->RestartKey);
+		if( avl_is_nil(Table, Table->RestartKey) )
+			return NULL;
+		else
+			return avl_data(Table->RestartKey);
+	}
+
 	return 0;
 }
 
@@ -104,7 +217,7 @@
 }
 
 /*
-* @unimplemented
+* @implemented
 */
 PVOID
 NTAPI
@@ -113,8 +226,7 @@
 	PVOID *RestartKey
 	)
 {
-	UNIMPLEMENTED;
-	return 0;
+	return RtlEnumerateGenericTableWithoutSplayingAvl(Table, RestartKey);
 }
 
 /*
@@ -132,7 +244,7 @@
 }
 
 /*
-* @unimplemented
+* @implemented
 */
 PVOID
 NTAPI
@@ -141,8 +253,15 @@
 	ULONG I
 	)
 {
-	UNIMPLEMENTED;
-	return 0;
+	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);
+	}
 }
 
 /*
@@ -182,11 +301,11 @@
   RtlZeroMemory(Table,
                 sizeof(RTL_AVL_TABLE));
   Table->BalancedRoot.Parent = &Table->BalancedRoot;
-
   Table->CompareRoutine = CompareRoutine;
   Table->AllocateRoutine = AllocateRoutine;
   Table->FreeRoutine = FreeRoutine;
   Table->TableContext = TableContext;
+  avl_init(Table);
 }
 
 
@@ -202,24 +321,8 @@
 	PBOOLEAN NewElement OPTIONAL
 	)
 {
-	UNIMPLEMENTED;
-	return 0;
-}
-
-/*
-* @unimplemented
-*/
-PVOID
-NTAPI
-RtlInsertElementGenericTableAvl (
-	PRTL_AVL_TABLE Table,
-	PVOID Buffer,
-	ULONG BufferSize,
-	PBOOLEAN NewElement OPTIONAL
-	)
-{
-	UNIMPLEMENTED;
-	return 0;
+    UNIMPLEMENTED;
+    return 0;
 }
 
 /*
@@ -241,7 +344,7 @@
 }
 
 /*
-* @unimplemented
+* @implemented
 */
 PVOID
 NTAPI
@@ -250,12 +353,71 @@
 	PVOID Buffer,
 	ULONG BufferSize,
 	PBOOLEAN NewElement OPTIONAL,
-	PVOID NodeOrParent,
-	TABLE_SEARCH_RESULT SearchResult
-	)
-{
-	UNIMPLEMENTED;
-	return 0;
+	PVOID *NodeOrParent,
+	TABLE_SEARCH_RESULT *SearchResult
+	)
+{
+	PRTL_BALANCED_LINKS OurNodeOrParent;
+	TABLE_SEARCH_RESULT OurSearchResult;
+
+	if(NewElement)
+		*NewElement = FALSE;
+
+	if( Table->NumberGenericTableElements )
+	{
+		OurSearchResult = TableEmptyTree;
+		OurNodeOrParent = NULL;
+		return NULL;
+	}
+
+	OurSearchResult = avl_search
+		(Table, Buffer, &Table->BalancedRoot, &OurNodeOrParent);
+
+	if(NodeOrParent) *NodeOrParent = OurNodeOrParent;
+	if(SearchResult) *SearchResult = OurSearchResult;
+
+	if(OurSearchResult == TableFoundNode) 
+	{
+		if(NewElement)
+			*NewElement = TRUE;
+		RtlCopyMemory(avl_data(OurNodeOrParent), Buffer, BufferSize);
+		return avl_data(OurNodeOrParent);
+	}
+	else
+	{
+		PRTL_BALANCED_LINKS NewNode = 
+			Table->AllocateRoutine
+			(Table, 
+			 BufferSize + sizeof(RTL_BALANCED_LINKS) + BufferSize);
+
+		if( !NewNode ) return NULL;
+
+		RtlCopyMemory(avl_data(NewNode), Buffer, BufferSize);
+
+		OurNodeOrParent = NewNode;
+
+		avl_insert_node(Table, NewNode);
+		return avl_data(NewNode);
+	}
+}
+
+/*
+* @implemented
+*/
+PVOID
+NTAPI
+RtlInsertElementGenericTableAvl (
+	PRTL_AVL_TABLE Table,
+	PVOID Buffer,
+	ULONG BufferSize,
+	PBOOLEAN NewElement OPTIONAL
+	)
+{
+	PVOID NodeOrParent;
+	TABLE_SEARCH_RESULT SearchResult;
+
+	return RtlInsertElementGenericTableFullAvl
+	(Table, Buffer, BufferSize, NewElement, &NodeOrParent, &SearchResult);
 }
 
 
@@ -281,69 +443,7 @@
 	PRTL_AVL_TABLE Table
 	)
 {
-	UNIMPLEMENTED;
-	return FALSE;
-}
-
-
-/*
-* @unimplemented
-*/
-PVOID
-NTAPI
-RtlLookupElementGenericTable (
-	PRTL_GENERIC_TABLE Table,
-	PVOID Buffer
-	)
-{
-	UNIMPLEMENTED;
-	return 0;
-}
-
-/*
-* @unimplemented
-*/
-PVOID
-NTAPI
-RtlLookupElementGenericTableAvl (
-	PRTL_AVL_TABLE Table,
-	PVOID Buffer
-	)
-{
-	UNIMPLEMENTED;
-	return 0;
-}
-
-/*
-* @unimplemented
-*/
-PVOID
-NTAPI
-RtlLookupElementGenericTableFull (
-	PRTL_GENERIC_TABLE Table,
-	PVOID Buffer,
-	OUT PVOID *NodeOrParent,
-	OUT TABLE_SEARCH_RESULT *SearchResult
-	)
-{
-	UNIMPLEMENTED;
-	return 0;
-}
-
-/*
-* @unimplemented
-*/
-PVOID
-NTAPI
-RtlLookupElementGenericTableFullAvl (
-	PRTL_AVL_TABLE Table,
-	PVOID Buffer,
-	OUT PVOID *NodeOrParent,
-	OUT TABLE_SEARCH_RESULT *SearchResult
-	)
-{
-	UNIMPLEMENTED;
-	return 0;
+	return Table->NumberGenericTableElements == 0;
 }
 
 

Modified: trunk/reactos/lib/rtl/rtl.rbuild
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/rtl.rbuild?rev=244…
==============================================================================
--- trunk/reactos/lib/rtl/rtl.rbuild (original)
+++ trunk/reactos/lib/rtl/rtl.rbuild Tue Oct 10 16:31:16 2006
@@ -40,6 +40,10 @@
 			<file>tan_asm.s</file>
 		</directory>
 	</if>
+	<directory name="austin">
+		<file>avl.c</file>
+		<file>tree.c</file>
+	</directory>
 
       <ifnot property="ARCH" value="i386">
              <file>memgen.c</file>