/* ========================================================================== **
* ubi_AVLtree.c
*
- * Copyright (C) 1991-1997 by Christopher R. Hertel
+ * Copyright (C) 1991-1998 by Christopher R. Hertel
*
* Email: crh@ubiqx.mn.org
* -------------------------------------------------------------------------- **
* 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
*
* -------------------------------------------------------------------------- **
*
- * 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.
+ * Log: ubi_AVLtree.c,v
+ * Revision 4.1 1998/05/20 04:35:50 crh
+ * The C file now includes ubi_null.h. See ubi_null.h for more info.
+ *
+ * Revision 4.0 1998/03/10 03:37:09 crh
+ * Major changes.
+ * By adding the AVL balance field to the base ubi_btNode structure, I no
+ * longer need AVL-specific ReplaceNode(), SwapNodes(), and InitNode()
+ * functions. The Remove() function is also simplified. It's all much
+ * cleaner.
+ * This is rev. 4.0. The 3.x series was dropped.
+ *
+ * Revision 2.5 1997/12/23 04:00:42 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: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_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.
*
- * 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!
+ * 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 1; 93/10/15 - 95/03/05:
- * Added the ubi_tr defines. See ubi_BinTree.h for more info.
+ * Note that the original names do still exist, and can be used if you wish
+ * to write code directly to a specific module. This should probably only be
+ * done if you are planning to implement a new descendant type, such as
+ * red/black trees. CRH
*
* V0.0 - May, 1990 - Written by Christopher R. Hertel (CRH).
*
* ========================================================================= **
*/
-#include "ubi_AVLtree.h" /* Header for THIS module. */
-#include <stdlib.h> /* Standard C definitions, etc. */
+#include "ubi_null.h" /* ubiqx NULL source. */
+#include "ubi_AVLtree.h" /* Header for THIS module. */
/* ========================================================================== **
* Static data.
*/
static char ModuleID[] = "ubi_AVLtree\n\
-\tRevision: 3.0\n\
-\tDate: 1997/12/08 05:38:55\n\
-\tAuthor: crh\n";
+\tRevision: 4.1 \n\
+\tDate: 1998/05/20 04:35:50 \n\
+\tAuthor: crh \n";
/* ========================================================================== **
* The next set of functions are the AVL balancing routines. There are left
* -------------------------------------------------------------------------- **
*/
-static ubi_avlNodePtr L1( ubi_avlNodePtr p )
+static ubi_btNodePtr L1( ubi_btNodePtr p )
/* ------------------------------------------------------------------------ **
* Single rotate left.
*
* ------------------------------------------------------------------------ **
*/
{
- ubi_avlNodePtr tmp;
+ ubi_btNodePtr tmp;
tmp = p->Link[ubi_trRIGHT];
p->Link[ubi_trRIGHT] = tmp->Link[ubi_trLEFT];
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;
+ (tmp->Link[ubi_trPARENT])->Link[(int)(tmp->gender)] = tmp;
p->Link[ubi_trPARENT] = tmp;
p->gender = ubi_trLEFT;
if( p->Link[ubi_trRIGHT] )
p->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = p;
(p->Link[ubi_trRIGHT])->gender = ubi_trRIGHT;
}
- p->balance -= tmp->balance;
+ p->balance -= ubi_trNormalize( tmp->balance );
(tmp->balance)--;
return( tmp );
} /* L1 */
-static ubi_avlNodePtr R1( ubi_avlNodePtr p )
+static ubi_btNodePtr R1( ubi_btNodePtr p )
/* ------------------------------------------------------------------------ **
* Single rotate right.
*
* ------------------------------------------------------------------------ **
*/
{
- ubi_avlNodePtr tmp;
+ ubi_btNodePtr tmp;
tmp = p->Link[ubi_trLEFT];
p->Link[ubi_trLEFT] = tmp->Link[ubi_trRIGHT];
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;
+ (tmp->Link[ubi_trPARENT])->Link[(int)(tmp->gender)] = tmp;
p->Link[ubi_trPARENT] = tmp;
p->gender = ubi_trRIGHT;
if(p->Link[ubi_trLEFT])
p->Link[ubi_trLEFT]->Link[ubi_trPARENT] = p;
p->Link[ubi_trLEFT]->gender = ubi_trLEFT;
}
- p->balance -= tmp->balance;
+ p->balance -= ubi_trNormalize( tmp->balance );
(tmp->balance)++;
return( tmp );
} /* R1 */
-static ubi_avlNodePtr L2( ubi_avlNodePtr tree )
+static ubi_btNodePtr L2( ubi_btNodePtr tree )
/* ------------------------------------------------------------------------ **
* Double rotate left.
*
* ------------------------------------------------------------------------ **
*/
{
- ubi_avlNodePtr tmp, newroot;
+ ubi_btNodePtr tmp, newroot;
tmp = tree->Link[ubi_trRIGHT];
newroot = tmp->Link[ubi_trLEFT];
tmp->Link[ubi_trLEFT]->gender = ubi_trLEFT;
}
if(newroot->Link[ubi_trPARENT])
- newroot->Link[ubi_trPARENT]->Link[newroot->gender] = newroot;
+ newroot->Link[ubi_trPARENT]->Link[(int)(newroot->gender)] = newroot;
switch( newroot->balance )
{
return( newroot );
} /* L2 */
-static ubi_avlNodePtr R2( ubi_avlNodePtr tree )
+static ubi_btNodePtr R2( ubi_btNodePtr tree )
/* ------------------------------------------------------------------------ **
* Double rotate right.
*
* ------------------------------------------------------------------------ **
*/
{
- ubi_avlNodePtr tmp, newroot;
+ ubi_btNodePtr tmp, newroot;
tmp = tree->Link[ubi_trLEFT];
newroot = tmp->Link[ubi_trRIGHT];
tmp->Link[ubi_trRIGHT]->gender = ubi_trRIGHT;
}
if(newroot->Link[ubi_trPARENT])
- newroot->Link[ubi_trPARENT]->Link[newroot->gender] = newroot;
+ newroot->Link[ubi_trPARENT]->Link[(int)(newroot->gender)] = newroot;
switch( newroot->balance )
{
} /* R2 */
-static ubi_avlNodePtr Adjust( ubi_avlNodePtr p, signed char LorR )
+static ubi_btNodePtr Adjust( ubi_btNodePtr p, char LorR )
/* ------------------------------------------------------------------------ **
* Adjust the balance value at node *p. If necessary, rotate the subtree
* rooted at p.
*/
{
if( p->balance != LorR )
- p->balance += LorR;
+ p->balance += ubi_trNormalize(LorR);
else
{
- signed char tallerbal; /* Balance of root of the taller subtree of p. */
+ char tallerbal; /* Balance value of the root of the taller subtree of p. */
- tallerbal = p->Link[LorR]->balance;
+ tallerbal = p->Link[(int)LorR]->balance;
if( ( ubi_trEQUAL == tallerbal ) || ( p->balance == tallerbal ) )
p = ( (ubi_trLEFT==LorR) ? R1(p) : L1(p) ); /* single rotation */
else
return( p );
} /* Adjust */
-static ubi_avlNodePtr Rebalance( ubi_avlNodePtr Root,
- ubi_avlNodePtr subtree,
- signed char LorR )
+static ubi_btNodePtr Rebalance( ubi_btNodePtr Root,
+ ubi_btNodePtr subtree,
+ char LorR )
/* ------------------------------------------------------------------------ **
* Rebalance the tree following an insertion.
*
return( Root );
} /* Rebalance */
-static ubi_avlNodePtr Debalance( ubi_avlNodePtr Root,
- ubi_avlNodePtr subtree,
- signed char LorR )
+static ubi_btNodePtr Debalance( ubi_btNodePtr Root,
+ ubi_btNodePtr subtree,
+ char LorR )
/* ------------------------------------------------------------------------ **
* Rebalance the tree following a deletion.
*
return( Root );
} /* Debalance */
-
-/* -------------------------------------------------------------------------- **
- * The next two functions are used for general tree manipulation. They are
- * each slightly different from their ubi_BinTree counterparts.
- * -------------------------------------------------------------------------- **
- */
-
-static void ReplaceNode( ubi_avlNodePtr *parent,
- ubi_avlNodePtr oldnode,
- ubi_avlNodePtr newnode )
- /* ------------------------------------------------------------------------ **
- * Remove node oldnode from the tree, replacing it with node newnode.
- *
- * Input:
- * parent - A pointer to he parent pointer of the node to be
- * replaced. <parent> may point to the Link[] field of
- * a parent node, or it may indicate the root pointer at
- * the top of the tree.
- * oldnode - A pointer to the node that is to be replaced.
- * newnode - A pointer to the node that is to be installed in the
- * place of <*oldnode>.
- *
- * Notes: Don't forget to free oldnode.
- * The only difference between this function and the ubi_bt
- * version is that the node size is sizeof( ubi_avlNode ), not
- * sizeof( ubi_btNode ).
- * ------------------------------------------------------------------------ **
- */
- {
- register int i;
- register int avlNodeSize = sizeof( ubi_avlNode );
-
- for( i = 0; i < avlNodeSize; i++ )
- ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
- (*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_avlNodePtr Node1,
- ubi_avlNodePtr Node2 )
- /* ------------------------------------------------------------------------ **
- * This function swaps two nodes in the tree. Node1 will take the place of
- * Node2, and Node2 will fill in the space left vacant by Node 1.
- *
- * Input:
- * RootPtr - pointer to the tree header structure for this tree.
- * Node1 - \
- * > These are the two nodes which are to be swapped.
- * Node2 - /
- *
- * Notes:
- * This function does a three step swap, using a dummy node as a place
- * holder. This function is used by ubi_avlRemove().
- * The only difference between this function and its ubi_bt counterpart
- * is that the nodes are ubi_avlNodes, not ubi_btNodes.
- * ------------------------------------------------------------------------ **
- */
- {
- ubi_avlNodePtr *Parent;
- ubi_avlNode dummy;
- ubi_avlNodePtr dummy_p = &dummy;
-
- 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[ubi_trPARENT] )
- Parent = &((Node2->Link[ubi_trPARENT])->Link[Node2->gender]);
- else
- Parent = (ubi_avlNodePtr *)&(RootPtr->root);
- ReplaceNode( Parent, Node2, Node1 );
-
- 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 );
- } /* SwapNodes */
-
-
/* ========================================================================== **
* Public, exported (ie. not static-ly declared) functions...
* -------------------------------------------------------------------------- **
*/
-ubi_avlNodePtr ubi_avlInitNode( ubi_avlNodePtr NodePtr )
- /* ------------------------------------------------------------------------ **
- * Initialize a tree node.
- *
- * Input: NodePtr - pointer to a ubi_btNode structure to be
- * initialized.
- * Output: a pointer to the initialized ubi_avlNode structure (ie. the
- * same as the input pointer).
- * ------------------------------------------------------------------------ **
- */
- {
- (void)ubi_btInitNode( (ubi_btNodePtr)NodePtr );
- NodePtr->balance = ubi_trEQUAL;
- return( NodePtr );
- } /* ubi_avlInitNode */
-
-ubi_trBool ubi_avlInsert( ubi_btRootPtr RootPtr,
- ubi_avlNodePtr NewNode,
- ubi_btItemPtr ItemPtr,
- ubi_avlNodePtr *OldNode )
+ubi_trBool ubi_avlInsert( ubi_btRootPtr RootPtr,
+ ubi_btNodePtr NewNode,
+ ubi_btItemPtr ItemPtr,
+ ubi_btNodePtr *OldNode )
/* ------------------------------------------------------------------------ **
* This function uses a non-recursive algorithm to add a new element to
* the tree.
*
* Input: RootPtr - a pointer to the ubi_btRoot structure that indicates
* the root of the tree to which NewNode is to be added.
- * NewNode - a pointer to an ubi_avlNode structure that is NOT
+ * NewNode - a pointer to an ubi_btNode structure that is NOT
* part of any tree.
* ItemPtr - A pointer to the sort key that is stored within
* *NewNode. ItemPtr MUST point to information stored
* ------------------------------------------------------------------------ **
*/
{
- ubi_avlNodePtr OtherP;
+ ubi_btNodePtr OtherP;
- if( !(OldNode) ) OldNode = &OtherP;
+ if( !(OldNode) )
+ OldNode = &OtherP;
if( ubi_btInsert( RootPtr,
(ubi_btNodePtr)NewNode,
ItemPtr,
else
{
NewNode->balance = ubi_trEQUAL;
- RootPtr->root = (ubi_btNodePtr)Rebalance( (ubi_avlNodePtr)RootPtr->root,
+ RootPtr->root = (ubi_btNodePtr)Rebalance( (ubi_btNodePtr)RootPtr->root,
NewNode->Link[ubi_trPARENT],
NewNode->gender );
}
return( ubi_trFALSE ); /* Failure: could not replace an existing node. */
} /* ubi_avlInsert */
-ubi_avlNodePtr ubi_avlRemove( ubi_btRootPtr RootPtr,
- ubi_avlNodePtr DeadNode )
+ubi_btNodePtr ubi_avlRemove( ubi_btRootPtr RootPtr,
+ ubi_btNodePtr DeadNode )
/* ------------------------------------------------------------------------ **
* This function removes the indicated node from the tree, after which the
* tree is rebalanced.
*
* Note: The node MUST be in the tree indicated by RootPtr. If not,
* strange and evil things will happen to your trees.
+ *
* ------------------------------------------------------------------------ **
*/
{
- ubi_btNodePtr p,
- *parentp;
-
- /* if the node has both left and right subtrees, then we have to swap
- * it with another node.
- */
- 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[ubi_trPARENT] )
- parentp = (ubi_btNodePtr *)
- &((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( ubi_trEQUAL == DeadNode->balance )
- (*parentp) = NULL;
- else
- {
- p = (ubi_btNodePtr)(DeadNode->Link[(DeadNode->balance)]);
- 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[ubi_trPARENT],
- DeadNode->gender );
-
- (RootPtr->count)--;
+ /* Let the base binary tree module do the removal, then rebalance. */
+ if( ubi_btRemove( RootPtr, DeadNode ) )
+ RootPtr->root = Debalance( RootPtr->root,
+ DeadNode->Link[ubi_trPARENT],
+ DeadNode->gender );
return( DeadNode );
} /* ubi_avlRemove */
git.samba.org / samba.git / blobdiff