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: NTP_INSIST(pentry != pentry->nextlink); \
220: NTP_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 */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ntp_lists.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / ntp / include