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