1 /* Copyright (c) 2013, Ben Noordhuis <info@bnoordhuis.nl> 2 * 3 * Permission to use, copy, modify, and/or distribute this software for any 4 * purpose with or without fee is hereby granted, provided that the above 5 * copyright notice and this permission notice appear in all copies. 6 * 7 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 8 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 9 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 10 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 11 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 12 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 13 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 14 */ 15 16 #ifndef QUEUE_H_ 17 #define QUEUE_H_ 18 19 #include <stddef.h> 20 21 typedef void *QUEUE[2]; 22 23 /* Private macros. */ 24 #define QUEUE_NEXT(q) (*(QUEUE **) &((*(q))[0])) 25 #define QUEUE_PREV(q) (*(QUEUE **) &((*(q))[1])) 26 #define QUEUE_PREV_NEXT(q) (QUEUE_NEXT(QUEUE_PREV(q))) 27 #define QUEUE_NEXT_PREV(q) (QUEUE_PREV(QUEUE_NEXT(q))) 28 29 /* Public macros. */ 30 #define QUEUE_DATA(ptr, type, field) \ 31 ((type *) ((char *) (ptr) - offsetof(type, field))) 32 33 /* Important note: mutating the list while QUEUE_FOREACH is 34 * iterating over its elements results in undefined behavior. 35 */ 36 #define QUEUE_FOREACH(q, h) \ 37 for ((q) = QUEUE_NEXT(h); (q) != (h); (q) = QUEUE_NEXT(q)) 38 39 #define QUEUE_EMPTY(q) \ 40 ((const QUEUE *) (q) == (const QUEUE *) QUEUE_NEXT(q)) 41 42 #define QUEUE_HEAD(q) \ 43 (QUEUE_NEXT(q)) 44 45 #define QUEUE_INIT(q) \ 46 do { \ 47 QUEUE_NEXT(q) = (q); \ 48 QUEUE_PREV(q) = (q); \ 49 } \ 50 while (0) 51 52 #define QUEUE_ADD(h, n) \ 53 do { \ 54 QUEUE_PREV_NEXT(h) = QUEUE_NEXT(n); \ 55 QUEUE_NEXT_PREV(n) = QUEUE_PREV(h); \ 56 QUEUE_PREV(h) = QUEUE_PREV(n); \ 57 QUEUE_PREV_NEXT(h) = (h); \ 58 } \ 59 while (0) 60 61 #define QUEUE_SPLIT(h, q, n) \ 62 do { \ 63 QUEUE_PREV(n) = QUEUE_PREV(h); \ 64 QUEUE_PREV_NEXT(n) = (n); \ 65 QUEUE_NEXT(n) = (q); \ 66 QUEUE_PREV(h) = QUEUE_PREV(q); \ 67 QUEUE_PREV_NEXT(h) = (h); \ 68 QUEUE_PREV(q) = (n); \ 69 } \ 70 while (0) 71 72 #define QUEUE_MOVE(h, n) \ 73 do { \ 74 if (QUEUE_EMPTY(h)) \ 75 QUEUE_INIT(n); \ 76 else { \ 77 QUEUE* q = QUEUE_HEAD(h); \ 78 QUEUE_SPLIT(h, q, n); \ 79 } \ 80 } \ 81 while (0) 82 83 #define QUEUE_INSERT_HEAD(h, q) \ 84 do { \ 85 QUEUE_NEXT(q) = QUEUE_NEXT(h); \ 86 QUEUE_PREV(q) = (h); \ 87 QUEUE_NEXT_PREV(q) = (q); \ 88 QUEUE_NEXT(h) = (q); \ 89 } \ 90 while (0) 91 92 #define QUEUE_INSERT_TAIL(h, q) \ 93 do { \ 94 QUEUE_NEXT(q) = (h); \ 95 QUEUE_PREV(q) = QUEUE_PREV(h); \ 96 QUEUE_PREV_NEXT(q) = (q); \ 97 QUEUE_PREV(h) = (q); \ 98 } \ 99 while (0) 100 101 #define QUEUE_REMOVE(q) \ 102 do { \ 103 QUEUE_PREV_NEXT(q) = QUEUE_NEXT(q); \ 104 QUEUE_NEXT_PREV(q) = QUEUE_PREV(q); \ 105 } \ 106 while (0) 107 108 #endif /* QUEUE_H_ */ 109