1: /* $OpenBSD: queue.h,v 1.31 2005/11/25 08:06:25 otto 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: #ifdef QUEUE_MACRO_DEBUG
86: #define _Q_INVALIDATE(a) (a) = ((void *)-1)
87: #else
88: #define _Q_INVALIDATE(a)
89: #endif
90:
91: /*
92: * Singly-linked List definitions.
93: */
94: #define SLIST_HEAD(name, type) \
95: struct name { \
96: struct type *slh_first; /* first element */ \
97: }
98:
99: #define SLIST_HEAD_INITIALIZER(head) \
100: { NULL }
101:
102: #ifdef SLIST_ENTRY
103: #undef SLIST_ENTRY
104: #endif
105:
106: #define SLIST_ENTRY(type) \
107: struct { \
108: struct type *sle_next; /* next element */ \
109: }
110:
111: /*
112: * Singly-linked List access methods.
113: */
114: #define SLIST_FIRST(head) ((head)->slh_first)
115: #define SLIST_END(head) NULL
116: #define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head))
117: #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
118:
119: #define SLIST_FOREACH(var, head, field) \
120: for((var) = SLIST_FIRST(head); \
121: (var) != SLIST_END(head); \
122: (var) = SLIST_NEXT(var, field))
123:
124: #define SLIST_FOREACH_PREVPTR(var, varp, head, field) \
125: for ((varp) = &SLIST_FIRST((head)); \
126: ((var) = *(varp)) != SLIST_END(head); \
127: (varp) = &SLIST_NEXT((var), field))
128:
129: /*
130: * Singly-linked List functions.
131: */
132: #define SLIST_INIT(head) { \
133: SLIST_FIRST(head) = SLIST_END(head); \
134: }
135:
136: #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
137: (elm)->field.sle_next = (slistelm)->field.sle_next; \
138: (slistelm)->field.sle_next = (elm); \
139: } while (0)
140:
141: #define SLIST_INSERT_HEAD(head, elm, field) do { \
142: (elm)->field.sle_next = (head)->slh_first; \
143: (head)->slh_first = (elm); \
144: } while (0)
145:
146: #define SLIST_REMOVE_NEXT(head, elm, field) do { \
147: (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \
148: } while (0)
149:
150: #define SLIST_REMOVE_HEAD(head, field) do { \
151: (head)->slh_first = (head)->slh_first->field.sle_next; \
152: } while (0)
153:
154: #define SLIST_REMOVE(head, elm, type, field) do { \
155: if ((head)->slh_first == (elm)) { \
156: SLIST_REMOVE_HEAD((head), field); \
157: } else { \
158: struct type *curelm = (head)->slh_first; \
159: \
160: while (curelm->field.sle_next != (elm)) \
161: curelm = curelm->field.sle_next; \
162: curelm->field.sle_next = \
163: curelm->field.sle_next->field.sle_next; \
164: _Q_INVALIDATE((elm)->field.sle_next); \
165: } \
166: } while (0)
167:
168: /*
169: * List definitions.
170: */
171: #define LIST_HEAD(name, type) \
172: struct name { \
173: struct type *lh_first; /* first element */ \
174: }
175:
176: #define LIST_HEAD_INITIALIZER(head) \
177: { NULL }
178:
179: #define LIST_ENTRY(type) \
180: struct { \
181: struct type *le_next; /* next element */ \
182: struct type **le_prev; /* address of previous next element */ \
183: }
184:
185: /*
186: * List access methods
187: */
188: #define LIST_FIRST(head) ((head)->lh_first)
189: #define LIST_END(head) NULL
190: #define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))
191: #define LIST_NEXT(elm, field) ((elm)->field.le_next)
192:
193: #define LIST_FOREACH(var, head, field) \
194: for((var) = LIST_FIRST(head); \
195: (var)!= LIST_END(head); \
196: (var) = LIST_NEXT(var, field))
197:
198: /*
199: * List functions.
200: */
201: #define LIST_INIT(head) do { \
202: LIST_FIRST(head) = LIST_END(head); \
203: } while (0)
204:
205: #define LIST_INSERT_AFTER(listelm, elm, field) do { \
206: if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
207: (listelm)->field.le_next->field.le_prev = \
208: &(elm)->field.le_next; \
209: (listelm)->field.le_next = (elm); \
210: (elm)->field.le_prev = &(listelm)->field.le_next; \
211: } while (0)
212:
213: #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
214: (elm)->field.le_prev = (listelm)->field.le_prev; \
215: (elm)->field.le_next = (listelm); \
216: *(listelm)->field.le_prev = (elm); \
217: (listelm)->field.le_prev = &(elm)->field.le_next; \
218: } while (0)
219:
220: #define LIST_INSERT_HEAD(head, elm, field) do { \
221: if (((elm)->field.le_next = (head)->lh_first) != NULL) \
222: (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
223: (head)->lh_first = (elm); \
224: (elm)->field.le_prev = &(head)->lh_first; \
225: } while (0)
226:
227: #define LIST_REMOVE(elm, field) do { \
228: if ((elm)->field.le_next != NULL) \
229: (elm)->field.le_next->field.le_prev = \
230: (elm)->field.le_prev; \
231: *(elm)->field.le_prev = (elm)->field.le_next; \
232: _Q_INVALIDATE((elm)->field.le_prev); \
233: _Q_INVALIDATE((elm)->field.le_next); \
234: } while (0)
235:
236: #define LIST_REPLACE(elm, elm2, field) do { \
237: if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \
238: (elm2)->field.le_next->field.le_prev = \
239: &(elm2)->field.le_next; \
240: (elm2)->field.le_prev = (elm)->field.le_prev; \
241: *(elm2)->field.le_prev = (elm2); \
242: _Q_INVALIDATE((elm)->field.le_prev); \
243: _Q_INVALIDATE((elm)->field.le_next); \
244: } while (0)
245:
246: /*
247: * Simple queue definitions.
248: */
249: #define SIMPLEQ_HEAD(name, type) \
250: struct name { \
251: struct type *sqh_first; /* first element */ \
252: struct type **sqh_last; /* addr of last next element */ \
253: }
254:
255: #define SIMPLEQ_HEAD_INITIALIZER(head) \
256: { NULL, &(head).sqh_first }
257:
258: #define SIMPLEQ_ENTRY(type) \
259: struct { \
260: struct type *sqe_next; /* next element */ \
261: }
262:
263: /*
264: * Simple queue access methods.
265: */
266: #define SIMPLEQ_FIRST(head) ((head)->sqh_first)
267: #define SIMPLEQ_END(head) NULL
268: #define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
269: #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
270:
271: #define SIMPLEQ_FOREACH(var, head, field) \
272: for((var) = SIMPLEQ_FIRST(head); \
273: (var) != SIMPLEQ_END(head); \
274: (var) = SIMPLEQ_NEXT(var, field))
275:
276: /*
277: * Simple queue functions.
278: */
279: #define SIMPLEQ_INIT(head) do { \
280: (head)->sqh_first = NULL; \
281: (head)->sqh_last = &(head)->sqh_first; \
282: } while (0)
283:
284: #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
285: if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
286: (head)->sqh_last = &(elm)->field.sqe_next; \
287: (head)->sqh_first = (elm); \
288: } while (0)
289:
290: #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
291: (elm)->field.sqe_next = NULL; \
292: *(head)->sqh_last = (elm); \
293: (head)->sqh_last = &(elm)->field.sqe_next; \
294: } while (0)
295:
296: #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
297: if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
298: (head)->sqh_last = &(elm)->field.sqe_next; \
299: (listelm)->field.sqe_next = (elm); \
300: } while (0)
301:
302: #define SIMPLEQ_REMOVE_HEAD(head, field) do { \
303: if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
304: (head)->sqh_last = &(head)->sqh_first; \
305: } while (0)
306:
307: /*
308: * Tail queue definitions.
309: */
310: #define TAILQ_HEAD(name, type) \
311: struct name { \
312: struct type *tqh_first; /* first element */ \
313: struct type **tqh_last; /* addr of last next element */ \
314: }
315:
316: #define TAILQ_HEAD_INITIALIZER(head) \
317: { NULL, &(head).tqh_first }
318:
319: #define TAILQ_ENTRY(type) \
320: struct { \
321: struct type *tqe_next; /* next element */ \
322: struct type **tqe_prev; /* address of previous next element */ \
323: }
324:
325: /*
326: * tail queue access methods
327: */
328: #define TAILQ_FIRST(head) ((head)->tqh_first)
329: #define TAILQ_END(head) NULL
330: #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
331: #define TAILQ_LAST(head, headname) \
332: (*(((struct headname *)((head)->tqh_last))->tqh_last))
333: /* XXX */
334: #define TAILQ_PREV(elm, headname, field) \
335: (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
336: #define TAILQ_EMPTY(head) \
337: (TAILQ_FIRST(head) == TAILQ_END(head))
338:
339: #define TAILQ_FOREACH(var, head, field) \
340: for((var) = TAILQ_FIRST(head); \
341: (var) != TAILQ_END(head); \
342: (var) = TAILQ_NEXT(var, field))
343:
344: #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
345: for((var) = TAILQ_LAST(head, headname); \
346: (var) != TAILQ_END(head); \
347: (var) = TAILQ_PREV(var, headname, field))
348:
349: /*
350: * Tail queue functions.
351: */
352: #define TAILQ_INIT(head) do { \
353: (head)->tqh_first = NULL; \
354: (head)->tqh_last = &(head)->tqh_first; \
355: } while (0)
356:
357: #define TAILQ_INSERT_HEAD(head, elm, field) do { \
358: if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
359: (head)->tqh_first->field.tqe_prev = \
360: &(elm)->field.tqe_next; \
361: else \
362: (head)->tqh_last = &(elm)->field.tqe_next; \
363: (head)->tqh_first = (elm); \
364: (elm)->field.tqe_prev = &(head)->tqh_first; \
365: } while (0)
366:
367: #define TAILQ_INSERT_TAIL(head, elm, field) do { \
368: (elm)->field.tqe_next = NULL; \
369: (elm)->field.tqe_prev = (head)->tqh_last; \
370: *(head)->tqh_last = (elm); \
371: (head)->tqh_last = &(elm)->field.tqe_next; \
372: } while (0)
373:
374: #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
375: if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
376: (elm)->field.tqe_next->field.tqe_prev = \
377: &(elm)->field.tqe_next; \
378: else \
379: (head)->tqh_last = &(elm)->field.tqe_next; \
380: (listelm)->field.tqe_next = (elm); \
381: (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
382: } while (0)
383:
384: #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
385: (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
386: (elm)->field.tqe_next = (listelm); \
387: *(listelm)->field.tqe_prev = (elm); \
388: (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
389: } while (0)
390:
391: #define TAILQ_REMOVE(head, elm, field) do { \
392: if (((elm)->field.tqe_next) != NULL) \
393: (elm)->field.tqe_next->field.tqe_prev = \
394: (elm)->field.tqe_prev; \
395: else \
396: (head)->tqh_last = (elm)->field.tqe_prev; \
397: *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
398: _Q_INVALIDATE((elm)->field.tqe_prev); \
399: _Q_INVALIDATE((elm)->field.tqe_next); \
400: } while (0)
401:
402: #define TAILQ_REPLACE(head, elm, elm2, field) do { \
403: if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \
404: (elm2)->field.tqe_next->field.tqe_prev = \
405: &(elm2)->field.tqe_next; \
406: else \
407: (head)->tqh_last = &(elm2)->field.tqe_next; \
408: (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
409: *(elm2)->field.tqe_prev = (elm2); \
410: _Q_INVALIDATE((elm)->field.tqe_prev); \
411: _Q_INVALIDATE((elm)->field.tqe_next); \
412: } while (0)
413:
414: /*
415: * Circular queue definitions.
416: */
417: #define CIRCLEQ_HEAD(name, type) \
418: struct name { \
419: struct type *cqh_first; /* first element */ \
420: struct type *cqh_last; /* last element */ \
421: }
422:
423: #define CIRCLEQ_HEAD_INITIALIZER(head) \
424: { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
425:
426: #define CIRCLEQ_ENTRY(type) \
427: struct { \
428: struct type *cqe_next; /* next element */ \
429: struct type *cqe_prev; /* previous element */ \
430: }
431:
432: /*
433: * Circular queue access methods
434: */
435: #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
436: #define CIRCLEQ_LAST(head) ((head)->cqh_last)
437: #define CIRCLEQ_END(head) ((void *)(head))
438: #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
439: #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
440: #define CIRCLEQ_EMPTY(head) \
441: (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
442:
443: #define CIRCLEQ_FOREACH(var, head, field) \
444: for((var) = CIRCLEQ_FIRST(head); \
445: (var) != CIRCLEQ_END(head); \
446: (var) = CIRCLEQ_NEXT(var, field))
447:
448: #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
449: for((var) = CIRCLEQ_LAST(head); \
450: (var) != CIRCLEQ_END(head); \
451: (var) = CIRCLEQ_PREV(var, field))
452:
453: /*
454: * Circular queue functions.
455: */
456: #define CIRCLEQ_INIT(head) do { \
457: (head)->cqh_first = CIRCLEQ_END(head); \
458: (head)->cqh_last = CIRCLEQ_END(head); \
459: } while (0)
460:
461: #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
462: (elm)->field.cqe_next = (listelm)->field.cqe_next; \
463: (elm)->field.cqe_prev = (listelm); \
464: if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \
465: (head)->cqh_last = (elm); \
466: else \
467: (listelm)->field.cqe_next->field.cqe_prev = (elm); \
468: (listelm)->field.cqe_next = (elm); \
469: } while (0)
470:
471: #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
472: (elm)->field.cqe_next = (listelm); \
473: (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
474: if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \
475: (head)->cqh_first = (elm); \
476: else \
477: (listelm)->field.cqe_prev->field.cqe_next = (elm); \
478: (listelm)->field.cqe_prev = (elm); \
479: } while (0)
480:
481: #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
482: (elm)->field.cqe_next = (head)->cqh_first; \
483: (elm)->field.cqe_prev = CIRCLEQ_END(head); \
484: if ((head)->cqh_last == CIRCLEQ_END(head)) \
485: (head)->cqh_last = (elm); \
486: else \
487: (head)->cqh_first->field.cqe_prev = (elm); \
488: (head)->cqh_first = (elm); \
489: } while (0)
490:
491: #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
492: (elm)->field.cqe_next = CIRCLEQ_END(head); \
493: (elm)->field.cqe_prev = (head)->cqh_last; \
494: if ((head)->cqh_first == CIRCLEQ_END(head)) \
495: (head)->cqh_first = (elm); \
496: else \
497: (head)->cqh_last->field.cqe_next = (elm); \
498: (head)->cqh_last = (elm); \
499: } while (0)
500:
501: #define CIRCLEQ_REMOVE(head, elm, field) do { \
502: if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \
503: (head)->cqh_last = (elm)->field.cqe_prev; \
504: else \
505: (elm)->field.cqe_next->field.cqe_prev = \
506: (elm)->field.cqe_prev; \
507: if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \
508: (head)->cqh_first = (elm)->field.cqe_next; \
509: else \
510: (elm)->field.cqe_prev->field.cqe_next = \
511: (elm)->field.cqe_next; \
512: _Q_INVALIDATE((elm)->field.cqe_prev); \
513: _Q_INVALIDATE((elm)->field.cqe_next); \
514: } while (0)
515:
516: #define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \
517: if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \
518: CIRCLEQ_END(head)) \
519: (head).cqh_last = (elm2); \
520: else \
521: (elm2)->field.cqe_next->field.cqe_prev = (elm2); \
522: if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \
523: CIRCLEQ_END(head)) \
524: (head).cqh_first = (elm2); \
525: else \
526: (elm2)->field.cqe_prev->field.cqe_next = (elm2); \
527: _Q_INVALIDATE((elm)->field.cqe_prev); \
528: _Q_INVALIDATE((elm)->field.cqe_next); \
529: } while (0)
530:
531: #endif /* !_SYS_QUEUE_H_ */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to bsdqueue.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / miniupnpc