| 1 | /* BEGIN CSTYLED */
|
|---|
| 2 | /*-
|
|---|
| 3 | * Copyright (c) 1991, 1993
|
|---|
| 4 | * The Regents of the University of California. All rights reserved.
|
|---|
| 5 | *
|
|---|
| 6 | * Redistribution and use in source and binary forms, with or without
|
|---|
| 7 | * modification, are permitted provided that the following conditions
|
|---|
| 8 | * are met:
|
|---|
| 9 | * 1. Redistributions of source code must retain the above copyright
|
|---|
| 10 | * notice, this list of conditions and the following disclaimer.
|
|---|
| 11 | * 2. Redistributions in binary form must reproduce the above copyright
|
|---|
| 12 | * notice, this list of conditions and the following disclaimer in the
|
|---|
| 13 | * documentation and/or other materials provided with the distribution.
|
|---|
| 14 | * 4. Neither the name of the University nor the names of its contributors
|
|---|
| 15 | * may be used to endorse or promote products derived from this software
|
|---|
| 16 | * without specific prior written permission.
|
|---|
| 17 | *
|
|---|
| 18 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
|
|---|
| 19 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
|
|---|
| 20 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
|
|---|
| 21 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
|
|---|
| 22 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
|
|---|
| 23 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
|
|---|
| 24 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
|
|---|
| 25 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
|
|---|
| 26 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
|
|---|
| 27 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
|
|---|
| 28 | * SUCH DAMAGE.
|
|---|
| 29 | *
|
|---|
| 30 | * @(#)queue.h 8.5 (Berkeley) 8/20/94
|
|---|
| 31 | * $FreeBSD: /repoman/r/ncvs/src/sys/sys/queue.h,v 1.66 2006/05/26 18:17:53 emaste Exp $
|
|---|
| 32 | */
|
|---|
| 33 |
|
|---|
| 34 | #ifndef _SYS_QUEUE_H_
|
|---|
| 35 | #define _SYS_QUEUE_H_
|
|---|
| 36 |
|
|---|
| 37 | #pragma ident "%Z%%M% %I% %E% SMI"
|
|---|
| 38 |
|
|---|
| 39 | /*
|
|---|
| 40 | * This file defines four types of data structures: singly-linked lists,
|
|---|
| 41 | * singly-linked tail queues, lists and tail queues.
|
|---|
| 42 | *
|
|---|
| 43 | * A singly-linked list is headed by a single forward pointer. The elements
|
|---|
| 44 | * are singly linked for minimum space and pointer manipulation overhead at
|
|---|
| 45 | * the expense of O(n) removal for arbitrary elements. New elements can be
|
|---|
| 46 | * added to the list after an existing element or at the head of the list.
|
|---|
| 47 | * Elements being removed from the head of the list should use the explicit
|
|---|
| 48 | * macro for this purpose for optimum efficiency. A singly-linked list may
|
|---|
| 49 | * only be traversed in the forward direction. Singly-linked lists are ideal
|
|---|
| 50 | * for applications with large datasets and few or no removals or for
|
|---|
| 51 | * implementing a LIFO queue.
|
|---|
| 52 | *
|
|---|
| 53 | * A singly-linked tail queue is headed by a pair of pointers, one to the
|
|---|
| 54 | * head of the list and the other to the tail of the list. The elements are
|
|---|
| 55 | * singly linked for minimum space and pointer manipulation overhead at the
|
|---|
| 56 | * expense of O(n) removal for arbitrary elements. New elements can be added
|
|---|
| 57 | * to the list after an existing element, at the head of the list, or at the
|
|---|
| 58 | * end of the list. Elements being removed from the head of the tail queue
|
|---|
| 59 | * should use the explicit macro for this purpose for optimum efficiency.
|
|---|
| 60 | * A singly-linked tail queue may only be traversed in the forward direction.
|
|---|
| 61 | * Singly-linked tail queues are ideal for applications with large datasets
|
|---|
| 62 | * and few or no removals or for implementing a FIFO queue.
|
|---|
| 63 | *
|
|---|
| 64 | * A list is headed by a single forward pointer (or an array of forward
|
|---|
| 65 | * pointers for a hash table header). The elements are doubly linked
|
|---|
| 66 | * so that an arbitrary element can be removed without a need to
|
|---|
| 67 | * traverse the list. New elements can be added to the list before
|
|---|
| 68 | * or after an existing element or at the head of the list. A list
|
|---|
| 69 | * may only be traversed in the forward direction.
|
|---|
| 70 | *
|
|---|
| 71 | * A tail queue is headed by a pair of pointers, one to the head of the
|
|---|
| 72 | * list and the other to the tail of the list. The elements are doubly
|
|---|
| 73 | * linked so that an arbitrary element can be removed without a need to
|
|---|
| 74 | * traverse the list. New elements can be added to the list before or
|
|---|
| 75 | * after an existing element, at the head of the list, or at the end of
|
|---|
| 76 | * the list. A tail queue may be traversed in either direction.
|
|---|
| 77 | *
|
|---|
| 78 | * For details on the use of these macros, see the queue(3) manual page.
|
|---|
| 79 | *
|
|---|
| 80 | *
|
|---|
| 81 | * SLIST LIST STAILQ TAILQ
|
|---|
| 82 | * _HEAD + + + +
|
|---|
| 83 | * _HEAD_INITIALIZER + + + +
|
|---|
| 84 | * _ENTRY + + + +
|
|---|
| 85 | * _INIT + + + +
|
|---|
| 86 | * _EMPTY + + + +
|
|---|
| 87 | * _FIRST + + + +
|
|---|
| 88 | * _NEXT + + + +
|
|---|
| 89 | * _PREV - - - +
|
|---|
| 90 | * _LAST - - + +
|
|---|
| 91 | * _FOREACH + + + +
|
|---|
| 92 | * _FOREACH_SAFE + + + +
|
|---|
| 93 | * _FOREACH_REVERSE - - - +
|
|---|
| 94 | * _FOREACH_REVERSE_SAFE - - - +
|
|---|
| 95 | * _INSERT_HEAD + + + +
|
|---|
| 96 | * _INSERT_BEFORE - + - +
|
|---|
| 97 | * _INSERT_AFTER + + + +
|
|---|
| 98 | * _INSERT_TAIL - - + +
|
|---|
| 99 | * _CONCAT - - + +
|
|---|
| 100 | * _REMOVE_HEAD + - + -
|
|---|
| 101 | * _REMOVE + + + +
|
|---|
| 102 | *
|
|---|
| 103 | */
|
|---|
| 104 | #ifdef QUEUE_MACRO_DEBUG
|
|---|
| 105 | /* Store the last 2 places the queue element or head was altered */
|
|---|
| 106 | struct qm_trace {
|
|---|
| 107 | char * lastfile;
|
|---|
| 108 | int lastline;
|
|---|
| 109 | char * prevfile;
|
|---|
| 110 | int prevline;
|
|---|
| 111 | };
|
|---|
| 112 |
|
|---|
| 113 | #define TRACEBUF struct qm_trace trace;
|
|---|
| 114 | #define TRASHIT(x) do {(x) = (void *)-1;} while (*"\0")
|
|---|
| 115 |
|
|---|
| 116 | #define QMD_TRACE_HEAD(head) do { \
|
|---|
| 117 | (head)->trace.prevline = (head)->trace.lastline; \
|
|---|
| 118 | (head)->trace.prevfile = (head)->trace.lastfile; \
|
|---|
| 119 | (head)->trace.lastline = __LINE__; \
|
|---|
| 120 | (head)->trace.lastfile = __FILE__; \
|
|---|
| 121 | } while (*"\0")
|
|---|
| 122 |
|
|---|
| 123 | #define QMD_TRACE_ELEM(elem) do { \
|
|---|
| 124 | (elem)->trace.prevline = (elem)->trace.lastline; \
|
|---|
| 125 | (elem)->trace.prevfile = (elem)->trace.lastfile; \
|
|---|
| 126 | (elem)->trace.lastline = __LINE__; \
|
|---|
| 127 | (elem)->trace.lastfile = __FILE__; \
|
|---|
| 128 | } while (*"\0")
|
|---|
| 129 |
|
|---|
| 130 | #else
|
|---|
| 131 | #define QMD_TRACE_ELEM(elem)
|
|---|
| 132 | #define QMD_TRACE_HEAD(head)
|
|---|
| 133 | #define TRACEBUF
|
|---|
| 134 | #define TRASHIT(x)
|
|---|
| 135 | #endif /* QUEUE_MACRO_DEBUG */
|
|---|
| 136 |
|
|---|
| 137 | /*
|
|---|
| 138 | * Singly-linked List declarations.
|
|---|
| 139 | */
|
|---|
| 140 | #define SLIST_HEAD(name, type) \
|
|---|
| 141 | struct name { \
|
|---|
| 142 | struct type *slh_first; /* first element */ \
|
|---|
| 143 | }
|
|---|
| 144 |
|
|---|
| 145 | #define SLIST_HEAD_INITIALIZER(head) \
|
|---|
| 146 | { NULL }
|
|---|
| 147 |
|
|---|
| 148 | #define SLIST_ENTRY(type) \
|
|---|
| 149 | struct { \
|
|---|
| 150 | struct type *sle_next; /* next element */ \
|
|---|
| 151 | }
|
|---|
| 152 |
|
|---|
| 153 | /*
|
|---|
| 154 | * Singly-linked List functions.
|
|---|
| 155 | */
|
|---|
| 156 | #define SLIST_EMPTY(head) ((head)->slh_first == NULL)
|
|---|
| 157 |
|
|---|
| 158 | #define SLIST_FIRST(head) ((head)->slh_first)
|
|---|
| 159 |
|
|---|
| 160 | #define SLIST_FOREACH(var, head, field) \
|
|---|
| 161 | for ((var) = SLIST_FIRST((head)); \
|
|---|
| 162 | (var); \
|
|---|
| 163 | (var) = SLIST_NEXT((var), field))
|
|---|
| 164 |
|
|---|
| 165 | #define SLIST_FOREACH_SAFE(var, head, field, tvar) \
|
|---|
| 166 | for ((var) = SLIST_FIRST((head)); \
|
|---|
| 167 | (var) && ((tvar) = SLIST_NEXT((var), field), 1); \
|
|---|
| 168 | (var) = (tvar))
|
|---|
| 169 |
|
|---|
| 170 | #define SLIST_FOREACH_PREVPTR(var, varp, head, field) \
|
|---|
| 171 | for ((varp) = &SLIST_FIRST((head)); \
|
|---|
| 172 | ((var) = *(varp)) != NULL; \
|
|---|
| 173 | (varp) = &SLIST_NEXT((var), field))
|
|---|
| 174 |
|
|---|
| 175 | #define SLIST_INIT(head) do { \
|
|---|
| 176 | SLIST_FIRST((head)) = NULL; \
|
|---|
| 177 | } while (*"\0")
|
|---|
| 178 |
|
|---|
| 179 | #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
|
|---|
| 180 | SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
|
|---|
| 181 | SLIST_NEXT((slistelm), field) = (elm); \
|
|---|
| 182 | } while (*"\0")
|
|---|
| 183 |
|
|---|
| 184 | #define SLIST_INSERT_HEAD(head, elm, field) do { \
|
|---|
| 185 | SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
|
|---|
| 186 | SLIST_FIRST((head)) = (elm); \
|
|---|
| 187 | } while (*"\0")
|
|---|
| 188 |
|
|---|
| 189 | #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
|
|---|
| 190 |
|
|---|
| 191 | #define SLIST_REMOVE(head, elm, type, field) do { \
|
|---|
| 192 | if (SLIST_FIRST((head)) == (elm)) { \
|
|---|
| 193 | SLIST_REMOVE_HEAD((head), field); \
|
|---|
| 194 | } \
|
|---|
| 195 | else { \
|
|---|
| 196 | struct type *curelm = SLIST_FIRST((head)); \
|
|---|
| 197 | while (SLIST_NEXT(curelm, field) != (elm)) \
|
|---|
| 198 | curelm = SLIST_NEXT(curelm, field); \
|
|---|
| 199 | SLIST_NEXT(curelm, field) = \
|
|---|
| 200 | SLIST_NEXT(SLIST_NEXT(curelm, field), field); \
|
|---|
| 201 | } \
|
|---|
| 202 | TRASHIT((elm)->field.sle_next); \
|
|---|
| 203 | } while (*"\0")
|
|---|
| 204 |
|
|---|
| 205 | #define SLIST_REMOVE_HEAD(head, field) do { \
|
|---|
| 206 | SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \
|
|---|
| 207 | } while (*"\0")
|
|---|
| 208 |
|
|---|
| 209 | /*
|
|---|
| 210 | * Singly-linked Tail queue declarations.
|
|---|
| 211 | */
|
|---|
| 212 | #define STAILQ_HEAD(name, type) \
|
|---|
| 213 | struct name { \
|
|---|
| 214 | struct type *stqh_first;/* first element */ \
|
|---|
| 215 | struct type **stqh_last;/* addr of last next element */ \
|
|---|
| 216 | }
|
|---|
| 217 |
|
|---|
| 218 | #define STAILQ_HEAD_INITIALIZER(head) \
|
|---|
| 219 | { NULL, &(head).stqh_first }
|
|---|
| 220 |
|
|---|
| 221 | #define STAILQ_ENTRY(type) \
|
|---|
| 222 | struct { \
|
|---|
| 223 | struct type *stqe_next; /* next element */ \
|
|---|
| 224 | }
|
|---|
| 225 |
|
|---|
| 226 | /*
|
|---|
| 227 | * Singly-linked Tail queue functions.
|
|---|
| 228 | */
|
|---|
| 229 | #define STAILQ_CONCAT(head1, head2) do { \
|
|---|
| 230 | if (!STAILQ_EMPTY((head2))) { \
|
|---|
| 231 | *(head1)->stqh_last = (head2)->stqh_first; \
|
|---|
| 232 | (head1)->stqh_last = (head2)->stqh_last; \
|
|---|
| 233 | STAILQ_INIT((head2)); \
|
|---|
| 234 | } \
|
|---|
| 235 | } while (*"\0")
|
|---|
| 236 |
|
|---|
| 237 | #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
|
|---|
| 238 |
|
|---|
| 239 | #define STAILQ_FIRST(head) ((head)->stqh_first)
|
|---|
| 240 |
|
|---|
| 241 | #define STAILQ_FOREACH(var, head, field) \
|
|---|
| 242 | for((var) = STAILQ_FIRST((head)); \
|
|---|
| 243 | (var); \
|
|---|
| 244 | (var) = STAILQ_NEXT((var), field))
|
|---|
| 245 |
|
|---|
| 246 |
|
|---|
| 247 | #define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
|
|---|
| 248 | for ((var) = STAILQ_FIRST((head)); \
|
|---|
| 249 | (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
|
|---|
| 250 | (var) = (tvar))
|
|---|
| 251 |
|
|---|
| 252 | #define STAILQ_INIT(head) do { \
|
|---|
| 253 | STAILQ_FIRST((head)) = NULL; \
|
|---|
| 254 | (head)->stqh_last = &STAILQ_FIRST((head)); \
|
|---|
| 255 | } while (*"\0")
|
|---|
| 256 |
|
|---|
| 257 | #define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
|
|---|
| 258 | if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
|
|---|
| 259 | (head)->stqh_last = &STAILQ_NEXT((elm), field); \
|
|---|
| 260 | STAILQ_NEXT((tqelm), field) = (elm); \
|
|---|
| 261 | } while (*"\0")
|
|---|
| 262 |
|
|---|
| 263 | #define STAILQ_INSERT_HEAD(head, elm, field) do { \
|
|---|
| 264 | if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
|
|---|
| 265 | (head)->stqh_last = &STAILQ_NEXT((elm), field); \
|
|---|
| 266 | STAILQ_FIRST((head)) = (elm); \
|
|---|
| 267 | } while (*"\0")
|
|---|
| 268 |
|
|---|
| 269 | #define STAILQ_INSERT_TAIL(head, elm, field) do { \
|
|---|
| 270 | STAILQ_NEXT((elm), field) = NULL; \
|
|---|
| 271 | *(head)->stqh_last = (elm); \
|
|---|
| 272 | (head)->stqh_last = &STAILQ_NEXT((elm), field); \
|
|---|
| 273 | } while (*"\0")
|
|---|
| 274 |
|
|---|
| 275 | #define STAILQ_LAST(head, type, field) \
|
|---|
| 276 | (STAILQ_EMPTY((head)) ? \
|
|---|
| 277 | NULL : \
|
|---|
| 278 | ((struct type *)(void *) \
|
|---|
| 279 | ((char *)((head)->stqh_last) - __offsetof(struct type, field))))
|
|---|
| 280 |
|
|---|
| 281 | #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
|
|---|
| 282 |
|
|---|
| 283 | #define STAILQ_REMOVE(head, elm, type, field) do { \
|
|---|
| 284 | if (STAILQ_FIRST((head)) == (elm)) { \
|
|---|
| 285 | STAILQ_REMOVE_HEAD((head), field); \
|
|---|
| 286 | } \
|
|---|
| 287 | else { \
|
|---|
| 288 | struct type *curelm = STAILQ_FIRST((head)); \
|
|---|
| 289 | while (STAILQ_NEXT(curelm, field) != (elm)) \
|
|---|
| 290 | curelm = STAILQ_NEXT(curelm, field); \
|
|---|
| 291 | if ((STAILQ_NEXT(curelm, field) = \
|
|---|
| 292 | STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\
|
|---|
| 293 | (head)->stqh_last = &STAILQ_NEXT((curelm), field);\
|
|---|
| 294 | } \
|
|---|
| 295 | TRASHIT((elm)->field.stqe_next); \
|
|---|
| 296 | } while (*"\0")
|
|---|
| 297 |
|
|---|
| 298 | #define STAILQ_REMOVE_HEAD(head, field) do { \
|
|---|
| 299 | if ((STAILQ_FIRST((head)) = \
|
|---|
| 300 | STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \
|
|---|
| 301 | (head)->stqh_last = &STAILQ_FIRST((head)); \
|
|---|
| 302 | } while (*"\0")
|
|---|
| 303 |
|
|---|
| 304 | #define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \
|
|---|
| 305 | if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \
|
|---|
| 306 | (head)->stqh_last = &STAILQ_FIRST((head)); \
|
|---|
| 307 | } while (*"\0")
|
|---|
| 308 |
|
|---|
| 309 | /*
|
|---|
| 310 | * List declarations.
|
|---|
| 311 | */
|
|---|
| 312 | #define LIST_HEAD(name, type) \
|
|---|
| 313 | struct name { \
|
|---|
| 314 | struct type *lh_first; /* first element */ \
|
|---|
| 315 | }
|
|---|
| 316 |
|
|---|
| 317 | #define LIST_HEAD_INITIALIZER(head) \
|
|---|
| 318 | { NULL }
|
|---|
| 319 |
|
|---|
| 320 | #define LIST_ENTRY(type) \
|
|---|
| 321 | struct { \
|
|---|
| 322 | struct type *le_next; /* next element */ \
|
|---|
| 323 | struct type **le_prev; /* address of previous next element */ \
|
|---|
| 324 | }
|
|---|
| 325 |
|
|---|
| 326 | /*
|
|---|
| 327 | * List functions.
|
|---|
| 328 | */
|
|---|
| 329 |
|
|---|
| 330 | #if (defined(_KERNEL) && defined(INVARIANTS))
|
|---|
| 331 | #define QMD_LIST_CHECK_HEAD(head, field) do { \
|
|---|
| 332 | if (LIST_FIRST((head)) != NULL && \
|
|---|
| 333 | LIST_FIRST((head))->field.le_prev != \
|
|---|
| 334 | &LIST_FIRST((head))) \
|
|---|
| 335 | panic("Bad list head %p first->prev != head", (head)); \
|
|---|
| 336 | } while (*"\0")
|
|---|
| 337 |
|
|---|
| 338 | #define QMD_LIST_CHECK_NEXT(elm, field) do { \
|
|---|
| 339 | if (LIST_NEXT((elm), field) != NULL && \
|
|---|
| 340 | LIST_NEXT((elm), field)->field.le_prev != \
|
|---|
| 341 | &((elm)->field.le_next)) \
|
|---|
| 342 | panic("Bad link elm %p next->prev != elm", (elm)); \
|
|---|
| 343 | } while (*"\0")
|
|---|
| 344 |
|
|---|
| 345 | #define QMD_LIST_CHECK_PREV(elm, field) do { \
|
|---|
| 346 | if (*(elm)->field.le_prev != (elm)) \
|
|---|
| 347 | panic("Bad link elm %p prev->next != elm", (elm)); \
|
|---|
| 348 | } while (*"\0")
|
|---|
| 349 | #else
|
|---|
| 350 | #define QMD_LIST_CHECK_HEAD(head, field)
|
|---|
| 351 | #define QMD_LIST_CHECK_NEXT(elm, field)
|
|---|
| 352 | #define QMD_LIST_CHECK_PREV(elm, field)
|
|---|
| 353 | #endif /* (_KERNEL && INVARIANTS) */
|
|---|
| 354 |
|
|---|
| 355 | #define LIST_EMPTY(head) ((head)->lh_first == NULL)
|
|---|
| 356 |
|
|---|
| 357 | #define LIST_FIRST(head) ((head)->lh_first)
|
|---|
| 358 |
|
|---|
| 359 | #define LIST_FOREACH(var, head, field) \
|
|---|
| 360 | for ((var) = LIST_FIRST((head)); \
|
|---|
| 361 | (var); \
|
|---|
| 362 | (var) = LIST_NEXT((var), field))
|
|---|
| 363 |
|
|---|
| 364 | #define LIST_FOREACH_SAFE(var, head, field, tvar) \
|
|---|
| 365 | for ((var) = LIST_FIRST((head)); \
|
|---|
| 366 | (var) && ((tvar) = LIST_NEXT((var), field), 1); \
|
|---|
| 367 | (var) = (tvar))
|
|---|
| 368 |
|
|---|
| 369 | #define LIST_INIT(head) do { \
|
|---|
| 370 | LIST_FIRST((head)) = NULL; \
|
|---|
| 371 | } while (*"\0")
|
|---|
| 372 |
|
|---|
| 373 | #define LIST_INSERT_AFTER(listelm, elm, field) do { \
|
|---|
| 374 | QMD_LIST_CHECK_NEXT(listelm, field); \
|
|---|
| 375 | if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
|
|---|
| 376 | LIST_NEXT((listelm), field)->field.le_prev = \
|
|---|
| 377 | &LIST_NEXT((elm), field); \
|
|---|
| 378 | LIST_NEXT((listelm), field) = (elm); \
|
|---|
| 379 | (elm)->field.le_prev = &LIST_NEXT((listelm), field); \
|
|---|
| 380 | } while (*"\0")
|
|---|
| 381 |
|
|---|
| 382 | #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
|
|---|
| 383 | QMD_LIST_CHECK_PREV(listelm, field); \
|
|---|
| 384 | (elm)->field.le_prev = (listelm)->field.le_prev; \
|
|---|
| 385 | LIST_NEXT((elm), field) = (listelm); \
|
|---|
| 386 | *(listelm)->field.le_prev = (elm); \
|
|---|
| 387 | (listelm)->field.le_prev = &LIST_NEXT((elm), field); \
|
|---|
| 388 | } while (*"\0")
|
|---|
| 389 |
|
|---|
| 390 | #define LIST_INSERT_HEAD(head, elm, field) do { \
|
|---|
| 391 | QMD_LIST_CHECK_HEAD((head), field); \
|
|---|
| 392 | if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
|
|---|
| 393 | LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
|
|---|
| 394 | LIST_FIRST((head)) = (elm); \
|
|---|
| 395 | (elm)->field.le_prev = &LIST_FIRST((head)); \
|
|---|
| 396 | } while (*"\0")
|
|---|
| 397 |
|
|---|
| 398 | #define LIST_NEXT(elm, field) ((elm)->field.le_next)
|
|---|
| 399 |
|
|---|
| 400 | #define LIST_REMOVE(elm, field) do { \
|
|---|
| 401 | QMD_LIST_CHECK_NEXT(elm, field); \
|
|---|
| 402 | QMD_LIST_CHECK_PREV(elm, field); \
|
|---|
| 403 | if (LIST_NEXT((elm), field) != NULL) \
|
|---|
| 404 | LIST_NEXT((elm), field)->field.le_prev = \
|
|---|
| 405 | (elm)->field.le_prev; \
|
|---|
| 406 | *(elm)->field.le_prev = LIST_NEXT((elm), field); \
|
|---|
| 407 | TRASHIT((elm)->field.le_next); \
|
|---|
| 408 | TRASHIT((elm)->field.le_prev); \
|
|---|
| 409 | } while (*"\0")
|
|---|
| 410 |
|
|---|
| 411 | /*
|
|---|
| 412 | * Tail queue declarations.
|
|---|
| 413 | */
|
|---|
| 414 | #define TAILQ_HEAD(name, type) \
|
|---|
| 415 | struct name { \
|
|---|
| 416 | struct type *tqh_first; /* first element */ \
|
|---|
| 417 | struct type **tqh_last; /* addr of last next element */ \
|
|---|
| 418 | TRACEBUF \
|
|---|
| 419 | }
|
|---|
| 420 |
|
|---|
| 421 | #define TAILQ_HEAD_INITIALIZER(head) \
|
|---|
| 422 | { NULL, &(head).tqh_first }
|
|---|
| 423 |
|
|---|
| 424 | #define TAILQ_ENTRY(type) \
|
|---|
| 425 | struct { \
|
|---|
| 426 | struct type *tqe_next; /* next element */ \
|
|---|
| 427 | struct type **tqe_prev; /* address of previous next element */ \
|
|---|
| 428 | TRACEBUF \
|
|---|
| 429 | }
|
|---|
| 430 |
|
|---|
| 431 | /*
|
|---|
| 432 | * Tail queue functions.
|
|---|
| 433 | */
|
|---|
| 434 | #if (defined(_KERNEL) && defined(INVARIANTS))
|
|---|
| 435 | #define QMD_TAILQ_CHECK_HEAD(head, field) do { \
|
|---|
| 436 | if (!TAILQ_EMPTY(head) && \
|
|---|
| 437 | TAILQ_FIRST((head))->field.tqe_prev != \
|
|---|
| 438 | &TAILQ_FIRST((head))) \
|
|---|
| 439 | panic("Bad tailq head %p first->prev != head", (head)); \
|
|---|
| 440 | } while (*"\0")
|
|---|
| 441 |
|
|---|
| 442 | #define QMD_TAILQ_CHECK_TAIL(head, field) do { \
|
|---|
| 443 | if (*(head)->tqh_last != NULL) \
|
|---|
| 444 | panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \
|
|---|
| 445 | } while (*"\0")
|
|---|
| 446 |
|
|---|
| 447 | #define QMD_TAILQ_CHECK_NEXT(elm, field) do { \
|
|---|
| 448 | if (TAILQ_NEXT((elm), field) != NULL && \
|
|---|
| 449 | TAILQ_NEXT((elm), field)->field.tqe_prev != \
|
|---|
| 450 | &((elm)->field.tqe_next)) \
|
|---|
| 451 | panic("Bad link elm %p next->prev != elm", (elm)); \
|
|---|
| 452 | } while (*"\0")
|
|---|
| 453 |
|
|---|
| 454 | #define QMD_TAILQ_CHECK_PREV(elm, field) do { \
|
|---|
| 455 | if (*(elm)->field.tqe_prev != (elm)) \
|
|---|
| 456 | panic("Bad link elm %p prev->next != elm", (elm)); \
|
|---|
| 457 | } while (*"\0")
|
|---|
| 458 | #else
|
|---|
| 459 | #define QMD_TAILQ_CHECK_HEAD(head, field)
|
|---|
| 460 | #define QMD_TAILQ_CHECK_TAIL(head, headname)
|
|---|
| 461 | #define QMD_TAILQ_CHECK_NEXT(elm, field)
|
|---|
| 462 | #define QMD_TAILQ_CHECK_PREV(elm, field)
|
|---|
| 463 | #endif /* (_KERNEL && INVARIANTS) */
|
|---|
| 464 |
|
|---|
| 465 | #define TAILQ_CONCAT(head1, head2, field) do { \
|
|---|
| 466 | if (!TAILQ_EMPTY(head2)) { \
|
|---|
| 467 | *(head1)->tqh_last = (head2)->tqh_first; \
|
|---|
| 468 | (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
|
|---|
| 469 | (head1)->tqh_last = (head2)->tqh_last; \
|
|---|
| 470 | TAILQ_INIT((head2)); \
|
|---|
| 471 | QMD_TRACE_HEAD(head1); \
|
|---|
| 472 | QMD_TRACE_HEAD(head2); \
|
|---|
| 473 | } \
|
|---|
| 474 | } while (*"\0")
|
|---|
| 475 |
|
|---|
| 476 | #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
|
|---|
| 477 |
|
|---|
| 478 | #define TAILQ_FIRST(head) ((head)->tqh_first)
|
|---|
| 479 |
|
|---|
| 480 | #define TAILQ_FOREACH(var, head, field) \
|
|---|
| 481 | for ((var) = TAILQ_FIRST((head)); \
|
|---|
| 482 | (var); \
|
|---|
| 483 | (var) = TAILQ_NEXT((var), field))
|
|---|
| 484 |
|
|---|
| 485 | #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
|
|---|
| 486 | for ((var) = TAILQ_FIRST((head)); \
|
|---|
| 487 | (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
|
|---|
| 488 | (var) = (tvar))
|
|---|
| 489 |
|
|---|
| 490 | #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
|
|---|
| 491 | for ((var) = TAILQ_LAST((head), headname); \
|
|---|
| 492 | (var); \
|
|---|
| 493 | (var) = TAILQ_PREV((var), headname, field))
|
|---|
| 494 |
|
|---|
| 495 | #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
|
|---|
| 496 | for ((var) = TAILQ_LAST((head), headname); \
|
|---|
| 497 | (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
|
|---|
| 498 | (var) = (tvar))
|
|---|
| 499 |
|
|---|
| 500 | #define TAILQ_INIT(head) do { \
|
|---|
| 501 | TAILQ_FIRST((head)) = NULL; \
|
|---|
| 502 | (head)->tqh_last = &TAILQ_FIRST((head)); \
|
|---|
| 503 | QMD_TRACE_HEAD(head); \
|
|---|
| 504 | } while (*"\0")
|
|---|
| 505 |
|
|---|
| 506 | #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
|
|---|
| 507 | QMD_TAILQ_CHECK_NEXT(listelm, field); \
|
|---|
| 508 | if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
|
|---|
| 509 | TAILQ_NEXT((elm), field)->field.tqe_prev = \
|
|---|
| 510 | &TAILQ_NEXT((elm), field); \
|
|---|
| 511 | else { \
|
|---|
| 512 | (head)->tqh_last = &TAILQ_NEXT((elm), field); \
|
|---|
| 513 | QMD_TRACE_HEAD(head); \
|
|---|
| 514 | } \
|
|---|
| 515 | TAILQ_NEXT((listelm), field) = (elm); \
|
|---|
| 516 | (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
|
|---|
| 517 | QMD_TRACE_ELEM(&(elm)->field); \
|
|---|
| 518 | QMD_TRACE_ELEM(&listelm->field); \
|
|---|
| 519 | } while (*"\0")
|
|---|
| 520 |
|
|---|
| 521 | #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
|
|---|
| 522 | QMD_TAILQ_CHECK_PREV(listelm, field); \
|
|---|
| 523 | (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
|
|---|
| 524 | TAILQ_NEXT((elm), field) = (listelm); \
|
|---|
| 525 | *(listelm)->field.tqe_prev = (elm); \
|
|---|
| 526 | (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
|
|---|
| 527 | QMD_TRACE_ELEM(&(elm)->field); \
|
|---|
| 528 | QMD_TRACE_ELEM(&listelm->field); \
|
|---|
| 529 | } while (*"\0")
|
|---|
| 530 |
|
|---|
| 531 | #define TAILQ_INSERT_HEAD(head, elm, field) do { \
|
|---|
| 532 | QMD_TAILQ_CHECK_HEAD(head, field); \
|
|---|
| 533 | if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
|
|---|
| 534 | TAILQ_FIRST((head))->field.tqe_prev = \
|
|---|
| 535 | &TAILQ_NEXT((elm), field); \
|
|---|
| 536 | else \
|
|---|
| 537 | (head)->tqh_last = &TAILQ_NEXT((elm), field); \
|
|---|
| 538 | TAILQ_FIRST((head)) = (elm); \
|
|---|
| 539 | (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
|
|---|
| 540 | QMD_TRACE_HEAD(head); \
|
|---|
| 541 | QMD_TRACE_ELEM(&(elm)->field); \
|
|---|
| 542 | } while (*"\0")
|
|---|
| 543 |
|
|---|
| 544 | #define TAILQ_INSERT_TAIL(head, elm, field) do { \
|
|---|
| 545 | QMD_TAILQ_CHECK_TAIL(head, field); \
|
|---|
| 546 | TAILQ_NEXT((elm), field) = NULL; \
|
|---|
| 547 | (elm)->field.tqe_prev = (head)->tqh_last; \
|
|---|
| 548 | *(head)->tqh_last = (elm); \
|
|---|
| 549 | (head)->tqh_last = &TAILQ_NEXT((elm), field); \
|
|---|
| 550 | QMD_TRACE_HEAD(head); \
|
|---|
| 551 | QMD_TRACE_ELEM(&(elm)->field); \
|
|---|
| 552 | } while (*"\0")
|
|---|
| 553 |
|
|---|
| 554 | #define TAILQ_LAST(head, headname) \
|
|---|
| 555 | (*(((struct headname *)((head)->tqh_last))->tqh_last))
|
|---|
| 556 |
|
|---|
| 557 | #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
|
|---|
| 558 |
|
|---|
| 559 | #define TAILQ_PREV(elm, headname, field) \
|
|---|
| 560 | (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
|
|---|
| 561 |
|
|---|
| 562 | #define TAILQ_REMOVE(head, elm, field) do { \
|
|---|
| 563 | QMD_TAILQ_CHECK_NEXT(elm, field); \
|
|---|
| 564 | QMD_TAILQ_CHECK_PREV(elm, field); \
|
|---|
| 565 | if ((TAILQ_NEXT((elm), field)) != NULL) \
|
|---|
| 566 | TAILQ_NEXT((elm), field)->field.tqe_prev = \
|
|---|
| 567 | (elm)->field.tqe_prev; \
|
|---|
| 568 | else { \
|
|---|
| 569 | (head)->tqh_last = (elm)->field.tqe_prev; \
|
|---|
| 570 | QMD_TRACE_HEAD(head); \
|
|---|
| 571 | } \
|
|---|
| 572 | *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
|
|---|
| 573 | TRASHIT((elm)->field.tqe_next); \
|
|---|
| 574 | TRASHIT((elm)->field.tqe_prev); \
|
|---|
| 575 | QMD_TRACE_ELEM(&(elm)->field); \
|
|---|
| 576 | } while (*"\0")
|
|---|
| 577 |
|
|---|
| 578 |
|
|---|
| 579 | #ifdef _KERNEL
|
|---|
| 580 |
|
|---|
| 581 | #endif /* _KERNEL */
|
|---|
| 582 |
|
|---|
| 583 | #endif /* !_SYS_QUEUE_H_ */
|
|---|
| 584 |
|
|---|
| 585 | /* END CSTYLED */
|
|---|
