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 (const QUEUE *) (q) != (const QUEUE *) QUEUE_PREV(QUEUE_NEXT(q))) 42 /* treat broken queue as empty */ 43 44 #define QUEUE_HEAD(q) \ 45 (QUEUE_NEXT(q)) 46 47 #define QUEUE_INIT(q) \ 48 do { \ 49 QUEUE_NEXT(q) = (q); \ 50 QUEUE_PREV(q) = (q); \ 51 } \ 52 while (0) 53 54 #define QUEUE_ADD(h, n) \ 55 do { \ 56 QUEUE_PREV_NEXT(h) = QUEUE_NEXT(n); \ 57 QUEUE_NEXT_PREV(n) = QUEUE_PREV(h); \ 58 QUEUE_PREV(h) = QUEUE_PREV(n); \ 59 QUEUE_PREV_NEXT(h) = (h); \ 60 } \ 61 while (0) 62 63 #define QUEUE_SPLIT(h, q, n) \ 64 do { \ 65 QUEUE_PREV(n) = QUEUE_PREV(h); \ 66 QUEUE_PREV_NEXT(n) = (n); \ 67 QUEUE_NEXT(n) = (q); \ 68 QUEUE_PREV(h) = QUEUE_PREV(q); \ 69 QUEUE_PREV_NEXT(h) = (h); \ 70 QUEUE_PREV(q) = (n); \ 71 } \ 72 while (0) 73 74 #define QUEUE_MOVE(h, n) \ 75 do { \ 76 if (QUEUE_EMPTY(h)) \ 77 QUEUE_INIT(n); \ 78 else { \ 79 QUEUE* q = QUEUE_HEAD(h); \ 80 QUEUE_SPLIT(h, q, n); \ 81 } \ 82 } \ 83 while (0) 84 85 #define QUEUE_INSERT_HEAD(h, q) \ 86 do { \ 87 QUEUE_NEXT(q) = QUEUE_NEXT(h); \ 88 QUEUE_PREV(q) = (h); \ 89 QUEUE_NEXT_PREV(q) = (q); \ 90 QUEUE_NEXT(h) = (q); \ 91 } \ 92 while (0) 93 94 #define QUEUE_INSERT_TAIL(h, q) \ 95 do { \ 96 QUEUE_NEXT(q) = (h); \ 97 QUEUE_PREV(q) = QUEUE_PREV(h); \ 98 QUEUE_PREV_NEXT(q) = (q); \ 99 QUEUE_PREV(h) = (q); \ 100 } \ 101 while (0) 102 103 #define QUEUE_REMOVE(q) \ 104 do { \ 105 QUEUE_PREV_NEXT(q) = QUEUE_NEXT(q); \ 106 QUEUE_NEXT_PREV(q) = QUEUE_PREV(q); \ 107 } \ 108 while (0) 109 110 #ifdef USE_FFRT 111 #define QUEUE_APPEND(h, n) \ 112 do { \ 113 QUEUE* q = QUEUE_HEAD(h); \ 114 QUEUE* p = QUEUE_PREV(n); \ 115 QUEUE_PREV(n) = QUEUE_PREV(h); \ 116 QUEUE_PREV_NEXT(n) = (n); \ 117 QUEUE_NEXT(p) = (q); \ 118 QUEUE_PREV(h) = QUEUE_PREV(q); \ 119 QUEUE_PREV_NEXT(h) = (h); \ 120 QUEUE_PREV(q) = (p); \ 121 } \ 122 while (0) 123 #endif 124 125 #endif /* QUEUE_H_ */ 126