1 /* 2 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 3 * 4 * Permission to use, copy, modify, and/or distribute this software for any 5 * purpose with or without fee is hereby granted, provided that the above 6 * copyright notice and this permission notice appear in all copies. 7 * 8 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 9 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 10 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 11 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 12 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 13 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 14 * PERFORMANCE OF THIS SOFTWARE. 15 */ 16 17 /* $Id: list.h,v 1.3 2020/09/14 08:40:44 florian Exp $ */ 18 19 #ifndef ISC_LIST_H 20 #define ISC_LIST_H 1 21 #include <isc/assertions.h> 22 23 #define ISC_LIST(type) struct { type *head, *tail; } 24 #define ISC_LIST_INIT(list) \ 25 do { (list).head = NULL; (list).tail = NULL; } while (0) 26 27 #define ISC_LINK(type) struct { type *prev, *next; } 28 #define ISC_LINK_INIT_TYPE(elt, link, type) \ 29 do { \ 30 (elt)->link.prev = (type *)(-1); \ 31 (elt)->link.next = (type *)(-1); \ 32 } while (0) 33 #define ISC_LINK_INIT(elt, link) \ 34 ISC_LINK_INIT_TYPE(elt, link, void) 35 #define ISC_LINK_LINKED(elt, link) ((void *)((elt)->link.prev) != (void *)(-1)) 36 37 #define ISC_LIST_HEAD(list) ((list).head) 38 #define ISC_LIST_TAIL(list) ((list).tail) 39 #define ISC_LIST_EMPTY(list) ((list).head == NULL) 40 41 #define __ISC_LIST_PREPENDUNSAFE(list, elt, link) \ 42 do { \ 43 if ((list).head != NULL) \ 44 (list).head->link.prev = (elt); \ 45 else \ 46 (list).tail = (elt); \ 47 (elt)->link.prev = NULL; \ 48 (elt)->link.next = (list).head; \ 49 (list).head = (elt); \ 50 } while (0) 51 52 #define ISC_LIST_PREPEND(list, elt, link) \ 53 do { \ 54 __ISC_LIST_PREPENDUNSAFE(list, elt, link); \ 55 } while (0) 56 57 #define ISC_LIST_INITANDPREPEND(list, elt, link) \ 58 __ISC_LIST_PREPENDUNSAFE(list, elt, link) 59 60 #define __ISC_LIST_APPENDUNSAFE(list, elt, link) \ 61 do { \ 62 if ((list).tail != NULL) \ 63 (list).tail->link.next = (elt); \ 64 else \ 65 (list).head = (elt); \ 66 (elt)->link.prev = (list).tail; \ 67 (elt)->link.next = NULL; \ 68 (list).tail = (elt); \ 69 } while (0) 70 71 #define ISC_LIST_APPEND(list, elt, link) \ 72 do { \ 73 __ISC_LIST_APPENDUNSAFE(list, elt, link); \ 74 } while (0) 75 76 #define ISC_LIST_INITANDAPPEND(list, elt, link) \ 77 __ISC_LIST_APPENDUNSAFE(list, elt, link) 78 79 #define __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) \ 80 do { \ 81 if ((elt)->link.next != NULL) \ 82 (elt)->link.next->link.prev = (elt)->link.prev; \ 83 else { \ 84 ISC_INSIST((list).tail == (elt)); \ 85 (list).tail = (elt)->link.prev; \ 86 } \ 87 if ((elt)->link.prev != NULL) \ 88 (elt)->link.prev->link.next = (elt)->link.next; \ 89 else { \ 90 ISC_INSIST((list).head == (elt)); \ 91 (list).head = (elt)->link.next; \ 92 } \ 93 (elt)->link.prev = (type *)(-1); \ 94 (elt)->link.next = (type *)(-1); \ 95 ISC_INSIST((list).head != (elt)); \ 96 ISC_INSIST((list).tail != (elt)); \ 97 } while (0) 98 99 #define __ISC_LIST_UNLINKUNSAFE(list, elt, link) \ 100 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void) 101 102 #define ISC_LIST_UNLINK_TYPE(list, elt, link, type) \ 103 do { \ 104 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type); \ 105 } while (0) 106 #define ISC_LIST_UNLINK(list, elt, link) \ 107 ISC_LIST_UNLINK_TYPE(list, elt, link, void) 108 109 #define ISC_LIST_PREV(elt, link) ((elt)->link.prev) 110 #define ISC_LIST_NEXT(elt, link) ((elt)->link.next) 111 112 #define __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link) \ 113 do { \ 114 if ((before)->link.prev == NULL) \ 115 ISC_LIST_PREPEND(list, elt, link); \ 116 else { \ 117 (elt)->link.prev = (before)->link.prev; \ 118 (before)->link.prev = (elt); \ 119 (elt)->link.prev->link.next = (elt); \ 120 (elt)->link.next = (before); \ 121 } \ 122 } while (0) 123 124 #define ISC_LIST_INSERTBEFORE(list, before, elt, link) \ 125 do { \ 126 __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link); \ 127 } while (0) 128 129 #define __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link) \ 130 do { \ 131 if ((after)->link.next == NULL) \ 132 ISC_LIST_APPEND(list, elt, link); \ 133 else { \ 134 (elt)->link.next = (after)->link.next; \ 135 (after)->link.next = (elt); \ 136 (elt)->link.next->link.prev = (elt); \ 137 (elt)->link.prev = (after); \ 138 } \ 139 } while (0) 140 141 #define ISC_LIST_INSERTAFTER(list, after, elt, link) \ 142 do { \ 143 __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link); \ 144 } while (0) 145 146 #define ISC_LIST_APPENDLIST(list1, list2, link) \ 147 do { \ 148 if (ISC_LIST_EMPTY(list1)) \ 149 (list1) = (list2); \ 150 else if (!ISC_LIST_EMPTY(list2)) { \ 151 (list1).tail->link.next = (list2).head; \ 152 (list2).head->link.prev = (list1).tail; \ 153 (list1).tail = (list2).tail; \ 154 } \ 155 (list2).head = NULL; \ 156 (list2).tail = NULL; \ 157 } while (0) 158 159 #define ISC_LIST_PREPENDLIST(list1, list2, link) \ 160 do { \ 161 if (ISC_LIST_EMPTY(list1)) \ 162 (list1) = (list2); \ 163 else if (!ISC_LIST_EMPTY(list2)) { \ 164 (list2).tail->link.next = (list1).head; \ 165 (list1).head->link.prev = (list2).tail; \ 166 (list1).head = (list2).head; \ 167 } \ 168 (list2).head = NULL; \ 169 (list2).tail = NULL; \ 170 } while (0) 171 172 #define ISC_LIST_ENQUEUE(list, elt, link) ISC_LIST_APPEND(list, elt, link) 173 #define __ISC_LIST_ENQUEUEUNSAFE(list, elt, link) \ 174 __ISC_LIST_APPENDUNSAFE(list, elt, link) 175 #define ISC_LIST_DEQUEUE(list, elt, link) \ 176 ISC_LIST_UNLINK_TYPE(list, elt, link, void) 177 #define ISC_LIST_DEQUEUE_TYPE(list, elt, link, type) \ 178 ISC_LIST_UNLINK_TYPE(list, elt, link, type) 179 #define __ISC_LIST_DEQUEUEUNSAFE(list, elt, link) \ 180 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void) 181 #define __ISC_LIST_DEQUEUEUNSAFE_TYPE(list, elt, link, type) \ 182 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) 183 184 #endif /* ISC_LIST_H */ 185