[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 <kaz@ashi.footprints.net> Copyright (C) 2000 Carl van Tast <vanTast@netway.at> 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@ashi.footprints.net Copyright (C) 2000 Carl van Tast vanTast@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=24... ============================================================================== --- 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@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 "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=24... ============================================================================== --- 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?rev... ============================================================================== --- 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@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=2... ============================================================================== --- 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@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=2... ============================================================================== --- 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@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@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=2448... ============================================================================== --- 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>
-
arty＠svn.reactos.org