xref: /illumos-gate/usr/src/cmd/sendmail/db/include/queue.h (revision 7c478bd95313f5f23a4c958a745db2134aa03244)
1 /*	BSDI $Id: queue.h,v 2.4 1996/07/02 13:22:11 bostic Exp $	*/
2 
3 /*
4  * Copyright (c) 1991, 1993
5  *	The Regents of the University of California.  All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice, this list of conditions and the following disclaimer.
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in the
14  *    documentation and/or other materials provided with the distribution.
15  * 3. All advertising materials mentioning features or use of this software
16  *    must display the following acknowledgement:
17  *	This product includes software developed by the University of
18  *	California, Berkeley and its contributors.
19  * 4. Neither the name of the University nor the names of its contributors
20  *    may be used to endorse or promote products derived from this software
21  *    without specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33  * SUCH DAMAGE.
34  *
35  *	@(#)queue.h	8.5 (Berkeley) 8/20/94
36  *	%W% (Sun) %G%
37  */
38 /*
39  * Copyright (c) 1998 by Sun Microsystems, Inc.
40  * All rights reserved.
41  */
42 
43 #pragma ident	"%Z%%M%	%I%	%E% SMI"
44 
45 #ifndef	_SYS_QUEUE_H_
46 #define	_SYS_QUEUE_H_
47 
48 /*
49  * This file defines three types of data structures: lists, tail queues,
50  * and circular queues.
51  *
52  * A list is headed by a single forward pointer (or an array of forward
53  * pointers for a hash table header). The elements are doubly linked
54  * so that an arbitrary element can be removed without a need to
55  * traverse the list. New elements can be added to the list before
56  * or after an existing element or at the head of the list. A list
57  * may only be traversed in the forward direction.
58  *
59  * A tail queue is headed by a pair of pointers, one to the head of the
60  * list and the other to the tail of the list. The elements are doubly
61  * linked so that an arbitrary element can be removed without a need to
62  * traverse the list. New elements can be added to the list before or
63  * after an existing element, at the head of the list, or at the end of
64  * the list. A tail queue may only be traversed in the forward direction.
65  *
66  * A circle queue is headed by a pair of pointers, one to the head of the
67  * list and the other to the tail of the list. The elements are doubly
68  * linked so that an arbitrary element can be removed without a need to
69  * traverse the list. New elements can be added to the list before or after
70  * an existing element, at the head of the list, or at the end of the list.
71  * A circle queue may be traversed in either direction, but has a more
72  * complex end of list detection.
73  *
74  * For details on the use of these macros, see the queue(3) manual page.
75  */
76 
77 /*
78  * List definitions.
79  */
80 #define LIST_HEAD(name, type)						\
81 struct name {								\
82 	struct type *lh_first;	/* first element */			\
83 }
84 
85 #define LIST_ENTRY(type)						\
86 struct {								\
87 	struct type *le_next;	/* next element */			\
88 	struct type **le_prev;	/* address of previous next element */	\
89 }
90 
91 #define	LIST_FIRST(head)		((head)->lh_first)
92 #define	LIST_NEXT(elm, field)		((elm)->field.le_next)
93 #define	LIST_END(head)			NULL
94 
95 /*
96  * List functions.
97  */
98 #define	LIST_INIT(head) {						\
99 	(head)->lh_first = NULL;					\
100 }
101 
102 #define LIST_INSERT_AFTER(listelm, elm, field) do {			\
103 	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\
104 		(listelm)->field.le_next->field.le_prev =		\
105 		    &(elm)->field.le_next;				\
106 	(listelm)->field.le_next = (elm);				\
107 	(elm)->field.le_prev = &(listelm)->field.le_next;		\
108 } while (0)
109 
110 #define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
111 	(elm)->field.le_prev = (listelm)->field.le_prev;		\
112 	(elm)->field.le_next = (listelm);				\
113 	*(listelm)->field.le_prev = (elm);				\
114 	(listelm)->field.le_prev = &(elm)->field.le_next;		\
115 } while (0)
116 
117 #define LIST_INSERT_HEAD(head, elm, field) do {				\
118 	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
119 		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
120 	(head)->lh_first = (elm);					\
121 	(elm)->field.le_prev = &(head)->lh_first;			\
122 } while (0)
123 
124 #define LIST_REMOVE(elm, field) do {					\
125 	if ((elm)->field.le_next != NULL)				\
126 		(elm)->field.le_next->field.le_prev = 			\
127 		    (elm)->field.le_prev;				\
128 	*(elm)->field.le_prev = (elm)->field.le_next;			\
129 } while (0)
130 
131 /*
132  * Tail queue definitions.
133  */
134 #define TAILQ_HEAD(name, type)						\
135 struct name {								\
136 	struct type *tqh_first;	/* first element */			\
137 	struct type **tqh_last;	/* addr of last next element */		\
138 }
139 
140 #define TAILQ_ENTRY(type)						\
141 struct {								\
142 	struct type *tqe_next;	/* next element */			\
143 	struct type **tqe_prev;	/* address of previous next element */	\
144 }
145 
146 #define	TAILQ_FIRST(head)		((head)->tqh_first)
147 #define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
148 #define	TAILQ_END(head)			NULL
149 
150 /*
151  * Tail queue functions.
152  */
153 #define	TAILQ_INIT(head) do {						\
154 	(head)->tqh_first = NULL;					\
155 	(head)->tqh_last = &(head)->tqh_first;				\
156 } while (0)
157 
158 #define TAILQ_INSERT_HEAD(head, elm, field) do {			\
159 	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
160 		(head)->tqh_first->field.tqe_prev =			\
161 		    &(elm)->field.tqe_next;				\
162 	else								\
163 		(head)->tqh_last = &(elm)->field.tqe_next;		\
164 	(head)->tqh_first = (elm);					\
165 	(elm)->field.tqe_prev = &(head)->tqh_first;			\
166 } while (0)
167 
168 #define TAILQ_INSERT_TAIL(head, elm, field) do {			\
169 	(elm)->field.tqe_next = NULL;					\
170 	(elm)->field.tqe_prev = (head)->tqh_last;			\
171 	*(head)->tqh_last = (elm);					\
172 	(head)->tqh_last = &(elm)->field.tqe_next;			\
173 } while (0)
174 
175 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
176 	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
177 		(elm)->field.tqe_next->field.tqe_prev = 		\
178 		    &(elm)->field.tqe_next;				\
179 	else								\
180 		(head)->tqh_last = &(elm)->field.tqe_next;		\
181 	(listelm)->field.tqe_next = (elm);				\
182 	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
183 } while (0)
184 
185 #define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
186 	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
187 	(elm)->field.tqe_next = (listelm);				\
188 	*(listelm)->field.tqe_prev = (elm);				\
189 	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
190 } while (0)
191 
192 #define TAILQ_REMOVE(head, elm, field) do {				\
193 	if (((elm)->field.tqe_next) != NULL)				\
194 		(elm)->field.tqe_next->field.tqe_prev = 		\
195 		    (elm)->field.tqe_prev;				\
196 	else								\
197 		(head)->tqh_last = (elm)->field.tqe_prev;		\
198 	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
199 } while (0)
200 
201 /*
202  * Circular queue definitions.
203  */
204 #define CIRCLEQ_HEAD(name, type)					\
205 struct name {								\
206 	struct type *cqh_first;		/* first element */		\
207 	struct type *cqh_last;		/* last element */		\
208 }
209 
210 #define CIRCLEQ_ENTRY(type)						\
211 struct {								\
212 	struct type *cqe_next;		/* next element */		\
213 	struct type *cqe_prev;		/* previous element */		\
214 }
215 
216 #define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
217 #define	CIRCLEQ_LAST(head)		((head)->cqh_last)
218 #define	CIRCLEQ_END(head)		((void *)(head))
219 #define	CIRCLEQ_NEXT(elm, field)	((elm)->field.cqe_next)
220 #define	CIRCLEQ_PREV(elm, field)	((elm)->field.cqe_prev)
221 
222 /*
223  * Circular queue functions.
224  */
225 #define	CIRCLEQ_INIT(head) do {						\
226 	(head)->cqh_first = (void *)(head);				\
227 	(head)->cqh_last = (void *)(head);				\
228 } while (0)
229 
230 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
231 	(elm)->field.cqe_next = (listelm)->field.cqe_next;		\
232 	(elm)->field.cqe_prev = (listelm);				\
233 	if ((listelm)->field.cqe_next == (void *)(head))		\
234 		(head)->cqh_last = (elm);				\
235 	else								\
236 		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
237 	(listelm)->field.cqe_next = (elm);				\
238 } while (0)
239 
240 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
241 	(elm)->field.cqe_next = (listelm);				\
242 	(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\
243 	if ((listelm)->field.cqe_prev == (void *)(head))		\
244 		(head)->cqh_first = (elm);				\
245 	else								\
246 		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
247 	(listelm)->field.cqe_prev = (elm);				\
248 } while (0)
249 
250 #define CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
251 	(elm)->field.cqe_next = (head)->cqh_first;			\
252 	(elm)->field.cqe_prev = (void *)(head);				\
253 	if ((head)->cqh_last == (void *)(head))				\
254 		(head)->cqh_last = (elm);				\
255 	else								\
256 		(head)->cqh_first->field.cqe_prev = (elm);		\
257 	(head)->cqh_first = (elm);					\
258 } while (0)
259 
260 #define CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
261 	(elm)->field.cqe_next = (void *)(head);				\
262 	(elm)->field.cqe_prev = (head)->cqh_last;			\
263 	if ((head)->cqh_first == (void *)(head))			\
264 		(head)->cqh_first = (elm);				\
265 	else								\
266 		(head)->cqh_last->field.cqe_next = (elm);		\
267 	(head)->cqh_last = (elm);					\
268 } while (0)
269 
270 #define	CIRCLEQ_REMOVE(head, elm, field) do {				\
271 	if ((elm)->field.cqe_next == (void *)(head))			\
272 		(head)->cqh_last = (elm)->field.cqe_prev;		\
273 	else								\
274 		(elm)->field.cqe_next->field.cqe_prev =			\
275 		    (elm)->field.cqe_prev;				\
276 	if ((elm)->field.cqe_prev == (void *)(head))			\
277 		(head)->cqh_first = (elm)->field.cqe_next;		\
278 	else								\
279 		(elm)->field.cqe_prev->field.cqe_next =			\
280 		    (elm)->field.cqe_next;				\
281 } while (0)
282 #endif	/* !_SYS_QUEUE_H_ */
283