1 /* $NetBSD: ntp_lists.h,v 1.6 2020/05/25 20:47:19 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 (NULL == *ppentry || (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 do { \ 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 } while (FALSE) 208 209 #define UNLINK_SLIST(punlinked, listhead, ptounlink, nextlink, \ 210 entrytype) \ 211 UNLINK_EXPR_SLIST(punlinked, listhead, (ptounlink) == \ 212 U_E_S_CUR(), nextlink, entrytype) 213 214 #define CHECK_SLIST(listhead, nextlink, entrytype) \ 215 do { \ 216 entrytype *pentry; \ 217 \ 218 for (pentry = (listhead); \ 219 pentry != NULL; \ 220 pentry = pentry->nextlink) { \ 221 INSIST(pentry != pentry->nextlink); \ 222 INSIST((listhead) != pentry->nextlink); \ 223 } \ 224 } while (FALSE) 225 226 /* 227 * FIFO 228 */ 229 230 #define DECL_FIFO_ANCHOR(entrytype) \ 231 struct { \ 232 entrytype * phead; /* NULL if list empty */ \ 233 entrytype ** pptail; /* NULL if list empty */ \ 234 } 235 236 #define HEAD_FIFO(anchor) ((anchor).phead) 237 #define TAIL_FIFO(anchor) ((NULL == (anchor).pptail) \ 238 ? NULL \ 239 : *((anchor).pptail)) 240 241 /* 242 * For DEBUG builds only, verify both or neither of the anchor pointers 243 * are NULL with each operation. 244 */ 245 #if !defined(NTP_DEBUG_LISTS_H) 246 #define CHECK_FIFO_CONSISTENCY(anchor) do { } while (FALSE) 247 #else 248 #define CHECK_FIFO_CONSISTENCY(anchor) \ 249 check_gen_fifo_consistency(&(anchor)) 250 void check_gen_fifo_consistency(void *fifo); 251 #endif 252 253 /* 254 * generic FIFO element used to access any FIFO where each element 255 * begins with the link pointer 256 */ 257 typedef struct gen_node_tag gen_node; 258 struct gen_node_tag { 259 gen_node * link; 260 }; 261 262 /* generic FIFO */ 263 typedef DECL_FIFO_ANCHOR(gen_node) gen_fifo; 264 265 266 #define LINK_FIFO(anchor, pentry, nextlink) \ 267 do { \ 268 CHECK_FIFO_CONSISTENCY(anchor); \ 269 \ 270 (pentry)->nextlink = NULL; \ 271 if (NULL != (anchor).pptail) { \ 272 (*((anchor).pptail))->nextlink = (pentry); \ 273 (anchor).pptail = \ 274 &(*((anchor).pptail))->nextlink; \ 275 } else { \ 276 (anchor).phead = (pentry); \ 277 (anchor).pptail = &(anchor).phead; \ 278 } \ 279 \ 280 CHECK_FIFO_CONSISTENCY(anchor); \ 281 } while (FALSE) 282 283 #define UNLINK_FIFO(punlinked, anchor, nextlink) \ 284 do { \ 285 CHECK_FIFO_CONSISTENCY(anchor); \ 286 \ 287 (punlinked) = (anchor).phead; \ 288 if (NULL != (punlinked)) { \ 289 (anchor).phead = (punlinked)->nextlink; \ 290 if (NULL == (anchor).phead) \ 291 (anchor).pptail = NULL; \ 292 else if ((anchor).pptail == \ 293 &(punlinked)->nextlink) \ 294 (anchor).pptail = &(anchor).phead; \ 295 MAYBE_Z_LISTS((punlinked)->nextlink); \ 296 CHECK_FIFO_CONSISTENCY(anchor); \ 297 } \ 298 } while (FALSE) 299 300 #define UNLINK_MID_FIFO(punlinked, anchor, tounlink, nextlink, \ 301 entrytype) \ 302 do { \ 303 entrytype **ppentry; \ 304 \ 305 CHECK_FIFO_CONSISTENCY(anchor); \ 306 \ 307 ppentry = &(anchor).phead; \ 308 \ 309 while ((tounlink) != *ppentry) \ 310 if ((*ppentry)->nextlink != NULL) { \ 311 ppentry = &((*ppentry)->nextlink); \ 312 } else { \ 313 ppentry = NULL; \ 314 break; \ 315 } \ 316 \ 317 if (ppentry != NULL) { \ 318 (punlinked) = *ppentry; \ 319 *ppentry = (punlinked)->nextlink; \ 320 if (NULL == *ppentry) \ 321 (anchor).pptail = NULL; \ 322 else if ((anchor).pptail == \ 323 &(punlinked)->nextlink) \ 324 (anchor).pptail = &(anchor).phead; \ 325 MAYBE_Z_LISTS((punlinked)->nextlink); \ 326 CHECK_FIFO_CONSISTENCY(anchor); \ 327 } else { \ 328 (punlinked) = NULL; \ 329 } \ 330 } while (FALSE) 331 332 #define CONCAT_FIFO(f1, f2, nextlink) \ 333 do { \ 334 CHECK_FIFO_CONSISTENCY(f1); \ 335 CHECK_FIFO_CONSISTENCY(f2); \ 336 \ 337 if ((f2).pptail != NULL) { \ 338 if ((f1).pptail != NULL) { \ 339 (*(f1).pptail)->nextlink = (f2).phead; \ 340 if ((f2).pptail == &(f2).phead) \ 341 (f1).pptail = \ 342 &(*(f1).pptail)->nextlink; \ 343 else \ 344 (f1).pptail = (f2).pptail; \ 345 CHECK_FIFO_CONSISTENCY(f1); \ 346 } else { \ 347 (f1) = (f2); \ 348 } \ 349 MAYBE_Z_LISTS((f2).phead); \ 350 MAYBE_Z_LISTS((f2).pptail); \ 351 } \ 352 } while (FALSE) 353 354 /* 355 * DLIST 356 */ 357 #define DECL_DLIST_LINK(entrytype, link) \ 358 struct { \ 359 entrytype * b; \ 360 entrytype * f; \ 361 } link 362 363 #define INIT_DLIST(listhead, link) \ 364 do { \ 365 (listhead).link.f = &(listhead); \ 366 (listhead).link.b = &(listhead); \ 367 } while (FALSE) 368 369 #define HEAD_DLIST(listhead, link) \ 370 ( \ 371 (&(listhead) != (listhead).link.f) \ 372 ? (listhead).link.f \ 373 : NULL \ 374 ) 375 376 #define TAIL_DLIST(listhead, link) \ 377 ( \ 378 (&(listhead) != (listhead).link.b) \ 379 ? (listhead).link.b \ 380 : NULL \ 381 ) 382 383 #define NEXT_DLIST(listhead, entry, link) \ 384 ( \ 385 (&(listhead) != (entry)->link.f) \ 386 ? (entry)->link.f \ 387 : NULL \ 388 ) 389 390 #define PREV_DLIST(listhead, entry, link) \ 391 ( \ 392 (&(listhead) != (entry)->link.b) \ 393 ? (entry)->link.b \ 394 : NULL \ 395 ) 396 397 #define LINK_DLIST(listhead, pentry, link) \ 398 do { \ 399 (pentry)->link.f = (listhead).link.f; \ 400 (pentry)->link.b = &(listhead); \ 401 (listhead).link.f->link.b = (pentry); \ 402 (listhead).link.f = (pentry); \ 403 } while (FALSE) 404 405 #define LINK_TAIL_DLIST(listhead, pentry, link) \ 406 do { \ 407 (pentry)->link.b = (listhead).link.b; \ 408 (pentry)->link.f = &(listhead); \ 409 (listhead).link.b->link.f = (pentry); \ 410 (listhead).link.b = (pentry); \ 411 } while (FALSE) 412 413 #define UNLINK_DLIST(ptounlink, link) \ 414 do { \ 415 (ptounlink)->link.b->link.f = (ptounlink)->link.f; \ 416 (ptounlink)->link.f->link.b = (ptounlink)->link.b; \ 417 MAYBE_Z_LISTS((ptounlink)->link.b); \ 418 MAYBE_Z_LISTS((ptounlink)->link.f); \ 419 } while (FALSE) 420 421 #define ITER_DLIST_BEGIN(listhead, iter, link, entrytype) \ 422 { \ 423 entrytype *i_dl_nextiter; \ 424 \ 425 for ((iter) = (listhead).link.f; \ 426 (iter) != &(listhead) \ 427 && ((i_dl_nextiter = (iter)->link.f), TRUE); \ 428 (iter) = i_dl_nextiter) { 429 #define ITER_DLIST_END() \ 430 } \ 431 } 432 433 #define REV_ITER_DLIST_BEGIN(listhead, iter, link, entrytype) \ 434 { \ 435 entrytype *i_dl_nextiter; \ 436 \ 437 for ((iter) = (listhead).link.b; \ 438 (iter) != &(listhead) \ 439 && ((i_dl_nextiter = (iter)->link.b), TRUE); \ 440 (iter) = i_dl_nextiter) { 441 #define REV_ITER_DLIST_END() \ 442 } \ 443 } 444 445 #endif /* NTP_LISTS_H */ 446