summaryrefslogtreecommitdiff
path: root/source3/ubiqx/ubi_AVLtree.h
diff options
context:
space:
mode:
authorChristopher R. Hertel <crh@samba.org>1998-03-10 15:39:41 +0000
committerChristopher R. Hertel <crh@samba.org>1998-03-10 15:39:41 +0000
commit87d4fc1d225ab0aa5bac2b104d7958065a453144 (patch)
tree2d741498eb38ad36c46621cbaef111490effd590 /source3/ubiqx/ubi_AVLtree.h
parentc0b06785c11eca0e037febfe887ce9dbb776d4e4 (diff)
downloadsamba-87d4fc1d225ab0aa5bac2b104d7958065a453144.tar.gz
samba-87d4fc1d225ab0aa5bac2b104d7958065a453144.tar.bz2
samba-87d4fc1d225ab0aa5bac2b104d7958065a453144.zip
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)
Diffstat (limited to 'source3/ubiqx/ubi_AVLtree.h')
-rw-r--r--source3/ubiqx/ubi_AVLtree.h131
1 files changed, 22 insertions, 109 deletions
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 )