Backed out changes that attempted to address a pointer array using -1,0,1.
[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 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 2.5  1997/12/23 04:00:42  crh
36  * In this version, all constants & macros defined in the header file have
37  * the ubi_tr prefix.  Also cleaned up anything that gcc complained about
38  * when run with '-pedantic -fsyntax-only -Wall'.
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 \tRevision: 2.5\n\
133 \tDate: 1997/12/23 04:00:42\n\
134 \tAuthor: 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[ubi_trRIGHT];
163   p->Link[ubi_trRIGHT]     = tmp->Link[ubi_trLEFT];
164   tmp->Link[ubi_trLEFT]    = p;
165
166   tmp->Link[ubi_trPARENT]  = p->Link[ubi_trPARENT];
167   tmp->gender              = p->gender;
168   if(tmp->Link[ubi_trPARENT])
169     (tmp->Link[ubi_trPARENT])->Link[(int)(tmp->gender)] = tmp;
170   p->Link[ubi_trPARENT]    = tmp;
171   p->gender                = ubi_trLEFT;
172   if( p->Link[ubi_trRIGHT] )
173     {
174     p->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = p;
175     (p->Link[ubi_trRIGHT])->gender           = ubi_trRIGHT;
176     }
177   p->balance -= ubi_trNormalize( 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[ubi_trLEFT];
195   p->Link[ubi_trLEFT]      = tmp->Link[ubi_trRIGHT];
196   tmp->Link[ubi_trRIGHT]   = p;
197
198   tmp->Link[ubi_trPARENT]  = p->Link[ubi_trPARENT];
199   tmp->gender              = p->gender;
200   if(tmp->Link[ubi_trPARENT])
201     (tmp->Link[ubi_trPARENT])->Link[(int)(tmp->gender)] = tmp;
202   p->Link[ubi_trPARENT]    = tmp;
203   p->gender                = ubi_trRIGHT;
204   if(p->Link[ubi_trLEFT])
205     {
206     p->Link[ubi_trLEFT]->Link[ubi_trPARENT]  = p;
207     p->Link[ubi_trLEFT]->gender              = ubi_trLEFT;
208     }
209   p->balance -= ubi_trNormalize( 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[ubi_trRIGHT];
227   newroot                     = tmp->Link[ubi_trLEFT];
228   tmp->Link[ubi_trLEFT]       = newroot->Link[ubi_trRIGHT];
229   newroot->Link[ubi_trRIGHT]  = tmp;
230   tree->Link[ubi_trRIGHT]     = newroot->Link[ubi_trLEFT];
231   newroot->Link[ubi_trLEFT]   = tree;
232
233   newroot->Link[ubi_trPARENT] = tree->Link[ubi_trPARENT];
234   newroot->gender             = tree->gender;
235   tree->Link[ubi_trPARENT]    = newroot;
236   tree->gender                = ubi_trLEFT;
237   tmp->Link[ubi_trPARENT]     = newroot;
238   tmp->gender                 = ubi_trRIGHT;
239
240   if( tree->Link[ubi_trRIGHT] )
241     {
242     tree->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = tree;
243     tree->Link[ubi_trRIGHT]->gender             = ubi_trRIGHT;
244     }
245   if( tmp->Link[ubi_trLEFT] )
246     {
247     tmp->Link[ubi_trLEFT]->Link[ubi_trPARENT]   = tmp;
248     tmp->Link[ubi_trLEFT]->gender               = ubi_trLEFT;
249     }
250   if(newroot->Link[ubi_trPARENT])
251     newroot->Link[ubi_trPARENT]->Link[(int)(newroot->gender)] = newroot;
252
253   switch( newroot->balance )
254     {
255     case ubi_trLEFT :
256       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trRIGHT; break;
257     case ubi_trEQUAL:
258       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trEQUAL; break;
259     case ubi_trRIGHT:
260       tree->balance = ubi_trLEFT;  tmp->balance = ubi_trEQUAL; break;
261     }
262   newroot->balance = ubi_trEQUAL;
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[ubi_trLEFT];
279   newroot                     = tmp->Link[ubi_trRIGHT];
280   tmp->Link[ubi_trRIGHT]      = newroot->Link[ubi_trLEFT];
281   newroot->Link[ubi_trLEFT]   = tmp;
282   tree->Link[ubi_trLEFT]      = newroot->Link[ubi_trRIGHT];
283   newroot->Link[ubi_trRIGHT]  = tree;
284
285   newroot->Link[ubi_trPARENT] = tree->Link[ubi_trPARENT];
286   newroot->gender             = tree->gender;
287   tree->Link[ubi_trPARENT]    = newroot;
288   tree->gender                = ubi_trRIGHT;
289   tmp->Link[ubi_trPARENT]     = newroot;
290   tmp->gender                 = ubi_trLEFT;
291
292   if( tree->Link[ubi_trLEFT] )
293     {
294     tree->Link[ubi_trLEFT]->Link[ubi_trPARENT]  = tree;
295     tree->Link[ubi_trLEFT]->gender              = ubi_trLEFT;
296     }
297   if( tmp->Link[ubi_trRIGHT] )
298     {
299     tmp->Link[ubi_trRIGHT]->Link[ubi_trPARENT]  = tmp;
300     tmp->Link[ubi_trRIGHT]->gender              = ubi_trRIGHT;
301     }
302   if(newroot->Link[ubi_trPARENT])
303     newroot->Link[ubi_trPARENT]->Link[(int)(newroot->gender)] = newroot;
304
305   switch( newroot->balance )
306     {
307     case ubi_trLEFT  :
308       tree->balance = ubi_trRIGHT; tmp->balance = ubi_trEQUAL; break;
309     case ubi_trEQUAL :
310       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trEQUAL; break;
311     case ubi_trRIGHT :
312       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trLEFT;  break;
313     }
314   newroot->balance = ubi_trEQUAL;
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 += ubi_trNormalize(LorR);
339   else
340     {
341     char tallerbal;  /* Balance value of the root of the taller subtree of p. */
342
343     tallerbal = p->Link[(int)LorR]->balance;
344     if( ( ubi_trEQUAL == tallerbal ) || ( p->balance == tallerbal ) )
345       p = ( (ubi_trLEFT==LorR) ? R1(p) : L1(p) );   /* single rotation */
346     else
347       p = ( (ubi_trLEFT==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( ubi_trPARENT == subtree->gender )
381       return( subtree );
382     if( ubi_trEQUAL == subtree->balance )
383       return( Root );
384     LorR = subtree->gender;
385     subtree = subtree->Link[ubi_trPARENT];
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, ubi_trRevWay(LorR) );
421     if( ubi_trPARENT == subtree->gender )
422       return( subtree );
423     if( ubi_trEQUAL != subtree->balance )
424       return( Root );
425     LorR = subtree->gender;
426     subtree = subtree->Link[ubi_trPARENT];
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[ubi_trLEFT ] )
468     (oldnode->Link[ubi_trLEFT ])->Link[ubi_trPARENT] = newnode;
469   if(oldnode->Link[ubi_trRIGHT] )
470     (oldnode->Link[ubi_trRIGHT])->Link[ubi_trPARENT] = 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[ubi_trPARENT] )
499     Parent = &((Node1->Link[ubi_trPARENT])->Link[(int)(Node1->gender)]);
500   else
501     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
502   ReplaceNode( Parent, Node1, dummy_p );
503
504   if( Node2->Link[ubi_trPARENT] )
505     Parent = &((Node2->Link[ubi_trPARENT])->Link[(int)(Node2->gender)]);
506   else
507     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
508   ReplaceNode( Parent, Node2, Node1 );
509
510   if( dummy_p->Link[ubi_trPARENT] )
511     Parent = &((dummy_p->Link[ubi_trPARENT])->Link[(int)(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 = ubi_trEQUAL;
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 = ubi_trEQUAL;
601       RootPtr->root = (ubi_btNodePtr)Rebalance( (ubi_avlNodePtr)RootPtr->root,
602                                                 NewNode->Link[ubi_trPARENT],
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[ubi_trLEFT]) && (DeadNode->Link[ubi_trRIGHT]) )
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[ubi_trPARENT] )
642     parentp = (ubi_btNodePtr *)
643               &((DeadNode->Link[ubi_trPARENT])->Link[(int)(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( ubi_trEQUAL == DeadNode->balance )
651     (*parentp) = NULL;
652   else
653     {
654     p = (ubi_btNodePtr)(DeadNode->Link[(int)(DeadNode->balance)]);
655     p->Link[ubi_trPARENT] = (ubi_btNodePtr)DeadNode->Link[ubi_trPARENT];
656     p->gender  = DeadNode->gender;
657     (*parentp) = p;
658     }
659   RootPtr->root = (ubi_btNodePtr)Debalance( (ubi_avlNodePtr)RootPtr->root,
660                                             DeadNode->Link[ubi_trPARENT],
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 ============================== */