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, 34 insertions, 10 deletions

diff --git a/source3/ubiqx/ubi_BinTree.h b/source3/ubiqx/ubi_BinTree.h
index 4b918a4609..f3c49c95e1 100644
--- a/source3/ubiqx/ubi_BinTree.h
+++ b/source3/ubiqx/ubi_BinTree.h
@@ -3,7 +3,7 @@
 /* ========================================================================== **
  *                              ubi_BinTree.h
  *
- *  Copyright (C) 1991-1997 by Christopher R. Hertel
+ *  Copyright (C) 1991-1998 by Christopher R. Hertel
  *
  *  Email:  crh@ubiqx.mn.org
  * -------------------------------------------------------------------------- **
@@ -29,6 +29,16 @@
  * -------------------------------------------------------------------------- **
  *
  * Log: ubi_BinTree.h,v
+ * Revision 4.0  1998/03/10 03:16:04  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:30  crh
+ * Added ubi_trCount() macro.
+ *
  * Revision 2.5  1997/12/23 03:59:21  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
@@ -81,10 +91,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
@@ -198,6 +207,16 @@ typedef enum {
         ((ubi_trOVERWRITE & ((A)->flags))?(ubi_trTRUE):(ubi_trFALSE))
 
 /* -------------------------------------------------------------------------- **
+ * A quickie for consistency.
+ *  ubi_trCount() - Given a pointer to a tree root, this macro returns the
+ *                  number of nodes currently in the tree.
+ *
+ * -------------------------------------------------------------------------- **
+ */
+
+#define ubi_trCount( R ) (((ubi_trRootPtr)(R))->count)
+
+/* -------------------------------------------------------------------------- **
  * Typedefs...
  * 
  * ubi_trBool   - Your typcial true or false...
@@ -211,7 +230,7 @@ typedef enum {
 
 typedef unsigned char ubi_trBool;
 
-typedef void *ubi_btItemPtr;              /* A pointer to data within a node. */
+typedef void *ubi_btItemPtr;          /* A pointer to key data within a node. */
 
 /*  ------------------------------------------------------------------------- **
  *  Binary Tree Node Structure:  This structure defines the basic elements of
@@ -230,11 +249,16 @@ 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.
+ *    balance  -  only used by the AVL tree module.  This field indicates
+ *                the height balance at a given node.  See ubi_AVLtree for
+ *                details.
+ *
  *  ------------------------------------------------------------------------- **
  */
 typedef struct ubi_btNodeStruct {
   struct ubi_btNodeStruct *Link[ 3 ];
-  char                     gender;
+  signed char              gender;
+  signed char              balance;
   } ubi_btNode;
 
 typedef ubi_btNode *ubi_btNodePtr;     /* Pointer to an ubi_btNode structure. */
@@ -272,8 +296,8 @@ typedef void (*ubi_btKillNodeRtn)( ubi_btNodePtr );
 
 /* -------------------------------------------------------------------------- **
  * 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.
+ *                      accessing whole binary trees.  The fields are:
+ *    root  -  A pointer to the root node of the 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
  *             searching the tree.
@@ -294,8 +318,8 @@ typedef void (*ubi_btKillNodeRtn)( ubi_btNodePtr );
 
 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  */
+  unsigned long  count;    /* A count of the number of nodes in the tree   */
   unsigned char  flags;    /* Overwrite Y|N, Duplicate keys Y|N...         */
   } ubi_btRoot;