ntp_lists.h revision 289999 
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)			\
129do {								\
130	(pentry)->nextlink = (listhead);			\
131	(listhead) = (pentry);					\
132} while (FALSE)
133
134#define LINK_TAIL_SLIST(listhead, pentry, nextlink, entrytype)	\
135do {								\
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)				\
151do {								\
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)	\
171do {								\
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)				\
184do {								\
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)		\
213do {								\
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)				\
229struct {							\
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))
248void	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 */
255typedef struct gen_node_tag gen_node;
256struct gen_node_tag {
257	gen_node *	link;
258};
259
260/* generic FIFO */
261typedef DECL_FIFO_ANCHOR(gen_node) gen_fifo;
262
263
264#define LINK_FIFO(anchor, pentry, nextlink)			\
265do {								\
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)		\
282do {								\
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)				\
300do {								\
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)				\
331do {								\
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)			\
356struct {							\
357	entrytype *	b;					\
358	entrytype *	f;					\
359} link
360
361#define INIT_DLIST(listhead, link)				\
362do {								\
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)			\
396do {								\
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)			\
404do {								\
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)				\
412do {								\
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