VirtualBox

source: kBuild/branches/FREEBSD/src/kmk/list.h@ 10

Last change on this file since 10 was 10, checked in by (none), 22 years ago

This commit was manufactured by cvs2svn to create branch 'FREEBSD'.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 10.1 KB
Line 
1/*
2 * Copyright (c) 1988, 1989, 1990, 1993
3 * The Regents of the University of California. All rights reserved.
4 * Copyright (c) 1988, 1989 by Adam de Boor
5 * Copyright (c) 1989 by Berkeley Softworks
6 * All rights reserved.
7 *
8 * This code is derived from software contributed to Berkeley by
9 * Adam de Boor.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. All advertising materials mentioning features or use of this software
20 * must display the following acknowledgement:
21 * This product includes software developed by the University of
22 * California, Berkeley and its contributors.
23 * 4. Neither the name of the University nor the names of its contributors
24 * may be used to endorse or promote products derived from this software
25 * without specific prior written permission.
26 *
27 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
28 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
30 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
31 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
32 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
33 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
34 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
35 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
36 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 * SUCH DAMAGE.
38 *
39 * @(#)list.h 8.2 (Berkeley) 4/28/95
40 * $FreeBSD: src/usr.bin/make/list.h,v 1.11 2002/09/17 21:29:06 jmallett Exp $
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/*
105 * data structure for lists
106 */
107
108typedef struct List_Links {
109 struct List_Links *prevPtr;
110 struct List_Links *nextPtr;
111} List_Links;
112
113/*
114 * procedures
115 */
116
117void List_Init(); /* initialize a header to a list */
118void List_Insert(); /* insert an element into a list */
119void List_Remove(); /* remove an element from a list */
120void List_Move(); /* move an element elsewhere in a list */
121
122
123/*
124 * ----------------------------------------------------------------------------
125 *
126 * List_InitElement --
127 *
128 * Initialize a list element. Must be called before an element is first
129 * inserted into a list.
130 *
131 * ----------------------------------------------------------------------------
132 */
133#define List_InitElement(elementPtr) \
134 (elementPtr)->prevPtr = (List_Links *) NULL; \
135 (elementPtr)->nextPtr = (List_Links *) NULL;
136
137/*
138 * Macros for stepping through or selecting parts of lists
139 */
140
141/*
142 * ----------------------------------------------------------------------------
143 *
144 * LIST_FORALL --
145 *
146 * Macro to loop through a list and perform an operation on each member.
147 *
148 * Usage: LIST_FORALL(headerPtr, itemPtr) {
149 * / *
150 * * operation on itemPtr, which points to successive members
151 * * of the list
152 * *
153 * * It may be appropriate to first assign
154 * * foobarPtr = (Foobar *) itemPtr;
155 * * to refer to the entire Foobar structure.
156 * * /
157 * }
158 *
159 * Note: itemPtr must be a List_Links pointer variable, and headerPtr
160 * must evaluate to a pointer to a List_Links structure.
161 *
162 * ----------------------------------------------------------------------------
163 */
164
165#define LIST_FORALL(headerPtr, itemPtr) \
166 for (itemPtr = List_First(headerPtr); \
167 !List_IsAtEnd((headerPtr),itemPtr); \
168 itemPtr = List_Next(itemPtr))
169
170/*
171 * ----------------------------------------------------------------------------
172 *
173 * List_IsEmpty --
174 *
175 * Macro: Boolean value, TRUE if the given list does not contain any
176 * members.
177 *
178 * Usage: if (List_IsEmpty(headerPtr)) ...
179 *
180 * ----------------------------------------------------------------------------
181 */
182
183#define List_IsEmpty(headerPtr) \
184 ((headerPtr) == (headerPtr)->nextPtr)
185
186/*
187 * ----------------------------------------------------------------------------
188 *
189 * List_IsAtEnd --
190 *
191 * Macro: Boolean value, TRUE if itemPtr is after the end of headerPtr
192 * (i.e., itemPtr is the header of the list).
193 *
194 * Usage: if (List_IsAtEnd(headerPtr, itemPtr)) ...
195 *
196 * ----------------------------------------------------------------------------
197 */
198
199
200#define List_IsAtEnd(headerPtr, itemPtr) \
201 ((itemPtr) == (headerPtr))
202
203
204
205/*
206 * ----------------------------------------------------------------------------
207 *
208 * List_First --
209 *
210 * Macro to return the first member in a list, which is the header if
211 * the list is empty.
212 *
213 * Usage: firstPtr = List_First(headerPtr);
214 *
215 * ----------------------------------------------------------------------------
216 */
217
218#define List_First(headerPtr) ((headerPtr)->nextPtr)
219
220/*
221 * ----------------------------------------------------------------------------
222 *
223 * List_Last --
224 *
225 * Macro to return the last member in a list, which is the header if
226 * the list is empty.
227 *
228 * Usage: lastPtr = List_Last(headerPtr);
229 *
230 * ----------------------------------------------------------------------------
231 */
232
233#define List_Last(headerPtr) ((headerPtr)->prevPtr)
234
235/*
236 * ----------------------------------------------------------------------------
237 *
238 * List_Prev --
239 *
240 * Macro to return the member preceding the given member in its list.
241 * If the given list member is the first element in the list, List_Prev
242 * returns the list header.
243 *
244 * Usage: prevPtr = List_Prev(itemPtr);
245 *
246 * ----------------------------------------------------------------------------
247 */
248
249#define List_Prev(itemPtr) ((itemPtr)->prevPtr)
250
251/*
252 * ----------------------------------------------------------------------------
253 *
254 * List_Next --
255 *
256 * Macro to return the member following the given member in its list.
257 * If the given list member is the last element in the list, List_Next
258 * returns the list header.
259 *
260 * Usage: nextPtr = List_Next(itemPtr);
261 *
262 * ----------------------------------------------------------------------------
263 */
264
265#define List_Next(itemPtr) ((itemPtr)->nextPtr)
266
267
268
269/*
270 * ----------------------------------------------------------------------------
271 * The List_Insert procedure takes two arguments. The first argument
272 * is a pointer to the structure to be inserted into a list, and
273 * the second argument is a pointer to the list member after which
274 * the new element is to be inserted. Macros are used to determine
275 * which existing member will precede the new one.
276 *
277 * The List_Move procedure takes a destination argument with the same
278 * semantics as List_Insert.
279 *
280 * The following macros define where to insert the new element
281 * in the list:
282 *
283 * LIST_AFTER(itemPtr) -- insert after itemPtr
284 * LIST_BEFORE(itemPtr) -- insert before itemPtr
285 * LIST_ATFRONT(headerPtr) -- insert at front of list
286 * LIST_ATREAR(headerPtr) -- insert at end of list
287 *
288 * For example,
289 *
290 * List_Insert(itemPtr, LIST_AFTER(otherPtr));
291 *
292 * will insert itemPtr following otherPtr in the list containing otherPtr.
293 * ----------------------------------------------------------------------------
294 */
295
296#define LIST_AFTER(itemPtr) ((List_Links *) itemPtr)
297
298#define LIST_BEFORE(itemPtr) (((List_Links *) itemPtr)->prevPtr)
299
300#define LIST_ATFRONT(headerPtr) ((List_Links *) headerPtr)
301
302#define LIST_ATREAR(headerPtr) (((List_Links *) headerPtr)->prevPtr)
303
304#endif /* _LIST */
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette