1290001Sglebius/* 2290001Sglebius * ntp_lists.h - linked lists common code 3290001Sglebius * 4290001Sglebius * SLIST: singly-linked lists 5290001Sglebius * ========================== 6290001Sglebius * 7290001Sglebius * These macros implement a simple singly-linked list template. Both 8290001Sglebius * the listhead and per-entry next fields are declared as pointers to 9290001Sglebius * the list entry struct type. Initialization to NULL is typically 10290001Sglebius * implicit (for globals and statics) or handled by zeroing of the 11290001Sglebius * containing structure. 12290001Sglebius * 13290001Sglebius * The name of the next link field is passed as an argument to allow 14290001Sglebius * membership in several lists at once using multiple next link fields. 15290001Sglebius * 16290001Sglebius * When possible, placing the link field first in the entry structure 17290001Sglebius * allows slightly smaller code to be generated on some platforms. 18290001Sglebius * 19290001Sglebius * LINK_SLIST(listhead, pentry, nextlink) 20290001Sglebius * add entry at head 21290001Sglebius * 22290001Sglebius * LINK_TAIL_SLIST(listhead, pentry, nextlink, entrytype) 23290001Sglebius * add entry at tail. This is O(n), if this is a common 24290001Sglebius * operation the FIFO template may be more appropriate. 25290001Sglebius * 26290001Sglebius * LINK_SORT_SLIST(listhead, pentry, beforecur, nextlink, entrytype) 27290001Sglebius * add entry in sorted order. beforecur is an expression comparing 28290001Sglebius * pentry with the current list entry. The current entry can be 29290001Sglebius * referenced within beforecur as L_S_S_CUR(), which is short for 30290001Sglebius * LINK_SORT_SLIST_CUR(). beforecur is nonzero if pentry sorts 31290001Sglebius * before L_S_S_CUR(). 32290001Sglebius * 33290001Sglebius * UNLINK_HEAD_SLIST(punlinked, listhead, nextlink) 34290001Sglebius * unlink first entry and point punlinked to it, or set punlinked 35290001Sglebius * to NULL if the list is empty. 36290001Sglebius * 37290001Sglebius * UNLINK_SLIST(punlinked, listhead, ptounlink, nextlink, entrytype) 38290001Sglebius * unlink entry pointed to by ptounlink. punlinked is set to NULL 39290001Sglebius * if the entry is not found on the list, otherwise it is set to 40290001Sglebius * ptounlink. 41290001Sglebius * 42290001Sglebius * UNLINK_EXPR_SLIST(punlinked, listhead, expr, nextlink, entrytype) 43290001Sglebius * unlink entry where expression expr is nonzero. expr can refer 44290001Sglebius * to the entry being tested using UNLINK_EXPR_SLIST_CURRENT(), 45290001Sglebius * alias U_E_S_CUR(). See the implementation of UNLINK_SLIST() 46290001Sglebius * below for an example. U_E_S_CUR() is NULL iff the list is empty. 47290001Sglebius * punlinked is pointed to the removed entry or NULL if none 48290001Sglebius * satisfy expr. 49290001Sglebius * 50290001Sglebius * FIFO: singly-linked lists plus tail pointer 51290001Sglebius * =========================================== 52290001Sglebius * 53290001Sglebius * This is the same as FreeBSD's sys/queue.h STAILQ -- a singly-linked 54290001Sglebius * list implementation with tail-pointer maintenance, so that adding 55290001Sglebius * at the tail for first-in, first-out access is O(1). 56290001Sglebius * 57290001Sglebius * DECL_FIFO_ANCHOR(entrytype) 58290001Sglebius * provides the type specification portion of the declaration for 59290001Sglebius * a variable to refer to a FIFO queue (similar to listhead). The 60290001Sglebius * anchor contains the head and indirect tail pointers. Example: 61290001Sglebius * 62290001Sglebius * #include "ntp_lists.h" 63290001Sglebius * 64290001Sglebius * typedef struct myentry_tag myentry; 65290001Sglebius * struct myentry_tag { 66290001Sglebius * myentry *next_link; 67290001Sglebius * ... 68290001Sglebius * }; 69290001Sglebius * 70290001Sglebius * DECL_FIFO_ANCHOR(myentry) my_fifo; 71290001Sglebius * 72290001Sglebius * void somefunc(myentry *pentry) 73290001Sglebius * { 74290001Sglebius * LINK_FIFO(my_fifo, pentry, next_link); 75290001Sglebius * } 76290001Sglebius * 77290001Sglebius * If DECL_FIFO_ANCHOR is used with stack or heap storage, it 78290001Sglebius * should be initialized to NULL pointers using a = { NULL }; 79290001Sglebius * initializer or memset. 80290001Sglebius * 81290001Sglebius * HEAD_FIFO(anchor) 82290001Sglebius * TAIL_FIFO(anchor) 83290001Sglebius * Pointer to first/last entry, NULL if FIFO is empty. 84290001Sglebius * 85290001Sglebius * LINK_FIFO(anchor, pentry, nextlink) 86290001Sglebius * add entry at tail. 87290001Sglebius * 88290001Sglebius * UNLINK_FIFO(punlinked, anchor, nextlink) 89290001Sglebius * unlink head entry and point punlinked to it, or set punlinked 90290001Sglebius * to NULL if the list is empty. 91290001Sglebius * 92290001Sglebius * CONCAT_FIFO(q1, q2, nextlink) 93290001Sglebius * empty fifoq q2 moving its nodes to q1 following q1's existing 94290001Sglebius * nodes. 95290001Sglebius * 96290001Sglebius * DLIST: doubly-linked lists 97290001Sglebius * ========================== 98290001Sglebius * 99290001Sglebius * Elements on DLISTs always have non-NULL forward and back links, 100290001Sglebius * because both link chains are circular. The beginning/end is marked 101290001Sglebius * by the listhead, which is the same type as elements for simplicity. 102290001Sglebius * An empty list's listhead has both links set to its own address. 103290001Sglebius * 104290001Sglebius * 105290001Sglebius */ 106290001Sglebius#ifndef NTP_LISTS_H 107290001Sglebius#define NTP_LISTS_H 108290001Sglebius 109290001Sglebius#include "ntp_types.h" /* TRUE and FALSE */ 110290001Sglebius#include "ntp_assert.h" 111290001Sglebius 112290001Sglebius#ifdef DEBUG 113290001Sglebius# define NTP_DEBUG_LISTS_H 114290001Sglebius#endif 115290001Sglebius 116290001Sglebius/* 117290001Sglebius * If list debugging is not enabled, save a little time by not clearing 118290001Sglebius * an entry's link pointer when it is unlinked, as the stale pointer 119290001Sglebius * is harmless as long as it is ignored when the entry is not in a 120290001Sglebius * list. 121290001Sglebius */ 122290001Sglebius#ifndef NTP_DEBUG_LISTS_H 123290001Sglebius#define MAYBE_Z_LISTS(p) do { } while (FALSE) 124290001Sglebius#else 125290001Sglebius#define MAYBE_Z_LISTS(p) (p) = NULL 126290001Sglebius#endif 127290001Sglebius 128290001Sglebius#define LINK_SLIST(listhead, pentry, nextlink) \ 129290001Sglebiusdo { \ 130290001Sglebius (pentry)->nextlink = (listhead); \ 131290001Sglebius (listhead) = (pentry); \ 132290001Sglebius} while (FALSE) 133290001Sglebius 134290001Sglebius#define LINK_TAIL_SLIST(listhead, pentry, nextlink, entrytype) \ 135290001Sglebiusdo { \ 136290001Sglebius entrytype **pptail; \ 137290001Sglebius \ 138290001Sglebius pptail = &(listhead); \ 139290001Sglebius while (*pptail != NULL) \ 140290001Sglebius pptail = &((*pptail)->nextlink); \ 141290001Sglebius \ 142290001Sglebius (pentry)->nextlink = NULL; \ 143290001Sglebius *pptail = (pentry); \ 144290001Sglebius} while (FALSE) 145290001Sglebius 146290001Sglebius#define LINK_SORT_SLIST_CURRENT() (*ppentry) 147290001Sglebius#define L_S_S_CUR() LINK_SORT_SLIST_CURRENT() 148290001Sglebius 149290001Sglebius#define LINK_SORT_SLIST(listhead, pentry, beforecur, nextlink, \ 150290001Sglebius entrytype) \ 151290001Sglebiusdo { \ 152290001Sglebius entrytype **ppentry; \ 153290001Sglebius \ 154290001Sglebius ppentry = &(listhead); \ 155290001Sglebius while (TRUE) { \ 156290001Sglebius if (NULL == *ppentry || (beforecur)) { \ 157290001Sglebius (pentry)->nextlink = *ppentry; \ 158290001Sglebius *ppentry = (pentry); \ 159290001Sglebius break; \ 160290001Sglebius } \ 161290001Sglebius ppentry = &((*ppentry)->nextlink); \ 162290001Sglebius if (NULL == *ppentry) { \ 163290001Sglebius (pentry)->nextlink = NULL; \ 164290001Sglebius *ppentry = (pentry); \ 165290001Sglebius break; \ 166290001Sglebius } \ 167290001Sglebius } \ 168290001Sglebius} while (FALSE) 169290001Sglebius 170290001Sglebius#define UNLINK_HEAD_SLIST(punlinked, listhead, nextlink) \ 171290001Sglebiusdo { \ 172290001Sglebius (punlinked) = (listhead); \ 173290001Sglebius if (NULL != (punlinked)) { \ 174290001Sglebius (listhead) = (punlinked)->nextlink; \ 175290001Sglebius MAYBE_Z_LISTS((punlinked)->nextlink); \ 176290001Sglebius } \ 177290001Sglebius} while (FALSE) 178290001Sglebius 179290001Sglebius#define UNLINK_EXPR_SLIST_CURRENT() (*ppentry) 180290001Sglebius#define U_E_S_CUR() UNLINK_EXPR_SLIST_CURRENT() 181290001Sglebius 182290001Sglebius#define UNLINK_EXPR_SLIST(punlinked, listhead, expr, nextlink, \ 183290001Sglebius entrytype) \ 184290001Sglebiusdo { \ 185290001Sglebius entrytype **ppentry; \ 186290001Sglebius \ 187290001Sglebius ppentry = &(listhead); \ 188290001Sglebius \ 189290001Sglebius while (!(expr)) \ 190290001Sglebius if (*ppentry != NULL && \ 191290001Sglebius (*ppentry)->nextlink != NULL) { \ 192290001Sglebius ppentry = &((*ppentry)->nextlink); \ 193290001Sglebius } else { \ 194290001Sglebius ppentry = NULL; \ 195290001Sglebius break; \ 196290001Sglebius } \ 197290001Sglebius \ 198290001Sglebius if (ppentry != NULL) { \ 199290001Sglebius (punlinked) = *ppentry; \ 200290001Sglebius *ppentry = (punlinked)->nextlink; \ 201290001Sglebius MAYBE_Z_LISTS((punlinked)->nextlink); \ 202290001Sglebius } else { \ 203290001Sglebius (punlinked) = NULL; \ 204290001Sglebius } \ 205290001Sglebius} while (FALSE) 206290001Sglebius 207290001Sglebius#define UNLINK_SLIST(punlinked, listhead, ptounlink, nextlink, \ 208290001Sglebius entrytype) \ 209290001Sglebius UNLINK_EXPR_SLIST(punlinked, listhead, (ptounlink) == \ 210290001Sglebius U_E_S_CUR(), nextlink, entrytype) 211290001Sglebius 212290001Sglebius#define CHECK_SLIST(listhead, nextlink, entrytype) \ 213290001Sglebiusdo { \ 214290001Sglebius entrytype *pentry; \ 215290001Sglebius \ 216290001Sglebius for (pentry = (listhead); \ 217290001Sglebius pentry != NULL; \ 218290001Sglebius pentry = pentry->nextlink) { \ 219290001Sglebius INSIST(pentry != pentry->nextlink); \ 220290001Sglebius INSIST((listhead) != pentry->nextlink); \ 221290001Sglebius } \ 222290001Sglebius} while (FALSE) 223290001Sglebius 224290001Sglebius/* 225290001Sglebius * FIFO 226290001Sglebius */ 227290001Sglebius 228290001Sglebius#define DECL_FIFO_ANCHOR(entrytype) \ 229290001Sglebiusstruct { \ 230290001Sglebius entrytype * phead; /* NULL if list empty */ \ 231290001Sglebius entrytype ** pptail; /* NULL if list empty */ \ 232290001Sglebius} 233290001Sglebius 234290001Sglebius#define HEAD_FIFO(anchor) ((anchor).phead) 235290001Sglebius#define TAIL_FIFO(anchor) ((NULL == (anchor).pptail) \ 236290001Sglebius ? NULL \ 237290001Sglebius : *((anchor).pptail)) 238290001Sglebius 239290001Sglebius/* 240290001Sglebius * For DEBUG builds only, verify both or neither of the anchor pointers 241290001Sglebius * are NULL with each operation. 242290001Sglebius */ 243290001Sglebius#if !defined(NTP_DEBUG_LISTS_H) 244290001Sglebius#define CHECK_FIFO_CONSISTENCY(anchor) do { } while (FALSE) 245290001Sglebius#else 246290001Sglebius#define CHECK_FIFO_CONSISTENCY(anchor) \ 247290001Sglebius check_gen_fifo_consistency(&(anchor)) 248290001Sglebiusvoid check_gen_fifo_consistency(void *fifo); 249290001Sglebius#endif 250290001Sglebius 251290001Sglebius/* 252290001Sglebius * generic FIFO element used to access any FIFO where each element 253290001Sglebius * begins with the link pointer 254290001Sglebius */ 255290001Sglebiustypedef struct gen_node_tag gen_node; 256290001Sglebiusstruct gen_node_tag { 257290001Sglebius gen_node * link; 258290001Sglebius}; 259290001Sglebius 260290001Sglebius/* generic FIFO */ 261290001Sglebiustypedef DECL_FIFO_ANCHOR(gen_node) gen_fifo; 262290001Sglebius 263290001Sglebius 264290001Sglebius#define LINK_FIFO(anchor, pentry, nextlink) \ 265290001Sglebiusdo { \ 266290001Sglebius CHECK_FIFO_CONSISTENCY(anchor); \ 267290001Sglebius \ 268290001Sglebius (pentry)->nextlink = NULL; \ 269290001Sglebius if (NULL != (anchor).pptail) { \ 270290001Sglebius (*((anchor).pptail))->nextlink = (pentry); \ 271290001Sglebius (anchor).pptail = \ 272290001Sglebius &(*((anchor).pptail))->nextlink; \ 273290001Sglebius } else { \ 274290001Sglebius (anchor).phead = (pentry); \ 275290001Sglebius (anchor).pptail = &(anchor).phead; \ 276290001Sglebius } \ 277290001Sglebius \ 278290001Sglebius CHECK_FIFO_CONSISTENCY(anchor); \ 279290001Sglebius} while (FALSE) 280290001Sglebius 281290001Sglebius#define UNLINK_FIFO(punlinked, anchor, nextlink) \ 282290001Sglebiusdo { \ 283290001Sglebius CHECK_FIFO_CONSISTENCY(anchor); \ 284290001Sglebius \ 285290001Sglebius (punlinked) = (anchor).phead; \ 286290001Sglebius if (NULL != (punlinked)) { \ 287290001Sglebius (anchor).phead = (punlinked)->nextlink; \ 288290001Sglebius if (NULL == (anchor).phead) \ 289290001Sglebius (anchor).pptail = NULL; \ 290290001Sglebius else if ((anchor).pptail == \ 291290001Sglebius &(punlinked)->nextlink) \ 292290001Sglebius (anchor).pptail = &(anchor).phead; \ 293290001Sglebius MAYBE_Z_LISTS((punlinked)->nextlink); \ 294290001Sglebius CHECK_FIFO_CONSISTENCY(anchor); \ 295290001Sglebius } \ 296290001Sglebius} while (FALSE) 297290001Sglebius 298290001Sglebius#define UNLINK_MID_FIFO(punlinked, anchor, tounlink, nextlink, \ 299290001Sglebius entrytype) \ 300290001Sglebiusdo { \ 301290001Sglebius entrytype **ppentry; \ 302290001Sglebius \ 303290001Sglebius CHECK_FIFO_CONSISTENCY(anchor); \ 304290001Sglebius \ 305290001Sglebius ppentry = &(anchor).phead; \ 306290001Sglebius \ 307290001Sglebius while ((tounlink) != *ppentry) \ 308290001Sglebius if ((*ppentry)->nextlink != NULL) { \ 309290001Sglebius ppentry = &((*ppentry)->nextlink); \ 310290001Sglebius } else { \ 311290001Sglebius ppentry = NULL; \ 312290001Sglebius break; \ 313290001Sglebius } \ 314290001Sglebius \ 315290001Sglebius if (ppentry != NULL) { \ 316290001Sglebius (punlinked) = *ppentry; \ 317290001Sglebius *ppentry = (punlinked)->nextlink; \ 318290001Sglebius if (NULL == *ppentry) \ 319290001Sglebius (anchor).pptail = NULL; \ 320290001Sglebius else if ((anchor).pptail == \ 321290001Sglebius &(punlinked)->nextlink) \ 322290001Sglebius (anchor).pptail = &(anchor).phead; \ 323290001Sglebius MAYBE_Z_LISTS((punlinked)->nextlink); \ 324290001Sglebius CHECK_FIFO_CONSISTENCY(anchor); \ 325290001Sglebius } else { \ 326290001Sglebius (punlinked) = NULL; \ 327290001Sglebius } \ 328290001Sglebius} while (FALSE) 329290001Sglebius 330290001Sglebius#define CONCAT_FIFO(f1, f2, nextlink) \ 331290001Sglebiusdo { \ 332290001Sglebius CHECK_FIFO_CONSISTENCY(f1); \ 333290001Sglebius CHECK_FIFO_CONSISTENCY(f2); \ 334290001Sglebius \ 335290001Sglebius if ((f2).pptail != NULL) { \ 336290001Sglebius if ((f1).pptail != NULL) { \ 337290001Sglebius (*(f1).pptail)->nextlink = (f2).phead; \ 338290001Sglebius if ((f2).pptail == &(f2).phead) \ 339290001Sglebius (f1).pptail = \ 340290001Sglebius &(*(f1).pptail)->nextlink; \ 341290001Sglebius else \ 342290001Sglebius (f1).pptail = (f2).pptail; \ 343290001Sglebius CHECK_FIFO_CONSISTENCY(f1); \ 344290001Sglebius } else { \ 345290001Sglebius (f1) = (f2); \ 346290001Sglebius } \ 347290001Sglebius MAYBE_Z_LISTS((f2).phead); \ 348290001Sglebius MAYBE_Z_LISTS((f2).pptail); \ 349290001Sglebius } \ 350290001Sglebius} while (FALSE) 351290001Sglebius 352290001Sglebius/* 353290001Sglebius * DLIST 354290001Sglebius */ 355290001Sglebius#define DECL_DLIST_LINK(entrytype, link) \ 356290001Sglebiusstruct { \ 357290001Sglebius entrytype * b; \ 358290001Sglebius entrytype * f; \ 359290001Sglebius} link 360290001Sglebius 361290001Sglebius#define INIT_DLIST(listhead, link) \ 362290001Sglebiusdo { \ 363290001Sglebius (listhead).link.f = &(listhead); \ 364290001Sglebius (listhead).link.b = &(listhead); \ 365290001Sglebius} while (FALSE) 366290001Sglebius 367290001Sglebius#define HEAD_DLIST(listhead, link) \ 368290001Sglebius ( \ 369290001Sglebius (&(listhead) != (listhead).link.f) \ 370290001Sglebius ? (listhead).link.f \ 371290001Sglebius : NULL \ 372290001Sglebius ) 373290001Sglebius 374290001Sglebius#define TAIL_DLIST(listhead, link) \ 375290001Sglebius ( \ 376290001Sglebius (&(listhead) != (listhead).link.b) \ 377290001Sglebius ? (listhead).link.b \ 378290001Sglebius : NULL \ 379290001Sglebius ) 380290001Sglebius 381290001Sglebius#define NEXT_DLIST(listhead, entry, link) \ 382290001Sglebius ( \ 383290001Sglebius (&(listhead) != (entry)->link.f) \ 384290001Sglebius ? (entry)->link.f \ 385290001Sglebius : NULL \ 386290001Sglebius ) 387290001Sglebius 388290001Sglebius#define PREV_DLIST(listhead, entry, link) \ 389290001Sglebius ( \ 390290001Sglebius (&(listhead) != (entry)->link.b) \ 391290001Sglebius ? (entry)->link.b \ 392290001Sglebius : NULL \ 393290001Sglebius ) 394290001Sglebius 395290001Sglebius#define LINK_DLIST(listhead, pentry, link) \ 396290001Sglebiusdo { \ 397290001Sglebius (pentry)->link.f = (listhead).link.f; \ 398290001Sglebius (pentry)->link.b = &(listhead); \ 399290001Sglebius (listhead).link.f->link.b = (pentry); \ 400290001Sglebius (listhead).link.f = (pentry); \ 401290001Sglebius} while (FALSE) 402290001Sglebius 403290001Sglebius#define LINK_TAIL_DLIST(listhead, pentry, link) \ 404290001Sglebiusdo { \ 405290001Sglebius (pentry)->link.b = (listhead).link.b; \ 406290001Sglebius (pentry)->link.f = &(listhead); \ 407290001Sglebius (listhead).link.b->link.f = (pentry); \ 408290001Sglebius (listhead).link.b = (pentry); \ 409290001Sglebius} while (FALSE) 410290001Sglebius 411290001Sglebius#define UNLINK_DLIST(ptounlink, link) \ 412290001Sglebiusdo { \ 413290001Sglebius (ptounlink)->link.b->link.f = (ptounlink)->link.f; \ 414290001Sglebius (ptounlink)->link.f->link.b = (ptounlink)->link.b; \ 415290001Sglebius MAYBE_Z_LISTS((ptounlink)->link.b); \ 416290001Sglebius MAYBE_Z_LISTS((ptounlink)->link.f); \ 417290001Sglebius} while (FALSE) 418290001Sglebius 419290001Sglebius#define ITER_DLIST_BEGIN(listhead, iter, link, entrytype) \ 420290001Sglebius{ \ 421290001Sglebius entrytype *i_dl_nextiter; \ 422290001Sglebius \ 423290001Sglebius for ((iter) = (listhead).link.f; \ 424290001Sglebius (iter) != &(listhead) \ 425290001Sglebius && ((i_dl_nextiter = (iter)->link.f), TRUE); \ 426290001Sglebius (iter) = i_dl_nextiter) { 427290001Sglebius#define ITER_DLIST_END() \ 428290001Sglebius } \ 429290001Sglebius} 430290001Sglebius 431290001Sglebius#define REV_ITER_DLIST_BEGIN(listhead, iter, link, entrytype) \ 432290001Sglebius{ \ 433290001Sglebius entrytype *i_dl_nextiter; \ 434290001Sglebius \ 435290001Sglebius for ((iter) = (listhead).link.b; \ 436290001Sglebius (iter) != &(listhead) \ 437290001Sglebius && ((i_dl_nextiter = (iter)->link.b), TRUE); \ 438290001Sglebius (iter) = i_dl_nextiter) { 439290001Sglebius#define REV_ITER_DLIST_END() \ 440290001Sglebius } \ 441290001Sglebius} 442290001Sglebius 443290001Sglebius#endif /* NTP_LISTS_H */ 444