xref: /minix3/lib/libc/include/isc/list.h (revision 2fe8fb192fe7e8720e3e7a77f928da545e872a6a)
1*2fe8fb19SBen Gras /*	$NetBSD: list.h,v 1.5 2009/04/12 17:07:16 christos Exp $	*/
2*2fe8fb19SBen Gras 
3*2fe8fb19SBen Gras /*
4*2fe8fb19SBen Gras  * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC")
5*2fe8fb19SBen Gras  * Copyright (c) 1997,1999 by Internet Software Consortium.
6*2fe8fb19SBen Gras  *
7*2fe8fb19SBen Gras  * Permission to use, copy, modify, and distribute this software for any
8*2fe8fb19SBen Gras  * purpose with or without fee is hereby granted, provided that the above
9*2fe8fb19SBen Gras  * copyright notice and this permission notice appear in all copies.
10*2fe8fb19SBen Gras  *
11*2fe8fb19SBen Gras  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
12*2fe8fb19SBen Gras  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13*2fe8fb19SBen Gras  * MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR
14*2fe8fb19SBen Gras  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15*2fe8fb19SBen Gras  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16*2fe8fb19SBen Gras  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
17*2fe8fb19SBen Gras  * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18*2fe8fb19SBen Gras  */
19*2fe8fb19SBen Gras 
20*2fe8fb19SBen Gras #ifndef LIST_H
21*2fe8fb19SBen Gras #define LIST_H 1
22*2fe8fb19SBen Gras #include <isc/assertions.h>
23*2fe8fb19SBen Gras 
24*2fe8fb19SBen Gras #define LIST(type) struct { type *head, *tail; }
25*2fe8fb19SBen Gras #define INIT_LIST(list) \
26*2fe8fb19SBen Gras 	do { (list).head = NULL; (list).tail = NULL; } while (/*CONSTCOND*/0)
27*2fe8fb19SBen Gras 
28*2fe8fb19SBen Gras #define LINK(type) struct { type *prev, *next; }
29*2fe8fb19SBen Gras #define INIT_LINK_TYPE(elt, link, type) \
30*2fe8fb19SBen Gras 	do { \
31*2fe8fb19SBen Gras 		(elt)->link.prev = (type *)(-1); \
32*2fe8fb19SBen Gras 		(elt)->link.next = (type *)(-1); \
33*2fe8fb19SBen Gras 	} while (/*CONSTCOND*/0)
34*2fe8fb19SBen Gras #define INIT_LINK(elt, link) \
35*2fe8fb19SBen Gras 	INIT_LINK_TYPE(elt, link, void)
36*2fe8fb19SBen Gras #define LINKED(elt, link) ((void *)((elt)->link.prev) != (void *)(-1) && \
37*2fe8fb19SBen Gras 			   (void *)((elt)->link.next) != (void *)(-1))
38*2fe8fb19SBen Gras 
39*2fe8fb19SBen Gras #define HEAD(list) ((list).head)
40*2fe8fb19SBen Gras #define TAIL(list) ((list).tail)
41*2fe8fb19SBen Gras #define EMPTY(list) ((list).head == NULL)
42*2fe8fb19SBen Gras 
43*2fe8fb19SBen Gras #define PREPEND(list, elt, link) \
44*2fe8fb19SBen Gras 	do { \
45*2fe8fb19SBen Gras 		INSIST(!LINKED(elt, link));\
46*2fe8fb19SBen Gras 		if ((list).head != NULL) \
47*2fe8fb19SBen Gras 			(list).head->link.prev = (elt); \
48*2fe8fb19SBen Gras 		else \
49*2fe8fb19SBen Gras 			(list).tail = (elt); \
50*2fe8fb19SBen Gras 		(elt)->link.prev = NULL; \
51*2fe8fb19SBen Gras 		(elt)->link.next = (list).head; \
52*2fe8fb19SBen Gras 		(list).head = (elt); \
53*2fe8fb19SBen Gras 	} while (/*CONSTCOND*/0)
54*2fe8fb19SBen Gras 
55*2fe8fb19SBen Gras #define APPEND(list, elt, link) \
56*2fe8fb19SBen Gras 	do { \
57*2fe8fb19SBen Gras 		INSIST(!LINKED(elt, link));\
58*2fe8fb19SBen Gras 		if ((list).tail != NULL) \
59*2fe8fb19SBen Gras 			(list).tail->link.next = (elt); \
60*2fe8fb19SBen Gras 		else \
61*2fe8fb19SBen Gras 			(list).head = (elt); \
62*2fe8fb19SBen Gras 		(elt)->link.prev = (list).tail; \
63*2fe8fb19SBen Gras 		(elt)->link.next = NULL; \
64*2fe8fb19SBen Gras 		(list).tail = (elt); \
65*2fe8fb19SBen Gras 	} while (/*CONSTCOND*/0)
66*2fe8fb19SBen Gras 
67*2fe8fb19SBen Gras #define UNLINK_TYPE(list, elt, link, type) \
68*2fe8fb19SBen Gras 	do { \
69*2fe8fb19SBen Gras 		INSIST(LINKED(elt, link));\
70*2fe8fb19SBen Gras 		if ((elt)->link.next != NULL) \
71*2fe8fb19SBen Gras 			(elt)->link.next->link.prev = (elt)->link.prev; \
72*2fe8fb19SBen Gras 		else { \
73*2fe8fb19SBen Gras 			INSIST((list).tail == (elt)); \
74*2fe8fb19SBen Gras 			(list).tail = (elt)->link.prev; \
75*2fe8fb19SBen Gras 		} \
76*2fe8fb19SBen Gras 		if ((elt)->link.prev != NULL) \
77*2fe8fb19SBen Gras 			(elt)->link.prev->link.next = (elt)->link.next; \
78*2fe8fb19SBen Gras 		else { \
79*2fe8fb19SBen Gras 			INSIST((list).head == (elt)); \
80*2fe8fb19SBen Gras 			(list).head = (elt)->link.next; \
81*2fe8fb19SBen Gras 		} \
82*2fe8fb19SBen Gras 		INIT_LINK_TYPE(elt, link, type); \
83*2fe8fb19SBen Gras 	} while (/*CONSTCOND*/0)
84*2fe8fb19SBen Gras #define UNLINK(list, elt, link) \
85*2fe8fb19SBen Gras 	UNLINK_TYPE(list, elt, link, void)
86*2fe8fb19SBen Gras 
87*2fe8fb19SBen Gras #define PREV(elt, link) ((elt)->link.prev)
88*2fe8fb19SBen Gras #define NEXT(elt, link) ((elt)->link.next)
89*2fe8fb19SBen Gras 
90*2fe8fb19SBen Gras #define INSERT_BEFORE(list, before, elt, link) \
91*2fe8fb19SBen Gras 	do { \
92*2fe8fb19SBen Gras 		INSIST(!LINKED(elt, link));\
93*2fe8fb19SBen Gras 		if ((before)->link.prev == NULL) \
94*2fe8fb19SBen Gras 			PREPEND(list, elt, link); \
95*2fe8fb19SBen Gras 		else { \
96*2fe8fb19SBen Gras 			(elt)->link.prev = (before)->link.prev; \
97*2fe8fb19SBen Gras 			(before)->link.prev = (elt); \
98*2fe8fb19SBen Gras 			(elt)->link.prev->link.next = (elt); \
99*2fe8fb19SBen Gras 			(elt)->link.next = (before); \
100*2fe8fb19SBen Gras 		} \
101*2fe8fb19SBen Gras 	} while (/*CONSTCOND*/0)
102*2fe8fb19SBen Gras 
103*2fe8fb19SBen Gras #define INSERT_AFTER(list, after, elt, link) \
104*2fe8fb19SBen Gras 	do { \
105*2fe8fb19SBen Gras 		INSIST(!LINKED(elt, link));\
106*2fe8fb19SBen Gras 		if ((after)->link.next == NULL) \
107*2fe8fb19SBen Gras 			APPEND(list, elt, link); \
108*2fe8fb19SBen Gras 		else { \
109*2fe8fb19SBen Gras 			(elt)->link.next = (after)->link.next; \
110*2fe8fb19SBen Gras 			(after)->link.next = (elt); \
111*2fe8fb19SBen Gras 			(elt)->link.next->link.prev = (elt); \
112*2fe8fb19SBen Gras 			(elt)->link.prev = (after); \
113*2fe8fb19SBen Gras 		} \
114*2fe8fb19SBen Gras 	} while (/*CONSTCOND*/0)
115*2fe8fb19SBen Gras 
116*2fe8fb19SBen Gras #define ENQUEUE(list, elt, link) APPEND(list, elt, link)
117*2fe8fb19SBen Gras #define DEQUEUE(list, elt, link) UNLINK(list, elt, link)
118*2fe8fb19SBen Gras 
119*2fe8fb19SBen Gras #endif /* LIST_H */
120*2fe8fb19SBen Gras /*! \file */
121