Annotation of src/usr.bin/make/list.h, Revision 1.1.1.1
1.1 deraadt 1: /* $NetBSD: list.h,v 1.4 1995/06/14 15:19:28 christos Exp $ */
2:
3: /*
4: * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
5: * Copyright (c) 1988, 1989 by Adam de Boor
6: * Copyright (c) 1989 by Berkeley Softworks
7: * All rights reserved.
8: *
9: * This code is derived from software contributed to Berkeley by
10: * Adam de Boor.
11: *
12: * Redistribution and use in source and binary forms, with or without
13: * modification, are permitted provided that the following conditions
14: * are met:
15: * 1. Redistributions of source code must retain the above copyright
16: * notice, this list of conditions and the following disclaimer.
17: * 2. Redistributions in binary form must reproduce the above copyright
18: * notice, this list of conditions and the following disclaimer in the
19: * documentation and/or other materials provided with the distribution.
20: * 3. All advertising materials mentioning features or use of this software
21: * must display the following acknowledgement:
22: * This product includes software developed by the University of
23: * California, Berkeley and its contributors.
24: * 4. Neither the name of the University nor the names of its contributors
25: * may be used to endorse or promote products derived from this software
26: * without specific prior written permission.
27: *
28: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
29: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
30: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
31: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
32: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
33: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
34: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
35: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
36: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
37: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38: * SUCH DAMAGE.
39: *
40: * from: @(#)list.h 5.3 (Berkeley) 6/1/90
41: */
42:
43: /*
44: * list.h --
45: *
46: * Structures, macros, and routines exported by the List module.
47: */
48:
49: #ifndef _LIST
50: #define _LIST
51:
52: #ifndef _SPRITE
53: #include "sprite.h"
54: #endif _SPRITE
55:
56: /*
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).
65: *
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:
71: *
72: * header
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 |
81: * | | | |
82: * | ... | | ... |
83: * ----------------- -----------------
84: *
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.
89: *
90: * A typical structure might be something like:
91: *
92: * typedef struct {
93: * List_Links links;
94: * char ch;
95: * integer flags;
96: * } EditChar;
97: *
98: * Before an element is inserted in a list for the first time, it must
99: * be initialized by calling the macro List_InitElement().
100: */
101:
102:
103: /*
104: * data structure for lists
105: */
106:
107: typedef struct List_Links {
108: struct List_Links *prevPtr;
109: struct List_Links *nextPtr;
110: } List_Links;
111:
112: /*
113: * procedures
114: */
115:
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 */
120:
121: /*
122: * ----------------------------------------------------------------------------
123: *
124: * List_InitElement --
125: *
126: * Initialize a list element. Must be called before an element is first
127: * inserted into a list.
128: *
129: * ----------------------------------------------------------------------------
130: */
131: #define List_InitElement(elementPtr) \
132: (elementPtr)->prevPtr = (List_Links *) NIL; \
133: (elementPtr)->nextPtr = (List_Links *) NIL;
134:
135: /*
136: * Macros for stepping through or selecting parts of lists
137: */
138:
139: /*
140: * ----------------------------------------------------------------------------
141: *
142: * LIST_FORALL --
143: *
144: * Macro to loop through a list and perform an operation on each member.
145: *
146: * Usage: LIST_FORALL(headerPtr, itemPtr) {
147: * / *
148: * * operation on itemPtr, which points to successive members
149: * * of the list
150: * *
151: * * It may be appropriate to first assign
152: * * foobarPtr = (Foobar *) itemPtr;
153: * * to refer to the entire Foobar structure.
154: * * /
155: * }
156: *
157: * Note: itemPtr must be a List_Links pointer variable, and headerPtr
158: * must evaluate to a pointer to a List_Links structure.
159: *
160: * ----------------------------------------------------------------------------
161: */
162:
163: #define LIST_FORALL(headerPtr, itemPtr) \
164: for (itemPtr = List_First(headerPtr); \
165: !List_IsAtEnd((headerPtr),itemPtr); \
166: itemPtr = List_Next(itemPtr))
167:
168: /*
169: * ----------------------------------------------------------------------------
170: *
171: * List_IsEmpty --
172: *
173: * Macro: Boolean value, TRUE if the given list does not contain any
174: * members.
175: *
176: * Usage: if (List_IsEmpty(headerPtr)) ...
177: *
178: * ----------------------------------------------------------------------------
179: */
180:
181: #define List_IsEmpty(headerPtr) \
182: ((headerPtr) == (headerPtr)->nextPtr)
183:
184: /*
185: * ----------------------------------------------------------------------------
186: *
187: * List_IsAtEnd --
188: *
189: * Macro: Boolean value, TRUE if itemPtr is after the end of headerPtr
190: * (i.e., itemPtr is the header of the list).
191: *
192: * Usage: if (List_IsAtEnd(headerPtr, itemPtr)) ...
193: *
194: * ----------------------------------------------------------------------------
195: */
196:
197:
198: #define List_IsAtEnd(headerPtr, itemPtr) \
199: ((itemPtr) == (headerPtr))
200:
201:
202: /*
203: * ----------------------------------------------------------------------------
204: *
205: * List_First --
206: *
207: * Macro to return the first member in a list, which is the header if
208: * the list is empty.
209: *
210: * Usage: firstPtr = List_First(headerPtr);
211: *
212: * ----------------------------------------------------------------------------
213: */
214:
215: #define List_First(headerPtr) ((headerPtr)->nextPtr)
216:
217: /*
218: * ----------------------------------------------------------------------------
219: *
220: * List_Last --
221: *
222: * Macro to return the last member in a list, which is the header if
223: * the list is empty.
224: *
225: * Usage: lastPtr = List_Last(headerPtr);
226: *
227: * ----------------------------------------------------------------------------
228: */
229:
230: #define List_Last(headerPtr) ((headerPtr)->prevPtr)
231:
232: /*
233: * ----------------------------------------------------------------------------
234: *
235: * List_Prev --
236: *
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.
240: *
241: * Usage: prevPtr = List_Prev(itemPtr);
242: *
243: * ----------------------------------------------------------------------------
244: */
245:
246: #define List_Prev(itemPtr) ((itemPtr)->prevPtr)
247:
248: /*
249: * ----------------------------------------------------------------------------
250: *
251: * List_Next --
252: *
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.
256: *
257: * Usage: nextPtr = List_Next(itemPtr);
258: *
259: * ----------------------------------------------------------------------------
260: */
261:
262: #define List_Next(itemPtr) ((itemPtr)->nextPtr)
263:
264:
265: /*
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.
272: *
273: * The List_Move procedure takes a destination argument with the same
274: * semantics as List_Insert.
275: *
276: * The following macros define where to insert the new element
277: * in the list:
278: *
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
283: *
284: * For example,
285: *
286: * List_Insert(itemPtr, LIST_AFTER(otherPtr));
287: *
288: * will insert itemPtr following otherPtr in the list containing otherPtr.
289: * ----------------------------------------------------------------------------
290: */
291:
292: #define LIST_AFTER(itemPtr) ((List_Links *) itemPtr)
293:
294: #define LIST_BEFORE(itemPtr) (((List_Links *) itemPtr)->prevPtr)
295:
296: #define LIST_ATFRONT(headerPtr) ((List_Links *) headerPtr)
297:
298: #define LIST_ATREAR(headerPtr) (((List_Links *) headerPtr)->prevPtr)
299:
300: #endif /* _LIST */
![[BACK]](/icons/back.gif){kind=icon}
Return to list.h CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / make