This is my library of lists and trees. My hope is to replace all of the
[samba.git] / 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 ============================== */