1 /* 2 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 3 * 4 * This Source Code Form is subject to the terms of the Mozilla Public 5 * License, v. 2.0. If a copy of the MPL was not distributed with this 6 * file, You can obtain one at http://mozilla.org/MPL/2.0/. 7 * 8 * See the COPYRIGHT file distributed with this work for additional 9 * information regarding copyright ownership. 10 */ 11 12 #ifndef ISC_LIST_H 13 #define ISC_LIST_H 1 14 15 #include <isc/assertions.h> 16 17 #ifdef ISC_LIST_CHECKINIT 18 #define ISC_LINK_INSIST(x) ISC_INSIST(x) 19 #else /* ifdef ISC_LIST_CHECKINIT */ 20 #define ISC_LINK_INSIST(x) 21 #endif /* ifdef ISC_LIST_CHECKINIT */ 22 23 #define ISC_LIST(type) \ 24 struct { \ 25 type *head, *tail; \ 26 } 27 #define ISC_LIST_INIT(list) \ 28 do { \ 29 (list).head = NULL; \ 30 (list).tail = NULL; \ 31 } while (0) 32 33 #define ISC_LINK(type) \ 34 struct { \ 35 type *prev, *next; \ 36 } 37 #define ISC_LINK_INIT_TYPE(elt, link, type) \ 38 do { \ 39 (elt)->link.prev = (type *)(-1); \ 40 (elt)->link.next = (type *)(-1); \ 41 } while (0) 42 #define ISC_LINK_INIT(elt, link) ISC_LINK_INIT_TYPE(elt, link, void) 43 #define ISC_LINK_LINKED(elt, link) ((void *)((elt)->link.prev) != (void *)(-1)) 44 45 #define ISC_LIST_HEAD(list) ((list).head) 46 #define ISC_LIST_TAIL(list) ((list).tail) 47 #define ISC_LIST_EMPTY(list) ((list).head == NULL) 48 49 #define __ISC_LIST_PREPENDUNSAFE(list, elt, link) \ 50 do { \ 51 if ((list).head != NULL) { \ 52 (list).head->link.prev = (elt); \ 53 } else { \ 54 (list).tail = (elt); \ 55 } \ 56 (elt)->link.prev = NULL; \ 57 (elt)->link.next = (list).head; \ 58 (list).head = (elt); \ 59 } while (0) 60 61 #define ISC_LIST_PREPEND(list, elt, link) \ 62 do { \ 63 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 64 __ISC_LIST_PREPENDUNSAFE(list, elt, link); \ 65 } while (0) 66 67 #define ISC_LIST_INITANDPREPEND(list, elt, link) \ 68 __ISC_LIST_PREPENDUNSAFE(list, elt, link) 69 70 #define __ISC_LIST_APPENDUNSAFE(list, elt, link) \ 71 do { \ 72 if ((list).tail != NULL) { \ 73 (list).tail->link.next = (elt); \ 74 } else { \ 75 (list).head = (elt); \ 76 } \ 77 (elt)->link.prev = (list).tail; \ 78 (elt)->link.next = NULL; \ 79 (list).tail = (elt); \ 80 } while (0) 81 82 #define ISC_LIST_APPEND(list, elt, link) \ 83 do { \ 84 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 85 __ISC_LIST_APPENDUNSAFE(list, elt, link); \ 86 } while (0) 87 88 #define ISC_LIST_INITANDAPPEND(list, elt, link) \ 89 __ISC_LIST_APPENDUNSAFE(list, elt, link) 90 91 #define __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) \ 92 do { \ 93 if ((elt)->link.next != NULL) { \ 94 (elt)->link.next->link.prev = (elt)->link.prev; \ 95 } else { \ 96 ISC_INSIST((list).tail == (elt)); \ 97 (list).tail = (elt)->link.prev; \ 98 } \ 99 if ((elt)->link.prev != NULL) { \ 100 (elt)->link.prev->link.next = (elt)->link.next; \ 101 } else { \ 102 ISC_INSIST((list).head == (elt)); \ 103 (list).head = (elt)->link.next; \ 104 } \ 105 (elt)->link.prev = (type *)(-1); \ 106 (elt)->link.next = (type *)(-1); \ 107 ISC_INSIST((list).head != (elt)); \ 108 ISC_INSIST((list).tail != (elt)); \ 109 } while (0) 110 111 #define __ISC_LIST_UNLINKUNSAFE(list, elt, link) \ 112 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void) 113 114 #define ISC_LIST_UNLINK_TYPE(list, elt, link, type) \ 115 do { \ 116 ISC_LINK_INSIST(ISC_LINK_LINKED(elt, link)); \ 117 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type); \ 118 } while (0) 119 #define ISC_LIST_UNLINK(list, elt, link) \ 120 ISC_LIST_UNLINK_TYPE(list, elt, link, void) 121 122 #define ISC_LIST_PREV(elt, link) ((elt)->link.prev) 123 #define ISC_LIST_NEXT(elt, link) ((elt)->link.next) 124 125 #define __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link) \ 126 do { \ 127 if ((before)->link.prev == NULL) { \ 128 ISC_LIST_PREPEND(list, elt, link); \ 129 } else { \ 130 (elt)->link.prev = (before)->link.prev; \ 131 (before)->link.prev = (elt); \ 132 (elt)->link.prev->link.next = (elt); \ 133 (elt)->link.next = (before); \ 134 } \ 135 } while (0) 136 137 #define ISC_LIST_INSERTBEFORE(list, before, elt, link) \ 138 do { \ 139 ISC_LINK_INSIST(ISC_LINK_LINKED(before, link)); \ 140 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 141 __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link); \ 142 } while (0) 143 144 #define __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link) \ 145 do { \ 146 if ((after)->link.next == NULL) { \ 147 ISC_LIST_APPEND(list, elt, link); \ 148 } else { \ 149 (elt)->link.next = (after)->link.next; \ 150 (after)->link.next = (elt); \ 151 (elt)->link.next->link.prev = (elt); \ 152 (elt)->link.prev = (after); \ 153 } \ 154 } while (0) 155 156 #define ISC_LIST_INSERTAFTER(list, after, elt, link) \ 157 do { \ 158 ISC_LINK_INSIST(ISC_LINK_LINKED(after, link)); \ 159 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 160 __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link); \ 161 } while (0) 162 163 #define ISC_LIST_APPENDLIST(list1, list2, link) \ 164 do { \ 165 if (ISC_LIST_EMPTY(list1)) { \ 166 (list1) = (list2); \ 167 } else if (!ISC_LIST_EMPTY(list2)) { \ 168 (list1).tail->link.next = (list2).head; \ 169 (list2).head->link.prev = (list1).tail; \ 170 (list1).tail = (list2).tail; \ 171 } \ 172 (list2).head = NULL; \ 173 (list2).tail = NULL; \ 174 } while (0) 175 176 #define ISC_LIST_PREPENDLIST(list1, list2, link) \ 177 do { \ 178 if (ISC_LIST_EMPTY(list1)) { \ 179 (list1) = (list2); \ 180 } else if (!ISC_LIST_EMPTY(list2)) { \ 181 (list2).tail->link.next = (list1).head; \ 182 (list1).head->link.prev = (list2).tail; \ 183 (list1).head = (list2).head; \ 184 } \ 185 (list2).head = NULL; \ 186 (list2).tail = NULL; \ 187 } while (0) 188 189 #define ISC_LIST_ENQUEUE(list, elt, link) ISC_LIST_APPEND(list, elt, link) 190 #define __ISC_LIST_ENQUEUEUNSAFE(list, elt, link) \ 191 __ISC_LIST_APPENDUNSAFE(list, elt, link) 192 #define ISC_LIST_DEQUEUE(list, elt, link) \ 193 ISC_LIST_UNLINK_TYPE(list, elt, link, void) 194 #define ISC_LIST_DEQUEUE_TYPE(list, elt, link, type) \ 195 ISC_LIST_UNLINK_TYPE(list, elt, link, type) 196 #define __ISC_LIST_DEQUEUEUNSAFE(list, elt, link) \ 197 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void) 198 #define __ISC_LIST_DEQUEUEUNSAFE_TYPE(list, elt, link, type) \ 199 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) 200 201 #endif /* ISC_LIST_H */ 202