From 87d4fc1d225ab0aa5bac2b104d7958065a453144 Mon Sep 17 00:00:00 2001
From: "Christopher R. Hertel" <crh@samba.org>
Date: Tue, 10 Mar 1998 15:39:41 +0000
Subject: 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)
---
 source3/ubiqx/ubi_AVLtree.c   | 217 +++++++++---------------------------------
 source3/ubiqx/ubi_AVLtree.h   | 131 +++++--------------------
 source3/ubiqx/ubi_BinTree.c   |  28 ++++--
 source3/ubiqx/ubi_BinTree.h   |  44 +++++++--
 source3/ubiqx/ubi_SplayTree.c |  23 +++--
 source3/ubiqx/ubi_SplayTree.h |  23 +++--
 source3/ubiqx/ubi_dLinkList.c |  50 +++++-----
 source3/ubiqx/ubi_dLinkList.h |  57 ++++++++---
 source3/ubiqx/ubi_sLinkList.c |  82 ++++++++++++----
 source3/ubiqx/ubi_sLinkList.h |  96 +++++++++++++++++--
 10 files changed, 370 insertions(+), 381 deletions(-)

diff --git a/source3/ubiqx/ubi_AVLtree.c b/source3/ubiqx/ubi_AVLtree.c
index 2cd8d1cbed..c02765f441 100644
--- a/source3/ubiqx/ubi_AVLtree.c
+++ b/source3/ubiqx/ubi_AVLtree.c
@@ -1,7 +1,7 @@
 /* ========================================================================== **
  *                              ubi_AVLtree.c
  *
- *  Copyright (C) 1991-1997 by Christopher R. Hertel
+ *  Copyright (C) 1991-1998 by Christopher R. Hertel
  *
  *  Email: crh@ubiqx.mn.org
  * -------------------------------------------------------------------------- **
@@ -32,6 +32,14 @@
  * -------------------------------------------------------------------------- **
  *
  * Log: ubi_AVLtree.c,v
+ * Revision 4.0  1998/03/10 03:37:09  crh
+ * Major changes.
+ * By adding the AVL balance field to the base ubi_btNode structure, I no
+ * longer need AVL-specific ReplaceNode(), SwapNodes(), and InitNode()
+ * functions.  The Remove() function is also simplified.  It's all much
+ * cleaner.
+ * This is rev. 4.0.  The 3.x series was dropped.
+ *
  * Revision 2.5  1997/12/23 04:00:42  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
@@ -92,10 +100,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
@@ -129,8 +136,8 @@
  */
 
 static char ModuleID[] = "ubi_AVLtree\n\
-\tRevision: 2.5\n\
-\tDate: 1997/12/23 04:00:42\n\
+\tRevision: 4.0\n\
+\tDate: 1998/03/10 03:37:09\n\
 \tAuthor: crh\n";
 
 /* ========================================================================== **
@@ -147,7 +154,7 @@ static char ModuleID[] = "ubi_AVLtree\n\
  * -------------------------------------------------------------------------- **
  */
 
-static ubi_avlNodePtr L1( ubi_avlNodePtr p )
+static ubi_btNodePtr L1( ubi_btNodePtr p )
   /* ------------------------------------------------------------------------ **
    * Single rotate left.
    *
@@ -157,7 +164,7 @@ static ubi_avlNodePtr L1( ubi_avlNodePtr p )
    * ------------------------------------------------------------------------ **
    */
   {
-  ubi_avlNodePtr tmp;
+  ubi_btNodePtr tmp;
 
   tmp                      = p->Link[ubi_trRIGHT];
   p->Link[ubi_trRIGHT]     = tmp->Link[ubi_trLEFT];
@@ -179,7 +186,7 @@ static ubi_avlNodePtr L1( ubi_avlNodePtr p )
   return( tmp );
   } /* L1 */
 
-static ubi_avlNodePtr R1( ubi_avlNodePtr p )
+static ubi_btNodePtr R1( ubi_btNodePtr p )
   /* ------------------------------------------------------------------------ **
    * Single rotate right.
    *
@@ -189,7 +196,7 @@ static ubi_avlNodePtr R1( ubi_avlNodePtr p )
    * ------------------------------------------------------------------------ **
    */
   {
-  ubi_avlNodePtr tmp;
+  ubi_btNodePtr tmp;
 
   tmp                      = p->Link[ubi_trLEFT];
   p->Link[ubi_trLEFT]      = tmp->Link[ubi_trRIGHT];
@@ -211,7 +218,7 @@ static ubi_avlNodePtr R1( ubi_avlNodePtr p )
   return( tmp );
   } /* R1 */
 
-static ubi_avlNodePtr L2( ubi_avlNodePtr tree )
+static ubi_btNodePtr L2( ubi_btNodePtr tree )
   /* ------------------------------------------------------------------------ **
    * Double rotate left.
    *
@@ -221,7 +228,7 @@ static ubi_avlNodePtr L2( ubi_avlNodePtr tree )
    * ------------------------------------------------------------------------ **
    */
   {
-  ubi_avlNodePtr tmp, newroot;
+  ubi_btNodePtr tmp, newroot;
 
   tmp                         = tree->Link[ubi_trRIGHT];
   newroot                     = tmp->Link[ubi_trLEFT];
@@ -263,7 +270,7 @@ static ubi_avlNodePtr L2( ubi_avlNodePtr tree )
   return( newroot );
   } /* L2 */
 
-static ubi_avlNodePtr R2( ubi_avlNodePtr tree )
+static ubi_btNodePtr R2( ubi_btNodePtr tree )
   /* ------------------------------------------------------------------------ **
    * Double rotate right.
    *
@@ -273,7 +280,7 @@ static ubi_avlNodePtr R2( ubi_avlNodePtr tree )
    * ------------------------------------------------------------------------ **
    */
   {
-  ubi_avlNodePtr tmp, newroot;
+  ubi_btNodePtr tmp, newroot;
 
   tmp                         = tree->Link[ubi_trLEFT];
   newroot                     = tmp->Link[ubi_trRIGHT];
@@ -316,7 +323,7 @@ static ubi_avlNodePtr R2( ubi_avlNodePtr tree )
   } /* R2 */
 
 
-static ubi_avlNodePtr Adjust( ubi_avlNodePtr p, char LorR )
+static ubi_btNodePtr Adjust( ubi_btNodePtr p, char LorR )
   /* ------------------------------------------------------------------------ **
    * Adjust the balance value at node *p.  If necessary, rotate the subtree
    * rooted at p.
@@ -349,9 +356,9 @@ static ubi_avlNodePtr Adjust( ubi_avlNodePtr p, char LorR )
   return( p );
   } /* Adjust */
 
-static ubi_avlNodePtr Rebalance( ubi_avlNodePtr Root,
-                                 ubi_avlNodePtr subtree,
-                                 char           LorR )
+static ubi_btNodePtr Rebalance( ubi_btNodePtr Root,
+                                ubi_btNodePtr subtree,
+                                char          LorR )
   /* ------------------------------------------------------------------------ **
    * Rebalance the tree following an insertion.
    *
@@ -387,9 +394,9 @@ static ubi_avlNodePtr Rebalance( ubi_avlNodePtr Root,
   return( Root );
   } /* Rebalance */
 
-static ubi_avlNodePtr Debalance( ubi_avlNodePtr Root,
-                                 ubi_avlNodePtr subtree,
-                                 char           LorR )
+static ubi_btNodePtr Debalance( ubi_btNodePtr Root,
+                                ubi_btNodePtr subtree,
+                                char          LorR )
   /* ------------------------------------------------------------------------ **
    * Rebalance the tree following a deletion.
    *
@@ -428,125 +435,22 @@ static ubi_avlNodePtr Debalance( ubi_avlNodePtr Root,
   return( Root );
   } /* Debalance */
 
-
-/* -------------------------------------------------------------------------- **
- * The next two functions are used for general tree manipulation.  They are
- * each slightly different from their ubi_BinTree counterparts.
- * -------------------------------------------------------------------------- **
- */
-
-static void ReplaceNode( ubi_avlNodePtr *parent,
-                         ubi_avlNodePtr  oldnode,
-                         ubi_avlNodePtr  newnode )
-  /* ------------------------------------------------------------------------ **
-   * Remove node oldnode from the tree, replacing it with node newnode.
-   *
-   * Input:
-   *  parent   - A pointer to he parent pointer of the node to be
-   *             replaced.  <parent> may point to the Link[] field of
-   *             a parent node, or it may indicate the root pointer at
-   *             the top of the tree.
-   *  oldnode  - A pointer to the node that is to be replaced.
-   *  newnode  - A pointer to the node that is to be installed in the
-   *             place of <*oldnode>.
-   *
-   * Notes:    Don't forget to free oldnode.
-   *           The only difference between this function and the ubi_bt
-   *           version is that the node size is sizeof( ubi_avlNode ), not
-   *           sizeof( ubi_btNode ).
-   * ------------------------------------------------------------------------ **
-   */
-  {
-  register int i;
-  register int avlNodeSize = sizeof( ubi_avlNode );
-
-  for( i = 0; i < avlNodeSize; i++ )
-    ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
-  (*parent) = newnode;
-
-  if(oldnode->Link[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,
-                       ubi_avlNodePtr Node1,
-                       ubi_avlNodePtr Node2 )
-  /* ------------------------------------------------------------------------ **
-   * This function swaps two nodes in the tree.  Node1 will take the place of
-   * Node2, and Node2 will fill in the space left vacant by Node 1.
-   *
-   * Input:
-   *  RootPtr  - pointer to the tree header structure for this tree.
-   *  Node1    - \
-   *              > These are the two nodes which are to be swapped.
-   *  Node2    - /
-   *
-   * Notes:
-   *  This function does a three step swap, using a dummy node as a place
-   *  holder.  This function is used by ubi_avlRemove().
-   *  The only difference between this function and its ubi_bt counterpart
-   *  is that the nodes are ubi_avlNodes, not ubi_btNodes.
-   * ------------------------------------------------------------------------ **
-   */
-  {
-  ubi_avlNodePtr *Parent;
-  ubi_avlNode     dummy;
-  ubi_avlNodePtr  dummy_p = &dummy;
-
-  if( Node1->Link[ubi_trPARENT] )
-    Parent = &((Node1->Link[ubi_trPARENT])->Link[(int)(Node1->gender)]);
-  else
-    Parent = (ubi_avlNodePtr *)&(RootPtr->root);
-  ReplaceNode( Parent, Node1, dummy_p );
-
-  if( Node2->Link[ubi_trPARENT] )
-    Parent = &((Node2->Link[ubi_trPARENT])->Link[(int)(Node2->gender)]);
-  else
-    Parent = (ubi_avlNodePtr *)&(RootPtr->root);
-  ReplaceNode( Parent, Node2, Node1 );
-
-  if( dummy_p->Link[ubi_trPARENT] )
-    Parent = &((dummy_p->Link[ubi_trPARENT])->Link[(int)(dummy_p->gender)]);
-  else
-    Parent = (ubi_avlNodePtr *)&(RootPtr->root);
-  ReplaceNode( Parent, dummy_p, Node2 );
-  } /* SwapNodes */
-
-
 /* ========================================================================== **
  *         Public, exported (ie. not static-ly declared) functions...
  * -------------------------------------------------------------------------- **
  */
 
-ubi_avlNodePtr ubi_avlInitNode( ubi_avlNodePtr NodePtr )
-  /* ------------------------------------------------------------------------ **
-   * Initialize a tree node.
-   *
-   *  Input:   NodePtr  - pointer to a ubi_btNode structure to be
-   *                      initialized.
-   *  Output:  a pointer to the initialized ubi_avlNode structure (ie. the
-   *           same as the input pointer).
-   * ------------------------------------------------------------------------ **
-   */
-  {
-  (void)ubi_btInitNode( (ubi_btNodePtr)NodePtr );
-  NodePtr->balance = ubi_trEQUAL;
-  return( NodePtr );
-  } /* ubi_avlInitNode */
-
-ubi_trBool ubi_avlInsert( ubi_btRootPtr   RootPtr,
-                          ubi_avlNodePtr  NewNode,
-                          ubi_btItemPtr   ItemPtr,
-                          ubi_avlNodePtr *OldNode )
+ubi_trBool ubi_avlInsert( ubi_btRootPtr  RootPtr,
+                          ubi_btNodePtr  NewNode,
+                          ubi_btItemPtr  ItemPtr,
+                          ubi_btNodePtr *OldNode )
   /* ------------------------------------------------------------------------ **
    * This function uses a non-recursive algorithm to add a new element to
    * the tree.
    *
    *  Input:   RootPtr  -  a pointer to the ubi_btRoot structure that indicates
    *                       the root of the tree to which NewNode is to be added.
-   *           NewNode  -  a pointer to an ubi_avlNode structure that is NOT
+   *           NewNode  -  a pointer to an ubi_btNode structure that is NOT
    *                       part of any tree.
    *           ItemPtr  -  A pointer to the sort key that is stored within
    *                       *NewNode.  ItemPtr MUST point to information stored
@@ -585,9 +489,10 @@ ubi_trBool ubi_avlInsert( ubi_btRootPtr   RootPtr,
    * ------------------------------------------------------------------------ **
    */
   {
-  ubi_avlNodePtr OtherP;
+  ubi_btNodePtr OtherP;
 
-  if( !(OldNode) ) OldNode = &OtherP;
+  if( !(OldNode) )
+    OldNode = &OtherP;
   if( ubi_btInsert( RootPtr,
                     (ubi_btNodePtr)NewNode,
                     ItemPtr,
@@ -598,7 +503,7 @@ ubi_trBool ubi_avlInsert( ubi_btRootPtr   RootPtr,
     else
       {
       NewNode->balance = ubi_trEQUAL;
-      RootPtr->root = (ubi_btNodePtr)Rebalance( (ubi_avlNodePtr)RootPtr->root,
+      RootPtr->root = (ubi_btNodePtr)Rebalance( (ubi_btNodePtr)RootPtr->root,
                                                 NewNode->Link[ubi_trPARENT],
                                                 NewNode->gender );
       }
@@ -607,8 +512,8 @@ ubi_trBool ubi_avlInsert( ubi_btRootPtr   RootPtr,
   return( ubi_trFALSE );      /* Failure: could not replace an existing node. */
   } /* ubi_avlInsert */
 
-ubi_avlNodePtr ubi_avlRemove( ubi_btRootPtr  RootPtr,
-                              ubi_avlNodePtr DeadNode )
+ubi_btNodePtr ubi_avlRemove( ubi_btRootPtr  RootPtr,
+                             ubi_btNodePtr  DeadNode )
   /* ------------------------------------------------------------------------ **
    * This function removes the indicated node from the tree, after which the
    * tree is rebalanced.
@@ -622,45 +527,15 @@ ubi_avlNodePtr ubi_avlRemove( ubi_btRootPtr  RootPtr,
    *
    *  Note:   The node MUST be in the tree indicated by RootPtr.  If not,
    *          strange and evil things will happen to your trees.
+   *
    * ------------------------------------------------------------------------ **
    */
   {
-  ubi_btNodePtr p,
-               *parentp;
-
-  /* if the node has both left and right subtrees, then we have to swap
-   * it with another node.
-   */
-  if( (DeadNode->Link[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[ubi_trPARENT] )
-    parentp = (ubi_btNodePtr *)
-              &((DeadNode->Link[ubi_trPARENT])->Link[(int)(DeadNode->gender)]);
-  else
-    parentp = &( RootPtr->root );
-
-  /* Now link the parent to the only grand-child.  Patch up the gender and
-   * such, and rebalance.
-   */
-  if( ubi_trEQUAL == DeadNode->balance )
-    (*parentp) = NULL;
-  else
-    {
-    p = (ubi_btNodePtr)(DeadNode->Link[(int)(DeadNode->balance)]);
-    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[ubi_trPARENT],
-                                            DeadNode->gender );
-
-  (RootPtr->count)--;
+  /* Let the base binary tree module do the removal, then rebalance. */
+  if( ubi_btRemove( RootPtr, DeadNode ) )
+    RootPtr->root = Debalance( RootPtr->root,
+                               DeadNode->Link[ubi_trPARENT],
+                               DeadNode->gender );
   return( DeadNode );
   } /* ubi_avlRemove */
 
diff --git a/source3/ubiqx/ubi_AVLtree.h b/source3/ubiqx/ubi_AVLtree.h
index ebae7f3c13..f99a78aa26 100644
--- a/source3/ubiqx/ubi_AVLtree.h
+++ b/source3/ubiqx/ubi_AVLtree.h
@@ -3,7 +3,7 @@
 /* ========================================================================== **
  *                              ubi_AVLtree.h
  *
- *  Copyright (C) 1991-1997 by Christopher R. Hertel
+ *  Copyright (C) 1991-1998 by Christopher R. Hertel
  *
  *  Email: crh@ubiqx.mn.org
  * -------------------------------------------------------------------------- **
@@ -35,6 +35,14 @@
  *
  * -------------------------------------------------------------------------- **
  * Log: ubi_AVLtree.h,v
+ * Revision 4.0  1998/03/10 03:34:45  crh
+ * Major changes.
+ * By adding the AVL balance field to the base ubi_btNode structure, I no
+ * longer need AVL-specific ReplaceNode(), SwapNodes(), and InitNode()
+ * functions.  The Remove() function is also simplified.  It's all much
+ * cleaner.
+ * This is rev. 4.0.  The 3.x series was dropped.
+ *
  * Revision 2.5  1997/12/23 04:00:15  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
@@ -95,10 +103,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
@@ -126,70 +133,22 @@
 
 #include "ubi_BinTree.h"   /* Base erg binary tree support.       */
 
-/*  ------------------------------------------------------------------------- **
- *  AVL Tree Node Structure:  This structure defines the basic elements of
- *       the AVL 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 the structure as a building block.
- *
- *  The fields are as follows:
- *    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
- *                pointer, we avoid the need for recursive routines or hand-
- *                tooled stacks to keep track of our path back to the root.
- *                The use of these pointers is subject to change without
- *                notice.
- *    gender   -  For tree rebalancing purposes, it is necessary that each node
- *                know whether it is the left or right child of its parent, or
- *                if it is the root.  This information is stored in this field.
- *    balance  -  This field is also needed for AVL balancing purposes.  It
- *                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 ubi_avlNode *ubi_avlNodePtr;    /* a Pointer to an AVL node */
-
 /* -------------------------------------------------------------------------- **
  *  Function prototypes.
  * -------------------------------------------------------------------------- **
  */
 
-ubi_avlNodePtr ubi_avlInitNode( ubi_avlNodePtr NodePtr );
-  /* ------------------------------------------------------------------------ **
-   * Initialize a tree node.
-   *
-   *  Input:   NodePtr  - a pointer to a ubi_btNode structure to be
-   *                      initialized.
-   *  Output:  a pointer to the initialized ubi_avlNode structure (ie. the
-   *           same as the input pointer).
-   * ------------------------------------------------------------------------ **
-   */
-
-ubi_trBool ubi_avlInsert( ubi_btRootPtr   RootPtr,
-                          ubi_avlNodePtr  NewNode,
-                          ubi_btItemPtr   ItemPtr,
-                          ubi_avlNodePtr *OldNode );
+ubi_trBool ubi_avlInsert( ubi_btRootPtr  RootPtr,
+                          ubi_btNodePtr  NewNode,
+                          ubi_btItemPtr  ItemPtr,
+                          ubi_btNodePtr *OldNode );
   /* ------------------------------------------------------------------------ **
    * This function uses a non-recursive algorithm to add a new element to
    * the tree.
    *
    *  Input:   RootPtr  -  a pointer to the ubi_btRoot structure that indicates
    *                       the root of the tree to which NewNode is to be added.
-   *           NewNode  -  a pointer to an ubi_avlNode structure that is NOT
+   *           NewNode  -  a pointer to an ubi_btNode structure that is NOT
    *                       part of any tree.
    *           ItemPtr  -  A pointer to the sort key that is stored within
    *                       *NewNode.  ItemPtr MUST point to information stored
@@ -228,8 +187,8 @@ ubi_trBool ubi_avlInsert( ubi_btRootPtr   RootPtr,
    * ------------------------------------------------------------------------ **
    */
 
-ubi_avlNodePtr ubi_avlRemove( ubi_btRootPtr  RootPtr,
-                              ubi_avlNodePtr DeadNode );
+ubi_btNodePtr ubi_avlRemove( ubi_btRootPtr RootPtr,
+                             ubi_btNodePtr DeadNode );
   /* ------------------------------------------------------------------------ **
    * This function removes the indicated node from the tree, after which the
    * tree is rebalanced.
@@ -273,60 +232,14 @@ int ubi_avlModuleID( int size, char *list[] );
  * type by including the appropriate module header.
  */
 
-#undef ubi_trNode
-#undef ubi_trNodePtr
-#define ubi_trNode    ubi_avlNode
-#define ubi_trNodePtr ubi_avlNodePtr
-
-#undef ubi_trInitNode
-#define ubi_trInitNode( Np ) ubi_avlInitNode( (ubi_avlNodePtr)(Np) )
-
 #undef ubi_trInsert
 #define ubi_trInsert( Rp, Nn, Ip, On ) \
-        ubi_avlInsert( (ubi_btRootPtr)(Rp), (ubi_avlNodePtr)(Nn), \
-                       (ubi_btItemPtr)(Ip), (ubi_avlNodePtr *)(On) )
+        ubi_avlInsert( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Nn), \
+                       (ubi_btItemPtr)(Ip), (ubi_btNodePtr *)(On) )
 
 #undef ubi_trRemove
 #define ubi_trRemove( Rp, Dn ) \
-        ubi_avlRemove( (ubi_btRootPtr)(Rp), (ubi_avlNodePtr)(Dn) )
-
-#undef ubi_trLocate
-#define ubi_trLocate( Rp, Ip, Op ) \
-        (ubi_avlNodePtr)ubi_btLocate( (ubi_btRootPtr)(Rp), \
-                                      (ubi_btItemPtr)(Ip), \
-                                      (ubi_trCompOps)(Op) )
-
-#undef ubi_trFind
-#define ubi_trFind( Rp, Ip ) \
-        (ubi_avlNodePtr)ubi_btFind( (ubi_btRootPtr)(Rp), (ubi_btItemPtr)(Ip) )
-
-#undef ubi_trNext
-#define ubi_trNext( P ) (ubi_avlNodePtr)ubi_btNext( (ubi_btNodePtr)(P) )
-
-#undef ubi_trPrev
-#define ubi_trPrev( P ) (ubi_avlNodePtr)ubi_btPrev( (ubi_btNodePtr)(P) )
-
-#undef ubi_trFirst
-#define ubi_trFirst( P ) (ubi_avlNodePtr)ubi_btFirst( (ubi_btNodePtr)(P) )
-
-#undef ubi_trLast
-#define ubi_trLast( P ) (ubi_avlNodePtr)ubi_btLast( (ubi_btNodePtr)(P) )
-
-#undef ubi_trFirstOf
-#define ubi_trFirstOf( Rp, Ip, P ) \
-        (ubi_avlNodePtr)ubi_btFirstOf( (ubi_btRootPtr)(Rp), \
-                       (ubi_btItemPtr)(Ip), \
-                       (ubi_btNodePtr)(P) )
-
-#undef ubi_trLastOf
-#define ubi_trLastOf( Rp, Ip, P ) \
-        (ubi_avlNodePtr)ubi_btLastOf( (ubi_btRootPtr)(Rp), \
-                                      (ubi_btItemPtr)(Ip), \
-                                      (ubi_btNodePtr)(P) )
-
-#undef ubi_trLeafNode
-#define ubi_trLeafNode( Nd ) \
-        (ubi_avlNodePtr)ubi_btLeafNode( (ubi_btNodePtr)(Nd) )
+        ubi_avlRemove( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Dn) )
 
 #undef ubi_trModuleID
 #define ubi_trModuleID( s, l ) ubi_avlModuleID( s, l )
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 */
 
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
@@ -197,6 +206,16 @@ typedef enum {
 #define ubi_trOvwt_OK(A) \
         ((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...
  * 
@@ -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;
 
diff --git a/source3/ubiqx/ubi_SplayTree.c b/source3/ubiqx/ubi_SplayTree.c
index 799996b6cc..89ddfb988a 100644
--- a/source3/ubiqx/ubi_SplayTree.c
+++ b/source3/ubiqx/ubi_SplayTree.c
@@ -1,7 +1,7 @@
 /* ========================================================================== **
  *                              ubi_SplayTree.c
  *
- *  Copyright (C) 1993-1995 by Christopher R. Hertel
+ *  Copyright (C) 1993-1998 by Christopher R. Hertel
  *
  *  Email: crh@ubiqx.mn.org
  * -------------------------------------------------------------------------- **
@@ -16,6 +16,8 @@
  *              Robert Tarjan.  Journal of the Association for Computing
  *              Machinery Vol 32, No. 3, July 1985 pp. 652-686
  *
+ *    See also: http://www.cs.cmu.edu/~sleator/
+ *
  * -------------------------------------------------------------------------- **
  *
  *  This library is free software; you can redistribute it and/or
@@ -35,6 +37,13 @@
  * -------------------------------------------------------------------------- **
  *
  * Log: ubi_SplayTree.c,v
+ * Revision 4.0  1998/03/10 03:41:33  crh
+ * Minor comment changes.  The revision number is now 4.0 to match the
+ * BinTree and AVLtree modules.
+ *
+ * Revision 2.7  1998/01/24 06:37:08  crh
+ * Added a URL for more information.
+ *
  * Revision 2.6  1997/12/23 04:01:12  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
@@ -80,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
@@ -123,8 +131,8 @@
  */
 
 static char ModuleID[] = "ubi_SplayTree\n\
-\tRevision: 2.6\n\
-\tDate: 1997/12/23 04:01:12\n\
+\tRevision: 4.0\n\
+\tDate: 1998/03/10 03:41:33\n\
 \tAuthor: crh\n";
 
 
@@ -466,3 +474,4 @@ int ubi_sptModuleID( int size, char *list[] )
   } /* ubi_sptModuleID */
 
 /* ================================ The End ================================= */
+
diff --git a/source3/ubiqx/ubi_SplayTree.h b/source3/ubiqx/ubi_SplayTree.h
index d45c32fce8..9e55734702 100644
--- a/source3/ubiqx/ubi_SplayTree.h
+++ b/source3/ubiqx/ubi_SplayTree.h
@@ -3,7 +3,7 @@
 /* ========================================================================== **
  *                              ubi_SplayTree.h
  *
- *  Copyright (C) 1993,1995 by Christopher R. Hertel
+ *  Copyright (C) 1993-1998 by Christopher R. Hertel
  *
  *  Email: crh@ubiqx.mn.org
  * -------------------------------------------------------------------------- **
@@ -18,6 +18,8 @@
  *              Robert Tarjan.  Journal of the Association for Computing
  *              Machinery Vol 32, No. 3, July 1985 pp. 652-686
  *
+ *    See also: http://www.cs.cmu.edu/~sleator/ 
+ *
  * -------------------------------------------------------------------------- **
  *
  *  This library is free software; you can redistribute it and/or
@@ -37,6 +39,13 @@
  * -------------------------------------------------------------------------- **
  *
  * Log: ubi_SplayTree.h,v
+ * Revision 4.0  1998/03/10 03:40:57  crh
+ * Minor comment changes.  The revision number is now 4.0 to match the
+ * BinTree and AVLtree modules.
+ *
+ * Revision 2.7  1998/01/24 06:37:57  crh
+ * Added a URL for more information.
+ *
  * Revision 2.6  1997/12/23 04:02:20  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 +88,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
@@ -328,8 +336,3 @@ int ubi_sptModuleID( int size, char *list[] );
 
 /* ================================ The End ================================= */
 #endif /* ubi_SplayTree_H */
-
-
-
-
-
diff --git a/source3/ubiqx/ubi_dLinkList.c b/source3/ubiqx/ubi_dLinkList.c
index 5d970a9ca1..c903dcbc04 100644
--- a/source3/ubiqx/ubi_dLinkList.c
+++ b/source3/ubiqx/ubi_dLinkList.c
@@ -1,7 +1,7 @@
 /* ========================================================================== **
  *                              ubi_dLinkList.c
  *
- *  Copyright (C) 1997 by Christopher R. Hertel
+ *  Copyright (C) 1997, 1998 by Christopher R. Hertel
  *
  *  Email: crh@ubiqx.mn.org
  * -------------------------------------------------------------------------- **
@@ -24,6 +24,13 @@
  *
  * -------------------------------------------------------------------------- **
  *
+ * Log: ubi_dLinkList.c,v
+ * Revision 0.5  1998/03/10 02:55:00  crh
+ * Simplified the code and added macros for stack & queue manipulations.
+ *
+ * Revision 0.4  1998/01/03 01:53:56  crh
+ * Added ubi_dlCount() macro.
+ *
  * Revision 0.3  1997/10/15 03:05:39  crh
  * Added some handy type casting to the macros.  Added AddHere and RemThis
  * macros.
@@ -35,11 +42,16 @@
  * Revision 0.1  1997/10/07 04:34:07  crh
  * Initial Revision.
  *
+ * -------------------------------------------------------------------------- **
+ * This module is similar to the ubi_sLinkList module, but it is neither a
+ * descendant type nor an easy drop-in replacement for the latter.  One key
+ * difference is that the ubi_dlRemove() function removes the indicated node,
+ * while the ubi_slRemove() function (in ubi_sLinkList) removes the node
+ * *following* the indicated node.
  *
  * ========================================================================== **
  */
 
-#include "../includes.h"
 #include "ubi_dLinkList.h"
 
 /* ========================================================================== **
@@ -85,28 +97,17 @@ ubi_dlNodePtr ubi_dlInsert( ubi_dlListPtr ListPtr,
    * ------------------------------------------------------------------------ **
    */
   {
-  if( NULL == After )
-    {
-    New->Next           = ListPtr->Head;
-    New->Prev           = NULL;
-    if( NULL != ListPtr->Head )
-      ListPtr->Head->Prev = New;
-    else
-      ListPtr->Tail       = New;
-    ListPtr->Head       = New;
-    }
+  ubi_dlNodePtr PredNode = After ? After : (ubi_dlNodePtr)ListPtr;
+
+  New->Next         = PredNode->Next;
+  New->Prev         = After;
+  PredNode->Next    = New;
+  if( New->Next )
+    New->Next->Prev = New;
   else
-    {
-    New->Next         = After->Next;
-    New->Prev         = After;
-    if( NULL != After->Next )
-      After->Next->Prev = New;
-    else
-      ListPtr->Tail       = New;
-    After->Next       = New;
-    }
+    ListPtr->Tail   = New;
 
-  ++(ListPtr->count);
+  (ListPtr->count)++;
 
   return( New );
   } /* ubi_dlInsert */
@@ -125,7 +126,7 @@ ubi_dlNodePtr ubi_dlRemove( ubi_dlListPtr ListPtr, ubi_dlNodePtr Old )
    * ------------------------------------------------------------------------ **
    */
   {
-  if( NULL != Old )
+  if( Old )
     {
     if( Old->Next )
       Old->Next->Prev = Old->Prev;
@@ -137,11 +138,10 @@ ubi_dlNodePtr ubi_dlRemove( ubi_dlListPtr ListPtr, ubi_dlNodePtr Old )
     else
       ListPtr->Head = Old->Next;
 
-    --(ListPtr->count);
+    (ListPtr->count)--;
     }
 
   return( Old );
   } /* ubi_dlRemove */
 
-
 /* ================================ The End ================================= */
diff --git a/source3/ubiqx/ubi_dLinkList.h b/source3/ubiqx/ubi_dLinkList.h
index 1facf92d3b..9c6a3be2e2 100644
--- a/source3/ubiqx/ubi_dLinkList.h
+++ b/source3/ubiqx/ubi_dLinkList.h
@@ -3,7 +3,7 @@
 /* ========================================================================== **
  *                              ubi_dLinkList.h
  *
- *  Copyright (C) 1997 by Christopher R. Hertel
+ *  Copyright (C) 1997, 1998 by Christopher R. Hertel
  *
  *  Email: crh@ubiqx.mn.org
  * -------------------------------------------------------------------------- **
@@ -26,6 +26,13 @@
  *
  * -------------------------------------------------------------------------- **
  *
+ * Log: ubi_dLinkList.h,v
+ * Revision 0.5  1998/03/10 02:54:04  crh
+ * Simplified the code and added macros for stack & queue manipulations.
+ *
+ * Revision 0.4  1998/01/03 01:53:44  crh
+ * Added ubi_dlCount() macro.
+ *
  * Revision 0.3  1997/10/15 03:04:31  crh
  * Added some handy type casting to the macros.  Added AddHere and RemThis
  * macros.
@@ -37,6 +44,12 @@
  * Revision 0.1  1997/10/07 04:34:38  crh
  * Initial Revision.
  *
+ * -------------------------------------------------------------------------- **
+ * This module is similar to the ubi_sLinkList module, but it is neither a
+ * descendant type nor an easy drop-in replacement for the latter.  One key
+ * difference is that the ubi_dlRemove() function removes the indicated node,
+ * while the ubi_slRemove() function (in ubi_sLinkList) removes the node
+ * *following* the indicated node.
  *
  * ========================================================================== **
  */
@@ -73,46 +86,63 @@ typedef ubi_dlList *ubi_dlListPtr;
 
 /* ========================================================================== **
  * Macros...
- * 
+ *
+ *  ubi_dlCount   - Return the number of entries currently in the list.
+ *
  *  ubi_dlAddHead - Add a new node at the head of the list.
+ *  ubi_dlAddNext - Add a node following the given node.
  *  ubi_dlAddTail - Add a new node at the tail of the list.
- *  ubi_dlAddHere - Add a node following the given node.
+ *                  Note: AddTail evaluates the L parameter twice.
+ *
  *  ubi_dlRemHead - Remove the node at the head of the list, if any.
- *  ubi_dlRemTail - Remove the node at the tail of the list, if any.
+ *                  Note: RemHead evaluates the L parameter twice.
  *  ubi_dlRemThis - Remove the indicated node.
+ *  ubi_dlRemTail - Remove the node at the tail of the list, if any.
+ *                  Note: RemTail evaluates the L parameter twice.
+ *
  *  ubi_dlFirst   - Return a pointer to the first node in the list, if any.
  *  ubi_dlLast    - Return a pointer to the last node in the list, if any.
  *  ubi_dlNext    - Given a node, return a pointer to the next node.
  *  ubi_dlPrev    - Given a node, return a pointer to the previous node.
  *
+ *  ubi_dlPush    - Add a node at the head of the list (synonym of AddHead).
+ *  ubi_dlPop     - Remove a node at the head of the list (synonym of RemHead).
+ *  ubi_dlEnqueue - Add a node at the tail of the list (sysnonym of AddTail).
+ *  ubi_dlDequeue - Remove a node at the head of the list (synonym of RemHead).
+ *
  *  Note that all of these provide type casting of the parameters.  The
  *  Add and Rem macros are nothing more than nice front-ends to the
  *  Insert and Remove operations.
  *
+ *  Also note that there the First, Next and Last macros do no parameter
+ *  checking!
+ *
  */
 
+#define ubi_dlCount( L ) (((ubi_dlListPtr)(L))->count)
+
 #define ubi_dlAddHead( L, N ) \
         ubi_dlInsert( (ubi_dlListPtr)(L), (ubi_dlNodePtr)(N), NULL )
 
-#define ubi_dlAddTail( L, N ) \
+#define ubi_dlAddNext( L, N, A ) \
         ubi_dlInsert( (ubi_dlListPtr)(L), \
                       (ubi_dlNodePtr)(N), \
-                    (((ubi_dlListPtr)(L))->Tail) )
+                      (ubi_dlNodePtr)(A) )
 
-#define ubi_dlAddHere( L, N, P ) \
+#define ubi_dlAddTail( L, N ) \
         ubi_dlInsert( (ubi_dlListPtr)(L), \
                       (ubi_dlNodePtr)(N), \
-                      (ubi_dlNodePtr)(P) )
+                    (((ubi_dlListPtr)(L))->Tail) )
 
 #define ubi_dlRemHead( L ) ubi_dlRemove( (ubi_dlListPtr)(L), \
                                          (((ubi_dlListPtr)(L))->Head) )
 
-#define ubi_dlRemTail( L ) ubi_dlRemove( (ubi_dlListPtr)(L), \
-                                         (((ubi_dlListPtr)(L))->Tail) )
-
 #define ubi_dlRemThis( L, N ) ubi_dlRemove( (ubi_dlListPtr)(L), \
                                             (ubi_dlNodePtr)(N) )
 
+#define ubi_dlRemTail( L ) ubi_dlRemove( (ubi_dlListPtr)(L), \
+                                         (((ubi_dlListPtr)(L))->Tail) )
+
 #define ubi_dlFirst( L ) (((ubi_dlListPtr)(L))->Head)
 
 #define ubi_dlLast( L )  (((ubi_dlListPtr)(L))->Tail)
@@ -121,6 +151,10 @@ typedef ubi_dlList *ubi_dlListPtr;
 
 #define ubi_dlPrev( N )  (((ubi_dlNodePtr)(N))->Prev)
 
+#define ubi_dlPush    ubi_dlAddHead
+#define ubi_dlPop     ubi_dlRemHead
+#define ubi_dlEnqueue ubi_dlAddTail
+#define ubi_dlDequeue ubi_dlRemHead
 
 /* ========================================================================== **
  * Function prototypes...
@@ -173,6 +207,5 @@ ubi_dlNodePtr ubi_dlRemove( ubi_dlListPtr ListPtr, ubi_dlNodePtr Old );
    * ------------------------------------------------------------------------ **
    */
 
-
 /* ================================ The End ================================= */
 #endif /* ubi_dLinkList_H */
diff --git a/source3/ubiqx/ubi_sLinkList.c b/source3/ubiqx/ubi_sLinkList.c
index 5414d5f71d..3dc4f0640c 100644
--- a/source3/ubiqx/ubi_sLinkList.c
+++ b/source3/ubiqx/ubi_sLinkList.c
@@ -1,11 +1,11 @@
 /* ========================================================================== **
  *                              ubi_sLinkList.c
  *
- *  Copyright (C) 1997 by Christopher R. Hertel
+ *  Copyright (C) 1997, 1998 by Christopher R. Hertel
  *
  *  Email: crh@ubiqx.mn.org
  * -------------------------------------------------------------------------- **
- *  This module implements a really simple singly-linked list.
+ *  This module implements a simple singly-linked list.
  * -------------------------------------------------------------------------- **
  *
  *  This library is free software; you can redistribute it and/or
@@ -24,6 +24,14 @@
  *
  * -------------------------------------------------------------------------- **
  *
+ * Log: ubi_sLinkList.c,v
+ * Revision 0.4  1998/03/10 02:23:20  crh
+ * Combined ubi_StackQueue and ubi_sLinkList into one module.  Redesigned
+ * the functions and macros.  Not a complete rewrite but close to it.
+ *
+ * Revision 0.3  1998/01/03 01:59:52  crh
+ * Added ubi_slCount() macro.
+ *
  * Revision 0.2  1997/10/21 03:35:18  crh
  * Added parameter <After> in function Insert().  Made necessary changes
  * to macro AddHead() and added macro AddHere().
@@ -31,6 +39,36 @@
  * Revision 0.1  1997/10/16 02:53:45  crh
  * Initial Revision.
  *
+ * -------------------------------------------------------------------------- **
+ *  This module implements a singly-linked list which may also be used as a
+ *  queue or a stack.  For a queue, entries are added at the tail and removed
+ *  from the head of the list.  For a stack, the entries are entered and
+ *  removed from the head of the list.  A traversal of the list will always
+ *  start at the head of the list and proceed toward the tail.  This is all
+ *  mind-numbingly simple, but I'm surprised by the number of programs out
+ *  there which re-implement this a dozen or so times.
+ *
+ *  Notes:  When the list header is initialized, the Tail pointer is set to
+ *          point to the Head pointer.  This simplifies things a great deal,
+ *          except that you can't initialize a stack or queue by simply
+ *          zeroing it out.  One sure way to initialize the header is to call
+ *          ubi_slInit().  Another option would be something like this:
+ *
+ *          static ubi_slList MyList = { NULL, (ubi_slNodePtr)&MyList, 0 };
+ *
+ *          See ubi_slInit() and the ubi_slList structure for more info.
+ *
+ *        + Also, note that this module is similar to the ubi_dLinkList
+ *          module.  There are three key differences:
+ *          - This is a singly-linked list, the other is a doubly-linked
+ *            list.
+ *          - In this module, if the list is empty, the tail pointer will
+ *            point back to the head of the list as described above.  This
+ *            is not done in ubi_dLinkList.
+ *          - The ubi_slRemove() function, by necessity, removed the 'next'
+ *            node.  In ubi_dLinkList, the ubi_dlRemove() function removes
+ *            the 'current' node.
+ *
  * ========================================================================== **
  */
 
@@ -54,6 +92,7 @@ ubi_slListPtr ubi_slInitList( ubi_slListPtr ListPtr )
    */
   {
   ListPtr->Head  = NULL;
+  ListPtr->Tail  = (ubi_slNodePtr)ListPtr;
   ListPtr->count = 0;
   return( ListPtr );
   } /* ubi_slInitList */
@@ -62,7 +101,7 @@ ubi_slNodePtr ubi_slInsert( ubi_slListPtr ListPtr,
                             ubi_slNodePtr New,
                             ubi_slNodePtr After )
   /* ------------------------------------------------------------------------ **
-   * Insert a new node at the head of the list.
+   * Add a node to the list.
    *
    *  Input:  ListPtr - A pointer to the list into which the node is to
    *                    be inserted.
@@ -77,36 +116,43 @@ ubi_slNodePtr ubi_slInsert( ubi_slListPtr ListPtr,
    * ------------------------------------------------------------------------ **
    */
   {
-  ubi_slNodePtr *PredPtr;
-
-  PredPtr = ( NULL == After ) ? &(ListPtr->Head) : &(After->Next);
-  New->Next = *PredPtr;
-  *PredPtr  = New;
-  ++(ListPtr->count);
+  After = After ? After : (ubi_slNodePtr)ListPtr;
+  New->Next   = After->Next;
+  After->Next = New;
+  if( !(New->Next) )
+    ListPtr->Tail = New;
+  (ListPtr->count)++;
   return( New );
   } /* ubi_slInsert */
 
-ubi_slNodePtr ubi_slRemove( ubi_slListPtr ListPtr )
+ubi_slNodePtr ubi_slRemove( ubi_slListPtr ListPtr, ubi_slNodePtr After )
   /* ------------------------------------------------------------------------ **
-   * Remove a node from the head of the list.
+   * Remove the node followng <After>.  If <After> is NULL, remove from the
+   * head of the list.
    *
    *  Input:  ListPtr - A pointer to the list from which the node is to be
    *                    removed.
+   *          After   - Pointer to the node preceeding the node to be
+   *                    removed.
    *
-   *  Output: A pointer to the node that was removed.
+   *  Output: A pointer to the node that was removed, or NULL if the list is
+   *          empty.
    *
    * ------------------------------------------------------------------------ **
    */
   {
-  ubi_slNodePtr Old = ListPtr->Head;
+  ubi_slNodePtr DelNode;
 
-  if( NULL != Old )
+  After   = After ? After : (ubi_slNodePtr)ListPtr;
+  DelNode = After->Next;
+  if( DelNode )
     {
-    ListPtr->Head = Old->Next;
-    --(ListPtr->count);
+    if( !(DelNode->Next) )
+      ListPtr->Tail = After;
+    After->Next  = DelNode->Next;
+    (ListPtr->count)--;
     }
-  return( Old );
+  return( DelNode );
   } /* ubi_slRemove */
 
-
 /* ================================ The End ================================= */
diff --git a/source3/ubiqx/ubi_sLinkList.h b/source3/ubiqx/ubi_sLinkList.h
index 7d546f06e9..2275d852da 100644
--- a/source3/ubiqx/ubi_sLinkList.h
+++ b/source3/ubiqx/ubi_sLinkList.h
@@ -3,11 +3,11 @@
 /* ========================================================================== **
  *                              ubi_sLinkList.h
  *
- *  Copyright (C) 1997 by Christopher R. Hertel
+ *  Copyright (C) 1997, 1998 by Christopher R. Hertel
  *
  *  Email: crh@ubiqx.mn.org
  * -------------------------------------------------------------------------- **
- *  This module implements a really simple singly-linked list.
+ *  This module implements a simple singly-linked list.
  * -------------------------------------------------------------------------- **
  *
  *  This library is free software; you can redistribute it and/or
@@ -26,6 +26,14 @@
  *
  * -------------------------------------------------------------------------- **
  *
+ * Log: ubi_sLinkList.h,v
+ * Revision 0.4  1998/03/10 02:22:39  crh
+ * Combined ubi_StackQueue and ubi_sLinkList into one module.  Redesigned
+ * the functions and macros.  Not a complete rewrite but close to it.
+ *
+ * Revision 0.3  1998/01/03 02:00:02  crh
+ * Added ubi_slCount() macro.
+ *
  * Revision 0.2  1997/10/21 03:36:14  crh
  * Added parameter <After> in function Insert().  Made necessary changes
  * to macro AddHead() and added macro AddHere().
@@ -33,6 +41,36 @@
  * Revision 0.1  1997/10/16 02:54:08  crh
  * Initial Revision.
  *
+ * -------------------------------------------------------------------------- **
+ *  This module implements a singly-linked list which may also be used as a 
+ *  queue or a stack.  For a queue, entries are added at the tail and removed
+ *  from the head of the list.  For a stack, the entries are entered and
+ *  removed from the head of the list.  A traversal of the list will always
+ *  start at the head of the list and proceed toward the tail.  This is all
+ *  mind-numbingly simple, but I'm surprised by the number of programs out
+ *  there which re-implement this a dozen or so times.
+ *
+ *  Note:  When the list header is initialized, the Tail pointer is set to
+ *         point to the Head pointer.  This simplifies things a great deal,
+ *         except that you can't initialize a stack or queue by simply
+ *         zeroing it out.  One sure way to initialize the header is to call
+ *         ubi_slInit().  Another option would be something like this:
+ *
+ *         static ubi_slList MyList = { NULL, (ubi_slNodePtr)&MyList, 0 };
+ *
+ *         See ubi_slInit() and the ubi_slList structure for more info.
+ *
+ *        + Also, note that this module is similar to the ubi_dLinkList
+ *          module.  There are three key differences:
+ *          - This is a singly-linked list, the other is a doubly-linked
+ *            list.
+ *          - In this module, if the list is empty, the tail pointer will
+ *            point back to the head of the list as described above.  This
+ *            is not done in ubi_dLinkList.
+ *          - The ubi_slRemove() function, by necessity, removed the 'next'
+ *            node.  In ubi_dLinkList, the ubi_dlRemove() function removes
+ *            the 'current' node. 
+ *
  * ========================================================================== **
  */
 
@@ -59,6 +97,7 @@ typedef ubi_slNode *ubi_slNodePtr;
 typedef struct
   {
   ubi_slNodePtr Head;
+  ubi_slNodePtr Tail;
   unsigned long count;
   } ubi_slList;
 
@@ -67,31 +106,64 @@ typedef ubi_slList *ubi_slListPtr;
 /* ========================================================================== **
  * Macros...
  * 
+ *  ubi_slCount   - Returns the current number of entries in the list.
+ *
  *  ubi_slAddHead - Add a new node at the head of the list.
+ *  ubi_slAddNext - Add a new node following the indicated node.
+ *  ubi_slAddTail - Add a new node to the tail of the list.
+ *                  Note: AddTail evaluates the L parameter twice.
+ *
  *  ubi_slRemHead - Remove the node at the head of the list, if any.
+ *  ubi_slRemNext - Remove the node following the given node.
+ *
  *  ubi_slFirst   - Return a pointer to the first node in the list, if any.
  *  ubi_slNext    - Given a node, return a pointer to the next node.
+ *  ubi_slLast    - Return a pointer to the last node in the list, if any.
+ *
+ *  ubi_slPush    - Add a node at the head of the list (synonym of AddHead).
+ *  ubi_slPop     - Remove a node at the head of the list (synonym of RemHead).
+ *  ubi_slEnqueue - Add a node at the tail of the list (sysnonym of AddTail).
+ *  ubi_slDequeue - Remove a node at the head of the list (synonym of RemHead).
  *
  *  Note that all of these provide type casting of the parameters.  The
  *  Add and Rem macros are nothing more than nice front-ends to the
- *  Insert and Remove operations.
+ *  Insert and Remove functions.
+ *
+ *  Also note that there the First, Next and Last macros do no parameter
+ *  checking!
  *
  */
 
+#define ubi_slCount( L ) (((ubi_slListPtr)(L))->count)
+
 #define ubi_slAddHead( L, N ) \
         ubi_slInsert( (ubi_slListPtr)(L), (ubi_slNodePtr)(N), NULL )
 
-#define ubi_slAddHere( L, N, P ) \
+#define ubi_slAddNext( L, N, A ) \
+        ubi_slInsert( (ubi_slListPtr)(L), \
+                      (ubi_slNodePtr)(N), \
+                      (ubi_slNodePtr)(A) )
+
+#define ubi_slAddTail( L, N ) \
         ubi_slInsert( (ubi_slListPtr)(L), \
                       (ubi_slNodePtr)(N), \
-                      (ubi_slNodePtr)(P) )
+                     ((ubi_slListPtr)(L))->Tail )
+
+#define ubi_slRemHead( L ) ubi_slRemove( (ubi_slListPtr)(L), NULL )
 
-#define ubi_slRemHead( L ) ubi_slRemove( (ubi_slListPtr)(L) )
+#define ubi_slRemNext( L, N ) \
+        ubi_slRemove( (ubi_slListPtr)(L), (ubi_slNodePtr)(N) )
 
 #define ubi_slFirst( L ) (((ubi_slListPtr)(L))->Head)
 
 #define ubi_slNext( N )  (((ubi_slNodePtr)(N))->Next)
 
+#define ubi_slLast( L )  (((ubi_slListPtr)(L))->Tail)
+
+#define ubi_slPush    ubi_slAddHead
+#define ubi_slPop     ubi_slRemHead
+#define ubi_slEnqueue ubi_slAddTail
+#define ubi_slDequeue ubi_slRemHead
 
 /* ========================================================================== **
  * Function prototypes...
@@ -114,7 +186,7 @@ ubi_slNodePtr ubi_slInsert( ubi_slListPtr ListPtr,
                             ubi_slNodePtr New,
                             ubi_slNodePtr After );
   /* ------------------------------------------------------------------------ **
-   * Insert a new node at the head of the list.
+   * Add a node to the list.
    *
    *  Input:  ListPtr - A pointer to the list into which the node is to
    *                    be inserted.
@@ -129,14 +201,18 @@ ubi_slNodePtr ubi_slInsert( ubi_slListPtr ListPtr,
    * ------------------------------------------------------------------------ **
    */
 
-ubi_slNodePtr ubi_slRemove( ubi_slListPtr ListPtr );
+ubi_slNodePtr ubi_slRemove( ubi_slListPtr ListPtr, ubi_slNodePtr After );
   /* ------------------------------------------------------------------------ **
-   * Remove a node from the head of the list.
+   * Remove the node followng <After>.  If <After> is NULL, remove from the
+   * head of the list.
    *
    *  Input:  ListPtr - A pointer to the list from which the node is to be
    *                    removed.
+   *          After   - Pointer to the node preceeding the node to be
+   *                    removed.
    *
-   *  Output: A pointer to the node that was removed.
+   *  Output: A pointer to the node that was removed, or NULL if the list is
+   *          empty.
    *
    * ------------------------------------------------------------------------ **
    */
-- 
cgit