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 if (NULL != (listhead)) { \ 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 } else do { \ 206 (punlinked) = NULL; \ 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