contrib/ntp/include/ntp_lists.h

   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 */