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