2
* Copyright (c) 1991, 1993
3
* The Regents of the University of California. All rights reserved.
5
* Redistribution and use in source and binary forms, with or without
6
* modification, are permitted provided that the following conditions
8
* 1. Redistributions of source code must retain the above copyright
9
* notice, this list of conditions and the following disclaimer.
10
* 2. Redistributions in binary form must reproduce the above copyright
11
* notice, this list of conditions and the following disclaimer in the
12
* documentation and/or other materials provided with the distribution.
14
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
15
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
18
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26
* @(#)queue.h 8.5 (Berkeley) 8/20/94
27
* $FreeBSD: src/sys/sys/queue.h,v 1.38 2000/05/26 02:06:56 jake Exp $
34
* This file defines five types of data structures: singly-linked lists,
35
* singly-linked tail queues, lists, tail queues, and circular queues.
37
* A singly-linked list is headed by a single forward pointer. The elements
38
* are singly linked for minimum space and pointer manipulation overhead at
39
* the expense of O(n) removal for arbitrary elements. New elements can be
40
* added to the list after an existing element or at the head of the list.
41
* Elements being removed from the head of the list should use the explicit
42
* macro for this purpose for optimum efficiency. A singly-linked list may
43
* only be traversed in the forward direction. Singly-linked lists are ideal
44
* for applications with large datasets and few or no removals or for
45
* implementing a LIFO queue.
47
* A singly-linked tail queue is headed by a pair of pointers, one to the
48
* head of the list and the other to the tail of the list. The elements are
49
* singly linked for minimum space and pointer manipulation overhead at the
50
* expense of O(n) removal for arbitrary elements. New elements can be added
51
* to the list after an existing element, at the head of the list, or at the
52
* end of the list. Elements being removed from the head of the tail queue
53
* should use the explicit macro for this purpose for optimum efficiency.
54
* A singly-linked tail queue may only be traversed in the forward direction.
55
* Singly-linked tail queues are ideal for applications with large datasets
56
* and few or no removals or for implementing a FIFO queue.
58
* A list is headed by a single forward pointer (or an array of forward
59
* pointers for a hash table header). The elements are doubly linked
60
* so that an arbitrary element can be removed without a need to
61
* traverse the list. New elements can be added to the list before
62
* or after an existing element or at the head of the list. A list
63
* may only be traversed in the forward direction.
65
* A tail queue is headed by a pair of pointers, one to the head of the
66
* list and the other to the tail of the list. The elements are doubly
67
* linked 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 or
69
* after an existing element, at the head of the list, or at the end of
70
* the list. A tail queue may be traversed in either direction.
72
* A circle 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 after
76
* an existing element, at the head of the list, or at the end of the list.
77
* A circle queue may be traversed in either direction, but has a more
78
* complex end of list detection.
80
* For details on the use of these macros, see the queue(3) manual page.
83
* SLIST LIST STAILQ TAILQ CIRCLEQ
85
* _HEAD_INITIALIZER + + + + +
94
* _FOREACH_REVERSE - - - + +
95
* _INSERT_HEAD + + + + +
96
* _INSERT_BEFORE - + - + +
97
* _INSERT_AFTER + + + + +
98
* _INSERT_TAIL - - + + +
99
* _REMOVE_HEAD + - + - -
105
* Singly-linked List declarations.
107
#define SLIST_HEAD(name, type) \
109
struct type *slh_first; /* first element */ \
112
#define SLIST_HEAD_INITIALIZER(head) \
115
#define SLIST_ENTRY(type) \
117
struct type *sle_next; /* next element */ \
121
* Singly-linked List functions.
123
#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
125
#define SLIST_FIRST(head) ((head)->slh_first)
127
#define SLIST_FOREACH(var, head, field) \
128
for ((var) = SLIST_FIRST((head)); \
130
(var) = SLIST_NEXT((var), field))
132
#define SLIST_INIT(head) do { \
133
SLIST_FIRST((head)) = NULL; \
136
#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
137
SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
138
SLIST_NEXT((slistelm), field) = (elm); \
141
#define SLIST_INSERT_HEAD(head, elm, field) do { \
142
SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
143
SLIST_FIRST((head)) = (elm); \
146
#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
148
#define SLIST_REMOVE(head, elm, type, field) do { \
149
if (SLIST_FIRST((head)) == (elm)) { \
150
SLIST_REMOVE_HEAD((head), field); \
153
struct type *curelm = SLIST_FIRST((head)); \
154
while (SLIST_NEXT(curelm, field) != (elm)) \
155
curelm = SLIST_NEXT(curelm, field); \
156
SLIST_NEXT(curelm, field) = \
157
SLIST_NEXT(SLIST_NEXT(curelm, field), field); \
161
#define SLIST_REMOVE_HEAD(head, field) do { \
162
SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \
166
* Singly-linked Tail queue declarations.
168
#define STAILQ_HEAD(name, type) \
170
struct type *stqh_first;/* first element */ \
171
struct type **stqh_last;/* addr of last next element */ \
174
#define STAILQ_HEAD_INITIALIZER(head) \
175
{ NULL, &(head).stqh_first }
177
#define STAILQ_ENTRY(type) \
179
struct type *stqe_next; /* next element */ \
183
* Singly-linked Tail queue functions.
185
#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
187
#define STAILQ_FIRST(head) ((head)->stqh_first)
189
#define STAILQ_FOREACH(var, head, field) \
190
for((var) = STAILQ_FIRST((head)); \
192
(var) = STAILQ_NEXT((var), field))
194
#define STAILQ_INIT(head) do { \
195
STAILQ_FIRST((head)) = NULL; \
196
(head)->stqh_last = &STAILQ_FIRST((head)); \
199
#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
200
if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
201
(head)->stqh_last = &STAILQ_NEXT((elm), field); \
202
STAILQ_NEXT((tqelm), field) = (elm); \
205
#define STAILQ_INSERT_HEAD(head, elm, field) do { \
206
if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
207
(head)->stqh_last = &STAILQ_NEXT((elm), field); \
208
STAILQ_FIRST((head)) = (elm); \
211
#define STAILQ_INSERT_TAIL(head, elm, field) do { \
212
STAILQ_NEXT((elm), field) = NULL; \
213
STAILQ_LAST((head)) = (elm); \
214
(head)->stqh_last = &STAILQ_NEXT((elm), field); \
217
#define STAILQ_LAST(head) (*(head)->stqh_last)
219
#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
221
#define STAILQ_REMOVE(head, elm, type, field) do { \
222
if (STAILQ_FIRST((head)) == (elm)) { \
223
STAILQ_REMOVE_HEAD(head, field); \
226
struct type *curelm = STAILQ_FIRST((head)); \
227
while (STAILQ_NEXT(curelm, field) != (elm)) \
228
curelm = STAILQ_NEXT(curelm, field); \
229
if ((STAILQ_NEXT(curelm, field) = \
230
STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\
231
(head)->stqh_last = &STAILQ_NEXT((curelm), field);\
235
#define STAILQ_REMOVE_HEAD(head, field) do { \
236
if ((STAILQ_FIRST((head)) = \
237
STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \
238
(head)->stqh_last = &STAILQ_FIRST((head)); \
241
#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \
242
if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \
243
(head)->stqh_last = &STAILQ_FIRST((head)); \
249
#define LIST_HEAD(name, type) \
251
struct type *lh_first; /* first element */ \
254
#define LIST_HEAD_INITIALIZER(head) \
257
#define LIST_ENTRY(type) \
259
struct type *le_next; /* next element */ \
260
struct type **le_prev; /* address of previous next element */ \
267
#define LIST_EMPTY(head) ((head)->lh_first == NULL)
269
#define LIST_FIRST(head) ((head)->lh_first)
271
#define LIST_FOREACH(var, head, field) \
272
for ((var) = LIST_FIRST((head)); \
274
(var) = LIST_NEXT((var), field))
276
#define LIST_INIT(head) do { \
277
LIST_FIRST((head)) = NULL; \
280
#define LIST_INSERT_AFTER(listelm, elm, field) do { \
281
if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
282
LIST_NEXT((listelm), field)->field.le_prev = \
283
&LIST_NEXT((elm), field); \
284
LIST_NEXT((listelm), field) = (elm); \
285
(elm)->field.le_prev = &LIST_NEXT((listelm), field); \
288
#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
289
(elm)->field.le_prev = (listelm)->field.le_prev; \
290
LIST_NEXT((elm), field) = (listelm); \
291
*(listelm)->field.le_prev = (elm); \
292
(listelm)->field.le_prev = &LIST_NEXT((elm), field); \
295
#define LIST_INSERT_HEAD(head, elm, field) do { \
296
if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
297
LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
298
LIST_FIRST((head)) = (elm); \
299
(elm)->field.le_prev = &LIST_FIRST((head)); \
302
#define LIST_NEXT(elm, field) ((elm)->field.le_next)
304
#define LIST_REMOVE(elm, field) do { \
305
if (LIST_NEXT((elm), field) != NULL) \
306
LIST_NEXT((elm), field)->field.le_prev = \
307
(elm)->field.le_prev; \
308
*(elm)->field.le_prev = LIST_NEXT((elm), field); \
312
* Tail queue declarations.
314
#define TAILQ_HEAD(name, type) \
316
struct type *tqh_first; /* first element */ \
317
struct type **tqh_last; /* addr of last next element */ \
320
#define TAILQ_HEAD_INITIALIZER(head) \
321
{ NULL, &(head).tqh_first }
323
#define TAILQ_ENTRY(type) \
325
struct type *tqe_next; /* next element */ \
326
struct type **tqe_prev; /* address of previous next element */ \
330
* Tail queue functions.
332
#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
334
#define TAILQ_FIRST(head) ((head)->tqh_first)
336
#define TAILQ_FOREACH(var, head, field) \
337
for ((var) = TAILQ_FIRST((head)); \
339
(var) = TAILQ_NEXT((var), field))
341
#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
342
for ((var) = TAILQ_LAST((head), headname); \
344
(var) = TAILQ_PREV((var), headname, field))
346
#define TAILQ_INIT(head) do { \
347
TAILQ_FIRST((head)) = NULL; \
348
(head)->tqh_last = &TAILQ_FIRST((head)); \
351
#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
352
if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
353
TAILQ_NEXT((elm), field)->field.tqe_prev = \
354
&TAILQ_NEXT((elm), field); \
356
(head)->tqh_last = &TAILQ_NEXT((elm), field); \
357
TAILQ_NEXT((listelm), field) = (elm); \
358
(elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
361
#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
362
(elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
363
TAILQ_NEXT((elm), field) = (listelm); \
364
*(listelm)->field.tqe_prev = (elm); \
365
(listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
368
#define TAILQ_INSERT_HEAD(head, elm, field) do { \
369
if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
370
TAILQ_FIRST((head))->field.tqe_prev = \
371
&TAILQ_NEXT((elm), field); \
373
(head)->tqh_last = &TAILQ_NEXT((elm), field); \
374
TAILQ_FIRST((head)) = (elm); \
375
(elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
378
#define TAILQ_INSERT_TAIL(head, elm, field) do { \
379
TAILQ_NEXT((elm), field) = NULL; \
380
(elm)->field.tqe_prev = (head)->tqh_last; \
381
*(head)->tqh_last = (elm); \
382
(head)->tqh_last = &TAILQ_NEXT((elm), field); \
385
#define TAILQ_LAST(head, headname) \
386
(*(((struct headname *)((head)->tqh_last))->tqh_last))
388
#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
390
#define TAILQ_PREV(elm, headname, field) \
391
(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
393
#define TAILQ_REMOVE(head, elm, field) do { \
394
if ((TAILQ_NEXT((elm), field)) != NULL) \
395
TAILQ_NEXT((elm), field)->field.tqe_prev = \
396
(elm)->field.tqe_prev; \
398
(head)->tqh_last = (elm)->field.tqe_prev; \
399
*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
403
* Circular queue declarations.
405
#define CIRCLEQ_HEAD(name, type) \
407
struct type *cqh_first; /* first element */ \
408
struct type *cqh_last; /* last element */ \
411
#define CIRCLEQ_HEAD_INITIALIZER(head) \
412
{ (void *)&(head), (void *)&(head) }
414
#define CIRCLEQ_ENTRY(type) \
416
struct type *cqe_next; /* next element */ \
417
struct type *cqe_prev; /* previous element */ \
421
* Circular queue functions.
423
#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
425
#define CIRCLEQ_FIRST(head) ((head)->cqh_first)
427
#define CIRCLEQ_FOREACH(var, head, field) \
428
for ((var) = CIRCLEQ_FIRST((head)); \
429
(var) != (void *)(head); \
430
(var) = CIRCLEQ_NEXT((var), field))
432
#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
433
for ((var) = CIRCLEQ_LAST((head)); \
434
(var) != (void *)(head); \
435
(var) = CIRCLEQ_PREV((var), field))
437
#define CIRCLEQ_INIT(head) do { \
438
CIRCLEQ_FIRST((head)) = (void *)(head); \
439
CIRCLEQ_LAST((head)) = (void *)(head); \
442
#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
443
CIRCLEQ_NEXT((elm), field) = CIRCLEQ_NEXT((listelm), field); \
444
CIRCLEQ_PREV((elm), field) = (listelm); \
445
if (CIRCLEQ_NEXT((listelm), field) == (void *)(head)) \
446
CIRCLEQ_LAST((head)) = (elm); \
448
CIRCLEQ_PREV(CIRCLEQ_NEXT((listelm), field), field) = (elm);\
449
CIRCLEQ_NEXT((listelm), field) = (elm); \
452
#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
453
CIRCLEQ_NEXT((elm), field) = (listelm); \
454
CIRCLEQ_PREV((elm), field) = CIRCLEQ_PREV((listelm), field); \
455
if (CIRCLEQ_PREV((listelm), field) == (void *)(head)) \
456
CIRCLEQ_FIRST((head)) = (elm); \
458
CIRCLEQ_NEXT(CIRCLEQ_PREV((listelm), field), field) = (elm);\
459
CIRCLEQ_PREV((listelm), field) = (elm); \
462
#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
463
CIRCLEQ_NEXT((elm), field) = CIRCLEQ_FIRST((head)); \
464
CIRCLEQ_PREV((elm), field) = (void *)(head); \
465
if (CIRCLEQ_LAST((head)) == (void *)(head)) \
466
CIRCLEQ_LAST((head)) = (elm); \
468
CIRCLEQ_PREV(CIRCLEQ_FIRST((head)), field) = (elm); \
469
CIRCLEQ_FIRST((head)) = (elm); \
472
#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
473
CIRCLEQ_NEXT((elm), field) = (void *)(head); \
474
CIRCLEQ_PREV((elm), field) = CIRCLEQ_LAST((head)); \
475
if (CIRCLEQ_FIRST((head)) == (void *)(head)) \
476
CIRCLEQ_FIRST((head)) = (elm); \
478
CIRCLEQ_NEXT(CIRCLEQ_LAST((head)), field) = (elm); \
479
CIRCLEQ_LAST((head)) = (elm); \
482
#define CIRCLEQ_LAST(head) ((head)->cqh_last)
484
#define CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next)
486
#define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev)
488
#define CIRCLEQ_REMOVE(head, elm, field) do { \
489
if (CIRCLEQ_NEXT((elm), field) == (void *)(head)) \
490
CIRCLEQ_LAST((head)) = CIRCLEQ_PREV((elm), field); \
492
CIRCLEQ_PREV(CIRCLEQ_NEXT((elm), field), field) = \
493
CIRCLEQ_PREV((elm), field); \
494
if (CIRCLEQ_PREV((elm), field) == (void *)(head)) \
495
CIRCLEQ_FIRST((head)) = CIRCLEQ_NEXT((elm), field); \
497
CIRCLEQ_NEXT(CIRCLEQ_PREV((elm), field), field) = \
498
CIRCLEQ_NEXT((elm), field); \
501
#endif /* !_SYS_QUEUE_H_ */