| Brian Silverman | 41cdd3e | 2019-01-19 19:48:58 -0800 | [diff] [blame] | 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_ */ |