10 Oct
2006
10 Oct
'06
12:31 p.m.
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 <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.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 <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: 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>