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