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 +
65 #define LIST_HEAD(name, type) \
67 struct type *lh_first; /* first element */ \
70 #define QMD_TRACE_ELEM(elem)
71 #define QMD_TRACE_HEAD(head)
73 #define TRACEBUF_INITIALIZER
76 #define QMD_IS_TRASHED(x) 0
78 #define QMD_SAVELINK(name, link)
82 * In C++ there can be structure lists and class lists:
84 #define QUEUE_TYPEOF(type) type
86 #define QUEUE_TYPEOF(type) struct type
90 * Tail queue declarations.
92 #define TAILQ_HEAD(name, type) \
94 struct type *tqh_first; /* first element */ \
95 struct type **tqh_last; /* addr of last next element */ \
99 #define TAILQ_CLASS_HEAD(name, type) \
101 class type *tqh_first; /* first element */ \
102 class type **tqh_last; /* addr of last next element */ \
106 #define TAILQ_HEAD_INITIALIZER(head) \
107 { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER }
109 #define TAILQ_ENTRY(type) \
111 struct type *tqe_next; /* next element */ \
112 struct type **tqe_prev; /* address of previous next element */ \
116 #define TAILQ_CLASS_ENTRY(type) \
118 class type *tqe_next; /* next element */ \
119 class type **tqe_prev; /* address of previous next element */ \
124 * Tail queue functions.
126 #define QMD_TAILQ_CHECK_HEAD(head, field)
127 #define QMD_TAILQ_CHECK_TAIL(head, headname)
128 #define QMD_TAILQ_CHECK_NEXT(elm, field)
129 #define QMD_TAILQ_CHECK_PREV(elm, field)
131 #define TAILQ_CONCAT(head1, head2, field) do { \
132 if (!TAILQ_EMPTY(head2)) { \
133 *(head1)->tqh_last = (head2)->tqh_first; \
134 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
135 (head1)->tqh_last = (head2)->tqh_last; \
136 TAILQ_INIT((head2)); \
137 QMD_TRACE_HEAD(head1); \
138 QMD_TRACE_HEAD(head2); \
142 #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
144 #define TAILQ_FIRST(head) ((head)->tqh_first)
146 #define TAILQ_FOREACH(var, head, field) \
147 for ((var) = TAILQ_FIRST((head)); \
149 (var) = TAILQ_NEXT((var), field))
151 #define TAILQ_FOREACH_FROM(var, head, field) \
152 for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \
154 (var) = TAILQ_NEXT((var), field))
156 #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
157 for ((var) = TAILQ_FIRST((head)); \
158 (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
161 #define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \
162 for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \
163 (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
166 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
167 for ((var) = TAILQ_LAST((head), headname); \
169 (var) = TAILQ_PREV((var), headname, field))
171 #define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \
172 for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \
174 (var) = TAILQ_PREV((var), headname, field))
176 #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
177 for ((var) = TAILQ_LAST((head), headname); \
178 (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
181 #define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \
182 for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \
183 (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
186 #define TAILQ_INIT(head) do { \
187 TAILQ_FIRST((head)) = NULL; \
188 (head)->tqh_last = &TAILQ_FIRST((head)); \
189 QMD_TRACE_HEAD(head); \
192 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
193 QMD_TAILQ_CHECK_NEXT(listelm, field); \
194 TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field); \
195 if (TAILQ_NEXT((listelm), field) != NULL) \
196 TAILQ_NEXT((elm), field)->field.tqe_prev = \
197 &TAILQ_NEXT((elm), field); \
199 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
200 QMD_TRACE_HEAD(head); \
202 TAILQ_NEXT((listelm), field) = (elm); \
203 (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
204 QMD_TRACE_ELEM(&(elm)->field); \
205 QMD_TRACE_ELEM(&(listelm)->field); \
208 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
209 QMD_TAILQ_CHECK_PREV(listelm, field); \
210 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
211 TAILQ_NEXT((elm), field) = (listelm); \
212 *(listelm)->field.tqe_prev = (elm); \
213 (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
214 QMD_TRACE_ELEM(&(elm)->field); \
215 QMD_TRACE_ELEM(&(listelm)->field); \
218 #define TAILQ_INSERT_HEAD(head, elm, field) do { \
219 QMD_TAILQ_CHECK_HEAD(head, field); \
220 TAILQ_NEXT((elm), field) = TAILQ_FIRST((head)); \
221 if (TAILQ_FIRST((head)) != NULL) \
222 TAILQ_FIRST((head))->field.tqe_prev = \
223 &TAILQ_NEXT((elm), field); \
225 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
226 TAILQ_FIRST((head)) = (elm); \
227 (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
228 QMD_TRACE_HEAD(head); \
229 QMD_TRACE_ELEM(&(elm)->field); \
232 #define TAILQ_INSERT_TAIL(head, elm, field) do { \
233 QMD_TAILQ_CHECK_TAIL(head, field); \
234 TAILQ_NEXT((elm), field) = NULL; \
235 (elm)->field.tqe_prev = (head)->tqh_last; \
236 *(head)->tqh_last = (elm); \
237 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
238 QMD_TRACE_HEAD(head); \
239 QMD_TRACE_ELEM(&(elm)->field); \
242 #define TAILQ_LAST(head, headname) \
243 (*(((struct headname *)((head)->tqh_last))->tqh_last))
246 * The FAST function is fast in that it causes no data access other
247 * then the access to the head. The standard LAST function above
248 * will cause a data access of both the element you want and
249 * the previous element. FAST is very useful for instances when
250 * you may want to prefetch the last data element.
252 #define TAILQ_LAST_FAST(head, type, field) \
253 (TAILQ_EMPTY(head) ? NULL : __containerof((head)->tqh_last, \
254 QUEUE_TYPEOF(type), field.tqe_next))
256 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
258 #define TAILQ_PREV(elm, headname, field) \
259 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
261 #define TAILQ_REMOVE(head, elm, field) do { \
262 QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \
263 QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \
264 QMD_TAILQ_CHECK_NEXT(elm, field); \
265 QMD_TAILQ_CHECK_PREV(elm, field); \
266 if ((TAILQ_NEXT((elm), field)) != NULL) \
267 TAILQ_NEXT((elm), field)->field.tqe_prev = \
268 (elm)->field.tqe_prev; \
270 (head)->tqh_last = (elm)->field.tqe_prev; \
271 QMD_TRACE_HEAD(head); \
273 *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
276 QMD_TRACE_ELEM(&(elm)->field); \
279 #define TAILQ_SWAP(head1, head2, type, field) do { \
280 QUEUE_TYPEOF(type) * swap_first = (head1)->tqh_first; \
281 QUEUE_TYPEOF(type) * *swap_last = (head1)->tqh_last; \
282 (head1)->tqh_first = (head2)->tqh_first; \
283 (head1)->tqh_last = (head2)->tqh_last; \
284 (head2)->tqh_first = swap_first; \
285 (head2)->tqh_last = swap_last; \
286 swap_first = (head1)->tqh_first; \
287 if (swap_first != NULL) \
288 swap_first->field.tqe_prev = &(head1)->tqh_first; \
290 (head1)->tqh_last = &(head1)->tqh_first; \
291 swap_first = (head2)->tqh_first; \
292 if (swap_first != NULL) \
293 swap_first->field.tqe_prev = &(head2)->tqh_first; \
295 (head2)->tqh_last = &(head2)->tqh_first; \
302 #endif /* _SYS_QUEUE_H_ */