a864b160b5532f840dc476867386fced38a14d65
[tprouty/samba.git] / source / 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 header file contains the basic AVL structure and pointer typedefs
13  *  as well as the prototypes needed to access the functions in the AVL
14  *  module ubi_AVLtree.  The .c file implements the low-level height balancing
15  *  routines that manage the AVL tree, plus all of the basic primops for
16  *  adding, searching for, and deleting nodes.
17  *
18  * -------------------------------------------------------------------------- **
19  *
20  *  This library is free software; you can redistribute it and/or
21  *  modify it under the terms of the GNU Library General Public
22  *  License as published by the Free Software Foundation; either
23  *  version 2 of the License, or (at your option) any later version.
24  *
25  *  This library is distributed in the hope that it will be useful,
26  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
27  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
28  *  Library General Public License for more details.
29  *
30  *  You should have received a copy of the GNU Library General Public
31  *  License along with this library; if not, write to the Free
32  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
33  *
34  * -------------------------------------------------------------------------- **
35  *
36  * Log: ubi_AVLtree.c,v
37  * Revision 3.1  1997/12/18 06:26:51  crh
38  * Fixed some comment bugs.
39  *
40  * Revision 3.0  1997/12/08 05:38:55  crh
41  * This is a new major revision level.  The handling of the pointers in the
42  * ubi_trNode structure was redesigned.  The result is that there are fewer
43  * macros floating about, and fewer cases in which values have to be
44  * incremented or decremented.  See ubi_BinTree for more information.
45  *
46  * Revision 2; 1995/03/05 - 1997/12/07:
47  * An overhaul to the node delete process.  I had gotten it wrong in a
48  * couple of places, thought I'd fixed it, and then found that I'd missed
49  * something more.  Thanks to Andrew Leppard for the bug report!
50  *
51  * Revision 1;  93/10/15 - 95/03/05:
52  * Added the ubi_tr defines.  See ubi_BinTree.h for more info.
53  *
54  *  V0.0 - May, 1990   -  Written by Christopher R. Hertel (CRH).
55  *
56  *  ========================================================================= **
57  */
58
59 #include "ubi_AVLtree.h"            /* Header for THIS module.             */
60 #include <stdlib.h>                 /* Standard C definitions, etc.        */
61
62 /* ========================================================================== **
63  * Static data.
64  */
65
66 static char ModuleID[] = "ubi_AVLtree\n\
67 \tRevision: 3.1\n\
68 \tDate: 1997/12/18 06:26:51 GMT\n\
69 \tAuthor: crh\n";
70
71 /* ========================================================================== **
72  * The next set of functions are the AVL balancing routines.  There are left
73  * and right, single and double rotations.  The rotation routines handle the
74  * rotations and reconnect all tree pointers that might get confused by the
75  * rotations.  A pointer to the new subtree root node is returned.
76  *
77  * Note that L1 and R1 are identical, except that all the RIGHTs and LEFTs
78  * are reversed.  The same is true for L2 and R2.  I'm sure that there is
79  * a clever way to reduce the amount of code by combining these functions,
80  * but it might involve additional overhead, and it would probably be a pain
81  * to read, debug, etc.
82  * -------------------------------------------------------------------------- **
83  */
84
85 static ubi_avlNodePtr L1( ubi_avlNodePtr p )
86   /* ------------------------------------------------------------------------ **
87    * Single rotate left.
88    *
89    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
90    *  Output: A pointer to the new root of the same subtree (now that node
91    *          p has been moved).
92    * ------------------------------------------------------------------------ **
93    */
94   {
95   ubi_avlNodePtr tmp;
96
97   tmp                      = p->Link[ubi_trRIGHT];
98   p->Link[ubi_trRIGHT]     = tmp->Link[ubi_trLEFT];
99   tmp->Link[ubi_trLEFT]    = p;
100
101   tmp->Link[ubi_trPARENT]  = p->Link[ubi_trPARENT];
102   tmp->gender              = p->gender;
103   if(tmp->Link[ubi_trPARENT])
104     (tmp->Link[ubi_trPARENT])->Link[(tmp->gender)] = tmp;
105   p->Link[ubi_trPARENT]    = tmp;
106   p->gender                = ubi_trLEFT;
107   if( p->Link[ubi_trRIGHT] )
108     {
109     p->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = p;
110     (p->Link[ubi_trRIGHT])->gender           = ubi_trRIGHT;
111     }
112   p->balance -= tmp->balance;
113   (tmp->balance)--;
114   return( tmp );
115   } /* L1 */
116
117 static ubi_avlNodePtr R1( ubi_avlNodePtr p )
118   /* ------------------------------------------------------------------------ **
119    * Single rotate right.
120    *
121    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
122    *  Output: A pointer to the new root of the same subtree (now that node
123    *          p has been moved).
124    * ------------------------------------------------------------------------ **
125    */
126   {
127   ubi_avlNodePtr tmp;
128
129   tmp                      = p->Link[ubi_trLEFT];
130   p->Link[ubi_trLEFT]      = tmp->Link[ubi_trRIGHT];
131   tmp->Link[ubi_trRIGHT]   = p;
132
133   tmp->Link[ubi_trPARENT]  = p->Link[ubi_trPARENT];
134   tmp->gender              = p->gender;
135   if(tmp->Link[ubi_trPARENT])
136     (tmp->Link[ubi_trPARENT])->Link[(tmp->gender)] = tmp;
137   p->Link[ubi_trPARENT]    = tmp;
138   p->gender                = ubi_trRIGHT;
139   if(p->Link[ubi_trLEFT])
140     {
141     p->Link[ubi_trLEFT]->Link[ubi_trPARENT]  = p;
142     p->Link[ubi_trLEFT]->gender              = ubi_trLEFT;
143     }
144   p->balance -= tmp->balance;
145   (tmp->balance)++;
146   return( tmp );
147   } /* R1 */
148
149 static ubi_avlNodePtr L2( ubi_avlNodePtr tree )
150   /* ------------------------------------------------------------------------ **
151    * Double rotate left.
152    *
153    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
154    *  Output: A pointer to the new root of the same subtree (now that node
155    *          p has been moved).
156    * ------------------------------------------------------------------------ **
157    */
158   {
159   ubi_avlNodePtr tmp, newroot;
160
161   tmp                         = tree->Link[ubi_trRIGHT];
162   newroot                     = tmp->Link[ubi_trLEFT];
163   tmp->Link[ubi_trLEFT]       = newroot->Link[ubi_trRIGHT];
164   newroot->Link[ubi_trRIGHT]  = tmp;
165   tree->Link[ubi_trRIGHT]     = newroot->Link[ubi_trLEFT];
166   newroot->Link[ubi_trLEFT]   = tree;
167
168   newroot->Link[ubi_trPARENT] = tree->Link[ubi_trPARENT];
169   newroot->gender             = tree->gender;
170   tree->Link[ubi_trPARENT]    = newroot;
171   tree->gender                = ubi_trLEFT;
172   tmp->Link[ubi_trPARENT]     = newroot;
173   tmp->gender                 = ubi_trRIGHT;
174
175   if( tree->Link[ubi_trRIGHT] )
176     {
177     tree->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = tree;
178     tree->Link[ubi_trRIGHT]->gender             = ubi_trRIGHT;
179     }
180   if( tmp->Link[ubi_trLEFT] )
181     {
182     tmp->Link[ubi_trLEFT]->Link[ubi_trPARENT]   = tmp;
183     tmp->Link[ubi_trLEFT]->gender               = ubi_trLEFT;
184     }
185   if(newroot->Link[ubi_trPARENT])
186     newroot->Link[ubi_trPARENT]->Link[newroot->gender] = newroot;
187
188   switch( newroot->balance )
189     {
190     case ubi_trLEFT :
191       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trRIGHT; break;
192     case ubi_trEQUAL:
193       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trEQUAL; break;
194     case ubi_trRIGHT:
195       tree->balance = ubi_trLEFT;  tmp->balance = ubi_trEQUAL; break;
196     }
197   newroot->balance = ubi_trEQUAL;
198   return( newroot );
199   } /* L2 */
200
201 static ubi_avlNodePtr R2( ubi_avlNodePtr tree )
202   /* ------------------------------------------------------------------------ **
203    * Double rotate right.
204    *
205    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
206    *  Output: A pointer to the new root of the same subtree (now that node
207    *          p has been moved).
208    * ------------------------------------------------------------------------ **
209    */
210   {
211   ubi_avlNodePtr tmp, newroot;
212
213   tmp                         = tree->Link[ubi_trLEFT];
214   newroot                     = tmp->Link[ubi_trRIGHT];
215   tmp->Link[ubi_trRIGHT]      = newroot->Link[ubi_trLEFT];
216   newroot->Link[ubi_trLEFT]   = tmp;
217   tree->Link[ubi_trLEFT]      = newroot->Link[ubi_trRIGHT];
218   newroot->Link[ubi_trRIGHT]  = tree;
219
220   newroot->Link[ubi_trPARENT] = tree->Link[ubi_trPARENT];
221   newroot->gender             = tree->gender;
222   tree->Link[ubi_trPARENT]    = newroot;
223   tree->gender                = ubi_trRIGHT;
224   tmp->Link[ubi_trPARENT]     = newroot;
225   tmp->gender                 = ubi_trLEFT;
226
227   if( tree->Link[ubi_trLEFT] )
228     {
229     tree->Link[ubi_trLEFT]->Link[ubi_trPARENT]  = tree;
230     tree->Link[ubi_trLEFT]->gender              = ubi_trLEFT;
231     }
232   if( tmp->Link[ubi_trRIGHT] )
233     {
234     tmp->Link[ubi_trRIGHT]->Link[ubi_trPARENT]  = tmp;
235     tmp->Link[ubi_trRIGHT]->gender              = ubi_trRIGHT;
236     }
237   if(newroot->Link[ubi_trPARENT])
238     newroot->Link[ubi_trPARENT]->Link[newroot->gender] = newroot;
239
240   switch( newroot->balance )
241     {
242     case ubi_trLEFT  :
243       tree->balance = ubi_trRIGHT; tmp->balance = ubi_trEQUAL; break;
244     case ubi_trEQUAL :
245       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trEQUAL; break;
246     case ubi_trRIGHT :
247       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trLEFT;  break;
248     }
249   newroot->balance = ubi_trEQUAL;
250   return( newroot );
251   } /* R2 */
252
253
254 static ubi_avlNodePtr Adjust( ubi_avlNodePtr p, signed char LorR )
255   /* ------------------------------------------------------------------------ **
256    * Adjust the balance value at node *p.  If necessary, rotate the subtree
257    * rooted at p.
258    *
259    *  Input:  p    -  A pointer to the node to be adjusted.  One of the
260    *                  subtrees of this node has changed height, so the
261    *                  balance value at this node must be adjusted, possibly
262    *                  by rotating the tree at this node.
263    *          LorR -  Indicates the TALLER subtree.
264    *
265    *  Output: A pointer to the (possibly new) root node of the subtree.
266    *
267    *  Notes:  This function may be called after a node has been added *or*
268    *          deleted, so LorR indicates the TALLER subtree.
269    * ------------------------------------------------------------------------ **
270    */
271   {
272   if( p->balance != LorR )
273     p->balance += LorR;
274   else
275     {
276     signed char tallerbal;  /* Balance of root of the taller subtree of p. */
277
278     tallerbal = p->Link[LorR]->balance;
279     if( ( ubi_trEQUAL == tallerbal ) || ( p->balance == tallerbal ) )
280       p = ( (ubi_trLEFT==LorR) ? R1(p) : L1(p) );   /* single rotation */
281     else
282       p = ( (ubi_trLEFT==LorR) ? R2(p) : L2(p) );   /* double rotation */
283     }
284   return( p );
285   } /* Adjust */
286
287 static ubi_avlNodePtr Rebalance( ubi_avlNodePtr Root,
288                                  ubi_avlNodePtr subtree,
289                                  signed char    LorR )
290   /* ------------------------------------------------------------------------ **
291    * Rebalance the tree following an insertion.
292    *
293    *  Input:  Root    - A pointer to the root node of the whole tree.
294    *          subtree - A pointer to the node that has just gained a new
295    *                    child.
296    *          LorR    - Gender of the child that has just been gained.
297    *
298    *  Output: A pointer to the (possibly new) root of the AVL tree.
299    *          Rebalancing the tree moves nodes around a bit, so the node
300    *          that *was* the root, may not be the root when we're finished.
301    *
302    *  Notes:  Rebalance() must walk up the tree from where we are (which is
303    *          where the latest change occurred), rebalancing the subtrees
304    *          along the way.  The rebalancing operation can stop if the
305    *          change at the current subtree root won't affect the rest of
306    *          the tree.  In the case of an addition, if a subtree root's
307    *          balance becomes EQUAL, then we know that the height of that
308    *          subtree has not changed, so we can exit.
309    * ------------------------------------------------------------------------ **
310    */
311   {
312   while( subtree )
313     {
314     subtree = Adjust( subtree, LorR );
315     if( ubi_trPARENT == subtree->gender )
316       return( subtree );
317     if( ubi_trEQUAL == subtree->balance )
318       return( Root );
319     LorR = subtree->gender;
320     subtree = subtree->Link[ubi_trPARENT];
321     }
322   return( Root );
323   } /* Rebalance */
324
325 static ubi_avlNodePtr Debalance( ubi_avlNodePtr Root,
326                                  ubi_avlNodePtr subtree,
327                                  signed char    LorR )
328   /* ------------------------------------------------------------------------ **
329    * Rebalance the tree following a deletion.
330    *
331    *  Input:  Root    - A pointer to the root node of the whole tree.
332    *          subtree - A pointer to the node who's child has just "left the
333    *                    nest".
334    *          LorR    - Gender of the child that left.
335    *
336    *  Output: A pointer to the (possibly new) root of the AVL tree.
337    *          Rebalancing the tree moves nodes around a bit, so the node
338    *          that *was* the root, may not be the root when we're finished.
339    *
340    *  Notes:  Debalance() is subtly different from Rebalance() (above) in
341    *          two respects.
342    *            * When it calls Adjust(), it passes the *opposite* of LorR.
343    *              This is because LorR, as passed into Debalance() indicates
344    *              the shorter subtree.  As we move up the tree, LorR is
345    *              assigned the gender of the node that we are leaving (i.e.,
346    *              the subtree that we just rebalanced).
347    *            * We know that a subtree has not changed height if the
348    *              balance becomes LEFT or RIGHT.  This is the *opposite* of
349    *              what happens in Rebalance().
350    * ------------------------------------------------------------------------ **
351    */
352   {
353   while( subtree )
354     {
355     subtree = Adjust( subtree, ubi_trRevWay(LorR) );
356     if( ubi_trPARENT == subtree->gender )
357       return( subtree );
358     if( ubi_trEQUAL != subtree->balance )
359       return( Root );
360     LorR = subtree->gender;
361     subtree = subtree->Link[ubi_trPARENT];
362     }
363   return( Root );
364   } /* Debalance */
365
366
367 /* -------------------------------------------------------------------------- **
368  * The next two functions are used for general tree manipulation.  They are
369  * each slightly different from their ubi_BinTree counterparts.
370  * -------------------------------------------------------------------------- **
371  */
372
373 static void ReplaceNode( ubi_avlNodePtr *parent,
374                          ubi_avlNodePtr  oldnode,
375                          ubi_avlNodePtr  newnode )
376   /* ------------------------------------------------------------------------ **
377    * Remove node oldnode from the tree, replacing it with node newnode.
378    *
379    * Input:
380    *  parent   - A pointer to he parent pointer of the node to be
381    *             replaced.  <parent> may point to the Link[] field of
382    *             a parent node, or it may indicate the root pointer at
383    *             the top of the tree.
384    *  oldnode  - A pointer to the node that is to be replaced.
385    *  newnode  - A pointer to the node that is to be installed in the
386    *             place of <*oldnode>.
387    *
388    * Notes:    Don't forget to free oldnode.
389    *           The only difference between this function and the ubi_bt
390    *           version is that the node size is sizeof( ubi_avlNode ), not
391    *           sizeof( ubi_btNode ).
392    * ------------------------------------------------------------------------ **
393    */
394   {
395   register int i;
396   register int avlNodeSize = sizeof( ubi_avlNode );
397
398   for( i = 0; i < avlNodeSize; i++ )
399     ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
400   (*parent) = newnode;
401
402   if(oldnode->Link[ubi_trLEFT ] )
403     (oldnode->Link[ubi_trLEFT ])->Link[ubi_trPARENT] = newnode;
404   if(oldnode->Link[ubi_trRIGHT] )
405     (oldnode->Link[ubi_trRIGHT])->Link[ubi_trPARENT] = newnode;
406   } /* ReplaceNode */
407
408 static void SwapNodes( ubi_btRootPtr  RootPtr,
409                        ubi_avlNodePtr Node1,
410                        ubi_avlNodePtr Node2 )
411   /* ------------------------------------------------------------------------ **
412    * This function swaps two nodes in the tree.  Node1 will take the place of
413    * Node2, and Node2 will fill in the space left vacant by Node 1.
414    *
415    * Input:
416    *  RootPtr  - pointer to the tree header structure for this tree.
417    *  Node1    - \
418    *              > These are the two nodes which are to be swapped.
419    *  Node2    - /
420    *
421    * Notes:
422    *  This function does a three step swap, using a dummy node as a place
423    *  holder.  This function is used by ubi_avlRemove().
424    *  The only difference between this function and its ubi_bt counterpart
425    *  is that the nodes are ubi_avlNodes, not ubi_btNodes.
426    * ------------------------------------------------------------------------ **
427    */
428   {
429   ubi_avlNodePtr *Parent;
430   ubi_avlNode     dummy;
431   ubi_avlNodePtr  dummy_p = &dummy;
432
433   if( Node1->Link[ubi_trPARENT] )
434     Parent = &((Node1->Link[ubi_trPARENT])->Link[Node1->gender]);
435   else
436     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
437   ReplaceNode( Parent, Node1, dummy_p );
438
439   if( Node2->Link[ubi_trPARENT] )
440     Parent = &((Node2->Link[ubi_trPARENT])->Link[Node2->gender]);
441   else
442     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
443   ReplaceNode( Parent, Node2, Node1 );
444
445   if( dummy_p->Link[ubi_trPARENT] )
446     Parent = &((dummy_p->Link[ubi_trPARENT])->Link[dummy_p->gender]);
447   else
448     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
449   ReplaceNode( Parent, dummy_p, Node2 );
450   } /* SwapNodes */
451
452
453 /* ========================================================================== **
454  *         Public, exported (ie. not static-ly declared) functions...
455  * -------------------------------------------------------------------------- **
456  */
457
458 ubi_avlNodePtr ubi_avlInitNode( ubi_avlNodePtr NodePtr )
459   /* ------------------------------------------------------------------------ **
460    * Initialize a tree node.
461    *
462    *  Input:   NodePtr  - pointer to a ubi_btNode structure to be
463    *                      initialized.
464    *  Output:  a pointer to the initialized ubi_avlNode structure (ie. the
465    *           same as the input pointer).
466    * ------------------------------------------------------------------------ **
467    */
468   {
469   (void)ubi_btInitNode( (ubi_btNodePtr)NodePtr );
470   NodePtr->balance = ubi_trEQUAL;
471   return( NodePtr );
472   } /* ubi_avlInitNode */
473
474 ubi_trBool ubi_avlInsert( ubi_btRootPtr   RootPtr,
475                           ubi_avlNodePtr  NewNode,
476                           ubi_btItemPtr   ItemPtr,
477                           ubi_avlNodePtr *OldNode )
478   /* ------------------------------------------------------------------------ **
479    * This function uses a non-recursive algorithm to add a new element to
480    * the tree.
481    *
482    *  Input:   RootPtr  -  a pointer to the ubi_btRoot structure that indicates
483    *                       the root of the tree to which NewNode is to be added.
484    *           NewNode  -  a pointer to an ubi_avlNode structure that is NOT
485    *                       part of any tree.
486    *           ItemPtr  -  A pointer to the sort key that is stored within
487    *                       *NewNode.  ItemPtr MUST point to information stored
488    *                       in *NewNode or an EXACT DUPLICATE.  The key data
489    *                       indicated by ItemPtr is used to place the new node
490    *                       into the tree.
491    *           OldNode  -  a pointer to an ubi_btNodePtr.  When searching
492    *                       the tree, a duplicate node may be found.  If
493    *                       duplicates are allowed, then the new node will
494    *                       be simply placed into the tree.  If duplicates
495    *                       are not allowed, however, then one of two things
496    *                       may happen.
497    *                       1) if overwritting *is not* allowed, this
498    *                          function will return FALSE (indicating that
499    *                          the new node could not be inserted), and
500    *                          *OldNode will point to the duplicate that is
501    *                          still in the tree.
502    *                       2) if overwritting *is* allowed, then this
503    *                          function will swap **OldNode for *NewNode.
504    *                          In this case, *OldNode will point to the node
505    *                          that was removed (thus allowing you to free
506    *                          the node).
507    *                          **  If you are using overwrite mode, ALWAYS  **
508    *                          ** check the return value of this parameter! **
509    *                 Note: You may pass NULL in this parameter, the
510    *                       function knows how to cope.  If you do this,
511    *                       however, there will be no way to return a
512    *                       pointer to an old (ie. replaced) node (which is
513    *                       a problem if you are using overwrite mode).
514    *
515    *  Output:  a boolean value indicating success or failure.  The function
516    *           will return FALSE if the node could not be added to the tree.
517    *           Such failure will only occur if duplicates are not allowed,
518    *           nodes cannot be overwritten, AND a duplicate key was found
519    *           within the tree.
520    * ------------------------------------------------------------------------ **
521    */
522   {
523   ubi_avlNodePtr OtherP;
524
525   if( !(OldNode) ) OldNode = &OtherP;
526   if( ubi_btInsert( RootPtr,
527                     (ubi_btNodePtr)NewNode,
528                     ItemPtr,
529                     (ubi_btNodePtr *)OldNode ) )
530     {
531     if( (*OldNode) )
532       NewNode->balance = (*OldNode)->balance;
533     else
534       {
535       NewNode->balance = ubi_trEQUAL;
536       RootPtr->root = (ubi_btNodePtr)Rebalance( (ubi_avlNodePtr)RootPtr->root,
537                                                 NewNode->Link[ubi_trPARENT],
538                                                 NewNode->gender );
539       }
540     return( ubi_trTRUE );
541     }
542   return( ubi_trFALSE );      /* Failure: could not replace an existing node. */
543   } /* ubi_avlInsert */
544
545 ubi_avlNodePtr ubi_avlRemove( ubi_btRootPtr  RootPtr,
546                               ubi_avlNodePtr DeadNode )
547   /* ------------------------------------------------------------------------ **
548    * This function removes the indicated node from the tree, after which the
549    * tree is rebalanced.
550    *
551    *  Input:  RootPtr  -  A pointer to the header of the tree that contains
552    *                      the node to be removed.
553    *          DeadNode -  A pointer to the node that will be removed.
554    *
555    *  Output: This function returns a pointer to the node that was removed
556    *          from the tree (ie. the same as DeadNode).
557    *
558    *  Note:   The node MUST be in the tree indicated by RootPtr.  If not,
559    *          strange and evil things will happen to your trees.
560    * ------------------------------------------------------------------------ **
561    */
562   {
563   ubi_btNodePtr p,
564                *parentp;
565
566   /* if the node has both left and right subtrees, then we have to swap
567    * it with another node.
568    */
569   if( (DeadNode->Link[ubi_trLEFT]) && (DeadNode->Link[ubi_trRIGHT]) )
570     SwapNodes( RootPtr, DeadNode, ubi_trPrev( DeadNode ) );
571
572   /* The parent of the node to be deleted may be another node, or it may be
573    * the root of the tree.  Since we're not sure, it's best just to have
574    * a pointer to the parent pointer, whatever it is.
575    */
576   if( DeadNode->Link[ubi_trPARENT] )
577     parentp = (ubi_btNodePtr *)
578               &((DeadNode->Link[ubi_trPARENT])->Link[(DeadNode->gender)]);
579   else
580     parentp = &( RootPtr->root );
581
582   /* Now link the parent to the only grand-child.  Patch up the gender and
583    * such, and rebalance.
584    */
585   if( ubi_trEQUAL == DeadNode->balance )
586     (*parentp) = NULL;
587   else
588     {
589     p = (ubi_btNodePtr)(DeadNode->Link[(DeadNode->balance)]);
590     p->Link[ubi_trPARENT]  = (ubi_btNodePtr)DeadNode->Link[ubi_trPARENT];
591     p->gender              = DeadNode->gender;
592     (*parentp) = p;
593     }
594   RootPtr->root = (ubi_btNodePtr)Debalance( (ubi_avlNodePtr)RootPtr->root,
595                                             DeadNode->Link[ubi_trPARENT],
596                                             DeadNode->gender );
597
598   (RootPtr->count)--;
599   return( DeadNode );
600   } /* ubi_avlRemove */
601
602 int ubi_avlModuleID( int size, char *list[] )
603   /* ------------------------------------------------------------------------ **
604    * Returns a set of strings that identify the module.
605    *
606    *  Input:  size  - The number of elements in the array <list>.
607    *          list  - An array of pointers of type (char *).  This array
608    *                  should, initially, be empty.  This function will fill
609    *                  in the array with pointers to strings.
610    *  Output: The number of elements of <list> that were used.  If this value
611    *          is less than <size>, the values of the remaining elements are
612    *          not guaranteed.
613    *
614    *  Notes:  Please keep in mind that the pointers returned indicate strings
615    *          stored in static memory.  Don't free() them, don't write over
616    *          them, etc.  Just read them.
617    * ------------------------------------------------------------------------ **
618    */
619   {
620   if( size > 0 )
621     {
622     list[0] = ModuleID;
623     if( size > 1 )
624       return( 1 + ubi_btModuleID( --size, &(list[1]) ) );
625     return( 1 );
626     }
627   return( 0 );
628   } /* ubi_avlModuleID */
629
630 /* ============================== The End ============================== */