2 * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
3 * Copyright (c) 1988, 1989 by Adam de Boor
4 * Copyright (c) 1989 by Berkeley Softworks
7 * This code is derived from software contributed to Berkeley by
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. All advertising materials mentioning features or use of this software
19 * must display the following acknowledgement:
20 * This product includes software developed by the University of
21 * California, Berkeley and its contributors.
22 * 4. Neither the name of the University nor the names of its contributors
23 * may be used to endorse or promote products derived from this software
24 * without specific prior written permission.
26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38 * from: @(#)list.h 8.1 (Berkeley) 6/6/93
39 * $FreeBSD: src/usr.bin/make/list.h,v 1.8 1999/08/28 01:03:32 peter Exp $
40 * $DragonFly: src/usr.bin/make/Attic/list.h,v 1.2 2003/06/17 04:29:29 dillon Exp $
46 * Structures, macros, and routines exported by the List module.
57 * This module defines the list abstraction, which enables one to link
58 * together arbitrary data structures. Lists are doubly-linked and
59 * circular. A list contains a header followed by its real members, if
60 * any. (An empty list therefore consists of a single element, the
61 * header, whose nextPtr and prevPtr fields point to itself). To refer
62 * to a list as a whole, the user keeps a pointer to the header; that
63 * header is initialized by a call to List_Init(), which creates an empty
64 * list given a pointer to a List_Links structure (described below).
66 * The links are contained in a two-element structure called List_Links.
67 * A list joins List_Links records (that is, each List_Links structure
68 * points to other List_Links structures), but if the List_Links is the
69 * first field within a larger structure, then the larger structures are
70 * effectively linked together as follows:
73 * (List_Links) first elt. second elt.
74 * ----------------- ----------------- -----------------
75 * ..-> | nextPtr | ----> | List_Links | ----> | List_Links |----..
76 * | - - - - - - - | | | | |
77 * ..-- | prevPtr | <---- | | <---- | |<---..
78 * ----------------- - --- --- --- - - --- --- --- -
79 * | rest of | | rest of |
80 * | structure | | structure |
83 * ----------------- -----------------
85 * It is possible to link structures through List_Links fields that are
86 * not at the beginning of the larger structure, but it is then necessary
87 * to perform pointer arithmetic to find the beginning of the larger
88 * structure, given a pointer to some point within it.
90 * A typical structure might be something like:
98 * Before an element is inserted in a list for the first time, it must
99 * be initialized by calling the macro List_InitElement().
104 * data structure for lists
107 typedef struct List_Links {
108 struct List_Links *prevPtr;
109 struct List_Links *nextPtr;
116 void List_Init(); /* initialize a header to a list */
117 void List_Insert(); /* insert an element into a list */
118 void List_Remove(); /* remove an element from a list */
119 void List_Move(); /* move an element elsewhere in a list */
122 * ----------------------------------------------------------------------------
124 * List_InitElement --
126 * Initialize a list element. Must be called before an element is first
127 * inserted into a list.
129 * ----------------------------------------------------------------------------
131 #define List_InitElement(elementPtr) \
132 (elementPtr)->prevPtr = (List_Links *) NIL; \
133 (elementPtr)->nextPtr = (List_Links *) NIL;
136 * Macros for stepping through or selecting parts of lists
140 * ----------------------------------------------------------------------------
144 * Macro to loop through a list and perform an operation on each member.
146 * Usage: LIST_FORALL(headerPtr, itemPtr) {
148 * * operation on itemPtr, which points to successive members
151 * * It may be appropriate to first assign
152 * * foobarPtr = (Foobar *) itemPtr;
153 * * to refer to the entire Foobar structure.
157 * Note: itemPtr must be a List_Links pointer variable, and headerPtr
158 * must evaluate to a pointer to a List_Links structure.
160 * ----------------------------------------------------------------------------
163 #define LIST_FORALL(headerPtr, itemPtr) \
164 for (itemPtr = List_First(headerPtr); \
165 !List_IsAtEnd((headerPtr),itemPtr); \
166 itemPtr = List_Next(itemPtr))
169 * ----------------------------------------------------------------------------
173 * Macro: Boolean value, TRUE if the given list does not contain any
176 * Usage: if (List_IsEmpty(headerPtr)) ...
178 * ----------------------------------------------------------------------------
181 #define List_IsEmpty(headerPtr) \
182 ((headerPtr) == (headerPtr)->nextPtr)
185 * ----------------------------------------------------------------------------
189 * Macro: Boolean value, TRUE if itemPtr is after the end of headerPtr
190 * (i.e., itemPtr is the header of the list).
192 * Usage: if (List_IsAtEnd(headerPtr, itemPtr)) ...
194 * ----------------------------------------------------------------------------
198 #define List_IsAtEnd(headerPtr, itemPtr) \
199 ((itemPtr) == (headerPtr))
203 * ----------------------------------------------------------------------------
207 * Macro to return the first member in a list, which is the header if
210 * Usage: firstPtr = List_First(headerPtr);
212 * ----------------------------------------------------------------------------
215 #define List_First(headerPtr) ((headerPtr)->nextPtr)
218 * ----------------------------------------------------------------------------
222 * Macro to return the last member in a list, which is the header if
225 * Usage: lastPtr = List_Last(headerPtr);
227 * ----------------------------------------------------------------------------
230 #define List_Last(headerPtr) ((headerPtr)->prevPtr)
233 * ----------------------------------------------------------------------------
237 * Macro to return the member preceding the given member in its list.
238 * If the given list member is the first element in the list, List_Prev
239 * returns the list header.
241 * Usage: prevPtr = List_Prev(itemPtr);
243 * ----------------------------------------------------------------------------
246 #define List_Prev(itemPtr) ((itemPtr)->prevPtr)
249 * ----------------------------------------------------------------------------
253 * Macro to return the member following the given member in its list.
254 * If the given list member is the last element in the list, List_Next
255 * returns the list header.
257 * Usage: nextPtr = List_Next(itemPtr);
259 * ----------------------------------------------------------------------------
262 #define List_Next(itemPtr) ((itemPtr)->nextPtr)
266 * ----------------------------------------------------------------------------
267 * The List_Insert procedure takes two arguments. The first argument
268 * is a pointer to the structure to be inserted into a list, and
269 * the second argument is a pointer to the list member after which
270 * the new element is to be inserted. Macros are used to determine
271 * which existing member will precede the new one.
273 * The List_Move procedure takes a destination argument with the same
274 * semantics as List_Insert.
276 * The following macros define where to insert the new element
279 * LIST_AFTER(itemPtr) -- insert after itemPtr
280 * LIST_BEFORE(itemPtr) -- insert before itemPtr
281 * LIST_ATFRONT(headerPtr) -- insert at front of list
282 * LIST_ATREAR(headerPtr) -- insert at end of list
286 * List_Insert(itemPtr, LIST_AFTER(otherPtr));
288 * will insert itemPtr following otherPtr in the list containing otherPtr.
289 * ----------------------------------------------------------------------------
292 #define LIST_AFTER(itemPtr) ((List_Links *) itemPtr)
294 #define LIST_BEFORE(itemPtr) (((List_Links *) itemPtr)->prevPtr)
296 #define LIST_ATFRONT(headerPtr) ((List_Links *) headerPtr)
298 #define LIST_ATREAR(headerPtr) (((List_Links *) headerPtr)->prevPtr)