/* ========================================================================== **
* ubi_BinTree.c
*
- * Copyright (C) 1991-1997 by Christopher R. Hertel
+ * Copyright (C) 1991-1998 by Christopher R. Hertel
*
* 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 a simple binary tree.
*
* -------------------------------------------------------------------------- **
*
*
* -------------------------------------------------------------------------- **
*
- * $Log: ubi_BinTree.c,v $
- * Revision 1.1 1997/10/10 14:46:38 crh
- * This is the ubiqx binary tree and linked list library.
- * This library is being included as part of the Samba distribution.
- * (Hurray!)
+ * Log: ubi_BinTree.c,v
+ * Revision 4.10 2000/06/06 20:38:40 crh
+ * In the ReplaceNode() function, the old node header was being copied
+ * to the new node header using a byte-by-byte copy. This was causing
+ * the 'insure' software testing program to report a memory leak. The
+ * fix was to do a simple assignement: *newnode = *oldnode;
+ * This quieted the (errant) memory leak reports and is probably a bit
+ * faster than the bytewise copy.
+ *
+ * Revision 4.9 2000/01/08 23:24:30 crh
+ * Clarified a variety of if( pointer ) lines, replacing them with
+ * if( NULL != pointer ). This is more correct, and I have heard
+ * of at least one (obscure?) system out there that uses a non-zero
+ * value for NULL.
+ * Also, speed improvement in Neighbor(). It was comparing pointers
+ * when it could have compared two gender values. The pointer
+ * comparison was somewhat indirect (does pointer equal the pointer
+ * of the parent of the node pointed to by pointer). Urq.
+ *
+ * Revision 4.8 1999/09/22 03:40:30 crh
+ * Modified ubi_btTraverse() and ubi_btKillTree(). They now return an
+ * unsigned long indicating the number of nodes processed. The change
+ * is subtle. An empty tree formerly returned False, and now returns
+ * zero.
+ *
+ * Revision 4.7 1998/10/21 06:14:42 crh
+ * Fixed bugs in FirstOf() and LastOf() reported by Massimo Campostrini.
+ * See function comments.
+ *
+ * Revision 4.6 1998/07/25 17:02:10 crh
+ * Added the ubi_trNewTree() macro.
+ *
+ * Revision 4.5 1998/06/04 21:29:27 crh
+ * Upper-cased defined constants (eg UBI_BINTREE_H) in some header files.
+ * This is more "standard", and is what people expect. Weird, eh?
+ *
+ * Revision 4.4 1998/06/03 17:42:46 crh
+ * Further fiddling with sys_include.h. It's now in ubi_BinTree.h which is
+ * included by all of the binary tree files.
+ *
+ * Reminder: Some of the ubi_tr* macros in ubi_BinTree.h are redefined in
+ * ubi_AVLtree.h and ubi_SplayTree.h. This allows easy swapping
+ * of tree types by simply changing a header. Unfortunately, the
+ * macro redefinitions in ubi_AVLtree.h and ubi_SplayTree.h will
+ * conflict if used together. You must either choose a single tree
+ * type, or use the underlying function calls directly. Compare
+ * the two header files for more information.
+ *
+ * Revision 4.3 1998/06/02 01:28:43 crh
+ * Changed ubi_null.h to sys_include.h to make it more generic.
+ *
+ * Revision 4.2 1998/05/20 04:32:36 crh
+ * The C file now includes ubi_null.h. See ubi_null.h for more info.
+ * Also, the balance and gender fields of the node were declared as
+ * signed char. As I understand it, at least one SunOS or Solaris
+ * compiler doesn't like "signed char". The declarations were
+ * wrong anyway, so I changed them to simple "char".
+ *
+ * Revision 4.1 1998/03/31 06:11:57 crh
+ * Thomas Aglassinger sent E'mail pointing out errors in the
+ * dereferencing of function pointers, and a missing typecast.
+ * Thanks, Thomas!
+ *
+ * Revision 4.0 1998/03/10 03:19:22 crh
+ * Added the AVL field 'balance' to the ubi_btNode structure. This means
+ * that all BinTree modules now use the same basic node structure, which
+ * greatly simplifies the AVL module.
+ * Decided that this was a big enough change to justify a new major revision
+ * number. 3.0 was an error, so we're at 4.0.
+ *
+ * Revision 2.6 1998/01/24 06:27:46 crh
+ * Added ubi_trCount() macro.
+ *
+ * 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'.
*
* Revision 2.4 1997/07/26 04:11:10 crh
* + Just to be annoying I changed ubi_TRUE and ubi_FALSE to ubi_trTRUE
*
* 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".
+ * For example, if you were using ubi_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
* ========================================================================== **
*/
-#include "ubi_BinTree.h" /* Header for this module */
-#include <stdlib.h> /* Standard C definitions. */
+#include "ubi_BinTree.h" /* Header for this module. */
/* ========================================================================== **
* Static data.
*/
static char ModuleID[] = "ubi_BinTree\n\
-\t$Revision: 1.1 $\n\
-\t$Date: 1997/10/10 14:46:38 $\n\
-\t$Author: crh $\n";
+\tRevision: 4.10 \n\
+\tDate: 2000/06/06 20:38:40 \n\
+\tAuthor: crh \n";
/* ========================================================================== **
* Internal (private) functions.
* ------------------------------------------------------------------------ **
*/
{
- char tmp;
+ int tmp;
- while( p && (( tmp = AbNormal((*cmp)(FindMe, p)) ) != EQUAL) )
+ while( (NULL != p)
+ && ((tmp = ubi_trAbNormal( (*cmp)(FindMe, p) )) != ubi_trEQUAL) )
p = p->Link[tmp];
return( p );
* ------------------------------------------------------------------------ **
*/
{
- register ubi_btNodePtr tmp_p = p;
- ubi_btNodePtr tmp_pp = NULL;
- char tmp_sex = EQUAL;
- char tmp_cmp;
+ register ubi_btNodePtr tmp_p = p;
+ ubi_btNodePtr tmp_pp = NULL;
+ char tmp_gender = ubi_trEQUAL;
+ int tmp_cmp;
- while( tmp_p && (EQUAL != (tmp_cmp = AbNormal((*CmpFunc)(findme, tmp_p)))) )
+ while( (NULL != tmp_p)
+ && (ubi_trEQUAL != (tmp_cmp = ubi_trAbNormal((*CmpFunc)(findme, tmp_p)))) )
{
- tmp_pp = tmp_p; /* Keep track of previous node. */
- tmp_sex = 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 = (char)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:
* that now reads:
* ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
* Bleah!
- * ------------------------------------------------------------------ *
+ * ------------------------------------------------------------------------ **
*/
{
- register int i;
- register int btNodeSize = sizeof( ubi_btNode );
+ *newnode = *oldnode; /* Copy node internals to new node. */
- 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. */
+ (*parent) = newnode; /* Old node's parent points to new child. */
/* 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,
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( NULL != Node1->Link[ubi_trPARENT] )
+ 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[PARENT] )
- Parent = &((Node2->Link[PARENT])->Link[Node2->gender]);
+ if( NULL != Node2->Link[ubi_trPARENT] )
+ 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[PARENT] )
- Parent = &((dummy_p->Link[PARENT])->Link[dummy_p->gender]);
+ if( NULL != dummy_p->Link[ubi_trPARENT] )
+ 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 char whichway )
+ register int whichway )
/* ------------------------------------------------------------------------ **
* Slide down the side of a subtree.
*
* ------------------------------------------------------------------------ **
*/
{
- ubi_btNodePtr Q = NULL;
- while( P )
- {
- Q = P;
- P = P->Link[ whichway ];
- }
- return( Q );
+ if( NULL != P )
+ while( NULL != P->Link[ whichway ] )
+ P = P->Link[ whichway ];
+ return( P );
} /* SubSlide */
static ubi_btNodePtr Neighbor( register ubi_btNodePtr P,
- register 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 ], (char)RevWay(whichway) ) );
+ if( NULL != P->Link[ whichway ] )
+ return( SubSlide( P->Link[ whichway ], (char)ubi_trRevWay(whichway) ) );
else
- while( P->Link[ PARENT ] )
+ while( NULL != P->Link[ ubi_trPARENT ] )
{
- if( (P->Link[ PARENT ])->Link[ whichway ] == P )
- P = P->Link[ PARENT ];
+ if( whichway == P->gender )
+ P = P->Link[ ubi_trPARENT ];
else
- return( P->Link[ PARENT ] );
+ return( P->Link[ ubi_trPARENT ] );
}
}
return( NULL );
static ubi_btNodePtr Border( ubi_btRootPtr RootPtr,
ubi_btItemPtr FindMe,
ubi_btNodePtr p,
- 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.
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( (NULL != q)
+ && (ubi_trEQUAL == ubi_trAbNormal( (*(RootPtr->cmp))(FindMe, q) )) )
{
p = q;
- q = p->Link[PARENT];
+ q = p->Link[ubi_trPARENT];
}
/* Next, move back down in the "whichway" direction. */
q = p->Link[whichway];
- while( q )
+ while( NULL != q )
{
- if( q = qFind( RootPtr->cmp, FindMe, q ) )
+ q = qFind( RootPtr->cmp, FindMe, q );
+ if( q )
{
p = q;
q = p->Link[whichway];
* 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!
+ * ubi_trAbNormal() conversion macro!
*
* ------------------------------------------------------------------------ **
*/
* ------------------------------------------------------------------------ **
*/
{
- 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;
+ NodePtr->balance = ubi_trEQUAL;
return( NodePtr );
} /* ubi_btInitNode */
ubi_btRootPtr ubi_btInitTree( ubi_btRootPtr RootPtr,
ubi_btCompFunc CompFunc,
- unsigned char Flags )
+ char Flags )
/* ------------------------------------------------------------------------ **
* Initialize the fields of a Tree Root header structure.
*
parent = NULL;
char tmp;
- if( !(OldNode) ) /* If they didn't give us a pointer, supply our own. */
+ if( NULL == OldNode ) /* If they didn't give us a pointer, supply our own. */
OldNode = &OtherP;
(void)ubi_btInitNode( NewNode ); /* Init the new node's BinTree fields. */
*OldNode = TreeFind(ItemPtr, (RootPtr->root), &parent, &tmp, (RootPtr->cmp));
/* Now add the node to the tree... */
- if (!(*OldNode)) /* The easy one: we have a space for a new node! */
+ if( NULL == (*OldNode) ) /* The easy one: we have a space for a new node! */
{
- if (!(parent))
+ if( NULL == parent )
RootPtr->root = NewNode;
else
{
- parent->Link[tmp] = NewNode;
- NewNode->Link[PARENT] = parent;
- NewNode->gender = tmp;
+ parent->Link[(int)tmp] = NewNode;
+ NewNode->Link[ubi_trPARENT] = parent;
+ NewNode->gender = tmp;
}
(RootPtr->count)++;
return( ubi_trTRUE );
/* 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 )
+ while( NULL != q )
{
parent = q;
- if( tmp == EQUAL ) tmp = RIGHT;
- q = q->Link[tmp];
+ if( tmp == ubi_trEQUAL )
+ tmp = ubi_trRIGHT;
+ q = q->Link[(int)tmp];
if ( q )
- tmp = AbNormal( (*(RootPtr->cmp))(ItemPtr, q) );
+ tmp = ubi_trAbNormal( (*(RootPtr->cmp))(ItemPtr, q) );
}
- parent->Link[tmp] = NewNode;
- NewNode->Link[PARENT] = parent;
- NewNode->gender = tmp;
+ parent->Link[(int)tmp] = NewNode;
+ NewNode->Link[ubi_trPARENT] = parent;
+ NewNode->gender = tmp;
(RootPtr->count)++;
return( ubi_trTRUE );
}
* 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))
+ if( NULL == 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;
- 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
* node, which is garunteed to have no RIGHT child.
*/
- if( (DeadNode->Link[LEFT]) && (DeadNode->Link[RIGHT]) )
+ if( (NULL != DeadNode->Link[ubi_trLEFT])
+ && (NULL != 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]);
- else
+ if( NULL == DeadNode->Link[ubi_trPARENT] )
parentp = &( RootPtr->root );
+ else
+ parentp = &((DeadNode->Link[ubi_trPARENT])->Link[(int)(DeadNode->gender)]);
/* 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 )
+ if( NULL != p )
{
- p->Link[PARENT] = DeadNode->Link[PARENT];
+ p->Link[ubi_trPARENT] = DeadNode->Link[ubi_trPARENT];
p->gender = DeadNode->gender;
}
(*parentp) = p;
&whichkid,
RootPtr->cmp );
- if( p ) /* If we have found a match, we can resolve as follows: */
+ if( NULL != p ) /* If we have found a match, we can resolve as follows: */
{
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 ) );
+ default:
+ p = Border( RootPtr, FindMe, p, ubi_trLEFT );
+ return( p );
}
- p = Border( RootPtr, FindMe, p, LEFT );
- return( p );
}
/* Else, no match. */
* 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,
* ------------------------------------------------------------------------ **
*/
{
- return( Neighbor( P, RIGHT ) );
+ return( Neighbor( P, ubi_trRIGHT ) );
} /* ubi_btNext */
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 )
* ------------------------------------------------------------------------ **
*/
{
- return( SubSlide( P, LEFT ) );
+ return( SubSlide( P, ubi_trLEFT ) );
} /* ubi_btFirst */
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,
* matching <FindMe>.
* Notes: Node *p MUST be in the set of nodes with keys matching
* <FindMe>. If not, this function will return NULL.
+ *
+ * 4.7: Bug found & fixed by Massimo Campostrini,
+ * Istituto Nazionale di Fisica Nucleare, Sezione di Pisa.
+ *
* ------------------------------------------------------------------------ **
*/
{
/* If our starting point is invalid, return NULL. */
- if( !p || AbNormal( (*(RootPtr->cmp))( MatchMe, p ) != EQUAL ) )
+ if( (NULL == p)
+ || (ubi_trEQUAL != ubi_trAbNormal( (*(RootPtr->cmp))( MatchMe, p ) )) )
return( NULL );
- return( Border( RootPtr, MatchMe, p, LEFT ) );
+ return( Border( RootPtr, MatchMe, p, ubi_trLEFT ) );
} /* ubi_btFirstOf */
ubi_btNodePtr ubi_btLastOf( ubi_btRootPtr RootPtr,
* matching <FindMe>.
* Notes: Node *p MUST be in the set of nodes with keys matching
* <FindMe>. If not, this function will return NULL.
+ *
+ * 4.7: Bug found & fixed by Massimo Campostrini,
+ * Istituto Nazionale di Fisica Nucleare, Sezione di Pisa.
+ *
* ------------------------------------------------------------------------ **
*/
{
/* If our starting point is invalid, return NULL. */
- if( !p || AbNormal( (*(RootPtr->cmp))( MatchMe, p ) != EQUAL ) )
+ if( (NULL != p)
+ || (ubi_trEQUAL != ubi_trAbNormal( (*(RootPtr->cmp))( MatchMe, p ) )) )
return( NULL );
- return( Border( RootPtr, MatchMe, p, RIGHT ) );
+ return( Border( RootPtr, MatchMe, p, ubi_trRIGHT ) );
} /* ubi_btLastOf */
-ubi_trBool ubi_btTraverse( ubi_btRootPtr RootPtr,
- ubi_btActionRtn EachNode,
- void *UserData )
+unsigned long ubi_btTraverse( ubi_btRootPtr RootPtr,
+ ubi_btActionRtn EachNode,
+ void *UserData )
/* ------------------------------------------------------------------------ **
* Traverse a tree in sorted order (non-recursively). At each node, call
* (*EachNode)(), passing a pointer to the current node, and UserData as the
* second parameter.
+ *
* Input: RootPtr - a pointer to an ubi_btRoot structure that indicates
* the tree to be traversed.
* EachNode - a pointer to a function to be called at each node
* as the node is visited.
* UserData - a generic pointer that may point to anything that
* you choose.
- * Output: A boolean value. FALSE if the tree is empty, otherwise TRUE.
+ *
+ * Output: A count of the number of nodes visited. This will be zero
+ * if the tree is empty.
+ *
* ------------------------------------------------------------------------ **
*/
{
- ubi_btNodePtr p;
-
- if( !(p = ubi_btFirst( RootPtr->root )) ) return( ubi_trFALSE );
+ ubi_btNodePtr p = ubi_btFirst( RootPtr->root );
+ unsigned long count = 0;
- while( p )
+ while( NULL != p )
{
- EachNode( p, UserData );
+ (*EachNode)( p, UserData );
+ count++;
p = ubi_btNext( p );
}
- return( ubi_trTRUE );
+ return( count );
} /* ubi_btTraverse */
-ubi_trBool ubi_btKillTree( ubi_btRootPtr RootPtr,
- ubi_btKillNodeRtn FreeNode )
+unsigned long ubi_btKillTree( ubi_btRootPtr RootPtr,
+ ubi_btKillNodeRtn FreeNode )
/* ------------------------------------------------------------------------ **
* Delete an entire tree (non-recursively) and reinitialize the ubi_btRoot
- * structure. Note that this function will return FALSE if either parameter
- * is NULL.
+ * structure. Return a count of the number of nodes deleted.
*
* Input: RootPtr - a pointer to an ubi_btRoot structure that indicates
* the root of the tree to delete.
* FreeNode - a function that will be called for each node in the
* tree to deallocate the memory used by the node.
*
- * Output: A boolean value. FALSE if either input parameter was NULL, else
- * TRUE.
+ * Output: The number of nodes removed from the tree.
+ * A value of 0 will be returned if:
+ * - The tree actually contains 0 entries.
+ * - the value of <RootPtr> is NULL, in which case the tree is
+ * assumed to be empty
+ * - the value of <FreeNode> is NULL, in which case entries
+ * cannot be removed, so 0 is returned. *Make sure that you
+ * provide a valid value for <FreeNode>*.
+ * In all other cases, you should get a positive value equal to
+ * the value of RootPtr->count upon entry.
*
* ------------------------------------------------------------------------ **
*/
{
ubi_btNodePtr p, q;
+ unsigned long count = 0;
- if( !(RootPtr) || !(FreeNode) )
- return( ubi_trFALSE );
+ if( (NULL == RootPtr) || (NULL == FreeNode) )
+ return( 0 );
p = ubi_btFirst( RootPtr->root );
- while( p )
+ while( NULL != p )
{
q = p;
- while( q->Link[RIGHT] )
- q = SubSlide( q->Link[RIGHT], LEFT );
- p = q->Link[PARENT];
- if( p )
- p->Link[ ((p->Link[LEFT] == q)?LEFT:RIGHT) ] = NULL;
- FreeNode((void *)q);
+ while( q->Link[ubi_trRIGHT] )
+ q = SubSlide( q->Link[ubi_trRIGHT], ubi_trLEFT );
+ p = q->Link[ubi_trPARENT];
+ if( NULL != p )
+ p->Link[ ((p->Link[ubi_trLEFT] == q)?ubi_trLEFT:ubi_trRIGHT) ] = NULL;
+ (*FreeNode)((void *)q);
+ count++;
}
+ /* overkill... */
(void)ubi_btInitTree( RootPtr,
RootPtr->cmp,
RootPtr->flags );
- return( ubi_trTRUE );
+ return( count );
} /* ubi_btKillTree */
ubi_btNodePtr ubi_btLeafNode( ubi_btNodePtr leader )
*/
{
ubi_btNodePtr follower = NULL;
- int whichway = LEFT;
+ int whichway = ubi_trLEFT;
while( NULL != leader )
{
leader = follower->Link[ whichway ];
if( NULL == leader )
{
- whichway = RevWay( whichway );
+ whichway = ubi_trRevWay( whichway );
leader = follower->Link[ whichway ];
}
}
git.samba.org / jra / samba / .git / blobdiff