1 /* SPDX-License-Identifier: BSD-3-Clause
3 * Copyright (c) 1991, 1993
4 * The Regents of the University of California. All rights reserved.
11 * This file defines tail queues.
13 * A tail queue is headed by a pair of pointers, one to the head of the
14 * list and the other to the tail of the list. The elements are doubly
15 * linked so that an arbitrary element can be removed without a need to
16 * traverse the list. New elements can be added to the list before or
17 * after an existing element, at the head of the list, or at the end of
18 * the list. A tail queue may be traversed in either direction.
20 * Below is a summary of implemented functions where:
21 * + means the macro is available
22 * - means the macro is not available
23 * s means the macro is available but is slow (runs in O(n) time)
41 * _FOREACH_FROM_SAFE +
43 * _FOREACH_REVERSE_FROM +
44 * _FOREACH_REVERSE_SAFE +
45 * _FOREACH_REVERSE_FROM_SAFE +
62 #define QMD_TRACE_ELEM(elem)
63 #define QMD_TRACE_HEAD(head)
65 #define TRACEBUF_INITIALIZER
68 #define QMD_IS_TRASHED(x) 0
70 #define QMD_SAVELINK(name, link)
74 * In C++ there can be structure lists and class lists:
76 #define QUEUE_TYPEOF(type) type
78 #define QUEUE_TYPEOF(type) struct type
82 * Tail queue declarations.
84 #define TAILQ_HEAD(name, type) \
86 struct type *tqh_first; /* first element */ \
87 struct type **tqh_last; /* addr of last next element */ \
91 #define TAILQ_CLASS_HEAD(name, type) \
93 class type *tqh_first; /* first element */ \
94 class type **tqh_last; /* addr of last next element */ \
98 #define TAILQ_HEAD_INITIALIZER(head) \
99 { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER }
101 #define TAILQ_ENTRY(type) \
103 struct type *tqe_next; /* next element */ \
104 struct type **tqe_prev; /* address of previous next element */ \
108 #define TAILQ_CLASS_ENTRY(type) \
110 class type *tqe_next; /* next element */ \
111 class type **tqe_prev; /* address of previous next element */ \
116 * Tail queue functions.
118 #define QMD_TAILQ_CHECK_HEAD(head, field)
119 #define QMD_TAILQ_CHECK_TAIL(head, headname)
120 #define QMD_TAILQ_CHECK_NEXT(elm, field)
121 #define QMD_TAILQ_CHECK_PREV(elm, field)
123 #define TAILQ_CONCAT(head1, head2, field) do { \
124 if (!TAILQ_EMPTY(head2)) { \
125 *(head1)->tqh_last = (head2)->tqh_first; \
126 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
127 (head1)->tqh_last = (head2)->tqh_last; \
128 TAILQ_INIT((head2)); \
129 QMD_TRACE_HEAD(head1); \
130 QMD_TRACE_HEAD(head2); \
134 #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
136 #define TAILQ_FIRST(head) ((head)->tqh_first)
138 #define TAILQ_FOREACH(var, head, field) \
139 for ((var) = TAILQ_FIRST((head)); \
141 (var) = TAILQ_NEXT((var), field))
143 #define TAILQ_FOREACH_FROM(var, head, field) \
144 for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \
146 (var) = TAILQ_NEXT((var), field))
148 #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
149 for ((var) = TAILQ_FIRST((head)); \
150 (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
153 #define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \
154 for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \
155 (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
158 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
159 for ((var) = TAILQ_LAST((head), headname); \
161 (var) = TAILQ_PREV((var), headname, field))
163 #define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \
164 for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \
166 (var) = TAILQ_PREV((var), headname, field))
168 #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
169 for ((var) = TAILQ_LAST((head), headname); \
170 (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
173 #define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \
174 for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \
175 (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
178 #define TAILQ_INIT(head) do { \
179 TAILQ_FIRST((head)) = NULL; \
180 (head)->tqh_last = &TAILQ_FIRST((head)); \
181 QMD_TRACE_HEAD(head); \
184 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
185 QMD_TAILQ_CHECK_NEXT(listelm, field); \
186 TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field); \
187 if (TAILQ_NEXT((listelm), field) != NULL) \
188 TAILQ_NEXT((elm), field)->field.tqe_prev = \
189 &TAILQ_NEXT((elm), field); \
191 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
192 QMD_TRACE_HEAD(head); \
194 TAILQ_NEXT((listelm), field) = (elm); \
195 (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
196 QMD_TRACE_ELEM(&(elm)->field); \
197 QMD_TRACE_ELEM(&(listelm)->field); \
200 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
201 QMD_TAILQ_CHECK_PREV(listelm, field); \
202 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
203 TAILQ_NEXT((elm), field) = (listelm); \
204 *(listelm)->field.tqe_prev = (elm); \
205 (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
206 QMD_TRACE_ELEM(&(elm)->field); \
207 QMD_TRACE_ELEM(&(listelm)->field); \
210 #define TAILQ_INSERT_HEAD(head, elm, field) do { \
211 QMD_TAILQ_CHECK_HEAD(head, field); \
212 TAILQ_NEXT((elm), field) = TAILQ_FIRST((head)); \
213 if (TAILQ_FIRST((head)) != NULL) \
214 TAILQ_FIRST((head))->field.tqe_prev = \
215 &TAILQ_NEXT((elm), field); \
217 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
218 TAILQ_FIRST((head)) = (elm); \
219 (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
220 QMD_TRACE_HEAD(head); \
221 QMD_TRACE_ELEM(&(elm)->field); \
224 #define TAILQ_INSERT_TAIL(head, elm, field) do { \
225 QMD_TAILQ_CHECK_TAIL(head, field); \
226 TAILQ_NEXT((elm), field) = NULL; \
227 (elm)->field.tqe_prev = (head)->tqh_last; \
228 *(head)->tqh_last = (elm); \
229 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
230 QMD_TRACE_HEAD(head); \
231 QMD_TRACE_ELEM(&(elm)->field); \
234 #define TAILQ_LAST(head, headname) \
235 (*(((struct headname *)((head)->tqh_last))->tqh_last))
238 * The FAST function is fast in that it causes no data access other
239 * then the access to the head. The standard LAST function above
240 * will cause a data access of both the element you want and
241 * the previous element. FAST is very useful for instances when
242 * you may want to prefetch the last data element.
244 #define TAILQ_LAST_FAST(head, type, field) \
245 (TAILQ_EMPTY(head) ? NULL : __containerof((head)->tqh_last, \
246 QUEUE_TYPEOF(type), field.tqe_next))
248 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
250 #define TAILQ_PREV(elm, headname, field) \
251 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
253 #define TAILQ_REMOVE(head, elm, field) do { \
254 QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \
255 QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \
256 QMD_TAILQ_CHECK_NEXT(elm, field); \
257 QMD_TAILQ_CHECK_PREV(elm, field); \
258 if ((TAILQ_NEXT((elm), field)) != NULL) \
259 TAILQ_NEXT((elm), field)->field.tqe_prev = \
260 (elm)->field.tqe_prev; \
262 (head)->tqh_last = (elm)->field.tqe_prev; \
263 QMD_TRACE_HEAD(head); \
265 *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
268 QMD_TRACE_ELEM(&(elm)->field); \
271 #define TAILQ_SWAP(head1, head2, type, field) do { \
272 QUEUE_TYPEOF(type) * swap_first = (head1)->tqh_first; \
273 QUEUE_TYPEOF(type) * *swap_last = (head1)->tqh_last; \
274 (head1)->tqh_first = (head2)->tqh_first; \
275 (head1)->tqh_last = (head2)->tqh_last; \
276 (head2)->tqh_first = swap_first; \
277 (head2)->tqh_last = swap_last; \
278 swap_first = (head1)->tqh_first; \
279 if (swap_first != NULL) \
280 swap_first->field.tqe_prev = &(head1)->tqh_first; \
282 (head1)->tqh_last = &(head1)->tqh_first; \
283 swap_first = (head2)->tqh_first; \
284 if (swap_first != NULL) \
285 swap_first->field.tqe_prev = &(head2)->tqh_first; \
287 (head2)->tqh_last = &(head2)->tqh_first; \
294 #endif /* _SYS_QUEUE_H_ */