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