* Email: crh@ubiqx.mn.org
* -------------------------------------------------------------------------- **
*
- * This module implements simple binary trees.
+ * This module implements a simple binary tree.
*
* -------------------------------------------------------------------------- **
*
* -------------------------------------------------------------------------- **
*
* 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:
+ * Revision 2.5 1997/12/23 03:56:29 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'.
*
- * typedef struct ubi_btNodeStruct
- * {
- * struct ubi_btNodeStruct *Link[3];
- * signed char gender;
- * } ubi_btNode;
+ * 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().
*
- * As a result, the pointers were indexed as
+ * 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.
*
- * Link[0] == Left Child
- * Link[1] == Parent
- * Link[2] == Right Child
+ * 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:
*
- * With this release, the node structure changes to:
+ * 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.
*
- * typedef struct ubi_btNodeStruct
- * {
- * struct ubi_btNodeStruct *leftlink
- * struct ubi_btNodeStruct *Link[2];
- * signed char gender;
- * } ubi_btNode;
+ * 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.
*
- * 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:
+ * 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:
*
* Module Prefix
* ubi_BinTree ubi_bt
* ubi_AVLtree ubi_avl
* ubi_SplayTree ubi_spt
*
- * 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".
+ * 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 is confusing.
+ * 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 added a set of defined names that get redefined in any of the
+ * 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
* 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, or if you plan to use two or more specific tree types
- * in the same piece of code. CRH
+ * red/black trees. CRH
*
* V0.0 - June, 1991 - Written by Christopher R. Hertel (CRH).
*
*/
static char ModuleID[] = "ubi_BinTree\n\
-\tRevision: 3.0\n\
-\tDate: 1997/12/08 06:49:11\n\
+\tRevision: 2.5\n\
+\tDate: 1997/12/23 03:56:29\n\
\tAuthor: crh\n";
/* ========================================================================== **
/* ------------------------------------------------------------------------ **
* This function performs a non-recursive search of a tree for a node
* matching a specific key. It is called "qFind()" because it is
- * (probably a little bit) faster that TreeFind (below).
+ * faster that TreeFind (below).
*
* Input:
* cmp - a pointer to the tree's comparison function.
* ------------------------------------------------------------------------ **
*/
{
- signed char tmp;
+ int tmp;
- while( p && (( tmp = ubi_trNormalize((*cmp)(FindMe, p)) ) != ubi_trEQUAL) )
+ while( p && (( tmp = ubi_trAbNormal((*cmp)(FindMe, p)) ) != ubi_trEQUAL) )
p = p->Link[tmp];
return( p );
static ubi_btNodePtr TreeFind( ubi_btItemPtr findme,
ubi_btNodePtr p,
ubi_btNodePtr *parentp,
- signed char *gender,
+ char *gender,
ubi_btCompFunc CmpFunc )
/* ------------------------------------------------------------------------ **
* TreeFind() searches a tree for a given value (findme). It will return a
{
register ubi_btNodePtr tmp_p = p;
ubi_btNodePtr tmp_pp = NULL;
- signed char tmp_gender = ubi_trEQUAL;
- signed char tmp_cmp;
+ int tmp_gender = ubi_trEQUAL;
+ int tmp_cmp;
while( tmp_p
- && (ubi_trEQUAL != (tmp_cmp = ubi_trNormalize((*CmpFunc)(findme, tmp_p))))
- )
+ && (ubi_trEQUAL != (tmp_cmp = ubi_trAbNormal((*CmpFunc)(findme, tmp_p)))) )
{
- tmp_pp = tmp_p; /* Keep track of previous node. */
- tmp_gender = tmp_cmp; /* Keep track of sex of child. */
- tmp_p = tmp_p->Link[tmp_cmp]; /* Go to child. */
+ tmp_pp = tmp_p; /* Keep track of previous node. */
+ 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_gender;
static void ReplaceNode( ubi_btNodePtr *parent,
ubi_btNodePtr oldnode,
ubi_btNodePtr newnode )
- /* ------------------------------------------------------------------------ **
+ /* ------------------------------------------------------------------ *
* Remove node oldnode from the tree, replacing it with node newnode.
*
* Input:
* 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;
for( i = 0; i < btNodeSize; i++ ) /* Copy node internals to new node. */
((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
-
- /* Old node's parent points to new child. */
- (*parent) = newnode;
-
+ (*parent) = newnode; /* Old node's parent points to new child. */
/* Now tell the children about their new step-parent. */
- if( oldnode->Link[ubi_trLEFT ] )
- (oldnode->Link[ubi_trLEFT ])->Link[ubi_trPARENT] = 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,
/* Replace Node 1 with the dummy, thus removing Node1 from the tree. */
if( Node1->Link[ubi_trPARENT] )
- Parent = &((Node1->Link[ubi_trPARENT])->Link[Node1->gender]);
+ Parent = &((Node1->Link[ubi_trPARENT])->Link[(int)(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[ubi_trPARENT] )
- Parent = &((Node2->Link[ubi_trPARENT])->Link[Node2->gender]);
+ Parent = &((Node2->Link[ubi_trPARENT])->Link[(int)(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[ubi_trPARENT] )
- Parent = &((dummy_p->Link[ubi_trPARENT])->Link[dummy_p->gender]);
+ Parent = &((dummy_p->Link[ubi_trPARENT])->Link[(int)(dummy_p->gender)]);
else
Parent = &(RootPtr->root);
ReplaceNode( Parent, dummy_p, Node2 );
*/
static ubi_btNodePtr SubSlide( register ubi_btNodePtr P,
- register signed char whichway )
+ register int whichway )
/* ------------------------------------------------------------------------ **
* Slide down the side of a subtree.
*
} /* SubSlide */
static ubi_btNodePtr Neighbor( register ubi_btNodePtr P,
- register signed char whichway )
+ register int whichway )
/* ------------------------------------------------------------------------ **
* Given starting point p, return the (key order) next or preceeding node
* in the tree.
if( P )
{
if( P->Link[ whichway ] )
- return( SubSlide( P->Link[ whichway ], ubi_trRevWay(whichway) ) );
+ return( SubSlide( P->Link[ whichway ], (char)ubi_trRevWay(whichway) ) );
else
while( P->Link[ ubi_trPARENT ] )
{
static ubi_btNodePtr Border( ubi_btRootPtr RootPtr,
ubi_btItemPtr FindMe,
ubi_btNodePtr p,
- signed char whichway )
+ int whichway )
/* ------------------------------------------------------------------------ **
* Given starting point p, which has a key value equal to *FindMe, locate
* the first (index order) node with the same key value.
* subtree that contains all of the matching nodes.
*/
q = p->Link[ubi_trPARENT];
- while( q && (ubi_trEQUAL == ubi_trNormalize( (*(RootPtr->cmp))(FindMe, q) )) )
+ while( q && (ubi_trEQUAL == ubi_trAbNormal( (*(RootPtr->cmp))(FindMe, q) )) )
{
p = q;
q = p->Link[ubi_trPARENT];
q = p->Link[whichway];
while( q )
{
- if( q = qFind( RootPtr->cmp, FindMe, q ) )
+ q = qFind( RootPtr->cmp, FindMe, q );
+ if( q )
{
p = q;
q = p->Link[whichway];
*
* Input: x - a signed long integer value.
*
- * Output: -1, 0, or 1 representing the "sign" of x as follows:
+ * Output: the "sign" of x, represented 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: {ubi_trLEFT, ubi_trPARENT, ubi_trEQUAL}. It is
- * incorporated into the ubi_trNormalize() conversion macro.
+ * 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
+ * ubi_trAbNormal() conversion macro!
*
* ------------------------------------------------------------------------ **
*/
{
ubi_btNodePtr OtherP,
parent = NULL;
- signed char tmp;
+ char tmp;
if( !(OldNode) ) /* If they didn't give us a pointer, supply our own. */
OldNode = &OtherP;
RootPtr->root = NewNode;
else
{
- parent->Link[tmp] = NewNode;
+ parent->Link[(int)tmp] = NewNode;
NewNode->Link[ubi_trPARENT] = parent;
NewNode->gender = tmp;
}
parent = q;
if( tmp == ubi_trEQUAL )
tmp = ubi_trRIGHT;
- q = q->Link[tmp];
+ q = q->Link[(int)tmp];
if ( q )
- tmp = ubi_trNormalize( (*(RootPtr->cmp))(ItemPtr, q) );
+ tmp = ubi_trAbNormal( (*(RootPtr->cmp))(ItemPtr, q) );
}
- parent->Link[tmp] = NewNode;
+ parent->Link[(int)tmp] = NewNode;
NewNode->Link[ubi_trPARENT] = parent;
NewNode->gender = tmp;
(RootPtr->count)++;
if (!(parent))
ReplaceNode( &(RootPtr->root), *OldNode, NewNode );
else
- ReplaceNode( &(parent->Link[(*OldNode)->gender]), *OldNode, NewNode );
+ ReplaceNode( &(parent->Link[(int)((*OldNode)->gender)]),
+ *OldNode, NewNode );
return( ubi_trTRUE );
}
{
ubi_btNodePtr p,
*parentp;
- signed char tmp;
+ int 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
* a pointer to the parent pointer, whatever it is.
*/
if (DeadNode->Link[ubi_trPARENT])
- parentp = &((DeadNode->Link[ubi_trPARENT])->Link[DeadNode->gender]);
+ parentp = &((DeadNode->Link[ubi_trPARENT])->Link[(int)(DeadNode->gender)]);
else
parentp = &( RootPtr->root );
/* Now link the parent to the only grand-child and patch up the gender. */
- tmp = ((DeadNode->Link[ubi_trLEFT]) ? ubi_trLEFT : ubi_trRIGHT);
+ tmp = ((DeadNode->Link[ubi_trLEFT])?ubi_trLEFT:ubi_trRIGHT);
p = (DeadNode->Link[tmp]);
if( p )
{
p->Link[ubi_trPARENT] = DeadNode->Link[ubi_trPARENT];
- p->gender = DeadNode->gender;
+ p->gender = DeadNode->gender;
}
(*parentp) = p;
{
register ubi_btNodePtr p;
ubi_btNodePtr parent;
- signed char whichkid;
+ char whichkid;
/* Start by searching for a matching node. */
p = TreeFind( FindMe,
case ubi_trGT: /* ...and then a jump to the right. */
p = Border( RootPtr, FindMe, p, ubi_trRIGHT );
return( Neighbor( p, ubi_trRIGHT ) );
+ default:
+ p = Border( RootPtr, FindMe, p, ubi_trLEFT );
+ return( p );
}
- p = Border( RootPtr, FindMe, p, ubi_trLEFT );
- return( p );
}
/* Else, no match. */
* Remaining possibilities are LT and GT (including LE & GE).
*/
if( (ubi_trLT == CompOp) || (ubi_trLE == CompOp) )
- return( (ubi_trLEFT == whichkid) ? Neighbor( parent, whichkid ) : parent );
+ return( (ubi_trLEFT == whichkid) ? Neighbor( parent, whichkid ) : parent );
else
return( (ubi_trRIGHT == whichkid) ? Neighbor( parent, whichkid ) : parent );
} /* ubi_btLocate */
*/
{
/* If our starting point is invalid, return NULL. */
- if( !p || ubi_trNormalize( (*(RootPtr->cmp))( MatchMe, p ) != ubi_trEQUAL ) )
+ if( !p || ubi_trAbNormal( (*(RootPtr->cmp))( MatchMe, p ) != ubi_trEQUAL ) )
return( NULL );
return( Border( RootPtr, MatchMe, p, ubi_trLEFT ) );
} /* ubi_btFirstOf */
*/
{
/* If our starting point is invalid, return NULL. */
- if( !p || ubi_trNormalize( (*(RootPtr->cmp))( MatchMe, p ) != ubi_trEQUAL ) )
+ if( !p || ubi_trAbNormal( (*(RootPtr->cmp))( MatchMe, p ) != ubi_trEQUAL ) )
return( NULL );
return( Border( RootPtr, MatchMe, p, ubi_trRIGHT ) );
} /* ubi_btLastOf */
* 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.
*
* ------------------------------------------------------------------------ **
*/
while( NULL != leader )
{
- /* The next line is a weak attempt at randomizing. */
- whichway = ((int)leader & 0x0010) ? whichway : ubi_trRevWay(whichway);
follower = leader;
- leader = leader->Link[ whichway ];
+ leader = follower->Link[ whichway ];
if( NULL == leader )
{
whichway = ubi_trRevWay( whichway );
return( 0 );
} /* ubi_btModuleID */
+
/* ========================================================================== */
git.samba.org / samba.git / blobdiff