1/* $NetBSD: gcq.h,v 1.2 2007/08/19 07:35:32 kiyohara Exp $ */
2/*
3 * Not (c) 2007 Matthew Orgass
4 * This file is public domain, meaning anyone can make any use of part or all
5 * of this file including copying into other works without credit. Any use,
6 * modified or not, is solely the responsibility of the user. If this file is
7 * part of a collection then use in the collection is governed by the terms of
8 * the collection.
9 */
10
11/*
12 * Generic Circular Queues: Pointer arithmetic is used to recover the
13 * enclosing object. Merge operation is provided. Items can be multiply
14 * removed, but queue traversal requires separate knowledge of the queue head.
15 */
16
17#ifndef _GCQ_H
18#define _GCQ_H
19
20#ifdef _KERNEL
21#include <sys/types.h>
22#include <sys/null.h>
23#include <lib/libkern/libkern.h>
24#else
25#include <stdbool.h>
26#include <stdint.h>
27#include <stddef.h>
28#include <assert.h>
29#endif
30
31#ifdef GCQ_USE_ASSERT
32#define GCQ_ASSERT(x) assert(x)
33#else
34#ifdef _KERNEL
35#define GCQ_ASSERT(x) KASSERT(x)
36#else
37#define GCQ_ASSERT(x) _DIAGASSERT(x)
38#endif
39#endif
40
41struct gcq {
42 struct gcq *q_next;
43 struct gcq *q_prev;
44};
45
46struct gcq_head {
47 struct gcq hq;
48};
49
50#define GCQ_INIT(q) { &(q), &(q) }
51#define GCQ_INIT_HEAD(head) { GCQ_INIT((head).hq) }
52
53__attribute__((nonnull, always_inline)) static inline void
54gcq_init(struct gcq *q)
55{
56 q->q_next = q->q_prev = q;
57}
58
59__attribute__((nonnull, const, warn_unused_result, always_inline))
60static inline struct gcq *
61gcq_q(struct gcq *q)
62{
63 return q;
64}
65
66__attribute__((nonnull, const, warn_unused_result, always_inline))
67static inline struct gcq *
68gcq_hq(struct gcq_head *head)
69{
70 return (struct gcq *)head;
71}
72
73__attribute__((nonnull, const, warn_unused_result, always_inline))
74static inline struct gcq_head *
75gcq_head(struct gcq *q)
76{
77 return (struct gcq_head *)q;
78}
79
80__attribute__((nonnull, always_inline)) static inline void
81gcq_init_head(struct gcq_head *head)
82{
83 gcq_init(gcq_hq(head));
84}
85
86__attribute__((nonnull, pure, warn_unused_result, always_inline))
87static inline bool
88gcq_onlist(struct gcq *q)
89{
90 return (q->q_next != q);
91}
92
93__attribute__((nonnull, pure, warn_unused_result, always_inline))
94static inline bool
95gcq_empty(struct gcq_head *head)
96{
97 return (!gcq_onlist(gcq_hq(head)));
98}
99
100__attribute__((nonnull, pure, warn_unused_result, always_inline))
101static inline bool
102gcq_linked(struct gcq *prev, struct gcq *next)
103{
104 return (prev->q_next == next && next->q_prev == prev);
105}
106
107__attribute__((nonnull, always_inline)) static inline void
108gcq_insert_after(struct gcq *on, struct gcq *off)
109{
110 struct gcq *on_next;
111 GCQ_ASSERT(off->q_next == off && off->q_prev == off);
112 on_next = on->q_next;
113
114 off->q_prev = on;
115 off->q_next = on_next;
116 on_next->q_prev = off;
117 on->q_next = off;
118}
119
120__attribute__((nonnull)) static inline void
121gcq_insert_before(struct gcq *on, struct gcq *off)
122{
123 struct gcq *on_prev;
124 GCQ_ASSERT(off->q_next == off && off->q_prev == off);
125 on_prev = on->q_prev;
126
127 off->q_next = on;
128 off->q_prev = on_prev;
129 on_prev->q_next = off;
130 on->q_prev = off;
131}
132
133__attribute__((nonnull, always_inline)) static inline void
134gcq_insert_head(struct gcq_head *head, struct gcq *q)
135{
136 gcq_insert_after(gcq_hq(head), q);
137}
138
139__attribute__((nonnull, always_inline)) static inline void
140gcq_insert_tail(struct gcq_head *head, struct gcq *q)
141{
142 gcq_insert_before(gcq_hq(head), q);
143}
144
145__attribute__((nonnull)) static inline void
146gcq_tie(struct gcq *dst, struct gcq *src)
147{
148 struct gcq *dst_next, *src_prev;
149 dst_next = dst->q_next;
150 src_prev = src->q_prev;
151
152 src_prev->q_next = dst_next;
153 dst_next->q_prev = src_prev;
154 src->q_prev = dst;
155 dst->q_next = src;
156}
157
158__attribute__((nonnull, always_inline)) static inline void
159gcq_tie_after(struct gcq *dst, struct gcq *src)
160{
161 GCQ_ASSERT(dst != src && dst->q_prev != src);
162 gcq_tie(dst, src);
163}
164
165__attribute__((nonnull, always_inline)) static inline void
166gcq_tie_before(struct gcq *dst, struct gcq *src)
167{
168 gcq_tie_after(dst->q_prev, src);
169}
170
171__attribute__((nonnull)) static inline struct gcq *
172gcq_remove(struct gcq *q)
173{
174 struct gcq *next, *prev;
175 next = q->q_next;
176 prev = q->q_prev;
177
178 prev->q_next = next;
179 next->q_prev = prev;
180 gcq_init(q);
181 return q;
182}
183
184#ifdef GCQ_UNCONDITIONAL_MERGE
185__attribute__((nonnull)) static inline void
186gcq_merge(struct gcq *dst, struct gcq *src)
187{
188 GCQ_ASSERT(dst != src && dst->q_prev != src);
189 gcq_tie(dst, src);
190 gcq_tie(src, src);
191}
192
193__attribute__((nonnull, always_inline)) static inline void
194gcq_merge_head(struct gcq_head *dst, struct gcq_head *src)
195{
196 gcq_merge(gcq_hq(dst), gcq_hq(src));
197}
198
199__attribute__((nonnull, always_inline)) static inline void
200gcq_merge_tail(struct gcq_head *dst, struct gcq_head *src)
201{
202 gcq_merge(gcq_hq(dst)->q_prev, gcq_hq(src));
203}
204#else
205__attribute__((nonnull)) static inline void
206gcq_merge(struct gcq *dst, struct gcq *src)
207{
208 struct gcq *dst_next, *src_prev, *src_next;
209 GCQ_ASSERT(dst != src && dst->q_prev != src);
210
211 if (gcq_onlist(src)) {
212 dst_next = dst->q_next;
213 src_prev = src->q_prev;
214 src_next = src->q_next;
215
216 dst_next->q_prev = src_prev;
217 src_prev->q_next = dst_next;
218 dst->q_next = src_next;
219 src_next->q_prev = dst;
220 gcq_init(src);
221 }
222}
223
224__attribute__((nonnull, always_inline)) static inline void
225gcq_merge_head(struct gcq_head *dst, struct gcq_head *src)
226{
227 gcq_merge(gcq_hq(dst), gcq_hq(src));
228}
229
230__attribute__((nonnull, always_inline)) static inline void
231gcq_merge_tail(struct gcq_head *dst, struct gcq_head *src)
232{
233 gcq_merge(gcq_hq(dst)->q_prev, gcq_hq(src));
234}
235#endif
236
237__attribute__((nonnull)) static inline void
238gcq_clear(struct gcq *q)
239{
240 struct gcq *nq, *next;
241 nq=q;
242 do {
243 next = nq->q_next;
244 gcq_init(nq);
245 nq = next;
246 } while (next != q);
247}
248
249__attribute__((nonnull, always_inline)) static inline void
250gcq_remove_all(struct gcq_head *head)
251{
252 gcq_clear(gcq_hq(head));
253}
254
255__attribute__((nonnull, always_inline)) static inline struct gcq *
256_gcq_next(struct gcq *current, struct gcq_head *head, struct gcq *start)
257{
258 struct gcq *q, *hq;
259 hq = gcq_hq(head);
260 q = current->q_next;
261 if (hq != start && q == hq)
262 q = hq->q_next;
263 if (current != start)
264 GCQ_ASSERT(gcq_onlist(current));
265 return q;
266}
267
268__attribute__((nonnull, always_inline)) static inline struct gcq *
269_gcq_prev(struct gcq *current, struct gcq_head *head, struct gcq *start)
270{
271 struct gcq *q, *hq;
272 hq = gcq_hq(head);
273 q = current->q_prev;
274 if (hq != start && q == hq)
275 q = hq->q_prev;
276 if (current != start)
277 GCQ_ASSERT(gcq_onlist(current));
278 return q;
279}
280
281
282#define GCQ_ITEM(q, type, name) \
283 ((type *)(void *)((uint8_t *)gcq_q(q) - offsetof(type, name)))
284
285
286#define _GCQ_GDQ(var, h, ptr, fn) (gcq_hq(h)->ptr != gcq_hq(h) ? \
287 (var = fn(gcq_hq(h)->ptr), true) : (var = NULL, false))
288#define _GCQ_GDQ_TYPED(tvar, h, type, name, ptr, fn) \
289 (gcq_hq(h)->ptr != gcq_hq(h) ? (tvar = GCQ_ITEM(fn(gcq_hq(h)->ptr), \
290 type, name), true) : (tvar = NULL, false))
291#define _GCQ_NP(var, current, head, start, np, fn) \
292 (np(current, head, start) != (start) ? \
293 (var = fn(np(current, head, start)), true) : (var = NULL, false))
294#define _GCQ_NP_TYPED(tvar, current, head, start, type, name, np, fn) \
295 (np(current, head, start) != (start) ? \
296 (tvar = GCQ_ITEM(fn(np(current, head, start)), type, name), true) : \
297 (tvar = NULL, false))
298
299#define _GCQ_GDQ_COND(var, h, ptr, rem, cond) \
300 (gcq_hq(h)->ptr != gcq_hq(h) ? (var = gcq_hq(h)->ptr, \
301 ((cond) ? (rem, true) : (var = NULL, false))) : \
302 (var = NULL, false))
303#define _GCQ_GDQ_COND_TYPED(tvar, h, type, name, ptr, rem, cond) \
304 (gcq_hq(h)->ptr != gcq_hq(h) ? (tvar = GCQ_ITEM(gcq_hq(h)->ptr, \
305 type, name), ((cond) ? (rem, true) : (tvar = NULL, false))) : \
306 (tvar = NULL, false))
307#define _GCQ_NP_COND(var, current, head, start, np, rem, cond) \
308 (np(current, head, start) != (start) ? \
309 (var = fn(np(current, head, start)), ((cond) ? (rem), true) : \
310 (var = NULL, false))) : (var = NULL, false))
311#define _GCQ_NP_COND_TYPED(tvar, current, head, start, type, name, np, \
312 rem, cond) (np(current, head, start) != (start) ? \
313 (tvar = GCQ_ITEM(fn(np(current, head, start)), type, name), \
314 ((cond) ? (rem, true) : (var = NULL, false))) : \
315 (tvar = NULL, false))
316
317#define GCQ_GOT_FIRST(var, h) _GCQ_GDQ(var, h, q_next, gcq_q)
318#define GCQ_GOT_LAST(var, h) _GCQ_GDQ(var, h, q_prev, gcq_q)
319#define GCQ_DEQUEUED_FIRST(var, h) _GCQ_GDQ(var, h, q_next, gcq_remove)
320#define GCQ_DEQUEUED_LAST(var, h) _GCQ_GDQ(var, h, q_prev, gcq_remove)
321#define GCQ_GOT_FIRST_TYPED(tvar, h, type, name) \
322 _GCQ_GDQ_TYPED(tvar, h, type, name, q_next, gcq_q)
323#define GCQ_GOT_LAST_TYPED(tvar, h, type, name) \
324 _GCQ_GDQ_TYPED(tvar, h, type, name, q_prev, gcq_q)
325#define GCQ_DEQUEUED_FIRST_TYPED(tvar, h, type, name) \
326 _GCQ_GDQ_TYPED(tvar, h, type, name, q_next, gcq_remove)
327#define GCQ_DEQUEUED_LAST_TYPED(tvar, h, type, name) \
328 _GCQ_GDQ_TYPED(tvar, h, type, name, q_prev, gcq_remove)
329#define GCQ_GOT_NEXT(var, current, head, start) \
330 _GCQ_NP(var, current, head, start, _gcq_next, gcq_q)
331#define GCQ_GOT_PREV(var, current, head, start) \
332 _GCQ_NP(var, current, head, start, _gcq_prev, gcq_q)
333#define GCQ_DEQUEUED_NEXT(var, current, head, start) \
334 _GCQ_NP(var, current, head, start, _gcq_next, gcq_remove)
335#define GCQ_DEQUEUED_PREV(var, current, head, start) \
336 _GCQ_NP(var, current, head, start, _gcq_prev, gcq_remove)
337#define GCQ_GOT_NEXT_TYPED(tvar, current, head, start, type, name) \
338 _GCQ_NP_TYPED(tvar, current, head, start, type, name, \
339 _gcq_next, gcq_q)
340#define GCQ_GOT_PREV_TYPED(tvar, current, head, start, type, name) \
341 _GCQ_NP_TYPED(tvar, current, head, start, type, name, \
342 _gcq_prev, gcq_q)
343#define GCQ_DEQUEUED_NEXT_TYPED(tvar, current, head, start, type, name) \
344 _GCQ_NP_TYPED(tvar, current, head, start, type, name, \
345 _gcq_next, gcq_remove)
346#define GCQ_DEQUEUED_PREV_TYPED(tvar, current, head, start, type, name) \
347 _GCQ_NP_TYPED(tvar, current, head, start, type, name, \
348 _gcq_prev, gcq_remove)
349
350#define GCQ_GOT_FIRST_COND(var, h, cond) \
351 _GCQ_GDQ_COND(var, h, q_next, ((void)0), cond)
352#define GCQ_GOT_LAST_COND(var, h, cond) \
353 _GCQ_GDQ_COND(var, h, q_prev, ((void)0), cond)
354#define GCQ_DEQUEUED_FIRST_COND(var, h, cond) \
355 _GCQ_GDQ_COND(var, h, q_next, gcq_remove(var), cond)
356#define GCQ_DEQUEUED_LAST_COND(var, h, cond) \
357 _GCQ_GDQ_COND(var, h, q_prev, gcq_remove(var), cond)
358#define GCQ_GOT_FIRST_COND_TYPED(tvar, h, type, name, cond) \
359 _GCQ_GDQ_COND_TYPED(tvar, h, type, name, q_next, ((void)0), cond)
360#define GCQ_GOT_LAST_COND_TYPED(tvar, h, type, name, cond) \
361 _GCQ_GDQ_COND_TYPED(tvar, h, type, name, q_prev, ((void)0), cond)
362#define GCQ_DEQUEUED_FIRST_COND_TYPED(tvar, h, type, name, cond) \
363 _GCQ_GDQ_COND_TYPED(tvar, h, type, name, q_next, \
364 gcq_remove(&(tvar)->name), cond)
365#define GCQ_DEQUEUED_LAST_COND_TYPED(tvar, h, type, name, cond) \
366 _GCQ_GDQ_COND_TYPED(tvar, h, type, name, q_prev, \
367 gcq_remove(&(tvar)->name), cond)
368#define GCQ_GOT_NEXT_COND(var, current, head, start, cond) \
369 _GCQ_NP_COND(var, current, head, start, _gcq_next, ((void)0), cond)
370#define GCQ_GOT_PREV_COND(var, current, head, start, cond) \
371 _GCQ_NP_COND(var, current, head, start, _gcq_prev, ((void)0), cond)
372#define GCQ_DEQUEUED_NEXT_COND(var, current, head, start, cond) \
373 _GCQ_NP_COND(var, current, head, start, _gcq_next, gcq_remove(var), \
374 cond)
375#define GCQ_DEQUEUED_PREV_COND(var, current, head, start, cond) \
376 _GCQ_NP_COND(var, current, head, start, _gcq_prev, gcq_remove(var), \
377 cond)
378#define GCQ_GOT_NEXT_COND_TYPED(tvar, current, head, start, type, name, \
379 cond) _GCQ_NP_COND_TYPED(tvar, current, head, start, type, name, \
380 _gcq_next, ((void)0), cond)
381#define GCQ_GOT_PREV_COND_TYPED(tvar, current, head, start, type, name, \
382 cond) _GCQ_NP_COND_TYPED(tvar, current, head, start, type, name, \
383 _gcq_prev, ((void)0), cond)
384#define GCQ_DEQUEUED_NEXT_COND_TYPED(tvar, current, head, start, type, \
385 name, cond) _GCQ_NP_COND_TYPED(tvar, current, head, start, type, \
386 name, _gcq_next, gcq_remove(&(tvar)->name), cond)
387#define GCQ_DEQUEUED_PREV_COND_TYPED(tvar, current, head, start, type, \
388 name, cond) _GCQ_NP_COND_TYPED(tvar, current, head, start, type, \
389 name, _gcq_prev, gcq_remove(&(tvar)->name), cond)
390
391
392#define _GCQ_FOREACH(var, h, tnull, item, ptr) \
393 for ((var)=gcq_hq(h)->ptr; ((var) != gcq_hq(h) && \
394 (GCQ_ASSERT(gcq_onlist(var)), item, true)) || \
395 (tnull, false); (var)=(var)->ptr)
396#define _GCQ_FOREACH_NVAR(var, nvar, h, tnull, item, ptr, ol, rem, ro) \
397 for ((nvar)=gcq_hq(h)->ptr; (((var)=(nvar), (nvar) != gcq_hq(h)) && \
398 (ol, (nvar)=(nvar)->ptr, rem, item, true)) || (tnull, false); ro)
399
400#define GCQ_FOREACH(var, h) \
401 _GCQ_FOREACH(var, h, ((void)0), ((void)0), q_next)
402#define GCQ_FOREACH_REV(var, h) \
403 _GCQ_FOREACH(var, h, ((void)0), ((void)0), q_prev)
404#define GCQ_FOREACH_NVAR(var, nvar, h) \
405 _GCQ_FOREACH_NVAR(var, nvar, h, ((void)0), ((void)0), \
406 q_next, GCQ_ASSERT(gcq_onlist(nvar)), ((void)0), ((void)0))
407#define GCQ_FOREACH_NVAR_REV(var, nvar, h) \
408 _GCQ_FOREACH_NVAR(var, nvar, h, ((void)0), ((void)0), \
409 q_prev, GCQ_ASSERT(gcq_onlist(nvar)), ((void)0), ((void)0))
410#define GCQ_FOREACH_RO(var, nvar, h) \
411 _GCQ_FOREACH_NVAR(var, nvar, h, ((void)0), ((void)0), \
412 q_next, ((void)0), ((void)0), GCQ_ASSERT(gcq_linked(var, nvar)))
413#define GCQ_FOREACH_RO_REV(var, nvar, h) \
414 _GCQ_FOREACH_NVAR(var, nvar, h, ((void)0), ((void)0), \
415 q_prev, ((void)0), ((void)0), GCQ_ASSERT(gcq_linked(nvar, var)))
416#define GCQ_FOREACH_DEQUEUED(var, nvar, h) \
417 _GCQ_FOREACH_NVAR(var, nvar, h, ((void)0), ((void)0), \
418 q_next, GCQ_ASSERT(gcq_onlist(nvar)), gcq_remove(var), ((void)0)
419#define GCQ_FOREACH_DEQUEUED_REV(var, nvar, h) \
420 _GCQ_FOREACH_NVAR(var, nvar, h, ((void)0), ((void)0), \
421 q_prev, GCQ_ASSERT(gcq_onlist(nvar)), gcq_remove(var), ((void)0)
422
423#define GCQ_FOREACH_TYPED(var, h, tvar, type, name) \
424 _GCQ_FOREACH(var, h, (tvar)=NULL, (tvar)=GCQ_ITEM(var, type, name), \
425 q_next)
426#define GCQ_FOREACH_TYPED_REV(var, h, tvar, type, name) \
427 _GCQ_FOREACH(var, h, (tvar)=NULL, (tvar)=GCQ_ITEM(var, type, name), \
428 q_prev)
429#define GCQ_FOREACH_NVAR_TYPED(var, nvar, h, tvar, type, name) \
430 _GCQ_FOREACH_NVAR(var, nvar, h, (tvar)=NULL, \
431 (tvar)=GCQ_ITEM(var, type, name), \
432 q_next, GCQ_ASSERT(gcq_onlist(nvar)), ((void)0), ((void)0))
433#define GCQ_FOREACH_NVAR_REV_TYPED(var, nvar, h, tvar, type, name) \
434 _GCQ_FOREACH_NVAR(var, nvar, h, (tvar)=NULL, \
435 (tvar)=GCQ_ITEM(var, type, name), \
436 q_prev, GCQ_ASSERT(gcq_onlist(nvar)), ((void)0), ((void)0))
437#define GCQ_FOREACH_RO_TYPED(var, nvar, h, tvar, type, name) \
438 _GCQ_FOREACH_NVAR(var, nvar, h, (tvar)=NULL, \
439 (tvar)=GCQ_ITEM(var, type, name), \
440 q_next, ((void)0), ((void)0), GCQ_ASSERT(gcq_lined(var, nvar)))
441#define GCQ_FOREACH_RO_REV_TYPED(var, nvar, h, tvar, type, name) \
442 _GCQ_FOREACH_NVAR(var, nvar, h, (tvar)=NULL, \
443 (tvar)=GCQ_ITEM(var, type, name), \
444 q_prev, ((void)0), ((void)0), GCQ_ASSERT(gcq_linked(nvar, var)))
445#define GCQ_FOREACH_DEQUEUED_TYPED(var, nvar, h, tvar, type, name) \
446 _GCQ_FOREACH_NVAR(var, nvar, h, (tvar)=NULL, \
447 (tvar)=GCQ_ITEM(var, type, name), \
448 q_next, GCQ_ASSERT(gcq_onlist(nvar)), gcq_remove(var), ((void)0))
449#define GCQ_FOREACH_DEQUEUED_REV_TYPED(var, nvar, h, tvar, type, name) \
450 _GCQ_FOREACH_NVAR(var, nvar, h, (tvar)=NULL, \
451 (tvar)=GCQ_ITEM(var, type, name), \
452 q_prev, GCQ_ASSERT(gcq_onlist(nvar)), gcq_remove(var), ((void)0))
453
454#define _GCQ_COND(fe, cond) do { fe { if (cond) break; } } while (0)
455
456#define GCQ_FIND(var, h, cond) _GCQ_COND(GCQ_FOREACH(var, h), cond)
457#define GCQ_FIND_REV(var, h, cond) _GCQ_COND(GCQ_FOREACH_REV(var, h), cond)
458#define GCQ_FIND_TYPED(var, h, tvar, type, name, cond) \
459 _GCQ_COND(GCQ_FOREACH_TYPED(var, h, tvar, type, name), cond)
460#define GCQ_FIND_TYPED_REV(var, h, tvar, type, name, cond) \
461 _GCQ_COND(GCQ_FOREACH_REV_TYPED(var, h, tvar, type, name), cond)
462
463#endif /* _GCQ_H */
464