1 /* $NetBSD: list.h,v 1.10 2025/01/26 16:25:41 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, \ 25 .tail = NULL, \ 26 } 27 #define ISC_LINK_INITIALIZER_TYPE(type) \ 28 { \ 29 .prev = ISC_LINK_TOMBSTONE(type), \ 30 .next = ISC_LINK_TOMBSTONE(type), \ 31 } 32 #define ISC_LINK_INITIALIZER ISC_LINK_INITIALIZER_TYPE(void) 33 34 #ifdef ISC_LIST_CHECKINIT 35 #define ISC_LINK_INSIST(x) ISC_INSIST(x) 36 #else /* ifdef ISC_LIST_CHECKINIT */ 37 #define ISC_LINK_INSIST(x) 38 #endif /* ifdef ISC_LIST_CHECKINIT */ 39 40 #define ISC_LIST(type) \ 41 struct { \ 42 type *head, *tail; \ 43 } 44 #define ISC_LIST_INIT(list) \ 45 do { \ 46 (list).head = NULL; \ 47 (list).tail = NULL; \ 48 } while (0) 49 50 #define ISC_LINK(type) \ 51 struct { \ 52 type *prev, *next; \ 53 } 54 #define ISC_LINK_INIT_TYPE(elt, link, type) \ 55 do { \ 56 (elt)->link.prev = ISC_LINK_TOMBSTONE(type); \ 57 (elt)->link.next = ISC_LINK_TOMBSTONE(type); \ 58 } while (0) 59 #define ISC_LINK_INIT(elt, link) ISC_LINK_INIT_TYPE(elt, link, void) 60 #define ISC_LINK_LINKED_TYPE(elt, link, type) \ 61 ((type *)((elt)->link.prev) != ISC_LINK_TOMBSTONE(type)) 62 #define ISC_LINK_LINKED(elt, link) ISC_LINK_LINKED_TYPE(elt, link, void) 63 64 #define ISC_LIST_HEAD(list) ((list).head) 65 #define ISC_LIST_TAIL(list) ((list).tail) 66 #define ISC_LIST_EMPTY(list) ((list).head == NULL) 67 68 #define __ISC_LIST_PREPENDUNSAFE(list, elt, link) \ 69 do { \ 70 if ((list).head != NULL) { \ 71 (list).head->link.prev = (elt); \ 72 } else { \ 73 (list).tail = (elt); \ 74 } \ 75 (elt)->link.prev = NULL; \ 76 (elt)->link.next = (list).head; \ 77 (list).head = (elt); \ 78 } while (0) 79 80 #define ISC_LIST_PREPEND(list, elt, link) \ 81 do { \ 82 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 83 __ISC_LIST_PREPENDUNSAFE(list, elt, link); \ 84 } while (0) 85 86 #define ISC_LIST_INITANDPREPEND(list, elt, link) \ 87 __ISC_LIST_PREPENDUNSAFE(list, elt, link) 88 89 #define __ISC_LIST_APPENDUNSAFE(list, elt, link) \ 90 do { \ 91 if ((list).tail != NULL) { \ 92 (list).tail->link.next = (elt); \ 93 } else { \ 94 (list).head = (elt); \ 95 } \ 96 (elt)->link.prev = (list).tail; \ 97 (elt)->link.next = NULL; \ 98 (list).tail = (elt); \ 99 } while (0) 100 101 #define ISC_LIST_APPEND(list, elt, link) \ 102 do { \ 103 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 104 __ISC_LIST_APPENDUNSAFE(list, elt, link); \ 105 } while (0) 106 107 #define ISC_LIST_INITANDAPPEND(list, elt, link) \ 108 __ISC_LIST_APPENDUNSAFE(list, elt, link) 109 110 #define __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) \ 111 do { \ 112 if ((elt)->link.next != NULL) { \ 113 (elt)->link.next->link.prev = (elt)->link.prev; \ 114 } else { \ 115 ISC_INSIST((list).tail == (elt)); \ 116 (list).tail = (elt)->link.prev; \ 117 } \ 118 if ((elt)->link.prev != NULL) { \ 119 (elt)->link.prev->link.next = (elt)->link.next; \ 120 } else { \ 121 ISC_INSIST((list).head == (elt)); \ 122 (list).head = (elt)->link.next; \ 123 } \ 124 (elt)->link.prev = ISC_LINK_TOMBSTONE(type); \ 125 (elt)->link.next = ISC_LINK_TOMBSTONE(type); \ 126 ISC_INSIST((list).head != (elt)); \ 127 ISC_INSIST((list).tail != (elt)); \ 128 } while (0) 129 130 #define __ISC_LIST_UNLINKUNSAFE(list, elt, link) \ 131 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void) 132 133 #define ISC_LIST_UNLINK_TYPE(list, elt, link, type) \ 134 do { \ 135 ISC_LINK_INSIST(ISC_LINK_LINKED(elt, link)); \ 136 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type); \ 137 } while (0) 138 #define ISC_LIST_UNLINK(list, elt, link) \ 139 ISC_LIST_UNLINK_TYPE(list, elt, link, void) 140 141 #define ISC_LIST_PREV(elt, link) ((elt)->link.prev) 142 #define ISC_LIST_NEXT(elt, link) ((elt)->link.next) 143 144 #define __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link) \ 145 do { \ 146 if ((before)->link.prev == NULL) { \ 147 ISC_LIST_PREPEND(list, elt, link); \ 148 } else { \ 149 (elt)->link.prev = (before)->link.prev; \ 150 (before)->link.prev = (elt); \ 151 (elt)->link.prev->link.next = (elt); \ 152 (elt)->link.next = (before); \ 153 } \ 154 } while (0) 155 156 #define ISC_LIST_INSERTBEFORE(list, before, elt, link) \ 157 do { \ 158 ISC_LINK_INSIST(ISC_LINK_LINKED(before, link)); \ 159 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 160 __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link); \ 161 } while (0) 162 163 #define __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link) \ 164 do { \ 165 if ((after)->link.next == NULL) { \ 166 ISC_LIST_APPEND(list, elt, link); \ 167 } else { \ 168 (elt)->link.next = (after)->link.next; \ 169 (after)->link.next = (elt); \ 170 (elt)->link.next->link.prev = (elt); \ 171 (elt)->link.prev = (after); \ 172 } \ 173 } while (0) 174 175 #define ISC_LIST_INSERTAFTER(list, after, elt, link) \ 176 do { \ 177 ISC_LINK_INSIST(ISC_LINK_LINKED(after, link)); \ 178 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 179 __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link); \ 180 } while (0) 181 182 #define ISC_LIST_APPENDLIST(list1, list2, link) \ 183 do { \ 184 if (ISC_LIST_EMPTY(list1)) { \ 185 (list1) = (list2); \ 186 } else if (!ISC_LIST_EMPTY(list2)) { \ 187 (list1).tail->link.next = (list2).head; \ 188 (list2).head->link.prev = (list1).tail; \ 189 (list1).tail = (list2).tail; \ 190 } \ 191 (list2).head = NULL; \ 192 (list2).tail = NULL; \ 193 } while (0) 194 195 #define ISC_LIST_PREPENDLIST(list1, list2, link) \ 196 do { \ 197 if (ISC_LIST_EMPTY(list1)) { \ 198 (list1) = (list2); \ 199 } else if (!ISC_LIST_EMPTY(list2)) { \ 200 (list2).tail->link.next = (list1).head; \ 201 (list1).head->link.prev = (list2).tail; \ 202 (list1).head = (list2).head; \ 203 } \ 204 (list2).head = NULL; \ 205 (list2).tail = NULL; \ 206 } while (0) 207 208 #define ISC_LIST_ENQUEUE(list, elt, link) ISC_LIST_APPEND(list, elt, link) 209 #define __ISC_LIST_ENQUEUEUNSAFE(list, elt, link) \ 210 __ISC_LIST_APPENDUNSAFE(list, elt, link) 211 #define ISC_LIST_DEQUEUE(list, elt, link) \ 212 ISC_LIST_UNLINK_TYPE(list, elt, link, void) 213 #define ISC_LIST_DEQUEUE_TYPE(list, elt, link, type) \ 214 ISC_LIST_UNLINK_TYPE(list, elt, link, type) 215 #define __ISC_LIST_DEQUEUEUNSAFE(list, elt, link) \ 216 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void) 217 #define __ISC_LIST_DEQUEUEUNSAFE_TYPE(list, elt, link, type) \ 218 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) 219 220 #define ISC_LIST_MOVEUNSAFE(dest, src) \ 221 { \ 222 (dest).head = (src).head; \ 223 (dest).tail = (src).tail; \ 224 (src).head = NULL; \ 225 (src).tail = NULL; \ 226 } 227 228 #define ISC_LIST_MOVE(dest, src) \ 229 { \ 230 INSIST(ISC_LIST_EMPTY(dest)); \ 231 ISC_LIST_MOVEUNSAFE(dest, src); \ 232 } 233 234 /* clang-format off */ 235 #define ISC_LIST_FOREACH(list, elt, link) \ 236 for (elt = ISC_LIST_HEAD(list); \ 237 elt != NULL; \ 238 elt = ISC_LIST_NEXT(elt, link)) 239 /* clang-format on */ 240 241 /* clang-format off */ 242 #define ISC_LIST_FOREACH_SAFE(list, elt, link, next) \ 243 for (elt = ISC_LIST_HEAD(list), next = (elt != NULL) ? ISC_LIST_NEXT(elt, link) : NULL; \ 244 elt != NULL; \ 245 elt = next, next = (elt != NULL) ? ISC_LIST_NEXT(elt, link) : NULL) 246 /* clang-format on */ 247 248 /* clang-format off */ 249 #define ISC_LIST_FOREACH_REV(list, elt, link) \ 250 for (elt = ISC_LIST_TAIL(list); \ 251 elt != NULL; \ 252 elt = ISC_LIST_PREV(elt, link)) 253 /* clang-format on */ 254 255 /* clang-format off */ 256 #define ISC_LIST_FOREACH_REV_SAFE(list, elt, link, prev) \ 257 for (elt = ISC_LIST_TAIL(list), prev = (elt != NULL) ? ISC_LIST_PREV(elt, link) : NULL; \ 258 elt != NULL; \ 259 elt = prev, prev = (elt != NULL) ? ISC_LIST_PREV(elt, link) : NULL) 260 /* clang-format on */ 261
Indexes created Fri Jun 12 00:25:51 UTC 2026