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