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