xref: /titanic_41/usr/src/cmd/sendmail/db/include/shqueue.h (revision 7c478bd95313f5f23a4c958a745db2134aa03244)
1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 1996, 1997
5  *	Sleepycat Software.  All rights reserved.
6  *
7  *	@(#)shqueue.h	8.12 (Sleepycat) 9/10/97
8  *	%W% (Sun) %G%
9  */
10 /*
11  * Copyright (c) 1998 by Sun Microsystems, Inc.
12  * All rights reserved.
13  */
14 
15 #pragma ident	"%Z%%M%	%I%	%E% SMI"
16 
17 #ifndef	_SYS_SHQUEUE_H_
18 #define	_SYS_SHQUEUE_H_
19 
20 /*
21  * This file defines three types of data structures: lists, tail queues, and
22  * circular queues, similarly to the include file <sys/queue.h>.
23  *
24  * The difference is that this set of macros can be used for structures that
25  * reside in shared memory that may be mapped at different addresses in each
26  * process.  In most cases, the macros for shared structures exactly mirror
27  * the normal macros, although the macro calls require an additional type
28  * parameter, only used by the HEAD and ENTRY macros of the standard macros.
29  *
30  * For details on the use of these macros, see the queue(3) manual page.
31  */
32 
33 /*
34  * Shared list definitions.
35  */
36 #define SH_LIST_HEAD(name)						\
37 struct name {								\
38 	ssize_t slh_first;	/* first element */			\
39 }
40 
41 #define SH_LIST_ENTRY							\
42 struct {								\
43 	ssize_t sle_next;	/* relative offset next element */	\
44 	ssize_t sle_prev;	/* relative offset of prev element */	\
45 }
46 
47 /*
48  * Shared list functions.  Since we use relative offsets for pointers,
49  * 0 is a valid offset.  Therefore, we use -1 to indicate end of list.
50  * The macros ending in "P" return pointers without checking for end
51  * of list, the others check for end of list and evaluate to either a
52  * pointer or NULL.
53  */
54 
55 #define SH_LIST_FIRSTP(head, type)					\
56 	((struct type *)(((u_int8_t *)(head)) + (head)->slh_first))
57 
58 #define SH_LIST_FIRST(head, type)					\
59 	((head)->slh_first == -1 ? NULL :				\
60 	((struct type *)(((u_int8_t *)(head)) + (head)->slh_first)))
61 
62 #define SH_LIST_NEXTP(elm, field, type)					\
63 	((struct type *)(((u_int8_t *)(elm)) + (elm)->field.sle_next))
64 
65 #define SH_LIST_NEXT(elm, field, type)					\
66 	((elm)->field.sle_next == -1 ? NULL : 				\
67 	((struct type *)(((u_int8_t *)(elm)) + (elm)->field.sle_next)))
68 
69 #define SH_LIST_PREV(elm, field)					\
70 	((ssize_t *)(((u_int8_t *)(elm)) + (elm)->field.sle_prev))
71 
72 #define SH_PTR_TO_OFF(src, dest)					\
73 	((ssize_t)(((u_int8_t *)(dest)) - ((u_int8_t *)(src))))
74 
75 #define	SH_LIST_END(head)			NULL
76 
77 /*
78  * Take the element's next pointer and calculate what the corresponding
79  * Prev pointer should be -- basically it is the negation plus the offset
80  * of the next field in the structure.
81  */
82 #define SH_LIST_NEXT_TO_PREV(elm, field)				\
83 	(-(elm)->field.sle_next + SH_PTR_TO_OFF(elm, &(elm)->field.sle_next))
84 
85 #define	SH_LIST_INIT(head) (head)->slh_first = -1
86 
87 #define SH_LIST_INSERT_AFTER(listelm, elm, field, type) do {		\
88 	if ((listelm)->field.sle_next != -1) {				\
89 		(elm)->field.sle_next = SH_PTR_TO_OFF(elm,		\
90 		    SH_LIST_NEXTP(listelm, field, type));		\
91 		SH_LIST_NEXTP(listelm, field, type)->field.sle_prev = 	\
92 			SH_LIST_NEXT_TO_PREV(elm, field);		\
93 	} else 								\
94 		(elm)->field.sle_next = -1;				\
95 	(listelm)->field.sle_next = SH_PTR_TO_OFF(listelm, elm);	\
96 	(elm)->field.sle_prev = SH_LIST_NEXT_TO_PREV(listelm, field);	\
97 } while (0)
98 
99 #define SH_LIST_INSERT_HEAD(head, elm, field, type) do {		\
100 	if ((head)->slh_first != -1) {					\
101 		(elm)->field.sle_next = 				\
102 		    (head)->slh_first - SH_PTR_TO_OFF(head, elm);	\
103 		SH_LIST_FIRSTP(head, type)->field.sle_prev =		\
104 			SH_LIST_NEXT_TO_PREV(elm, field);		\
105 	} else								\
106 		(elm)->field.sle_next = -1;				\
107 	(head)->slh_first = SH_PTR_TO_OFF(head, elm);			\
108 	(elm)->field.sle_prev = SH_PTR_TO_OFF(elm, &(head)->slh_first);	\
109 } while (0)
110 
111 #define SH_LIST_REMOVE(elm, field, type) do {				\
112 	if ((elm)->field.sle_next != -1) {				\
113 		SH_LIST_NEXTP(elm, field, type)->field.sle_prev = 	\
114 			(elm)->field.sle_prev - (elm)->field.sle_next;	\
115 		*SH_LIST_PREV(elm, field) += (elm)->field.sle_next;	\
116 	} else								\
117 		*SH_LIST_PREV(elm, field) = -1;				\
118 } while (0)
119 
120 /*
121  * Shared tail queue definitions.
122  */
123 #define SH_TAILQ_HEAD(name)						\
124 struct name {								\
125 	ssize_t stqh_first; 	/* relative offset of first element */	\
126 	ssize_t stqh_last;	/* relative offset of last's next */	\
127 }
128 
129 #define SH_TAILQ_ENTRY							\
130 struct {								\
131 	ssize_t stqe_next;	/* relative offset of next element */	\
132 	ssize_t stqe_prev;	/* relative offset of prev's next */	\
133 }
134 
135 /*
136  * Shared tail queue functions.
137  */
138 #define SH_TAILQ_FIRSTP(head, type)					\
139 	((struct type *)((u_int8_t *)(head) + (head)->stqh_first))
140 
141 #define SH_TAILQ_FIRST(head, type)					\
142 	((head)->stqh_first == -1 ? NULL : SH_TAILQ_FIRSTP(head, type))
143 
144 #define SH_TAILQ_NEXTP(elm, field, type)				\
145 	((struct type *)((u_int8_t *)(elm) + (elm)->field.stqe_next))
146 
147 #define SH_TAILQ_NEXT(elm, field, type)					\
148 	((elm)->field.stqe_next == -1 ? NULL : SH_TAILQ_NEXTP(elm, field, type))
149 
150 #define SH_TAILQ_PREVP(elm, field)					\
151 	((ssize_t *)((u_int8_t *)(elm) + (elm)->field.stqe_prev))
152 
153 #define SH_TAILQ_LAST(head)						\
154 	((ssize_t *)(((u_int8_t *)(head)) + (head)->stqh_last))
155 
156 #define SH_TAILQ_NEXT_TO_PREV(elm, field)				\
157 	(-(elm)->field.stqe_next + SH_PTR_TO_OFF(elm, &(elm)->field.stqe_next))
158 
159 #define SH_TAILQ_END(head)		NULL
160 
161 #define	SH_TAILQ_INIT(head) {						\
162 	(head)->stqh_first = -1;					\
163 	(head)->stqh_last = SH_PTR_TO_OFF(head, &(head)->stqh_first);	\
164 }
165 
166 #define SH_TAILQ_INSERT_HEAD(head, elm, field, type) do {		\
167 	if ((head)->stqh_first != -1) {					\
168 		(elm)->field.stqe_next =				\
169 		    (head)->stqh_first - SH_PTR_TO_OFF(head, elm);	\
170 		SH_TAILQ_FIRSTP(head, type)->field.stqe_prev =		\
171 			SH_TAILQ_NEXT_TO_PREV(elm, field);		\
172 	} else {							\
173 		(elm)->field.stqe_next = -1;				\
174 		(head)->stqh_last =					\
175 		    SH_PTR_TO_OFF(head, &(elm)->field.stqe_next);	\
176 	}								\
177 	(head)->stqh_first = SH_PTR_TO_OFF(head, elm);			\
178 	(elm)->field.stqe_prev =					\
179 	    SH_PTR_TO_OFF(elm, &(head)->stqh_first);			\
180 } while (0)
181 
182 #define SH_TAILQ_INSERT_TAIL(head, elm, field) do {			\
183 	(elm)->field.stqe_next = -1;					\
184 	(elm)->field.stqe_prev =					\
185 	    -SH_PTR_TO_OFF(head, elm) + (head)->stqh_last;		\
186 	if ((head)->stqh_last ==					\
187 	    SH_PTR_TO_OFF((head), &(head)->stqh_first))			\
188 		(head)->stqh_first = SH_PTR_TO_OFF(head, elm);		\
189 	else								\
190 		*SH_TAILQ_LAST(head) = -(head)->stqh_last +		\
191 		    SH_PTR_TO_OFF((elm), &(elm)->field.stqe_next) +	\
192 		    SH_PTR_TO_OFF(head, elm);				\
193 	(head)->stqh_last = 						\
194 	    SH_PTR_TO_OFF(head, &((elm)->field.stqe_next));		\
195 } while (0)
196 
197 #define SH_TAILQ_INSERT_AFTER(head, listelm, elm, field, type) do {	\
198 	if ((listelm)->field.stqe_next != -1) {				\
199 		(elm)->field.stqe_next = (listelm)->field.stqe_next -	\
200 		    SH_PTR_TO_OFF(listelm, elm);			\
201 		SH_TAILQ_NEXTP(listelm, field, type)->field.stqe_prev =	\
202 		    SH_TAILQ_NEXT_TO_PREV(elm, field);			\
203 	} else {							\
204 		(elm)->field.stqe_next = -1;				\
205 		(head)->stqh_last =					\
206 		    SH_PTR_TO_OFF(head, &elm->field.stqe_next);		\
207 	}								\
208 	(listelm)->field.stqe_next = SH_PTR_TO_OFF(listelm, elm);	\
209 	(elm)->field.stqe_prev = SH_TAILQ_NEXT_TO_PREV(listelm, field);	\
210 } while (0)
211 
212 #define SH_TAILQ_REMOVE(head, elm, field, type) do {			\
213 	if ((elm)->field.stqe_next != -1) {				\
214 		SH_TAILQ_NEXTP(elm, field, type)->field.stqe_prev = 	\
215 		    (elm)->field.stqe_prev +				\
216 		    SH_PTR_TO_OFF(SH_TAILQ_NEXTP(elm,			\
217 		    field, type), elm);					\
218 		*SH_TAILQ_PREVP(elm, field) += elm->field.stqe_next;	\
219 	} else {							\
220 		(head)->stqh_last = (elm)->field.stqe_prev +		\
221 			SH_PTR_TO_OFF(head, elm);			\
222 		*SH_TAILQ_PREVP(elm, field) = -1;			\
223 	}								\
224 } while (0)
225 
226 /*
227  * Shared circular queue definitions.
228  */
229 #define SH_CIRCLEQ_HEAD(name)						\
230 struct name {								\
231 	ssize_t scqh_first;		/* first element */		\
232 	ssize_t scqh_last;		/* last element */		\
233 }
234 
235 #define SH_CIRCLEQ_ENTRY						\
236 struct {								\
237 	ssize_t scqe_next;		/* next element */		\
238 	ssize_t scqe_prev;		/* previous element */		\
239 }
240 
241 /*
242  * Shared circular queue functions.
243  */
244 #define SH_CIRCLEQ_FIRSTP(head, type)					\
245 	((struct type *)(((u_int8_t *)(head)) + (head)->scqh_first))
246 
247 #define SH_CIRCLEQ_FIRST(head, type)					\
248 	((head)->scqh_first == -1 ? 					\
249 	(void *)head : SH_CIRCLEQ_FIRSTP(head, type))
250 
251 #define SH_CIRCLEQ_LASTP(head, type)					\
252 	((struct type *)(((u_int8_t *)(head)) + (head)->scqh_last))
253 
254 #define SH_CIRCLEQ_LAST(head, type)					\
255 	((head)->scqh_last == -1 ? (void *)head : SH_CIRCLEQ_LASTP(head, type))
256 
257 #define SH_CIRCLEQ_NEXTP(elm, field, type)				\
258 	((struct type *)(((u_int8_t *)(elm)) + (elm)->field.scqe_next))
259 
260 #define SH_CIRCLEQ_NEXT(head, elm, field, type)				\
261 	((elm)->field.scqe_next == SH_PTR_TO_OFF(elm, head) ?		\
262 	    (void *)head : SH_CIRCLEQ_NEXTP(elm, field, type))
263 
264 #define SH_CIRCLEQ_PREVP(elm, field, type)				\
265 	((struct type *)(((u_int8_t *)(elm)) + (elm)->field.scqe_prev))
266 
267 #define SH_CIRCLEQ_PREV(head, elm, field, type)				\
268 	((elm)->field.scqe_prev == SH_PTR_TO_OFF(elm, head) ?		\
269 	    (void *)head : SH_CIRCLEQ_PREVP(elm, field, type))
270 
271 #define	SH_CIRCLEQ_END(head)		((void *)(head))
272 
273 #define	SH_CIRCLEQ_INIT(head) {						\
274 	(head)->scqh_first = 0;						\
275 	(head)->scqh_last = 0;						\
276 }
277 
278 #define SH_CIRCLEQ_INSERT_AFTER(head, listelm, elm, field, type) do {	\
279 	(elm)->field.scqe_prev = SH_PTR_TO_OFF(elm, listelm);		\
280 	(elm)->field.scqe_next = (listelm)->field.scqe_next +		\
281 	    (elm)->field.scqe_prev;					\
282 	if (SH_CIRCLEQ_NEXTP(listelm, field, type) == (void *)head)	\
283 		(head)->scqh_last = SH_PTR_TO_OFF(head, elm);		\
284 	else								\
285 		SH_CIRCLEQ_NEXTP(listelm,				\
286 		    field, type)->field.scqe_prev =			\
287 		    SH_PTR_TO_OFF(SH_CIRCLEQ_NEXTP(listelm,		\
288 		    field, type), elm);					\
289 	(listelm)->field.scqe_next = -(elm)->field.scqe_prev;		\
290 } while (0)
291 
292 #define SH_CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field, type) do {	\
293 	(elm)->field.scqe_next = SH_PTR_TO_OFF(elm, listelm);		\
294 	(elm)->field.scqe_prev = (elm)->field.scqe_next -		\
295 		SH_CIRCLEQ_PREVP(listelm, field, type)->field.scqe_next;\
296 	if (SH_CIRCLEQ_PREVP(listelm, field, type) == (void *)(head))	\
297 		(head)->scqh_first = SH_PTR_TO_OFF(head, elm);		\
298 	else								\
299 		SH_CIRCLEQ_PREVP(listelm,				\
300 		    field, type)->field.scqe_next =			\
301 		    SH_PTR_TO_OFF(SH_CIRCLEQ_PREVP(listelm,		\
302 		    field, type), elm);					\
303 	(listelm)->field.scqe_prev = -(elm)->field.scqe_next;		\
304 } while (0)
305 
306 #define SH_CIRCLEQ_INSERT_HEAD(head, elm, field, type) do {		\
307 	(elm)->field.scqe_prev = SH_PTR_TO_OFF(elm, head);		\
308 	(elm)->field.scqe_next = (head)->scqh_first +			\
309 		(elm)->field.scqe_prev;					\
310 	if ((head)->scqh_last == 0)					\
311 		(head)->scqh_last = -(elm)->field.scqe_prev;		\
312 	else								\
313 		SH_CIRCLEQ_FIRSTP(head, type)->field.scqe_prev =	\
314 		    SH_PTR_TO_OFF(SH_CIRCLEQ_FIRSTP(head, type), elm);	\
315 	(head)->scqh_first = -(elm)->field.scqe_prev;			\
316 } while (0)
317 
318 #define SH_CIRCLEQ_INSERT_TAIL(head, elm, field, type) do {		\
319 	(elm)->field.scqe_next = SH_PTR_TO_OFF(elm, head);		\
320 	(elm)->field.scqe_prev = (head)->scqh_last +			\
321 	    (elm)->field.scqe_next;					\
322 	if ((head)->scqh_first == 0)					\
323 		(head)->scqh_first = -(elm)->field.scqe_next;		\
324 	else								\
325 		SH_CIRCLEQ_LASTP(head, type)->field.scqe_next = 	\
326 		    SH_PTR_TO_OFF(SH_CIRCLEQ_LASTP(head, type), elm);	\
327 	(head)->scqh_last = -(elm)->field.scqe_next;			\
328 } while (0)
329 
330 #define	SH_CIRCLEQ_REMOVE(head, elm, field, type) do {			\
331 	if (SH_CIRCLEQ_NEXTP(elm, field, type) == (void *)(head))	\
332 		(head)->scqh_last += (elm)->field.scqe_prev;		\
333 	else								\
334 		SH_CIRCLEQ_NEXTP(elm, field, type)->field.scqe_prev +=	\
335 		    (elm)->field.scqe_prev;				\
336 	if (SH_CIRCLEQ_PREVP(elm, field, type) == (void *)(head))	\
337 		(head)->scqh_first += (elm)->field.scqe_next;		\
338 	else								\
339 		SH_CIRCLEQ_PREVP(elm, field, type)->field.scqe_next +=	\
340 		    (elm)->field.scqe_next;				\
341 } while (0)
342 #endif	/* !_SYS_SHQUEUE_H_ */
343