source3/ubi_AVLtree.c

   1 /* ========================================================================== **
   2  *                              ubi_AVLtree.c
   3  *
   4  *  Copyright (C) 1991-1997 by Christopher R. Hertel
   5  *
   6  *  Email: crh@ubiqx.mn.org
   7  * -------------------------------------------------------------------------- **
   8  *
   9  *  This module provides an implementation of AVL height balanced binary
  10  *  trees.  (Adelson-Velskii, Landis 1962)
  11  *
  12  *  This file implements the core of the height-balanced (AVL) tree management
  13  *  routines.  The header file, ubi_AVLtree.h, contains function prototypes
  14  *  for all "exported" functions.
  15  *
  16  * -------------------------------------------------------------------------- **
  17  *
  18  *  This library is free software; you can redistribute it and/or
  19  *  modify it under the terms of the GNU Library General Public
  20  *  License as published by the Free Software Foundation; either
  21  *  version 2 of the License, or (at your option) any later version.
  22  *
  23  *  This library is distributed in the hope that it will be useful,
  24  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  25  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  26  *  Library General Public License for more details.
  27  *
  28  *  You should have received a copy of the GNU Library General Public
  29  *  License along with this library; if not, write to the Free
  30  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  31  *
  32  * -------------------------------------------------------------------------- **
  33  *
  34  * $Log: ubi_AVLtree.c,v $
  35  * Revision 1.1  1997/10/09 04:09:51  crh
  36  * This is my library of lists and trees.  My hope is to replace all of the
  37  * hard coded linked lists that are currently used in Samba with calls to
  38  * these modules.  This should make the code simpler, smaller, and (I hope)
  39  * faster.  The tree code, in particular, should speed up processing where
  40  * large lists are involved.
  41  *
  42  * Chris -)-----
  43  *
  44  * Revision 2.4  1997/07/26 04:36:20  crh
  45  * Andrew Leppard, aka "Grazgur", discovered that I still had my brains tied
  46  * on backwards with respect to node deletion.  I did some more digging and
  47  * discovered that I was not changing the balance values correctly in the
  48  * single rotation functions.  Double rotation was working correctly because
  49  * the formula for changing the balance values is the same for insertion or
  50  * deletion.  Not so for single rotation.
  51  *
  52  * I have tested the fix by loading the tree with over 44 thousand names,
  53  * deleting 2,629 of them (all those in which the second character is 'u')
  54  * and then walking the tree recursively to verify that the balance factor of
  55  * each node is correct.  Passed.
  56  *
  57  * Thanks Andrew!
  58  *
  59  * Also:
  60  * + Changed ubi_TRUE and ubi_FALSE to ubi_trTRUE and ubi_trFALSE.
  61  * + Rewrote the ubi_tr<func> macros because they weren't doing what I'd
  62  *   hoped they would do (see the bottom of the header file).  They work now.
  63  *
  64  * Revision 2.3  1997/06/03 04:41:35  crh
  65  * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing
  66  * problems.
  67  *
  68  * Revision 2.2  1995/10/03 22:16:01  CRH
  69  * Ubisized!
  70  *
  71  * Revision 2.1  95/03/09  23:45:59  CRH
  72  * Added the ModuleID static string and function.  These modules are now
  73  * self-identifying.
  74  *
  75  * Revision 2.0  95/03/05  14:10:51  CRH
  76  * This revision of ubi_AVLtree coincides with revision 2.0 of ubi_BinTree,
  77  * and so includes all of the changes to that module.  In addition, a bug in
  78  * the node deletion process has been fixed.
  79  *
  80  * After rewriting the Locate() function in ubi_BinTree, I decided that it was
  81  * time to overhaul this module.  In the process, I discovered a bug related
  82  * to node deletion.  To fix the bug, I wrote function Debalance().  A quick
  83  * glance will show that it is very similar to the Rebalance() function.  In
  84  * previous versions of this module, I tried to include the functionality of
  85  * Debalance() within Rebalance(), with poor results.
  86  *
  87  * Revision 1.0  93/10/15  22:58:56  CRH
  88  * With this revision, I have added a set of #define's that provide a single,
  89  * standard API to all existing tree modules.  Until now, each of the three
  90  * existing modules had a different function and typedef prefix, as follows:
  91  *
  92  *       Module        Prefix
  93  *     ubi_BinTree     ubi_bt
  94  *     ubi_AVLtree     ubi_avl
  95  *     ubi_SplayTree   ubi_spt
  96  *
  97  * To further complicate matters, only those portions of the base module
  98  * (ubi_BinTree) that were superceeded in the new module had the new names.
  99  * For example, if you were using ubi_AVLtree, the AVL node structure was
 100  * named "ubi_avlNode", but the root structure was still "ubi_btRoot".  Using
 101  * SplayTree, the locate function was called "ubi_sptLocate", but the next
 102  * and previous functions remained "ubi_btNext" and "ubi_btPrev".
 103  *
 104  * This was not too terrible if you were familiar with the modules and knew
 105  * exactly which tree model you wanted to use.  If you wanted to be able to
 106  * change modules (for speed comparisons, etc), things could get messy very
 107  * quickly.
 108  *
 109  * So, I have added a set of defined names that get redefined in any of the
 110  * descendant modules.  To use this standardized interface in your code,
 111  * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with
 112  * "ubi_tr".  The "ubi_tr" names will resolve to the correct function or
 113  * datatype names for the module that you are using.  Just remember to
 114  * include the header for that module in your program file.  Because these
 115  * names are handled by the preprocessor, there is no added run-time
 116  * overhead.
 117  *
 118  * Note that the original names do still exist, and can be used if you wish
 119  * to write code directly to a specific module.  This should probably only be
 120  * done if you are planning to implement a new descendant type, such as
 121  * red/black trees.  CRH
 122  *
 123  *  V0.0 - May, 1990   -  Written by Christopher R. Hertel (CRH).
 124  *
 125  *  ========================================================================= **
 126  */
 127
 128 #include "ubi_AVLtree.h"            /* Header for THIS module.             */
 129 #include <stdlib.h>                 /* Standard C definitions, etc.        */
 130
 131 /* ========================================================================== **
 132  * Static data.
 133  */
 134
 135 static char ModuleID[] = "ubi_AVLtree\n\
 136 \t$Revision: 1.1 $\n\
 137 \t$Date: 1997/10/09 04:09:51 $\n\
 138 \t$Author: crh $\n";
 139
 140 /* ========================================================================== **
 141  * The next set of functions are the AVL balancing routines.  There are left
 142  * and right, single and double rotations.  The rotation routines handle the
 143  * rotations and reconnect all tree pointers that might get confused by the
 144  * rotations.  A pointer to the new subtree root node is returned.
 145  *
 146  * Note that L1 and R1 are identical, except that all the RIGHTs and LEFTs
 147  * are reversed.  The same is true for L2 and R2.  I'm sure that there is
 148  * a clever way to reduce the amount of code by combining these functions,
 149  * but it might involve additional overhead, and it would probably be a pain
 150  * to read, debug, etc.
 151  * -------------------------------------------------------------------------- **
 152  */
 153
 154 static ubi_avlNodePtr L1( ubi_avlNodePtr p )
 155   /* ------------------------------------------------------------------------ **
 156    * Single rotate left.
 157    *
 158    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
 159    *  Output: A pointer to the new root of the same subtree (now that node
 160    *          p has been moved).
 161    * ------------------------------------------------------------------------ **
 162    */
 163   {
 164   ubi_avlNodePtr tmp;
 165
 166   tmp                = p->Link[RIGHT];
 167   p->Link[RIGHT]     = tmp->Link[LEFT];
 168   tmp->Link[LEFT]    = p;
 169
 170   tmp->Link[PARENT]  = p->Link[PARENT];
 171   tmp->gender        = p->gender;
 172   if(tmp->Link[PARENT])
 173     (tmp->Link[PARENT])->Link[(tmp->gender)] = tmp;
 174   p->Link[PARENT]    = tmp;
 175   p->gender          = LEFT;
 176   if( p->Link[RIGHT] )
 177     {
 178     p->Link[RIGHT]->Link[PARENT] = p;
 179     (p->Link[RIGHT])->gender     = RIGHT;
 180     }
 181   p->balance -= Normalize( tmp->balance );
 182   (tmp->balance)--;
 183   return( tmp );
 184   } /* L1 */
 185
 186 static ubi_avlNodePtr R1( ubi_avlNodePtr p )
 187   /* ------------------------------------------------------------------------ **
 188    * Single rotate right.
 189    *
 190    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
 191    *  Output: A pointer to the new root of the same subtree (now that node
 192    *          p has been moved).
 193    * ------------------------------------------------------------------------ **
 194    */
 195   {
 196   ubi_avlNodePtr tmp;
 197
 198   tmp                = p->Link[LEFT];
 199   p->Link[LEFT]      = tmp->Link[RIGHT];
 200   tmp->Link[RIGHT]   = p;
 201
 202   tmp->Link[PARENT]  = p->Link[PARENT];
 203   tmp->gender        = p->gender;
 204   if(tmp->Link[PARENT])
 205     (tmp->Link[PARENT])->Link[(tmp->gender)] = tmp;
 206   p->Link[PARENT]    = tmp;
 207   p->gender          = RIGHT;
 208   if(p->Link[LEFT])
 209     {
 210     p->Link[LEFT]->Link[PARENT]  = p;
 211     p->Link[LEFT]->gender        = LEFT;
 212     }
 213   p->balance -= Normalize( tmp->balance );
 214   (tmp->balance)++;
 215   return( tmp );
 216   } /* R1 */
 217
 218 static ubi_avlNodePtr L2( ubi_avlNodePtr tree )
 219   /* ------------------------------------------------------------------------ **
 220    * Double rotate left.
 221    *
 222    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
 223    *  Output: A pointer to the new root of the same subtree (now that node
 224    *          p has been moved).
 225    * ------------------------------------------------------------------------ **
 226    */
 227   {
 228   ubi_avlNodePtr tmp, newroot;
 229
 230   tmp                   = tree->Link[RIGHT];
 231   newroot               = tmp->Link[LEFT];
 232   tmp->Link[LEFT]       = newroot->Link[RIGHT];
 233   newroot->Link[RIGHT]  = tmp;
 234   tree->Link[RIGHT]     = newroot->Link[LEFT];
 235   newroot->Link[LEFT]   = tree;
 236
 237   newroot->Link[PARENT] = tree->Link[PARENT];
 238   newroot->gender       = tree->gender;
 239   tree->Link[PARENT]    = newroot;
 240   tree->gender          = LEFT;
 241   tmp->Link[PARENT]     = newroot;
 242   tmp->gender           = RIGHT;
 243
 244   if( tree->Link[RIGHT] )
 245     {
 246     tree->Link[RIGHT]->Link[PARENT] = tree;
 247     tree->Link[RIGHT]->gender       = RIGHT;
 248     }
 249   if( tmp->Link[LEFT] )
 250     {
 251     tmp->Link[LEFT]->Link[PARENT]   = tmp;
 252     tmp->Link[LEFT]->gender         = LEFT;
 253     }
 254   if(newroot->Link[PARENT])
 255     newroot->Link[PARENT]->Link[newroot->gender] = newroot;
 256
 257   switch( newroot->balance )
 258     {
 259     case LEFT :
 260       tree->balance = EQUAL; tmp->balance = RIGHT; break;
 261     case EQUAL:
 262       tree->balance = EQUAL; tmp->balance = EQUAL; break;
 263     case RIGHT:
 264       tree->balance = LEFT;  tmp->balance = EQUAL; break;
 265     }
 266   newroot->balance = EQUAL;
 267   return( newroot );
 268   } /* L2 */
 269
 270 static ubi_avlNodePtr R2( ubi_avlNodePtr tree )
 271   /* ------------------------------------------------------------------------ **
 272    * Double rotate right.
 273    *
 274    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
 275    *  Output: A pointer to the new root of the same subtree (now that node
 276    *          p has been moved).
 277    * ------------------------------------------------------------------------ **
 278    */
 279   {
 280   ubi_avlNodePtr tmp, newroot;
 281
 282   tmp                   = tree->Link[LEFT];
 283   newroot               = tmp->Link[RIGHT];
 284   tmp->Link[RIGHT]      = newroot->Link[LEFT];
 285   newroot->Link[LEFT]   = tmp;
 286   tree->Link[LEFT]      = newroot->Link[RIGHT];
 287   newroot->Link[RIGHT]  = tree;
 288
 289   newroot->Link[PARENT] = tree->Link[PARENT];
 290   newroot->gender       = tree->gender;
 291   tree->Link[PARENT]    = newroot;
 292   tree->gender          = RIGHT;
 293   tmp->Link[PARENT]     = newroot;
 294   tmp->gender           = LEFT;
 295
 296   if( tree->Link[LEFT] )
 297     {
 298     tree->Link[LEFT]->Link[PARENT]  = tree;
 299     tree->Link[LEFT]->gender        = LEFT;
 300     }
 301   if( tmp->Link[RIGHT] )
 302     {
 303     tmp->Link[RIGHT]->Link[PARENT]  = tmp;
 304     tmp->Link[RIGHT]->gender        = RIGHT;
 305     }
 306   if(newroot->Link[PARENT])
 307     newroot->Link[PARENT]->Link[newroot->gender] = newroot;
 308
 309   switch( newroot->balance )
 310     {
 311     case LEFT  :
 312       tree->balance = RIGHT; tmp->balance = EQUAL; break;
 313     case EQUAL :
 314       tree->balance = EQUAL; tmp->balance = EQUAL; break;
 315     case RIGHT :
 316       tree->balance = EQUAL; tmp->balance = LEFT;  break;
 317     }
 318   newroot->balance = EQUAL;
 319   return( newroot );
 320   } /* R2 */
 321
 322
 323 static ubi_avlNodePtr Adjust( ubi_avlNodePtr p, char LorR )
 324   /* ------------------------------------------------------------------------ **
 325    * Adjust the balance value at node *p.  If necessary, rotate the subtree
 326    * rooted at p.
 327    *
 328    *  Input:  p    -  A pointer to the node to be adjusted.  One of the
 329    *                  subtrees of this node has changed height, so the
 330    *                  balance value at this node must be adjusted, possibly
 331    *                  by rotating the tree at this node.
 332    *          LorR -  Indicates the TALLER subtree.
 333    *
 334    *  Output: A pointer to the (possibly new) root node of the subtree.
 335    *
 336    *  Notes:  This function may be called after a node has been added *or*
 337    *          deleted, so LorR indicates the TALLER subtree.
 338    * ------------------------------------------------------------------------ **
 339    */
 340   {
 341   if( p->balance != LorR )
 342     p->balance += Normalize(LorR);
 343   else
 344     {
 345     char tallerbal;  /* Balance value of the root of the taller subtree of p. */
 346
 347     tallerbal = p->Link[LorR]->balance;
 348     if( ( EQUAL == tallerbal ) || ( p->balance == tallerbal ) )
 349       p = ( (LEFT==LorR) ? R1(p) : L1(p) );   /* single rotation */
 350     else
 351       p = ( (LEFT==LorR) ? R2(p) : L2(p) );   /* double rotation */
 352     }
 353   return( p );
 354   } /* Adjust */
 355
 356 static ubi_avlNodePtr Rebalance( ubi_avlNodePtr Root,
 357                                  ubi_avlNodePtr subtree,
 358                                  char           LorR )
 359   /* ------------------------------------------------------------------------ **
 360    * Rebalance the tree following an insertion.
 361    *
 362    *  Input:  Root    - A pointer to the root node of the whole tree.
 363    *          subtree - A pointer to the node that has just gained a new
 364    *                    child.
 365    *          LorR    - Gender of the child that has just been gained.
 366    *
 367    *  Output: A pointer to the (possibly new) root of the AVL tree.
 368    *          Rebalancing the tree moves nodes around a bit, so the node
 369    *          that *was* the root, may not be the root when we're finished.
 370    *
 371    *  Notes:  Rebalance() must walk up the tree from where we are (which is
 372    *          where the latest change occurred), rebalancing the subtrees
 373    *          along the way.  The rebalancing operation can stop if the
 374    *          change at the current subtree root won't affect the rest of
 375    *          the tree.  In the case of an addition, if a subtree root's
 376    *          balance becomes EQUAL, then we know that the height of that
 377    *          subtree has not changed, so we can exit.
 378    * ------------------------------------------------------------------------ **
 379    */
 380   {
 381   while( subtree )
 382     {
 383     subtree = Adjust( subtree, LorR );
 384     if( PARENT == subtree->gender )
 385       return( subtree );
 386     if( EQUAL == subtree->balance )
 387       return( Root );
 388     LorR = subtree->gender;
 389     subtree = subtree->Link[PARENT];
 390     }
 391   return( Root );
 392   } /* Rebalance */
 393
 394 static ubi_avlNodePtr Debalance( ubi_avlNodePtr Root,
 395                                  ubi_avlNodePtr subtree,
 396                                  char           LorR )
 397   /* ------------------------------------------------------------------------ **
 398    * Rebalance the tree following a deletion.
 399    *
 400    *  Input:  Root    - A pointer to the root node of the whole tree.
 401    *          subtree - A pointer to the node who's child has just "left the
 402    *                    nest".
 403    *          LorR    - Gender of the child that left.
 404    *
 405    *  Output: A pointer to the (possibly new) root of the AVL tree.
 406    *          Rebalancing the tree moves nodes around a bit, so the node
 407    *          that *was* the root, may not be the root when we're finished.
 408    *
 409    *  Notes:  Debalance() is subtly different from Rebalance() (above) in
 410    *          two respects.
 411    *            * When it calls Adjust(), it passes the *opposite* of LorR.
 412    *              This is because LorR, as passed into Debalance() indicates
 413    *              the shorter subtree.  As we move up the tree, LorR is
 414    *              assigned the gender of the node that we are leaving (i.e.,
 415    *              the subtree that we just rebalanced).
 416    *            * We know that a subtree has not changed height if the
 417    *              balance becomes LEFT or RIGHT.  This is the *opposite* of
 418    *              what happens in Rebalance().
 419    * ------------------------------------------------------------------------ **
 420    */
 421   {
 422   while( subtree )
 423     {
 424     subtree = Adjust( subtree, RevWay(LorR) );
 425     if( PARENT == subtree->gender )
 426       return( subtree );
 427     if( EQUAL != subtree->balance )
 428       return( Root );
 429     LorR = subtree->gender;
 430     subtree = subtree->Link[PARENT];
 431     }
 432   return( Root );
 433   } /* Debalance */
 434
 435
 436 /* -------------------------------------------------------------------------- **
 437  * The next two functions are used for general tree manipulation.  They are
 438  * each slightly different from their ubi_BinTree counterparts.
 439  * -------------------------------------------------------------------------- **
 440  */
 441
 442 static void ReplaceNode( ubi_avlNodePtr *parent,
 443                          ubi_avlNodePtr  oldnode,
 444                          ubi_avlNodePtr  newnode )
 445   /* ------------------------------------------------------------------------ **
 446    * Remove node oldnode from the tree, replacing it with node newnode.
 447    *
 448    * Input:
 449    *  parent   - A pointer to he parent pointer of the node to be
 450    *             replaced.  <parent> may point to the Link[] field of
 451    *             a parent node, or it may indicate the root pointer at
 452    *             the top of the tree.
 453    *  oldnode  - A pointer to the node that is to be replaced.
 454    *  newnode  - A pointer to the node that is to be installed in the
 455    *             place of <*oldnode>.
 456    *
 457    * Notes:    Don't forget to free oldnode.
 458    *           The only difference between this function and the ubi_bt
 459    *           version is that the node size is sizeof( ubi_avlNode ), not
 460    *           sizeof( ubi_btNode ).
 461    * ------------------------------------------------------------------------ **
 462    */
 463   {
 464   register int i;
 465   register int avlNodeSize = sizeof( ubi_avlNode );
 466
 467   for( i = 0; i < avlNodeSize; i++ )
 468     ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
 469   (*parent) = newnode;
 470
 471   if(oldnode->Link[LEFT ] )
 472     (oldnode->Link[LEFT ])->Link[PARENT] = newnode;
 473   if(oldnode->Link[RIGHT] )
 474     (oldnode->Link[RIGHT])->Link[PARENT] = newnode;
 475   } /* ReplaceNode */
 476
 477 static void SwapNodes( ubi_btRootPtr  RootPtr,
 478                        ubi_avlNodePtr Node1,
 479                        ubi_avlNodePtr Node2 )
 480   /* ------------------------------------------------------------------------ **
 481    * This function swaps two nodes in the tree.  Node1 will take the place of
 482    * Node2, and Node2 will fill in the space left vacant by Node 1.
 483    *
 484    * Input:
 485    *  RootPtr  - pointer to the tree header structure for this tree.
 486    *  Node1    - \
 487    *              > These are the two nodes which are to be swapped.
 488    *  Node2    - /
 489    *
 490    * Notes:
 491    *  This function does a three step swap, using a dummy node as a place
 492    *  holder.  This function is used by ubi_avlRemove().
 493    *  The only difference between this function and its ubi_bt counterpart
 494    *  is that the nodes are ubi_avlNodes, not ubi_btNodes.
 495    * ------------------------------------------------------------------------ **
 496    */
 497   {
 498   ubi_avlNodePtr *Parent;
 499   ubi_avlNode     dummy;
 500   ubi_avlNodePtr  dummy_p = &dummy;
 501
 502   if( Node1->Link[PARENT] )
 503     Parent = &((Node1->Link[PARENT])->Link[Node1->gender]);
 504   else
 505     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
 506   ReplaceNode( Parent, Node1, dummy_p );
 507
 508   if( Node2->Link[PARENT] )
 509     Parent = &((Node2->Link[PARENT])->Link[Node2->gender]);
 510   else
 511     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
 512   ReplaceNode( Parent, Node2, Node1 );
 513
 514   if( dummy_p->Link[PARENT] )
 515     Parent = &((dummy_p->Link[PARENT])->Link[dummy_p->gender]);
 516   else
 517     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
 518   ReplaceNode( Parent, dummy_p, Node2 );
 519   } /* SwapNodes */
 520
 521
 522 /* ========================================================================== **
 523  *         Public, exported (ie. not static-ly declared) functions...
 524  * -------------------------------------------------------------------------- **
 525  */
 526
 527 ubi_avlNodePtr ubi_avlInitNode( ubi_avlNodePtr NodePtr )
 528   /* ------------------------------------------------------------------------ **
 529    * Initialize a tree node.
 530    *
 531    *  Input:   NodePtr  - pointer to a ubi_btNode structure to be
 532    *                      initialized.
 533    *  Output:  a pointer to the initialized ubi_avlNode structure (ie. the
 534    *           same as the input pointer).
 535    * ------------------------------------------------------------------------ **
 536    */
 537   {
 538   (void)ubi_btInitNode( (ubi_btNodePtr)NodePtr );
 539   NodePtr->balance = EQUAL;
 540   return( NodePtr );
 541   } /* ubi_avlInitNode */
 542
 543 ubi_trBool ubi_avlInsert( ubi_btRootPtr   RootPtr,
 544                           ubi_avlNodePtr  NewNode,
 545                           ubi_btItemPtr   ItemPtr,
 546                           ubi_avlNodePtr *OldNode )
 547   /* ------------------------------------------------------------------------ **
 548    * This function uses a non-recursive algorithm to add a new element to
 549    * the tree.
 550    *
 551    *  Input:   RootPtr  -  a pointer to the ubi_btRoot structure that indicates
 552    *                       the root of the tree to which NewNode is to be added.
 553    *           NewNode  -  a pointer to an ubi_avlNode structure that is NOT
 554    *                       part of any tree.
 555    *           ItemPtr  -  A pointer to the sort key that is stored within
 556    *                       *NewNode.  ItemPtr MUST point to information stored
 557    *                       in *NewNode or an EXACT DUPLICATE.  The key data
 558    *                       indicated by ItemPtr is used to place the new node
 559    *                       into the tree.
 560    *           OldNode  -  a pointer to an ubi_btNodePtr.  When searching
 561    *                       the tree, a duplicate node may be found.  If
 562    *                       duplicates are allowed, then the new node will
 563    *                       be simply placed into the tree.  If duplicates
 564    *                       are not allowed, however, then one of two things
 565    *                       may happen.
 566    *                       1) if overwritting *is not* allowed, this
 567    *                          function will return FALSE (indicating that
 568    *                          the new node could not be inserted), and
 569    *                          *OldNode will point to the duplicate that is
 570    *                          still in the tree.
 571    *                       2) if overwritting *is* allowed, then this
 572    *                          function will swap **OldNode for *NewNode.
 573    *                          In this case, *OldNode will point to the node
 574    *                          that was removed (thus allowing you to free
 575    *                          the node).
 576    *                          **  If you are using overwrite mode, ALWAYS  **
 577    *                          ** check the return value of this parameter! **
 578    *                 Note: You may pass NULL in this parameter, the
 579    *                       function knows how to cope.  If you do this,
 580    *                       however, there will be no way to return a
 581    *                       pointer to an old (ie. replaced) node (which is
 582    *                       a problem if you are using overwrite mode).
 583    *
 584    *  Output:  a boolean value indicating success or failure.  The function
 585    *           will return FALSE if the node could not be added to the tree.
 586    *           Such failure will only occur if duplicates are not allowed,
 587    *           nodes cannot be overwritten, AND a duplicate key was found
 588    *           within the tree.
 589    * ------------------------------------------------------------------------ **
 590    */
 591   {
 592   ubi_avlNodePtr OtherP;
 593
 594   if( !(OldNode) ) OldNode = &OtherP;
 595   if( ubi_btInsert( RootPtr,
 596                     (ubi_btNodePtr)NewNode,
 597                     ItemPtr,
 598                     (ubi_btNodePtr *)OldNode ) )
 599     {
 600     if( (*OldNode) )
 601       NewNode->balance = (*OldNode)->balance;
 602     else
 603       {
 604       NewNode->balance = EQUAL;
 605       RootPtr->root = (ubi_btNodePtr)Rebalance( (ubi_avlNodePtr)RootPtr->root,
 606                                                 NewNode->Link[PARENT],
 607                                                 NewNode->gender );
 608       }
 609     return( ubi_trTRUE );
 610     }
 611   return( ubi_trFALSE );      /* Failure: could not replace an existing node. */
 612   } /* ubi_avlInsert */
 613
 614 ubi_avlNodePtr ubi_avlRemove( ubi_btRootPtr  RootPtr,
 615                               ubi_avlNodePtr DeadNode )
 616   /* ------------------------------------------------------------------------ **
 617    * This function removes the indicated node from the tree, after which the
 618    * tree is rebalanced.
 619    *
 620    *  Input:  RootPtr  -  A pointer to the header of the tree that contains
 621    *                      the node to be removed.
 622    *          DeadNode -  A pointer to the node that will be removed.
 623    *
 624    *  Output: This function returns a pointer to the node that was removed
 625    *          from the tree (ie. the same as DeadNode).
 626    *
 627    *  Note:   The node MUST be in the tree indicated by RootPtr.  If not,
 628    *          strange and evil things will happen to your trees.
 629    * ------------------------------------------------------------------------ **
 630    */
 631   {
 632   ubi_btNodePtr p,
 633                *parentp;
 634
 635   /* if the node has both left and right subtrees, then we have to swap
 636    * it with another node.
 637    */
 638   if( (DeadNode->Link[LEFT]) && (DeadNode->Link[RIGHT]) )
 639     SwapNodes( RootPtr, DeadNode, ubi_trPrev( DeadNode ) );
 640
 641   /* The parent of the node to be deleted may be another node, or it may be
 642    * the root of the tree.  Since we're not sure, it's best just to have
 643    * a pointer to the parent pointer, whatever it is.
 644    */
 645   if( DeadNode->Link[PARENT] )
 646     parentp = (ubi_btNodePtr *)
 647               &((DeadNode->Link[PARENT])->Link[(DeadNode->gender)]);
 648   else
 649     parentp = &( RootPtr->root );
 650
 651   /* Now link the parent to the only grand-child.  Patch up the gender and
 652    * such, and rebalance.
 653    */
 654   if( EQUAL == DeadNode->balance )
 655     (*parentp) = NULL;
 656   else
 657     {
 658     p = (ubi_btNodePtr)(DeadNode->Link[(DeadNode->balance)]);
 659     p->Link[PARENT]  = (ubi_btNodePtr)DeadNode->Link[PARENT];
 660     p->gender        = DeadNode->gender;
 661     (*parentp) = p;
 662     }
 663   RootPtr->root = (ubi_btNodePtr)Debalance( (ubi_avlNodePtr)RootPtr->root,
 664                                             DeadNode->Link[PARENT],
 665                                             DeadNode->gender );
 666
 667   (RootPtr->count)--;
 668   return( DeadNode );
 669   } /* ubi_avlRemove */
 670
 671 int ubi_avlModuleID( int size, char *list[] )
 672   /* ------------------------------------------------------------------------ **
 673    * Returns a set of strings that identify the module.
 674    *
 675    *  Input:  size  - The number of elements in the array <list>.
 676    *          list  - An array of pointers of type (char *).  This array
 677    *                  should, initially, be empty.  This function will fill
 678    *                  in the array with pointers to strings.
 679    *  Output: The number of elements of <list> that were used.  If this value
 680    *          is less than <size>, the values of the remaining elements are
 681    *          not guaranteed.
 682    *
 683    *  Notes:  Please keep in mind that the pointers returned indicate strings
 684    *          stored in static memory.  Don't free() them, don't write over
 685    *          them, etc.  Just read them.
 686    * ------------------------------------------------------------------------ **
 687    */
 688   {
 689   if( size > 0 )
 690     {
 691     list[0] = ModuleID;
 692     if( size > 1 )
 693       return( 1 + ubi_btModuleID( --size, &(list[1]) ) );
 694     return( 1 );
 695     }
 696   return( 0 );
 697   } /* ubi_avlModuleID */
 698
 699 /* ============================== The End ============================== */