From 87d4fc1d225ab0aa5bac2b104d7958065a453144 Mon Sep 17 00:00:00 2001 From: "Christopher R. Hertel" 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_dLinkList.h | 57 ++++++++++++++++++++++++++++++++++--------- 1 file changed, 45 insertions(+), 12 deletions(-) (limited to 'source3/ubiqx/ubi_dLinkList.h') 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 */ -- cgit