1: /* $OpenBSD: queue.h,v 1.16 2000/09/07 19:47:59 art Exp $ */
2: /* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */
3:
4: /*
5: * Copyright (c) 1991, 1993
6: * The Regents of the University of California. All rights reserved.
7: *
8: * Redistribution and use in source and binary forms, with or without
9: * modification, are permitted provided that the following conditions
10: * are met:
11: * 1. Redistributions of source code must retain the above copyright
12: * notice, this list of conditions and the following disclaimer.
13: * 2. Redistributions in binary form must reproduce the above copyright
14: * notice, this list of conditions and the following disclaimer in the
15: * documentation and/or other materials provided with the distribution.
16: * 3. Neither the name of the University nor the names of its contributors
17: * may be used to endorse or promote products derived from this software
18: * without specific prior written permission.
19: *
20: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30: * SUCH DAMAGE.
31: *
32: * @(#)queue.h 8.5 (Berkeley) 8/20/94
33: */
34:
35: #ifndef _SYS_QUEUE_H_
36: #define _SYS_QUEUE_H_
37:
38: /*
39: * This file defines five types of data structures: singly-linked lists,
40: * lists, simple queues, tail queues, and circular queues.
41: *
42: *
43: * A singly-linked list is headed by a single forward pointer. The elements
44: * are singly linked for minimum space and pointer manipulation overhead at
45: * the expense of O(n) removal for arbitrary elements. New elements can be
46: * added to the list after an existing element or at the head of the list.
47: * Elements being removed from the head of the list should use the explicit
48: * macro for this purpose for optimum efficiency. A singly-linked list may
49: * only be traversed in the forward direction. Singly-linked lists are ideal
50: * for applications with large datasets and few or no removals or for
51: * implementing a LIFO queue.
52: *
53: * A list is headed by a single forward pointer (or an array of forward
54: * pointers for a hash table header). The elements are doubly linked
55: * so that an arbitrary element can be removed without a need to
56: * traverse the list. New elements can be added to the list before
57: * or after an existing element or at the head of the list. A list
58: * may only be traversed in the forward direction.
59: *
60: * A simple queue is headed by a pair of pointers, one the head of the
61: * list and the other to the tail of the list. The elements are singly
62: * linked to save space, so elements can only be removed from the
63: * head of the list. New elements can be added to the list before or after
64: * an existing element, at the head of the list, or at the end of the
65: * list. A simple queue may only be traversed in the forward direction.
66: *
67: * A tail queue is headed by a pair of pointers, one to the head of the
68: * list and the other to the tail of the list. The elements are doubly
69: * linked so that an arbitrary element can be removed without a need to
70: * traverse the list. New elements can be added to the list before or
71: * after an existing element, at the head of the list, or at the end of
72: * the list. A tail queue may be traversed in either direction.
73: *
74: * A circle queue is headed by a pair of pointers, one to the head of the
75: * list and the other to the tail of the list. The elements are doubly
76: * linked so that an arbitrary element can be removed without a need to
77: * traverse the list. New elements can be added to the list before or after
78: * an existing element, at the head of the list, or at the end of the list.
79: * A circle queue may be traversed in either direction, but has a more
80: * complex end of list detection.
81: *
82: * For details on the use of these macros, see the queue(3) manual page.
83: */
84:
85: /*
86: * Singly-linked List definitions.
87: */
88: #define SLIST_HEAD(name, type) \
89: struct name { \
90: struct type *slh_first; /* first element */ \
91: }
92:
93: #define SLIST_HEAD_INITIALIZER(head) \
94: { NULL }
95:
96: #ifndef WIN32
97: #define SLIST_ENTRY(type) \
98: struct { \
99: struct type *sle_next; /* next element */ \
100: }
101: #endif
102:
103: /*
104: * Singly-linked List access methods.
105: */
106: #define SLIST_FIRST(head) ((head)->slh_first)
107: #define SLIST_END(head) NULL
108: #define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head))
109: #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
110:
111: #define SLIST_FOREACH(var, head, field) \
112: for((var) = SLIST_FIRST(head); \
113: (var) != SLIST_END(head); \
114: (var) = SLIST_NEXT(var, field))
115:
116: /*
117: * Singly-linked List functions.
118: */
119: #define SLIST_INIT(head) { \
120: SLIST_FIRST(head) = SLIST_END(head); \
121: }
122:
123: #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
124: (elm)->field.sle_next = (slistelm)->field.sle_next; \
125: (slistelm)->field.sle_next = (elm); \
126: } while (0)
127:
128: #define SLIST_INSERT_HEAD(head, elm, field) do { \
129: (elm)->field.sle_next = (head)->slh_first; \
130: (head)->slh_first = (elm); \
131: } while (0)
132:
133: #define SLIST_REMOVE_HEAD(head, field) do { \
134: (head)->slh_first = (head)->slh_first->field.sle_next; \
135: } while (0)
136:
137: /*
138: * List definitions.
139: */
140: #define LIST_HEAD(name, type) \
141: struct name { \
142: struct type *lh_first; /* first element */ \
143: }
144:
145: #define LIST_HEAD_INITIALIZER(head) \
146: { NULL }
147:
148: #define LIST_ENTRY(type) \
149: struct { \
150: struct type *le_next; /* next element */ \
151: struct type **le_prev; /* address of previous next element */ \
152: }
153:
154: /*
155: * List access methods
156: */
157: #define LIST_FIRST(head) ((head)->lh_first)
158: #define LIST_END(head) NULL
159: #define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))
160: #define LIST_NEXT(elm, field) ((elm)->field.le_next)
161:
162: #define LIST_FOREACH(var, head, field) \
163: for((var) = LIST_FIRST(head); \
164: (var)!= LIST_END(head); \
165: (var) = LIST_NEXT(var, field))
166:
167: /*
168: * List functions.
169: */
170: #define LIST_INIT(head) do { \
171: LIST_FIRST(head) = LIST_END(head); \
172: } while (0)
173:
174: #define LIST_INSERT_AFTER(listelm, elm, field) do { \
175: if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
176: (listelm)->field.le_next->field.le_prev = \
177: &(elm)->field.le_next; \
178: (listelm)->field.le_next = (elm); \
179: (elm)->field.le_prev = &(listelm)->field.le_next; \
180: } while (0)
181:
182: #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
183: (elm)->field.le_prev = (listelm)->field.le_prev; \
184: (elm)->field.le_next = (listelm); \
185: *(listelm)->field.le_prev = (elm); \
186: (listelm)->field.le_prev = &(elm)->field.le_next; \
187: } while (0)
188:
189: #define LIST_INSERT_HEAD(head, elm, field) do { \
190: if (((elm)->field.le_next = (head)->lh_first) != NULL) \
191: (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
192: (head)->lh_first = (elm); \
193: (elm)->field.le_prev = &(head)->lh_first; \
194: } while (0)
195:
196: #define LIST_REMOVE(elm, field) do { \
197: if ((elm)->field.le_next != NULL) \
198: (elm)->field.le_next->field.le_prev = \
199: (elm)->field.le_prev; \
200: *(elm)->field.le_prev = (elm)->field.le_next; \
201: } while (0)
202:
203: #define LIST_REPLACE(elm, elm2, field) do { \
204: if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \
205: (elm2)->field.le_next->field.le_prev = \
206: &(elm2)->field.le_next; \
207: (elm2)->field.le_prev = (elm)->field.le_prev; \
208: *(elm2)->field.le_prev = (elm2); \
209: } while (0)
210:
211: /*
212: * Simple queue definitions.
213: */
214: #define SIMPLEQ_HEAD(name, type) \
215: struct name { \
216: struct type *sqh_first; /* first element */ \
217: struct type **sqh_last; /* addr of last next element */ \
218: }
219:
220: #define SIMPLEQ_HEAD_INITIALIZER(head) \
221: { NULL, &(head).sqh_first }
222:
223: #define SIMPLEQ_ENTRY(type) \
224: struct { \
225: struct type *sqe_next; /* next element */ \
226: }
227:
228: /*
229: * Simple queue access methods.
230: */
231: #define SIMPLEQ_FIRST(head) ((head)->sqh_first)
232: #define SIMPLEQ_END(head) NULL
233: #define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
234: #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
235:
236: #define SIMPLEQ_FOREACH(var, head, field) \
237: for((var) = SIMPLEQ_FIRST(head); \
238: (var) != SIMPLEQ_END(head); \
239: (var) = SIMPLEQ_NEXT(var, field))
240:
241: /*
242: * Simple queue functions.
243: */
244: #define SIMPLEQ_INIT(head) do { \
245: (head)->sqh_first = NULL; \
246: (head)->sqh_last = &(head)->sqh_first; \
247: } while (0)
248:
249: #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
250: if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
251: (head)->sqh_last = &(elm)->field.sqe_next; \
252: (head)->sqh_first = (elm); \
253: } while (0)
254:
255: #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
256: (elm)->field.sqe_next = NULL; \
257: *(head)->sqh_last = (elm); \
258: (head)->sqh_last = &(elm)->field.sqe_next; \
259: } while (0)
260:
261: #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
262: if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
263: (head)->sqh_last = &(elm)->field.sqe_next; \
264: (listelm)->field.sqe_next = (elm); \
265: } while (0)
266:
267: #define SIMPLEQ_REMOVE_HEAD(head, elm, field) do { \
268: if (((head)->sqh_first = (elm)->field.sqe_next) == NULL) \
269: (head)->sqh_last = &(head)->sqh_first; \
270: } while (0)
271:
272: /*
273: * Tail queue definitions.
274: */
275: #define TAILQ_HEAD(name, type) \
276: struct name { \
277: struct type *tqh_first; /* first element */ \
278: struct type **tqh_last; /* addr of last next element */ \
279: }
280:
281: #define TAILQ_HEAD_INITIALIZER(head) \
282: { NULL, &(head).tqh_first }
283:
284: #define TAILQ_ENTRY(type) \
285: struct { \
286: struct type *tqe_next; /* next element */ \
287: struct type **tqe_prev; /* address of previous next element */ \
288: }
289:
290: /*
291: * tail queue access methods
292: */
293: #define TAILQ_FIRST(head) ((head)->tqh_first)
294: #define TAILQ_END(head) NULL
295: #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
296: #define TAILQ_LAST(head, headname) \
297: (*(((struct headname *)((head)->tqh_last))->tqh_last))
298: /* XXX */
299: #define TAILQ_PREV(elm, headname, field) \
300: (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
301: #define TAILQ_EMPTY(head) \
302: (TAILQ_FIRST(head) == TAILQ_END(head))
303:
304: #define TAILQ_FOREACH(var, head, field) \
305: for((var) = TAILQ_FIRST(head); \
306: (var) != TAILQ_END(head); \
307: (var) = TAILQ_NEXT(var, field))
308:
309: #define TAILQ_FOREACH_REVERSE(var, head, field, headname) \
310: for((var) = TAILQ_LAST(head, headname); \
311: (var) != TAILQ_END(head); \
312: (var) = TAILQ_PREV(var, headname, field))
313:
314: /*
315: * Tail queue functions.
316: */
317: #define TAILQ_INIT(head) do { \
318: (head)->tqh_first = NULL; \
319: (head)->tqh_last = &(head)->tqh_first; \
320: } while (0)
321:
322: #define TAILQ_INSERT_HEAD(head, elm, field) do { \
323: if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
324: (head)->tqh_first->field.tqe_prev = \
325: &(elm)->field.tqe_next; \
326: else \
327: (head)->tqh_last = &(elm)->field.tqe_next; \
328: (head)->tqh_first = (elm); \
329: (elm)->field.tqe_prev = &(head)->tqh_first; \
330: } while (0)
331:
332: #define TAILQ_INSERT_TAIL(head, elm, field) do { \
333: (elm)->field.tqe_next = NULL; \
334: (elm)->field.tqe_prev = (head)->tqh_last; \
335: *(head)->tqh_last = (elm); \
336: (head)->tqh_last = &(elm)->field.tqe_next; \
337: } while (0)
338:
339: #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
340: if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
341: (elm)->field.tqe_next->field.tqe_prev = \
342: &(elm)->field.tqe_next; \
343: else \
344: (head)->tqh_last = &(elm)->field.tqe_next; \
345: (listelm)->field.tqe_next = (elm); \
346: (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
347: } while (0)
348:
349: #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
350: (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
351: (elm)->field.tqe_next = (listelm); \
352: *(listelm)->field.tqe_prev = (elm); \
353: (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
354: } while (0)
355:
356: #define TAILQ_REMOVE(head, elm, field) do { \
357: if (((elm)->field.tqe_next) != NULL) \
358: (elm)->field.tqe_next->field.tqe_prev = \
359: (elm)->field.tqe_prev; \
360: else \
361: (head)->tqh_last = (elm)->field.tqe_prev; \
362: *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
363: } while (0)
364:
365: #define TAILQ_REPLACE(head, elm, elm2, field) do { \
366: if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \
367: (elm2)->field.tqe_next->field.tqe_prev = \
368: &(elm2)->field.tqe_next; \
369: else \
370: (head)->tqh_last = &(elm2)->field.tqe_next; \
371: (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
372: *(elm2)->field.tqe_prev = (elm2); \
373: } while (0)
374:
375: /*
376: * Circular queue definitions.
377: */
378: #define CIRCLEQ_HEAD(name, type) \
379: struct name { \
380: struct type *cqh_first; /* first element */ \
381: struct type *cqh_last; /* last element */ \
382: }
383:
384: #define CIRCLEQ_HEAD_INITIALIZER(head) \
385: { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
386:
387: #define CIRCLEQ_ENTRY(type) \
388: struct { \
389: struct type *cqe_next; /* next element */ \
390: struct type *cqe_prev; /* previous element */ \
391: }
392:
393: /*
394: * Circular queue access methods
395: */
396: #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
397: #define CIRCLEQ_LAST(head) ((head)->cqh_last)
398: #define CIRCLEQ_END(head) ((void *)(head))
399: #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
400: #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
401: #define CIRCLEQ_EMPTY(head) \
402: (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
403:
404: #define CIRCLEQ_FOREACH(var, head, field) \
405: for((var) = CIRCLEQ_FIRST(head); \
406: (var) != CIRCLEQ_END(head); \
407: (var) = CIRCLEQ_NEXT(var, field))
408:
409: #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
410: for((var) = CIRCLEQ_LAST(head); \
411: (var) != CIRCLEQ_END(head); \
412: (var) = CIRCLEQ_PREV(var, field))
413:
414: /*
415: * Circular queue functions.
416: */
417: #define CIRCLEQ_INIT(head) do { \
418: (head)->cqh_first = CIRCLEQ_END(head); \
419: (head)->cqh_last = CIRCLEQ_END(head); \
420: } while (0)
421:
422: #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
423: (elm)->field.cqe_next = (listelm)->field.cqe_next; \
424: (elm)->field.cqe_prev = (listelm); \
425: if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \
426: (head)->cqh_last = (elm); \
427: else \
428: (listelm)->field.cqe_next->field.cqe_prev = (elm); \
429: (listelm)->field.cqe_next = (elm); \
430: } while (0)
431:
432: #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
433: (elm)->field.cqe_next = (listelm); \
434: (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
435: if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \
436: (head)->cqh_first = (elm); \
437: else \
438: (listelm)->field.cqe_prev->field.cqe_next = (elm); \
439: (listelm)->field.cqe_prev = (elm); \
440: } while (0)
441:
442: #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
443: (elm)->field.cqe_next = (head)->cqh_first; \
444: (elm)->field.cqe_prev = CIRCLEQ_END(head); \
445: if ((head)->cqh_last == CIRCLEQ_END(head)) \
446: (head)->cqh_last = (elm); \
447: else \
448: (head)->cqh_first->field.cqe_prev = (elm); \
449: (head)->cqh_first = (elm); \
450: } while (0)
451:
452: #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
453: (elm)->field.cqe_next = CIRCLEQ_END(head); \
454: (elm)->field.cqe_prev = (head)->cqh_last; \
455: if ((head)->cqh_first == CIRCLEQ_END(head)) \
456: (head)->cqh_first = (elm); \
457: else \
458: (head)->cqh_last->field.cqe_next = (elm); \
459: (head)->cqh_last = (elm); \
460: } while (0)
461:
462: #define CIRCLEQ_REMOVE(head, elm, field) do { \
463: if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \
464: (head)->cqh_last = (elm)->field.cqe_prev; \
465: else \
466: (elm)->field.cqe_next->field.cqe_prev = \
467: (elm)->field.cqe_prev; \
468: if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \
469: (head)->cqh_first = (elm)->field.cqe_next; \
470: else \
471: (elm)->field.cqe_prev->field.cqe_next = \
472: (elm)->field.cqe_next; \
473: } while (0)
474:
475: #define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \
476: if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \
477: CIRCLEQ_END(head)) \
478: (head).cqh_last = (elm2); \
479: else \
480: (elm2)->field.cqe_next->field.cqe_prev = (elm2); \
481: if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \
482: CIRCLEQ_END(head)) \
483: (head).cqh_first = (elm2); \
484: else \
485: (elm2)->field.cqe_prev->field.cqe_next = (elm2); \
486: } while (0)
487:
488: #endif /* !_SYS_QUEUE_H_ */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to queue.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / libevent / compat / sys