1/* $NetBSD: gcq.h,v 1.3 2018/04/19 21:19:07 christos 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