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_sLinkList.c | 82 +++++++++++++++++++++++++++++++++---------- 1 file changed, 64 insertions(+), 18 deletions(-) (limited to 'source3/ubiqx/ubi_sLinkList.c') 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 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 . If 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 ================================= */ -- cgit