NeoMutt  2025-05-10
Teaching an old dog new tricks
 		DOXYGEN
Loading...
Searching...
No Matches
queue.h
Go to the documentation of this file.
1/*-
2 * SPDX-License-Identifier: BSD-3-Clause
3 *
4 * Copyright (c) 1991, 1993
5 * The Regents of the University of California. All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the University nor the names of its contributors
16 * may be used to endorse or promote products derived from this software
17 * without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 */
31
32#ifndef _SYS_QUEUE_H_
33#define _SYS_QUEUE_H_
34
35/*
36 * This file defines four types of data structures: singly-linked lists,
37 * singly-linked tail queues, lists and tail queues.
38 *
39 * A singly-linked list is headed by a single forward pointer. The elements
40 * are singly linked for minimum space and pointer manipulation overhead at
41 * the expense of O(n) removal for arbitrary elements. New elements can be
42 * added to the list after an existing element or at the head of the list.
43 * Elements being removed from the head of the list should use the explicit
44 * macro for this purpose for optimum efficiency. A singly-linked list may
45 * only be traversed in the forward direction. Singly-linked lists are ideal
46 * for applications with large datasets and few or no removals or for
47 * implementing a LIFO queue.
48 *
49 * A singly-linked tail queue is headed by a pair of pointers, one to the
50 * head of the list and the other to the tail of the list. The elements are
51 * singly linked for minimum space and pointer manipulation overhead at the
52 * expense of O(n) removal for arbitrary elements. New elements can be added
53 * to the list after an existing element, at the head of the list, or at the
54 * end of the list. Elements being removed from the head of the tail queue
55 * should use the explicit macro for this purpose for optimum efficiency.
56 * A singly-linked tail queue may only be traversed in the forward direction.
57 * Singly-linked tail queues are ideal for applications with large datasets
58 * and few or no removals or for implementing a FIFO queue.
59 *
60 * A list is headed by a single forward pointer (or an array of forward
61 * pointers for a hash table header). The elements are doubly linked
62 * so that an arbitrary element can be removed without a need to
63 * traverse the list. New elements can be added to the list before
64 * or after an existing element or at the head of the list. A list
65 * may be traversed in either direction.
66 *
67 * A tail queue is headed by a pair of pointers, one to the head of the
68 * list and the other to the tail of the list. The elements are doubly
69 * linked so that an arbitrary element can be removed without a need to
70 * traverse the list. New elements can be added to the list before or
71 * after an existing element, at the head of the list, or at the end of
72 * the list. A tail queue may be traversed in either direction.
73 *
74 * For details on the use of these macros, see the queue(3) manual page.
75 *
76 * Below is a summary of implemented functions where:
77 * + means the macro is available
78 * - means the macro is not available
79 * s means the macro is available but is slow (runs in O(n) time)
80 *
81 * SLIST LIST STAILQ TAILQ
82 * _HEAD + + + +
83 * _CLASS_HEAD + + + +
84 * _HEAD_INITIALIZER + + + +
85 * _ENTRY + + + +
86 * _CLASS_ENTRY + + + +
87 * _INIT + + + +
88 * _EMPTY + + + +
89 * _END + + + +
90 * _FIRST + + + +
91 * _NEXT + + + +
92 * _PREV - + - +
93 * _LAST - - + +
94 * _LAST_FAST - - - +
95 * _FOREACH + + + +
96 * _FOREACH_FROM + + + +
97 * _FOREACH_SAFE + + + +
98 * _FOREACH_FROM_SAFE + + + +
99 * _FOREACH_REVERSE - - - +
100 * _FOREACH_REVERSE_FROM - - - +
101 * _FOREACH_REVERSE_SAFE - - - +
102 * _FOREACH_REVERSE_FROM_SAFE - - - +
103 * _INSERT_HEAD + + + +
104 * _INSERT_BEFORE - + - +
105 * _INSERT_AFTER + + + +
106 * _INSERT_TAIL - - + +
107 * _CONCAT s s + +
108 * _REMOVE_AFTER + - + -
109 * _REMOVE_HEAD + + + +
110 * _REMOVE s + s +
111 * _REPLACE - + - +
112 * _SWAP + + + +
113 *
114 */
115#ifdef QUEUE_MACRO_DEBUG
116#warn Use QUEUE_MACRO_DEBUG_TRACE and/or QUEUE_MACRO_DEBUG_TRASH
117#define QUEUE_MACRO_DEBUG_TRACE
118#define QUEUE_MACRO_DEBUG_TRASH
119#endif
120
121#ifdef QUEUE_MACRO_DEBUG_TRACE
122/* Store the last 2 places the queue element or head was altered */
123struct qm_trace {
124 unsigned long lastline;
125 unsigned long prevline;
126 const char *lastfile;
127 const char *prevfile;
128};
129
130#define TRACEBUF struct qm_trace trace;
131#define TRACEBUF_INITIALIZER { __LINE__, 0, __FILE__, NULL } ,
132
133#define QMD_TRACE_HEAD(head) do { \
134 (head)->trace.prevline = (head)->trace.lastline; \
135 (head)->trace.prevfile = (head)->trace.lastfile; \
136 (head)->trace.lastline = __LINE__; \
137 (head)->trace.lastfile = __FILE__; \
138} while (0)
139
140#define QMD_TRACE_ELEM(elem) do { \
141 (elem)->trace.prevline = (elem)->trace.lastline; \
142 (elem)->trace.prevfile = (elem)->trace.lastfile; \
143 (elem)->trace.lastline = __LINE__; \
144 (elem)->trace.lastfile = __FILE__; \
145} while (0)
146
147#else /* !QUEUE_MACRO_DEBUG_TRACE */
148#define QMD_TRACE_ELEM(elem)
149#define QMD_TRACE_HEAD(head)
150#define TRACEBUF
151#define TRACEBUF_INITIALIZER
152#endif /* QUEUE_MACRO_DEBUG_TRACE */
153
154#ifdef QUEUE_MACRO_DEBUG_TRASH
155#define QMD_SAVELINK(name, link) void **name = (void *)&(link)
156#define TRASHIT(x) do {(x) = (void *)-1;} while (0)
157#define QMD_IS_TRASHED(x) ((x) == (void *)(intptr_t)-1)
158#else /* !QUEUE_MACRO_DEBUG_TRASH */
159#define QMD_SAVELINK(name, link)
160#define TRASHIT(x)
161#define QMD_IS_TRASHED(x) 0
162#endif /* QUEUE_MACRO_DEBUG_TRASH */
163
164#ifdef __cplusplus
165/*
166 * In C++ there can be structure lists and class lists:
167 */
168#define QUEUE_TYPEOF(type) type
169#else
170#define QUEUE_TYPEOF(type) struct type
171#endif
172
173/*
174 * Singly-linked List declarations.
175 */
176#define SLIST_HEAD(name, type) \
177struct name { \
178 struct type *slh_first; /* first element */ \
179}
180
181#define SLIST_CLASS_HEAD(name, type) \
182struct name { \
183 class type *slh_first; /* first element */ \
184}
185
186#define SLIST_HEAD_INITIALIZER(head) \
187 { NULL }
188
189#define SLIST_ENTRY(type) \
190struct { \
191 struct type *sle_next; /* next element */ \
192}
193
194#define SLIST_CLASS_ENTRY(type) \
195struct { \
196 class type *sle_next; /* next element */ \
197}
198
199/*
200 * Singly-linked List functions.
201 */
202#if (defined(_KERNEL) && defined(INVARIANTS))
203#define QMD_SLIST_CHECK_PREVPTR(prevp, elm) do { \
204 if (*(prevp) != (elm)) \
205 panic("Bad prevptr *(%p) == %p != %p", \
206 (prevp), *(prevp), (elm)); \
207} while (0)
208#else
209#define QMD_SLIST_CHECK_PREVPTR(prevp, elm)
210#endif
211
212#define SLIST_CONCAT(head1, head2, type, field) do { \
213 QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1); \
214 if (curelm == NULL) { \
215 if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL) \
216 SLIST_INIT(head2); \
217 } else if (SLIST_FIRST(head2) != NULL) { \
218 while (SLIST_NEXT(curelm, field) != NULL) \
219 curelm = SLIST_NEXT(curelm, field); \
220 SLIST_NEXT(curelm, field) = SLIST_FIRST(head2); \
221 SLIST_INIT(head2); \
222 } \
223} while (0)
224
225#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
226
227#define SLIST_FIRST(head) ((head)->slh_first)
228
229#define SLIST_FOREACH(var, head, field) \
230 for ((var) = SLIST_FIRST((head)); \
231 (var); \
232 (var) = SLIST_NEXT((var), field))
233
234#define SLIST_FOREACH_FROM(var, head, field) \
235 for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \
236 (var); \
237 (var) = SLIST_NEXT((var), field))
238
239#define SLIST_FOREACH_SAFE(var, head, field, tvar) \
240 for ((var) = SLIST_FIRST((head)); \
241 (var) && ((tvar) = SLIST_NEXT((var), field), 1); \
242 (var) = (tvar))
243
244#define SLIST_FOREACH_FROM_SAFE(var, head, field, tvar) \
245 for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \
246 (var) && ((tvar) = SLIST_NEXT((var), field), 1); \
247 (var) = (tvar))
248
249#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \
250 for ((varp) = &SLIST_FIRST((head)); \
251 ((var) = *(varp)) != NULL; \
252 (varp) = &SLIST_NEXT((var), field))
253
254#define SLIST_INIT(head) do { \
255 SLIST_FIRST((head)) = NULL; \
256} while (0)
257
258#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
259 SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
260 SLIST_NEXT((slistelm), field) = (elm); \
261} while (0)
262
263#define SLIST_INSERT_HEAD(head, elm, field) do { \
264 SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
265 SLIST_FIRST((head)) = (elm); \
266} while (0)
267
268#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
269
270#define SLIST_REMOVE(head, elm, type, field) do { \
271 if (SLIST_FIRST((head)) == (elm)) { \
272 SLIST_REMOVE_HEAD((head), field); \
273 } \
274 else { \
275 QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head); \
276 while (SLIST_NEXT(curelm, field) != (elm)) \
277 curelm = SLIST_NEXT(curelm, field); \
278 SLIST_REMOVE_AFTER(curelm, field); \
279 } \
280} while (0)
281
282#define SLIST_REMOVE_AFTER(elm, field) do { \
283 QMD_SAVELINK(oldnext, SLIST_NEXT(elm, field)->field.sle_next); \
284 SLIST_NEXT(elm, field) = \
285 SLIST_NEXT(SLIST_NEXT(elm, field), field); \
286 TRASHIT(*oldnext); \
287} while (0)
288
289#define SLIST_REMOVE_HEAD(head, field) do { \
290 QMD_SAVELINK(oldnext, SLIST_FIRST(head)->field.sle_next); \
291 SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \
292 TRASHIT(*oldnext); \
293} while (0)
294
295#define SLIST_REMOVE_PREVPTR(prevp, elm, field) do { \
296 QMD_SLIST_CHECK_PREVPTR(prevp, elm); \
297 *(prevp) = SLIST_NEXT(elm, field); \
298 TRASHIT((elm)->field.sle_next); \
299} while (0)
300
301#define SLIST_SWAP(head1, head2, type) do { \
302 QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1); \
303 SLIST_FIRST(head1) = SLIST_FIRST(head2); \
304 SLIST_FIRST(head2) = swap_first; \
305} while (0)
306
307#define SLIST_END(head) NULL
308
309/*
310 * Singly-linked Tail queue declarations.
311 */
312#define STAILQ_HEAD(name, type) \
313struct name { \
314 struct type *stqh_first;/* first element */ \
315 struct type **stqh_last;/* addr of last next element */ \
316}
317
318#define STAILQ_CLASS_HEAD(name, type) \
319struct name { \
320 class type *stqh_first; /* first element */ \
321 class type **stqh_last; /* addr of last next element */ \
322}
323
324#define STAILQ_HEAD_INITIALIZER(head) \
325 { NULL, &(head).stqh_first }
326
327#define STAILQ_ENTRY(type) \
328struct { \
329 struct type *stqe_next; /* next element */ \
330}
331
332#define STAILQ_CLASS_ENTRY(type) \
333struct { \
334 class type *stqe_next; /* next element */ \
335}
336
337/*
338 * Singly-linked Tail queue functions.
339 */
340#if (defined(_KERNEL) && defined(INVARIANTS))
341/*
342 * QMD_STAILQ_CHECK_EMPTY(STAILQ_HEAD *head)
343 *
344 * Validates that the stailq head's pointer to the last element's next pointer
345 * actually points to the head's first element pointer field.
346 */
347#define QMD_STAILQ_CHECK_EMPTY(head) do { \
348 if ((head)->stqh_last != &(head)->stqh_first) \
349 panic("Empty stailq %p->stqh_last is %p, not head's " \
350 "first field address", (head), (head)->stqh_last); \
351} while (0)
352
353#define STAILQ_ASSERT_EMPTY(head) do { \
354 if (!STAILQ_EMPTY((head))) \
355 panic("stailq %p is not empty", (head)); \
356}
357
358/*
359 * QMD_STAILQ_CHECK_TAIL(STAILQ_HEAD *head)
360 *
361 * Validates that the stailq's last element's next pointer is NULL.
362 */
363#define QMD_STAILQ_CHECK_TAIL(head) do { \
364 if (*(head)->stqh_last != NULL) \
365 panic("Stailq %p last element's next pointer is %p, " \
366 "not NULL", (head), *(head)->stqh_last); \
367} while (0)
368#else
369#define QMD_STAILQ_CHECK_EMPTY(head)
370#define STAILQ_ASSERT_EMPTY(head)
371#define QMD_STAILQ_CHECK_TAIL(head)
372#endif /* (_KERNEL && INVARIANTS) */
373
374#define STAILQ_CONCAT(head1, head2) do { \
375 if (!STAILQ_EMPTY((head2))) { \
376 *(head1)->stqh_last = (head2)->stqh_first; \
377 (head1)->stqh_last = (head2)->stqh_last; \
378 STAILQ_INIT((head2)); \
379 } \
380} while (0)
381
382#define STAILQ_EMPTY(head) ({ \
383 if (STAILQ_FIRST(head) == NULL) \
384 QMD_STAILQ_CHECK_EMPTY(head); \
385 STAILQ_FIRST(head) == NULL; \
386})
387
388#define STAILQ_FIRST(head) ((head)->stqh_first)
389
390#define STAILQ_FOREACH(var, head, field) \
391 for((var) = STAILQ_FIRST((head)); \
392 (var); \
393 (var) = STAILQ_NEXT((var), field))
394
395#define STAILQ_FOREACH_FROM(var, head, field) \
396 for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \
397 (var); \
398 (var) = STAILQ_NEXT((var), field))
399
400#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
401 for ((var) = STAILQ_FIRST((head)); \
402 (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
403 (var) = (tvar))
404
405#define STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \
406 for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \
407 (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
408 (var) = (tvar))
409
410#define STAILQ_INIT(head) do { \
411 STAILQ_FIRST((head)) = NULL; \
412 (head)->stqh_last = &STAILQ_FIRST((head)); \
413} while (0)
414
415#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
416 if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
417 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
418 STAILQ_NEXT((tqelm), field) = (elm); \
419} while (0)
420
421#define STAILQ_INSERT_HEAD(head, elm, field) do { \
422 if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
423 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
424 STAILQ_FIRST((head)) = (elm); \
425} while (0)
426
427#define STAILQ_INSERT_TAIL(head, elm, field) do { \
428 QMD_STAILQ_CHECK_TAIL(head); \
429 STAILQ_NEXT((elm), field) = NULL; \
430 *(head)->stqh_last = (elm); \
431 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
432} while (0)
433
434#define STAILQ_LAST(head, type, field) \
435 (STAILQ_EMPTY((head)) ? NULL : \
436 __containerof((head)->stqh_last, \
437 QUEUE_TYPEOF(type), field.stqe_next))
438
439#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
440
441#define STAILQ_REMOVE(head, elm, type, field) do { \
442 QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \
443 if (STAILQ_FIRST((head)) == (elm)) { \
444 STAILQ_REMOVE_HEAD((head), field); \
445 } \
446 else { \
447 QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head); \
448 while (STAILQ_NEXT(curelm, field) != (elm)) \
449 curelm = STAILQ_NEXT(curelm, field); \
450 STAILQ_REMOVE_AFTER(head, curelm, field); \
451 } \
452 TRASHIT(*oldnext); \
453} while (0)
454
455#define STAILQ_REMOVE_AFTER(head, elm, field) do { \
456 if ((STAILQ_NEXT(elm, field) = \
457 STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \
458 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
459} while (0)
460
461#define STAILQ_REMOVE_HEAD(head, field) do { \
462 if ((STAILQ_FIRST((head)) = \
463 STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \
464 (head)->stqh_last = &STAILQ_FIRST((head)); \
465} while (0)
466
467#define STAILQ_SWAP(head1, head2, type) do { \
468 QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1); \
469 QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last; \
470 STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \
471 (head1)->stqh_last = (head2)->stqh_last; \
472 STAILQ_FIRST(head2) = swap_first; \
473 (head2)->stqh_last = swap_last; \
474 if (STAILQ_FIRST(head1) == NULL) \
475 (head1)->stqh_last = &STAILQ_FIRST(head1); \
476 if (STAILQ_FIRST(head2) == NULL) \
477 (head2)->stqh_last = &STAILQ_FIRST(head2); \
478} while (0)
479
480#define STAILQ_END(head) NULL
481
482
483/*
484 * List declarations.
485 */
486#define LIST_HEAD(name, type) \
487struct name { \
488 struct type *lh_first; /* first element */ \
489}
490
491#define LIST_CLASS_HEAD(name, type) \
492struct name { \
493 class type *lh_first; /* first element */ \
494}
495
496#define LIST_HEAD_INITIALIZER(head) \
497 { NULL }
498
499#define LIST_ENTRY(type) \
500struct { \
501 struct type *le_next; /* next element */ \
502 struct type **le_prev; /* address of previous next element */ \
503}
504
505#define LIST_CLASS_ENTRY(type) \
506struct { \
507 class type *le_next; /* next element */ \
508 class type **le_prev; /* address of previous next element */ \
509}
510
511/*
512 * List functions.
513 */
514
515#if (defined(_KERNEL) && defined(INVARIANTS))
516/*
517 * QMD_LIST_CHECK_HEAD(LIST_HEAD *head, LIST_ENTRY NAME)
518 *
519 * If the list is non-empty, validates that the first element of the list
520 * points back at 'head.'
521 */
522#define QMD_LIST_CHECK_HEAD(head, field) do { \
523 if (LIST_FIRST((head)) != NULL && \
524 LIST_FIRST((head))->field.le_prev != \
525 &LIST_FIRST((head))) \
526 panic("Bad list head %p first->prev != head", (head)); \
527} while (0)
528
529/*
530 * QMD_LIST_CHECK_NEXT(TYPE *elm, LIST_ENTRY NAME)
531 *
532 * If an element follows 'elm' in the list, validates that the next element
533 * points back at 'elm.'
534 */
535#define QMD_LIST_CHECK_NEXT(elm, field) do { \
536 if (LIST_NEXT((elm), field) != NULL && \
537 LIST_NEXT((elm), field)->field.le_prev != \
538 &((elm)->field.le_next)) \
539 panic("Bad link elm %p next->prev != elm", (elm)); \
540} while (0)
541
542/*
543 * QMD_LIST_CHECK_PREV(TYPE *elm, LIST_ENTRY NAME)
544 *
545 * Validates that the previous element (or head of the list) points to 'elm.'
546 */
547#define QMD_LIST_CHECK_PREV(elm, field) do { \
548 if (*(elm)->field.le_prev != (elm)) \
549 panic("Bad link elm %p prev->next != elm", (elm)); \
550} while (0)
551#else
552#define QMD_LIST_CHECK_HEAD(head, field)
553#define QMD_LIST_CHECK_NEXT(elm, field)
554#define QMD_LIST_CHECK_PREV(elm, field)
555#endif /* (_KERNEL && INVARIANTS) */
556
557#define LIST_CONCAT(head1, head2, type, field) do { \
558 QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1); \
559 if (curelm == NULL) { \
560 if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) { \
561 LIST_FIRST(head2)->field.le_prev = \
562 &LIST_FIRST((head1)); \
563 LIST_INIT(head2); \
564 } \
565 } else if (LIST_FIRST(head2) != NULL) { \
566 while (LIST_NEXT(curelm, field) != NULL) \
567 curelm = LIST_NEXT(curelm, field); \
568 LIST_NEXT(curelm, field) = LIST_FIRST(head2); \
569 LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field);\
570 LIST_INIT(head2); \
571 } \
572} while (0)
573
574#define LIST_EMPTY(head) ((head)->lh_first == NULL)
575
576#define LIST_FIRST(head) ((head)->lh_first)
577
578#define LIST_FOREACH(var, head, field) \
579 for ((var) = LIST_FIRST((head)); \
580 (var); \
581 (var) = LIST_NEXT((var), field))
582
583#define LIST_FOREACH_FROM(var, head, field) \
584 for ((var) = ((var) ? (var) : LIST_FIRST((head))); \
585 (var); \
586 (var) = LIST_NEXT((var), field))
587
588#define LIST_FOREACH_SAFE(var, head, field, tvar) \
589 for ((var) = LIST_FIRST((head)); \
590 (var) && ((tvar) = LIST_NEXT((var), field), 1); \
591 (var) = (tvar))
592
593#define LIST_FOREACH_FROM_SAFE(var, head, field, tvar) \
594 for ((var) = ((var) ? (var) : LIST_FIRST((head))); \
595 (var) && ((tvar) = LIST_NEXT((var), field), 1); \
596 (var) = (tvar))
597
598#define LIST_INIT(head) do { \
599 LIST_FIRST((head)) = NULL; \
600} while (0)
601
602#define LIST_INSERT_AFTER(listelm, elm, field) do { \
603 QMD_LIST_CHECK_NEXT(listelm, field); \
604 if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
605 LIST_NEXT((listelm), field)->field.le_prev = \
606 &LIST_NEXT((elm), field); \
607 LIST_NEXT((listelm), field) = (elm); \
608 (elm)->field.le_prev = &LIST_NEXT((listelm), field); \
609} while (0)
610
611#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
612 QMD_LIST_CHECK_PREV(listelm, field); \
613 (elm)->field.le_prev = (listelm)->field.le_prev; \
614 LIST_NEXT((elm), field) = (listelm); \
615 *(listelm)->field.le_prev = (elm); \
616 (listelm)->field.le_prev = &LIST_NEXT((elm), field); \
617} while (0)
618
619#define LIST_INSERT_HEAD(head, elm, field) do { \
620 QMD_LIST_CHECK_HEAD((head), field); \
621 if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
622 LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
623 LIST_FIRST((head)) = (elm); \
624 (elm)->field.le_prev = &LIST_FIRST((head)); \
625} while (0)
626
627#define LIST_NEXT(elm, field) ((elm)->field.le_next)
628
629#define LIST_PREV(elm, head, type, field) \
630 ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \
631 __containerof((elm)->field.le_prev, \
632 QUEUE_TYPEOF(type), field.le_next))
633
634#define LIST_REMOVE_HEAD(head, field) \
635 LIST_REMOVE(LIST_FIRST(head), field)
636
637#define LIST_REMOVE(elm, field) do { \
638 QMD_SAVELINK(oldnext, (elm)->field.le_next); \
639 QMD_SAVELINK(oldprev, (elm)->field.le_prev); \
640 QMD_LIST_CHECK_NEXT(elm, field); \
641 QMD_LIST_CHECK_PREV(elm, field); \
642 if (LIST_NEXT((elm), field) != NULL) \
643 LIST_NEXT((elm), field)->field.le_prev = \
644 (elm)->field.le_prev; \
645 *(elm)->field.le_prev = LIST_NEXT((elm), field); \
646 TRASHIT(*oldnext); \
647 TRASHIT(*oldprev); \
648} while (0)
649
650#define LIST_REPLACE(elm, elm2, field) do { \
651 QMD_SAVELINK(oldnext, (elm)->field.le_next); \
652 QMD_SAVELINK(oldprev, (elm)->field.le_prev); \
653 QMD_LIST_CHECK_NEXT(elm, field); \
654 QMD_LIST_CHECK_PREV(elm, field); \
655 LIST_NEXT((elm2), field) = LIST_NEXT((elm), field); \
656 if (LIST_NEXT((elm2), field) != NULL) \
657 LIST_NEXT((elm2), field)->field.le_prev = \
658 &(elm2)->field.le_next; \
659 (elm2)->field.le_prev = (elm)->field.le_prev; \
660 *(elm2)->field.le_prev = (elm2); \
661 TRASHIT(*oldnext); \
662 TRASHIT(*oldprev); \
663} while (0)
664
665#define LIST_SWAP(head1, head2, type, field) do { \
666 QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1); \
667 LIST_FIRST((head1)) = LIST_FIRST((head2)); \
668 LIST_FIRST((head2)) = swap_tmp; \
669 if ((swap_tmp = LIST_FIRST((head1))) != NULL) \
670 swap_tmp->field.le_prev = &LIST_FIRST((head1)); \
671 if ((swap_tmp = LIST_FIRST((head2))) != NULL) \
672 swap_tmp->field.le_prev = &LIST_FIRST((head2)); \
673} while (0)
674
675#define LIST_END(head) NULL
676
677/*
678 * Tail queue declarations.
679 */
680#define TAILQ_HEAD(name, type) \
681struct name { \
682 struct type *tqh_first; /* first element */ \
683 struct type **tqh_last; /* addr of last next element */ \
684 TRACEBUF \
685}
686
687#define TAILQ_CLASS_HEAD(name, type) \
688struct name { \
689 class type *tqh_first; /* first element */ \
690 class type **tqh_last; /* addr of last next element */ \
691 TRACEBUF \
692}
693
694#define TAILQ_HEAD_INITIALIZER(head) \
695 { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER }
696
697#define TAILQ_ENTRY(type) \
698struct { \
699 struct type *tqe_next; /* next element */ \
700 struct type **tqe_prev; /* address of previous next element */ \
701 TRACEBUF \
702}
703
704#define TAILQ_CLASS_ENTRY(type) \
705struct { \
706 class type *tqe_next; /* next element */ \
707 class type **tqe_prev; /* address of previous next element */ \
708 TRACEBUF \
709}
710
711/*
712 * Tail queue functions.
713 */
714#if (defined(_KERNEL) && defined(INVARIANTS))
715/*
716 * QMD_TAILQ_CHECK_HEAD(TAILQ_HEAD *head, TAILQ_ENTRY NAME)
717 *
718 * If the tailq is non-empty, validates that the first element of the tailq
719 * points back at 'head.'
720 */
721#define QMD_TAILQ_CHECK_HEAD(head, field) do { \
722 if (!TAILQ_EMPTY(head) && \
723 TAILQ_FIRST((head))->field.tqe_prev != \
724 &TAILQ_FIRST((head))) \
725 panic("Bad tailq head %p first->prev != head", (head)); \
726} while (0)
727
728/*
729 * QMD_TAILQ_CHECK_TAIL(TAILQ_HEAD *head, TAILQ_ENTRY NAME)
730 *
731 * Validates that the tail of the tailq is a pointer to pointer to NULL.
732 */
733#define QMD_TAILQ_CHECK_TAIL(head, field) do { \
734 if (*(head)->tqh_last != NULL) \
735 panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \
736} while (0)
737
738/*
739 * QMD_TAILQ_CHECK_NEXT(TYPE *elm, TAILQ_ENTRY NAME)
740 *
741 * If an element follows 'elm' in the tailq, validates that the next element
742 * points back at 'elm.'
743 */
744#define QMD_TAILQ_CHECK_NEXT(elm, field) do { \
745 if (TAILQ_NEXT((elm), field) != NULL && \
746 TAILQ_NEXT((elm), field)->field.tqe_prev != \
747 &((elm)->field.tqe_next)) \
748 panic("Bad link elm %p next->prev != elm", (elm)); \
749} while (0)
750
751/*
752 * QMD_TAILQ_CHECK_PREV(TYPE *elm, TAILQ_ENTRY NAME)
753 *
754 * Validates that the previous element (or head of the tailq) points to 'elm.'
755 */
756#define QMD_TAILQ_CHECK_PREV(elm, field) do { \
757 if (*(elm)->field.tqe_prev != (elm)) \
758 panic("Bad link elm %p prev->next != elm", (elm)); \
759} while (0)
760#else
761#define QMD_TAILQ_CHECK_HEAD(head, field)
762#define QMD_TAILQ_CHECK_TAIL(head, headname)
763#define QMD_TAILQ_CHECK_NEXT(elm, field)
764#define QMD_TAILQ_CHECK_PREV(elm, field)
765#endif /* (_KERNEL && INVARIANTS) */
766
767#define TAILQ_CONCAT(head1, head2, field) do { \
768 if (!TAILQ_EMPTY(head2)) { \
769 *(head1)->tqh_last = (head2)->tqh_first; \
770 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
771 (head1)->tqh_last = (head2)->tqh_last; \
772 TAILQ_INIT((head2)); \
773 QMD_TRACE_HEAD(head1); \
774 QMD_TRACE_HEAD(head2); \
775 } \
776} while (0)
777
778#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
779
780#define TAILQ_FIRST(head) ((head)->tqh_first)
781
782#define TAILQ_FOREACH(var, head, field) \
783 for ((var) = TAILQ_FIRST((head)); \
784 (var); \
785 (var) = TAILQ_NEXT((var), field))
786
787#define TAILQ_FOREACH_FROM(var, head, field) \
788 for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \
789 (var); \
790 (var) = TAILQ_NEXT((var), field))
791
792#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
793 for ((var) = TAILQ_FIRST((head)); \
794 (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
795 (var) = (tvar))
796
797#define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \
798 for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \
799 (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
800 (var) = (tvar))
801
802#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
803 for ((var) = TAILQ_LAST((head), headname); \
804 (var); \
805 (var) = TAILQ_PREV((var), headname, field))
806
807#define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \
808 for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \
809 (var); \
810 (var) = TAILQ_PREV((var), headname, field))
811
812#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
813 for ((var) = TAILQ_LAST((head), headname); \
814 (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
815 (var) = (tvar))
816
817#define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar)\
818 for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \
819 (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
820 (var) = (tvar))
821
822#define TAILQ_INIT(head) do { \
823 TAILQ_FIRST((head)) = NULL; \
824 (head)->tqh_last = &TAILQ_FIRST((head)); \
825 QMD_TRACE_HEAD(head); \
826} while (0)
827
828#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
829 QMD_TAILQ_CHECK_NEXT(listelm, field); \
830 if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
831 TAILQ_NEXT((elm), field)->field.tqe_prev = \
832 &TAILQ_NEXT((elm), field); \
833 else { \
834 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
835 QMD_TRACE_HEAD(head); \
836 } \
837 TAILQ_NEXT((listelm), field) = (elm); \
838 (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
839 QMD_TRACE_ELEM(&(elm)->field); \
840 QMD_TRACE_ELEM(&(listelm)->field); \
841} while (0)
842
843#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
844 QMD_TAILQ_CHECK_PREV(listelm, field); \
845 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
846 TAILQ_NEXT((elm), field) = (listelm); \
847 *(listelm)->field.tqe_prev = (elm); \
848 (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
849 QMD_TRACE_ELEM(&(elm)->field); \
850 QMD_TRACE_ELEM(&(listelm)->field); \
851} while (0)
852
853#define TAILQ_INSERT_HEAD(head, elm, field) do { \
854 QMD_TAILQ_CHECK_HEAD(head, field); \
855 if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
856 TAILQ_FIRST((head))->field.tqe_prev = \
857 &TAILQ_NEXT((elm), field); \
858 else \
859 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
860 TAILQ_FIRST((head)) = (elm); \
861 (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
862 QMD_TRACE_HEAD(head); \
863 QMD_TRACE_ELEM(&(elm)->field); \
864} while (0)
865
866#define TAILQ_INSERT_TAIL(head, elm, field) do { \
867 QMD_TAILQ_CHECK_TAIL(head, field); \
868 TAILQ_NEXT((elm), field) = NULL; \
869 (elm)->field.tqe_prev = (head)->tqh_last; \
870 *(head)->tqh_last = (elm); \
871 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
872 QMD_TRACE_HEAD(head); \
873 QMD_TRACE_ELEM(&(elm)->field); \
874} while (0)
875
876#define TAILQ_LAST(head, headname) \
877 (*(((struct headname *)((head)->tqh_last))->tqh_last))
878
879/*
880 * The FAST function is fast in that it causes no data access other
881 * then the access to the head. The standard LAST function above
882 * will cause a data access of both the element you want and
883 * the previous element. FAST is very useful for instances when
884 * you may want to prefetch the last data element.
885 */
886#define TAILQ_LAST_FAST(head, type, field) \
887 (TAILQ_EMPTY(head) ? NULL : __containerof((head)->tqh_last, QUEUE_TYPEOF(type), field.tqe_next))
888
889#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
890
891#define TAILQ_PREV(elm, headname, field) \
892 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
893
894#define TAILQ_PREV_FAST(elm, head, type, field) \
895 ((elm)->field.tqe_prev == &(head)->tqh_first ? NULL : \
896 __containerof((elm)->field.tqe_prev, QUEUE_TYPEOF(type), field.tqe_next))
897
898#define TAILQ_REMOVE_HEAD(head, field) \
899 TAILQ_REMOVE(head, TAILQ_FIRST(head), field)
900
901#define TAILQ_REMOVE(head, elm, field) do { \
902 QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \
903 QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \
904 QMD_TAILQ_CHECK_NEXT(elm, field); \
905 QMD_TAILQ_CHECK_PREV(elm, field); \
906 if ((TAILQ_NEXT((elm), field)) != NULL) \
907 TAILQ_NEXT((elm), field)->field.tqe_prev = \
908 (elm)->field.tqe_prev; \
909 else { \
910 (head)->tqh_last = (elm)->field.tqe_prev; \
911 QMD_TRACE_HEAD(head); \
912 } \
913 *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
914 TRASHIT(*oldnext); \
915 TRASHIT(*oldprev); \
916 QMD_TRACE_ELEM(&(elm)->field); \
917} while (0)
918
919#define TAILQ_REPLACE(head, elm, elm2, field) do { \
920 QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \
921 QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \
922 QMD_TAILQ_CHECK_NEXT(elm, field); \
923 QMD_TAILQ_CHECK_PREV(elm, field); \
924 TAILQ_NEXT((elm2), field) = TAILQ_NEXT((elm), field); \
925 if (TAILQ_NEXT((elm2), field) != TAILQ_END(head)) \
926 TAILQ_NEXT((elm2), field)->field.tqe_prev = \
927 &(elm2)->field.tqe_next; \
928 else \
929 (head)->tqh_last = &(elm2)->field.tqe_next; \
930 (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
931 *(elm2)->field.tqe_prev = (elm2); \
932 TRASHIT(*oldnext); \
933 TRASHIT(*oldprev); \
934 QMD_TRACE_ELEM(&(elm)->field); \
935} while (0)
936
937#define TAILQ_SWAP(head1, head2, type, field) do { \
938 QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first; \
939 QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \
940 (head1)->tqh_first = (head2)->tqh_first; \
941 (head1)->tqh_last = (head2)->tqh_last; \
942 (head2)->tqh_first = swap_first; \
943 (head2)->tqh_last = swap_last; \
944 if ((swap_first = (head1)->tqh_first) != NULL) \
945 swap_first->field.tqe_prev = &(head1)->tqh_first; \
946 else \
947 (head1)->tqh_last = &(head1)->tqh_first; \
948 if ((swap_first = (head2)->tqh_first) != NULL) \
949 swap_first->field.tqe_prev = &(head2)->tqh_first; \
950 else \
951 (head2)->tqh_last = &(head2)->tqh_first; \
952} while (0)
953
954#define TAILQ_END(head) NULL
955
956#endif /* !_SYS_QUEUE_H_ */