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