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