1 #ifndef ubi_sLinkList_H
2 #define ubi_sLinkList_H
3 /* ========================================================================== **
6 * Copyright (C) 1997, 1998 by Christopher R. Hertel
8 * Email: crh@ubiqx.mn.org
9 * -------------------------------------------------------------------------- **
10 * This module implements a simple singly-linked list.
11 * -------------------------------------------------------------------------- **
13 * This library is free software; you can redistribute it and/or
14 * modify it under the terms of the GNU Library General Public
15 * License as published by the Free Software Foundation; either
16 * version 2 of the License, or (at your option) any later version.
18 * This library is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 * Library General Public License for more details.
23 * You should have received a copy of the GNU Library General Public
24 * License along with this library; if not, write to the Free
25 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
27 * -------------------------------------------------------------------------- **
29 * Log: ubi_sLinkList.h,v
30 * Revision 0.6 1998/06/02 01:38:47 crh
31 * Changed include file name from ubi_null.h to sys_include.h to make it
34 * Revision 0.5 1998/05/20 04:38:05 crh
35 * The C file now includes ubi_null.h. See ubi_null.h for more info.
37 * Revision 0.4 1998/03/10 02:22:39 crh
38 * Combined ubi_StackQueue and ubi_sLinkList into one module. Redesigned
39 * the functions and macros. Not a complete rewrite but close to it.
41 * Revision 0.3 1998/01/03 02:00:02 crh
42 * Added ubi_slCount() macro.
44 * Revision 0.2 1997/10/21 03:36:14 crh
45 * Added parameter <After> in function Insert(). Made necessary changes
46 * to macro AddHead() and added macro AddHere().
48 * Revision 0.1 1997/10/16 02:54:08 crh
51 * -------------------------------------------------------------------------- **
52 * This module implements a singly-linked list which may also be used as a
53 * queue or a stack. For a queue, entries are added at the tail and removed
54 * from the head of the list. For a stack, the entries are entered and
55 * removed from the head of the list. A traversal of the list will always
56 * start at the head of the list and proceed toward the tail. This is all
57 * mind-numbingly simple, but I'm surprised by the number of programs out
58 * there which re-implement this a dozen or so times.
60 * Note: When the list header is initialized, the Tail pointer is set to
61 * point to the Head pointer. This simplifies things a great deal,
62 * except that you can't initialize a stack or queue by simply
63 * zeroing it out. One sure way to initialize the header is to call
64 * ubi_slInit(). Another option would be something like this:
66 * static ubi_slList MyList = { NULL, (ubi_slNodePtr)&MyList, 0 };
68 * See ubi_slInit() and the ubi_slList structure for more info.
70 * + Also, note that this module is similar to the ubi_dLinkList
71 * module. There are three key differences:
72 * - This is a singly-linked list, the other is a doubly-linked
74 * - In this module, if the list is empty, the tail pointer will
75 * point back to the head of the list as described above. This
76 * is not done in ubi_dLinkList.
77 * - The ubi_slRemove() function, by necessity, removed the 'next'
78 * node. In ubi_dLinkList, the ubi_dlRemove() function removes
81 * ========================================================================== **
85 /* ========================================================================== **
88 * ubi_slNode - This is the basic node structure.
89 * ubi_slNodePtr - Pointer to a node.
90 * ubi_slList - This is the list header structure.
91 * ubi_slListPtr - Pointer to a List (i.e., a list header structure).
95 typedef struct ubi_slListNode
97 struct ubi_slListNode *Next;
100 typedef ubi_slNode *ubi_slNodePtr;
109 typedef ubi_slList *ubi_slListPtr;
111 /* ========================================================================== **
114 * ubi_slCount - Returns the current number of entries in the list.
116 * ubi_slAddHead - Add a new node at the head of the list.
117 * ubi_slAddNext - Add a new node following the indicated node.
118 * ubi_slAddTail - Add a new node to the tail of the list.
119 * Note: AddTail evaluates the L parameter twice.
121 * ubi_slRemHead - Remove the node at the head of the list, if any.
122 * ubi_slRemNext - Remove the node following the given node.
124 * ubi_slFirst - Return a pointer to the first node in the list, if any.
125 * ubi_slNext - Given a node, return a pointer to the next node.
126 * ubi_slLast - Return a pointer to the last node in the list, if any.
128 * ubi_slPush - Add a node at the head of the list (synonym of AddHead).
129 * ubi_slPop - Remove a node at the head of the list (synonym of RemHead).
130 * ubi_slEnqueue - Add a node at the tail of the list (sysnonym of AddTail).
131 * ubi_slDequeue - Remove a node at the head of the list (synonym of RemHead).
133 * Note that all of these provide type casting of the parameters. The
134 * Add and Rem macros are nothing more than nice front-ends to the
135 * Insert and Remove functions.
137 * Also note that there the First, Next and Last macros do no parameter
142 #define ubi_slCount( L ) (((ubi_slListPtr)(L))->count)
144 #define ubi_slAddHead( L, N ) \
145 ubi_slInsert( (ubi_slListPtr)(L), (ubi_slNodePtr)(N), NULL )
147 #define ubi_slAddNext( L, N, A ) \
148 ubi_slInsert( (ubi_slListPtr)(L), \
149 (ubi_slNodePtr)(N), \
152 #define ubi_slAddTail( L, N ) \
153 ubi_slInsert( (ubi_slListPtr)(L), \
154 (ubi_slNodePtr)(N), \
155 ((ubi_slListPtr)(L))->Tail )
157 #define ubi_slRemHead( L ) ubi_slRemove( (ubi_slListPtr)(L), NULL )
159 #define ubi_slRemNext( L, N ) \
160 ubi_slRemove( (ubi_slListPtr)(L), (ubi_slNodePtr)(N) )
162 #define ubi_slFirst( L ) (((ubi_slListPtr)(L))->Head)
164 #define ubi_slNext( N ) (((ubi_slNodePtr)(N))->Next)
166 #define ubi_slLast( L ) (((ubi_slListPtr)(L))->Tail)
168 #define ubi_slPush ubi_slAddHead
169 #define ubi_slPop ubi_slRemHead
170 #define ubi_slEnqueue ubi_slAddTail
171 #define ubi_slDequeue ubi_slRemHead
173 /* ========================================================================== **
174 * Function prototypes...
177 ubi_slListPtr ubi_slInitList( ubi_slListPtr ListPtr );
178 /* ------------------------------------------------------------------------ **
179 * Initialize a singly-linked list header.
181 * Input: ListPtr - A pointer to the list structure that is to be
182 * initialized for use.
184 * Output: A pointer to the initialized list header (i.e., same as
187 * ------------------------------------------------------------------------ **
190 ubi_slNodePtr ubi_slInsert( ubi_slListPtr ListPtr,
192 ubi_slNodePtr After );
193 /* ------------------------------------------------------------------------ **
194 * Add a node to the list.
196 * Input: ListPtr - A pointer to the list into which the node is to
198 * New - Pointer to the node that is to be added to the list.
199 * After - Pointer to a list in a node after which the new node
200 * will be inserted. If NULL, then the new node will
201 * be added at the head of the list.
203 * Output: A pointer to the node that was inserted into the list (i.e.,
204 * the same as <New>).
206 * ------------------------------------------------------------------------ **
209 ubi_slNodePtr ubi_slRemove( ubi_slListPtr ListPtr, ubi_slNodePtr After );
210 /* ------------------------------------------------------------------------ **
211 * Remove the node followng <After>. If <After> is NULL, remove from the
214 * Input: ListPtr - A pointer to the list from which the node is to be
216 * After - Pointer to the node preceeding the node to be
219 * Output: A pointer to the node that was removed, or NULL if the list is
222 * ------------------------------------------------------------------------ **
225 /* ================================ The End ================================= */
226 #endif /* ubi_sLinkList_H */