Updates to all of these base level modules.

Trees: Previously, the AVL node type was different than the node type used
       in the BinTree and SplayTree modules.  It requires an additional
       field to maintain AVL balance information.  I merged that field into
       the base type (in ubi_BinTree.h) so that all three use the same
       node type.  On most systems this will have zero effect on the node
       size, due to word alignment.  The change allowed me to remove a
       bigbunch of redundant code, which makes the AVL module smaller and
       cleaner.
Linked Lists:  I combined ubi_StackQueue into ubi_sLinkList.  The interface
       has changed a tiny bit.  I added macros to ubi_dLinkList to round
       it out a bit.

I have verified that the few Samba modules that use these tools (so far)
do not have any problems with the changes.

Chris -)-----
(This used to be commit 599a29401defded32358dfae18e54704c0428f38)

1 files changed, 19 insertions, 9 deletions

diff --git a/source3/ubiqx/ubi_BinTree.c b/source3/ubiqx/ubi_BinTree.c
index 501f3eeca7..c0f527e2d7 100644
--- a/source3/ubiqx/ubi_BinTree.c
+++ b/source3/ubiqx/ubi_BinTree.c
@@ -1,7 +1,7 @@
 /* ========================================================================== **
  *                              ubi_BinTree.c
  *
- *  Copyright (C) 1991-1997 by Christopher R. Hertel
+ *  Copyright (C) 1991-1998 by Christopher R. Hertel
  *
  *  Email:  crh@ubiqx.mn.org
  * -------------------------------------------------------------------------- **
@@ -27,6 +27,16 @@
  * -------------------------------------------------------------------------- **
  *
  * Log: ubi_BinTree.c,v
+ * Revision 4.0  1998/03/10 03:19:22  crh
+ * Added the AVL field 'balance' to the ubi_btNode structure.  This means
+ * that all BinTree modules now use the same basic node structure, which
+ * greatly simplifies the AVL module.
+ * Decided that this was a big enough change to justify a new major revision
+ * number.  3.0 was an error, so we're at 4.0.
+ *
+ * Revision 2.6  1998/01/24 06:27:46  crh
+ * Added ubi_trCount() macro.
+ *
  * 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
@@ -79,10 +89,9 @@
  *
  * 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".
+ * For example, if you were using ubi_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
@@ -116,8 +125,8 @@
  */
 
 static char ModuleID[] = "ubi_BinTree\n\
-\tRevision: 2.5\n\
-\tDate: 1997/12/23 03:56:29\n\
+\tRevision: 4.0\n\
+\tDate: 1998/03/10 03:19:22\n\
 \tAuthor: crh\n";
 
 /* ========================================================================== **
@@ -209,7 +218,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,7 +236,7 @@ static void ReplaceNode( ubi_btNodePtr *parent,
    *           that now reads:
    *     ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
    *           Bleah!
-   * ------------------------------------------------------------------ *
+   * ------------------------------------------------------------------------ **
    */
   {
   register int i;
@@ -456,6 +465,7 @@ ubi_btNodePtr ubi_btInitNode( ubi_btNodePtr NodePtr )
   NodePtr->Link[ ubi_trPARENT ] = NULL;
   NodePtr->Link[ ubi_trRIGHT ]  = NULL;
   NodePtr->gender               = ubi_trEQUAL;
+  NodePtr->balance              = ubi_trEQUAL;
   return( NodePtr );
   } /* ubi_btInitNode */