1 /* $NetBSD: list.h,v 1.7 2014/12/10 04:38:00 christos Exp $ */ 2 3 /* 4 * Copyright (C) 2004, 2006, 2007, 2011-2013 Internet Systems Consortium, Inc. ("ISC") 5 * Copyright (C) 1997-2002 Internet Software Consortium. 6 * 7 * Permission to use, copy, modify, and/or distribute this software for any 8 * purpose with or without fee is hereby granted, provided that the above 9 * copyright notice and this permission notice appear in all copies. 10 * 11 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 12 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 13 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 14 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 15 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 16 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 17 * PERFORMANCE OF THIS SOFTWARE. 18 */ 19 20 /* Id */ 21 22 #ifndef ISC_LIST_H 23 #define ISC_LIST_H 1 24 #include <isc/boolean.h> 25 #include <isc/assertions.h> 26 27 #ifdef ISC_LIST_CHECKINIT 28 #define ISC_LINK_INSIST(x) ISC_INSIST(x) 29 #else 30 #define ISC_LINK_INSIST(x) 31 #endif 32 33 #define ISC_LIST(type) struct { type *head, *tail; } 34 #define ISC_LIST_INIT(list) \ 35 do { (list).head = NULL; (list).tail = NULL; } while (/*CONSTCOND*/0) 36 37 #define ISC_LINK(type) struct { type *prev, *next; } 38 #define ISC_LINK_INIT_TYPE(elt, link, type) \ 39 do { \ 40 (elt)->link.prev = (type *)(-1); \ 41 (elt)->link.next = (type *)(-1); \ 42 } while (/*CONSTCOND*/0) 43 #define ISC_LINK_INIT(elt, link) \ 44 ISC_LINK_INIT_TYPE(elt, link, void) 45 #define ISC_LINK_LINKED(elt, link) ((void *)((elt)->link.prev) != (void *)(-1)) 46 47 #define ISC_LIST_HEAD(list) ((list).head) 48 #define ISC_LIST_TAIL(list) ((list).tail) 49 #define ISC_LIST_EMPTY(list) ISC_TF((list).head == NULL) 50 51 #define __ISC_LIST_PREPENDUNSAFE(list, elt, link) \ 52 do { \ 53 if ((list).head != NULL) \ 54 (list).head->link.prev = (elt); \ 55 else \ 56 (list).tail = (elt); \ 57 (elt)->link.prev = NULL; \ 58 (elt)->link.next = (list).head; \ 59 (list).head = (elt); \ 60 } while (/*CONSTCOND*/0) 61 62 #define ISC_LIST_PREPEND(list, elt, link) \ 63 do { \ 64 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 65 __ISC_LIST_PREPENDUNSAFE(list, elt, link); \ 66 } while (/*CONSTCOND*/0) 67 68 #define ISC_LIST_INITANDPREPEND(list, elt, link) \ 69 __ISC_LIST_PREPENDUNSAFE(list, elt, link) 70 71 #define __ISC_LIST_APPENDUNSAFE(list, elt, link) \ 72 do { \ 73 if ((list).tail != NULL) \ 74 (list).tail->link.next = (elt); \ 75 else \ 76 (list).head = (elt); \ 77 (elt)->link.prev = (list).tail; \ 78 (elt)->link.next = NULL; \ 79 (list).tail = (elt); \ 80 } while (/*CONSTCOND*/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 (/*CONSTCOND*/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 (/*CONSTCOND*/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 (/*CONSTCOND*/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 (/*CONSTCOND*/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 (/*CONSTCOND*/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 (/*CONSTCOND*/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 (/*CONSTCOND*/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 (/*CONSTCOND*/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 (/*CONSTCOND*/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