---

---

---

001: /*
002:  * Copyright (c) 1991, 1993
003:  *      The Regents of the University of California.  All rights reserved.
004:  *
005:  * Redistribution and use in source and binary forms, with or without
006:  * modification, are permitted provided that the following conditions
007:  * are met:
008:  * 1. Redistributions of source code must retain the above copyright
009:  *    notice, this list of conditions and the following disclaimer.
010:  * 2. Redistributions in binary form must reproduce the above copyright
011:  *    notice, this list of conditions and the following disclaimer in the
012:  *    documentation and/or other materials provided with the distribution.
013:  * 3. Neither the name of the University nor the names of its contributors
014:  *    may be used to endorse or promote products derived from this software
015:  *    without specific prior written permission.
016:  *
017:  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
018:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
019:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
020:  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
021:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
022:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
023:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
024:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
025:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
026:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
027:  * SUCH DAMAGE.
028:  *
029:  *      @(#)queue.h     8.5 (Berkeley) 8/20/94
030:  */
031: 
032: #ifndef _SYS_QUEUE_H_
033: #define _SYS_QUEUE_H_
034: 
035: /*
036:  * This file defines five types of data structures: singly-linked lists,
037:  * lists, simple queues, tail queues, and circular queues.
038:  *
039:  * A singly-linked list is headed by a single forward pointer. The
040:  * elements are singly linked for minimum space and pointer manipulation
041:  * overhead at the expense of O(n) removal for arbitrary elements. New
042:  * elements can be added to the list after an existing element or at the
043:  * head of the list.  Elements being removed from the head of the list
044:  * should use the explicit macro for this purpose for optimum
045:  * efficiency. A singly-linked list may only be traversed in the forward
046:  * direction.  Singly-linked lists are ideal for applications with large
047:  * datasets and few or no removals or for implementing a LIFO queue.
048:  *
049:  * A list is headed by a single forward pointer (or an array of forward
050:  * pointers for a hash table header). The elements are doubly linked
051:  * so that an arbitrary element can be removed without a need to
052:  * traverse the list. New elements can be added to the list before
053:  * or after an existing element or at the head of the list. A list
054:  * may only be traversed in the forward direction.
055:  *
056:  * A simple queue is headed by a pair of pointers, one the head of the
057:  * list and the other to the tail of the list. The elements are singly
058:  * linked to save space, so elements can only be removed from the
059:  * head of the list. New elements can be added to the list after
060:  * an existing element, at the head of the list, or at the end of the
061:  * list. A simple queue may only be traversed in the forward direction.
062:  *
063:  * A tail queue is headed by a pair of pointers, one to the head of the
064:  * list and the other to the tail of the list. The elements are doubly
065:  * linked so that an arbitrary element can be removed without a need to
066:  * traverse the list. New elements can be added to the list before or
067:  * after an existing element, at the head of the list, or at the end of
068:  * the list. A tail queue may be traversed in either direction.
069:  *
070:  * A circle queue is headed by a pair of pointers, one to the head of the
071:  * list and the other to the tail of the list. The elements are doubly
072:  * linked so that an arbitrary element can be removed without a need to
073:  * traverse the list. New elements can be added to the list before or after
074:  * an existing element, at the head of the list, or at the end of the list.
075:  * A circle queue may be traversed in either direction, but has a more
076:  * complex end of list detection.
077:  *
078:  * For details on the use of these macros, see the queue(3) manual page.
079:  */
080: 
081: /*
082:  * List definitions.
083:  */
084: #define LIST_HEAD(name, type)                                           \
085: struct name {                                                           \
086:         struct type *lh_first;  /* first element */                     \
087: }
088: 
089: #define LIST_HEAD_INITIALIZER(head)                                     \
090:         { NULL }
091: 
092: #define LIST_ENTRY(type)                                                \
093: struct {                                                                \
094:         struct type *le_next;   /* next element */                      \
095:         struct type **le_prev;  /* address of previous next element */  \
096: }
097: 
098: /*
099:  * List functions.
100:  */
101: #define LIST_INIT(head) do {                                            \
102:         (head)->lh_first = NULL;                                        \
103: } while (/*CONSTCOND*/0)
104: 
105: #define LIST_INSERT_AFTER(listelm, elm, field) do {                     \
106:         if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)  \
107:                 (listelm)->field.le_next->field.le_prev =               \
108:                     &(elm)->field.le_next;                              \
109:         (listelm)->field.le_next = (elm);                               \
110:         (elm)->field.le_prev = &(listelm)->field.le_next;               \
111: } while (/*CONSTCOND*/0)
112: 
113: #define LIST_INSERT_BEFORE(listelm, elm, field) do {                    \
114:         (elm)->field.le_prev = (listelm)->field.le_prev;                \
115:         (elm)->field.le_next = (listelm);                               \
116:         *(listelm)->field.le_prev = (elm);                              \
117:         (listelm)->field.le_prev = &(elm)->field.le_next;               \
118: } while (/*CONSTCOND*/0)
119: 
120: #define LIST_INSERT_HEAD(head, elm, field) do {                         \
121:         if (((elm)->field.le_next = (head)->lh_first) != NULL)          \
122:                 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
123:         (head)->lh_first = (elm);                                       \
124:         (elm)->field.le_prev = &(head)->lh_first;                       \
125: } while (/*CONSTCOND*/0)
126: 
127: #define LIST_REMOVE(elm, field) do {                                    \
128:         if ((elm)->field.le_next != NULL)                               \
129:                 (elm)->field.le_next->field.le_prev =                   \
130:                     (elm)->field.le_prev;                               \
131:         *(elm)->field.le_prev = (elm)->field.le_next;                   \
132: } while (/*CONSTCOND*/0)
133: 
134: #define LIST_FOREACH(var, head, field)                                  \
135:         for ((var) = ((head)->lh_first);                                \
136:                 (var);                                                  \
137:                 (var) = ((var)->field.le_next))
138: 
139: /*
140:  * List access methods.
141:  */
142: #define LIST_EMPTY(head)                ((head)->lh_first == NULL)
143: #define LIST_FIRST(head)                ((head)->lh_first)
144: #define LIST_NEXT(elm, field)           ((elm)->field.le_next)
145: 
146: 
147: /*
148:  * Singly-linked List definitions.
149:  */
150: #define SLIST_HEAD(name, type)                                          \
151: struct name {                                                           \
152:         struct type *slh_first; /* first element */                     \
153: }
154: 
155: #define SLIST_HEAD_INITIALIZER(head)                                    \
156:         { NULL }
157: 
158: #define SLIST_ENTRY(type)                                               \
159: struct {                                                                \
160:         struct type *sle_next;  /* next element */                      \
161: }
162: 
163: /*
164:  * Singly-linked List functions.
165:  */
166: #define SLIST_INIT(head) do {                                           \
167:         (head)->slh_first = NULL;                                       \
168: } while (/*CONSTCOND*/0)
169: 
170: #define SLIST_INSERT_AFTER(slistelm, elm, field) do {                   \
171:         (elm)->field.sle_next = (slistelm)->field.sle_next;             \
172:         (slistelm)->field.sle_next = (elm);                             \
173: } while (/*CONSTCOND*/0)
174: 
175: #define SLIST_INSERT_HEAD(head, elm, field) do {                        \
176:         (elm)->field.sle_next = (head)->slh_first;                      \
177:         (head)->slh_first = (elm);                                      \
178: } while (/*CONSTCOND*/0)
179: 
180: #define SLIST_REMOVE_HEAD(head, field) do {                             \
181:         (head)->slh_first = (head)->slh_first->field.sle_next;          \
182: } while (/*CONSTCOND*/0)
183: 
184: #define SLIST_REMOVE(head, elm, type, field) do {                       \
185:         if ((head)->slh_first == (elm)) {                               \
186:                 SLIST_REMOVE_HEAD((head), field);                       \
187:         }                                                               \
188:         else {                                                          \
189:                 struct type *curelm = (head)->slh_first;                \
190:                 while(curelm->field.sle_next != (elm))                  \
191:                         curelm = curelm->field.sle_next;                \
192:                 curelm->field.sle_next =                                \
193:                     curelm->field.sle_next->field.sle_next;             \
194:         }                                                               \
195: } while (/*CONSTCOND*/0)
196: 
197: #define SLIST_FOREACH(var, head, field)                                 \
198:         for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
199: 
200: /*
201:  * Singly-linked List access methods.
202:  */
203: #define SLIST_EMPTY(head)       ((head)->slh_first == NULL)
204: #define SLIST_FIRST(head)       ((head)->slh_first)
205: #define SLIST_NEXT(elm, field)  ((elm)->field.sle_next)
206: 
207: 
208: /*
209:  * Singly-linked Tail queue declarations.
210:  */
211: #define STAILQ_HEAD(name, type)                                 \
212: struct name {                                                           \
213:         struct type *stqh_first;        /* first element */                     \
214:         struct type **stqh_last;        /* addr of last next element */         \
215: }
216: 
217: #define STAILQ_HEAD_INITIALIZER(head)                                   \
218:         { NULL, &(head).stqh_first }
219: 
220: #define STAILQ_ENTRY(type)                                              \
221: struct {                                                                \
222:         struct type *stqe_next; /* next element */                      \
223: }
224: 
225: /*
226:  * Singly-linked Tail queue functions.
227:  */
228: #define STAILQ_INIT(head) do {                                          \
229:         (head)->stqh_first = NULL;                                      \
230:         (head)->stqh_last = &(head)->stqh_first;                                \
231: } while (/*CONSTCOND*/0)
232: 
233: #define STAILQ_INSERT_HEAD(head, elm, field) do {                       \
234:         if (((elm)->field.stqe_next = (head)->stqh_first) == NULL)      \
235:                 (head)->stqh_last = &(elm)->field.stqe_next;            \
236:         (head)->stqh_first = (elm);                                     \
237: } while (/*CONSTCOND*/0)
238: 
239: #define STAILQ_INSERT_TAIL(head, elm, field) do {                       \
240:         (elm)->field.stqe_next = NULL;                                  \
241:         *(head)->stqh_last = (elm);                                     \
242:         (head)->stqh_last = &(elm)->field.stqe_next;                    \
243: } while (/*CONSTCOND*/0)
244: 
245: #define STAILQ_INSERT_AFTER(head, listelm, elm, field) do {             \
246:         if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\
247:                 (head)->stqh_last = &(elm)->field.stqe_next;            \
248:         (listelm)->field.stqe_next = (elm);                             \
249: } while (/*CONSTCOND*/0)
250: 
251: #define STAILQ_REMOVE_HEAD(head, field) do {                            \
252:         if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \
253:                 (head)->stqh_last = &(head)->stqh_first;                        \
254: } while (/*CONSTCOND*/0)
255: 
256: #define STAILQ_REMOVE(head, elm, type, field) do {                      \
257:         if ((head)->stqh_first == (elm)) {                              \
258:                 STAILQ_REMOVE_HEAD((head), field);                      \
259:         } else {                                                        \
260:                 struct type *curelm = (head)->stqh_first;               \
261:                 while (curelm->field.stqe_next != (elm))                        \
262:                         curelm = curelm->field.stqe_next;               \
263:                 if ((curelm->field.stqe_next =                          \
264:                         curelm->field.stqe_next->field.stqe_next) == NULL) \
265:                             (head)->stqh_last = &(curelm)->field.stqe_next; \
266:         }                                                               \
267: } while (/*CONSTCOND*/0)
268: 
269: #define STAILQ_FOREACH(var, head, field)                                \
270:         for ((var) = ((head)->stqh_first);                              \
271:                 (var);                                                  \
272:                 (var) = ((var)->field.stqe_next))
273: 
274: #define STAILQ_CONCAT(head1, head2) do {                                \
275:         if (!STAILQ_EMPTY((head2))) {                                   \
276:                 *(head1)->stqh_last = (head2)->stqh_first;              \
277:                 (head1)->stqh_last = (head2)->stqh_last;                \
278:                 STAILQ_INIT((head2));                                   \
279:         }                                                               \
280: } while (/*CONSTCOND*/0)
281: 
282: /*
283:  * Singly-linked Tail queue access methods.
284:  */
285: #define STAILQ_EMPTY(head)      ((head)->stqh_first == NULL)
286: #define STAILQ_FIRST(head)      ((head)->stqh_first)
287: #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
288: 
289: 
290: /*
291:  * Simple queue definitions.
292:  */
293: #define SIMPLEQ_HEAD(name, type)                                        \
294: struct name {                                                           \
295:         struct type *sqh_first; /* first element */                     \
296:         struct type **sqh_last; /* addr of last next element */         \
297: }
298: 
299: #define SIMPLEQ_HEAD_INITIALIZER(head)                                  \
300:         { NULL, &(head).sqh_first }
301: 
302: #define SIMPLEQ_ENTRY(type)                                             \
303: struct {                                                                \
304:         struct type *sqe_next;  /* next element */                      \
305: }
306: 
307: /*
308:  * Simple queue functions.
309:  */
310: #define SIMPLEQ_INIT(head) do {                                         \
311:         (head)->sqh_first = NULL;                                       \
312:         (head)->sqh_last = &(head)->sqh_first;                          \
313: } while (/*CONSTCOND*/0)
314: 
315: #define SIMPLEQ_INSERT_HEAD(head, elm, field) do {                      \
316:         if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)        \
317:                 (head)->sqh_last = &(elm)->field.sqe_next;              \
318:         (head)->sqh_first = (elm);                                      \
319: } while (/*CONSTCOND*/0)
320: 
321: #define SIMPLEQ_INSERT_TAIL(head, elm, field) do {                      \
322:         (elm)->field.sqe_next = NULL;                                   \
323:         *(head)->sqh_last = (elm);                                      \
324:         (head)->sqh_last = &(elm)->field.sqe_next;                      \
325: } while (/*CONSTCOND*/0)
326: 
327: #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {            \
328:         if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
329:                 (head)->sqh_last = &(elm)->field.sqe_next;              \
330:         (listelm)->field.sqe_next = (elm);                              \
331: } while (/*CONSTCOND*/0)
332: 
333: #define SIMPLEQ_REMOVE_HEAD(head, field) do {                           \
334:         if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
335:                 (head)->sqh_last = &(head)->sqh_first;                  \
336: } while (/*CONSTCOND*/0)
337: 
338: #define SIMPLEQ_REMOVE(head, elm, type, field) do {                     \
339:         if ((head)->sqh_first == (elm)) {                               \
340:                 SIMPLEQ_REMOVE_HEAD((head), field);                     \
341:         } else {                                                        \
342:                 struct type *curelm = (head)->sqh_first;                \
343:                 while (curelm->field.sqe_next != (elm))                 \
344:                         curelm = curelm->field.sqe_next;                \
345:                 if ((curelm->field.sqe_next =                           \
346:                         curelm->field.sqe_next->field.sqe_next) == NULL) \
347:                             (head)->sqh_last = &(curelm)->field.sqe_next; \
348:         }                                                               \
349: } while (/*CONSTCOND*/0)
350: 
351: #define SIMPLEQ_FOREACH(var, head, field)                               \
352:         for ((var) = ((head)->sqh_first);                               \
353:                 (var);                                                  \
354:                 (var) = ((var)->field.sqe_next))
355: 
356: /*
357:  * Simple queue access methods.
358:  */
359: #define SIMPLEQ_EMPTY(head)             ((head)->sqh_first == NULL)
360: #define SIMPLEQ_FIRST(head)             ((head)->sqh_first)
361: #define SIMPLEQ_NEXT(elm, field)        ((elm)->field.sqe_next)
362: 
363: 
364: /*
365:  * Tail queue definitions.
366:  */
367: #define _TAILQ_HEAD(name, type, qual)                                   \
368: struct name {                                                           \
369:         qual type *tqh_first;           /* first element */             \
370:         qual type *qual *tqh_last;      /* addr of last next element */ \
371: }
372: #define TAILQ_HEAD(name, type)  _TAILQ_HEAD(name, struct type,)
373: 
374: #define TAILQ_HEAD_INITIALIZER(head)                                    \
375:         { NULL, &(head).tqh_first }
376: 
377: #define _TAILQ_ENTRY(type, qual)                                        \
378: struct {                                                                \
379:         qual type *tqe_next;            /* next element */              \
380:         qual type *qual *tqe_prev;      /* address of previous next element */\
381: }
382: #define TAILQ_ENTRY(type)       _TAILQ_ENTRY(struct type,)
383: 
384: /*
385:  * Tail queue functions.
386:  */
387: #define TAILQ_INIT(head) do {                                           \
388:         (head)->tqh_first = NULL;                                       \
389:         (head)->tqh_last = &(head)->tqh_first;                          \
390: } while (/*CONSTCOND*/0)
391: 
392: #define TAILQ_INSERT_HEAD(head, elm, field) do {                        \
393:         if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)        \
394:                 (head)->tqh_first->field.tqe_prev =                     \
395:                     &(elm)->field.tqe_next;                             \
396:         else                                                            \
397:                 (head)->tqh_last = &(elm)->field.tqe_next;              \
398:         (head)->tqh_first = (elm);                                      \
399:         (elm)->field.tqe_prev = &(head)->tqh_first;                     \
400: } while (/*CONSTCOND*/0)
401: 
402: #define TAILQ_INSERT_TAIL(head, elm, field) do {                        \
403:         (elm)->field.tqe_next = NULL;                                   \
404:         (elm)->field.tqe_prev = (head)->tqh_last;                       \
405:         *(head)->tqh_last = (elm);                                      \
406:         (head)->tqh_last = &(elm)->field.tqe_next;                      \
407: } while (/*CONSTCOND*/0)
408: 
409: #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {              \
410:         if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
411:                 (elm)->field.tqe_next->field.tqe_prev =                 \
412:                     &(elm)->field.tqe_next;                             \
413:         else                                                            \
414:                 (head)->tqh_last = &(elm)->field.tqe_next;              \
415:         (listelm)->field.tqe_next = (elm);                              \
416:         (elm)->field.tqe_prev = &(listelm)->field.tqe_next;             \
417: } while (/*CONSTCOND*/0)
418: 
419: #define TAILQ_INSERT_BEFORE(listelm, elm, field) do {                   \
420:         (elm)->field.tqe_prev = (listelm)->field.tqe_prev;              \
421:         (elm)->field.tqe_next = (listelm);                              \
422:         *(listelm)->field.tqe_prev = (elm);                             \
423:         (listelm)->field.tqe_prev = &(elm)->field.tqe_next;             \
424: } while (/*CONSTCOND*/0)
425: 
426: #define TAILQ_REMOVE(head, elm, field) do {                             \
427:         if (((elm)->field.tqe_next) != NULL)                            \
428:                 (elm)->field.tqe_next->field.tqe_prev =                 \
429:                     (elm)->field.tqe_prev;                              \
430:         else                                                            \
431:                 (head)->tqh_last = (elm)->field.tqe_prev;               \
432:         *(elm)->field.tqe_prev = (elm)->field.tqe_next;                 \
433: } while (/*CONSTCOND*/0)
434: 
435: #define TAILQ_FOREACH(var, head, field)                                 \
436:         for ((var) = ((head)->tqh_first);                               \
437:                 (var);                                                  \
438:                 (var) = ((var)->field.tqe_next))
439: 
440: #define TAILQ_FOREACH_REVERSE(var, head, headname, field)               \
441:         for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));    \
442:                 (var);                                                  \
443:                 (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
444: 
445: #define TAILQ_CONCAT(head1, head2, field) do {                          \
446:         if (!TAILQ_EMPTY(head2)) {                                      \
447:                 *(head1)->tqh_last = (head2)->tqh_first;                \
448:                 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
449:                 (head1)->tqh_last = (head2)->tqh_last;                  \
450:                 TAILQ_INIT((head2));                                    \
451:         }                                                               \
452: } while (/*CONSTCOND*/0)
453: 
454: /*
455:  * Tail queue access methods.
456:  */
457: #define TAILQ_EMPTY(head)               ((head)->tqh_first == NULL)
458: #define TAILQ_FIRST(head)               ((head)->tqh_first)
459: #define TAILQ_NEXT(elm, field)          ((elm)->field.tqe_next)
460: 
461: #define TAILQ_LAST(head, headname) \
462:         (*(((struct headname *)((head)->tqh_last))->tqh_last))
463: #define TAILQ_PREV(elm, headname, field) \
464:         (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
465: 
466: 
467: /*
468:  * Circular queue definitions.
469:  */
470: #define CIRCLEQ_HEAD(name, type)                                        \
471: struct name {                                                           \
472:         struct type *cqh_first;         /* first element */             \
473:         struct type *cqh_last;          /* last element */              \
474: }
475: 
476: #define CIRCLEQ_HEAD_INITIALIZER(head)                                  \
477:         { (void *)&head, (void *)&head }
478: 
479: #define CIRCLEQ_ENTRY(type)                                             \
480: struct {                                                                \
481:         struct type *cqe_next;          /* next element */              \
482:         struct type *cqe_prev;          /* previous element */          \
483: }
484: 
485: /*
486:  * Circular queue functions.
487:  */
488: #define CIRCLEQ_INIT(head) do {                                         \
489:         (head)->cqh_first = (void *)(head);                             \
490:         (head)->cqh_last = (void *)(head);                              \
491: } while (/*CONSTCOND*/0)
492: 
493: #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {            \
494:         (elm)->field.cqe_next = (listelm)->field.cqe_next;              \
495:         (elm)->field.cqe_prev = (listelm);                              \
496:         if ((listelm)->field.cqe_next == (void *)(head))                \
497:                 (head)->cqh_last = (elm);                               \
498:         else                                                            \
499:                 (listelm)->field.cqe_next->field.cqe_prev = (elm);      \
500:         (listelm)->field.cqe_next = (elm);                              \
501: } while (/*CONSTCOND*/0)
502: 
503: #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {           \
504:         (elm)->field.cqe_next = (listelm);                              \
505:         (elm)->field.cqe_prev = (listelm)->field.cqe_prev;              \
506:         if ((listelm)->field.cqe_prev == (void *)(head))                \
507:                 (head)->cqh_first = (elm);                              \
508:         else                                                            \
509:                 (listelm)->field.cqe_prev->field.cqe_next = (elm);      \
510:         (listelm)->field.cqe_prev = (elm);                              \
511: } while (/*CONSTCOND*/0)
512: 
513: #define CIRCLEQ_INSERT_HEAD(head, elm, field) do {                      \
514:         (elm)->field.cqe_next = (head)->cqh_first;                      \
515:         (elm)->field.cqe_prev = (void *)(head);                         \
516:         if ((head)->cqh_last == (void *)(head))                         \
517:                 (head)->cqh_last = (elm);                               \
518:         else                                                            \
519:                 (head)->cqh_first->field.cqe_prev = (elm);              \
520:         (head)->cqh_first = (elm);                                      \
521: } while (/*CONSTCOND*/0)
522: 
523: #define CIRCLEQ_INSERT_TAIL(head, elm, field) do {                      \
524:         (elm)->field.cqe_next = (void *)(head);                         \
525:         (elm)->field.cqe_prev = (head)->cqh_last;                       \
526:         if ((head)->cqh_first == (void *)(head))                        \
527:                 (head)->cqh_first = (elm);                              \
528:         else                                                            \
529:                 (head)->cqh_last->field.cqe_next = (elm);               \
530:         (head)->cqh_last = (elm);                                       \
531: } while (/*CONSTCOND*/0)
532: 
533: #define CIRCLEQ_REMOVE(head, elm, field) do {                           \
534:         if ((elm)->field.cqe_next == (void *)(head))                    \
535:                 (head)->cqh_last = (elm)->field.cqe_prev;               \
536:         else                                                            \
537:                 (elm)->field.cqe_next->field.cqe_prev =                 \
538:                     (elm)->field.cqe_prev;                              \
539:         if ((elm)->field.cqe_prev == (void *)(head))                    \
540:                 (head)->cqh_first = (elm)->field.cqe_next;              \
541:         else                                                            \
542:                 (elm)->field.cqe_prev->field.cqe_next =                 \
543:                     (elm)->field.cqe_next;                              \
544: } while (/*CONSTCOND*/0)
545: 
546: #define CIRCLEQ_FOREACH(var, head, field)                               \
547:         for ((var) = ((head)->cqh_first);                               \
548:                 (var) != (const void *)(head);                          \
549:                 (var) = ((var)->field.cqe_next))
550: 
551: #define CIRCLEQ_FOREACH_REVERSE(var, head, field)                       \
552:         for ((var) = ((head)->cqh_last);                                \
553:                 (var) != (const void *)(head);                          \
554:                 (var) = ((var)->field.cqe_prev))
555: 
556: /*
557:  * Circular queue access methods.
558:  */
559: #define CIRCLEQ_EMPTY(head)             ((head)->cqh_first == (void *)(head))
560: #define CIRCLEQ_FIRST(head)             ((head)->cqh_first)
561: #define CIRCLEQ_LAST(head)              ((head)->cqh_last)
562: #define CIRCLEQ_NEXT(elm, field)        ((elm)->field.cqe_next)
563: #define CIRCLEQ_PREV(elm, field)        ((elm)->field.cqe_prev)
564: 
565: #define CIRCLEQ_LOOP_NEXT(head, elm, field)                             \
566:         (((elm)->field.cqe_next == (void *)(head))                      \
567:             ? ((head)->cqh_first)                                       \
568:             : (elm->field.cqe_next))
569: #define CIRCLEQ_LOOP_PREV(head, elm, field)                             \
570:         (((elm)->field.cqe_prev == (void *)(head))                      \
571:             ? ((head)->cqh_last)                                        \
572:             : (elm->field.cqe_prev))
573: 
574: #endif  /* sys/queue.h */
575: 

---

---

---