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