This is the ubiqx binary tree and linked list library.

This library is being included as part of the Samba distribution.
(Hurray!)
(This used to be commit 3590a783338defa4ff1385b2d5bb095c5051ac82)

1 files changed, 695 insertions, 0 deletions

diff --git a/source3/ubiqx/ubi_AVLtree.c b/source3/ubiqx/ubi_AVLtree.c
new file mode 100644
index 0000000000..73b8ece25b
--- /dev/null
+++ b/source3/ubiqx/ubi_AVLtree.c
@@ -0,0 +1,695 @@
+/* ========================================================================== **
+ *                              ubi_AVLtree.c
+ *
+ *  Copyright (C) 1991-1997 by Christopher R. Hertel
+ *
+ *  Email: crh@ubiqx.mn.org
+ * -------------------------------------------------------------------------- **
+ *
+ *  This module provides an implementation of AVL height balanced binary
+ *  trees.  (Adelson-Velskii, Landis 1962)
+ *
+ *  This file implements the core of the height-balanced (AVL) tree management
+ *  routines.  The header file, ubi_AVLtree.h, contains function prototypes
+ *  for all "exported" functions.
+ *
+ * -------------------------------------------------------------------------- **
+ *
+ *  This library is free software; you can redistribute it and/or
+ *  modify it under the terms of the GNU Library General Public
+ *  License as published by the Free Software Foundation; either
+ *  version 2 of the License, or (at your option) any later version.
+ *
+ *  This library is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  Library General Public License for more details.
+ *
+ *  You should have received a copy of the GNU Library General Public
+ *  License along with this library; if not, write to the Free
+ *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ * -------------------------------------------------------------------------- **
+ *
+ * $Log: ubi_AVLtree.c,v $
+ * Revision 1.1  1997/10/10 14:46:36  crh
+ * This is the ubiqx binary tree and linked list library.
+ * This library is being included as part of the Samba distribution.
+ * (Hurray!)
+ *
+ * Revision 2.4  1997/07/26 04:36:20  crh
+ * Andrew Leppard, aka "Grazgur", discovered that I still had my brains tied
+ * on backwards with respect to node deletion.  I did some more digging and
+ * discovered that I was not changing the balance values correctly in the
+ * single rotation functions.  Double rotation was working correctly because
+ * the formula for changing the balance values is the same for insertion or
+ * deletion.  Not so for single rotation.
+ *
+ * I have tested the fix by loading the tree with over 44 thousand names,
+ * deleting 2,629 of them (all those in which the second character is 'u')
+ * and then walking the tree recursively to verify that the balance factor of
+ * each node is correct.  Passed.
+ *
+ * Thanks Andrew!
+ *
+ * Also:
+ * + Changed ubi_TRUE and ubi_FALSE to ubi_trTRUE and ubi_trFALSE.
+ * + Rewrote the ubi_tr<func> macros because they weren't doing what I'd
+ *   hoped they would do (see the bottom of the header file).  They work now.
+ *
+ * Revision 2.3  1997/06/03 04:41:35  crh
+ * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing
+ * problems.
+ *
+ * Revision 2.2  1995/10/03 22:16:01  CRH
+ * Ubisized!
+ *
+ * Revision 2.1  95/03/09  23:45:59  CRH
+ * Added the ModuleID static string and function.  These modules are now
+ * self-identifying.
+ * 
+ * Revision 2.0  95/03/05  14:10:51  CRH
+ * This revision of ubi_AVLtree coincides with revision 2.0 of ubi_BinTree,
+ * and so includes all of the changes to that module.  In addition, a bug in
+ * the node deletion process has been fixed.
+ *
+ * After rewriting the Locate() function in ubi_BinTree, I decided that it was
+ * time to overhaul this module.  In the process, I discovered a bug related
+ * to node deletion.  To fix the bug, I wrote function Debalance().  A quick
+ * glance will show that it is very similar to the Rebalance() function.  In
+ * previous versions of this module, I tried to include the functionality of
+ * Debalance() within Rebalance(), with poor results.
+ *
+ * Revision 1.0  93/10/15  22:58:56  CRH
+ * With this revision, I have added a set of #define's that provide a single,
+ * standard API to all existing tree modules.  Until now, each of the three
+ * existing modules had a different function and typedef prefix, as follows:
+ *
+ *       Module        Prefix
+ *     ubi_BinTree     ubi_bt
+ *     ubi_AVLtree     ubi_avl
+ *     ubi_SplayTree   ubi_spt
+ *
+ * To further complicate matters, only those portions of the base module
+ * (ubi_BinTree) that were superceeded in the new module had the new names.
+ * For example, if you were using ubi_AVLtree, the AVL node structure was
+ * named "ubi_avlNode", but the root structure was still "ubi_btRoot".  Using
+ * SplayTree, the locate function was called "ubi_sptLocate", but the next
+ * and previous functions remained "ubi_btNext" and "ubi_btPrev".
+ *
+ * This was not too terrible if you were familiar with the modules and knew
+ * exactly which tree model you wanted to use.  If you wanted to be able to
+ * change modules (for speed comparisons, etc), things could get messy very
+ * quickly.
+ *
+ * So, I have added a set of defined names that get redefined in any of the
+ * descendant modules.  To use this standardized interface in your code,
+ * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with
+ * "ubi_tr".  The "ubi_tr" names will resolve to the correct function or
+ * datatype names for the module that you are using.  Just remember to
+ * include the header for that module in your program file.  Because these
+ * names are handled by the preprocessor, there is no added run-time
+ * overhead.
+ *
+ * Note that the original names do still exist, and can be used if you wish
+ * to write code directly to a specific module.  This should probably only be
+ * done if you are planning to implement a new descendant type, such as
+ * red/black trees.  CRH
+ *
+ *  V0.0 - May, 1990   -  Written by Christopher R. Hertel (CRH).
+ *
+ *  ========================================================================= **
+ */
+
+#include "ubi_AVLtree.h"            /* Header for THIS module.             */
+#include <stdlib.h>                 /* Standard C definitions, etc.        */
+
+/* ========================================================================== **
+ * Static data.
+ */
+
+static char ModuleID[] = "ubi_AVLtree\n\
+\t$Revision: 1.1 $\n\
+\t$Date: 1997/10/10 14:46:36 $\n\
+\t$Author: crh $\n";
+
+/* ========================================================================== **
+ * The next set of functions are the AVL balancing routines.  There are left
+ * and right, single and double rotations.  The rotation routines handle the
+ * rotations and reconnect all tree pointers that might get confused by the
+ * rotations.  A pointer to the new subtree root node is returned.
+ *
+ * Note that L1 and R1 are identical, except that all the RIGHTs and LEFTs
+ * are reversed.  The same is true for L2 and R2.  I'm sure that there is
+ * a clever way to reduce the amount of code by combining these functions,
+ * but it might involve additional overhead, and it would probably be a pain
+ * to read, debug, etc.
+ * -------------------------------------------------------------------------- **
+ */
+
+static ubi_avlNodePtr L1( ubi_avlNodePtr p )
+  /* ------------------------------------------------------------------------ **
+   * Single rotate left.
+   *
+   *  Input:  p - Pointer to the root of a tree (possibly a subtree).
+   *  Output: A pointer to the new root of the same subtree (now that node
+   *          p has been moved).
+   * ------------------------------------------------------------------------ **
+   */
+  {
+  ubi_avlNodePtr tmp;
+
+  tmp                = p->Link[RIGHT];
+  p->Link[RIGHT]     = tmp->Link[LEFT];
+  tmp->Link[LEFT]    = p;
+
+  tmp->Link[PARENT]  = p->Link[PARENT];
+  tmp->gender        = p->gender;
+  if(tmp->Link[PARENT])
+    (tmp->Link[PARENT])->Link[(tmp->gender)] = tmp;
+  p->Link[PARENT]    = tmp;
+  p->gender          = LEFT;
+  if( p->Link[RIGHT] )
+    {
+    p->Link[RIGHT]->Link[PARENT] = p;
+    (p->Link[RIGHT])->gender     = RIGHT;
+    }
+  p->balance -= Normalize( tmp->balance );
+  (tmp->balance)--;
+  return( tmp );
+  } /* L1 */
+
+static ubi_avlNodePtr R1( ubi_avlNodePtr p )
+  /* ------------------------------------------------------------------------ **
+   * Single rotate right.
+   *
+   *  Input:  p - Pointer to the root of a tree (possibly a subtree).
+   *  Output: A pointer to the new root of the same subtree (now that node
+   *          p has been moved).
+   * ------------------------------------------------------------------------ **
+   */
+  {
+  ubi_avlNodePtr tmp;
+
+  tmp                = p->Link[LEFT];
+  p->Link[LEFT]      = tmp->Link[RIGHT];
+  tmp->Link[RIGHT]   = p;
+
+  tmp->Link[PARENT]  = p->Link[PARENT];
+  tmp->gender        = p->gender;
+  if(tmp->Link[PARENT])
+    (tmp->Link[PARENT])->Link[(tmp->gender)] = tmp;
+  p->Link[PARENT]    = tmp;
+  p->gender          = RIGHT;
+  if(p->Link[LEFT])
+    {
+    p->Link[LEFT]->Link[PARENT]  = p;
+    p->Link[LEFT]->gender        = LEFT;
+    }
+  p->balance -= Normalize( tmp->balance );
+  (tmp->balance)++;
+  return( tmp );
+  } /* R1 */
+
+static ubi_avlNodePtr L2( ubi_avlNodePtr tree )
+  /* ------------------------------------------------------------------------ **
+   * Double rotate left.
+   *
+   *  Input:  p - Pointer to the root of a tree (possibly a subtree).
+   *  Output: A pointer to the new root of the same subtree (now that node
+   *          p has been moved).
+   * ------------------------------------------------------------------------ **
+   */
+  {
+  ubi_avlNodePtr tmp, newroot;
+
+  tmp                   = tree->Link[RIGHT];
+  newroot               = tmp->Link[LEFT];
+  tmp->Link[LEFT]       = newroot->Link[RIGHT];
+  newroot->Link[RIGHT]  = tmp;
+  tree->Link[RIGHT]     = newroot->Link[LEFT];
+  newroot->Link[LEFT]   = tree;
+
+  newroot->Link[PARENT] = tree->Link[PARENT];
+  newroot->gender       = tree->gender;
+  tree->Link[PARENT]    = newroot;
+  tree->gender          = LEFT;
+  tmp->Link[PARENT]     = newroot;
+  tmp->gender           = RIGHT;
+
+  if( tree->Link[RIGHT] )
+    {
+    tree->Link[RIGHT]->Link[PARENT] = tree;
+    tree->Link[RIGHT]->gender       = RIGHT;
+    }
+  if( tmp->Link[LEFT] )
+    {
+    tmp->Link[LEFT]->Link[PARENT]   = tmp;
+    tmp->Link[LEFT]->gender         = LEFT;
+    }
+  if(newroot->Link[PARENT])
+    newroot->Link[PARENT]->Link[newroot->gender] = newroot;
+
+  switch( newroot->balance )
+    {
+    case LEFT :
+      tree->balance = EQUAL; tmp->balance = RIGHT; break;
+    case EQUAL:
+      tree->balance = EQUAL; tmp->balance = EQUAL; break;
+    case RIGHT:
+      tree->balance = LEFT;  tmp->balance = EQUAL; break;
+    }
+  newroot->balance = EQUAL;
+  return( newroot );
+  } /* L2 */
+
+static ubi_avlNodePtr R2( ubi_avlNodePtr tree )
+  /* ------------------------------------------------------------------------ **
+   * Double rotate right.
+   *
+   *  Input:  p - Pointer to the root of a tree (possibly a subtree).
+   *  Output: A pointer to the new root of the same subtree (now that node
+   *          p has been moved).
+   * ------------------------------------------------------------------------ **
+   */
+  {
+  ubi_avlNodePtr tmp, newroot;
+
+  tmp                   = tree->Link[LEFT];
+  newroot               = tmp->Link[RIGHT];
+  tmp->Link[RIGHT]      = newroot->Link[LEFT];
+  newroot->Link[LEFT]   = tmp;
+  tree->Link[LEFT]      = newroot->Link[RIGHT];
+  newroot->Link[RIGHT]  = tree;
+
+  newroot->Link[PARENT] = tree->Link[PARENT];
+  newroot->gender       = tree->gender;
+  tree->Link[PARENT]    = newroot;
+  tree->gender          = RIGHT;
+  tmp->Link[PARENT]     = newroot;
+  tmp->gender           = LEFT;
+
+  if( tree->Link[LEFT] )
+    {
+    tree->Link[LEFT]->Link[PARENT]  = tree;
+    tree->Link[LEFT]->gender        = LEFT;
+    }
+  if( tmp->Link[RIGHT] )
+    {
+    tmp->Link[RIGHT]->Link[PARENT]  = tmp;
+    tmp->Link[RIGHT]->gender        = RIGHT;
+    }
+  if(newroot->Link[PARENT])
+    newroot->Link[PARENT]->Link[newroot->gender] = newroot;
+
+  switch( newroot->balance )
+    {
+    case LEFT  :
+      tree->balance = RIGHT; tmp->balance = EQUAL; break;
+    case EQUAL :
+      tree->balance = EQUAL; tmp->balance = EQUAL; break;
+    case RIGHT :
+      tree->balance = EQUAL; tmp->balance = LEFT;  break;
+    }
+  newroot->balance = EQUAL;
+  return( newroot );
+  } /* R2 */
+
+
+static ubi_avlNodePtr Adjust( ubi_avlNodePtr p, char LorR )
+  /* ------------------------------------------------------------------------ **
+   * Adjust the balance value at node *p.  If necessary, rotate the subtree
+   * rooted at p.
+   *
+   *  Input:  p    -  A pointer to the node to be adjusted.  One of the
+   *                  subtrees of this node has changed height, so the
+   *                  balance value at this node must be adjusted, possibly
+   *                  by rotating the tree at this node.
+   *          LorR -  Indicates the TALLER subtree.
+   *
+   *  Output: A pointer to the (possibly new) root node of the subtree.
+   *
+   *  Notes:  This function may be called after a node has been added *or*
+   *          deleted, so LorR indicates the TALLER subtree.
+   * ------------------------------------------------------------------------ **
+   */
+  {
+  if( p->balance != LorR )
+    p->balance += Normalize(LorR);
+  else
+    {
+    char tallerbal;  /* Balance value of the root of the taller subtree of p. */
+
+    tallerbal = p->Link[LorR]->balance;
+    if( ( EQUAL == tallerbal ) || ( p->balance == tallerbal ) )
+      p = ( (LEFT==LorR) ? R1(p) : L1(p) );   /* single rotation */
+    else
+      p = ( (LEFT==LorR) ? R2(p) : L2(p) );   /* double rotation */
+    }
+  return( p );
+  } /* Adjust */
+
+static ubi_avlNodePtr Rebalance( ubi_avlNodePtr Root,
+                                 ubi_avlNodePtr subtree,
+                                 char           LorR )
+  /* ------------------------------------------------------------------------ **
+   * Rebalance the tree following an insertion.
+   *
+   *  Input:  Root    - A pointer to the root node of the whole tree.
+   *          subtree - A pointer to the node that has just gained a new
+   *                    child.
+   *          LorR    - Gender of the child that has just been gained.
+   *
+   *  Output: A pointer to the (possibly new) root of the AVL tree.
+   *          Rebalancing the tree moves nodes around a bit, so the node
+   *          that *was* the root, may not be the root when we're finished.
+   *
+   *  Notes:  Rebalance() must walk up the tree from where we are (which is
+   *          where the latest change occurred), rebalancing the subtrees
+   *          along the way.  The rebalancing operation can stop if the
+   *          change at the current subtree root won't affect the rest of
+   *          the tree.  In the case of an addition, if a subtree root's
+   *          balance becomes EQUAL, then we know that the height of that
+   *          subtree has not changed, so we can exit.
+   * ------------------------------------------------------------------------ **
+   */
+  {
+  while( subtree )
+    {
+    subtree = Adjust( subtree, LorR );
+    if( PARENT == subtree->gender )
+      return( subtree );
+    if( EQUAL == subtree->balance )
+      return( Root );
+    LorR = subtree->gender;
+    subtree = subtree->Link[PARENT];
+    }
+  return( Root );
+  } /* Rebalance */
+
+static ubi_avlNodePtr Debalance( ubi_avlNodePtr Root,
+                                 ubi_avlNodePtr subtree,
+                                 char           LorR )
+  /* ------------------------------------------------------------------------ **
+   * Rebalance the tree following a deletion.
+   *
+   *  Input:  Root    - A pointer to the root node of the whole tree.
+   *          subtree - A pointer to the node who's child has just "left the
+   *                    nest".
+   *          LorR    - Gender of the child that left.
+   *
+   *  Output: A pointer to the (possibly new) root of the AVL tree.
+   *          Rebalancing the tree moves nodes around a bit, so the node
+   *          that *was* the root, may not be the root when we're finished.
+   *
+   *  Notes:  Debalance() is subtly different from Rebalance() (above) in
+   *          two respects.
+   *            * When it calls Adjust(), it passes the *opposite* of LorR.
+   *              This is because LorR, as passed into Debalance() indicates
+   *              the shorter subtree.  As we move up the tree, LorR is
+   *              assigned the gender of the node that we are leaving (i.e.,
+   *              the subtree that we just rebalanced).
+   *            * We know that a subtree has not changed height if the
+   *              balance becomes LEFT or RIGHT.  This is the *opposite* of
+   *              what happens in Rebalance().
+   * ------------------------------------------------------------------------ **
+   */
+  {
+  while( subtree )
+    {
+    subtree = Adjust( subtree, RevWay(LorR) );
+    if( PARENT == subtree->gender )
+      return( subtree );
+    if( EQUAL != subtree->balance )
+      return( Root );
+    LorR = subtree->gender;
+    subtree = subtree->Link[PARENT];
+    }
+  return( Root );
+  } /* Debalance */
+
+
+/* -------------------------------------------------------------------------- **
+ * The next two functions are used for general tree manipulation.  They are
+ * each slightly different from their ubi_BinTree counterparts.
+ * -------------------------------------------------------------------------- **
+ */
+
+static void ReplaceNode( ubi_avlNodePtr *parent,
+                         ubi_avlNodePtr  oldnode,
+                         ubi_avlNodePtr  newnode )
+  /* ------------------------------------------------------------------------ **
+   * Remove node oldnode from the tree, replacing it with node newnode.
+   *
+   * Input:
+   *  parent   - A pointer to he parent pointer of the node to be
+   *             replaced.  <parent> may point to the Link[] field of
+   *             a parent node, or it may indicate the root pointer at
+   *             the top of the tree.
+   *  oldnode  - A pointer to the node that is to be replaced.
+   *  newnode  - A pointer to the node that is to be installed in the
+   *             place of <*oldnode>.
+   *
+   * Notes:    Don't forget to free oldnode.
+   *           The only difference between this function and the ubi_bt
+   *           version is that the node size is sizeof( ubi_avlNode ), not
+   *           sizeof( ubi_btNode ).
+   * ------------------------------------------------------------------------ **
+   */
+  {
+  register int i;
+  register int avlNodeSize = sizeof( ubi_avlNode );
+
+  for( i = 0; i < avlNodeSize; i++ )
+    ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
+  (*parent) = newnode;
+
+  if(oldnode->Link[LEFT ] )
+    (oldnode->Link[LEFT ])->Link[PARENT] = newnode;
+  if(oldnode->Link[RIGHT] )
+    (oldnode->Link[RIGHT])->Link[PARENT] = newnode;
+  } /* ReplaceNode */
+
+static void SwapNodes( ubi_btRootPtr  RootPtr,
+                       ubi_avlNodePtr Node1,
+                       ubi_avlNodePtr Node2 )
+  /* ------------------------------------------------------------------------ **
+   * This function swaps two nodes in the tree.  Node1 will take the place of
+   * Node2, and Node2 will fill in the space left vacant by Node 1.
+   *
+   * Input:
+   *  RootPtr  - pointer to the tree header structure for this tree.
+   *  Node1    - \
+   *              > These are the two nodes which are to be swapped.
+   *  Node2    - /
+   *
+   * Notes:
+   *  This function does a three step swap, using a dummy node as a place
+   *  holder.  This function is used by ubi_avlRemove().
+   *  The only difference between this function and its ubi_bt counterpart
+   *  is that the nodes are ubi_avlNodes, not ubi_btNodes.
+   * ------------------------------------------------------------------------ **
+   */
+  {
+  ubi_avlNodePtr *Parent;
+  ubi_avlNode     dummy;
+  ubi_avlNodePtr  dummy_p = &dummy;
+
+  if( Node1->Link[PARENT] )
+    Parent = &((Node1->Link[PARENT])->Link[Node1->gender]);
+  else
+    Parent = (ubi_avlNodePtr *)&(RootPtr->root);
+  ReplaceNode( Parent, Node1, dummy_p );
+
+  if( Node2->Link[PARENT] )
+    Parent = &((Node2->Link[PARENT])->Link[Node2->gender]);
+  else
+    Parent = (ubi_avlNodePtr *)&(RootPtr->root);
+  ReplaceNode( Parent, Node2, Node1 );
+
+  if( dummy_p->Link[PARENT] )
+    Parent = &((dummy_p->Link[PARENT])->Link[dummy_p->gender]);
+  else
+    Parent = (ubi_avlNodePtr *)&(RootPtr->root);
+  ReplaceNode( Parent, dummy_p, Node2 );
+  } /* SwapNodes */
+
+
+/* ========================================================================== **
+ *         Public, exported (ie. not static-ly declared) functions...
+ * -------------------------------------------------------------------------- **
+ */
+
+ubi_avlNodePtr ubi_avlInitNode( ubi_avlNodePtr NodePtr )
+  /* ------------------------------------------------------------------------ **
+   * Initialize a tree node.
+   *
+   *  Input:   NodePtr  - pointer to a ubi_btNode structure to be
+   *                      initialized.
+   *  Output:  a pointer to the initialized ubi_avlNode structure (ie. the
+   *           same as the input pointer).
+   * ------------------------------------------------------------------------ **
+   */
+  {
+  (void)ubi_btInitNode( (ubi_btNodePtr)NodePtr );
+  NodePtr->balance = EQUAL;
+  return( NodePtr );
+  } /* ubi_avlInitNode */
+
+ubi_trBool ubi_avlInsert( ubi_btRootPtr   RootPtr,
+                          ubi_avlNodePtr  NewNode,
+                          ubi_btItemPtr   ItemPtr,
+                          ubi_avlNodePtr *OldNode )
+  /* ------------------------------------------------------------------------ **
+   * This function uses a non-recursive algorithm to add a new element to
+   * the tree.
+   *
+   *  Input:   RootPtr  -  a pointer to the ubi_btRoot structure that indicates
+   *                       the root of the tree to which NewNode is to be added.
+   *           NewNode  -  a pointer to an ubi_avlNode structure that is NOT
+   *                       part of any tree.
+   *           ItemPtr  -  A pointer to the sort key that is stored within
+   *                       *NewNode.  ItemPtr MUST point to information stored
+   *                       in *NewNode or an EXACT DUPLICATE.  The key data
+   *                       indicated by ItemPtr is used to place the new node
+   *                       into the tree.
+   *           OldNode  -  a pointer to an ubi_btNodePtr.  When searching
+   *                       the tree, a duplicate node may be found.  If
+   *                       duplicates are allowed, then the new node will
+   *                       be simply placed into the tree.  If duplicates
+   *                       are not allowed, however, then one of two things
+   *                       may happen.
+   *                       1) if overwritting *is not* allowed, this
+   *                          function will return FALSE (indicating that
+   *                          the new node could not be inserted), and
+   *                          *OldNode will point to the duplicate that is
+   *                          still in the tree.
+   *                       2) if overwritting *is* allowed, then this
+   *                          function will swap **OldNode for *NewNode.
+   *                          In this case, *OldNode will point to the node
+   *                          that was removed (thus allowing you to free
+   *                          the node).
+   *                          **  If you are using overwrite mode, ALWAYS  **
+   *                          ** check the return value of this parameter! **
+   *                 Note: You may pass NULL in this parameter, the
+   *                       function knows how to cope.  If you do this,
+   *                       however, there will be no way to return a
+   *                       pointer to an old (ie. replaced) node (which is
+   *                       a problem if you are using overwrite mode).
+   *
+   *  Output:  a boolean value indicating success or failure.  The function
+   *           will return FALSE if the node could not be added to the tree.
+   *           Such failure will only occur if duplicates are not allowed,
+   *           nodes cannot be overwritten, AND a duplicate key was found
+   *           within the tree.
+   * ------------------------------------------------------------------------ **
+   */
+  {
+  ubi_avlNodePtr OtherP;
+
+  if( !(OldNode) ) OldNode = &OtherP;
+  if( ubi_btInsert( RootPtr,
+                    (ubi_btNodePtr)NewNode,
+                    ItemPtr,
+                    (ubi_btNodePtr *)OldNode ) )
+    {
+    if( (*OldNode) )
+      NewNode->balance = (*OldNode)->balance;
+    else
+      {
+      NewNode->balance = EQUAL;
+      RootPtr->root = (ubi_btNodePtr)Rebalance( (ubi_avlNodePtr)RootPtr->root,
+                                                NewNode->Link[PARENT],
+                                                NewNode->gender );
+      }
+    return( ubi_trTRUE );
+    }
+  return( ubi_trFALSE );      /* Failure: could not replace an existing node. */
+  } /* ubi_avlInsert */
+
+ubi_avlNodePtr ubi_avlRemove( ubi_btRootPtr  RootPtr,
+                              ubi_avlNodePtr DeadNode )
+  /* ------------------------------------------------------------------------ **
+   * This function removes the indicated node from the tree, after which the
+   * tree is rebalanced.
+   *
+   *  Input:  RootPtr  -  A pointer to the header of the tree that contains
+   *                      the node to be removed.
+   *          DeadNode -  A pointer to the node that will be removed.
+   *
+   *  Output: This function returns a pointer to the node that was removed
+   *          from the tree (ie. the same as DeadNode).
+   *
+   *  Note:   The node MUST be in the tree indicated by RootPtr.  If not,
+   *          strange and evil things will happen to your trees.
+   * ------------------------------------------------------------------------ **
+   */
+  {
+  ubi_btNodePtr p,
+               *parentp;
+
+  /* if the node has both left and right subtrees, then we have to swap
+   * it with another node.
+   */
+  if( (DeadNode->Link[LEFT]) && (DeadNode->Link[RIGHT]) )
+    SwapNodes( RootPtr, DeadNode, ubi_trPrev( DeadNode ) );
+
+  /* The parent of the node to be deleted may be another node, or it may be
+   * the root of the tree.  Since we're not sure, it's best just to have
+   * a pointer to the parent pointer, whatever it is.
+   */
+  if( DeadNode->Link[PARENT] )
+    parentp = (ubi_btNodePtr *)
+              &((DeadNode->Link[PARENT])->Link[(DeadNode->gender)]);
+  else
+    parentp = &( RootPtr->root );
+
+  /* Now link the parent to the only grand-child.  Patch up the gender and
+   * such, and rebalance.
+   */
+  if( EQUAL == DeadNode->balance )
+    (*parentp) = NULL;
+  else
+    {
+    p = (ubi_btNodePtr)(DeadNode->Link[(DeadNode->balance)]);
+    p->Link[PARENT]  = (ubi_btNodePtr)DeadNode->Link[PARENT];
+    p->gender        = DeadNode->gender;
+    (*parentp) = p;
+    }
+  RootPtr->root = (ubi_btNodePtr)Debalance( (ubi_avlNodePtr)RootPtr->root,
+                                            DeadNode->Link[PARENT],
+                                            DeadNode->gender );
+
+  (RootPtr->count)--;
+  return( DeadNode );
+  } /* ubi_avlRemove */
+
+int ubi_avlModuleID( int size, char *list[] )
+  /* ------------------------------------------------------------------------ **
+   * Returns a set of strings that identify the module.
+   *
+   *  Input:  size  - The number of elements in the array <list>.
+   *          list  - An array of pointers of type (char *).  This array
+   *                  should, initially, be empty.  This function will fill
+   *                  in the array with pointers to strings.
+   *  Output: The number of elements of <list> that were used.  If this value
+   *          is less than <size>, the values of the remaining elements are
+   *          not guaranteed.
+   *
+   *  Notes:  Please keep in mind that the pointers returned indicate strings
+   *          stored in static memory.  Don't free() them, don't write over
+   *          them, etc.  Just read them.
+   * ------------------------------------------------------------------------ **
+   */
+  {
+  if( size > 0 )
+    {
+    list[0] = ModuleID;
+    if( size > 1 )
+      return( 1 + ubi_btModuleID( --size, &(list[1]) ) );
+    return( 1 );
+    }
+  return( 0 );
+  } /* ubi_avlModuleID */
+
+/* ============================== The End ============================== */