1 /* $NetBSD: ntp_lists.h,v 1.8 2024/10/01 20:59:51 christos Exp $ */ 2 3 /* 4 * ntp_lists.h - linked lists common code 5 * 6 * SLIST: singly-linked lists 7 * ========================== 8 * 9 * These macros implement a simple singly-linked list template. Both 10 * the listhead and per-entry next fields are declared as pointers to 11 * the list entry struct type. Initialization to NULL is typically 12 * implicit (for globals and statics) or handled by zeroing of the 13 * containing structure. 14 * 15 * The name of the next link field is passed as an argument to allow 16 * membership in several lists at once using multiple next link fields. 17 * 18 * When possible, placing the link field first in the entry structure 19 * allows slightly smaller code to be generated on some platforms. 20 * 21 * LINK_SLIST(listhead, pentry, nextlink) 22 * add entry at head 23 * 24 * LINK_TAIL_SLIST(listhead, pentry, nextlink, entrytype) 25 * add entry at tail. This is O(n), if this is a common 26 * operation the FIFO template may be more appropriate. 27 * 28 * LINK_SORT_SLIST(listhead, pentry, beforecur, nextlink, entrytype) 29 * add entry in sorted order. beforecur is an expression comparing 30 * pentry with the current list entry. The current entry can be 31 * referenced within beforecur as L_S_S_CUR(), which is short for 32 * LINK_SORT_SLIST_CUR(). beforecur is nonzero if pentry sorts 33 * before L_S_S_CUR(). 34 * 35 * UNLINK_HEAD_SLIST(punlinked, listhead, nextlink) 36 * unlink first entry and point punlinked to it, or set punlinked 37 * to NULL if the list is empty. 38 * 39 * UNLINK_SLIST(punlinked, listhead, ptounlink, nextlink, entrytype) 40 * unlink entry pointed to by ptounlink. punlinked is set to NULL 41 * if the entry is not found on the list, otherwise it is set to 42 * ptounlink. 43 * 44 * UNLINK_EXPR_SLIST(punlinked, listhead, expr, nextlink, entrytype) 45 * unlink entry where expression expr is nonzero. expr can refer 46 * to the entry being tested using UNLINK_EXPR_SLIST_CURRENT(), 47 * alias U_E_S_CUR(). See the implementation of UNLINK_SLIST() 48 * below for an example. U_E_S_CUR() is NULL iff the list is empty. 49 * punlinked is pointed to the removed entry or NULL if none 50 * satisfy expr. 51 * 52 * FIFO: singly-linked lists plus tail pointer 53 * =========================================== 54 * 55 * This is the same as FreeBSD's sys/queue.h STAILQ -- a singly-linked 56 * list implementation with tail-pointer maintenance, so that adding 57 * at the tail for first-in, first-out access is O(1). 58 * 59 * DECL_FIFO_ANCHOR(entrytype) 60 * provides the type specification portion of the declaration for 61 * a variable to refer to a FIFO queue (similar to listhead). The 62 * anchor contains the head and indirect tail pointers. Example: 63 * 64 * #include "ntp_lists.h" 65 * 66 * typedef struct myentry_tag myentry; 67 * struct myentry_tag { 68 * myentry *next_link; 69 * ... 70 * }; 71 * 72 * DECL_FIFO_ANCHOR(myentry) my_fifo; 73 * 74 * void somefunc(myentry *pentry) 75 * { 76 * LINK_FIFO(my_fifo, pentry, next_link); 77 * } 78 * 79 * If DECL_FIFO_ANCHOR is used with stack or heap storage, it 80 * should be initialized to NULL pointers using a = { NULL }; 81 * initializer or memset. 82 * 83 * HEAD_FIFO(anchor) 84 * TAIL_FIFO(anchor) 85 * Pointer to first/last entry, NULL if FIFO is empty. 86 * 87 * LINK_FIFO(anchor, pentry, nextlink) 88 * add entry at tail. 89 * 90 * UNLINK_FIFO(punlinked, anchor, nextlink) 91 * unlink head entry and point punlinked to it, or set punlinked 92 * to NULL if the list is empty. 93 * 94 * CONCAT_FIFO(q1, q2, nextlink) 95 * empty fifoq q2 moving its nodes to q1 following q1's existing 96 * nodes. 97 * 98 * DLIST: doubly-linked lists 99 * ========================== 100 * 101 * Elements on DLISTs always have non-NULL forward and back links, 102 * because both link chains are circular. The beginning/end is marked 103 * by the listhead, which is the same type as elements for simplicity. 104 * An empty list's listhead has both links set to its own address. 105 * 106 * 107 */ 108 #ifndef NTP_LISTS_H 109 #define NTP_LISTS_H 110 111 #include "ntp_types.h" /* TRUE and FALSE */ 112 #include "ntp_assert.h" 113 114 #ifdef DEBUG 115 # define NTP_DEBUG_LISTS_H 116 #endif 117 118 /* 119 * If list debugging is not enabled, save a little time by not clearing 120 * an entry's link pointer when it is unlinked, as the stale pointer 121 * is harmless as long as it is ignored when the entry is not in a 122 * list. 123 */ 124 #ifndef NTP_DEBUG_LISTS_H 125 #define MAYBE_Z_LISTS(p) do { } while (FALSE) 126 #else 127 #define MAYBE_Z_LISTS(p) (p) = NULL 128 #endif 129 130 #define LINK_SLIST(listhead, pentry, nextlink) \ 131 do { \ 132 (pentry)->nextlink = (listhead); \ 133 (listhead) = (pentry); \ 134 } while (FALSE) 135 136 #define LINK_TAIL_SLIST(listhead, pentry, nextlink, entrytype) \ 137 do { \ 138 entrytype **pptail; \ 139 \ 140 pptail = &(listhead); \ 141 while (*pptail != NULL) \ 142 pptail = &((*pptail)->nextlink); \ 143 \ 144 (pentry)->nextlink = NULL; \ 145 *pptail = (pentry); \ 146 } while (FALSE) 147 148 #define LINK_SORT_SLIST_CURRENT() (*ppentry) 149 #define L_S_S_CUR() LINK_SORT_SLIST_CURRENT() 150 151 #define LINK_SORT_SLIST(listhead, pentry, beforecur, nextlink, \ 152 entrytype) \ 153 do { \ 154 entrytype **ppentry; \ 155 \ 156 ppentry = &(listhead); \ 157 while (TRUE) { \ 158 if (beforecur) { \ 159 (pentry)->nextlink = *ppentry; \ 160 *ppentry = (pentry); \ 161 break; \ 162 } \ 163 ppentry = &((*ppentry)->nextlink); \ 164 if (NULL == *ppentry) { \ 165 (pentry)->nextlink = NULL; \ 166 *ppentry = (pentry); \ 167 break; \ 168 } \ 169 } \ 170 } while (FALSE) 171 172 #define UNLINK_HEAD_SLIST(punlinked, listhead, nextlink) \ 173 do { \ 174 (punlinked) = (listhead); \ 175 if (NULL != (punlinked)) { \ 176 (listhead) = (punlinked)->nextlink; \ 177 MAYBE_Z_LISTS((punlinked)->nextlink); \ 178 } \ 179 } while (FALSE) 180 181 #define UNLINK_EXPR_SLIST_CURRENT() (*ppentry) 182 #define U_E_S_CUR() UNLINK_EXPR_SLIST_CURRENT() 183 184 #define UNLINK_EXPR_SLIST(punlinked, listhead, expr, nextlink, \ 185 entrytype) \ 186 if (NULL != (listhead)) { \ 187 entrytype **ppentry; \ 188 \ 189 ppentry = &(listhead); \ 190 \ 191 while (!(expr)) \ 192 if (*ppentry != NULL && \ 193 (*ppentry)->nextlink != NULL) { \ 194 ppentry = &((*ppentry)->nextlink); \ 195 } else { \ 196 ppentry = NULL; \ 197 break; \ 198 } \ 199 \ 200 if (ppentry != NULL) { \ 201 (punlinked) = *ppentry; \ 202 *ppentry = (punlinked)->nextlink; \ 203 MAYBE_Z_LISTS((punlinked)->nextlink); \ 204 } else { \ 205 (punlinked) = NULL; \ 206 } \ 207 } else do { \ 208 (punlinked) = NULL; \ 209 } while (FALSE) 210 211 #define UNLINK_SLIST(punlinked, listhead, ptounlink, nextlink, \ 212 entrytype) \ 213 UNLINK_EXPR_SLIST(punlinked, listhead, (ptounlink) == \ 214 U_E_S_CUR(), nextlink, entrytype) 215 216 #define CHECK_SLIST(listhead, nextlink, entrytype) \ 217 do { \ 218 entrytype *pentry; \ 219 \ 220 for (pentry = (listhead); \ 221 pentry != NULL; \ 222 pentry = pentry->nextlink) { \ 223 INSIST(pentry != pentry->nextlink); \ 224 INSIST((listhead) != pentry->nextlink); \ 225 } \ 226 } while (FALSE) 227 228 /* 229 * FIFO 230 */ 231 232 #define DECL_FIFO_ANCHOR(entrytype) \ 233 struct { \ 234 entrytype * phead; /* NULL if list empty */ \ 235 entrytype ** pptail; /* NULL if list empty */ \ 236 } 237 238 #define HEAD_FIFO(anchor) ((anchor).phead) 239 #define TAIL_FIFO(anchor) ((NULL == (anchor).pptail) \ 240 ? NULL \ 241 : *((anchor).pptail)) 242 243 /* 244 * For DEBUG builds only, verify both or neither of the anchor pointers 245 * are NULL with each operation. 246 */ 247 #if !defined(NTP_DEBUG_LISTS_H) 248 #define CHECK_FIFO_CONSISTENCY(anchor) do { } while (FALSE) 249 #else 250 #define CHECK_FIFO_CONSISTENCY(anchor) \ 251 check_gen_fifo_consistency(&(anchor)) 252 void check_gen_fifo_consistency(void *fifo); 253 #endif 254 255 /* 256 * generic FIFO element used to access any FIFO where each element 257 * begins with the link pointer 258 */ 259 typedef struct gen_node_tag gen_node; 260 struct gen_node_tag { 261 gen_node * link; 262 }; 263 264 /* generic FIFO */ 265 typedef DECL_FIFO_ANCHOR(gen_node) gen_fifo; 266 267 268 #define LINK_FIFO(anchor, pentry, nextlink) \ 269 do { \ 270 CHECK_FIFO_CONSISTENCY(anchor); \ 271 \ 272 (pentry)->nextlink = NULL; \ 273 if (NULL != (anchor).pptail) { \ 274 (*((anchor).pptail))->nextlink = (pentry); \ 275 (anchor).pptail = \ 276 &(*((anchor).pptail))->nextlink; \ 277 } else { \ 278 (anchor).phead = (pentry); \ 279 (anchor).pptail = &(anchor).phead; \ 280 } \ 281 \ 282 CHECK_FIFO_CONSISTENCY(anchor); \ 283 } while (FALSE) 284 285 #define UNLINK_FIFO(punlinked, anchor, nextlink) \ 286 do { \ 287 CHECK_FIFO_CONSISTENCY(anchor); \ 288 \ 289 (punlinked) = (anchor).phead; \ 290 if (NULL != (punlinked)) { \ 291 (anchor).phead = (punlinked)->nextlink; \ 292 if (NULL == (anchor).phead) \ 293 (anchor).pptail = NULL; \ 294 else if ((anchor).pptail == \ 295 &(punlinked)->nextlink) \ 296 (anchor).pptail = &(anchor).phead; \ 297 MAYBE_Z_LISTS((punlinked)->nextlink); \ 298 CHECK_FIFO_CONSISTENCY(anchor); \ 299 } \ 300 } while (FALSE) 301 302 #define UNLINK_MID_FIFO(punlinked, anchor, tounlink, nextlink, \ 303 entrytype) \ 304 do { \ 305 entrytype **ppentry; \ 306 \ 307 CHECK_FIFO_CONSISTENCY(anchor); \ 308 \ 309 ppentry = &(anchor).phead; \ 310 \ 311 while ((tounlink) != *ppentry) \ 312 if ((*ppentry)->nextlink != NULL) { \ 313 ppentry = &((*ppentry)->nextlink); \ 314 } else { \ 315 ppentry = NULL; \ 316 break; \ 317 } \ 318 \ 319 if (ppentry != NULL) { \ 320 (punlinked) = *ppentry; \ 321 *ppentry = (punlinked)->nextlink; \ 322 if (NULL == *ppentry) \ 323 (anchor).pptail = NULL; \ 324 else if ((anchor).pptail == \ 325 &(punlinked)->nextlink) \ 326 (anchor).pptail = &(anchor).phead; \ 327 MAYBE_Z_LISTS((punlinked)->nextlink); \ 328 CHECK_FIFO_CONSISTENCY(anchor); \ 329 } else { \ 330 (punlinked) = NULL; \ 331 } \ 332 } while (FALSE) 333 334 #define CONCAT_FIFO(f1, f2, nextlink) \ 335 do { \ 336 CHECK_FIFO_CONSISTENCY(f1); \ 337 CHECK_FIFO_CONSISTENCY(f2); \ 338 \ 339 if ((f2).pptail != NULL) { \ 340 if ((f1).pptail != NULL) { \ 341 (*(f1).pptail)->nextlink = (f2).phead; \ 342 if ((f2).pptail == &(f2).phead) \ 343 (f1).pptail = \ 344 &(*(f1).pptail)->nextlink; \ 345 else \ 346 (f1).pptail = (f2).pptail; \ 347 CHECK_FIFO_CONSISTENCY(f1); \ 348 } else { \ 349 (f1) = (f2); \ 350 } \ 351 MAYBE_Z_LISTS((f2).phead); \ 352 MAYBE_Z_LISTS((f2).pptail); \ 353 } \ 354 } while (FALSE) 355 356 /* 357 * DLIST 358 */ 359 #define DECL_DLIST_LINK(entrytype, link) \ 360 struct { \ 361 entrytype * b; \ 362 entrytype * f; \ 363 } link 364 365 #define INIT_DLIST(listhead, link) \ 366 do { \ 367 (listhead).link.f = &(listhead); \ 368 (listhead).link.b = &(listhead); \ 369 } while (FALSE) 370 371 #define HEAD_DLIST(listhead, link) \ 372 ( \ 373 (&(listhead) != (listhead).link.f) \ 374 ? (listhead).link.f \ 375 : NULL \ 376 ) 377 378 #define TAIL_DLIST(listhead, link) \ 379 ( \ 380 (&(listhead) != (listhead).link.b) \ 381 ? (listhead).link.b \ 382 : NULL \ 383 ) 384 385 #define NEXT_DLIST(listhead, entry, link) \ 386 ( \ 387 (&(listhead) != (entry)->link.f) \ 388 ? (entry)->link.f \ 389 : NULL \ 390 ) 391 392 #define PREV_DLIST(listhead, entry, link) \ 393 ( \ 394 (&(listhead) != (entry)->link.b) \ 395 ? (entry)->link.b \ 396 : NULL \ 397 ) 398 399 #define LINK_DLIST(listhead, pentry, link) \ 400 do { \ 401 (pentry)->link.f = (listhead).link.f; \ 402 (pentry)->link.b = &(listhead); \ 403 (listhead).link.f->link.b = (pentry); \ 404 (listhead).link.f = (pentry); \ 405 } while (FALSE) 406 407 #define LINK_TAIL_DLIST(listhead, pentry, link) \ 408 do { \ 409 (pentry)->link.b = (listhead).link.b; \ 410 (pentry)->link.f = &(listhead); \ 411 (listhead).link.b->link.f = (pentry); \ 412 (listhead).link.b = (pentry); \ 413 } while (FALSE) 414 415 #define UNLINK_DLIST(ptounlink, link) \ 416 do { \ 417 (ptounlink)->link.b->link.f = (ptounlink)->link.f; \ 418 (ptounlink)->link.f->link.b = (ptounlink)->link.b; \ 419 MAYBE_Z_LISTS((ptounlink)->link.b); \ 420 MAYBE_Z_LISTS((ptounlink)->link.f); \ 421 } while (FALSE) 422 423 #define ITER_DLIST_BEGIN(listhead, iter, link, entrytype) \ 424 { \ 425 entrytype *i_dl_nextiter; \ 426 \ 427 for ((iter) = (listhead).link.f; \ 428 (iter) != &(listhead) \ 429 && ((i_dl_nextiter = (iter)->link.f), TRUE); \ 430 (iter) = i_dl_nextiter) { 431 #define ITER_DLIST_END() \ 432 } \ 433 } 434 435 #define REV_ITER_DLIST_BEGIN(listhead, iter, link, entrytype) \ 436 { \ 437 entrytype *i_dl_nextiter; \ 438 \ 439 for ((iter) = (listhead).link.b; \ 440 (iter) != &(listhead) \ 441 && ((i_dl_nextiter = (iter)->link.b), TRUE); \ 442 (iter) = i_dl_nextiter) { 443 #define REV_ITER_DLIST_END() \ 444 } \ 445 } 446 447 #endif /* NTP_LISTS_H */ 448