diff options
author | Christopher R. Hertel <crh@samba.org> | 1997-12-24 02:50:19 +0000 |
---|---|---|
committer | Christopher R. Hertel <crh@samba.org> | 1997-12-24 02:50:19 +0000 |
commit | 6f429912e7a2d8c3f83a92adb914cd89a55af43d (patch) | |
tree | 92bda004f69b428ea2d3a2a2d4390f877e715734 /source3/ubiqx/ubi_AVLtree.h | |
parent | 08bd3b8cc0ed557e8fa9769c053b456ba0fa457e (diff) | |
download | samba-6f429912e7a2d8c3f83a92adb914cd89a55af43d.tar.gz samba-6f429912e7a2d8c3f83a92adb914cd89a55af43d.tar.bz2 samba-6f429912e7a2d8c3f83a92adb914cd89a55af43d.zip |
Backed out changes that attempted to address a pointer array using -1,0,1.
Jeremy pointed out that there might be problems with this. Darn shame.
(This used to be commit ce9acc96a6cbc91f0a3f95221c3e8f801cbdb602)
Diffstat (limited to 'source3/ubiqx/ubi_AVLtree.h')
-rw-r--r-- | source3/ubiqx/ubi_AVLtree.h | 118 |
1 files changed, 94 insertions, 24 deletions
diff --git a/source3/ubiqx/ubi_AVLtree.h b/source3/ubiqx/ubi_AVLtree.h index c7cac0ed1e..ebae7f3c13 100644 --- a/source3/ubiqx/ubi_AVLtree.h +++ b/source3/ubiqx/ubi_AVLtree.h @@ -35,22 +35,89 @@ * * -------------------------------------------------------------------------- ** * Log: ubi_AVLtree.h,v - * Revision 3.1 1997/12/18 06:27:01 crh - * Fixed some comment bugs. + * Revision 2.5 1997/12/23 04:00:15 crh + * In this version, all constants & macros defined in the header file have + * the ubi_tr prefix. Also cleaned up anything that gcc complained about + * when run with '-pedantic -fsyntax-only -Wall'. * - * Revision 3.0 1997/12/08 05:39:01 crh - * This is a new major revision level. The handling of the pointers in the - * ubi_trNode structure was redesigned. The result is that there are fewer - * macros floating about, and fewer cases in which values have to be - * incremented or decremented. See ubi_BinTree for more information. + * Revision 2.4 1997/07/26 04:36:23 crh + * Andrew Leppard, aka "Grazgur", discovered that I still had my brains tied + * on backwards with respect to node deletion. I did some more digging and + * discovered that I was not changing the balance values correctly in the + * single rotation functions. Double rotation was working correctly because + * the formula for changing the balance values is the same for insertion or + * deletion. Not so for single rotation. * - * Revision 2; 1995/03/05 - 1997/12/07: - * An overhaul to the node delete process. I had gotten it wrong in a - * couple of places, thought I'd fixed it, and then found that I'd missed - * something more. Thanks to Andrew Leppard for the bug report! + * I have tested the fix by loading the tree with over 44 thousand names, + * deleting 2,629 of them (all those in which the second character is 'u') + * and then walking the tree recursively to verify that the balance factor of + * each node is correct. Passed. + * + * Thanks Andrew! + * + * Also: + * + Changed ubi_TRUE and ubi_FALSE to ubi_trTRUE and ubi_trFALSE. + * + Rewrote the ubi_tr<func> macros because they weren't doing what I'd + * hoped they would do (see the bottom of the header file). They work now. + * + * Revision 2.3 1997/06/03 05:22:07 crh + * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing + * problems. + * + * Revision 2.2 1995/10/03 22:15:47 CRH + * Ubisized! + * + * Revision 2.1 95/03/09 23:46:44 CRH + * Added the ModuleID static string and function. These modules are now + * self-identifying. * - * Revision 1; 93/10/15 - 95/03/05: - * Added the ubi_tr defines. See ubi_BinTree.h for more info. + * Revision 2.0 95/03/05 14:11:22 CRH + * This revision of ubi_AVLtree coincides with revision 2.0 of ubi_BinTree, + * and so includes all of the changes to that module. In addition, a bug in + * the node deletion process has been fixed. + * + * After rewriting the Locate() function in ubi_BinTree, I decided that it was + * time to overhaul this module. In the process, I discovered a bug related + * to node deletion. To fix the bug, I wrote function Debalance(). A quick + * glance will show that it is very similar to the Rebalance() function. In + * previous versions of this module, I tried to include the functionality of + * Debalance() within Rebalance(), with poor results. + * + * Revision 1.0 93/10/15 22:58:48 CRH + * With this revision, I have added a set of #define's that provide a single, + * standard API to all existing tree modules. Until now, each of the three + * existing modules had a different function and typedef prefix, as follows: + * + * Module Prefix + * ubi_BinTree ubi_bt + * ubi_AVLtree ubi_avl + * ubi_SplayTree ubi_spt + * + * To further complicate matters, only those portions of the base module + * (ubi_BinTree) that were superceeded in the new module had the new names. + * For example, if you were using ubi_AVLtree, the AVL node structure was + * named "ubi_avlNode", but the root structure was still "ubi_btRoot". Using + * SplayTree, the locate function was called "ubi_sptLocate", but the next + * and previous functions remained "ubi_btNext" and "ubi_btPrev". + * + * This was not too terrible if you were familiar with the modules and knew + * exactly which tree model you wanted to use. If you wanted to be able to + * change modules (for speed comparisons, etc), things could get messy very + * quickly. + * + * So, I have added a set of defined names that get redefined in any of the + * descendant modules. To use this standardized interface in your code, + * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with + * "ubi_tr". The "ubi_tr" names will resolve to the correct function or + * datatype names for the module that you are using. Just remember to + * include the header for that module in your program file. Because these + * names are handled by the preprocessor, there is no added run-time + * overhead. + * + * Note that the original names do still exist, and can be used if you wish + * to write code directly to a specific module. This should probably only be + * done if you are planning to implement a new descendant type, such as + * red/black trees. CRH * * V0.0 - May, 1990 - Written by Christopher R. Hertel (CRH). * @@ -66,7 +133,6 @@ * header so that you can use the structure as a building block. * * The fields are as follows: - * leftlink - A space filler. This field will be accessed as Link[-1]. * Link - An array of pointers. These pointers are manipulated by the * BT and AVL routines, and indicate the left and right child * nodes, plus the parent node. By keeping track of the parent @@ -81,21 +147,25 @@ * indicates which subtree of the current node is longer, or if * the subtrees are, in fact, balanced with respect to each * other. - * + * ------------------------------------------------------------------------- ** */ -typedef struct ubi_avlNodeStruct - { - struct ubi_avlNodeStruct *leftlink; - struct ubi_avlNodeStruct *Link[2]; - signed char gender; - signed char balance; - } ubi_avlNode; +typedef struct ubi_avlNodeStruct { + struct ubi_avlNodeStruct + *Link[3]; /* Normal Binary Tree Node type. */ + char gender; /* The node is either the RIGHT or LEFT child of its */ + /* parent, or is the root node. */ + char balance; /* In an AVL tree, each node is the root of a subtree */ + /* that may be balanced, or be one node longer to the */ + /* right or left. This field keeps track of the */ + /* balance value of each node. */ + } ubi_avlNode; -typedef ubi_avlNode *ubi_avlNodePtr; /* a Pointer to an AVL node. */ +typedef ubi_avlNode *ubi_avlNodePtr; /* a Pointer to an AVL node */ /* -------------------------------------------------------------------------- ** - * Function prototypes... + * Function prototypes. + * -------------------------------------------------------------------------- ** */ ubi_avlNodePtr ubi_avlInitNode( ubi_avlNodePtr NodePtr ); |