While working on a general-purpose caching module (out soon), I thought of

a better way to handle the node pointer array used in ubi_BinTree.  The
change simplified the code a bigbunch.  It also forced updates to all of
the binary tree modules.  CRH
(This used to be commit db9898559f1493ade4478196b72663759bb18995)

6 files changed, 505 insertions, 718 deletions

diff --git a/source3/ubiqx/ubi_AVLtree.c b/source3/ubiqx/ubi_AVLtree.c
index 29ecc74740..6ad4053dfa 100644
--- a/source3/ubiqx/ubi_AVLtree.c
+++ b/source3/ubiqx/ubi_AVLtree.c
@@ -9,10 +9,6 @@
  *  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
@@ -31,84 +27,20 @@
  *
  * -------------------------------------------------------------------------- **
  *
- * 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.
+ * Log: ubi_AVLtree.c,v
+ * Revision 3.0  1997/12/08 05:38:55  crh
+ * This is a new major revision level.  The handling of the pointers in the
+ * ubi_trNode structure was redesigned.  The result is that there are fewer
+ * macros floating about, and fewer cases in which values have to be
+ * incremented or decremented.  See ubi_BinTree for more information.
  *
- * 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.
+ * Revision 2; 1995/03/05 - 1997/12/07:
+ * An overhaul to the node delete process.  I had gotten it wrong in a
+ * couple of places, thought I'd fixed it, and then found that I'd missing
+ * something more.  Thanks to Andrew Leppard for the bug report!
  *
- * 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
+ * Revision 1;  93/10/15 - 95/03/05:
+ * Added the ubi_tr defines.  See ubi_BinTree.h for more info.
  *
  *  V0.0 - May, 1990   -  Written by Christopher R. Hertel (CRH).
  *
@@ -123,8 +55,8 @@
  */
 
 static char ModuleID[] = "ubi_AVLtree\n\
-\tRevision: 2.4\n\
-\tDate: 1997/07/26 04:36:20\n\
+\tRevision: 3.0\n\
+\tDate: 1997/12/08 05:38:55\n\
 \tAuthor: crh\n";
 
 /* ========================================================================== **
@@ -153,22 +85,22 @@ static ubi_avlNodePtr L1( ubi_avlNodePtr p )
   {
   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] )
+  tmp                      = p->Link[ubi_trRIGHT];
+  p->Link[ubi_trRIGHT]     = tmp->Link[ubi_trLEFT];
+  tmp->Link[ubi_trLEFT]    = p;
+
+  tmp->Link[ubi_trPARENT]  = p->Link[ubi_trPARENT];
+  tmp->gender              = p->gender;
+  if(tmp->Link[ubi_trPARENT])
+    (tmp->Link[ubi_trPARENT])->Link[(tmp->gender)] = tmp;
+  p->Link[ubi_trPARENT]    = tmp;
+  p->gender                = ubi_trLEFT;
+  if( p->Link[ubi_trRIGHT] )
     {
-    p->Link[RIGHT]->Link[PARENT] = p;
-    (p->Link[RIGHT])->gender     = RIGHT;
+    p->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = p;
+    (p->Link[ubi_trRIGHT])->gender           = ubi_trRIGHT;
     }
-  p->balance -= Normalize( tmp->balance );
+  p->balance -= tmp->balance;
   (tmp->balance)--;
   return( tmp );
   } /* L1 */
@@ -185,22 +117,22 @@ static ubi_avlNodePtr R1( ubi_avlNodePtr p )
   {
   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])
+  tmp                      = p->Link[ubi_trLEFT];
+  p->Link[ubi_trLEFT]      = tmp->Link[ubi_trRIGHT];
+  tmp->Link[ubi_trRIGHT]   = p;
+
+  tmp->Link[ubi_trPARENT]  = p->Link[ubi_trPARENT];
+  tmp->gender              = p->gender;
+  if(tmp->Link[ubi_trPARENT])
+    (tmp->Link[ubi_trPARENT])->Link[(tmp->gender)] = tmp;
+  p->Link[ubi_trPARENT]    = tmp;
+  p->gender                = ubi_trRIGHT;
+  if(p->Link[ubi_trLEFT])
     {
-    p->Link[LEFT]->Link[PARENT]  = p;
-    p->Link[LEFT]->gender        = LEFT;
+    p->Link[ubi_trLEFT]->Link[ubi_trPARENT]  = p;
+    p->Link[ubi_trLEFT]->gender              = ubi_trLEFT;
     }
-  p->balance -= Normalize( tmp->balance );
+  p->balance -= tmp->balance;
   (tmp->balance)++;
   return( tmp );
   } /* R1 */
@@ -217,43 +149,43 @@ static ubi_avlNodePtr L2( ubi_avlNodePtr tree )
   {
   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] )
+  tmp                         = tree->Link[ubi_trRIGHT];
+  newroot                     = tmp->Link[ubi_trLEFT];
+  tmp->Link[ubi_trLEFT]       = newroot->Link[ubi_trRIGHT];
+  newroot->Link[ubi_trRIGHT]  = tmp;
+  tree->Link[ubi_trRIGHT]     = newroot->Link[ubi_trLEFT];
+  newroot->Link[ubi_trLEFT]   = tree;
+
+  newroot->Link[ubi_trPARENT] = tree->Link[ubi_trPARENT];
+  newroot->gender             = tree->gender;
+  tree->Link[ubi_trPARENT]    = newroot;
+  tree->gender                = ubi_trLEFT;
+  tmp->Link[ubi_trPARENT]     = newroot;
+  tmp->gender                 = ubi_trRIGHT;
+
+  if( tree->Link[ubi_trRIGHT] )
     {
-    tree->Link[RIGHT]->Link[PARENT] = tree;
-    tree->Link[RIGHT]->gender       = RIGHT;
+    tree->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = tree;
+    tree->Link[ubi_trRIGHT]->gender             = ubi_trRIGHT;
     }
-  if( tmp->Link[LEFT] )
+  if( tmp->Link[ubi_trLEFT] )
     {
-    tmp->Link[LEFT]->Link[PARENT]   = tmp;
-    tmp->Link[LEFT]->gender         = LEFT;
+    tmp->Link[ubi_trLEFT]->Link[ubi_trPARENT]   = tmp;
+    tmp->Link[ubi_trLEFT]->gender               = ubi_trLEFT;
     }
-  if(newroot->Link[PARENT])
-    newroot->Link[PARENT]->Link[newroot->gender] = newroot;
+  if(newroot->Link[ubi_trPARENT])
+    newroot->Link[ubi_trPARENT]->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;
+    case ubi_trLEFT :
+      tree->balance = ubi_trEQUAL; tmp->balance = ubi_trRIGHT; break;
+    case ubi_trEQUAL:
+      tree->balance = ubi_trEQUAL; tmp->balance = ubi_trEQUAL; break;
+    case ubi_trRIGHT:
+      tree->balance = ubi_trLEFT;  tmp->balance = ubi_trEQUAL; break;
     }
-  newroot->balance = EQUAL;
+  newroot->balance = ubi_trEQUAL;
   return( newroot );
   } /* L2 */
 
@@ -269,48 +201,48 @@ static ubi_avlNodePtr R2( ubi_avlNodePtr tree )
   {
   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] )
+  tmp                         = tree->Link[ubi_trLEFT];
+  newroot                     = tmp->Link[ubi_trRIGHT];
+  tmp->Link[ubi_trRIGHT]      = newroot->Link[ubi_trLEFT];
+  newroot->Link[ubi_trLEFT]   = tmp;
+  tree->Link[ubi_trLEFT]      = newroot->Link[ubi_trRIGHT];
+  newroot->Link[ubi_trRIGHT]  = tree;
+
+  newroot->Link[ubi_trPARENT] = tree->Link[ubi_trPARENT];
+  newroot->gender             = tree->gender;
+  tree->Link[ubi_trPARENT]    = newroot;
+  tree->gender                = ubi_trRIGHT;
+  tmp->Link[ubi_trPARENT]     = newroot;
+  tmp->gender                 = ubi_trLEFT;
+
+  if( tree->Link[ubi_trLEFT] )
     {
-    tree->Link[LEFT]->Link[PARENT]  = tree;
-    tree->Link[LEFT]->gender        = LEFT;
+    tree->Link[ubi_trLEFT]->Link[ubi_trPARENT]  = tree;
+    tree->Link[ubi_trLEFT]->gender              = ubi_trLEFT;
     }
-  if( tmp->Link[RIGHT] )
+  if( tmp->Link[ubi_trRIGHT] )
     {
-    tmp->Link[RIGHT]->Link[PARENT]  = tmp;
-    tmp->Link[RIGHT]->gender        = RIGHT;
+    tmp->Link[ubi_trRIGHT]->Link[ubi_trPARENT]  = tmp;
+    tmp->Link[ubi_trRIGHT]->gender              = ubi_trRIGHT;
     }
-  if(newroot->Link[PARENT])
-    newroot->Link[PARENT]->Link[newroot->gender] = newroot;
+  if(newroot->Link[ubi_trPARENT])
+    newroot->Link[ubi_trPARENT]->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;
+    case ubi_trLEFT  :
+      tree->balance = ubi_trRIGHT; tmp->balance = ubi_trEQUAL; break;
+    case ubi_trEQUAL :
+      tree->balance = ubi_trEQUAL; tmp->balance = ubi_trEQUAL; break;
+    case ubi_trRIGHT :
+      tree->balance = ubi_trEQUAL; tmp->balance = ubi_trLEFT;  break;
     }
-  newroot->balance = EQUAL;
+  newroot->balance = ubi_trEQUAL;
   return( newroot );
   } /* R2 */
 
 
-static ubi_avlNodePtr Adjust( ubi_avlNodePtr p, char LorR )
+static ubi_avlNodePtr Adjust( ubi_avlNodePtr p, signed char LorR )
   /* ------------------------------------------------------------------------ **
    * Adjust the balance value at node *p.  If necessary, rotate the subtree
    * rooted at p.
@@ -329,23 +261,23 @@ static ubi_avlNodePtr Adjust( ubi_avlNodePtr p, char LorR )
    */
   {
   if( p->balance != LorR )
-    p->balance += Normalize(LorR);
+    p->balance += LorR;
   else
     {
-    char tallerbal;  /* Balance value of the root of the taller subtree of p. */
+    signed char tallerbal;  /* Balance of 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 */
+    if( ( ubi_trEQUAL == tallerbal ) || ( p->balance == tallerbal ) )
+      p = ( (ubi_trLEFT==LorR) ? R1(p) : L1(p) );   /* single rotation */
     else
-      p = ( (LEFT==LorR) ? R2(p) : L2(p) );   /* double rotation */
+      p = ( (ubi_trLEFT==LorR) ? R2(p) : L2(p) );   /* double rotation */
     }
   return( p );
   } /* Adjust */
 
 static ubi_avlNodePtr Rebalance( ubi_avlNodePtr Root,
                                  ubi_avlNodePtr subtree,
-                                 char           LorR )
+                                 signed char    LorR )
   /* ------------------------------------------------------------------------ **
    * Rebalance the tree following an insertion.
    *
@@ -371,19 +303,19 @@ static ubi_avlNodePtr Rebalance( ubi_avlNodePtr Root,
   while( subtree )
     {
     subtree = Adjust( subtree, LorR );
-    if( PARENT == subtree->gender )
+    if( ubi_trPARENT == subtree->gender )
       return( subtree );
-    if( EQUAL == subtree->balance )
+    if( ubi_trEQUAL == subtree->balance )
       return( Root );
     LorR = subtree->gender;
-    subtree = subtree->Link[PARENT];
+    subtree = subtree->Link[ubi_trPARENT];
     }
   return( Root );
   } /* Rebalance */
 
 static ubi_avlNodePtr Debalance( ubi_avlNodePtr Root,
                                  ubi_avlNodePtr subtree,
-                                 char           LorR )
+                                 signed char    LorR )
   /* ------------------------------------------------------------------------ **
    * Rebalance the tree following a deletion.
    *
@@ -411,13 +343,13 @@ static ubi_avlNodePtr Debalance( ubi_avlNodePtr Root,
   {
   while( subtree )
     {
-    subtree = Adjust( subtree, RevWay(LorR) );
-    if( PARENT == subtree->gender )
+    subtree = Adjust( subtree, ubi_trRevWay(LorR) );
+    if( ubi_trPARENT == subtree->gender )
       return( subtree );
-    if( EQUAL != subtree->balance )
+    if( ubi_trEQUAL != subtree->balance )
       return( Root );
     LorR = subtree->gender;
-    subtree = subtree->Link[PARENT];
+    subtree = subtree->Link[ubi_trPARENT];
     }
   return( Root );
   } /* Debalance */
@@ -458,10 +390,10 @@ static void ReplaceNode( ubi_avlNodePtr *parent,
     ((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;
+  if(oldnode->Link[ubi_trLEFT ] )
+    (oldnode->Link[ubi_trLEFT ])->Link[ubi_trPARENT] = newnode;
+  if(oldnode->Link[ubi_trRIGHT] )
+    (oldnode->Link[ubi_trRIGHT])->Link[ubi_trPARENT] = newnode;
   } /* ReplaceNode */
 
 static void SwapNodes( ubi_btRootPtr  RootPtr,
@@ -489,20 +421,20 @@ static void SwapNodes( ubi_btRootPtr  RootPtr,
   ubi_avlNode     dummy;
   ubi_avlNodePtr  dummy_p = &dummy;
 
-  if( Node1->Link[PARENT] )
-    Parent = &((Node1->Link[PARENT])->Link[Node1->gender]);
+  if( Node1->Link[ubi_trPARENT] )
+    Parent = &((Node1->Link[ubi_trPARENT])->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]);
+  if( Node2->Link[ubi_trPARENT] )
+    Parent = &((Node2->Link[ubi_trPARENT])->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]);
+  if( dummy_p->Link[ubi_trPARENT] )
+    Parent = &((dummy_p->Link[ubi_trPARENT])->Link[dummy_p->gender]);
   else
     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
   ReplaceNode( Parent, dummy_p, Node2 );
@@ -526,7 +458,7 @@ ubi_avlNodePtr ubi_avlInitNode( ubi_avlNodePtr NodePtr )
    */
   {
   (void)ubi_btInitNode( (ubi_btNodePtr)NodePtr );
-  NodePtr->balance = EQUAL;
+  NodePtr->balance = ubi_trEQUAL;
   return( NodePtr );
   } /* ubi_avlInitNode */
 
@@ -591,9 +523,9 @@ ubi_trBool ubi_avlInsert( ubi_btRootPtr   RootPtr,
       NewNode->balance = (*OldNode)->balance;
     else
       {
-      NewNode->balance = EQUAL;
+      NewNode->balance = ubi_trEQUAL;
       RootPtr->root = (ubi_btNodePtr)Rebalance( (ubi_avlNodePtr)RootPtr->root,
-                                                NewNode->Link[PARENT],
+                                                NewNode->Link[ubi_trPARENT],
                                                 NewNode->gender );
       }
     return( ubi_trTRUE );
@@ -625,33 +557,33 @@ ubi_avlNodePtr ubi_avlRemove( ubi_btRootPtr  RootPtr,
   /* 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]) )
+  if( (DeadNode->Link[ubi_trLEFT]) && (DeadNode->Link[ubi_trRIGHT]) )
     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] )
+  if( DeadNode->Link[ubi_trPARENT] )
     parentp = (ubi_btNodePtr *)
-              &((DeadNode->Link[PARENT])->Link[(DeadNode->gender)]);
+              &((DeadNode->Link[ubi_trPARENT])->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 )
+  if( ubi_trEQUAL == DeadNode->balance )
     (*parentp) = NULL;
   else
     {
     p = (ubi_btNodePtr)(DeadNode->Link[(DeadNode->balance)]);
-    p->Link[PARENT]  = (ubi_btNodePtr)DeadNode->Link[PARENT];
-    p->gender        = DeadNode->gender;
+    p->Link[ubi_trPARENT]  = (ubi_btNodePtr)DeadNode->Link[ubi_trPARENT];
+    p->gender              = DeadNode->gender;
     (*parentp) = p;
     }
   RootPtr->root = (ubi_btNodePtr)Debalance( (ubi_avlNodePtr)RootPtr->root,
-                                            DeadNode->Link[PARENT],
+                                            DeadNode->Link[ubi_trPARENT],
                                             DeadNode->gender );
 
   (RootPtr->count)--;
diff --git a/source3/ubiqx/ubi_AVLtree.h b/source3/ubiqx/ubi_AVLtree.h
index b86f24a412..61aaf99348 100644
--- a/source3/ubiqx/ubi_AVLtree.h
+++ b/source3/ubiqx/ubi_AVLtree.h
@@ -34,85 +34,20 @@
  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  *
  * -------------------------------------------------------------------------- **
+ * Log: ubi_AVLtree.h,v
+ * Revision 3.0  1997/12/08 05:39:01  crh
+ * This is a new major revision level.  The handling of the pointers in the
+ * ubi_trNode structure was redesigned.  The result is that there are fewer
+ * macros floating about, and fewer cases in which values have to be
+ * incremented or decremented.  See ubi_BinTree for more information.
  *
- * Revision 2.4  1997/07/26 04:36:23  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 05:22:07  crh
- * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing
- * problems.
- *
- * Revision 2.2  1995/10/03 22:15:47  CRH
- * Ubisized!
- *
- * Revision 2.1  95/03/09  23:46:44  CRH
- * Added the ModuleID static string and function.  These modules are now
- * self-identifying.
+ * Revision 2; 1995/03/05 - 1997/12/07:
+ * An overhaul to the node delete process.  I had gotten it wrong in a
+ * couple of places, thought I'd fixed it, and then found that I'd missed
+ * something more.  Thanks to Andrew Leppard for the bug report!
  * 
- * Revision 2.0  95/03/05  14:11:22  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:48  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
+ * Revision 1;  93/10/15 - 95/03/05:
+ * Added the ubi_tr defines.  See ubi_BinTree.h for more info.
  *
  *  V0.0 - May, 1990   -  Written by Christopher R. Hertel (CRH).
  *
@@ -128,6 +63,7 @@
  *       header so that you can use the structure as a building block.
  *
  *  The fields are as follows:
+ *    leftlink -  A space filler.  This field will be accessed as Link[-1].
  *    Link     -  An array of pointers.  These pointers are manipulated by the
  *                BT and AVL routines, and indicate the left and right child
  *                nodes, plus the parent node.  By keeping track of the parent
@@ -142,25 +78,21 @@
  *                indicates which subtree of the current node is longer, or if
  *                the subtrees are, in fact, balanced with respect to each
  *                other.
- *  ------------------------------------------------------------------------- **
+ *
  */
 
-typedef struct ubi_avlNodeStruct {
-  struct ubi_avlNodeStruct
-         *Link[3];      /* Normal Binary Tree Node type.                      */
-  char    gender;       /* The node is either the RIGHT or LEFT child of its  */
-                        /* parent, or is the root node.                       */
-  char    balance;      /* In an AVL tree, each node is the root of a subtree */
-                        /* that may be balanced, or be one node longer to the */
-                        /* right or left.  This field keeps track of the      */
-                        /* balance value of each node.                        */
-    } ubi_avlNode;  /* Typedef'd name for an avl tree node. */
+typedef struct ubi_avlNodeStruct
+  {
+  struct ubi_avlNodeStruct *leftlink;
+  struct ubi_avlNodeStruct *Link[2];
+  signed char               gender; 
+  signed char               balance;
+  } ubi_avlNode;
 
-typedef ubi_avlNode *ubi_avlNodePtr;    /* a Pointer to an AVL node */
+typedef ubi_avlNode *ubi_avlNodePtr;    /* a Pointer to an AVL node. */
 
 /* -------------------------------------------------------------------------- **
- *  Function prototypes.
- * -------------------------------------------------------------------------- **
+ *  Function prototypes...
  */
 
 ubi_avlNodePtr ubi_avlInitNode( ubi_avlNodePtr NodePtr );
diff --git a/source3/ubiqx/ubi_BinTree.c b/source3/ubiqx/ubi_BinTree.c
index 68e819a14b..15bdeb1d85 100644
--- a/source3/ubiqx/ubi_BinTree.c
+++ b/source3/ubiqx/ubi_BinTree.c
@@ -6,12 +6,7 @@
  *  Email:  crh@ubiqx.mn.org
  * -------------------------------------------------------------------------- **
  *
- *  ubi_BinTree manages a simple binary tree.  Nothing fancy here.  No height
- *  balancing, no restructuring.  Still, a good tool for creating short, low-
- *  overhead sorted lists of things that need to be found in a hurry.
- *
- *  In addition, this module provides a good basis for creating other types
- *  of binary tree handling modules.
+ *  This module implements simple binary trees.
  *
  * -------------------------------------------------------------------------- **
  *
@@ -31,64 +26,73 @@
  *
  * -------------------------------------------------------------------------- **
  *
- * Revision 2.4  1997/07/26 04:11:10  crh
- * + Just to be annoying I changed ubi_TRUE and ubi_FALSE to ubi_trTRUE
- *   and ubi_trFALSE.
- * + There is now a type ubi_trBool to go with ubi_trTRUE and ubi_trFALSE.
- * + There used to be something called "ubi_TypeDefs.h".  I got rid of it.
- * + Added function ubi_btLeafNode().
+ * Log: ubi_BinTree.c,v
+ * Revision 3.0  1997/12/08 06:49:11  crh
+ * This is a new major revision level for all ubiqx binary tree modules.
+ * In previous releases, the ubi_trNode structure looked like this:
+ *
+ *   typedef struct ubi_btNodeStruct
+ *     {
+ *     struct ubi_btNodeStruct *Link[3];
+ *     signed char              gender;
+ *     } ubi_btNode;
+ *
+ * As a result, the pointers were indexed as
+ *
+ *   Link[0] == Left Child
+ *   Link[1] == Parent
+ *   Link[2] == Right Child
  *
- * Revision 2.3  1997/06/03 05:16:17  crh
- * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid conflicts.
- * Also changed the interface to function InitTree().  See the comments
- * for this function for more information.
+ * With this release, the node structure changes to:
  *
- * Revision 2.2  1995/10/03 22:00:07  CRH
- * Ubisized!
- * 
- * Revision 2.1  95/03/09  23:37:10  CRH
- * Added the ModuleID static string and function.  These modules are now
- * self-identifying.
- * 
- * Revision 2.0  95/02/27  22:00:17  CRH
- * Revision 2.0 of this program includes the following changes:
+ *   typedef struct ubi_btNodeStruct
+ *     {
+ *     struct ubi_btNodeStruct *leftlink
+ *     struct ubi_btNodeStruct *Link[2];
+ *     signed char              gender;
+ *     } ubi_btNode;
  *
- *     1)  A fix to a major typo in the RepaceNode() function.
- *     2)  The addition of the static function Border().
- *     3)  The addition of the public functions FirstOf() and LastOf(), which
- *         use Border(). These functions are used with trees that allow
- *         duplicate keys.
- *     4)  A complete rewrite of the Locate() function.  Locate() now accepts
- *         a "comparison" operator.
- *     5)  Overall enhancements to both code and comments.
+ * The leftlink field is used as a place holder, and the pointers are now
+ * index as
  *
- * I decided to give this a new major rev number because the interface has
- * changed.  In particular, there are two new functions, and changes to the
- * Locate() function.
+ *   Link[-1] == Left Child  (aka. leftlink)
+ *   Link[ 0] == Parent
+ *   Link[ 1] == Right Child
  *
- * Revision 1.0  93/10/15  22:44:59  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:
+ * which is much nicer.  Doing things this way removes the need to shift
+ * values between the two numbering schemes, thus removing one macro,
+ * simplifying another, and getting rid of a whole bunch of increment &
+ * decrement operations.
+ *
+ * Revision 2; 1995/02/27 - 1997/12/07 included:
+ *  - The addition of the ModuleID static string and ubi_ModuleID() function.
+ *  - The addition of the public functions FirstOf() and LastOf(). These
+ *    functions are used with trees that allow duplicate keys.
+ *  - The addition of the ubi_btLeafNode() function.
+ *  - A rewrite of the Locate() function.
+ *  - A change to the parameter list in function ubi_btInitTree().
+ *  - Bugfixes.
+ *
+ * Revision 1; 93/10/15 - 95/02/27:
+ * Revision 1 introduced a set of #define's that provide a single API to all
+ * of the existing tree modules.  Each of these modules has a different name
+ * 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".
+ * Only those portions of the base module (ubi_BinTree) that are superceeded
+ * in the descendant module have new names.  For example, the AVL node
+ * structure in ubi_AVLtree.h is named "ubi_avlNode", but the root structure
+ * is still "ubi_btRoot".  Using SplayTree, the locate function is 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.
+ * This is confusing.
  *
- * So, I have added a set of defined names that get redefined in any of the
+ * So, I 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
@@ -100,7 +104,8 @@
  * 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
+ * red/black trees, or if you plan to use two or more specific tree types
+ * in the same piece of code.  CRH
  *
  *  V0.0 - June, 1991   -  Written by Christopher R. Hertel (CRH).
  *
@@ -115,8 +120,8 @@
  */
 
 static char ModuleID[] = "ubi_BinTree\n\
-\tRevision: 2.4\n\
-\tDate: 1997/07/26 04:11:10\n\
+\tRevision: 3.0\n\
+\tDate: 1997/12/08 06:49:11\n\
 \tAuthor: crh\n";
 
 /* ========================================================================== **
@@ -129,7 +134,7 @@ static ubi_btNodePtr qFind( ubi_btCompFunc cmp,
   /* ------------------------------------------------------------------------ **
    * This function performs a non-recursive search of a tree for a node
    * matching a specific key.  It is called "qFind()" because it is
-   * faster that TreeFind (below).
+   * (probably a little bit) faster that TreeFind (below).
    *
    *  Input:
    *     cmp      -  a pointer to the tree's comparison function.
@@ -148,9 +153,9 @@ static ubi_btNodePtr qFind( ubi_btCompFunc cmp,
    * ------------------------------------------------------------------------ **
    */
   {
-  char tmp;
+  signed char tmp;
 
-  while( p && (( tmp = AbNormal((*cmp)(FindMe, p)) ) != EQUAL) )
+  while( p && (( tmp = ubi_trNormalize((*cmp)(FindMe, p)) ) != ubi_trEQUAL) )
     p = p->Link[tmp];
 
   return( p );
@@ -159,7 +164,7 @@ static ubi_btNodePtr qFind( ubi_btCompFunc cmp,
 static ubi_btNodePtr TreeFind( ubi_btItemPtr  findme,
                                ubi_btNodePtr  p,
                                ubi_btNodePtr *parentp,
-                               char          *gender,
+                               signed char   *gender,
                                ubi_btCompFunc CmpFunc )
   /* ------------------------------------------------------------------------ **
    * TreeFind() searches a tree for a given value (findme).  It will return a
@@ -189,25 +194,27 @@ static ubi_btNodePtr TreeFind( ubi_btItemPtr  findme,
    */
   {
   register ubi_btNodePtr tmp_p = p;
-  ubi_btNodePtr tmp_pp = NULL;
-  char tmp_sex = EQUAL;
-  char tmp_cmp;
+  ubi_btNodePtr tmp_pp         = NULL;
+  signed char   tmp_gender     = ubi_trEQUAL;
+  signed char   tmp_cmp;
 
-  while( tmp_p && (EQUAL != (tmp_cmp = AbNormal((*CmpFunc)(findme, tmp_p)))) )
+  while( tmp_p
+      && (ubi_trEQUAL != (tmp_cmp = ubi_trNormalize((*CmpFunc)(findme, tmp_p))))
+       )
     {
     tmp_pp  = tmp_p;                /* Keep track of previous node. */
-    tmp_sex = tmp_cmp;              /* Keep track of sex of child.  */
+    tmp_gender = tmp_cmp;           /* Keep track of sex of child.  */
     tmp_p = tmp_p->Link[tmp_cmp];   /* Go to child. */
     }
   *parentp = tmp_pp;                /* Return results. */
-  *gender  = tmp_sex;
+  *gender  = tmp_gender;
   return( tmp_p );
   } /* TreeFind */
 
 static void ReplaceNode( ubi_btNodePtr *parent,
                          ubi_btNodePtr  oldnode,
                          ubi_btNodePtr  newnode )
-  /* ------------------------------------------------------------------ *
+  /* ------------------------------------------------------------------------ **
    * Remove node oldnode from the tree, replacing it with node newnode.
    *
    * Input:
@@ -220,12 +227,8 @@ static void ReplaceNode( ubi_btNodePtr *parent,
    *             place of <*oldnode>.
    *
    * Notes:    Don't forget to free oldnode.
-   *           Also, this function used to have a really nasty typo
-   *           bug.  "oldnode" and "newnode" were swapped in the line
-   *           that now reads:
-   *     ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
-   *           Bleah!
-   * ------------------------------------------------------------------ *
+   *
+   * ------------------------------------------------------------------------ **
    */
   {
   register int i;
@@ -233,10 +236,17 @@ static void ReplaceNode( ubi_btNodePtr *parent,
 
   for( i = 0; i < btNodeSize; i++ ) /* Copy node internals to new node. */
     ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
-  (*parent) = newnode;              /* Old node's parent points to new child. */
+
+  /* Old node's parent points to new child. */
+  (*parent) = newnode;
+
   /* Now tell the children about their new step-parent. */
-  if( oldnode->Link[LEFT ] ) (oldnode->Link[LEFT ])->Link[PARENT] = newnode;
-  if( oldnode->Link[RIGHT] ) (oldnode->Link[RIGHT])->Link[PARENT] = newnode;
+  if( oldnode->Link[ubi_trLEFT ] )
+    (oldnode->Link[ubi_trLEFT ])->Link[ubi_trPARENT] = newnode;
+
+  if( oldnode->Link[ubi_trRIGHT] )
+    (oldnode->Link[ubi_trRIGHT])->Link[ubi_trPARENT] = newnode;
+
   } /* ReplaceNode */
 
 static void SwapNodes( ubi_btRootPtr RootPtr,
@@ -263,22 +273,22 @@ static void SwapNodes( ubi_btRootPtr RootPtr,
   ubi_btNodePtr  dummy_p = &dummy;
 
   /* Replace Node 1 with the dummy, thus removing Node1 from the tree. */
-  if( Node1->Link[PARENT] )
-    Parent = &((Node1->Link[PARENT])->Link[Node1->gender]);
+  if( Node1->Link[ubi_trPARENT] )
+    Parent = &((Node1->Link[ubi_trPARENT])->Link[Node1->gender]);
   else
     Parent = &(RootPtr->root);
   ReplaceNode( Parent, Node1, dummy_p );
 
   /* Swap Node 1 with Node 2, placing Node 1 back into the tree. */
-  if( Node2->Link[PARENT] )
-    Parent = &((Node2->Link[PARENT])->Link[Node2->gender]);
+  if( Node2->Link[ubi_trPARENT] )
+    Parent = &((Node2->Link[ubi_trPARENT])->Link[Node2->gender]);
   else
     Parent = &(RootPtr->root);
   ReplaceNode( Parent, Node2, Node1 );
 
   /* Swap Node 2 and the dummy, thus placing Node 2 back into the tree. */
-  if( dummy_p->Link[PARENT] )
-    Parent = &((dummy_p->Link[PARENT])->Link[dummy_p->gender]);
+  if( dummy_p->Link[ubi_trPARENT] )
+    Parent = &((dummy_p->Link[ubi_trPARENT])->Link[dummy_p->gender]);
   else
     Parent = &(RootPtr->root);
   ReplaceNode( Parent, dummy_p, Node2 );
@@ -289,7 +299,7 @@ static void SwapNodes( ubi_btRootPtr RootPtr,
  */
 
 static ubi_btNodePtr SubSlide( register ubi_btNodePtr P,
-                               register char  whichway )
+                               register signed char   whichway )
   /* ------------------------------------------------------------------------ **
    * Slide down the side of a subtree.
    *
@@ -317,7 +327,7 @@ static ubi_btNodePtr SubSlide( register ubi_btNodePtr P,
   } /* SubSlide */
 
 static ubi_btNodePtr Neighbor( register ubi_btNodePtr P,
-                               register char  whichway )
+                               register signed char   whichway )
   /* ------------------------------------------------------------------------ **
    * Given starting point p, return the (key order) next or preceeding node
    * in the tree.
@@ -336,14 +346,14 @@ static ubi_btNodePtr Neighbor( register ubi_btNodePtr P,
   if( P )
     {
     if( P->Link[ whichway ] )
-      return( SubSlide( P->Link[ whichway ], (char)RevWay(whichway) ) );
+      return( SubSlide( P->Link[ whichway ], ubi_trRevWay(whichway) ) );
     else
-      while( P->Link[ PARENT ] )
+      while( P->Link[ ubi_trPARENT ] )
         {
-        if( (P->Link[ PARENT ])->Link[ whichway ] == P )
-          P = P->Link[ PARENT ];
+        if( (P->Link[ ubi_trPARENT ])->Link[ whichway ] == P )
+          P = P->Link[ ubi_trPARENT ];
         else
-          return( P->Link[ PARENT ] );
+          return( P->Link[ ubi_trPARENT ] );
         }
     }
   return( NULL );
@@ -352,7 +362,7 @@ static ubi_btNodePtr Neighbor( register ubi_btNodePtr P,
 static ubi_btNodePtr Border( ubi_btRootPtr RootPtr,
                              ubi_btItemPtr FindMe,
                              ubi_btNodePtr p,
-                             char          whichway )
+                             signed char   whichway )
   /* ------------------------------------------------------------------------ **
    * Given starting point p, which has a key value equal to *FindMe, locate
    * the first (index order) node with the same key value.
@@ -384,17 +394,17 @@ static ubi_btNodePtr Border( ubi_btRootPtr RootPtr,
   register ubi_btNodePtr q;
 
   /* Exit if there's nothing that can be done. */
-  if( !Dups_OK( RootPtr ) || (PARENT == whichway) )
+  if( !ubi_trDups_OK( RootPtr ) || (ubi_trPARENT == whichway) )
     return( p );
 
   /* First, if needed, move up the tree.  We need to get to the root of the
    * subtree that contains all of the matching nodes.
    */
-  q = p->Link[PARENT];
-  while( q && (EQUAL == AbNormal( (*(RootPtr->cmp))(FindMe, q) )) )
+  q = p->Link[ubi_trPARENT];
+  while( q && (ubi_trEQUAL == ubi_trNormalize( (*(RootPtr->cmp))(FindMe, q) )) )
     {
     p = q;
-    q = p->Link[PARENT];
+    q = p->Link[ubi_trPARENT];
     }
 
   /* Next, move back down in the "whichway" direction. */
@@ -421,15 +431,15 @@ long ubi_btSgn( register long x )
    *
    *  Input:  x - a signed long integer value.
    *
-   *  Output: the "sign" of x, represented as follows:
+   *  Output: -1, 0, or 1 representing the "sign" of x as follows:
    *            -1 == negative
    *             0 == zero (no sign)
    *             1 == positive
    *
-   * Note: This utility is provided in order to facilitate the conversion
-   *       of C comparison function return values into BinTree direction
-   *       values: {LEFT, PARENT, EQUAL}.  It is INCORPORATED into the
-   *       AbNormal() conversion macro!
+   * Note:    This utility is provided in order to facilitate the conversion
+   *          of C comparison function return values into BinTree direction
+   *          values: {ubi_trLEFT, ubi_trPARENT, ubi_trEQUAL}.  It is
+   *          incorporated into the ubi_trNormalize() conversion macro.
    *
    * ------------------------------------------------------------------------ **
    */
@@ -447,10 +457,10 @@ ubi_btNodePtr ubi_btInitNode( ubi_btNodePtr NodePtr )
    * ------------------------------------------------------------------------ **
    */
   {
-  NodePtr->Link[ LEFT ]   = NULL;
-  NodePtr->Link[ PARENT ] = NULL;
-  NodePtr->Link[ RIGHT ]  = NULL;
-  NodePtr->gender         = EQUAL;
+  NodePtr->Link[ ubi_trLEFT ]   = NULL;
+  NodePtr->Link[ ubi_trPARENT ] = NULL;
+  NodePtr->Link[ ubi_trRIGHT ]  = NULL;
+  NodePtr->gender               = ubi_trEQUAL;
   return( NodePtr );
   } /* ubi_btInitNode */
 
@@ -543,7 +553,7 @@ ubi_trBool ubi_btInsert( ubi_btRootPtr  RootPtr,
   {
   ubi_btNodePtr OtherP,
                 parent = NULL;
-  char          tmp;
+  signed char   tmp;
 
   if( !(OldNode) )       /* If they didn't give us a pointer, supply our own. */
     OldNode = &OtherP;
@@ -560,9 +570,9 @@ ubi_trBool ubi_btInsert( ubi_btRootPtr  RootPtr,
       RootPtr->root = NewNode;
     else
       {
-      parent->Link[tmp]     = NewNode;
-      NewNode->Link[PARENT] = parent;
-      NewNode->gender       = tmp;
+      parent->Link[tmp]           = NewNode;
+      NewNode->Link[ubi_trPARENT] = parent;
+      NewNode->gender             = tmp;
       }
     (RootPtr->count)++;
     return( ubi_trTRUE );
@@ -571,24 +581,25 @@ ubi_trBool ubi_btInsert( ubi_btRootPtr  RootPtr,
   /* If we reach this point, we know that a duplicate node exists.  This
    * section adds the node to the tree if duplicate keys are allowed.
    */
-  if( Dups_OK(RootPtr) )    /* Key exists, add duplicate */
+  if( ubi_trDups_OK(RootPtr) )    /* Key exists, add duplicate */
     {
     ubi_btNodePtr q;
 
-    tmp = RIGHT;
+    tmp = ubi_trRIGHT;
     q = (*OldNode);
     *OldNode = NULL;
     while( q )
       {
       parent = q;
-      if( tmp == EQUAL ) tmp = RIGHT;
+      if( tmp == ubi_trEQUAL )
+        tmp = ubi_trRIGHT;
       q = q->Link[tmp];
       if ( q )
-        tmp = AbNormal( (*(RootPtr->cmp))(ItemPtr, q) );
+        tmp = ubi_trNormalize( (*(RootPtr->cmp))(ItemPtr, q) );
       }
-    parent->Link[tmp]      = NewNode;
-    NewNode->Link[PARENT]  = parent;
-    NewNode->gender        = tmp;
+    parent->Link[tmp]            = NewNode;
+    NewNode->Link[ubi_trPARENT]  = parent;
+    NewNode->gender              = tmp;
     (RootPtr->count)++;
     return( ubi_trTRUE );
     }
@@ -597,7 +608,7 @@ ubi_trBool ubi_btInsert( ubi_btRootPtr  RootPtr,
    * duplicate nodes, but our node keys match, so... may we replace the
    * old one?
    */
-  if( Ovwt_OK(RootPtr) )    /* Key exists, we replace */
+  if( ubi_trOvwt_OK(RootPtr) )    /* Key exists, we replace */
     {
     if (!(parent))
       ReplaceNode( &(RootPtr->root), *OldNode, NewNode );
@@ -628,32 +639,32 @@ ubi_btNodePtr ubi_btRemove( ubi_btRootPtr RootPtr,
   {
   ubi_btNodePtr p,
                *parentp;
-  char          tmp;
+  signed char   tmp;
 
   /* if the node has both left and right subtrees, then we have to swap
    * it with another node.  The other node we choose will be the Prev()ious
    * node, which is garunteed to have no RIGHT child.
    */
-  if( (DeadNode->Link[LEFT]) && (DeadNode->Link[RIGHT]) )
+  if( (DeadNode->Link[ubi_trLEFT]) && (DeadNode->Link[ubi_trRIGHT]) )
     SwapNodes( RootPtr, DeadNode, ubi_btPrev( 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 = &((DeadNode->Link[PARENT])->Link[DeadNode->gender]);
+  if (DeadNode->Link[ubi_trPARENT])
+    parentp = &((DeadNode->Link[ubi_trPARENT])->Link[DeadNode->gender]);
   else
     parentp = &( RootPtr->root );
 
   /* Now link the parent to the only grand-child and patch up the gender. */
-  tmp = ((DeadNode->Link[LEFT])?LEFT:RIGHT);
+  tmp = ((DeadNode->Link[ubi_trLEFT]) ? ubi_trLEFT : ubi_trRIGHT);
 
   p = (DeadNode->Link[tmp]);
   if( p )
     {
-    p->Link[PARENT] = DeadNode->Link[PARENT];
-    p->gender       = DeadNode->gender;
+    p->Link[ubi_trPARENT] = DeadNode->Link[ubi_trPARENT];
+    p->gender             = DeadNode->gender;
     }
   (*parentp) = p;
 
@@ -716,7 +727,7 @@ ubi_btNodePtr ubi_btLocate( ubi_btRootPtr RootPtr,
   {
   register ubi_btNodePtr p;
   ubi_btNodePtr   parent;
-  char            whichkid;
+  signed char     whichkid;
 
   /* Start by searching for a matching node. */
   p = TreeFind( FindMe,
@@ -730,13 +741,13 @@ ubi_btNodePtr ubi_btLocate( ubi_btRootPtr RootPtr,
     switch( CompOp )
       {
       case ubi_trLT:            /* It's just a jump to the left...  */
-        p = Border( RootPtr, FindMe, p, LEFT );
-        return( Neighbor( p, LEFT ) );
+        p = Border( RootPtr, FindMe, p, ubi_trLEFT );
+        return( Neighbor( p, ubi_trLEFT ) );
       case ubi_trGT:            /* ...and then a jump to the right. */
-        p = Border( RootPtr, FindMe, p, RIGHT );
-        return( Neighbor( p, RIGHT ) );
+        p = Border( RootPtr, FindMe, p, ubi_trRIGHT );
+        return( Neighbor( p, ubi_trRIGHT ) );
       }
-    p = Border( RootPtr, FindMe, p, LEFT );
+    p = Border( RootPtr, FindMe, p, ubi_trLEFT );
     return( p );
     }
 
@@ -750,9 +761,9 @@ ubi_btNodePtr ubi_btLocate( ubi_btRootPtr RootPtr,
    * Remaining possibilities are LT and GT (including LE & GE).
    */
   if( (ubi_trLT == CompOp) || (ubi_trLE == CompOp) )
-    return( (LEFT  == whichkid) ? Neighbor( parent, whichkid ) : parent );
+    return( (ubi_trLEFT  == whichkid) ? Neighbor( parent, whichkid ) : parent );
   else
-    return( (RIGHT == whichkid) ? Neighbor( parent, whichkid ) : parent );
+    return( (ubi_trRIGHT == whichkid) ? Neighbor( parent, whichkid ) : parent );
   } /* ubi_btLocate */
 
 ubi_btNodePtr ubi_btFind( ubi_btRootPtr RootPtr,
@@ -789,7 +800,7 @@ ubi_btNodePtr ubi_btNext( ubi_btNodePtr P )
    * ------------------------------------------------------------------------ **
    */
   {
-  return( Neighbor( P, RIGHT ) );
+  return( Neighbor( P, ubi_trRIGHT ) );
   } /* ubi_btNext */
 
 ubi_btNodePtr ubi_btPrev( ubi_btNodePtr P )
@@ -802,7 +813,7 @@ ubi_btNodePtr ubi_btPrev( ubi_btNodePtr P )
    * ------------------------------------------------------------------------ **
    */
   {
-  return( Neighbor( P, LEFT ) );
+  return( Neighbor( P, ubi_trLEFT ) );
   } /* ubi_btPrev */
 
 ubi_btNodePtr ubi_btFirst( ubi_btNodePtr P )
@@ -817,7 +828,7 @@ ubi_btNodePtr ubi_btFirst( ubi_btNodePtr P )
    * ------------------------------------------------------------------------ **
    */
   {
-  return( SubSlide( P, LEFT ) );
+  return( SubSlide( P, ubi_trLEFT ) );
   } /* ubi_btFirst */
 
 ubi_btNodePtr ubi_btLast( ubi_btNodePtr P )
@@ -832,7 +843,7 @@ ubi_btNodePtr ubi_btLast( ubi_btNodePtr P )
    * ------------------------------------------------------------------------ **
    */
   {
-  return( SubSlide( P, RIGHT ) );
+  return( SubSlide( P, ubi_trRIGHT ) );
   } /* ubi_btLast */
 
 ubi_btNodePtr ubi_btFirstOf( ubi_btRootPtr RootPtr,
@@ -855,9 +866,9 @@ ubi_btNodePtr ubi_btFirstOf( ubi_btRootPtr RootPtr,
    */
   {
   /* If our starting point is invalid, return NULL. */
-  if( !p || AbNormal( (*(RootPtr->cmp))( MatchMe, p ) != EQUAL ) )
+  if( !p || ubi_trNormalize( (*(RootPtr->cmp))( MatchMe, p ) != ubi_trEQUAL ) )
     return( NULL );
-  return( Border( RootPtr, MatchMe, p, LEFT ) );
+  return( Border( RootPtr, MatchMe, p, ubi_trLEFT ) );
   } /* ubi_btFirstOf */
 
 ubi_btNodePtr ubi_btLastOf( ubi_btRootPtr RootPtr,
@@ -880,9 +891,9 @@ ubi_btNodePtr ubi_btLastOf( ubi_btRootPtr RootPtr,
    */
   {
   /* If our starting point is invalid, return NULL. */
-  if( !p || AbNormal( (*(RootPtr->cmp))( MatchMe, p ) != EQUAL ) )
+  if( !p || ubi_trNormalize( (*(RootPtr->cmp))( MatchMe, p ) != ubi_trEQUAL ) )
     return( NULL );
-  return( Border( RootPtr, MatchMe, p, RIGHT ) );
+  return( Border( RootPtr, MatchMe, p, ubi_trRIGHT ) );
   } /* ubi_btLastOf */
 
 ubi_trBool ubi_btTraverse( ubi_btRootPtr   RootPtr,
@@ -941,11 +952,11 @@ ubi_trBool ubi_btKillTree( ubi_btRootPtr     RootPtr,
   while( p )
     {
     q = p;
-    while( q->Link[RIGHT] )
-      q = SubSlide( q->Link[RIGHT], LEFT );
-    p = q->Link[PARENT];
+    while( q->Link[ubi_trRIGHT] )
+      q = SubSlide( q->Link[ubi_trRIGHT], ubi_trLEFT );
+    p = q->Link[ubi_trPARENT];
     if( p )
-      p->Link[ ((p->Link[LEFT] == q)?LEFT:RIGHT) ] = NULL;
+      p->Link[ ((p->Link[ubi_trLEFT] == q)?ubi_trLEFT:ubi_trRIGHT) ] = NULL;
     FreeNode((void *)q);
     }
 
@@ -979,20 +990,24 @@ ubi_btNodePtr ubi_btLeafNode( ubi_btNodePtr leader )
    *          in pointers to nodes other than the root node each time.  A
    *          pointer to any node in the tree will do.  Of course, if you
    *          pass a pointer to a leaf node you'll get the same thing back.
+   *        + If using a splay tree, splaying the tree will tend to randomize
+   *          things a bit too.  See ubi_SplayTree for more info.
    *
    * ------------------------------------------------------------------------ **
    */
   {
   ubi_btNodePtr follower = NULL;
-  int           whichway = LEFT;
+  int           whichway = ubi_trLEFT;
 
   while( NULL != leader )
     {
+    /* The next line is a weak attempt at randomizing. */
+    whichway = ((int)leader & 0x0010) ? whichway : ubi_trRevWay(whichway);
     follower = leader;
-    leader   = follower->Link[ whichway ];
+    leader   = leader->Link[ whichway ];
     if( NULL == leader )
       {
-      whichway = RevWay( whichway );
+      whichway = ubi_trRevWay( whichway );
       leader   = follower->Link[ whichway ];
       }
     }
@@ -1028,5 +1043,4 @@ int ubi_btModuleID( int size, char *list[] )
   return( 0 );
   } /* ubi_btModuleID */
 
-
 /* ========================================================================== */
diff --git a/source3/ubiqx/ubi_BinTree.h b/source3/ubiqx/ubi_BinTree.h
index ee512989f9..d5032b58a2 100644
--- a/source3/ubiqx/ubi_BinTree.h
+++ b/source3/ubiqx/ubi_BinTree.h
@@ -8,12 +8,7 @@
  *  Email:  crh@ubiqx.mn.org
  * -------------------------------------------------------------------------- **
  *
- *  ubi_BinTree manages a simple binary tree.  Nothing fancy here.  No height
- *  balancing, no restructuring.  Still, a good tool for creating short, low-
- *  overhead sorted lists of things that need to be found in a hurry.
- *
- *  In addition, this module provides a good basis for creating other types
- *  of binary tree handling modules.
+ *  This module implements simple binary trees.
  *
  * -------------------------------------------------------------------------- **
  *
@@ -33,64 +28,73 @@
  *
  * -------------------------------------------------------------------------- **
  *
- * Revision 2.4  1997/07/26 04:11:14  crh
- * + Just to be annoying I changed ubi_TRUE and ubi_FALSE to ubi_trTRUE
- *   and ubi_trFALSE.
- * + There is now a type ubi_trBool to go with ubi_trTRUE and ubi_trFALSE.
- * + There used to be something called "ubi_TypeDefs.h".  I got rid of it.
- * + Added function ubi_btLeafNode().
- *
- * Revision 2.3  1997/06/03 05:15:27  crh
- * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid conflicts.
- * Also changed the interface to function InitTree().  See the comments
- * for this function for more information.
- *
- * Revision 2.2  1995/10/03 22:00:40  CRH
- * Ubisized!
- * 
- * Revision 2.1  95/03/09  23:43:46  CRH
- * Added the ModuleID static string and function.  These modules are now
- * self-identifying.
- * 
- * Revision 2.0  95/02/27  22:00:33  CRH
- * Revision 2.0 of this program includes the following changes:
- *
- *     1)  A fix to a major typo in the RepaceNode() function.
- *     2)  The addition of the static function Border().
- *     3)  The addition of the public functions FirstOf() and LastOf(), which
- *         use Border(). These functions are used with trees that allow
- *         duplicate keys.
- *     4)  A complete rewrite of the Locate() function.  Locate() now accepts
- *         a "comparison" operator.
- *     5)  Overall enhancements to both code and comments.
- *
- * I decided to give this a new major rev number because the interface has
- * changed.  In particular, there are two new functions, and changes to the
- * Locate() function.
- *
- * Revision 1.0  93/10/15  22:55:04  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:
+ * Log: ubi_BinTree.h,v
+ * Revision 3.0  1997/12/08 06:49:15  crh
+ * This is a new major revision level for all ubiqx binary tree modules.
+ * In previous releases, the ubi_trNode structure looked like this:
+ *
+ *   typedef struct ubi_btNodeStruct
+ *     {
+ *     struct ubi_btNodeStruct *Link[3];
+ *     signed char              gender;
+ *     } ubi_btNode;
+ *
+ * As a result, the pointers were indexed as
+ *
+ *   Link[0] == Left Child
+ *   Link[1] == Parent
+ *   Link[2] == Right Child
+ *
+ * With this release, the node structure changes to:
+ *
+ *   typedef struct ubi_btNodeStruct
+ *     {
+ *     struct ubi_btNodeStruct *leftlink
+ *     struct ubi_btNodeStruct *Link[2];
+ *     signed char              gender;
+ *     } ubi_btNode;
+ *
+ * The leftlink field is used as a place holder, and the pointers are now
+ * index as
+ *
+ *   Link[-1] == Left Child  (aka. leftlink)
+ *   Link[ 0] == Parent
+ *   Link[ 1] == Right Child
+ *
+ * which is much nicer.  Doing things this way removes the need to shift
+ * values between the two numbering schemes, thus removing one macro,
+ * simplifying another, and getting rid of a whole bunch of increment &
+ * decrement operations.
+ *
+ * Revision 2; 1995/02/27 - 1997/12/07 included:
+ *  - The addition of the ModuleID static string and ubi_ModuleID() function.
+ *  - The addition of the public functions FirstOf() and LastOf(). These
+ *    functions are used with trees that allow duplicate keys.
+ *  - The addition of the ubi_btLeafNode() function.
+ *  - A rewrite of the Locate() function.
+ *  - A change to the parameter list in function ubi_btInitTree().
+ *  - Bugfixes.
+ *
+ * Revision 1; 93/10/15 - 95/02/27:
+ * Revision 1 introduced a set of #define's that provide a single API to all
+ * of the existing tree modules.  Each of these modules has a different name
+ * 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".
+ * Only those portions of the base module (ubi_BinTree) that are superceeded
+ * in the descendant module have new names.  For example, the AVL node
+ * structure in ubi_AVLtree.h is named "ubi_avlNode", but the root structure
+ * is still "ubi_btRoot".  Using SplayTree, the locate function is 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.
+ * This is confusing.
  *
- * So, I have added a set of defined names that get redefined in any of the
+ * So, I 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
@@ -102,7 +106,8 @@
  * 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
+ * red/black trees, or if you plan to use two or more specific tree types
+ * in the same piece of code.  CRH
  *
  *  V0.0 - June, 1991   -  Written by Christopher R. Hertel (CRH).
  *
@@ -110,7 +115,7 @@
  */
 
 /* -------------------------------------------------------------------------- **
- * Macros and constants.
+ * Constants...
  *
  *  General purpose:
  *    ubi_trTRUE  - Boolean TRUE.
@@ -120,16 +125,16 @@
  *    ubi_trOVERWRITE   - This flag indicates that an existing node may be
  *                        overwritten by a new node with a matching key.
  *    ubi_trDUPKEY      - This flag indicates that the tree allows duplicate
- *                        keys.  If the tree does allow duplicates, the
- *                        overwrite flag is ignored.
+ *                        keys.  If the tree allows duplicates, the overwrite
+ *                        flag is ignored.
  *
- *  Node link array index constants:  (Each node has an array of three
- *  pointers.  One to the left, one to the right, and one back to the
- *  parent.)
- *    LEFT    - Left child pointer.
- *    PARENT  - Parent pointer.
- *    RIGHT   - Right child pointer.
- *    EQUAL   - Synonym for PARENT.
+ *  Node link array index constants:
+ *    (Each node has an array of three pointers; pointer to the left child,
+ *    pointer to the right child, and a pointer back to the parent node.)
+ *      ubi_trLEFT    - Left child pointer.
+ *      ubi_trPARENT  - Parent pointer.
+ *      ubi_trRIGHT   - Right child pointer.
+ *      ubi_trEQUAL   - Synonym for PARENT.
  *
  *  ubi_trCompOps:  These values are used in the ubi_trLocate() function.
  *    ubi_trLT  - request the first instance of the greatest key less than
@@ -142,7 +147,6 @@
  *                or equal to the search key.
  *    ubi_trGT  - request the first instance of the first key that is greater
  *                than the search key.
- * -------------------------------------------------------------------------- **
  */
 
 #define ubi_trTRUE  0xFF
@@ -152,12 +156,13 @@
 #define ubi_trDUPKEY    0x02        /* Turn on allow duplicate keys */
 
 /* Pointer array index constants... */
-#define LEFT   0x00
-#define PARENT 0x01
-#define RIGHT  0x02
-#define EQUAL  PARENT
+#define ubi_trLEFT   -1
+#define ubi_trPARENT  0
+#define ubi_trRIGHT   1
+#define ubi_trEQUAL   ubi_trPARENT
 
-typedef enum {
+typedef enum
+  {
   ubi_trLT = 1,
   ubi_trLE,
   ubi_trEQ,
@@ -166,57 +171,57 @@ typedef enum {
   } ubi_trCompOps;
 
 /* -------------------------------------------------------------------------- **
- * These three macros allow simple manipulation of pointer index values (LEFT,
- * RIGHT, and PARENT).
- *
- *    Normalize() -  converts {LEFT, PARENT, RIGHT} into {-1, 0 ,1}.  C
- *                   uses {negative, zero, positive} values to indicate
- *                   {less than, equal to, greater than}.
- *    AbNormal()  -  converts {negative, zero, positive} to {LEFT, PARENT,
- *                   RIGHT} (opposite of Normalize()).  Note: C comparison
- *                   functions, such as strcmp(), return {negative, zero,
- *                   positive} values, which are not necessarily {-1, 0,
- *                   1}.  This macro uses the the ubi_btSgn() function to
- *                   compensate.
- *    RevWay()    -  converts LEFT to RIGHT and RIGHT to LEFT.  PARENT (EQUAL)
- *                   is left as is.
- * -------------------------------------------------------------------------- **
+ * Macros...
+ *  ubi_trNormalize() - "Normalize" a value with respect to ubi_trLEFT,
+ *                      ubi_trRIGHT, and ubi_trPARENT.  This macro calls
+ *                      ubi_btSgn() to convert the input to -1, 0, or 1.
+ *                      The resultant value is returned as a signed char.
+ *
+ *  ubi_trRevWay()    - converts ubi_trLEFT to ubi_trRIGHT and vice versa.
+ *                      ubi_trPARENT (ubi_trEQUAL) is left as is.
+ *
+ *  ubi_trDups_OK()   - returns TRUE if the tree allows duplicates.
+ *
+ *  ubi_trOvwt_OK()   - returns TRUE if the overwrite flag is on.  Note
+ *                      that overwrites will not occur in a tree that
+ *                      allows duplicates.
  */
-#define Normalize(W) ((char)((W)-EQUAL))
-#define AbNormal(W) ((char)( EQUAL+((char)ubi_btSgn( (W) )) ))
-#define RevWay(W) ((char)((W)==LEFT?RIGHT:((W)==RIGHT?LEFT:EQUAL)))
 
-/* -------------------------------------------------------------------------- **
- * These macros allow us to quickly read the values of the OVERWRITE and
- * DUPlicate KEY bits of the tree root flags field.
- * -------------------------------------------------------------------------- **
- */
-#define Dups_OK(A) ((ubi_trDUPKEY & ((A)->flags))?(ubi_trTRUE):(ubi_trFALSE))
-#define Ovwt_OK(A) ((ubi_trOVERWRITE & ((A)->flags))?(ubi_trTRUE):(ubi_trFALSE))
+#define ubi_trNormalize(W) ((signed char)ubi_btSgn(W))
+#define ubi_trRevWay(W) (-(W))
+
+#define ubi_trDups_OK(A) \
+        ((ubi_trDUPKEY & ((A)->flags))   ? (ubi_trTRUE) : (ubi_trFALSE))
+#define ubi_trOvwt_OK(A) \
+        ((ubi_trOVERWRITE & ((A)->flags))? (ubi_trTRUE) : (ubi_trFALSE))
+
 
 /* -------------------------------------------------------------------------- **
  * Typedefs...
  * 
- * ubi_trBool   - Your typcial true or false...
+ * ubi_trBool     - Your typcial true or false...
  *
- * Item Pointer:  The ubi_btItemPtr is a generic pointer. It is used to
- *                indicate a key that is being searched for within the tree.
- *                Searching occurs whenever the ubi_trFind(), ubi_trLocate(),
- *                or ubi_trInsert() functions are called.
- * -------------------------------------------------------------------------- **
+ * ubi_btItemPtr  - The Item Pointer is a generic pointer.  It is used to
+ *                  indicate a key for which to search within the tree.
+ *                  The ubi_trFind(), ubi_trLocate(), and  ubi_trInsert()
+ *                  functions all perform searches.
  */
 
-typedef unsigned char ubi_trBool;
+typedef unsigned char ubi_trBool;   /* Our own name for "boolean".            */
 
-typedef void *ubi_btItemPtr;              /* A pointer to data within a node. */
+typedef void *ubi_btItemPtr;        /* A pointer to (key) data within a node. */
 
-/*  ------------------------------------------------------------------------- **
+/* -------------------------------------------------------------------------- **
+ * Typedefs continued...
+ *
  *  Binary Tree Node Structure:  This structure defines the basic elements of
  *       the tree nodes.  In general you *SHOULD NOT PLAY WITH THESE FIELDS*!
  *       But, of course, I have to put the structure into this header so that
  *       you can use it as a building block.
  *
  *  The fields are as follows:
+ *    leftlink -  pointer to the left child of the node.  This field will
+ *                be accessed as Link[-1].
  *    Link     -  an array of pointers.  These pointers are manipulated by
  *                the BT routines.  The pointers indicate the left and right
  *                child nodes and the parent node.  By keeping track of the
@@ -227,18 +232,22 @@ typedef void *ubi_btItemPtr;              /* A pointer to data within a node. */
  *    gender   -  a one-byte field indicating whether the node is the RIGHT or
  *                LEFT child of its parent.  If the node is the root of the
  *                tree, gender will be PARENT.
- *  ------------------------------------------------------------------------- **
  */
-typedef struct ubi_btNodeStruct {
-  struct ubi_btNodeStruct *Link[ 3 ];
-  char                     gender;
+
+typedef struct ubi_btNodeStruct
+  {
+  struct ubi_btNodeStruct *leftlink;    /* Will be accessed as Link[-1].      */
+  struct ubi_btNodeStruct *Link[2];     /* Parent & Right links.              */
+  signed char              gender;      /* Indicates Left/Right of parent.    */
   } ubi_btNode;
 
 typedef ubi_btNode *ubi_btNodePtr;     /* Pointer to an ubi_btNode structure. */
 
-/*  ------------------------------------------------------------------------- **
- * The next three typedefs define standard function types used by the binary
- * tree management routines.  In particular:
+/* -------------------------------------------------------------------------- **
+ * Typedefs continued...
+ *
+ *  The next three typedefs define standard function types used by the binary
+ *  tree management routines.  In particular:
  *
  *    ubi_btCompFunc    is a pointer to a comparison function.  Comparison
  *                      functions are passed an ubi_btItemPtr and an
@@ -258,7 +267,6 @@ typedef ubi_btNode *ubi_btNodePtr;     /* Pointer to an ubi_btNode structure. */
  *                      mean anything that you want it to mean.  Just remember
  *                      that the tree *will* be destroyed and that none of the
  *                      node pointers will be valid any more.
- *  ------------------------------------------------------------------------- **
  */
 
 typedef  int (*ubi_btCompFunc)( ubi_btItemPtr, ubi_btNodePtr );
@@ -268,8 +276,10 @@ typedef void (*ubi_btActionRtn)( ubi_btNodePtr, void * );
 typedef void (*ubi_btKillNodeRtn)( ubi_btNodePtr );
 
 /* -------------------------------------------------------------------------- **
- * Tree Root Structure: This structure gives us a convenient handle for
- *                      accessing whole AVL trees.  The fields are:
+ * Typedefs continued...
+ *
+ *  Tree Root Structure: This structure gives us a convenient handle for
+ *                       accessing whole AVL trees.  The fields are:
  *    root  -  A pointer to the root node of the AVL tree.
  *    count -  A count of the number of nodes stored in the tree.
  *    cmp   -  A pointer to the comparison routine to be used when building or
@@ -283,13 +293,15 @@ typedef void (*ubi_btKillNodeRtn)( ubi_btNodePtr );
  *         (bit 0x02)       allowed to contain nodes with duplicate keys.
  *
  *       NOTE: ubi_trInsert() tests ubi_trDUPKEY before ubi_trOVERWRITE.
+ *             If duplicate keys are allowed, then no entry will be
+ *             overwritten.
  *
- * All of these values are set when you initialize the root structure by
- * calling ubi_trInitTree().
- * -------------------------------------------------------------------------- **
+ *  All of these values are set when you initialize the root structure by
+ *  calling ubi_trInitTree().
  */
 
-typedef struct {
+typedef struct
+  {
   ubi_btNodePtr  root;     /* A pointer to the root node of the tree       */
   unsigned long  count;    /* A count of the number of nodes in the tree   */
   ubi_btCompFunc cmp;      /* A pointer to the tree's comparison function  */
@@ -309,15 +321,15 @@ long ubi_btSgn( long x );
    *
    *  Input:  x - a signed long integer value.
    *
-   *  Output: the "sign" of x, represented as follows:
+   *  Output: -1, 0, or 1 representing the "sign" of x as follows:
    *            -1 == negative
    *             0 == zero (no sign)
    *             1 == positive
    *
-   * Note: This utility is provided in order to facilitate the conversion
-   *       of C comparison function return values into BinTree direction
-   *       values: {LEFT, PARENT, EQUAL}.  It is INCORPORATED into the
-   *       AbNormal() conversion macro!
+   *  Notes:  This utility is provided in order to facilitate the conversion
+   *          of C comparison function return values into BinTree direction
+   *          values: {ubi_trLEFT, ubi_trPARENT, ubi_trEQUAL}.  It is
+   *          incorporated into the Normalize() conversion macro.
    *
    * ------------------------------------------------------------------------ **
    */
@@ -332,9 +344,9 @@ ubi_btNodePtr ubi_btInitNode( ubi_btNodePtr NodePtr );
    * ------------------------------------------------------------------------ **
    */
 
-ubi_btRootPtr  ubi_btInitTree( ubi_btRootPtr   RootPtr,
-                               ubi_btCompFunc  CompFunc,
-                               unsigned char   Flags );
+ubi_btRootPtr ubi_btInitTree( ubi_btRootPtr   RootPtr,
+                              ubi_btCompFunc  CompFunc,
+                              unsigned char   Flags );
   /* ------------------------------------------------------------------------ **
    * Initialize the fields of a Tree Root header structure.
    *  
@@ -636,6 +648,8 @@ ubi_btNodePtr ubi_btLeafNode( ubi_btNodePtr leader );
    *          in pointers to nodes other than the root node each time.  A
    *          pointer to any node in the tree will do.  Of course, if you
    *          pass a pointer to a leaf node you'll get the same thing back.
+   *        + If using a splay tree, splaying the tree will tend to randomize
+   *          things a bit too.  See ubi_SplayTree for more info.
    *
    * ------------------------------------------------------------------------ **
    */
diff --git a/source3/ubiqx/ubi_SplayTree.c b/source3/ubiqx/ubi_SplayTree.c
index 88be2ba9f4..fb4cc9f7c8 100644
--- a/source3/ubiqx/ubi_SplayTree.c
+++ b/source3/ubiqx/ubi_SplayTree.c
@@ -34,73 +34,17 @@
  *
  * -------------------------------------------------------------------------- **
  *
- * Revision 2.5  1997/07/26 04:15:42  crh
- * + Cleaned up a few minor syntax annoyances that gcc discovered for me.
- * + Changed ubi_TRUE and ubi_FALSE to ubi_trTRUE and ubi_trFALSE.
+ * Log: ubi_SplayTree.c,v
+ * Revision 3.0  1997/12/08 05:32:28  crh
+ * This is a new major revision level because of a redesign of the handling
+ * of the pointers in the ubi_trNode structure.  See ubi_BinTree for more
+ * info.
  *
- * Revision 2.4  1997/06/03 04:42:21  crh
- * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing
- * problems.
+ * Revision 2;  1995/02/27 - 1997/12/07:
+ * Major changes: added the function ubi_sptSplay().
  *
- * Revision 2.3  1995/10/03 22:19:07  CRH
- * Ubisized!
- * Also, added the function ubi_sptSplay().
- *
- * Revision 2.1  95/03/09  23:54:42  CRH
- * Added the ModuleID static string and function.  These modules are now
- * self-identifying.
- * 
- * Revision 2.0  95/02/27  22:34:46  CRH
- * This module was updated to match the interface changes made to the
- * ubi_BinTree module.  In particular, the interface to the Locate() function
- * has changed.  See ubi_BinTree for more information on changes and new
- * functions.
- *
- * The revision number was also upped to match ubi_BinTree.
- *
- * Revision 1.1  93/10/18  20:35:16  CRH
- * I removed the hard-coded logical device names from the include file
- * specifications.  CRH
- *
- * Revision 1.0  93/10/15  23:00:15  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
- *
- * Revision 0.1  93/04/25  22:03:32  CRH
- * Simply changed the <exec/types.h> #include reference the .c file to
- * use <stdlib.h> instead.  The latter is portable, the former is not.
+ * Revision 1; 93/10/15 - 95/02/27:
+ * Added the ubi_tr defines.  See ubi_BinTree.h for more info.
  *
  * Revision 0.0  93/04/21  23:05:52  CRH
  * Initial version, written by Christopher R. Hertel.
@@ -117,8 +61,8 @@
  */
 
 static char ModuleID[] = "ubi_SplayTree\n\
-\tRevision: 2.5\n\
-\tDate: 1997/07/26 04:15:42\n\
+\tRevision: 3.0\n\
+\tDate: 1997/12/08 05:32:28\n\
 \tAuthor: crh\n";
 
 
@@ -143,33 +87,33 @@ static void Rotate( ubi_btNodePtr p )
   {
   ubi_btNodePtr parentp;
   ubi_btNodePtr tmp;
-  char          way;
-  char          revway;
+  signed char   way;
+  signed char   revway;
 
-  parentp = p->Link[PARENT];    /* Find parent. */
+  parentp = p->Link[ubi_trPARENT];    /* Find parent. */
 
   if( parentp )                 /* If no parent, then we're already the root. */
     {
     way     = p->gender;
-    revway  = RevWay(way);
+    revway  = ubi_trRevWay(way);
     tmp     = p->Link[revway];
 
     parentp->Link[way]  = tmp;
     if( tmp )
       {
-      tmp->Link[PARENT] = parentp;
-      tmp->gender       = way;
+      tmp->Link[ubi_trPARENT] = parentp;
+      tmp->gender             = way;
       }
 
-    tmp                 = parentp->Link[PARENT];
-    p->Link[PARENT]     = tmp;
-    p->gender           = parentp->gender;
+    tmp                   = parentp->Link[ubi_trPARENT];
+    p->Link[ubi_trPARENT] = tmp;
+    p->gender             = parentp->gender;
     if( tmp )
       tmp->Link[p->gender] = p;
 
-    parentp->Link[PARENT] = p;
-    parentp->gender       = revway;
-    p->Link[revway]       = parentp;
+    parentp->Link[ubi_trPARENT] = p;
+    parentp->gender             = revway;
+    p->Link[revway]             = parentp;
     }
   } /* Rotate */
 
@@ -187,17 +131,17 @@ static ubi_btNodePtr Splay( ubi_btNodePtr SplayWithMe )
   {
   ubi_btNodePtr parent;
 
-  while( (parent = SplayWithMe->Link[PARENT]) )
+  while( (parent = SplayWithMe->Link[ubi_trPARENT]) )
     {
     if( parent->gender == SplayWithMe->gender )       /* Zig-Zig */
       Rotate( parent );
     else
       {
-      if( EQUAL != parent->gender )                   /* Zig-Zag */
+      if( ubi_trEQUAL != parent->gender )             /* Zig-Zag */
         Rotate( SplayWithMe );
       }
     Rotate( SplayWithMe );                            /* Zig */
-    } /* while */
+    } 
   return( SplayWithMe );
   } /* Splay */
 
@@ -289,24 +233,24 @@ ubi_btNodePtr ubi_sptRemove( ubi_btRootPtr RootPtr, ubi_btNodePtr DeadNode )
   ubi_btNodePtr p;
 
   (void)Splay( DeadNode );                  /* Move dead node to root.        */
-  if( (p = DeadNode->Link[LEFT]) )          /* If left subtree exists...      */
+  if( (p = DeadNode->Link[ubi_trLEFT]) )    /* If left subtree exists...      */
     {
-    ubi_btNodePtr q = DeadNode->Link[RIGHT];
+    ubi_btNodePtr q = DeadNode->Link[ubi_trRIGHT];
 
-    p->Link[PARENT] = NULL;                 /* Left subtree node becomes root.*/
-    p->gender       = PARENT;
+    p->Link[ubi_trPARENT] = NULL;           /* Left subtree node becomes root.*/
+    p->gender       = ubi_trPARENT;
     p               = ubi_btLast( p );      /* Find rightmost left tree node..*/
-    p->Link[RIGHT]  = q;                    /* ...attach right tree.          */
+    p->Link[ubi_trRIGHT]  = q;              /* ...attach right tree.          */
     if( q )
-      q->Link[PARENT] = p;
+      q->Link[ubi_trPARENT] = p;
     RootPtr->root   = Splay( p );           /* Resplay at p.                  */
     }
   else
     {
-    if( (p = DeadNode->Link[RIGHT]) )       /* No left, but right subtree...  */
+    if( (p = DeadNode->Link[ubi_trRIGHT]) ) /* No left, but right subtree...  */
       {                                     /* ...exists...                   */
-      p->Link[PARENT] = NULL;               /* Right subtree root becomes...  */
-      p->gender       = PARENT;             /* ...overall tree root.          */
+      p->Link[ubi_trPARENT] = NULL;         /* Right subtree root becomes...  */
+      p->gender       = ubi_trPARENT;       /* ...overall tree root.          */
       RootPtr->root   = p;
       }
     else
@@ -424,7 +368,7 @@ void ubi_sptSplay( ubi_btRootPtr RootPtr,
    *          Splaying the tree will not damage it (assuming that I've done
    *          *my* job), but there is overhead involved.  I don't recommend
    *          that you use this function unless you understand the underlying
-   *          Splay Tree principles involved.
+   *          Splay Tree.
    * ------------------------------------------------------------------------ **
    */
   {
diff --git a/source3/ubiqx/ubi_SplayTree.h b/source3/ubiqx/ubi_SplayTree.h
index 7585d532ce..089fdc9d68 100644
--- a/source3/ubiqx/ubi_SplayTree.h
+++ b/source3/ubiqx/ubi_SplayTree.h
@@ -36,66 +36,17 @@
  *
  * -------------------------------------------------------------------------- **
  *
- * Revision 2.5  1997/07/26 04:15:46  crh
- * + Cleaned up a few minor syntax annoyances that gcc discovered for me.
- * + Changed ubi_TRUE and ubi_FALSE to ubi_trTRUE and ubi_trFALSE.
+ * Log: ubi_SplayTree.h,v
+ * Revision 3.0  1997/12/08 05:32:35  crh
+ * This is a new major revision level because of a redesign of the handling
+ * of the pointers in the ubi_trNode structure.  See ubi_BinTree for more
+ * info.
  *
- * Revision 2.4  1997/06/03 05:22:56  crh
- * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing
- * problems.
+ * Revision 2;  1995/02/27 - 1997/12/07:
+ * Major changes: added the function ubi_sptSplay().
  *
- * Revision 2.3  1995/10/03 22:19:37  CRH
- * Ubisized!
- * Also, added the function ubi_sptSplay().
- *
- * Revision 2.1  95/03/09  23:55:04  CRH
- * Added the ModuleID static string and function.  These modules are now
- * self-identifying.
- * 
- * Revision 2.0  95/02/27  22:34:55  CRH
- * This module was updated to match the interface changes made to the
- * ubi_BinTree module.  In particular, the interface to the Locate() function
- * has changed.  See ubi_BinTree for more information on changes and new
- * functions.
- *
- * The revision number was also upped to match ubi_BinTree.
- *
- *
- * Revision 1.0  93/10/15  22:59:36  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
+ * Revision 1; 93/10/15 - 95/02/27:
+ * Added the ubi_tr defines.  See ubi_BinTree.h for more info.
  *
  * Revision 0.0  93/04/21  23:07:13  CRH
  * Initial version, written by Christopher R. Hertel.
@@ -266,7 +217,7 @@ void ubi_sptSplay( ubi_btRootPtr RootPtr,
    *          Splaying the tree will not damage it (assuming that I've done
    *          *my* job), but there is overhead involved.  I don't recommend
    *          that you use this function unless you understand the underlying
-   *          Splay Tree principles involved.
+   *          Splay Tree.
    * ------------------------------------------------------------------------ **
    */