diff options
| -rw-r--r-- | source3/ubiqx/ubi_AVLtree.c | 338 | ||||
| -rw-r--r-- | source3/ubiqx/ubi_AVLtree.h | 114 | ||||
| -rw-r--r-- | source3/ubiqx/ubi_BinTree.c | 302 | ||||
| -rw-r--r-- | source3/ubiqx/ubi_BinTree.h | 272 | ||||
| -rw-r--r-- | source3/ubiqx/ubi_SplayTree.c | 128 | ||||
| -rw-r--r-- | source3/ubiqx/ubi_SplayTree.h | 69 |
6 files changed, 505 insertions, 718 deletions
diff --git a/source3/ubiqx/ubi_AVLtree.c b/source3/ubiqx/ubi_AVLtree.c index 29ecc74740..6ad4053dfa 100644 --- a/source3/ubiqx/ubi_AVLtree.c +++ b/source3/ubiqx/ubi_AVLtree.c @@ -9,10 +9,6 @@ * This module provides an implementation of AVL height balanced binary * trees. (Adelson-Velskii, Landis 1962) * - * This file implements the core of the height-balanced (AVL) tree management - * routines. The header file, ubi_AVLtree.h, contains function prototypes - * for all "exported" functions. - * * -------------------------------------------------------------------------- ** * * This library is free software; you can redistribute it and/or @@ -31,84 +27,20 @@ * * -------------------------------------------------------------------------- ** * - * Revision 2.4 1997/07/26 04:36:20 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 04:41:35 crh - * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing - * problems. - * - * Revision 2.2 1995/10/03 22:16:01 CRH - * Ubisized! - * - * Revision 2.1 95/03/09 23:45:59 CRH - * Added the ModuleID static string and function. These modules are now - * self-identifying. - * - * Revision 2.0 95/03/05 14:10:51 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:56 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. + * Log: ubi_AVLtree.c,v + * Revision 3.0 1997/12/08 05:38:55 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. * - * 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. + * 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 missing + * something more. Thanks to Andrew Leppard for the bug report! * - * 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). * @@ -123,8 +55,8 @@ */ static char ModuleID[] = "ubi_AVLtree\n\ -\tRevision: 2.4\n\ -\tDate: 1997/07/26 04:36:20\n\ +\tRevision: 3.0\n\ +\tDate: 1997/12/08 05:38:55\n\ \tAuthor: crh\n"; /* ========================================================================== ** @@ -153,22 +85,22 @@ static ubi_avlNodePtr L1( ubi_avlNodePtr p ) { ubi_avlNodePtr tmp; - tmp = p->Link[RIGHT]; - p->Link[RIGHT] = tmp->Link[LEFT]; - tmp->Link[LEFT] = p; - - tmp->Link[PARENT] = p->Link[PARENT]; - tmp->gender = p->gender; - if(tmp->Link[PARENT]) - (tmp->Link[PARENT])->Link[(tmp->gender)] = tmp; - p->Link[PARENT] = tmp; - p->gender = LEFT; - if( p->Link[RIGHT] ) + tmp = p->Link[ubi_trRIGHT]; + p->Link[ubi_trRIGHT] = tmp->Link[ubi_trLEFT]; + tmp->Link[ubi_trLEFT] = p; + + tmp->Link[ubi_trPARENT] = p->Link[ubi_trPARENT]; + tmp->gender = p->gender; + if(tmp->Link[ubi_trPARENT]) + (tmp->Link[ubi_trPARENT])->Link[(tmp->gender)] = tmp; + p->Link[ubi_trPARENT] = tmp; + p->gender = ubi_trLEFT; + if( p->Link[ubi_trRIGHT] ) { - p->Link[RIGHT]->Link[PARENT] = p; - (p->Link[RIGHT])->gender = RIGHT; + p->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = p; + (p->Link[ubi_trRIGHT])->gender = ubi_trRIGHT; } - p->balance -= Normalize( tmp->balance ); + p->balance -= tmp->balance; (tmp->balance)--; return( tmp ); } /* L1 */ @@ -185,22 +117,22 @@ static ubi_avlNodePtr R1( ubi_avlNodePtr p ) { ubi_avlNodePtr tmp; - tmp = p->Link[LEFT]; - p->Link[LEFT] = tmp->Link[RIGHT]; - tmp->Link[RIGHT] = p; - - tmp->Link[PARENT] = p->Link[PARENT]; - tmp->gender = p->gender; - if(tmp->Link[PARENT]) - (tmp->Link[PARENT])->Link[(tmp->gender)] = tmp; - p->Link[PARENT] = tmp; - p->gender = RIGHT; - if(p->Link[LEFT]) + tmp = p->Link[ubi_trLEFT]; + p->Link[ubi_trLEFT] = tmp->Link[ubi_trRIGHT]; + tmp->Link[ubi_trRIGHT] = p; + + tmp->Link[ubi_trPARENT] = p->Link[ubi_trPARENT]; + tmp->gender = p->gender; + if(tmp->Link[ubi_trPARENT]) + (tmp->Link[ubi_trPARENT])->Link[(tmp->gender)] = tmp; + p->Link[ubi_trPARENT] = tmp; + p->gender = ubi_trRIGHT; + if(p->Link[ubi_trLEFT]) { - p->Link[LEFT]->Link[PARENT] = p; - p->Link[LEFT]->gender = LEFT; + p->Link[ubi_trLEFT]->Link[ubi_trPARENT] = p; + p->Link[ubi_trLEFT]->gender = ubi_trLEFT; } - p->balance -= Normalize( tmp->balance ); + p->balance -= tmp->balance; (tmp->balance)++; return( tmp ); } /* R1 */ @@ -217,43 +149,43 @@ static ubi_avlNodePtr L2( ubi_avlNodePtr tree ) { ubi_avlNodePtr tmp, newroot; - tmp = tree->Link[RIGHT]; - newroot = tmp->Link[LEFT]; - tmp->Link[LEFT] = newroot->Link[RIGHT]; - newroot->Link[RIGHT] = tmp; - tree->Link[RIGHT] = newroot->Link[LEFT]; - newroot->Link[LEFT] = tree; - - newroot->Link[PARENT] = tree->Link[PARENT]; - newroot->gender = tree->gender; - tree->Link[PARENT] = newroot; - tree->gender = LEFT; - tmp->Link[PARENT] = newroot; - tmp->gender = RIGHT; - - if( tree->Link[RIGHT] ) + tmp = tree->Link[ubi_trRIGHT]; + newroot = tmp->Link[ubi_trLEFT]; + tmp->Link[ubi_trLEFT] = newroot->Link[ubi_trRIGHT]; + newroot->Link[ubi_trRIGHT] = tmp; + tree->Link[ubi_trRIGHT] = newroot->Link[ubi_trLEFT]; + newroot->Link[ubi_trLEFT] = tree; + + newroot->Link[ubi_trPARENT] = tree->Link[ubi_trPARENT]; + newroot->gender = tree->gender; + tree->Link[ubi_trPARENT] = newroot; + tree->gender = ubi_trLEFT; + tmp->Link[ubi_trPARENT] = newroot; + tmp->gender = ubi_trRIGHT; + + if( tree->Link[ubi_trRIGHT] ) { - tree->Link[RIGHT]->Link[PARENT] = tree; - tree->Link[RIGHT]->gender = RIGHT; + tree->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = tree; + tree->Link[ubi_trRIGHT]->gender = ubi_trRIGHT; } - if( tmp->Link[LEFT] ) + if( tmp->Link[ubi_trLEFT] ) { - tmp->Link[LEFT]->Link[PARENT] = tmp; - tmp->Link[LEFT]->gender = LEFT; + tmp->Link[ubi_trLEFT]->Link[ubi_trPARENT] = tmp; + tmp->Link[ubi_trLEFT]->gender = ubi_trLEFT; } - if(newroot->Link[PARENT]) - newroot->Link[PARENT]->Link[newroot->gender] = newroot; + if(newroot->Link[ubi_trPARENT]) + newroot->Link[ubi_trPARENT]->Link[newroot->gender] = newroot; switch( newroot->balance ) { - case LEFT : - tree->balance = EQUAL; tmp->balance = RIGHT; break; - case EQUAL: - tree->balance = EQUAL; tmp->balance = EQUAL; break; - case RIGHT: - tree->balance = LEFT; tmp->balance = EQUAL; break; + case ubi_trLEFT : + tree->balance = ubi_trEQUAL; tmp->balance = ubi_trRIGHT; break; + case ubi_trEQUAL: + tree->balance = ubi_trEQUAL; tmp->balance = ubi_trEQUAL; break; + case ubi_trRIGHT: + tree->balance = ubi_trLEFT; tmp->balance = ubi_trEQUAL; break; } - newroot->balance = EQUAL; + newroot->balance = ubi_trEQUAL; return( newroot ); } /* L2 */ @@ -269,48 +201,48 @@ static ubi_avlNodePtr R2( ubi_avlNodePtr tree ) { ubi_avlNodePtr tmp, newroot; - tmp = tree->Link[LEFT]; - newroot = tmp->Link[RIGHT]; - tmp->Link[RIGHT] = newroot->Link[LEFT]; - newroot->Link[LEFT] = tmp; - tree->Link[LEFT] = newroot->Link[RIGHT]; - newroot->Link[RIGHT] = tree; - - newroot->Link[PARENT] = tree->Link[PARENT]; - newroot->gender = tree->gender; - tree->Link[PARENT] = newroot; - tree->gender = RIGHT; - tmp->Link[PARENT] = newroot; - tmp->gender = LEFT; - - if( tree->Link[LEFT] ) + tmp = tree->Link[ubi_trLEFT]; + newroot = tmp->Link[ubi_trRIGHT]; + tmp->Link[ubi_trRIGHT] = newroot->Link[ubi_trLEFT]; + newroot->Link[ubi_trLEFT] = tmp; + tree->Link[ubi_trLEFT] = newroot->Link[ubi_trRIGHT]; + newroot->Link[ubi_trRIGHT] = tree; + + newroot->Link[ubi_trPARENT] = tree->Link[ubi_trPARENT]; + newroot->gender = tree->gender; + tree->Link[ubi_trPARENT] = newroot; + tree->gender = ubi_trRIGHT; + tmp->Link[ubi_trPARENT] = newroot; + tmp->gender = ubi_trLEFT; + + if( tree->Link[ubi_trLEFT] ) { - tree->Link[LEFT]->Link[PARENT] = tree; - tree->Link[LEFT]->gender = LEFT; + tree->Link[ubi_trLEFT]->Link[ubi_trPARENT] = tree; + tree->Link[ubi_trLEFT]->gender = ubi_trLEFT; } - if( tmp->Link[RIGHT] ) + if( tmp->Link[ubi_trRIGHT] ) { - tmp->Link[RIGHT]->Link[PARENT] = tmp; - tmp->Link[RIGHT]->gender = RIGHT; + tmp->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = tmp; + tmp->Link[ubi_trRIGHT]->gender = ubi_trRIGHT; } - if(newroot->Link[PARENT]) - newroot->Link[PARENT]->Link[newroot->gender] = newroot; + if(newroot->Link[ubi_trPARENT]) + newroot->Link[ubi_trPARENT]->Link[newroot->gender] = newroot; switch( newroot->balance ) { - case LEFT : - tree->balance = RIGHT; tmp->balance = EQUAL; break; - case EQUAL : - tree->balance = EQUAL; tmp->balance = EQUAL; break; - case RIGHT : - tree->balance = EQUAL; tmp->balance = LEFT; break; + case ubi_trLEFT : + tree->balance = ubi_trRIGHT; tmp->balance = ubi_trEQUAL; break; + case ubi_trEQUAL : + tree->balance = ubi_trEQUAL; tmp->balance = ubi_trEQUAL; break; + case ubi_trRIGHT : + tree->balance = ubi_trEQUAL; tmp->balance = ubi_trLEFT; break; } - newroot->balance = EQUAL; + newroot->balance = ubi_trEQUAL; return( newroot ); } /* R2 */ -static ubi_avlNodePtr Adjust( ubi_avlNodePtr p, char LorR ) +static ubi_avlNodePtr Adjust( ubi_avlNodePtr p, signed char LorR ) /* ------------------------------------------------------------------------ ** * Adjust the balance value at node *p. If necessary, rotate the subtree * rooted at p. @@ -329,23 +261,23 @@ static ubi_avlNodePtr Adjust( ubi_avlNodePtr p, char LorR ) */ { if( p->balance != LorR ) - p->balance += Normalize(LorR); + p->balance += LorR; else { - char tallerbal; /* Balance value of the root of the taller subtree of p. */ + signed char tallerbal; /* Balance of root of the taller subtree of p. */ tallerbal = p->Link[LorR]->balance; - if( ( EQUAL == tallerbal ) || ( p->balance == tallerbal ) ) - p = ( (LEFT==LorR) ? R1(p) : L1(p) ); /* single rotation */ + if( ( ubi_trEQUAL == tallerbal ) || ( p->balance == tallerbal ) ) + p = ( (ubi_trLEFT==LorR) ? R1(p) : L1(p) ); /* single rotation */ else - p = ( (LEFT==LorR) ? R2(p) : L2(p) ); /* double rotation */ + p = ( (ubi_trLEFT==LorR) ? R2(p) : L2(p) ); /* double rotation */ } return( p ); } /* Adjust */ static ubi_avlNodePtr Rebalance( ubi_avlNodePtr Root, ubi_avlNodePtr subtree, - char LorR ) + signed char LorR ) /* ------------------------------------------------------------------------ ** * Rebalance the tree following an insertion. * @@ -371,19 +303,19 @@ static ubi_avlNodePtr Rebalance( ubi_avlNodePtr Root, while( subtree ) { subtree = Adjust( subtree, LorR ); - if( PARENT == subtree->gender ) + if( ubi_trPARENT == subtree->gender ) return( subtree ); - if( EQUAL == subtree->balance ) + if( ubi_trEQUAL == subtree->balance ) return( Root ); LorR = subtree->gender; - subtree = subtree->Link[PARENT]; + subtree = subtree->Link[ubi_trPARENT]; } return( Root ); } /* Rebalance */ static ubi_avlNodePtr Debalance( ubi_avlNodePtr Root, ubi_avlNodePtr subtree, - char LorR ) + signed char LorR ) /* ------------------------------------------------------------------------ ** * Rebalance the tree following a deletion. * @@ -411,13 +343,13 @@ static ubi_avlNodePtr Debalance( ubi_avlNodePtr Root, { while( subtree ) { - subtree = Adjust( subtree, RevWay(LorR) ); - if( PARENT == subtree->gender ) + subtree = Adjust( subtree, ubi_trRevWay(LorR) ); + if( ubi_trPARENT == subtree->gender ) return( subtree ); - if( EQUAL != subtree->balance ) + if( ubi_trEQUAL != subtree->balance ) return( Root ); LorR = subtree->gender; - subtree = subtree->Link[PARENT]; + subtree = subtree->Link[ubi_trPARENT]; } return( Root ); } /* Debalance */ @@ -458,10 +390,10 @@ static void ReplaceNode( ubi_avlNodePtr *parent, ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i]; (*parent) = newnode; - if(oldnode->Link[LEFT ] ) - (oldnode->Link[LEFT ])->Link[PARENT] = newnode; - if(oldnode->Link[RIGHT] ) - (oldnode->Link[RIGHT])->Link[PARENT] = newnode; + if(oldnode->Link[ubi_trLEFT ] ) + (oldnode->Link[ubi_trLEFT ])->Link[ubi_trPARENT] = newnode; + if(oldnode->Link[ubi_trRIGHT] ) + (oldnode->Link[ubi_trRIGHT])->Link[ubi_trPARENT] = newnode; } /* ReplaceNode */ static void SwapNodes( ubi_btRootPtr RootPtr, @@ -489,20 +421,20 @@ static void SwapNodes( ubi_btRootPtr RootPtr, ubi_avlNode dummy; ubi_avlNodePtr dummy_p = &dummy; - if( Node1->Link[PARENT] ) - Parent = &((Node1->Link[PARENT])->Link[Node1->gender]); + if( Node1->Link[ubi_trPARENT] ) + Parent = &((Node1->Link[ubi_trPARENT])->Link[Node1->gender]); else Parent = (ubi_avlNodePtr *)&(RootPtr->root); ReplaceNode( Parent, Node1, dummy_p ); - if( Node2->Link[PARENT] ) - Parent = &((Node2->Link[PARENT])->Link[Node2->gender]); + if( Node2->Link[ubi_trPARENT] ) + Parent = &((Node2->Link[ubi_trPARENT])->Link[Node2->gender]); else Parent = (ubi_avlNodePtr *)&(RootPtr->root); ReplaceNode( Parent, Node2, Node1 ); - if( dummy_p->Link[PARENT] ) - Parent = &((dummy_p->Link[PARENT])->Link[dummy_p->gender]); + if( dummy_p->Link[ubi_trPARENT] ) + Parent = &((dummy_p->Link[ubi_trPARENT])->Link[dummy_p->gender]); else Parent = (ubi_avlNodePtr *)&(RootPtr->root); ReplaceNode( Parent, dummy_p, Node2 ); @@ -526,7 +458,7 @@ ubi_avlNodePtr ubi_avlInitNode( ubi_avlNodePtr NodePtr ) */ { (void)ubi_btInitNode( (ubi_btNodePtr)NodePtr ); - NodePtr->balance = EQUAL; + NodePtr->balance = ubi_trEQUAL; return( NodePtr ); } /* ubi_avlInitNode */ @@ -591,9 +523,9 @@ ubi_trBool ubi_avlInsert( ubi_btRootPtr RootPtr, NewNode->balance = (*OldNode)->balance; else { - NewNode->balance = EQUAL; + NewNode->balance = ubi_trEQUAL; RootPtr->root = (ubi_btNodePtr)Rebalance( (ubi_avlNodePtr)RootPtr->root, - NewNode->Link[PARENT], + NewNode->Link[ubi_trPARENT], NewNode->gender ); } return( ubi_trTRUE ); @@ -625,33 +557,33 @@ ubi_avlNodePtr ubi_avlRemove( ubi_btRootPtr RootPtr, /* if the node has both left and right subtrees, then we have to swap * it with another node. */ - if( (DeadNode->Link[LEFT]) && (DeadNode->Link[RIGHT]) ) + if( (DeadNode->Link[ubi_trLEFT]) && (DeadNode->Link[ubi_trRIGHT]) ) SwapNodes( RootPtr, DeadNode, ubi_trPrev( DeadNode ) ); /* The parent of the node to be deleted may be another node, or it may be * the root of the tree. Since we're not sure, it's best just to have * a pointer to the parent pointer, whatever it is. */ - if( DeadNode->Link[PARENT] ) + if( DeadNode->Link[ubi_trPARENT] ) parentp = (ubi_btNodePtr *) - &((DeadNode->Link[PARENT])->Link[(DeadNode->gender)]); + &((DeadNode->Link[ubi_trPARENT])->Link[(DeadNode->gender)]); else parentp = &( RootPtr->root ); /* Now link the parent to the only grand-child. Patch up the gender and * such, and rebalance. */ - if( EQUAL == DeadNode->balance ) + if( ubi_trEQUAL == DeadNode->balance ) (*parentp) = NULL; else { p = (ubi_btNodePtr)(DeadNode->Link[(DeadNode->balance)]); - p->Link[PARENT] = (ubi_btNodePtr)DeadNode->Link[PARENT]; - p->gender = DeadNode->gender; + p->Link[ubi_trPARENT] = (ubi_btNodePtr)DeadNode->Link[ubi_trPARENT]; + p->gender = DeadNode->gender; (*parentp) = p; } RootPtr->root = (ubi_btNodePtr)Debalance( (ubi_avlNodePtr)RootPtr->root, - DeadNode->Link[PARENT], + DeadNode->Link[ubi_trPARENT], DeadNode->gender ); (RootPtr->count)--; 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 ); diff --git a/source3/ubiqx/ubi_BinTree.c b/source3/ubiqx/ubi_BinTree.c index 68e819a14b..15bdeb1d85 100644 --- a/source3/ubiqx/ubi_BinTree.c +++ b/source3/ubiqx/ubi_BinTree.c @@ -6,12 +6,7 @@ * Email: crh@ubiqx.mn.org * -------------------------------------------------------------------------- ** * - * ubi_BinTree manages a simple binary tree. Nothing fancy here. No height - * balancing, no restructuring. Still, a good tool for creating short, low- - * overhead sorted lists of things that need to be found in a hurry. - * - * In addition, this module provides a good basis for creating other types - * of binary tree handling modules. + * This module implements simple binary trees. * * -------------------------------------------------------------------------- ** * @@ -31,64 +26,73 @@ * * -------------------------------------------------------------------------- ** * - * Revision 2.4 1997/07/26 04:11:10 crh - * + Just to be annoying I changed ubi_TRUE and ubi_FALSE to ubi_trTRUE - * and ubi_trFALSE. - * + There is now a type ubi_trBool to go with ubi_trTRUE and ubi_trFALSE. - * + There used to be something called "ubi_TypeDefs.h". I got rid of it. - * + Added function ubi_btLeafNode(). + * Log: ubi_BinTree.c,v + * Revision 3.0 1997/12/08 06:49:11 crh + * This is a new major revision level for all ubiqx binary tree modules. + * In previous releases, the ubi_trNode structure looked like this: + * + * typedef struct ubi_btNodeStruct + * { + * struct ubi_btNodeStruct *Link[3]; + * signed char gender; + * } ubi_btNode; + * + * As a result, the pointers were indexed as + * + * Link[0] == Left Child + * Link[1] == Parent + * Link[2] == Right Child * - * Revision 2.3 1997/06/03 05:16:17 crh - * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid conflicts. - * Also changed the interface to function InitTree(). See the comments - * for this function for more information. + * With this release, the node structure changes to: * - * Revision 2.2 1995/10/03 22:00:07 CRH - * Ubisized! - * - * Revision 2.1 95/03/09 23:37:10 CRH - * Added the ModuleID static string and function. These modules are now - * self-identifying. - * - * Revision 2.0 95/02/27 22:00:17 CRH - * Revision 2.0 of this program includes the following changes: + * typedef struct ubi_btNodeStruct + * { + * struct ubi_btNodeStruct *leftlink + * struct ubi_btNodeStruct *Link[2]; + * signed char gender; + * } ubi_btNode; * - * 1) A fix to a major typo in the RepaceNode() function. - * 2) The addition of the static function Border(). - * 3) The addition of the public functions FirstOf() and LastOf(), which - * use Border(). These functions are used with trees that allow - * duplicate keys. - * 4) A complete rewrite of the Locate() function. Locate() now accepts - * a "comparison" operator. - * 5) Overall enhancements to both code and comments. + * The leftlink field is used as a place holder, and the pointers are now + * index as * - * I decided to give this a new major rev number because the interface has - * changed. In particular, there are two new functions, and changes to the - * Locate() function. + * Link[-1] == Left Child (aka. leftlink) + * Link[ 0] == Parent + * Link[ 1] == Right Child * - * Revision 1.0 93/10/15 22:44:59 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: + * which is much nicer. Doing things this way removes the need to shift + * values between the two numbering schemes, thus removing one macro, + * simplifying another, and getting rid of a whole bunch of increment & + * decrement operations. + * + * Revision 2; 1995/02/27 - 1997/12/07 included: + * - The addition of the ModuleID static string and ubi_ModuleID() function. + * - The addition of the public functions FirstOf() and LastOf(). These + * functions are used with trees that allow duplicate keys. + * - The addition of the ubi_btLeafNode() function. + * - A rewrite of the Locate() function. + * - A change to the parameter list in function ubi_btInitTree(). + * - Bugfixes. + * + * Revision 1; 93/10/15 - 95/02/27: + * Revision 1 introduced a set of #define's that provide a single API to all + * of the existing tree modules. Each of these modules has a different name + * 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". + * Only those portions of the base module (ubi_BinTree) that are superceeded + * in the descendant module have new names. For example, the AVL node + * structure in ubi_AVLtree.h is named "ubi_avlNode", but the root structure + * is still "ubi_btRoot". Using SplayTree, the locate function is 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. + * This is confusing. * - * So, I have added a set of defined names that get redefined in any of the + * So, I 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 @@ -100,7 +104,8 @@ * 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 + * red/black trees, or if you plan to use two or more specific tree types + * in the same piece of code. CRH * * V0.0 - June, 1991 - Written by Christopher R. Hertel (CRH). * @@ -115,8 +120,8 @@ */ static char ModuleID[] = "ubi_BinTree\n\ -\tRevision: 2.4\n\ -\tDate: 1997/07/26 04:11:10\n\ +\tRevision: 3.0\n\ +\tDate: 1997/12/08 06:49:11\n\ \tAuthor: crh\n"; /* ========================================================================== ** @@ -129,7 +134,7 @@ static ubi_btNodePtr qFind( ubi_btCompFunc cmp, /* ------------------------------------------------------------------------ ** * This function performs a non-recursive search of a tree for a node * matching a specific key. It is called "qFind()" because it is - * faster that TreeFind (below). + * (probably a little bit) faster that TreeFind (below). * * Input: * cmp - a pointer to the tree's comparison function. @@ -148,9 +153,9 @@ static ubi_btNodePtr qFind( ubi_btCompFunc cmp, * ------------------------------------------------------------------------ ** */ { - char tmp; + signed char tmp; - while( p && (( tmp = AbNormal((*cmp)(FindMe, p)) ) != EQUAL) ) + while( p && (( tmp = ubi_trNormalize((*cmp)(FindMe, p)) ) != ubi_trEQUAL) ) p = p->Link[tmp]; return( p ); @@ -159,7 +164,7 @@ static ubi_btNodePtr qFind( ubi_btCompFunc cmp, static ubi_btNodePtr TreeFind( ubi_btItemPtr findme, ubi_btNodePtr p, ubi_btNodePtr *parentp, - char *gender, + signed char *gender, ubi_btCompFunc CmpFunc ) /* ------------------------------------------------------------------------ ** * TreeFind() searches a tree for a given value (findme). It will return a @@ -189,25 +194,27 @@ static ubi_btNodePtr TreeFind( ubi_btItemPtr findme, */ { register ubi_btNodePtr tmp_p = p; - ubi_btNodePtr tmp_pp = NULL; - char tmp_sex = EQUAL; - char tmp_cmp; + ubi_btNodePtr tmp_pp = NULL; + signed char tmp_gender = ubi_trEQUAL; + signed char tmp_cmp; - while( tmp_p && (EQUAL != (tmp_cmp = AbNormal((*CmpFunc)(findme, tmp_p)))) ) + while( tmp_p + && (ubi_trEQUAL != (tmp_cmp = ubi_trNormalize((*CmpFunc)(findme, tmp_p)))) + ) { tmp_pp = tmp_p; /* Keep track of previous node. */ - tmp_sex = tmp_cmp; /* Keep track of sex of child. */ + tmp_gender = tmp_cmp; /* Keep track of sex of child. */ tmp_p = tmp_p->Link[tmp_cmp]; /* Go to child. */ } *parentp = tmp_pp; /* Return results. */ - *gender = tmp_sex; + *gender = tmp_gender; return( tmp_p ); } /* TreeFind */ static void ReplaceNode( ubi_btNodePtr *parent, ubi_btNodePtr oldnode, ubi_btNodePtr newnode ) - /* ------------------------------------------------------------------ * + /* ------------------------------------------------------------------------ ** * Remove node oldnode from the tree, replacing it with node newnode. * * Input: @@ -220,12 +227,8 @@ static void ReplaceNode( ubi_btNodePtr *parent, * place of <*oldnode>. * * Notes: Don't forget to free oldnode. - * Also, this function used to have a really nasty typo - * bug. "oldnode" and "newnode" were swapped in the line - * that now reads: - * ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i]; - * Bleah! - * ------------------------------------------------------------------ * + * + * ------------------------------------------------------------------------ ** */ { register int i; @@ -233,10 +236,17 @@ static void ReplaceNode( ubi_btNodePtr *parent, for( i = 0; i < btNodeSize; i++ ) /* Copy node internals to new node. */ ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i]; - (*parent) = newnode; /* Old node's parent points to new child. */ + + /* Old node's parent points to new child. */ + (*parent) = newnode; + /* Now tell the children about their new step-parent. */ - if( oldnode->Link[LEFT ] ) (oldnode->Link[LEFT ])->Link[PARENT] = newnode; - if( oldnode->Link[RIGHT] ) (oldnode->Link[RIGHT])->Link[PARENT] = newnode; + if( oldnode->Link[ubi_trLEFT ] ) + (oldnode->Link[ubi_trLEFT ])->Link[ubi_trPARENT] = newnode; + + if( oldnode->Link[ubi_trRIGHT] ) + (oldnode->Link[ubi_trRIGHT])->Link[ubi_trPARENT] = newnode; + } /* ReplaceNode */ static void SwapNodes( ubi_btRootPtr RootPtr, @@ -263,22 +273,22 @@ static void SwapNodes( ubi_btRootPtr RootPtr, ubi_btNodePtr dummy_p = &dummy; /* Replace Node 1 with the dummy, thus removing Node1 from the tree. */ - if( Node1->Link[PARENT] ) - Parent = &((Node1->Link[PARENT])->Link[Node1->gender]); + if( Node1->Link[ubi_trPARENT] ) + Parent = &((Node1->Link[ubi_trPARENT])->Link[Node1->gender]); else Parent = &(RootPtr->root); ReplaceNode( Parent, Node1, dummy_p ); /* Swap Node 1 with Node 2, placing Node 1 back into the tree. */ - if( Node2->Link[PARENT] ) - Parent = &((Node2->Link[PARENT])->Link[Node2->gender]); + if( Node2->Link[ubi_trPARENT] ) + Parent = &((Node2->Link[ubi_trPARENT])->Link[Node2->gender]); else Parent = &(RootPtr->root); ReplaceNode( Parent, Node2, Node1 ); /* Swap Node 2 and the dummy, thus placing Node 2 back into the tree. */ - if( dummy_p->Link[PARENT] ) - Parent = &((dummy_p->Link[PARENT])->Link[dummy_p->gender]); + if( dummy_p->Link[ubi_trPARENT] ) + Parent = &((dummy_p->Link[ubi_trPARENT])->Link[dummy_p->gender]); else Parent = &(RootPtr->root); ReplaceNode( Parent, dummy_p, Node2 ); @@ -289,7 +299,7 @@ static void SwapNodes( ubi_btRootPtr RootPtr, */ static ubi_btNodePtr SubSlide( register ubi_btNodePtr P, - register char whichway ) + register signed char whichway ) /* ------------------------------------------------------------------------ ** * Slide down the side of a subtree. * @@ -317,7 +327,7 @@ static ubi_btNodePtr SubSlide( register ubi_btNodePtr P, } /* SubSlide */ static ubi_btNodePtr Neighbor( register ubi_btNodePtr P, - register char whichway ) + register signed char whichway ) /* ------------------------------------------------------------------------ ** * Given starting point p, return the (key order) next or preceeding node * in the tree. @@ -336,14 +346,14 @@ static ubi_btNodePtr Neighbor( register ubi_btNodePtr P, if( P ) { if( P->Link[ whichway ] ) - return( SubSlide( P->Link[ whichway ], (char)RevWay(whichway) ) ); + return( SubSlide( P->Link[ whichway ], ubi_trRevWay(whichway) ) ); else - while( P->Link[ PARENT ] ) + while( P->Link[ ubi_trPARENT ] ) { - if( (P->Link[ PARENT ])->Link[ whichway ] == P ) - P = P->Link[ PARENT ]; + if( (P->Link[ ubi_trPARENT ])->Link[ whichway ] == P ) + P = P->Link[ ubi_trPARENT ]; else - return( P->Link[ PARENT ] ); + return( P->Link[ ubi_trPARENT ] ); } } return( NULL ); @@ -352,7 +362,7 @@ static ubi_btNodePtr Neighbor( register ubi_btNodePtr P, static ubi_btNodePtr Border( ubi_btRootPtr RootPtr, ubi_btItemPtr FindMe, ubi_btNodePtr p, - char whichway ) + signed char whichway ) /* ------------------------------------------------------------------------ ** * Given starting point p, which has a key value equal to *FindMe, locate * the first (index order) node with the same key value. @@ -384,17 +394,17 @@ static ubi_btNodePtr Border( ubi_btRootPtr RootPtr, register ubi_btNodePtr q; /* Exit if there's nothing that can be done. */ - if( !Dups_OK( RootPtr ) || (PARENT == whichway) ) + if( !ubi_trDups_OK( RootPtr ) || (ubi_trPARENT == whichway) ) return( p ); /* First, if needed, move up the tree. We need to get to the root of the * subtree that contains all of the matching nodes. */ - q = p->Link[PARENT]; - while( q && (EQUAL == AbNormal( (*(RootPtr->cmp))(FindMe, q) )) ) + q = p->Link[ubi_trPARENT]; + while( q && (ubi_trEQUAL == ubi_trNormalize( (*(RootPtr->cmp))(FindMe, q) )) ) { p = q; - q = p->Link[PARENT]; + q = p->Link[ubi_trPARENT]; } /* Next, move back down in the "whichway" direction. */ @@ -421,15 +431,15 @@ long ubi_btSgn( register long x ) * * Input: x - a signed long integer value. * - * Output: the "sign" of x, represented as follows: + * Output: -1, 0, or 1 representing the "sign" of x as follows: * -1 == negative * 0 == zero (no sign) * 1 == positive * - * Note: This utility is provided in order to facilitate the conversion - * of C comparison function return values into BinTree direction - * values: {LEFT, PARENT, EQUAL}. It is INCORPORATED into the - * AbNormal() conversion macro! + * Note: This utility is provided in order to facilitate the conversion + * of C comparison function return values into BinTree direction + * values: {ubi_trLEFT, ubi_trPARENT, ubi_trEQUAL}. It is + * incorporated into the ubi_trNormalize() conversion macro. * * ------------------------------------------------------------------------ ** */ @@ -447,10 +457,10 @@ ubi_btNodePtr ubi_btInitNode( ubi_btNodePtr NodePtr ) * ------------------------------------------------------------------------ ** */ { - NodePtr->Link[ LEFT ] = NULL; - NodePtr->Link[ PARENT ] = NULL; - NodePtr->Link[ RIGHT ] = NULL; - NodePtr->gender = EQUAL; + NodePtr->Link[ ubi_trLEFT ] = NULL; + NodePtr->Link[ ubi_trPARENT ] = NULL; + NodePtr->Link[ ubi_trRIGHT ] = NULL; + NodePtr->gender = ubi_trEQUAL; return( NodePtr ); } /* ubi_btInitNode */ @@ -543,7 +553,7 @@ ubi_trBool ubi_btInsert( ubi_btRootPtr RootPtr, { ubi_btNodePtr OtherP, parent = NULL; - char tmp; + signed char tmp; if( !(OldNode) ) /* If they didn't give us a pointer, supply our own. */ OldNode = &OtherP; @@ -560,9 +570,9 @@ ubi_trBool ubi_btInsert( ubi_btRootPtr RootPtr, RootPtr->root = NewNode; else { - parent->Link[tmp] = NewNode; - NewNode->Link[PARENT] = parent; - NewNode->gender = tmp; + parent->Link[tmp] = NewNode; + NewNode->Link[ubi_trPARENT] = parent; + NewNode->gender = tmp; } (RootPtr->count)++; return( ubi_trTRUE ); @@ -571,24 +581,25 @@ ubi_trBool ubi_btInsert( ubi_btRootPtr RootPtr, /* If we reach this point, we know that a duplicate node exists. This * section adds the node to the tree if duplicate keys are allowed. */ - if( Dups_OK(RootPtr) ) /* Key exists, add duplicate */ + if( ubi_trDups_OK(RootPtr) ) /* Key exists, add duplicate */ { ubi_btNodePtr q; - tmp = RIGHT; + tmp = ubi_trRIGHT; q = (*OldNode); *OldNode = NULL; while( q ) { parent = q; - if( tmp == EQUAL ) tmp = RIGHT; + if( tmp == ubi_trEQUAL ) + tmp = ubi_trRIGHT; q = q->Link[tmp]; if ( q ) - tmp = AbNormal( (*(RootPtr->cmp))(ItemPtr, q) ); + tmp = ubi_trNormalize( (*(RootPtr->cmp))(ItemPtr, q) ); } - parent->Link[tmp] = NewNode; - NewNode->Link[PARENT] = parent; - NewNode->gender = tmp; + parent->Link[tmp] = NewNode; + NewNode->Link[ubi_trPARENT] = parent; + NewNode->gender = tmp; (RootPtr->count)++; return( ubi_trTRUE ); } @@ -597,7 +608,7 @@ ubi_trBool ubi_btInsert( ubi_btRootPtr RootPtr, * duplicate nodes, but our node keys match, so... may we replace the * old one? */ - if( Ovwt_OK(RootPtr) ) /* Key exists, we replace */ + if( ubi_trOvwt_OK(RootPtr) ) /* Key exists, we replace */ { if (!(parent)) ReplaceNode( &(RootPtr->root), *OldNode, NewNode ); @@ -628,32 +639,32 @@ ubi_btNodePtr ubi_btRemove( ubi_btRootPtr RootPtr, { ubi_btNodePtr p, *parentp; - char tmp; + signed char tmp; /* if the node has both left and right subtrees, then we have to swap * it with another node. The other node we choose will be the Prev()ious * node, which is garunteed to have no RIGHT child. */ - if( (DeadNode->Link[LEFT]) && (DeadNode->Link[RIGHT]) ) + if( (DeadNode->Link[ubi_trLEFT]) && (DeadNode->Link[ubi_trRIGHT]) ) SwapNodes( RootPtr, DeadNode, ubi_btPrev( DeadNode ) ); /* The parent of the node to be deleted may be another node, or it may be * the root of the tree. Since we're not sure, it's best just to have * a pointer to the parent pointer, whatever it is. */ - if (DeadNode->Link[PARENT]) - parentp = &((DeadNode->Link[PARENT])->Link[DeadNode->gender]); + if (DeadNode->Link[ubi_trPARENT]) + parentp = &((DeadNode->Link[ubi_trPARENT])->Link[DeadNode->gender]); else parentp = &( RootPtr->root ); /* Now link the parent to the only grand-child and patch up the gender. */ - tmp = ((DeadNode->Link[LEFT])?LEFT:RIGHT); + tmp = ((DeadNode->Link[ubi_trLEFT]) ? ubi_trLEFT : ubi_trRIGHT); p = (DeadNode->Link[tmp]); if( p ) { - p->Link[PARENT] = DeadNode->Link[PARENT]; - p->gender = DeadNode->gender; + p->Link[ubi_trPARENT] = DeadNode->Link[ubi_trPARENT]; + p->gender = DeadNode->gender; } (*parentp) = p; @@ -716,7 +727,7 @@ ubi_btNodePtr ubi_btLocate( ubi_btRootPtr RootPtr, { register ubi_btNodePtr p; ubi_btNodePtr parent; - char whichkid; + signed char whichkid; /* Start by searching for a matching node. */ p = TreeFind( FindMe, @@ -730,13 +741,13 @@ ubi_btNodePtr ubi_btLocate( ubi_btRootPtr RootPtr, switch( CompOp ) { case ubi_trLT: /* It's just a jump to the left... */ - p = Border( RootPtr, FindMe, p, LEFT ); - return( Neighbor( p, LEFT ) ); + p = Border( RootPtr, FindMe, p, ubi_trLEFT ); + return( Neighbor( p, ubi_trLEFT ) ); case ubi_trGT: /* ...and then a jump to the right. */ - p = Border( RootPtr, FindMe, p, RIGHT ); - return( Neighbor( p, RIGHT ) ); + p = Border( RootPtr, FindMe, p, ubi_trRIGHT ); + return( Neighbor( p, ubi_trRIGHT ) ); } - p = Border( RootPtr, FindMe, p, LEFT ); + p = Border( RootPtr, FindMe, p, ubi_trLEFT ); return( p ); } @@ -750,9 +761,9 @@ ubi_btNodePtr ubi_btLocate( ubi_btRootPtr RootPtr, * Remaining possibilities are LT and GT (including LE & GE). */ if( (ubi_trLT == CompOp) || (ubi_trLE == CompOp) ) - return( (LEFT == whichkid) ? Neighbor( parent, whichkid ) : parent ); + return( (ubi_trLEFT == whichkid) ? Neighbor( parent, whichkid ) : parent ); else - return( (RIGHT == whichkid) ? Neighbor( parent, whichkid ) : parent ); + return( (ubi_trRIGHT == whichkid) ? Neighbor( parent, whichkid ) : parent ); } /* ubi_btLocate */ ubi_btNodePtr ubi_btFind( ubi_btRootPtr RootPtr, @@ -789,7 +800,7 @@ ubi_btNodePtr ubi_btNext( ubi_btNodePtr P ) * ------------------------------------------------------------------------ ** */ { - return( Neighbor( P, RIGHT ) ); + return( Neighbor( P, ubi_trRIGHT ) ); } /* ubi_btNext */ ubi_btNodePtr ubi_btPrev( ubi_btNodePtr P ) @@ -802,7 +813,7 @@ ubi_btNodePtr ubi_btPrev( ubi_btNodePtr P ) * ------------------------------------------------------------------------ ** */ { - return( Neighbor( P, LEFT ) ); + return( Neighbor( P, ubi_trLEFT ) ); } /* ubi_btPrev */ ubi_btNodePtr ubi_btFirst( ubi_btNodePtr P ) @@ -817,7 +828,7 @@ ubi_btNodePtr ubi_btFirst( ubi_btNodePtr P ) * ------------------------------------------------------------------------ ** */ { - return( SubSlide( P, LEFT ) ); + return( SubSlide( P, ubi_trLEFT ) ); } /* ubi_btFirst */ ubi_btNodePtr ubi_btLast( ubi_btNodePtr P ) @@ -832,7 +843,7 @@ ubi_btNodePtr ubi_btLast( ubi_btNodePtr P ) * ------------------------------------------------------------------------ ** */ { - return( SubSlide( P, RIGHT ) ); + return( SubSlide( P, ubi_trRIGHT ) ); } /* ubi_btLast */ ubi_btNodePtr ubi_btFirstOf( ubi_btRootPtr RootPtr, @@ -855,9 +866,9 @@ ubi_btNodePtr ubi_btFirstOf( ubi_btRootPtr RootPtr, */ { /* If our starting point is invalid, return NULL. */ - if( !p || AbNormal( (*(RootPtr->cmp))( MatchMe, p ) != EQUAL ) ) + if( !p || ubi_trNormalize( (*(RootPtr->cmp))( MatchMe, p ) != ubi_trEQUAL ) ) return( NULL ); - return( Border( RootPtr, MatchMe, p, LEFT ) ); + return( Border( RootPtr, MatchMe, p, ubi_trLEFT ) ); } /* ubi_btFirstOf */ ubi_btNodePtr ubi_btLastOf( ubi_btRootPtr RootPtr, @@ -880,9 +891,9 @@ ubi_btNodePtr ubi_btLastOf( ubi_btRootPtr RootPtr, */ { /* If our starting point is invalid, return NULL. */ - if( !p || AbNormal( (*(RootPtr->cmp))( MatchMe, p ) != EQUAL ) ) + if( !p || ubi_trNormalize( (*(RootPtr->cmp))( MatchMe, p ) != ubi_trEQUAL ) ) return( NULL ); - return( Border( RootPtr, MatchMe, p, RIGHT ) ); + return( Border( RootPtr, MatchMe, p, ubi_trRIGHT ) ); } /* ubi_btLastOf */ ubi_trBool ubi_btTraverse( ubi_btRootPtr RootPtr, @@ -941,11 +952,11 @@ ubi_trBool ubi_btKillTree( ubi_btRootPtr RootPtr, while( p ) { q = p; - while( q->Link[RIGHT] ) - q = SubSlide( q->Link[RIGHT], LEFT ); - p = q->Link[PARENT]; + while( q->Link[ubi_trRIGHT] ) + q = SubSlide( q->Link[ubi_trRIGHT], ubi_trLEFT ); + p = q->Link[ubi_trPARENT]; if( p ) - p->Link[ ((p->Link[LEFT] == q)?LEFT:RIGHT) ] = NULL; + p->Link[ ((p->Link[ubi_trLEFT] == q)?ubi_trLEFT:ubi_trRIGHT) ] = NULL; FreeNode((void *)q); } @@ -979,20 +990,24 @@ ubi_btNodePtr ubi_btLeafNode( ubi_btNodePtr leader ) * in pointers to nodes other than the root node each time. A * pointer to any node in the tree will do. Of course, if you * pass a pointer to a leaf node you'll get the same thing back. + * + If using a splay tree, splaying the tree will tend to randomize + * things a bit too. See ubi_SplayTree for more info. * * ------------------------------------------------------------------------ ** */ { ubi_btNodePtr follower = NULL; - int whichway = LEFT; + int whichway = ubi_trLEFT; while( NULL != leader ) { + /* The next line is a weak attempt at randomizing. */ + whichway = ((int)leader & 0x0010) ? whichway : ubi_trRevWay(whichway); follower = leader; - leader = follower->Link[ whichway ]; + leader = leader->Link[ whichway ]; if( NULL == leader ) { - whichway = RevWay( whichway ); + whichway = ubi_trRevWay( whichway ); leader = follower->Link[ whichway ]; } } @@ -1028,5 +1043,4 @@ int ubi_btModuleID( int size, char *list[] ) return( 0 ); } /* ubi_btModuleID */ - /* ========================================================================== */ diff --git a/source3/ubiqx/ubi_BinTree.h b/source3/ubiqx/ubi_BinTree.h index ee512989f9..d5032b58a2 100644 --- a/source3/ubiqx/ubi_BinTree.h +++ b/source3/ubiqx/ubi_BinTree.h @@ -8,12 +8,7 @@ * Email: crh@ubiqx.mn.org * -------------------------------------------------------------------------- ** * - * ubi_BinTree manages a simple binary tree. Nothing fancy here. No height - * balancing, no restructuring. Still, a good tool for creating short, low- - * overhead sorted lists of things that need to be found in a hurry. - * - * In addition, this module provides a good basis for creating other types - * of binary tree handling modules. + * This module implements simple binary trees. * * -------------------------------------------------------------------------- ** * @@ -33,64 +28,73 @@ * * -------------------------------------------------------------------------- ** * - * Revision 2.4 1997/07/26 04:11:14 crh - * + Just to be annoying I changed ubi_TRUE and ubi_FALSE to ubi_trTRUE - * and ubi_trFALSE. - * + There is now a type ubi_trBool to go with ubi_trTRUE and ubi_trFALSE. - * + There used to be something called "ubi_TypeDefs.h". I got rid of it. - * + Added function ubi_btLeafNode(). - * - * Revision 2.3 1997/06/03 05:15:27 crh - * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid conflicts. - * Also changed the interface to function InitTree(). See the comments - * for this function for more information. - * - * Revision 2.2 1995/10/03 22:00:40 CRH - * Ubisized! - * - * Revision 2.1 95/03/09 23:43:46 CRH - * Added the ModuleID static string and function. These modules are now - * self-identifying. - * - * Revision 2.0 95/02/27 22:00:33 CRH - * Revision 2.0 of this program includes the following changes: - * - * 1) A fix to a major typo in the RepaceNode() function. - * 2) The addition of the static function Border(). - * 3) The addition of the public functions FirstOf() and LastOf(), which - * use Border(). These functions are used with trees that allow - * duplicate keys. - * 4) A complete rewrite of the Locate() function. Locate() now accepts - * a "comparison" operator. - * 5) Overall enhancements to both code and comments. - * - * I decided to give this a new major rev number because the interface has - * changed. In particular, there are two new functions, and changes to the - * Locate() function. - * - * Revision 1.0 93/10/15 22:55:04 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: + * Log: ubi_BinTree.h,v + * Revision 3.0 1997/12/08 06:49:15 crh + * This is a new major revision level for all ubiqx binary tree modules. + * In previous releases, the ubi_trNode structure looked like this: + * + * typedef struct ubi_btNodeStruct + * { + * struct ubi_btNodeStruct *Link[3]; + * signed char gender; + * } ubi_btNode; + * + * As a result, the pointers were indexed as + * + * Link[0] == Left Child + * Link[1] == Parent + * Link[2] == Right Child + * + * With this release, the node structure changes to: + * + * typedef struct ubi_btNodeStruct + * { + * struct ubi_btNodeStruct *leftlink + * struct ubi_btNodeStruct *Link[2]; + * signed char gender; + * } ubi_btNode; + * + * The leftlink field is used as a place holder, and the pointers are now + * index as + * + * Link[-1] == Left Child (aka. leftlink) + * Link[ 0] == Parent + * Link[ 1] == Right Child + * + * which is much nicer. Doing things this way removes the need to shift + * values between the two numbering schemes, thus removing one macro, + * simplifying another, and getting rid of a whole bunch of increment & + * decrement operations. + * + * Revision 2; 1995/02/27 - 1997/12/07 included: + * - The addition of the ModuleID static string and ubi_ModuleID() function. + * - The addition of the public functions FirstOf() and LastOf(). These + * functions are used with trees that allow duplicate keys. + * - The addition of the ubi_btLeafNode() function. + * - A rewrite of the Locate() function. + * - A change to the parameter list in function ubi_btInitTree(). + * - Bugfixes. + * + * Revision 1; 93/10/15 - 95/02/27: + * Revision 1 introduced a set of #define's that provide a single API to all + * of the existing tree modules. Each of these modules has a different name + * 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". + * Only those portions of the base module (ubi_BinTree) that are superceeded + * in the descendant module have new names. For example, the AVL node + * structure in ubi_AVLtree.h is named "ubi_avlNode", but the root structure + * is still "ubi_btRoot". Using SplayTree, the locate function is 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. + * This is confusing. * - * So, I have added a set of defined names that get redefined in any of the + * So, I 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 @@ -102,7 +106,8 @@ * 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 + * red/black trees, or if you plan to use two or more specific tree types + * in the same piece of code. CRH * * V0.0 - June, 1991 - Written by Christopher R. Hertel (CRH). * @@ -110,7 +115,7 @@ */ /* -------------------------------------------------------------------------- ** - * Macros and constants. + * Constants... * * General purpose: * ubi_trTRUE - Boolean TRUE. @@ -120,16 +125,16 @@ * ubi_trOVERWRITE - This flag indicates that an existing node may be * overwritten by a new node with a matching key. * ubi_trDUPKEY - This flag indicates that the tree allows duplicate - * keys. If the tree does allow duplicates, the - * overwrite flag is ignored. + * keys. If the tree allows duplicates, the overwrite + * flag is ignored. * - * Node link array index constants: (Each node has an array of three - * pointers. One to the left, one to the right, and one back to the - * parent.) - * LEFT - Left child pointer. - * PARENT - Parent pointer. - * RIGHT - Right child pointer. - * EQUAL - Synonym for PARENT. + * Node link array index constants: + * (Each node has an array of three pointers; pointer to the left child, + * pointer to the right child, and a pointer back to the parent node.) + * ubi_trLEFT - Left child pointer. + * ubi_trPARENT - Parent pointer. + * ubi_trRIGHT - Right child pointer. + * ubi_trEQUAL - Synonym for PARENT. * * ubi_trCompOps: These values are used in the ubi_trLocate() function. * ubi_trLT - request the first instance of the greatest key less than @@ -142,7 +147,6 @@ * or equal to the search key. * ubi_trGT - request the first instance of the first key that is greater * than the search key. - * -------------------------------------------------------------------------- ** */ #define ubi_trTRUE 0xFF @@ -152,12 +156,13 @@ #define ubi_trDUPKEY 0x02 /* Turn on allow duplicate keys */ /* Pointer array index constants... */ -#define LEFT 0x00 -#define PARENT 0x01 -#define RIGHT 0x02 -#define EQUAL PARENT +#define ubi_trLEFT -1 +#define ubi_trPARENT 0 +#define ubi_trRIGHT 1 +#define ubi_trEQUAL ubi_trPARENT -typedef enum { +typedef enum + { ubi_trLT = 1, ubi_trLE, ubi_trEQ, @@ -166,57 +171,57 @@ typedef enum { } ubi_trCompOps; /* -------------------------------------------------------------------------- ** - * These three macros allow simple manipulation of pointer index values (LEFT, - * RIGHT, and PARENT). - * - * Normalize() - converts {LEFT, PARENT, RIGHT} into {-1, 0 ,1}. C - * uses {negative, zero, positive} values to indicate - * {less than, equal to, greater than}. - * AbNormal() - converts {negative, zero, positive} to {LEFT, PARENT, - * RIGHT} (opposite of Normalize()). Note: C comparison - * functions, such as strcmp(), return {negative, zero, - * positive} values, which are not necessarily {-1, 0, - * 1}. This macro uses the the ubi_btSgn() function to - * compensate. - * RevWay() - converts LEFT to RIGHT and RIGHT to LEFT. PARENT (EQUAL) - * is left as is. - * -------------------------------------------------------------------------- ** + * Macros... + * ubi_trNormalize() - "Normalize" a value with respect to ubi_trLEFT, + * ubi_trRIGHT, and ubi_trPARENT. This macro calls + * ubi_btSgn() to convert the input to -1, 0, or 1. + * The resultant value is returned as a signed char. + * + * ubi_trRevWay() - converts ubi_trLEFT to ubi_trRIGHT and vice versa. + * ubi_trPARENT (ubi_trEQUAL) is left as is. + * + * ubi_trDups_OK() - returns TRUE if the tree allows duplicates. + * + * ubi_trOvwt_OK() - returns TRUE if the overwrite flag is on. Note + * that overwrites will not occur in a tree that + * allows duplicates. */ -#define Normalize(W) ((char)((W)-EQUAL)) -#define AbNormal(W) ((char)( EQUAL+((char)ubi_btSgn( (W) )) )) -#define RevWay(W) ((char)((W)==LEFT?RIGHT:((W)==RIGHT?LEFT:EQUAL))) -/* -------------------------------------------------------------------------- ** - * These macros allow us to quickly read the values of the OVERWRITE and - * DUPlicate KEY bits of the tree root flags field. - * -------------------------------------------------------------------------- ** - */ -#define Dups_OK(A) ((ubi_trDUPKEY & ((A)->flags))?(ubi_trTRUE):(ubi_trFALSE)) -#define Ovwt_OK(A) ((ubi_trOVERWRITE & ((A)->flags))?(ubi_trTRUE):(ubi_trFALSE)) +#define ubi_trNormalize(W) ((signed char)ubi_btSgn(W)) +#define ubi_trRevWay(W) (-(W)) + +#define ubi_trDups_OK(A) \ + ((ubi_trDUPKEY & ((A)->flags)) ? (ubi_trTRUE) : (ubi_trFALSE)) +#define ubi_trOvwt_OK(A) \ + ((ubi_trOVERWRITE & ((A)->flags))? (ubi_trTRUE) : (ubi_trFALSE)) + /* -------------------------------------------------------------------------- ** * Typedefs... * - * ubi_trBool - Your typcial true or false... + * ubi_trBool - Your typcial true or false... * - * Item Pointer: The ubi_btItemPtr is a generic pointer. It is used to - * indicate a key that is being searched for within the tree. - * Searching occurs whenever the ubi_trFind(), ubi_trLocate(), - * or ubi_trInsert() functions are called. - * -------------------------------------------------------------------------- ** + * ubi_btItemPtr - The Item Pointer is a generic pointer. It is used to + * indicate a key for which to search within the tree. + * The ubi_trFind(), ubi_trLocate(), and ubi_trInsert() + * functions all perform searches. */ -typedef unsigned char ubi_trBool; +typedef unsigned char ubi_trBool; /* Our own name for "boolean". */ -typedef void *ubi_btItemPtr; /* A pointer to data within a node. */ +typedef void *ubi_btItemPtr; /* A pointer to (key) data within a node. */ -/* ------------------------------------------------------------------------- ** +/* -------------------------------------------------------------------------- ** + * Typedefs continued... + * * Binary Tree Node Structure: This structure defines the basic elements of * the tree nodes. In general you *SHOULD NOT PLAY WITH THESE FIELDS*! * But, of course, I have to put the structure into this header so that * you can use it as a building block. * * The fields are as follows: + * leftlink - pointer to the left child of the node. This field will + * be accessed as Link[-1]. * Link - an array of pointers. These pointers are manipulated by * the BT routines. The pointers indicate the left and right * child nodes and the parent node. By keeping track of the @@ -227,18 +232,22 @@ typedef void *ubi_btItemPtr; /* A pointer to data within a node. */ * gender - a one-byte field indicating whether the node is the RIGHT or * LEFT child of its parent. If the node is the root of the * tree, gender will be PARENT. - * ------------------------------------------------------------------------- ** */ -typedef struct ubi_btNodeStruct { - struct ubi_btNodeStruct *Link[ 3 ]; - char gender; + +typedef struct ubi_btNodeStruct + { + struct ubi_btNodeStruct *leftlink; /* Will be accessed as Link[-1]. */ + struct ubi_btNodeStruct *Link[2]; /* Parent & Right links. */ + signed char gender; /* Indicates Left/Right of parent. */ } ubi_btNode; typedef ubi_btNode *ubi_btNodePtr; /* Pointer to an ubi_btNode structure. */ -/* ------------------------------------------------------------------------- ** - * The next three typedefs define standard function types used by the binary - * tree management routines. In particular: +/* -------------------------------------------------------------------------- ** + * Typedefs continued... + * + * The next three typedefs define standard function types used by the binary + * tree management routines. In particular: * * ubi_btCompFunc is a pointer to a comparison function. Comparison * functions are passed an ubi_btItemPtr and an @@ -258,7 +267,6 @@ typedef ubi_btNode *ubi_btNodePtr; /* Pointer to an ubi_btNode structure. */ * mean anything that you want it to mean. Just remember * that the tree *will* be destroyed and that none of the * node pointers will be valid any more. - * ------------------------------------------------------------------------- ** */ typedef int (*ubi_btCompFunc)( ubi_btItemPtr, ubi_btNodePtr ); @@ -268,8 +276,10 @@ typedef void (*ubi_btActionRtn)( ubi_btNodePtr, void * ); typedef void (*ubi_btKillNodeRtn)( ubi_btNodePtr ); /* -------------------------------------------------------------------------- ** - * Tree Root Structure: This structure gives us a convenient handle for - * accessing whole AVL trees. The fields are: + * Typedefs continued... + * + * Tree Root Structure: This structure gives us a convenient handle for + * accessing whole AVL trees. The fields are: * root - A pointer to the root node of the AVL tree. * count - A count of the number of nodes stored in the tree. * cmp - A pointer to the comparison routine to be used when building or @@ -283,13 +293,15 @@ typedef void (*ubi_btKillNodeRtn)( ubi_btNodePtr ); * (bit 0x02) allowed to contain nodes with duplicate keys. * * NOTE: ubi_trInsert() tests ubi_trDUPKEY before ubi_trOVERWRITE. + * If duplicate keys are allowed, then no entry will be + * overwritten. * - * All of these values are set when you initialize the root structure by - * calling ubi_trInitTree(). - * -------------------------------------------------------------------------- ** + * All of these values are set when you initialize the root structure by + * calling ubi_trInitTree(). */ -typedef struct { +typedef struct + { ubi_btNodePtr root; /* A pointer to the root node of the tree */ unsigned long count; /* A count of the number of nodes in the tree */ ubi_btCompFunc cmp; /* A pointer to the tree's comparison function */ @@ -309,15 +321,15 @@ long ubi_btSgn( long x ); * * Input: x - a signed long integer value. * - * Output: the "sign" of x, represented as follows: + * Output: -1, 0, or 1 representing the "sign" of x as follows: * -1 == negative * 0 == zero (no sign) * 1 == positive * - * Note: This utility is provided in order to facilitate the conversion - * of C comparison function return values into BinTree direction - * values: {LEFT, PARENT, EQUAL}. It is INCORPORATED into the - * AbNormal() conversion macro! + * Notes: This utility is provided in order to facilitate the conversion + * of C comparison function return values into BinTree direction + * values: {ubi_trLEFT, ubi_trPARENT, ubi_trEQUAL}. It is + * incorporated into the Normalize() conversion macro. * * ------------------------------------------------------------------------ ** */ @@ -332,9 +344,9 @@ ubi_btNodePtr ubi_btInitNode( ubi_btNodePtr NodePtr ); * ------------------------------------------------------------------------ ** */ -ubi_btRootPtr ubi_btInitTree( ubi_btRootPtr RootPtr, - ubi_btCompFunc CompFunc, - unsigned char Flags ); +ubi_btRootPtr ubi_btInitTree( ubi_btRootPtr RootPtr, + ubi_btCompFunc CompFunc, + unsigned char Flags ); /* ------------------------------------------------------------------------ ** * Initialize the fields of a Tree Root header structure. * @@ -636,6 +648,8 @@ ubi_btNodePtr ubi_btLeafNode( ubi_btNodePtr leader ); * in pointers to nodes other than the root node each time. A * pointer to any node in the tree will do. Of course, if you * pass a pointer to a leaf node you'll get the same thing back. + * + If using a splay tree, splaying the tree will tend to randomize + * things a bit too. See ubi_SplayTree for more info. * * ------------------------------------------------------------------------ ** */ diff --git a/source3/ubiqx/ubi_SplayTree.c b/source3/ubiqx/ubi_SplayTree.c index 88be2ba9f4..fb4cc9f7c8 100644 --- a/source3/ubiqx/ubi_SplayTree.c +++ b/source3/ubiqx/ubi_SplayTree.c @@ -34,73 +34,17 @@ * * -------------------------------------------------------------------------- ** * - * Revision 2.5 1997/07/26 04:15:42 crh - * + Cleaned up a few minor syntax annoyances that gcc discovered for me. - * + Changed ubi_TRUE and ubi_FALSE to ubi_trTRUE and ubi_trFALSE. + * Log: ubi_SplayTree.c,v + * Revision 3.0 1997/12/08 05:32:28 crh + * This is a new major revision level because of a redesign of the handling + * of the pointers in the ubi_trNode structure. See ubi_BinTree for more + * info. * - * Revision 2.4 1997/06/03 04:42:21 crh - * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing - * problems. + * Revision 2; 1995/02/27 - 1997/12/07: + * Major changes: added the function ubi_sptSplay(). * - * Revision 2.3 1995/10/03 22:19:07 CRH - * Ubisized! - * Also, added the function ubi_sptSplay(). - * - * Revision 2.1 95/03/09 23:54:42 CRH - * Added the ModuleID static string and function. These modules are now - * self-identifying. - * - * Revision 2.0 95/02/27 22:34:46 CRH - * This module was updated to match the interface changes made to the - * ubi_BinTree module. In particular, the interface to the Locate() function - * has changed. See ubi_BinTree for more information on changes and new - * functions. - * - * The revision number was also upped to match ubi_BinTree. - * - * Revision 1.1 93/10/18 20:35:16 CRH - * I removed the hard-coded logical device names from the include file - * specifications. CRH - * - * Revision 1.0 93/10/15 23:00:15 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 0.1 93/04/25 22:03:32 CRH - * Simply changed the <exec/types.h> #include reference the .c file to - * use <stdlib.h> instead. The latter is portable, the former is not. + * Revision 1; 93/10/15 - 95/02/27: + * Added the ubi_tr defines. See ubi_BinTree.h for more info. * * Revision 0.0 93/04/21 23:05:52 CRH * Initial version, written by Christopher R. Hertel. @@ -117,8 +61,8 @@ */ static char ModuleID[] = "ubi_SplayTree\n\ -\tRevision: 2.5\n\ -\tDate: 1997/07/26 04:15:42\n\ +\tRevision: 3.0\n\ +\tDate: 1997/12/08 05:32:28\n\ \tAuthor: crh\n"; @@ -143,33 +87,33 @@ static void Rotate( ubi_btNodePtr p ) { ubi_btNodePtr parentp; ubi_btNodePtr tmp; - char way; - char revway; + signed char way; + signed char revway; - parentp = p->Link[PARENT]; /* Find parent. */ + parentp = p->Link[ubi_trPARENT]; /* Find parent. */ if( parentp ) /* If no parent, then we're already the root. */ { way = p->gender; - revway = RevWay(way); + revway = ubi_trRevWay(way); tmp = p->Link[revway]; parentp->Link[way] = tmp; if( tmp ) { - tmp->Link[PARENT] = parentp; - tmp->gender = way; + tmp->Link[ubi_trPARENT] = parentp; + tmp->gender = way; } - tmp = parentp->Link[PARENT]; - p->Link[PARENT] = tmp; - p->gender = parentp->gender; + tmp = parentp->Link[ubi_trPARENT]; + p->Link[ubi_trPARENT] = tmp; + p->gender = parentp->gender; if( tmp ) tmp->Link[p->gender] = p; - parentp->Link[PARENT] = p; - parentp->gender = revway; - p->Link[revway] = parentp; + parentp->Link[ubi_trPARENT] = p; + parentp->gender = revway; + p->Link[revway] = parentp; } } /* Rotate */ @@ -187,17 +131,17 @@ static ubi_btNodePtr Splay( ubi_btNodePtr SplayWithMe ) { ubi_btNodePtr parent; - while( (parent = SplayWithMe->Link[PARENT]) ) + while( (parent = SplayWithMe->Link[ubi_trPARENT]) ) { if( parent->gender == SplayWithMe->gender ) /* Zig-Zig */ Rotate( parent ); else { - if( EQUAL != parent->gender ) /* Zig-Zag */ + if( ubi_trEQUAL != parent->gender ) /* Zig-Zag */ Rotate( SplayWithMe ); } Rotate( SplayWithMe ); /* Zig */ - } /* while */ + } return( SplayWithMe ); } /* Splay */ @@ -289,24 +233,24 @@ ubi_btNodePtr ubi_sptRemove( ubi_btRootPtr RootPtr, ubi_btNodePtr DeadNode ) ubi_btNodePtr p; (void)Splay( DeadNode ); /* Move dead node to root. */ - if( (p = DeadNode->Link[LEFT]) ) /* If left subtree exists... */ + if( (p = DeadNode->Link[ubi_trLEFT]) ) /* If left subtree exists... */ { - ubi_btNodePtr q = DeadNode->Link[RIGHT]; + ubi_btNodePtr q = DeadNode->Link[ubi_trRIGHT]; - p->Link[PARENT] = NULL; /* Left subtree node becomes root.*/ - p->gender = PARENT; + p->Link[ubi_trPARENT] = NULL; /* Left subtree node becomes root.*/ + p->gender = ubi_trPARENT; p = ubi_btLast( p ); /* Find rightmost left tree node..*/ - p->Link[RIGHT] = q; /* ...attach right tree. */ + p->Link[ubi_trRIGHT] = q; /* ...attach right tree. */ if( q ) - q->Link[PARENT] = p; + q->Link[ubi_trPARENT] = p; RootPtr->root = Splay( p ); /* Resplay at p. */ } else { - if( (p = DeadNode->Link[RIGHT]) ) /* No left, but right subtree... */ + if( (p = DeadNode->Link[ubi_trRIGHT]) ) /* No left, but right subtree... */ { /* ...exists... */ - p->Link[PARENT] = NULL; /* Right subtree root becomes... */ - p->gender = PARENT; /* ...overall tree root. */ + p->Link[ubi_trPARENT] = NULL; /* Right subtree root becomes... */ + p->gender = ubi_trPARENT; /* ...overall tree root. */ RootPtr->root = p; } else @@ -424,7 +368,7 @@ void ubi_sptSplay( ubi_btRootPtr RootPtr, * Splaying the tree will not damage it (assuming that I've done * *my* job), but there is overhead involved. I don't recommend * that you use this function unless you understand the underlying - * Splay Tree principles involved. + * Splay Tree. * ------------------------------------------------------------------------ ** */ { diff --git a/source3/ubiqx/ubi_SplayTree.h b/source3/ubiqx/ubi_SplayTree.h index 7585d532ce..089fdc9d68 100644 --- a/source3/ubiqx/ubi_SplayTree.h +++ b/source3/ubiqx/ubi_SplayTree.h @@ -36,66 +36,17 @@ * * -------------------------------------------------------------------------- ** * - * Revision 2.5 1997/07/26 04:15:46 crh - * + Cleaned up a few minor syntax annoyances that gcc discovered for me. - * + Changed ubi_TRUE and ubi_FALSE to ubi_trTRUE and ubi_trFALSE. + * Log: ubi_SplayTree.h,v + * Revision 3.0 1997/12/08 05:32:35 crh + * This is a new major revision level because of a redesign of the handling + * of the pointers in the ubi_trNode structure. See ubi_BinTree for more + * info. * - * Revision 2.4 1997/06/03 05:22:56 crh - * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing - * problems. + * Revision 2; 1995/02/27 - 1997/12/07: + * Major changes: added the function ubi_sptSplay(). * - * Revision 2.3 1995/10/03 22:19:37 CRH - * Ubisized! - * Also, added the function ubi_sptSplay(). - * - * Revision 2.1 95/03/09 23:55:04 CRH - * Added the ModuleID static string and function. These modules are now - * self-identifying. - * - * Revision 2.0 95/02/27 22:34:55 CRH - * This module was updated to match the interface changes made to the - * ubi_BinTree module. In particular, the interface to the Locate() function - * has changed. See ubi_BinTree for more information on changes and new - * functions. - * - * The revision number was also upped to match ubi_BinTree. - * - * - * Revision 1.0 93/10/15 22:59:36 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/02/27: + * Added the ubi_tr defines. See ubi_BinTree.h for more info. * * Revision 0.0 93/04/21 23:07:13 CRH * Initial version, written by Christopher R. Hertel. @@ -266,7 +217,7 @@ void ubi_sptSplay( ubi_btRootPtr RootPtr, * Splaying the tree will not damage it (assuming that I've done * *my* job), but there is overhead involved. I don't recommend * that you use this function unless you understand the underlying - * Splay Tree principles involved. + * Splay Tree. * ------------------------------------------------------------------------ ** */ |