1178825Sdfr/* $NetBSD: ntp_lists.h,v 1.6 2020/05/25 20:47:19 christos Exp $ */ 2233294Sstas 3233294Sstas/* 4233294Sstas * ntp_lists.h - linked lists common code 5178825Sdfr * 6233294Sstas * SLIST: singly-linked lists 7233294Sstas * ========================== 8233294Sstas * 9178825Sdfr * These macros implement a simple singly-linked list template. Both 10233294Sstas * the listhead and per-entry next fields are declared as pointers to 11233294Sstas * the list entry struct type. Initialization to NULL is typically 12178825Sdfr * implicit (for globals and statics) or handled by zeroing of the 13233294Sstas * containing structure. 14233294Sstas * 15233294Sstas * The name of the next link field is passed as an argument to allow 16178825Sdfr * membership in several lists at once using multiple next link fields. 17233294Sstas * 18233294Sstas * When possible, placing the link field first in the entry structure 19233294Sstas * allows slightly smaller code to be generated on some platforms. 20178825Sdfr * 21233294Sstas * LINK_SLIST(listhead, pentry, nextlink) 22233294Sstas * add entry at head 23233294Sstas * 24233294Sstas * LINK_TAIL_SLIST(listhead, pentry, nextlink, entrytype) 25233294Sstas * add entry at tail. This is O(n), if this is a common 26233294Sstas * operation the FIFO template may be more appropriate. 27233294Sstas * 28233294Sstas * LINK_SORT_SLIST(listhead, pentry, beforecur, nextlink, entrytype) 29233294Sstas * add entry in sorted order. beforecur is an expression comparing 30233294Sstas * pentry with the current list entry. The current entry can be 31233294Sstas * referenced within beforecur as L_S_S_CUR(), which is short for 32178825Sdfr * LINK_SORT_SLIST_CUR(). beforecur is nonzero if pentry sorts 33178825Sdfr * before L_S_S_CUR(). 34178825Sdfr * 35178825Sdfr * UNLINK_HEAD_SLIST(punlinked, listhead, nextlink) 36178825Sdfr * unlink first entry and point punlinked to it, or set punlinked 37178825Sdfr * to NULL if the list is empty. 38178825Sdfr * 39178825Sdfr * UNLINK_SLIST(punlinked, listhead, ptounlink, nextlink, entrytype) 40178825Sdfr * unlink entry pointed to by ptounlink. punlinked is set to NULL 41178825Sdfr * if the entry is not found on the list, otherwise it is set to 42178825Sdfr * ptounlink. 43178825Sdfr * 44178825Sdfr * UNLINK_EXPR_SLIST(punlinked, listhead, expr, nextlink, entrytype) 45178825Sdfr * unlink entry where expression expr is nonzero. expr can refer 46178825Sdfr * to the entry being tested using UNLINK_EXPR_SLIST_CURRENT(), 47178825Sdfr * alias U_E_S_CUR(). See the implementation of UNLINK_SLIST() 48178825Sdfr * below for an example. U_E_S_CUR() is NULL iff the list is empty. 49178825Sdfr * punlinked is pointed to the removed entry or NULL if none 50178825Sdfr * satisfy expr. 51178825Sdfr * 52178825Sdfr * FIFO: singly-linked lists plus tail pointer 53233294Sstas * =========================================== 54178825Sdfr * 55178825Sdfr * This is the same as FreeBSD's sys/queue.h STAILQ -- a singly-linked 56178825Sdfr * list implementation with tail-pointer maintenance, so that adding 57178825Sdfr * at the tail for first-in, first-out access is O(1). 58178825Sdfr * 59178825Sdfr * DECL_FIFO_ANCHOR(entrytype) 60178825Sdfr * provides the type specification portion of the declaration for 61178825Sdfr * a variable to refer to a FIFO queue (similar to listhead). The 62178825Sdfr * anchor contains the head and indirect tail pointers. Example: 63178825Sdfr * 64178825Sdfr * #include "ntp_lists.h" 65178825Sdfr * 66178825Sdfr * typedef struct myentry_tag myentry; 67178825Sdfr * struct myentry_tag { 68178825Sdfr * myentry *next_link; 69178825Sdfr * ... 70178825Sdfr * }; 71178825Sdfr * 72178825Sdfr * DECL_FIFO_ANCHOR(myentry) my_fifo; 73178825Sdfr * 74178825Sdfr * void somefunc(myentry *pentry) 75178825Sdfr * { 76178825Sdfr * LINK_FIFO(my_fifo, pentry, next_link); 77178825Sdfr * } 78178825Sdfr * 79178825Sdfr * If DECL_FIFO_ANCHOR is used with stack or heap storage, it 80178825Sdfr * should be initialized to NULL pointers using a = { NULL }; 81178825Sdfr * initializer or memset. 82178825Sdfr * 83178825Sdfr * HEAD_FIFO(anchor) 84178825Sdfr * TAIL_FIFO(anchor) 85178825Sdfr * Pointer to first/last entry, NULL if FIFO is empty. 86178825Sdfr * 87178825Sdfr * LINK_FIFO(anchor, pentry, nextlink) 88178825Sdfr * add entry at tail. 89178825Sdfr * 90178825Sdfr * UNLINK_FIFO(punlinked, anchor, nextlink) 91178825Sdfr * unlink head entry and point punlinked to it, or set punlinked 92178825Sdfr * to NULL if the list is empty. 93178825Sdfr * 94178825Sdfr * CONCAT_FIFO(q1, q2, nextlink) 95178825Sdfr * empty fifoq q2 moving its nodes to q1 following q1's existing 96178825Sdfr * nodes. 97178825Sdfr * 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) \ 131do { \ 132 (pentry)->nextlink = (listhead); \ 133 (listhead) = (pentry); \ 134} while (FALSE) 135 136#define LINK_TAIL_SLIST(listhead, pentry, nextlink, entrytype) \ 137do { \ 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) \ 153do { \ 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) \ 173do { \ 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) \ 186do { \ 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) \ 215do { \ 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) \ 231struct { \ 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)) 250void 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 */ 257typedef struct gen_node_tag gen_node; 258struct gen_node_tag { 259 gen_node * link; 260}; 261 262/* generic FIFO */ 263typedef DECL_FIFO_ANCHOR(gen_node) gen_fifo; 264 265 266#define LINK_FIFO(anchor, pentry, nextlink) \ 267do { \ 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) \ 284do { \ 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) \ 302do { \ 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) \ 333do { \ 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) \ 358struct { \ 359 entrytype * b; \ 360 entrytype * f; \ 361} link 362 363#define INIT_DLIST(listhead, link) \ 364do { \ 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) \ 398do { \ 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) \ 406do { \ 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) \ 414do { \ 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