2 * ntp_lists.h - linked lists common code
4 * SLIST: singly-linked lists
5 * ==========================
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.
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.
16 * When possible, placing the link field first in the entry structure
17 * allows slightly smaller code to be generated on some platforms.
19 * LINK_SLIST(listhead, pentry, nextlink)
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.
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
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.
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
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
50 * FIFO: singly-linked lists plus tail pointer
51 * ===========================================
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).
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:
62 * #include "ntp_lists.h"
64 * typedef struct myentry_tag myentry;
65 * struct myentry_tag {
70 * DECL_FIFO_ANCHOR(myentry) my_fifo;
72 * void somefunc(myentry *pentry)
74 * LINK_FIFO(my_fifo, pentry, next_link);
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.
83 * Pointer to first/last entry, NULL if FIFO is empty.
85 * LINK_FIFO(anchor, pentry, nextlink)
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.
92 * CONCAT_FIFO(q1, q2, nextlink)
93 * empty fifoq q2 moving its nodes to q1 following q1's existing
96 * DLIST: doubly-linked lists
97 * ==========================
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.
109 #include "ntp_types.h" /* TRUE and FALSE */
110 #include "ntp_assert.h"
113 # define NTP_DEBUG_LISTS_H
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
122 #ifndef NTP_DEBUG_LISTS_H
123 #define MAYBE_Z_LISTS(p) do { } while (FALSE)
125 #define MAYBE_Z_LISTS(p) (p) = NULL
128 #define LINK_SLIST(listhead, pentry, nextlink) \
130 (pentry)->nextlink = (listhead); \
131 (listhead) = (pentry); \
134 #define LINK_TAIL_SLIST(listhead, pentry, nextlink, entrytype) \
136 entrytype **pptail; \
138 pptail = &(listhead); \
139 while (*pptail != NULL) \
140 pptail = &((*pptail)->nextlink); \
142 (pentry)->nextlink = NULL; \
143 *pptail = (pentry); \
146 #define LINK_SORT_SLIST_CURRENT() (*ppentry)
147 #define L_S_S_CUR() LINK_SORT_SLIST_CURRENT()
149 #define LINK_SORT_SLIST(listhead, pentry, beforecur, nextlink, \
152 entrytype **ppentry; \
154 ppentry = &(listhead); \
156 if (NULL == *ppentry || (beforecur)) { \
157 (pentry)->nextlink = *ppentry; \
158 *ppentry = (pentry); \
161 ppentry = &((*ppentry)->nextlink); \
162 if (NULL == *ppentry) { \
163 (pentry)->nextlink = NULL; \
164 *ppentry = (pentry); \
170 #define UNLINK_HEAD_SLIST(punlinked, listhead, nextlink) \
172 (punlinked) = (listhead); \
173 if (NULL != (punlinked)) { \
174 (listhead) = (punlinked)->nextlink; \
175 MAYBE_Z_LISTS((punlinked)->nextlink); \
179 #define UNLINK_EXPR_SLIST_CURRENT() (*ppentry)
180 #define U_E_S_CUR() UNLINK_EXPR_SLIST_CURRENT()
182 #define UNLINK_EXPR_SLIST(punlinked, listhead, expr, nextlink, \
185 entrytype **ppentry; \
187 ppentry = &(listhead); \
190 if (*ppentry != NULL && \
191 (*ppentry)->nextlink != NULL) { \
192 ppentry = &((*ppentry)->nextlink); \
198 if (ppentry != NULL) { \
199 (punlinked) = *ppentry; \
200 *ppentry = (punlinked)->nextlink; \
201 MAYBE_Z_LISTS((punlinked)->nextlink); \
203 (punlinked) = NULL; \
207 #define UNLINK_SLIST(punlinked, listhead, ptounlink, nextlink, \
209 UNLINK_EXPR_SLIST(punlinked, listhead, (ptounlink) == \
210 U_E_S_CUR(), nextlink, entrytype)
212 #define CHECK_SLIST(listhead, nextlink, entrytype) \
216 for (pentry = (listhead); \
218 pentry = pentry->nextlink) { \
219 INSIST(pentry != pentry->nextlink); \
220 INSIST((listhead) != pentry->nextlink); \
228 #define DECL_FIFO_ANCHOR(entrytype) \
230 entrytype * phead; /* NULL if list empty */ \
231 entrytype ** pptail; /* NULL if list empty */ \
234 #define HEAD_FIFO(anchor) ((anchor).phead)
235 #define TAIL_FIFO(anchor) ((NULL == (anchor).pptail) \
237 : *((anchor).pptail))
240 * For DEBUG builds only, verify both or neither of the anchor pointers
241 * are NULL with each operation.
243 #if !defined(NTP_DEBUG_LISTS_H)
244 #define CHECK_FIFO_CONSISTENCY(anchor) do { } while (FALSE)
246 #define CHECK_FIFO_CONSISTENCY(anchor) \
247 check_gen_fifo_consistency(&(anchor))
248 void check_gen_fifo_consistency(void *fifo);
252 * generic FIFO element used to access any FIFO where each element
253 * begins with the link pointer
255 typedef struct gen_node_tag gen_node;
256 struct gen_node_tag {
261 typedef DECL_FIFO_ANCHOR(gen_node) gen_fifo;
264 #define LINK_FIFO(anchor, pentry, nextlink) \
266 CHECK_FIFO_CONSISTENCY(anchor); \
268 (pentry)->nextlink = NULL; \
269 if (NULL != (anchor).pptail) { \
270 (*((anchor).pptail))->nextlink = (pentry); \
272 &(*((anchor).pptail))->nextlink; \
274 (anchor).phead = (pentry); \
275 (anchor).pptail = &(anchor).phead; \
278 CHECK_FIFO_CONSISTENCY(anchor); \
281 #define UNLINK_FIFO(punlinked, anchor, nextlink) \
283 CHECK_FIFO_CONSISTENCY(anchor); \
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); \
298 #define UNLINK_MID_FIFO(punlinked, anchor, tounlink, nextlink, \
301 entrytype **ppentry; \
303 CHECK_FIFO_CONSISTENCY(anchor); \
305 ppentry = &(anchor).phead; \
307 while ((tounlink) != *ppentry) \
308 if ((*ppentry)->nextlink != NULL) { \
309 ppentry = &((*ppentry)->nextlink); \
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); \
326 (punlinked) = NULL; \
330 #define CONCAT_FIFO(f1, f2, nextlink) \
332 CHECK_FIFO_CONSISTENCY(f1); \
333 CHECK_FIFO_CONSISTENCY(f2); \
335 if ((f2).pptail != NULL) { \
336 if ((f1).pptail != NULL) { \
337 (*(f1).pptail)->nextlink = (f2).phead; \
338 if ((f2).pptail == &(f2).phead) \
340 &(*(f1).pptail)->nextlink; \
342 (f1).pptail = (f2).pptail; \
343 CHECK_FIFO_CONSISTENCY(f1); \
347 MAYBE_Z_LISTS((f2).phead); \
348 MAYBE_Z_LISTS((f2).pptail); \
355 #define DECL_DLIST_LINK(entrytype, link) \
361 #define INIT_DLIST(listhead, link) \
363 (listhead).link.f = &(listhead); \
364 (listhead).link.b = &(listhead); \
367 #define HEAD_DLIST(listhead, link) \
369 (&(listhead) != (listhead).link.f) \
370 ? (listhead).link.f \
374 #define TAIL_DLIST(listhead, link) \
376 (&(listhead) != (listhead).link.b) \
377 ? (listhead).link.b \
381 #define NEXT_DLIST(listhead, entry, link) \
383 (&(listhead) != (entry)->link.f) \
388 #define PREV_DLIST(listhead, entry, link) \
390 (&(listhead) != (entry)->link.b) \
395 #define LINK_DLIST(listhead, pentry, link) \
397 (pentry)->link.f = (listhead).link.f; \
398 (pentry)->link.b = &(listhead); \
399 (listhead).link.f->link.b = (pentry); \
400 (listhead).link.f = (pentry); \
403 #define LINK_TAIL_DLIST(listhead, pentry, link) \
405 (pentry)->link.b = (listhead).link.b; \
406 (pentry)->link.f = &(listhead); \
407 (listhead).link.b->link.f = (pentry); \
408 (listhead).link.b = (pentry); \
411 #define UNLINK_DLIST(ptounlink, link) \
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); \
419 #define ITER_DLIST_BEGIN(listhead, iter, link, entrytype) \
421 entrytype *i_dl_nextiter; \
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() \
431 #define REV_ITER_DLIST_BEGIN(listhead, iter, link, entrytype) \
433 entrytype *i_dl_nextiter; \
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() \
443 #endif /* NTP_LISTS_H */