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