Print this page
DLPX-25998 TCP congestion control is inadequate
Reviewed at: http://reviews.delphix.com/r/34808/
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/uts/common/sys/queue.h
+++ new/usr/src/uts/common/sys/queue.h
1 1 /* $NetBSD: queue.h,v 1.42 2005/07/13 15:08:24 wiz Exp $ */
2 2
3 3 /*
4 4 * Copyright (c) 1991, 1993
5 5 * The Regents of the University of California. All rights reserved.
6 6 *
7 7 * Redistribution and use in source and binary forms, with or without
8 8 * modification, are permitted provided that the following conditions
9 9 * are met:
10 10 * 1. Redistributions of source code must retain the above copyright
11 11 * notice, this list of conditions and the following disclaimer.
12 12 * 2. Redistributions in binary form must reproduce the above copyright
13 13 * notice, this list of conditions and the following disclaimer in the
14 14 * documentation and/or other materials provided with the distribution.
15 15 * 3. Neither the name of the University nor the names of its contributors
16 16 * may be used to endorse or promote products derived from this software
17 17 * without specific prior written permission.
18 18 *
19 19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 29 * SUCH DAMAGE.
30 30 *
31 31 * @(#)queue.h 8.5 (Berkeley) 8/20/94
32 32 */
33 33 /*
34 34 * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
35 35 * Use is subject to license terms.
36 36 */
37 37
38 38 #ifndef _SYS_QUEUE_H
39 39 #define _SYS_QUEUE_H
40 40
41 41 #include <sys/note.h>
42 42
43 43 #ifdef __cplusplus
44 44 extern "C" {
45 45 #endif
46 46
47 47 /*
48 48 * This file defines five types of data structures: singly-linked lists,
49 49 * lists, simple queues, tail queues, and circular queues.
50 50 *
51 51 * A singly-linked list is headed by a single forward pointer. The
52 52 * elements are singly linked for minimum space and pointer manipulation
53 53 * overhead at the expense of O(n) removal for arbitrary elements. New
54 54 * elements can be added to the list after an existing element or at the
55 55 * head of the list. Elements being removed from the head of the list
56 56 * should use the explicit macro for this purpose for optimum
57 57 * efficiency. A singly-linked list may only be traversed in the forward
58 58 * direction. Singly-linked lists are ideal for applications with large
59 59 * datasets and few or no removals or for implementing a LIFO queue.
60 60 *
61 61 * A list is headed by a single forward pointer (or an array of forward
62 62 * pointers for a hash table header). The elements are doubly linked
63 63 * so that an arbitrary element can be removed without a need to
64 64 * traverse the list. New elements can be added to the list before
65 65 * or after an existing element or at the head of the list. A list
66 66 * may only be traversed in the forward direction.
67 67 *
68 68 * A simple queue is headed by a pair of pointers, one the head of the
69 69 * list and the other to the tail of the list. The elements are singly
70 70 * linked to save space, so elements can only be removed from the
71 71 * head of the list. New elements can be added to the list after
72 72 * an existing element, at the head of the list, or at the end of the
73 73 * list. A simple queue may only be traversed in the forward direction.
74 74 *
75 75 * A tail queue is headed by a pair of pointers, one to the head of the
76 76 * list and the other to the tail of the list. The elements are doubly
77 77 * linked so that an arbitrary element can be removed without a need to
78 78 * traverse the list. New elements can be added to the list before or
79 79 * after an existing element, at the head of the list, or at the end of
80 80 * the list. A tail queue may be traversed in either direction.
81 81 *
82 82 * A circle queue is headed by a pair of pointers, one to the head of the
83 83 * list and the other to the tail of the list. The elements are doubly
84 84 * linked so that an arbitrary element can be removed without a need to
85 85 * traverse the list. New elements can be added to the list before or after
86 86 * an existing element, at the head of the list, or at the end of the list.
87 87 * A circle queue may be traversed in either direction, but has a more
88 88 * complex end of list detection.
89 89 *
90 90 * For details on the use of these macros, see the queue(3) manual page.
91 91 */
92 92
93 93 /*
94 94 * List definitions.
95 95 */
96 96 #define LIST_HEAD(name, type) \
97 97 struct name { \
98 98 struct type *lh_first; /* first element */ \
99 99 }
100 100
101 101 #define LIST_HEAD_INITIALIZER(head) \
102 102 { NULL }
103 103
104 104 #define LIST_ENTRY(type) \
105 105 struct { \
106 106 struct type *le_next; /* next element */ \
107 107 struct type **le_prev; /* address of previous next element */ \
108 108 }
109 109
110 110 /*
111 111 * List functions.
112 112 */
113 113 #if defined(_KERNEL) && defined(QUEUEDEBUG)
114 114 #define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field) \
115 115 if ((head)->lh_first && \
116 116 (head)->lh_first->field.le_prev != &(head)->lh_first) \
117 117 panic("LIST_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
118 118 #define QUEUEDEBUG_LIST_OP(elm, field) \
119 119 if ((elm)->field.le_next && \
120 120 (elm)->field.le_next->field.le_prev != \
121 121 &(elm)->field.le_next) \
122 122 panic("LIST_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
123 123 if (*(elm)->field.le_prev != (elm)) \
124 124 panic("LIST_* back %p %s:%d", (elm), __FILE__, __LINE__);
125 125 #define QUEUEDEBUG_LIST_POSTREMOVE(elm, field) \
126 126 (elm)->field.le_next = (void *)1L; \
127 127 (elm)->field.le_prev = (void *)1L;
128 128 #else
129 129 #define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)
130 130 #define QUEUEDEBUG_LIST_OP(elm, field)
131 131 #define QUEUEDEBUG_LIST_POSTREMOVE(elm, field)
132 132 #endif
133 133
134 134 #define LIST_INIT(head) do { \
135 135 (head)->lh_first = NULL; \
136 136 _NOTE(CONSTCOND) \
137 137 } while (0)
138 138
139 139 #define LIST_INSERT_AFTER(listelm, elm, field) do { \
140 140 QUEUEDEBUG_LIST_OP((listelm), field) \
141 141 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
142 142 (listelm)->field.le_next->field.le_prev = \
143 143 &(elm)->field.le_next; \
144 144 (listelm)->field.le_next = (elm); \
145 145 (elm)->field.le_prev = &(listelm)->field.le_next; \
146 146 _NOTE(CONSTCOND) \
147 147 } while (0)
148 148
149 149 #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
150 150 QUEUEDEBUG_LIST_OP((listelm), field) \
151 151 (elm)->field.le_prev = (listelm)->field.le_prev; \
152 152 (elm)->field.le_next = (listelm); \
153 153 *(listelm)->field.le_prev = (elm); \
154 154 (listelm)->field.le_prev = &(elm)->field.le_next; \
155 155 _NOTE(CONSTCOND) \
156 156 } while (0)
157 157
158 158 #define LIST_INSERT_HEAD(head, elm, field) do { \
159 159 QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field) \
160 160 if (((elm)->field.le_next = (head)->lh_first) != NULL) \
161 161 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
162 162 (head)->lh_first = (elm); \
163 163 (elm)->field.le_prev = &(head)->lh_first; \
164 164 _NOTE(CONSTCOND) \
165 165 } while (0)
166 166
167 167 #define LIST_REMOVE(elm, field) do { \
168 168 QUEUEDEBUG_LIST_OP((elm), field) \
169 169 if ((elm)->field.le_next != NULL) \
170 170 (elm)->field.le_next->field.le_prev = \
171 171 (elm)->field.le_prev; \
172 172 *(elm)->field.le_prev = (elm)->field.le_next; \
173 173 QUEUEDEBUG_LIST_POSTREMOVE((elm), field) \
174 174 _NOTE(CONSTCOND) \
175 175 } while (0)
176 176
177 177 #define LIST_FOREACH(var, head, field) \
178 178 for ((var) = ((head)->lh_first); \
179 179 (var); \
180 180 (var) = ((var)->field.le_next))
181 181
182 182 /*
183 183 * List access methods.
184 184 */
185 185 #define LIST_EMPTY(head) ((head)->lh_first == NULL)
186 186 #define LIST_FIRST(head) ((head)->lh_first)
187 187 #define LIST_NEXT(elm, field) ((elm)->field.le_next)
188 188
189 189
190 190 /*
191 191 * Singly-linked List definitions.
192 192 */
193 193 #define SLIST_HEAD(name, type) \
194 194 struct name { \
195 195 struct type *slh_first; /* first element */ \
196 196 }
197 197
198 198 #define SLIST_HEAD_INITIALIZER(head) \
199 199 { NULL }
200 200
201 201 #define SLIST_ENTRY(type) \
202 202 struct { \
203 203 struct type *sle_next; /* next element */ \
204 204 }
205 205
206 206 /*
207 207 * Singly-linked List functions.
208 208 */
209 209 #define SLIST_INIT(head) do { \
210 210 (head)->slh_first = NULL; \
211 211 _NOTE(CONSTCOND) \
212 212 } while (0)
213 213
214 214 #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
215 215 (elm)->field.sle_next = (slistelm)->field.sle_next; \
216 216 (slistelm)->field.sle_next = (elm); \
217 217 _NOTE(CONSTCOND) \
218 218 } while (0)
219 219
220 220 #define SLIST_INSERT_HEAD(head, elm, field) do { \
221 221 (elm)->field.sle_next = (head)->slh_first; \
222 222 (head)->slh_first = (elm); \
223 223 _NOTE(CONSTCOND) \
224 224 } while (0)
225 225
226 226 #define SLIST_REMOVE_HEAD(head, field) do { \
227 227 (head)->slh_first = (head)->slh_first->field.sle_next; \
228 228 _NOTE(CONSTCOND) \
229 229 } while (0)
230 230
231 231 #define SLIST_REMOVE(head, elm, type, field) do { \
232 232 if ((head)->slh_first == (elm)) { \
233 233 SLIST_REMOVE_HEAD((head), field); \
234 234 } \
235 235 else { \
236 236 struct type *curelm = (head)->slh_first; \
237 237 while (curelm->field.sle_next != (elm)) \
238 238 curelm = curelm->field.sle_next; \
239 239 curelm->field.sle_next = \
240 240 curelm->field.sle_next->field.sle_next; \
241 241 } \
242 242 _NOTE(CONSTCOND) \
243 243 } while (0)
244 244
245 245 #define SLIST_FOREACH(var, head, field) \
246 246 for ((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
247 247
248 248 /*
249 249 * Singly-linked List access methods.
250 250 */
251 251 #define SLIST_EMPTY(head) ((head)->slh_first == NULL)
252 252 #define SLIST_FIRST(head) ((head)->slh_first)
253 253 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
254 254
255 255
256 256 /*
257 257 * Singly-linked Tail queue declarations.
258 258 */
259 259 #define STAILQ_HEAD(name, type) \
260 260 struct name { \
261 261 struct type *stqh_first; /* first element */ \
262 262 struct type **stqh_last; /* addr of last next element */ \
263 263 }
264 264
265 265 #define STAILQ_HEAD_INITIALIZER(head) \
266 266 { NULL, &(head).stqh_first }
267 267
268 268 #define STAILQ_ENTRY(type) \
269 269 struct { \
270 270 struct type *stqe_next; /* next element */ \
271 271 }
272 272
273 273 /*
274 274 * Singly-linked Tail queue functions.
275 275 */
276 276 #define STAILQ_INIT(head) do { \
277 277 (head)->stqh_first = NULL; \
278 278 (head)->stqh_last = &(head)->stqh_first; \
279 279 _NOTE(CONSTCOND) \
280 280 } while (0)
281 281
282 282 #define STAILQ_INSERT_HEAD(head, elm, field) do { \
283 283 if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \
284 284 (head)->stqh_last = &(elm)->field.stqe_next; \
285 285 (head)->stqh_first = (elm); \
286 286 _NOTE(CONSTCOND) \
287 287 } while (0)
288 288
289 289 #define STAILQ_INSERT_TAIL(head, elm, field) do { \
290 290 (elm)->field.stqe_next = NULL; \
291 291 *(head)->stqh_last = (elm); \
292 292 (head)->stqh_last = &(elm)->field.stqe_next; \
293 293 _NOTE(CONSTCOND) \
294 294 } while (0)
295 295
296 296 #define STAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
297 297 if (((elm)->field.stqe_next = (listelm)->field.stqe_next) \
298 298 == NULL) \
299 299 (head)->stqh_last = &(elm)->field.stqe_next; \
300 300 (listelm)->field.stqe_next = (elm); \
301 301 _NOTE(CONSTCOND) \
302 302 } while (0)
303 303
304 304 #define STAILQ_REMOVE_HEAD(head, field) do { \
305 305 if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) \
306 306 == NULL) \
307 307 (head)->stqh_last = &(head)->stqh_first; \
308 308 _NOTE(CONSTCOND) \
309 309 } while (0)
310 310
311 311 #define STAILQ_REMOVE(head, elm, type, field) do { \
312 312 if ((head)->stqh_first == (elm)) { \
313 313 STAILQ_REMOVE_HEAD((head), field); \
314 314 } else { \
|
↓ open down ↓ |
314 lines elided |
↑ open up ↑ |
315 315 struct type *curelm = (head)->stqh_first; \
316 316 while (curelm->field.stqe_next != (elm)) \
317 317 curelm = curelm->field.stqe_next; \
318 318 if ((curelm->field.stqe_next = \
319 319 curelm->field.stqe_next->field.stqe_next) == NULL) \
320 320 (head)->stqh_last = &(curelm)->field.stqe_next; \
321 321 } \
322 322 _NOTE(CONSTCOND) \
323 323 } while (0)
324 324
325 -#define STAILQ_FOREACH(var, head, field) \
326 - for ((var) = ((head)->stqh_first); \
327 - (var); \
328 - (var) = ((var)->field.stqe_next))
329 -
330 325 /*
331 326 * Singly-linked Tail queue access methods.
332 327 */
333 328 #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
334 329 #define STAILQ_FIRST(head) ((head)->stqh_first)
335 330 #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
336 331
332 +#define STAILQ_FOREACH(var, head, field) \
333 + for ((var) = ((head)->stqh_first); \
334 + (var); \
335 + (var) = ((var)->field.stqe_next))
337 336
337 +#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
338 + for ((var) = STAILQ_FIRST((head)); \
339 + (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
340 + (var) = (tvar))
341 +
342 +
338 343 /*
339 344 * Simple queue definitions.
340 345 */
341 346 #define SIMPLEQ_HEAD(name, type) \
342 347 struct name { \
343 348 struct type *sqh_first; /* first element */ \
344 349 struct type **sqh_last; /* addr of last next element */ \
345 350 }
346 351
347 352 #define SIMPLEQ_HEAD_INITIALIZER(head) \
348 353 { NULL, &(head).sqh_first }
349 354
350 355 #define SIMPLEQ_ENTRY(type) \
351 356 struct { \
352 357 struct type *sqe_next; /* next element */ \
353 358 }
354 359
355 360 /*
356 361 * Simple queue functions.
357 362 */
358 363 #define SIMPLEQ_INIT(head) do { \
359 364 (head)->sqh_first = NULL; \
360 365 (head)->sqh_last = &(head)->sqh_first; \
361 366 _NOTE(CONSTCOND) \
362 367 } while (0)
363 368
364 369 #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
365 370 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
366 371 (head)->sqh_last = &(elm)->field.sqe_next; \
367 372 (head)->sqh_first = (elm); \
368 373 _NOTE(CONSTCOND) \
369 374 } while (0)
370 375
371 376 #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
372 377 (elm)->field.sqe_next = NULL; \
373 378 *(head)->sqh_last = (elm); \
374 379 (head)->sqh_last = &(elm)->field.sqe_next; \
375 380 _NOTE(CONSTCOND) \
376 381 } while (0)
377 382
378 383 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
379 384 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
380 385 (head)->sqh_last = &(elm)->field.sqe_next; \
381 386 (listelm)->field.sqe_next = (elm); \
382 387 _NOTE(CONSTCOND) \
383 388 } while (0)
384 389
385 390 #define SIMPLEQ_REMOVE_HEAD(head, field) do { \
386 391 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
387 392 (head)->sqh_last = &(head)->sqh_first; \
388 393 _NOTE(CONSTCOND) \
389 394 } while (0)
390 395
391 396 #define SIMPLEQ_REMOVE(head, elm, type, field) do { \
392 397 if ((head)->sqh_first == (elm)) { \
393 398 SIMPLEQ_REMOVE_HEAD((head), field); \
394 399 } else { \
395 400 struct type *curelm = (head)->sqh_first; \
396 401 while (curelm->field.sqe_next != (elm)) \
397 402 curelm = curelm->field.sqe_next; \
398 403 if ((curelm->field.sqe_next = \
399 404 curelm->field.sqe_next->field.sqe_next) == NULL) \
400 405 (head)->sqh_last = &(curelm)->field.sqe_next; \
401 406 } \
402 407 _NOTE(CONSTCOND) \
403 408 } while (0)
404 409
405 410 #define SIMPLEQ_FOREACH(var, head, field) \
406 411 for ((var) = ((head)->sqh_first); \
407 412 (var); \
408 413 (var) = ((var)->field.sqe_next))
409 414
410 415 /*
411 416 * Simple queue access methods.
412 417 */
413 418 #define SIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL)
414 419 #define SIMPLEQ_FIRST(head) ((head)->sqh_first)
415 420 #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
416 421
417 422
418 423 /*
419 424 * Tail queue definitions.
420 425 */
421 426 #define _TAILQ_HEAD(name, type) \
422 427 struct name { \
423 428 type *tqh_first; /* first element */ \
424 429 type **tqh_last; /* addr of last next element */ \
425 430 }
426 431 #define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type)
427 432
428 433 #define TAILQ_HEAD_INITIALIZER(head) \
429 434 { NULL, &(head).tqh_first }
430 435
431 436 #define _TAILQ_ENTRY(type) \
432 437 struct { \
433 438 type *tqe_next; /* next element */ \
434 439 type **tqe_prev; /* address of previous next element */\
435 440 }
436 441 #define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type)
437 442
438 443 /*
439 444 * Tail queue functions.
440 445 */
441 446 #if defined(_KERNEL) && defined(QUEUEDEBUG)
442 447 #define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field) \
443 448 if ((head)->tqh_first && \
444 449 (head)->tqh_first->field.tqe_prev != &(head)->tqh_first) \
445 450 panic("TAILQ_INSERT_HEAD %p %s:%d", (void *)(head), \
446 451 __FILE__, __LINE__);
447 452 #define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field) \
448 453 if (*(head)->tqh_last != NULL) \
449 454 panic("TAILQ_INSERT_TAIL %p %s:%d", (void *)(head), \
450 455 __FILE__, __LINE__);
451 456 #define QUEUEDEBUG_TAILQ_OP(elm, field) \
452 457 if ((elm)->field.tqe_next && \
453 458 (elm)->field.tqe_next->field.tqe_prev != \
454 459 &(elm)->field.tqe_next) \
455 460 panic("TAILQ_* forw %p %s:%d", (void *)(elm), \
456 461 __FILE__, __LINE__);\
457 462 if (*(elm)->field.tqe_prev != (elm)) \
458 463 panic("TAILQ_* back %p %s:%d", (void *)(elm), \
459 464 __FILE__, __LINE__);
460 465 #define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field) \
461 466 if ((elm)->field.tqe_next == NULL && \
462 467 (head)->tqh_last != &(elm)->field.tqe_next) \
463 468 panic("TAILQ_PREREMOVE head %p elm %p %s:%d", \
464 469 (void *)(head), (void *)(elm), __FILE__, __LINE__);
465 470 #define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field) \
466 471 (elm)->field.tqe_next = (void *)1L; \
467 472 (elm)->field.tqe_prev = (void *)1L;
468 473 #else
469 474 #define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)
470 475 #define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)
471 476 #define QUEUEDEBUG_TAILQ_OP(elm, field)
472 477 #define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field)
473 478 #define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)
474 479 #endif
475 480
476 481 #define TAILQ_INIT(head) do { \
477 482 (head)->tqh_first = NULL; \
478 483 (head)->tqh_last = &(head)->tqh_first; \
479 484 _NOTE(CONSTCOND) \
480 485 } while (0)
481 486
482 487 #define TAILQ_INSERT_HEAD(head, elm, field) do { \
483 488 QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field) \
484 489 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
485 490 (head)->tqh_first->field.tqe_prev = \
486 491 &(elm)->field.tqe_next; \
487 492 else \
488 493 (head)->tqh_last = &(elm)->field.tqe_next; \
489 494 (head)->tqh_first = (elm); \
490 495 (elm)->field.tqe_prev = &(head)->tqh_first; \
491 496 _NOTE(CONSTCOND) \
492 497 } while (0)
493 498
494 499 #define TAILQ_INSERT_TAIL(head, elm, field) do { \
495 500 QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field) \
496 501 (elm)->field.tqe_next = NULL; \
497 502 (elm)->field.tqe_prev = (head)->tqh_last; \
498 503 *(head)->tqh_last = (elm); \
499 504 (head)->tqh_last = &(elm)->field.tqe_next; \
500 505 _NOTE(CONSTCOND) \
501 506 } while (0)
502 507
503 508 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
504 509 QUEUEDEBUG_TAILQ_OP((listelm), field) \
505 510 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
506 511 (elm)->field.tqe_next->field.tqe_prev = \
507 512 &(elm)->field.tqe_next; \
508 513 else \
509 514 (head)->tqh_last = &(elm)->field.tqe_next; \
510 515 (listelm)->field.tqe_next = (elm); \
511 516 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
512 517 _NOTE(CONSTCOND) \
513 518 } while (0)
514 519
515 520 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
516 521 QUEUEDEBUG_TAILQ_OP((listelm), field) \
517 522 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
518 523 (elm)->field.tqe_next = (listelm); \
519 524 *(listelm)->field.tqe_prev = (elm); \
520 525 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
521 526 _NOTE(CONSTCOND) \
522 527 } while (0)
523 528
524 529 #define TAILQ_REMOVE(head, elm, field) do { \
525 530 QUEUEDEBUG_TAILQ_PREREMOVE((head), (elm), field) \
526 531 QUEUEDEBUG_TAILQ_OP((elm), field) \
527 532 if (((elm)->field.tqe_next) != NULL) \
528 533 (elm)->field.tqe_next->field.tqe_prev = \
529 534 (elm)->field.tqe_prev; \
530 535 else \
531 536 (head)->tqh_last = (elm)->field.tqe_prev; \
532 537 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
533 538 QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field); \
534 539 _NOTE(CONSTCOND) \
535 540 } while (0)
536 541
537 542 #define TAILQ_FOREACH(var, head, field) \
538 543 for ((var) = ((head)->tqh_first); \
539 544 (var); \
540 545 (var) = ((var)->field.tqe_next))
541 546
542 547 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
543 548 for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));\
544 549 (var); \
545 550 (var) = \
546 551 (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
547 552
548 553 /*
549 554 * Tail queue access methods.
550 555 */
551 556 #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
552 557 #define TAILQ_FIRST(head) ((head)->tqh_first)
553 558 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
554 559
555 560 #define TAILQ_LAST(head, headname) \
556 561 (*(((struct headname *)((head)->tqh_last))->tqh_last))
557 562 #define TAILQ_PREV(elm, headname, field) \
558 563 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
559 564
560 565
561 566 /*
562 567 * Circular queue definitions.
563 568 */
564 569 #define CIRCLEQ_HEAD(name, type) \
565 570 struct name { \
566 571 struct type *cqh_first; /* first element */ \
567 572 struct type *cqh_last; /* last element */ \
568 573 }
569 574
570 575 #define CIRCLEQ_HEAD_INITIALIZER(head) \
571 576 { (void *)&head, (void *)&head }
572 577
573 578 #define CIRCLEQ_ENTRY(type) \
574 579 struct { \
575 580 struct type *cqe_next; /* next element */ \
576 581 struct type *cqe_prev; /* previous element */ \
577 582 }
578 583
579 584 /*
580 585 * Circular queue functions.
581 586 */
582 587 #define CIRCLEQ_INIT(head) do { \
583 588 (head)->cqh_first = (void *)(head); \
584 589 (head)->cqh_last = (void *)(head); \
585 590 _NOTE(CONSTCOND) \
586 591 } while (0)
587 592
588 593 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
589 594 (elm)->field.cqe_next = (listelm)->field.cqe_next; \
590 595 (elm)->field.cqe_prev = (listelm); \
591 596 if ((listelm)->field.cqe_next == (void *)(head)) \
592 597 (head)->cqh_last = (elm); \
593 598 else \
594 599 (listelm)->field.cqe_next->field.cqe_prev = (elm); \
595 600 (listelm)->field.cqe_next = (elm); \
596 601 _NOTE(CONSTCOND) \
597 602 } while (0)
598 603
599 604 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
600 605 (elm)->field.cqe_next = (listelm); \
601 606 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
602 607 if ((listelm)->field.cqe_prev == (void *)(head)) \
603 608 (head)->cqh_first = (elm); \
604 609 else \
605 610 (listelm)->field.cqe_prev->field.cqe_next = (elm); \
606 611 (listelm)->field.cqe_prev = (elm); \
607 612 _NOTE(CONSTCOND) \
608 613 } while (0)
609 614
610 615 #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
611 616 (elm)->field.cqe_next = (head)->cqh_first; \
612 617 (elm)->field.cqe_prev = (void *)(head); \
613 618 if ((head)->cqh_last == (void *)(head)) \
614 619 (head)->cqh_last = (elm); \
615 620 else \
616 621 (head)->cqh_first->field.cqe_prev = (elm); \
617 622 (head)->cqh_first = (elm); \
618 623 _NOTE(CONSTCOND) \
619 624 } while (0)
620 625
621 626 #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
622 627 (elm)->field.cqe_next = (void *)(head); \
623 628 (elm)->field.cqe_prev = (head)->cqh_last; \
624 629 if ((head)->cqh_first == (void *)(head)) \
625 630 (head)->cqh_first = (elm); \
626 631 else \
627 632 (head)->cqh_last->field.cqe_next = (elm); \
628 633 (head)->cqh_last = (elm); \
629 634 _NOTE(CONSTCOND) \
630 635 } while (0)
631 636
632 637 #define CIRCLEQ_REMOVE(head, elm, field) do { \
633 638 if ((elm)->field.cqe_next == (void *)(head)) \
634 639 (head)->cqh_last = (elm)->field.cqe_prev; \
635 640 else \
636 641 (elm)->field.cqe_next->field.cqe_prev = \
637 642 (elm)->field.cqe_prev; \
638 643 if ((elm)->field.cqe_prev == (void *)(head)) \
639 644 (head)->cqh_first = (elm)->field.cqe_next; \
640 645 else \
641 646 (elm)->field.cqe_prev->field.cqe_next = \
642 647 (elm)->field.cqe_next; \
643 648 _NOTE(CONSTCOND) \
644 649 } while (0)
645 650
646 651 #define CIRCLEQ_FOREACH(var, head, field) \
647 652 for ((var) = ((head)->cqh_first); \
648 653 (var) != (void *)(head); \
649 654 (var) = ((var)->field.cqe_next))
650 655
651 656 #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
652 657 for ((var) = ((head)->cqh_last); \
653 658 (var) != (void *)(head); \
654 659 (var) = ((var)->field.cqe_prev))
655 660
656 661 /*
657 662 * Circular queue access methods.
658 663 */
659 664 #define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
660 665 #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
661 666 #define CIRCLEQ_LAST(head) ((head)->cqh_last)
662 667 #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
663 668 #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
664 669
665 670 #define CIRCLEQ_LOOP_NEXT(head, elm, field) \
666 671 (((elm)->field.cqe_next == (void *)(head)) \
667 672 ? ((head)->cqh_first) \
668 673 : (elm->field.cqe_next))
669 674 #define CIRCLEQ_LOOP_PREV(head, elm, field) \
670 675 (((elm)->field.cqe_prev == (void *)(head)) \
671 676 ? ((head)->cqh_last) \
672 677 : (elm->field.cqe_prev))
673 678
674 679 #ifdef __cplusplus
675 680 }
676 681 #endif
677 682
678 683 #endif /* !_SYS_QUEUE_H */
|
↓ open down ↓ |
331 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX