1/*
2 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28/*-
29 * Copyright (c) 1991, 1993
30 * The Regents of the University of California. All rights reserved.
31 *
32 * Redistribution and use in source and binary forms, with or without
33 * modification, are permitted provided that the following conditions
34 * are met:
35 * 1. Redistributions of source code must retain the above copyright
36 * notice, this list of conditions and the following disclaimer.
37 * 2. Redistributions in binary form must reproduce the above copyright
38 * notice, this list of conditions and the following disclaimer in the
39 * documentation and/or other materials provided with the distribution.
40 * 4. Neither the name of the University nor the names of its contributors
41 * may be used to endorse or promote products derived from this software
42 * without specific prior written permission.
43 *
44 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
45 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
46 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
47 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
48 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
49 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
50 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
51 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
52 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
53 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
54 * SUCH DAMAGE.
55 *
56 * @(#)queue.h 8.5 (Berkeley) 8/20/94
57 */
58
59#ifndef _SYS_QUEUE_H_
60#define _SYS_QUEUE_H_
61
62#ifndef __improbable
63#define __improbable(x) (x) /* noop in userspace */
64#endif /* __improbable */
65
66/*
67 * This file defines five types of data structures: singly-linked lists,
68 * singly-linked tail queues, lists, tail queues, and circular queues.
69 *
70 * A singly-linked list is headed by a single forward pointer. The elements
71 * are singly linked for minimum space and pointer manipulation overhead at
72 * the expense of O(n) removal for arbitrary elements. New elements can be
73 * added to the list after an existing element or at the head of the list.
74 * Elements being removed from the head of the list should use the explicit
75 * macro for this purpose for optimum efficiency. A singly-linked list may
76 * only be traversed in the forward direction. Singly-linked lists are ideal
77 * for applications with large datasets and few or no removals or for
78 * implementing a LIFO queue.
79 *
80 * A singly-linked tail queue is headed by a pair of pointers, one to the
81 * head of the list and the other to the tail of the list. The elements are
82 * singly linked for minimum space and pointer manipulation overhead at the
83 * expense of O(n) removal for arbitrary elements. New elements can be added
84 * to the list after an existing element, at the head of the list, or at the
85 * end of the list. Elements being removed from the head of the tail queue
86 * should use the explicit macro for this purpose for optimum efficiency.
87 * A singly-linked tail queue may only be traversed in the forward direction.
88 * Singly-linked tail queues are ideal for applications with large datasets
89 * and few or no removals or for implementing a FIFO queue.
90 *
91 * A list is headed by a single forward pointer (or an array of forward
92 * pointers for a hash table header). The elements are doubly linked
93 * so that an arbitrary element can be removed without a need to
94 * traverse the list. New elements can be added to the list before
95 * or after an existing element or at the head of the list. A list
96 * may only be traversed in the forward direction.
97 *
98 * A tail queue is headed by a pair of pointers, one to the head of the
99 * list and the other to the tail of the list. The elements are doubly
100 * linked so that an arbitrary element can be removed without a need to
101 * traverse the list. New elements can be added to the list before or
102 * after an existing element, at the head of the list, or at the end of
103 * the list. A tail queue may be traversed in either direction.
104 *
105 * A circle queue is headed by a pair of pointers, one to the head of the
106 * list and the other to the tail of the list. The elements are doubly
107 * linked so that an arbitrary element can be removed without a need to
108 * traverse the list. New elements can be added to the list before or after
109 * an existing element, at the head of the list, or at the end of the list.
110 * A circle queue may be traversed in either direction, but has a more
111 * complex end of list detection.
112 * Note that circle queues are deprecated, because, as the removal log
113 * in FreeBSD states, "CIRCLEQs are a disgrace to everything Knuth taught
114 * us in Volume 1 Chapter 2. [...] Use TAILQ instead, it provides the same
115 * functionality." Code using them will continue to compile, but they
116 * are no longer documented on the man page.
117 *
118 * For details on the use of these macros, see the queue(3) manual page.
119 *
120 *
121 * SLIST LIST STAILQ TAILQ CIRCLEQ
122 * _HEAD + + + + +
123 * _HEAD_INITIALIZER + + + + -
124 * _ENTRY + + + + +
125 * _INIT + + + + +
126 * _EMPTY + + + + +
127 * _FIRST + + + + +
128 * _NEXT + + + + +
129 * _PREV - - - + +
130 * _LAST - - + + +
131 * _FOREACH + + + + +
132 * _FOREACH_SAFE + + + + -
133 * _FOREACH_REVERSE - - - + -
134 * _FOREACH_REVERSE_SAFE - - - + -
135 * _INSERT_HEAD + + + + +
136 * _INSERT_BEFORE - + - + +
137 * _INSERT_AFTER + + + + +
138 * _INSERT_TAIL - - + + +
139 * _CONCAT - - + + -
140 * _REMOVE_AFTER + - + - -
141 * _REMOVE_HEAD + - + - -
142 * _REMOVE_HEAD_UNTIL - - + - -
143 * _REMOVE + + + + +
144 * _SWAP - + + + -
145 *
146 */
147#ifdef QUEUE_MACRO_DEBUG
148/* Store the last 2 places the queue element or head was altered */
149struct qm_trace {
150 char * lastfile;
151 int lastline;
152 char * prevfile;
153 int prevline;
154};
155
156#define TRACEBUF struct qm_trace trace;
157#define TRASHIT(x) do {(x) = (void *)-1;} while (0)
158
159#define QMD_TRACE_HEAD(head) do { \
160 (head)->trace.prevline = (head)->trace.lastline; \
161 (head)->trace.prevfile = (head)->trace.lastfile; \
162 (head)->trace.lastline = __LINE__; \
163 (head)->trace.lastfile = __FILE__; \
164} while (0)
165
166#define QMD_TRACE_ELEM(elem) do { \
167 (elem)->trace.prevline = (elem)->trace.lastline; \
168 (elem)->trace.prevfile = (elem)->trace.lastfile; \
169 (elem)->trace.lastline = __LINE__; \
170 (elem)->trace.lastfile = __FILE__; \
171} while (0)
172
173#else
174#define QMD_TRACE_ELEM(elem)
175#define QMD_TRACE_HEAD(head)
176#define TRACEBUF
177#define TRASHIT(x)
178#endif /* QUEUE_MACRO_DEBUG */
179
180/*
181 * Horrible macros to enable use of code that was meant to be C-specific
182 * (and which push struct onto type) in C++; without these, C++ code
183 * that uses these macros in the context of a class will blow up
184 * due to "struct" being preprended to "type" by the macros, causing
185 * inconsistent use of tags.
186 *
187 * This approach is necessary because these are macros; we have to use
188 * these on a per-macro basis (because the queues are implemented as
189 * macros, disabling this warning in the scope of the header file is
190 * insufficient), whuch means we can't use #pragma, and have to use
191 * _Pragma. We only need to use these for the queue macros that
192 * prepend "struct" to "type" and will cause C++ to blow up.
193 */
194#if defined(__clang__) && defined(__cplusplus)
195#define __MISMATCH_TAGS_PUSH \
196 _Pragma("clang diagnostic push") \
197 _Pragma("clang diagnostic ignored \"-Wmismatched-tags\"")
198#define __MISMATCH_TAGS_POP \
199 _Pragma("clang diagnostic pop")
200#else
201#define __MISMATCH_TAGS_PUSH
202#define __MISMATCH_TAGS_POP
203#endif
204
205/*!
206 * Ensures that these macros can safely be used in structs when compiling with
207 * clang. The macros do not allow for nullability attributes to be specified due
208 * to how they are expanded. For example:
209 *
210 * SLIST_HEAD(, foo _Nullable) bar;
211 *
212 * expands to
213 *
214 * struct {
215 * struct foo _Nullable *slh_first;
216 * }
217 *
218 * which is not valid because the nullability specifier has to apply to the
219 * pointer. So just ignore nullability completeness in all the places where this
220 * is an issue.
221 */
222#if defined(__clang__)
223#define __NULLABILITY_COMPLETENESS_PUSH \
224 _Pragma("clang diagnostic push") \
225 _Pragma("clang diagnostic ignored \"-Wnullability-completeness\"")
226#define __NULLABILITY_COMPLETENESS_POP \
227 _Pragma("clang diagnostic pop")
228#else
229#define __NULLABILITY_COMPLETENESS_PUSH
230#define __NULLABILITY_COMPLETENESS_POP
231#endif
232
233/*
234 * Singly-linked List declarations.
235 */
236#define SLIST_HEAD(name, type) \
237__MISMATCH_TAGS_PUSH \
238__NULLABILITY_COMPLETENESS_PUSH \
239struct name { \
240 struct type *slh_first; /* first element */ \
241} \
242__NULLABILITY_COMPLETENESS_POP \
243__MISMATCH_TAGS_POP
244
245#define SLIST_HEAD_INITIALIZER(head) \
246 { NULL }
247
248#define SLIST_ENTRY(type) \
249__MISMATCH_TAGS_PUSH \
250__NULLABILITY_COMPLETENESS_PUSH \
251struct { \
252 struct type *sle_next; /* next element */ \
253} \
254__NULLABILITY_COMPLETENESS_POP \
255__MISMATCH_TAGS_POP
256
257/*
258 * Singly-linked List functions.
259 */
260#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
261
262#define SLIST_FIRST(head) ((head)->slh_first)
263
264#define SLIST_FOREACH(var, head, field) \
265 for ((var) = SLIST_FIRST((head)); \
266 (var); \
267 (var) = SLIST_NEXT((var), field))
268
269#define SLIST_FOREACH_SAFE(var, head, field, tvar) \
270 for ((var) = SLIST_FIRST((head)); \
271 (var) && ((tvar) = SLIST_NEXT((var), field), 1); \
272 (var) = (tvar))
273
274#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \
275 for ((varp) = &SLIST_FIRST((head)); \
276 ((var) = *(varp)) != NULL; \
277 (varp) = &SLIST_NEXT((var), field))
278
279#define SLIST_INIT(head) do { \
280 SLIST_FIRST((head)) = NULL; \
281} while (0)
282
283#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
284 SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
285 SLIST_NEXT((slistelm), field) = (elm); \
286} while (0)
287
288#define SLIST_INSERT_HEAD(head, elm, field) do { \
289 SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
290 SLIST_FIRST((head)) = (elm); \
291} while (0)
292
293#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
294
295#define SLIST_REMOVE(head, elm, type, field) \
296__MISMATCH_TAGS_PUSH \
297__NULLABILITY_COMPLETENESS_PUSH \
298do { \
299 if (SLIST_FIRST((head)) == (elm)) { \
300 SLIST_REMOVE_HEAD((head), field); \
301 } \
302 else { \
303 struct type *curelm = SLIST_FIRST((head)); \
304 while (SLIST_NEXT(curelm, field) != (elm)) \
305 curelm = SLIST_NEXT(curelm, field); \
306 SLIST_REMOVE_AFTER(curelm, field); \
307 } \
308 TRASHIT((elm)->field.sle_next); \
309} while (0) \
310__NULLABILITY_COMPLETENESS_POP \
311__MISMATCH_TAGS_POP
312
313#define SLIST_REMOVE_AFTER(elm, field) do { \
314 SLIST_NEXT(elm, field) = \
315 SLIST_NEXT(SLIST_NEXT(elm, field), field); \
316} while (0)
317
318#define SLIST_REMOVE_HEAD(head, field) do { \
319 SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \
320} while (0)
321
322/*
323 * Singly-linked Tail queue declarations.
324 */
325#define STAILQ_HEAD(name, type) \
326__MISMATCH_TAGS_PUSH \
327__NULLABILITY_COMPLETENESS_PUSH \
328struct name { \
329 struct type *stqh_first;/* first element */ \
330 struct type **stqh_last;/* addr of last next element */ \
331} \
332__NULLABILITY_COMPLETENESS_POP \
333__MISMATCH_TAGS_POP
334
335#define STAILQ_HEAD_INITIALIZER(head) \
336 { NULL, &(head).stqh_first }
337
338#define STAILQ_ENTRY(type) \
339__MISMATCH_TAGS_PUSH \
340__NULLABILITY_COMPLETENESS_PUSH \
341struct { \
342 struct type *stqe_next; /* next element */ \
343} \
344__NULLABILITY_COMPLETENESS_POP \
345__MISMATCH_TAGS_POP
346
347/*
348 * Singly-linked Tail queue functions.
349 */
350#define STAILQ_CONCAT(head1, head2) do { \
351 if (!STAILQ_EMPTY((head2))) { \
352 *(head1)->stqh_last = (head2)->stqh_first; \
353 (head1)->stqh_last = (head2)->stqh_last; \
354 STAILQ_INIT((head2)); \
355 } \
356} while (0)
357
358#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
359
360#define STAILQ_FIRST(head) ((head)->stqh_first)
361
362#define STAILQ_FOREACH(var, head, field) \
363 for((var) = STAILQ_FIRST((head)); \
364 (var); \
365 (var) = STAILQ_NEXT((var), field))
366
367
368#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
369 for ((var) = STAILQ_FIRST((head)); \
370 (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
371 (var) = (tvar))
372
373#define STAILQ_INIT(head) do { \
374 STAILQ_FIRST((head)) = NULL; \
375 (head)->stqh_last = &STAILQ_FIRST((head)); \
376} while (0)
377
378#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
379 if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
380 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
381 STAILQ_NEXT((tqelm), field) = (elm); \
382} while (0)
383
384#define STAILQ_INSERT_HEAD(head, elm, field) do { \
385 if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
386 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
387 STAILQ_FIRST((head)) = (elm); \
388} while (0)
389
390#define STAILQ_INSERT_TAIL(head, elm, field) do { \
391 STAILQ_NEXT((elm), field) = NULL; \
392 *(head)->stqh_last = (elm); \
393 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
394} while (0)
395
396#define STAILQ_LAST(head, type, field) \
397__MISMATCH_TAGS_PUSH \
398__NULLABILITY_COMPLETENESS_PUSH \
399 (STAILQ_EMPTY((head)) ? \
400 NULL : \
401 ((struct type *)(void *) \
402 ((char *)((head)->stqh_last) - __offsetof(struct type, field))))\
403__NULLABILITY_COMPLETENESS_POP \
404__MISMATCH_TAGS_POP
405
406#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
407
408#define STAILQ_REMOVE(head, elm, type, field) \
409__MISMATCH_TAGS_PUSH \
410__NULLABILITY_COMPLETENESS_PUSH \
411do { \
412 if (STAILQ_FIRST((head)) == (elm)) { \
413 STAILQ_REMOVE_HEAD((head), field); \
414 } \
415 else { \
416 struct type *curelm = STAILQ_FIRST((head)); \
417 while (STAILQ_NEXT(curelm, field) != (elm)) \
418 curelm = STAILQ_NEXT(curelm, field); \
419 STAILQ_REMOVE_AFTER(head, curelm, field); \
420 } \
421 TRASHIT((elm)->field.stqe_next); \
422} while (0) \
423__NULLABILITY_COMPLETENESS_POP \
424__MISMATCH_TAGS_POP
425
426#define STAILQ_REMOVE_HEAD(head, field) do { \
427 if ((STAILQ_FIRST((head)) = \
428 STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \
429 (head)->stqh_last = &STAILQ_FIRST((head)); \
430} while (0)
431
432#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \
433 if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \
434 (head)->stqh_last = &STAILQ_FIRST((head)); \
435} while (0)
436
437#define STAILQ_REMOVE_AFTER(head, elm, field) do { \
438 if ((STAILQ_NEXT(elm, field) = \
439 STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \
440 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
441} while (0)
442
443#define STAILQ_SWAP(head1, head2, type) \
444__MISMATCH_TAGS_PUSH \
445__NULLABILITY_COMPLETENESS_PUSH \
446do { \
447 struct type *swap_first = STAILQ_FIRST(head1); \
448 struct type **swap_last = (head1)->stqh_last; \
449 STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \
450 (head1)->stqh_last = (head2)->stqh_last; \
451 STAILQ_FIRST(head2) = swap_first; \
452 (head2)->stqh_last = swap_last; \
453 if (STAILQ_EMPTY(head1)) \
454 (head1)->stqh_last = &STAILQ_FIRST(head1); \
455 if (STAILQ_EMPTY(head2)) \
456 (head2)->stqh_last = &STAILQ_FIRST(head2); \
457} while (0) \
458__NULLABILITY_COMPLETENESS_POP \
459__MISMATCH_TAGS_POP
460
461
462/*
463 * List declarations.
464 */
465#define LIST_HEAD(name, type) \
466__MISMATCH_TAGS_PUSH \
467__NULLABILITY_COMPLETENESS_PUSH \
468struct name { \
469 struct type *lh_first; /* first element */ \
470} \
471__NULLABILITY_COMPLETENESS_POP \
472__MISMATCH_TAGS_POP
473
474#define LIST_HEAD_INITIALIZER(head) \
475 { NULL }
476
477#define LIST_ENTRY(type) \
478__MISMATCH_TAGS_PUSH \
479__NULLABILITY_COMPLETENESS_PUSH \
480struct { \
481 struct type *le_next; /* next element */ \
482 struct type **le_prev; /* address of previous next element */ \
483} \
484__NULLABILITY_COMPLETENESS_POP \
485__MISMATCH_TAGS_POP
486
487/*
488 * List functions.
489 */
490
491#define LIST_CHECK_HEAD(head, field)
492#define LIST_CHECK_NEXT(elm, field)
493#define LIST_CHECK_PREV(elm, field)
494
495#define LIST_EMPTY(head) ((head)->lh_first == NULL)
496
497#define LIST_FIRST(head) ((head)->lh_first)
498
499#define LIST_FOREACH(var, head, field) \
500 for ((var) = LIST_FIRST((head)); \
501 (var); \
502 (var) = LIST_NEXT((var), field))
503
504#define LIST_FOREACH_SAFE(var, head, field, tvar) \
505 for ((var) = LIST_FIRST((head)); \
506 (var) && ((tvar) = LIST_NEXT((var), field), 1); \
507 (var) = (tvar))
508
509#define LIST_INIT(head) do { \
510 LIST_FIRST((head)) = NULL; \
511} while (0)
512
513#define LIST_INSERT_AFTER(listelm, elm, field) do { \
514 LIST_CHECK_NEXT(listelm, field); \
515 if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
516 LIST_NEXT((listelm), field)->field.le_prev = \
517 &LIST_NEXT((elm), field); \
518 LIST_NEXT((listelm), field) = (elm); \
519 (elm)->field.le_prev = &LIST_NEXT((listelm), field); \
520} while (0)
521
522#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
523 LIST_CHECK_PREV(listelm, field); \
524 (elm)->field.le_prev = (listelm)->field.le_prev; \
525 LIST_NEXT((elm), field) = (listelm); \
526 *(listelm)->field.le_prev = (elm); \
527 (listelm)->field.le_prev = &LIST_NEXT((elm), field); \
528} while (0)
529
530#define LIST_INSERT_HEAD(head, elm, field) do { \
531 LIST_CHECK_HEAD((head), field); \
532 if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
533 LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
534 LIST_FIRST((head)) = (elm); \
535 (elm)->field.le_prev = &LIST_FIRST((head)); \
536} while (0)
537
538#define LIST_NEXT(elm, field) ((elm)->field.le_next)
539
540#define LIST_REMOVE(elm, field) do { \
541 LIST_CHECK_NEXT(elm, field); \
542 LIST_CHECK_PREV(elm, field); \
543 if (LIST_NEXT((elm), field) != NULL) \
544 LIST_NEXT((elm), field)->field.le_prev = \
545 (elm)->field.le_prev; \
546 *(elm)->field.le_prev = LIST_NEXT((elm), field); \
547 TRASHIT((elm)->field.le_next); \
548 TRASHIT((elm)->field.le_prev); \
549} while (0)
550
551#define LIST_SWAP(head1, head2, type, field) \
552__MISMATCH_TAGS_PUSH \
553__NULLABILITY_COMPLETENESS_PUSH \
554do { \
555 struct type *swap_tmp = LIST_FIRST((head1)); \
556 LIST_FIRST((head1)) = LIST_FIRST((head2)); \
557 LIST_FIRST((head2)) = swap_tmp; \
558 if ((swap_tmp = LIST_FIRST((head1))) != NULL) \
559 swap_tmp->field.le_prev = &LIST_FIRST((head1)); \
560 if ((swap_tmp = LIST_FIRST((head2))) != NULL) \
561 swap_tmp->field.le_prev = &LIST_FIRST((head2)); \
562} while (0) \
563__NULLABILITY_COMPLETENESS_POP \
564__MISMATCH_TAGS_POP
565
566/*
567 * Tail queue declarations.
568 */
569#define TAILQ_HEAD(name, type) \
570__MISMATCH_TAGS_PUSH \
571__NULLABILITY_COMPLETENESS_PUSH \
572struct name { \
573 struct type *tqh_first; /* first element */ \
574 struct type **tqh_last; /* addr of last next element */ \
575 TRACEBUF \
576} \
577__NULLABILITY_COMPLETENESS_POP \
578__MISMATCH_TAGS_POP
579
580#define TAILQ_HEAD_INITIALIZER(head) \
581 { NULL, &(head).tqh_first }
582
583#define TAILQ_ENTRY(type) \
584__MISMATCH_TAGS_PUSH \
585__NULLABILITY_COMPLETENESS_PUSH \
586struct { \
587 struct type *tqe_next; /* next element */ \
588 struct type **tqe_prev; /* address of previous next element */ \
589 TRACEBUF \
590} \
591__NULLABILITY_COMPLETENESS_POP \
592__MISMATCH_TAGS_POP
593
594/*
595 * Tail queue functions.
596 */
597#define TAILQ_CHECK_HEAD(head, field)
598#define TAILQ_CHECK_NEXT(elm, field)
599#define TAILQ_CHECK_PREV(elm, field)
600
601#define TAILQ_CONCAT(head1, head2, field) do { \
602 if (!TAILQ_EMPTY(head2)) { \
603 *(head1)->tqh_last = (head2)->tqh_first; \
604 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
605 (head1)->tqh_last = (head2)->tqh_last; \
606 TAILQ_INIT((head2)); \
607 QMD_TRACE_HEAD(head1); \
608 QMD_TRACE_HEAD(head2); \
609 } \
610} while (0)
611
612#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
613
614#define TAILQ_FIRST(head) ((head)->tqh_first)
615
616#define TAILQ_FOREACH(var, head, field) \
617 for ((var) = TAILQ_FIRST((head)); \
618 (var); \
619 (var) = TAILQ_NEXT((var), field))
620
621#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
622 for ((var) = TAILQ_FIRST((head)); \
623 (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
624 (var) = (tvar))
625
626#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
627 for ((var) = TAILQ_LAST((head), headname); \
628 (var); \
629 (var) = TAILQ_PREV((var), headname, field))
630
631#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
632 for ((var) = TAILQ_LAST((head), headname); \
633 (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
634 (var) = (tvar))
635
636
637#define TAILQ_INIT(head) do { \
638 TAILQ_FIRST((head)) = NULL; \
639 (head)->tqh_last = &TAILQ_FIRST((head)); \
640 QMD_TRACE_HEAD(head); \
641} while (0)
642
643
644#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
645 TAILQ_CHECK_NEXT(listelm, field); \
646 if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
647 TAILQ_NEXT((elm), field)->field.tqe_prev = \
648 &TAILQ_NEXT((elm), field); \
649 else { \
650 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
651 QMD_TRACE_HEAD(head); \
652 } \
653 TAILQ_NEXT((listelm), field) = (elm); \
654 (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
655 QMD_TRACE_ELEM(&(elm)->field); \
656 QMD_TRACE_ELEM(&listelm->field); \
657} while (0)
658
659#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
660 TAILQ_CHECK_PREV(listelm, field); \
661 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
662 TAILQ_NEXT((elm), field) = (listelm); \
663 *(listelm)->field.tqe_prev = (elm); \
664 (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
665 QMD_TRACE_ELEM(&(elm)->field); \
666 QMD_TRACE_ELEM(&listelm->field); \
667} while (0)
668
669#define TAILQ_INSERT_HEAD(head, elm, field) do { \
670 TAILQ_CHECK_HEAD(head, field); \
671 if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
672 TAILQ_FIRST((head))->field.tqe_prev = \
673 &TAILQ_NEXT((elm), field); \
674 else \
675 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
676 TAILQ_FIRST((head)) = (elm); \
677 (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
678 QMD_TRACE_HEAD(head); \
679 QMD_TRACE_ELEM(&(elm)->field); \
680} while (0)
681
682#define TAILQ_INSERT_TAIL(head, elm, field) do { \
683 TAILQ_NEXT((elm), field) = NULL; \
684 (elm)->field.tqe_prev = (head)->tqh_last; \
685 *(head)->tqh_last = (elm); \
686 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
687 QMD_TRACE_HEAD(head); \
688 QMD_TRACE_ELEM(&(elm)->field); \
689} while (0)
690
691#define TAILQ_LAST(head, headname) \
692__MISMATCH_TAGS_PUSH \
693__NULLABILITY_COMPLETENESS_PUSH \
694 (*(((struct headname *)((head)->tqh_last))->tqh_last)) \
695__NULLABILITY_COMPLETENESS_POP \
696__MISMATCH_TAGS_POP
697
698#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
699
700#define TAILQ_PREV(elm, headname, field) \
701__MISMATCH_TAGS_PUSH \
702__NULLABILITY_COMPLETENESS_PUSH \
703 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) \
704__NULLABILITY_COMPLETENESS_POP \
705__MISMATCH_TAGS_POP
706
707#define TAILQ_REMOVE(head, elm, field) do { \
708 TAILQ_CHECK_NEXT(elm, field); \
709 TAILQ_CHECK_PREV(elm, field); \
710 if ((TAILQ_NEXT((elm), field)) != NULL) \
711 TAILQ_NEXT((elm), field)->field.tqe_prev = \
712 (elm)->field.tqe_prev; \
713 else { \
714 (head)->tqh_last = (elm)->field.tqe_prev; \
715 QMD_TRACE_HEAD(head); \
716 } \
717 *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
718 TRASHIT((elm)->field.tqe_next); \
719 TRASHIT((elm)->field.tqe_prev); \
720 QMD_TRACE_ELEM(&(elm)->field); \
721} while (0)
722
723/*
724 * Why did they switch to spaces for this one macro?
725 */
726#define TAILQ_SWAP(head1, head2, type, field) \
727__MISMATCH_TAGS_PUSH \
728__NULLABILITY_COMPLETENESS_PUSH \
729do { \
730 struct type *swap_first = (head1)->tqh_first; \
731 struct type **swap_last = (head1)->tqh_last; \
732 (head1)->tqh_first = (head2)->tqh_first; \
733 (head1)->tqh_last = (head2)->tqh_last; \
734 (head2)->tqh_first = swap_first; \
735 (head2)->tqh_last = swap_last; \
736 if ((swap_first = (head1)->tqh_first) != NULL) \
737 swap_first->field.tqe_prev = &(head1)->tqh_first; \
738 else \
739 (head1)->tqh_last = &(head1)->tqh_first; \
740 if ((swap_first = (head2)->tqh_first) != NULL) \
741 swap_first->field.tqe_prev = &(head2)->tqh_first; \
742 else \
743 (head2)->tqh_last = &(head2)->tqh_first; \
744} while (0) \
745__NULLABILITY_COMPLETENESS_POP \
746__MISMATCH_TAGS_POP
747
748/*
749 * Circular queue definitions.
750 */
751#define CIRCLEQ_HEAD(name, type) \
752__MISMATCH_TAGS_PUSH \
753__NULLABILITY_COMPLETENESS_PUSH \
754struct name { \
755 struct type *cqh_first; /* first element */ \
756 struct type *cqh_last; /* last element */ \
757} \
758__NULLABILITY_COMPLETENESS_POP \
759__MISMATCH_TAGS_POP
760
761#define CIRCLEQ_ENTRY(type) \
762__MISMATCH_TAGS_PUSH \
763__NULLABILITY_COMPLETENESS_PUSH \
764struct { \
765 struct type *cqe_next; /* next element */ \
766 struct type *cqe_prev; /* previous element */ \
767} \
768__NULLABILITY_COMPLETENESS_POP \
769__MISMATCH_TAGS_POP
770
771/*
772 * Circular queue functions.
773 */
774#define CIRCLEQ_CHECK_HEAD(head, field)
775#define CIRCLEQ_CHECK_NEXT(head, elm, field)
776#define CIRCLEQ_CHECK_PREV(head, elm, field)
777
778#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
779
780#define CIRCLEQ_FIRST(head) ((head)->cqh_first)
781
782#define CIRCLEQ_FOREACH(var, head, field) \
783 for((var) = (head)->cqh_first; \
784 (var) != (void *)(head); \
785 (var) = (var)->field.cqe_next)
786
787#define CIRCLEQ_INIT(head) do { \
788 (head)->cqh_first = (void *)(head); \
789 (head)->cqh_last = (void *)(head); \
790} while (0)
791
792#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
793 CIRCLEQ_CHECK_NEXT(head, listelm, field); \
794 (elm)->field.cqe_next = (listelm)->field.cqe_next; \
795 (elm)->field.cqe_prev = (listelm); \
796 if ((listelm)->field.cqe_next == (void *)(head)) \
797 (head)->cqh_last = (elm); \
798 else \
799 (listelm)->field.cqe_next->field.cqe_prev = (elm); \
800 (listelm)->field.cqe_next = (elm); \
801} while (0)
802
803#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
804 CIRCLEQ_CHECK_PREV(head, listelm, field); \
805 (elm)->field.cqe_next = (listelm); \
806 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
807 if ((listelm)->field.cqe_prev == (void *)(head)) \
808 (head)->cqh_first = (elm); \
809 else \
810 (listelm)->field.cqe_prev->field.cqe_next = (elm); \
811 (listelm)->field.cqe_prev = (elm); \
812} while (0)
813
814#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
815 CIRCLEQ_CHECK_HEAD(head, field); \
816 (elm)->field.cqe_next = (head)->cqh_first; \
817 (elm)->field.cqe_prev = (void *)(head); \
818 if ((head)->cqh_last == (void *)(head)) \
819 (head)->cqh_last = (elm); \
820 else \
821 (head)->cqh_first->field.cqe_prev = (elm); \
822 (head)->cqh_first = (elm); \
823} while (0)
824
825#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
826 (elm)->field.cqe_next = (void *)(head); \
827 (elm)->field.cqe_prev = (head)->cqh_last; \
828 if ((head)->cqh_first == (void *)(head)) \
829 (head)->cqh_first = (elm); \
830 else \
831 (head)->cqh_last->field.cqe_next = (elm); \
832 (head)->cqh_last = (elm); \
833} while (0)
834
835#define CIRCLEQ_LAST(head) ((head)->cqh_last)
836
837#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
838
839#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
840
841#define CIRCLEQ_REMOVE(head, elm, field) do { \
842 CIRCLEQ_CHECK_NEXT(head, elm, field); \
843 CIRCLEQ_CHECK_PREV(head, elm, field); \
844 if ((elm)->field.cqe_next == (void *)(head)) \
845 (head)->cqh_last = (elm)->field.cqe_prev; \
846 else \
847 (elm)->field.cqe_next->field.cqe_prev = \
848 (elm)->field.cqe_prev; \
849 if ((elm)->field.cqe_prev == (void *)(head)) \
850 (head)->cqh_first = (elm)->field.cqe_next; \
851 else \
852 (elm)->field.cqe_prev->field.cqe_next = \
853 (elm)->field.cqe_next; \
854} while (0)
855
856#ifdef _KERNEL
857
858#if NOTFB31
859
860/*
861 * XXX insque() and remque() are an old way of handling certain queues.
862 * They bogusly assumes that all queue heads look alike.
863 */
864
865struct quehead {
866 struct quehead *qh_link;
867 struct quehead *qh_rlink;
868};
869
870#ifdef __GNUC__
871#define chkquenext(a)
872#define chkqueprev(a)
873
874static __inline void
875insque(void *a, void *b)
876{
877 struct quehead *element = (struct quehead *)a,
878 *head = (struct quehead *)b;
879 chkquenext(head);
880
881 element->qh_link = head->qh_link;
882 element->qh_rlink = head;
883 head->qh_link = element;
884 element->qh_link->qh_rlink = element;
885}
886
887static __inline void
888remque(void *a)
889{
890 struct quehead *element = (struct quehead *)a;
891 chkquenext(element);
892 chkqueprev(element);
893
894 element->qh_link->qh_rlink = element->qh_rlink;
895 element->qh_rlink->qh_link = element->qh_link;
896 element->qh_rlink = 0;
897}
898
899#else /* !__GNUC__ */
900
901void insque(void *a, void *b);
902void remque(void *a);
903
904#endif /* __GNUC__ */
905
906#endif /* NOTFB31 */
907#endif /* _KERNEL */
908
909#endif /* !_SYS_QUEUE_H_ */