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 41 struct gcq { 42 struct gcq *q_next; 43 struct gcq *q_prev; 44 }; 45 46 struct 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 54 gcq_init(struct gcq *q) 55 { 56 q->q_next = q->q_prev = q; 57 } 58 59 __attribute__((nonnull, const, warn_unused_result, always_inline)) 60 static __inline struct gcq * 61 gcq_q(struct gcq *q) 62 { 63 return q; 64 } 65 66 __attribute__((nonnull, const, warn_unused_result, always_inline)) 67 static __inline struct gcq * 68 gcq_hq(struct gcq_head *head) 69 { 70 return (struct gcq *)head; 71 } 72 73 __attribute__((nonnull, const, warn_unused_result, always_inline)) 74 static __inline struct gcq_head * 75 gcq_head(struct gcq *q) 76 { 77 return (struct gcq_head *)q; 78 } 79 80 __attribute__((nonnull, always_inline)) static __inline void 81 gcq_init_head(struct gcq_head *head) 82 { 83 gcq_init(gcq_hq(head)); 84 } 85 86 __attribute__((nonnull, pure, warn_unused_result, always_inline)) 87 static __inline bool 88 gcq_onlist(struct gcq *q) 89 { 90 return (q->q_next != q); 91 } 92 93 __attribute__((nonnull, pure, warn_unused_result, always_inline)) 94 static __inline bool 95 gcq_empty(struct gcq_head *head) 96 { 97 return (!gcq_onlist(gcq_hq(head))); 98 } 99 100 __attribute__((nonnull, pure, warn_unused_result, always_inline)) 101 static __inline bool 102 gcq_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 108 gcq_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 121 gcq_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 134 gcq_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 140 gcq_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 146 gcq_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 159 gcq_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 166 gcq_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 * 172 gcq_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 186 gcq_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 194 gcq_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 200 gcq_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 206 gcq_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 225 gcq_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 231 gcq_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 238 gcq_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 250 gcq_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
Indexes created Wed Sep 24 05:09:52 GMT 2025