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