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