Backed out changes that attempted to address a pointer array using -1,0,1.

Jeremy pointed out that there might be problems with this.  Darn shame.
(This used to be commit ce9acc96a6cbc91f0a3f95221c3e8f801cbdb602)

1 files changed, 108 insertions, 114 deletions

diff --git a/source3/ubiqx/ubi_BinTree.c b/source3/ubiqx/ubi_BinTree.c
index 15bdeb1d85..501f3eeca7 100644
--- a/source3/ubiqx/ubi_BinTree.c
+++ b/source3/ubiqx/ubi_BinTree.c
@@ -6,7 +6,7 @@
  *  Email:  crh@ubiqx.mn.org
  * -------------------------------------------------------------------------- **
  *
- *  This module implements simple binary trees.
+ *  This module implements a simple binary tree.
  *
  * -------------------------------------------------------------------------- **
  *
@@ -27,72 +27,69 @@
  * -------------------------------------------------------------------------- **
  *
  * 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:
+ * Revision 2.5  1997/12/23 03:56:29  crh
+ * In this version, all constants & macros defined in the header file have
+ * the ubi_tr prefix.  Also cleaned up anything that gcc complained about
+ * when run with '-pedantic -fsyntax-only -Wall'.
  *
- *   typedef struct ubi_btNodeStruct
- *     {
- *     struct ubi_btNodeStruct *Link[3];
- *     signed char              gender;
- *     } ubi_btNode;
+ * 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().
  *
- * As a result, the pointers were indexed as
+ * 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.
  *
- *   Link[0] == Left Child
- *   Link[1] == Parent
- *   Link[2] == Right Child
+ * 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:
  *
- * With this release, the node structure changes to:
+ *     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.
  *
- *   typedef struct ubi_btNodeStruct
- *     {
- *     struct ubi_btNodeStruct *leftlink
- *     struct ubi_btNodeStruct *Link[2];
- *     signed char              gender;
- *     } ubi_btNode;
+ * 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.
  *
- * 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:
+ * 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:
  *
  *       Module        Prefix
  *     ubi_BinTree     ubi_bt
  *     ubi_AVLtree     ubi_avl
  *     ubi_SplayTree   ubi_spt
  *
- * 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".
+ * 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 is confusing.
+ * 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 added a set of defined names that get redefined in any of the
+ * 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
@@ -104,8 +101,7 @@
  * 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, or if you plan to use two or more specific tree types
- * in the same piece of code.  CRH
+ * red/black trees.  CRH
  *
  *  V0.0 - June, 1991   -  Written by Christopher R. Hertel (CRH).
  *
@@ -120,8 +116,8 @@
  */
 
 static char ModuleID[] = "ubi_BinTree\n\
-\tRevision: 3.0\n\
-\tDate: 1997/12/08 06:49:11\n\
+\tRevision: 2.5\n\
+\tDate: 1997/12/23 03:56:29\n\
 \tAuthor: crh\n";
 
 /* ========================================================================== **
@@ -134,7 +130,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
-   * (probably a little bit) faster that TreeFind (below).
+   * faster that TreeFind (below).
    *
    *  Input:
    *     cmp      -  a pointer to the tree's comparison function.
@@ -153,9 +149,9 @@ static ubi_btNodePtr qFind( ubi_btCompFunc cmp,
    * ------------------------------------------------------------------------ **
    */
   {
-  signed char tmp;
+  int tmp;
 
-  while( p && (( tmp = ubi_trNormalize((*cmp)(FindMe, p)) ) != ubi_trEQUAL) )
+  while( p && (( tmp = ubi_trAbNormal((*cmp)(FindMe, p)) ) != ubi_trEQUAL) )
     p = p->Link[tmp];
 
   return( p );
@@ -164,7 +160,7 @@ static ubi_btNodePtr qFind( ubi_btCompFunc cmp,
 static ubi_btNodePtr TreeFind( ubi_btItemPtr  findme,
                                ubi_btNodePtr  p,
                                ubi_btNodePtr *parentp,
-                               signed char   *gender,
+                               char          *gender,
                                ubi_btCompFunc CmpFunc )
   /* ------------------------------------------------------------------------ **
    * TreeFind() searches a tree for a given value (findme).  It will return a
@@ -195,16 +191,15 @@ static ubi_btNodePtr TreeFind( ubi_btItemPtr  findme,
   {
   register ubi_btNodePtr tmp_p = p;
   ubi_btNodePtr tmp_pp         = NULL;
-  signed char   tmp_gender     = ubi_trEQUAL;
-  signed char   tmp_cmp;
+  int tmp_gender               = ubi_trEQUAL;
+  int tmp_cmp;
 
   while( tmp_p
-      && (ubi_trEQUAL != (tmp_cmp = ubi_trNormalize((*CmpFunc)(findme, tmp_p))))
-       )
+     && (ubi_trEQUAL != (tmp_cmp = ubi_trAbNormal((*CmpFunc)(findme, tmp_p)))) )
     {
-    tmp_pp  = tmp_p;                /* Keep track of previous node. */
-    tmp_gender = tmp_cmp;           /* Keep track of sex of child.  */
-    tmp_p = tmp_p->Link[tmp_cmp];   /* Go to child. */
+    tmp_pp     = tmp_p;                 /* Keep track of previous node. */
+    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_gender;
@@ -214,7 +209,7 @@ static ubi_btNodePtr TreeFind( ubi_btItemPtr  findme,
 static void ReplaceNode( ubi_btNodePtr *parent,
                          ubi_btNodePtr  oldnode,
                          ubi_btNodePtr  newnode )
-  /* ------------------------------------------------------------------------ **
+  /* ------------------------------------------------------------------ *
    * Remove node oldnode from the tree, replacing it with node newnode.
    *
    * Input:
@@ -227,8 +222,12 @@ 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;
@@ -236,17 +235,12 @@ 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];
-
-  /* Old node's parent points to new child. */
-  (*parent) = newnode;
-
+  (*parent) = newnode;              /* Old node's parent points to new child. */
   /* Now tell the children about their new step-parent. */
-  if( oldnode->Link[ubi_trLEFT ] )
-    (oldnode->Link[ubi_trLEFT ])->Link[ubi_trPARENT] = 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,
@@ -274,21 +268,21 @@ static void SwapNodes( ubi_btRootPtr RootPtr,
 
   /* Replace Node 1 with the dummy, thus removing Node1 from the tree. */
   if( Node1->Link[ubi_trPARENT] )
-    Parent = &((Node1->Link[ubi_trPARENT])->Link[Node1->gender]);
+    Parent = &((Node1->Link[ubi_trPARENT])->Link[(int)(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[ubi_trPARENT] )
-    Parent = &((Node2->Link[ubi_trPARENT])->Link[Node2->gender]);
+    Parent = &((Node2->Link[ubi_trPARENT])->Link[(int)(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[ubi_trPARENT] )
-    Parent = &((dummy_p->Link[ubi_trPARENT])->Link[dummy_p->gender]);
+    Parent = &((dummy_p->Link[ubi_trPARENT])->Link[(int)(dummy_p->gender)]);
   else
     Parent = &(RootPtr->root);
   ReplaceNode( Parent, dummy_p, Node2 );
@@ -299,7 +293,7 @@ static void SwapNodes( ubi_btRootPtr RootPtr,
  */
 
 static ubi_btNodePtr SubSlide( register ubi_btNodePtr P,
-                               register signed char   whichway )
+                               register int           whichway )
   /* ------------------------------------------------------------------------ **
    * Slide down the side of a subtree.
    *
@@ -327,7 +321,7 @@ static ubi_btNodePtr SubSlide( register ubi_btNodePtr P,
   } /* SubSlide */
 
 static ubi_btNodePtr Neighbor( register ubi_btNodePtr P,
-                               register signed char   whichway )
+                               register int           whichway )
   /* ------------------------------------------------------------------------ **
    * Given starting point p, return the (key order) next or preceeding node
    * in the tree.
@@ -346,7 +340,7 @@ static ubi_btNodePtr Neighbor( register ubi_btNodePtr P,
   if( P )
     {
     if( P->Link[ whichway ] )
-      return( SubSlide( P->Link[ whichway ], ubi_trRevWay(whichway) ) );
+      return( SubSlide( P->Link[ whichway ], (char)ubi_trRevWay(whichway) ) );
     else
       while( P->Link[ ubi_trPARENT ] )
         {
@@ -362,7 +356,7 @@ static ubi_btNodePtr Neighbor( register ubi_btNodePtr P,
 static ubi_btNodePtr Border( ubi_btRootPtr RootPtr,
                              ubi_btItemPtr FindMe,
                              ubi_btNodePtr p,
-                             signed char   whichway )
+                             int           whichway )
   /* ------------------------------------------------------------------------ **
    * Given starting point p, which has a key value equal to *FindMe, locate
    * the first (index order) node with the same key value.
@@ -401,7 +395,7 @@ static ubi_btNodePtr Border( ubi_btRootPtr RootPtr,
    * subtree that contains all of the matching nodes.
    */
   q = p->Link[ubi_trPARENT];
-  while( q && (ubi_trEQUAL == ubi_trNormalize( (*(RootPtr->cmp))(FindMe, q) )) )
+  while( q && (ubi_trEQUAL == ubi_trAbNormal( (*(RootPtr->cmp))(FindMe, q) )) )
     {
     p = q;
     q = p->Link[ubi_trPARENT];
@@ -411,7 +405,8 @@ static ubi_btNodePtr Border( ubi_btRootPtr RootPtr,
   q = p->Link[whichway];
   while( q )
     {
-    if( q = qFind( RootPtr->cmp, FindMe, q ) )
+    q = qFind( RootPtr->cmp, FindMe, q );
+    if( q )
       {
       p = q;
       q = p->Link[whichway];
@@ -431,15 +426,15 @@ long ubi_btSgn( register long x )
    *
    *  Input:  x - a signed long integer value.
    *
-   *  Output: -1, 0, or 1 representing the "sign" of x as follows:
+   *  Output: the "sign" of x, represented 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: {ubi_trLEFT, ubi_trPARENT, ubi_trEQUAL}.  It is
-   *          incorporated into the ubi_trNormalize() conversion macro.
+   * 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
+   *       ubi_trAbNormal() conversion macro!
    *
    * ------------------------------------------------------------------------ **
    */
@@ -553,7 +548,7 @@ ubi_trBool ubi_btInsert( ubi_btRootPtr  RootPtr,
   {
   ubi_btNodePtr OtherP,
                 parent = NULL;
-  signed char   tmp;
+  char          tmp;
 
   if( !(OldNode) )       /* If they didn't give us a pointer, supply our own. */
     OldNode = &OtherP;
@@ -570,7 +565,7 @@ ubi_trBool ubi_btInsert( ubi_btRootPtr  RootPtr,
       RootPtr->root = NewNode;
     else
       {
-      parent->Link[tmp]           = NewNode;
+      parent->Link[(int)tmp]      = NewNode;
       NewNode->Link[ubi_trPARENT] = parent;
       NewNode->gender             = tmp;
       }
@@ -593,11 +588,11 @@ ubi_trBool ubi_btInsert( ubi_btRootPtr  RootPtr,
       parent = q;
       if( tmp == ubi_trEQUAL )
         tmp = ubi_trRIGHT;
-      q = q->Link[tmp];
+      q = q->Link[(int)tmp];
       if ( q )
-        tmp = ubi_trNormalize( (*(RootPtr->cmp))(ItemPtr, q) );
+        tmp = ubi_trAbNormal( (*(RootPtr->cmp))(ItemPtr, q) );
       }
-    parent->Link[tmp]            = NewNode;
+    parent->Link[(int)tmp]       = NewNode;
     NewNode->Link[ubi_trPARENT]  = parent;
     NewNode->gender              = tmp;
     (RootPtr->count)++;
@@ -613,7 +608,8 @@ ubi_trBool ubi_btInsert( ubi_btRootPtr  RootPtr,
     if (!(parent))
       ReplaceNode( &(RootPtr->root), *OldNode, NewNode );
     else
-      ReplaceNode( &(parent->Link[(*OldNode)->gender]), *OldNode, NewNode );
+      ReplaceNode( &(parent->Link[(int)((*OldNode)->gender)]),
+                   *OldNode, NewNode );
     return( ubi_trTRUE );
     }
 
@@ -639,7 +635,7 @@ ubi_btNodePtr ubi_btRemove( ubi_btRootPtr RootPtr,
   {
   ubi_btNodePtr p,
                *parentp;
-  signed char   tmp;
+  int           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
@@ -653,18 +649,18 @@ ubi_btNodePtr ubi_btRemove( ubi_btRootPtr RootPtr,
    * a pointer to the parent pointer, whatever it is.
    */
   if (DeadNode->Link[ubi_trPARENT])
-    parentp = &((DeadNode->Link[ubi_trPARENT])->Link[DeadNode->gender]);
+    parentp = &((DeadNode->Link[ubi_trPARENT])->Link[(int)(DeadNode->gender)]);
   else
     parentp = &( RootPtr->root );
 
   /* Now link the parent to the only grand-child and patch up the gender. */
-  tmp = ((DeadNode->Link[ubi_trLEFT]) ? ubi_trLEFT : ubi_trRIGHT);
+  tmp = ((DeadNode->Link[ubi_trLEFT])?ubi_trLEFT:ubi_trRIGHT);
 
   p = (DeadNode->Link[tmp]);
   if( p )
     {
     p->Link[ubi_trPARENT] = DeadNode->Link[ubi_trPARENT];
-    p->gender             = DeadNode->gender;
+    p->gender       = DeadNode->gender;
     }
   (*parentp) = p;
 
@@ -727,7 +723,7 @@ ubi_btNodePtr ubi_btLocate( ubi_btRootPtr RootPtr,
   {
   register ubi_btNodePtr p;
   ubi_btNodePtr   parent;
-  signed char     whichkid;
+  char            whichkid;
 
   /* Start by searching for a matching node. */
   p = TreeFind( FindMe,
@@ -746,9 +742,10 @@ ubi_btNodePtr ubi_btLocate( ubi_btRootPtr RootPtr,
       case ubi_trGT:            /* ...and then a jump to the right. */
         p = Border( RootPtr, FindMe, p, ubi_trRIGHT );
         return( Neighbor( p, ubi_trRIGHT ) );
+      default:
+        p = Border( RootPtr, FindMe, p, ubi_trLEFT );
+        return( p );
       }
-    p = Border( RootPtr, FindMe, p, ubi_trLEFT );
-    return( p );
     }
 
   /* Else, no match. */
@@ -761,7 +758,7 @@ ubi_btNodePtr ubi_btLocate( ubi_btRootPtr RootPtr,
    * Remaining possibilities are LT and GT (including LE & GE).
    */
   if( (ubi_trLT == CompOp) || (ubi_trLE == CompOp) )
-    return( (ubi_trLEFT  == whichkid) ? Neighbor( parent, whichkid ) : parent );
+    return( (ubi_trLEFT == whichkid) ? Neighbor( parent, whichkid ) : parent );
   else
     return( (ubi_trRIGHT == whichkid) ? Neighbor( parent, whichkid ) : parent );
   } /* ubi_btLocate */
@@ -866,7 +863,7 @@ ubi_btNodePtr ubi_btFirstOf( ubi_btRootPtr RootPtr,
    */
   {
   /* If our starting point is invalid, return NULL. */
-  if( !p || ubi_trNormalize( (*(RootPtr->cmp))( MatchMe, p ) != ubi_trEQUAL ) )
+  if( !p || ubi_trAbNormal( (*(RootPtr->cmp))( MatchMe, p ) != ubi_trEQUAL ) )
     return( NULL );
   return( Border( RootPtr, MatchMe, p, ubi_trLEFT ) );
   } /* ubi_btFirstOf */
@@ -891,7 +888,7 @@ ubi_btNodePtr ubi_btLastOf( ubi_btRootPtr RootPtr,
    */
   {
   /* If our starting point is invalid, return NULL. */
-  if( !p || ubi_trNormalize( (*(RootPtr->cmp))( MatchMe, p ) != ubi_trEQUAL ) )
+  if( !p || ubi_trAbNormal( (*(RootPtr->cmp))( MatchMe, p ) != ubi_trEQUAL ) )
     return( NULL );
   return( Border( RootPtr, MatchMe, p, ubi_trRIGHT ) );
   } /* ubi_btLastOf */
@@ -990,8 +987,6 @@ 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.
    *
    * ------------------------------------------------------------------------ **
    */
@@ -1001,10 +996,8 @@ ubi_btNodePtr ubi_btLeafNode( ubi_btNodePtr leader )
 
   while( NULL != leader )
     {
-    /* The next line is a weak attempt at randomizing. */
-    whichway = ((int)leader & 0x0010) ? whichway : ubi_trRevWay(whichway);
     follower = leader;
-    leader   = leader->Link[ whichway ];
+    leader   = follower->Link[ whichway ];
     if( NULL == leader )
       {
       whichway = ubi_trRevWay( whichway );
@@ -1043,4 +1036,5 @@ int ubi_btModuleID( int size, char *list[] )
   return( 0 );
   } /* ubi_btModuleID */
 
+
 /* ========================================================================== */