Commit | Line | Data |
---|---|---|
e72c71e5 WJ |
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, with or without | |
11 | * modification, are permitted provided that the following conditions | |
12 | * are met: | |
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. | |
25 | * | |
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 | |
36 | * SUCH DAMAGE. | |
37 | * | |
38 | * @(#)list.h 5.3 (Berkeley) 6/1/90 | |
39 | */ | |
40 | ||
41 | /* | |
42 | * list.h -- | |
43 | * | |
44 | * Structures, macros, and routines exported by the List module. | |
45 | */ | |
46 | ||
47 | #ifndef _LIST | |
48 | #define _LIST | |
49 | ||
50 | #ifndef _SPRITE | |
51 | #include "sprite.h" | |
52 | #endif _SPRITE | |
53 | ||
54 | /* | |
55 | * This module defines the list abstraction, which enables one to link | |
56 | * together arbitrary data structures. Lists are doubly-linked and | |
57 | * circular. A list contains a header followed by its real members, if | |
58 | * any. (An empty list therefore consists of a single element, the | |
59 | * header, whose nextPtr and prevPtr fields point to itself). To refer | |
60 | * to a list as a whole, the user keeps a pointer to the header; that | |
61 | * header is initialized by a call to List_Init(), which creates an empty | |
62 | * list given a pointer to a List_Links structure (described below). | |
63 | * | |
64 | * The links are contained in a two-element structure called List_Links. | |
65 | * A list joins List_Links records (that is, each List_Links structure | |
66 | * points to other List_Links structures), but if the List_Links is the | |
67 | * first field within a larger structure, then the larger structures are | |
68 | * effectively linked together as follows: | |
69 | * | |
70 | * header | |
71 | * (List_Links) first elt. second elt. | |
72 | * ----------------- ----------------- ----------------- | |
73 | * ..-> | nextPtr | ----> | List_Links | ----> | List_Links |----.. | |
74 | * | - - - - - - - | | | | | | |
75 | * ..-- | prevPtr | <---- | | <---- | |<---.. | |
76 | * ----------------- - --- --- --- - - --- --- --- - | |
77 | * | rest of | | rest of | | |
78 | * | structure | | structure | | |
79 | * | | | | | |
80 | * | ... | | ... | | |
81 | * ----------------- ----------------- | |
82 | * | |
83 | * It is possible to link structures through List_Links fields that are | |
84 | * not at the beginning of the larger structure, but it is then necessary | |
85 | * to perform pointer arithmetic to find the beginning of the larger | |
86 | * structure, given a pointer to some point within it. | |
87 | * | |
88 | * A typical structure might be something like: | |
89 | * | |
90 | * typedef struct { | |
91 | * List_Links links; | |
92 | * char ch; | |
93 | * integer flags; | |
94 | * } EditChar; | |
95 | * | |
96 | * Before an element is inserted in a list for the first time, it must | |
97 | * be initialized by calling the macro List_InitElement(). | |
98 | */ | |
99 | \f | |
100 | ||
101 | /* | |
102 | * data structure for lists | |
103 | */ | |
104 | ||
105 | typedef struct List_Links { | |
106 | struct List_Links *prevPtr; | |
107 | struct List_Links *nextPtr; | |
108 | } List_Links; | |
109 | ||
110 | /* | |
111 | * procedures | |
112 | */ | |
113 | ||
114 | void List_Init(); /* initialize a header to a list */ | |
115 | void List_Insert(); /* insert an element into a list */ | |
116 | void List_Remove(); /* remove an element from a list */ | |
117 | void List_Move(); /* move an element elsewhere in a list */ | |
118 | \f | |
119 | /* | |
120 | * ---------------------------------------------------------------------------- | |
121 | * | |
122 | * List_InitElement -- | |
123 | * | |
124 | * Initialize a list element. Must be called before an element is first | |
125 | * inserted into a list. | |
126 | * | |
127 | * ---------------------------------------------------------------------------- | |
128 | */ | |
129 | #define List_InitElement(elementPtr) \ | |
130 | (elementPtr)->prevPtr = (List_Links *) NIL; \ | |
131 | (elementPtr)->nextPtr = (List_Links *) NIL; | |
132 | ||
133 | /* | |
134 | * Macros for stepping through or selecting parts of lists | |
135 | */ | |
136 | ||
137 | /* | |
138 | * ---------------------------------------------------------------------------- | |
139 | * | |
140 | * LIST_FORALL -- | |
141 | * | |
142 | * Macro to loop through a list and perform an operation on each member. | |
143 | * | |
144 | * Usage: LIST_FORALL(headerPtr, itemPtr) { | |
145 | * / * | |
146 | * * operation on itemPtr, which points to successive members | |
147 | * * of the list | |
148 | * * | |
149 | * * It may be appropriate to first assign | |
150 | * * foobarPtr = (Foobar *) itemPtr; | |
151 | * * to refer to the entire Foobar structure. | |
152 | * * / | |
153 | * } | |
154 | * | |
155 | * Note: itemPtr must be a List_Links pointer variable, and headerPtr | |
156 | * must evaluate to a pointer to a List_Links structure. | |
157 | * | |
158 | * ---------------------------------------------------------------------------- | |
159 | */ | |
160 | ||
161 | #define LIST_FORALL(headerPtr, itemPtr) \ | |
162 | for (itemPtr = List_First(headerPtr); \ | |
163 | !List_IsAtEnd((headerPtr),itemPtr); \ | |
164 | itemPtr = List_Next(itemPtr)) | |
165 | ||
166 | /* | |
167 | * ---------------------------------------------------------------------------- | |
168 | * | |
169 | * List_IsEmpty -- | |
170 | * | |
171 | * Macro: Boolean value, TRUE if the given list does not contain any | |
172 | * members. | |
173 | * | |
174 | * Usage: if (List_IsEmpty(headerPtr)) ... | |
175 | * | |
176 | * ---------------------------------------------------------------------------- | |
177 | */ | |
178 | ||
179 | #define List_IsEmpty(headerPtr) \ | |
180 | ((headerPtr) == (headerPtr)->nextPtr) | |
181 | ||
182 | /* | |
183 | * ---------------------------------------------------------------------------- | |
184 | * | |
185 | * List_IsAtEnd -- | |
186 | * | |
187 | * Macro: Boolean value, TRUE if itemPtr is after the end of headerPtr | |
188 | * (i.e., itemPtr is the header of the list). | |
189 | * | |
190 | * Usage: if (List_IsAtEnd(headerPtr, itemPtr)) ... | |
191 | * | |
192 | * ---------------------------------------------------------------------------- | |
193 | */ | |
194 | ||
195 | ||
196 | #define List_IsAtEnd(headerPtr, itemPtr) \ | |
197 | ((itemPtr) == (headerPtr)) | |
198 | ||
199 | \f | |
200 | /* | |
201 | * ---------------------------------------------------------------------------- | |
202 | * | |
203 | * List_First -- | |
204 | * | |
205 | * Macro to return the first member in a list, which is the header if | |
206 | * the list is empty. | |
207 | * | |
208 | * Usage: firstPtr = List_First(headerPtr); | |
209 | * | |
210 | * ---------------------------------------------------------------------------- | |
211 | */ | |
212 | ||
213 | #define List_First(headerPtr) ((headerPtr)->nextPtr) | |
214 | ||
215 | /* | |
216 | * ---------------------------------------------------------------------------- | |
217 | * | |
218 | * List_Last -- | |
219 | * | |
220 | * Macro to return the last member in a list, which is the header if | |
221 | * the list is empty. | |
222 | * | |
223 | * Usage: lastPtr = List_Last(headerPtr); | |
224 | * | |
225 | * ---------------------------------------------------------------------------- | |
226 | */ | |
227 | ||
228 | #define List_Last(headerPtr) ((headerPtr)->prevPtr) | |
229 | ||
230 | /* | |
231 | * ---------------------------------------------------------------------------- | |
232 | * | |
233 | * List_Prev -- | |
234 | * | |
235 | * Macro to return the member preceding the given member in its list. | |
236 | * If the given list member is the first element in the list, List_Prev | |
237 | * returns the list header. | |
238 | * | |
239 | * Usage: prevPtr = List_Prev(itemPtr); | |
240 | * | |
241 | * ---------------------------------------------------------------------------- | |
242 | */ | |
243 | ||
244 | #define List_Prev(itemPtr) ((itemPtr)->prevPtr) | |
245 | ||
246 | /* | |
247 | * ---------------------------------------------------------------------------- | |
248 | * | |
249 | * List_Next -- | |
250 | * | |
251 | * Macro to return the member following the given member in its list. | |
252 | * If the given list member is the last element in the list, List_Next | |
253 | * returns the list header. | |
254 | * | |
255 | * Usage: nextPtr = List_Next(itemPtr); | |
256 | * | |
257 | * ---------------------------------------------------------------------------- | |
258 | */ | |
259 | ||
260 | #define List_Next(itemPtr) ((itemPtr)->nextPtr) | |
261 | ||
262 | \f | |
263 | /* | |
264 | * ---------------------------------------------------------------------------- | |
265 | * The List_Insert procedure takes two arguments. The first argument | |
266 | * is a pointer to the structure to be inserted into a list, and | |
267 | * the second argument is a pointer to the list member after which | |
268 | * the new element is to be inserted. Macros are used to determine | |
269 | * which existing member will precede the new one. | |
270 | * | |
271 | * The List_Move procedure takes a destination argument with the same | |
272 | * semantics as List_Insert. | |
273 | * | |
274 | * The following macros define where to insert the new element | |
275 | * in the list: | |
276 | * | |
277 | * LIST_AFTER(itemPtr) -- insert after itemPtr | |
278 | * LIST_BEFORE(itemPtr) -- insert before itemPtr | |
279 | * LIST_ATFRONT(headerPtr) -- insert at front of list | |
280 | * LIST_ATREAR(headerPtr) -- insert at end of list | |
281 | * | |
282 | * For example, | |
283 | * | |
284 | * List_Insert(itemPtr, LIST_AFTER(otherPtr)); | |
285 | * | |
286 | * will insert itemPtr following otherPtr in the list containing otherPtr. | |
287 | * ---------------------------------------------------------------------------- | |
288 | */ | |
289 | ||
290 | #define LIST_AFTER(itemPtr) ((List_Links *) itemPtr) | |
291 | ||
292 | #define LIST_BEFORE(itemPtr) (((List_Links *) itemPtr)->prevPtr) | |
293 | ||
294 | #define LIST_ATFRONT(headerPtr) ((List_Links *) headerPtr) | |
295 | ||
296 | #define LIST_ATREAR(headerPtr) (((List_Links *) headerPtr)->prevPtr) | |
297 | ||
298 | #endif _LIST |