diff options
Diffstat (limited to 'source3/ubiqx/ubi_AVLtree.h')
| -rw-r--r-- | source3/ubiqx/ubi_AVLtree.h | 114 |
1 files changed, 23 insertions, 91 deletions
diff --git a/source3/ubiqx/ubi_AVLtree.h b/source3/ubiqx/ubi_AVLtree.h index b86f24a412..61aaf99348 100644 --- a/source3/ubiqx/ubi_AVLtree.h +++ b/source3/ubiqx/ubi_AVLtree.h @@ -34,85 +34,20 @@ * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. * * -------------------------------------------------------------------------- ** + * Log: ubi_AVLtree.h,v + * 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. - * - * 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 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! * - * 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 + * Revision 1; 93/10/15 - 95/03/05: + * Added the ubi_tr defines. See ubi_BinTree.h for more info. * * V0.0 - May, 1990 - Written by Christopher R. Hertel (CRH). * @@ -128,6 +63,7 @@ * 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 @@ -142,25 +78,21 @@ * 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 - *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'd name for an avl tree node. */ +typedef struct ubi_avlNodeStruct + { + struct ubi_avlNodeStruct *leftlink; + struct ubi_avlNodeStruct *Link[2]; + signed char gender; + signed char balance; + } 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 ); |