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