diff options
author | Christopher R. Hertel <crh@samba.org> | 1998-03-10 15:39:41 +0000 |
---|---|---|
committer | Christopher R. Hertel <crh@samba.org> | 1998-03-10 15:39:41 +0000 |
commit | 87d4fc1d225ab0aa5bac2b104d7958065a453144 (patch) | |
tree | 2d741498eb38ad36c46621cbaef111490effd590 /source3/ubiqx/ubi_BinTree.c | |
parent | c0b06785c11eca0e037febfe887ce9dbb776d4e4 (diff) | |
download | samba-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_BinTree.c')
-rw-r--r-- | source3/ubiqx/ubi_BinTree.c | 28 |
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 */ |