xref: /freebsd/sys/contrib/ck/include/ck_queue.h (revision 2b833162)
1 /*
2  * Copyright 2012-2015 Samy Al Bahra.
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24  * SUCH DAMAGE.
25  */
26 
27 /*-
28  * Copyright (c) 1991, 1993
29  *	The Regents of the University of California.  All rights reserved.
30  *
31  * Redistribution and use in source and binary forms, with or without
32  * modification, are permitted provided that the following conditions
33  * are met:
34  * 1. Redistributions of source code must retain the above copyright
35  *    notice, this list of conditions and the following disclaimer.
36  * 2. Redistributions in binary form must reproduce the above copyright
37  *    notice, this list of conditions and the following disclaimer in the
38  *    documentation and/or other materials provided with the distribution.
39  * 4. Neither the name of the University nor the names of its contributors
40  *    may be used to endorse or promote products derived from this software
41  *    without specific prior written permission.
42  *
43  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
44  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
45  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
46  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
47  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
48  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
49  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
50  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
51  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
52  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
53  * SUCH DAMAGE.
54  *
55  *	@(#)queue.h	8.5 (Berkeley) 8/20/94
56  * $FreeBSD: release/9.0.0/sys/sys/queue.h 221843 2011-05-13 15:49:23Z mdf $
57  */
58 
59 #ifndef CK_QUEUE_H
60 #define	CK_QUEUE_H
61 
62 #include <ck_pr.h>
63 
64 /*
65  * This file defines three types of data structures: singly-linked lists,
66  * singly-linked tail queues and lists.
67  *
68  * A singly-linked list is headed by a single forward pointer. The elements
69  * are singly linked for minimum space and pointer manipulation overhead at
70  * the expense of O(n) removal for arbitrary elements. New elements can be
71  * added to the list after an existing element or at the head of the list.
72  * Elements being removed from the head of the list should use the explicit
73  * macro for this purpose for optimum efficiency. A singly-linked list may
74  * only be traversed in the forward direction.  Singly-linked lists are ideal
75  * for applications with large datasets and few or no removals or for
76  * implementing a LIFO queue.
77  *
78  * A singly-linked tail queue is headed by a pair of pointers, one to the
79  * head of the list and the other to the tail of the list. The elements are
80  * singly linked for minimum space and pointer manipulation overhead at the
81  * expense of O(n) removal for arbitrary elements. New elements can be added
82  * to the list after an existing element, at the head of the list, or at the
83  * end of the list. Elements being removed from the head of the tail queue
84  * should use the explicit macro for this purpose for optimum efficiency.
85  * A singly-linked tail queue may only be traversed in the forward direction.
86  * Singly-linked tail queues are ideal for applications with large datasets
87  * and few or no removals or for implementing a FIFO queue.
88  *
89  * A list is headed by a single forward pointer (or an array of forward
90  * pointers for a hash table header). The elements are doubly linked
91  * so that an arbitrary element can be removed without a need to
92  * traverse the list. New elements can be added to the list before
93  * or after an existing element or at the head of the list. A list
94  * may only be traversed in the forward direction.
95  *
96  * It is safe to use _FOREACH/_FOREACH_SAFE in the presence of concurrent
97  * modifications to the list. Writers to these lists must, on the other hand,
98  * implement writer-side synchronization. The _SWAP operations are not atomic.
99  * This facility is currently unsupported on architectures such as the Alpha
100  * which require load-depend memory fences.
101  *
102  *				CK_SLIST	CK_LIST	CK_STAILQ
103  * _HEAD			+		+	+
104  * _HEAD_INITIALIZER		+		+	+
105  * _ENTRY			+		+	+
106  * _INIT			+		+	+
107  * _EMPTY			+		+	+
108  * _FIRST			+		+	+
109  * _NEXT			+		+	+
110  * _FOREACH			+		+	+
111  * _FOREACH_SAFE		+		+	+
112  * _INSERT_HEAD			+		+	+
113  * _INSERT_BEFORE		-		+	-
114  * _INSERT_AFTER		+		+	+
115  * _INSERT_TAIL			-		-	+
116  * _REMOVE_AFTER		+		-	+
117  * _REMOVE_HEAD			+		-	+
118  * _REMOVE			+		+	+
119  * _SWAP			+		+	+
120  * _MOVE			+		+	+
121  */
122 
123 /*
124  * Singly-linked List declarations.
125  */
126 #define	CK_SLIST_HEAD(name, type)						\
127 struct name {									\
128 	struct type *cslh_first;	/* first element */				\
129 }
130 
131 #define	CK_SLIST_HEAD_INITIALIZER(head)						\
132 	{ NULL }
133 
134 #define	CK_SLIST_ENTRY(type)							\
135 struct {									\
136 	struct type *csle_next;	/* next element */				\
137 }
138 
139 /*
140  * Singly-linked List functions.
141  */
142 #define	CK_SLIST_EMPTY(head)							\
143 	(ck_pr_load_ptr(&(head)->cslh_first) == NULL)
144 
145 #define	CK_SLIST_FIRST(head)							\
146 	(ck_pr_load_ptr(&(head)->cslh_first))
147 
148 #define	CK_SLIST_NEXT(elm, field)						\
149 	ck_pr_load_ptr(&((elm)->field.csle_next))
150 
151 #define	CK_SLIST_FOREACH(var, head, field)					\
152 	for ((var) = CK_SLIST_FIRST((head));					\
153 	    (var);								\
154 	    (var) = CK_SLIST_NEXT((var), field))
155 
156 #define	CK_SLIST_FOREACH_FROM(var, head, field)					\
157 	for ((var) = ((var) != NULL ? (var) : CK_SLIST_FIRST((head)));		\
158 	    (var);								\
159 	    (var) = CK_SLIST_NEXT((var), field))
160 
161 #define	CK_SLIST_FOREACH_SAFE(var, head, field, tvar)				\
162 	for ((var) = CK_SLIST_FIRST(head);					\
163 	    (var) && ((tvar) = CK_SLIST_NEXT(var, field), 1);			\
164 	    (var) = (tvar))
165 
166 #define	CK_SLIST_FOREACH_PREVPTR(var, varp, head, field)			\
167 	for ((varp) = &(head)->cslh_first;					\
168 	    ((var) = ck_pr_load_ptr(varp)) != NULL;				\
169 	    (varp) = &(var)->field.csle_next)
170 
171 #define	CK_SLIST_INIT(head) do {						\
172 	ck_pr_store_ptr(&(head)->cslh_first, NULL);				\
173 	ck_pr_fence_store();							\
174 } while (0)
175 
176 #define	CK_SLIST_INSERT_AFTER(a, b, field) do {					\
177 	(b)->field.csle_next = (a)->field.csle_next;				\
178 	ck_pr_fence_store();							\
179 	ck_pr_store_ptr(&(a)->field.csle_next, b);				\
180 } while (0)
181 
182 #define	CK_SLIST_INSERT_HEAD(head, elm, field) do {				\
183 	(elm)->field.csle_next = (head)->cslh_first;				\
184 	ck_pr_fence_store();							\
185 	ck_pr_store_ptr(&(head)->cslh_first, elm);				\
186 } while (0)
187 
188 #define	CK_SLIST_INSERT_PREVPTR(prevp, slistelm, elm, field) do {		\
189 	(elm)->field.csle_next = (slistelm);					\
190 	ck_pr_fence_store();							\
191 	ck_pr_store_ptr(prevp, elm);						\
192 } while (0)
193 
194 #define CK_SLIST_REMOVE_AFTER(elm, field) do {					\
195 	ck_pr_store_ptr(&(elm)->field.csle_next,				\
196 	    (elm)->field.csle_next->field.csle_next);				\
197 } while (0)
198 
199 #define	CK_SLIST_REMOVE(head, elm, type, field) do {				\
200 	if ((head)->cslh_first == (elm)) {					\
201 		CK_SLIST_REMOVE_HEAD((head), field);				\
202 	} else {								\
203 		struct type *curelm = (head)->cslh_first;			\
204 		while (curelm->field.csle_next != (elm))			\
205 			curelm = curelm->field.csle_next;			\
206 		CK_SLIST_REMOVE_AFTER(curelm, field);				\
207 	}									\
208 } while (0)
209 
210 #define	CK_SLIST_REMOVE_HEAD(head, field) do {					\
211 	ck_pr_store_ptr(&(head)->cslh_first,					\
212 		(head)->cslh_first->field.csle_next);				\
213 } while (0)
214 
215 #define CK_SLIST_REMOVE_PREVPTR(prevp, elm, field) do {				\
216 	ck_pr_store_ptr(prevptr, (elm)->field.csle_next);			\
217 } while (0)
218 
219 #define CK_SLIST_MOVE(head1, head2, field) do {					\
220 	ck_pr_store_ptr(&(head1)->cslh_first, (head2)->cslh_first);		\
221 } while (0)
222 
223 /*
224  * This operation is not applied atomically.
225  */
226 #define CK_SLIST_SWAP(a, b, type) do {						\
227 	struct type *swap_first = (a)->cslh_first;				\
228 	(a)->cslh_first = (b)->cslh_first;					\
229 	(b)->cslh_first = swap_first;						\
230 } while (0)
231 
232 /*
233  * Singly-linked Tail queue declarations.
234  */
235 #define	CK_STAILQ_HEAD(name, type)					\
236 struct name {								\
237 	struct type *cstqh_first;/* first element */			\
238 	struct type **cstqh_last;/* addr of last next element */		\
239 }
240 
241 #define	CK_STAILQ_HEAD_INITIALIZER(head)				\
242 	{ NULL, &(head).cstqh_first }
243 
244 #define	CK_STAILQ_ENTRY(type)						\
245 struct {								\
246 	struct type *cstqe_next;	/* next element */			\
247 }
248 
249 /*
250  * Singly-linked Tail queue functions.
251  */
252 #define	CK_STAILQ_CONCAT(head1, head2) do {					\
253 	if ((head2)->cstqh_first != NULL) {					\
254 		ck_pr_store_ptr((head1)->cstqh_last, (head2)->cstqh_first);	\
255 		ck_pr_fence_store();						\
256 		(head1)->cstqh_last = (head2)->cstqh_last;			\
257 		CK_STAILQ_INIT((head2));					\
258 	}									\
259 } while (0)
260 
261 #define	CK_STAILQ_EMPTY(head)	(ck_pr_load_ptr(&(head)->cstqh_first) == NULL)
262 
263 #define	CK_STAILQ_FIRST(head)	(ck_pr_load_ptr(&(head)->cstqh_first))
264 
265 #define	CK_STAILQ_FOREACH(var, head, field)				\
266 	for((var) = CK_STAILQ_FIRST((head));				\
267 	   (var);							\
268 	   (var) = CK_STAILQ_NEXT((var), field))
269 
270 #define	CK_STAILQ_FOREACH_FROM(var, head, field)			\
271 	for ((var) = ((var) != NULL ? (var) : CK_STAILQ_FIRST((head)));	\
272 	    (var);							\
273 	    (var) = CK_STAILQ_NEXT((var), field))
274 
275 #define	CK_STAILQ_FOREACH_SAFE(var, head, field, tvar)			\
276 	for ((var) = CK_STAILQ_FIRST((head));				\
277 	    (var) && ((tvar) =						\
278 		CK_STAILQ_NEXT((var), field), 1);			\
279 	    (var) = (tvar))
280 
281 #define	CK_STAILQ_INIT(head) do {					\
282 	ck_pr_store_ptr(&(head)->cstqh_first, NULL);			\
283 	ck_pr_fence_store();						\
284 	(head)->cstqh_last = &(head)->cstqh_first;			\
285 } while (0)
286 
287 #define	CK_STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {			\
288 	(elm)->field.cstqe_next = (tqelm)->field.cstqe_next;			\
289 	ck_pr_fence_store();							\
290 	ck_pr_store_ptr(&(tqelm)->field.cstqe_next, elm);			\
291 	if ((elm)->field.cstqe_next == NULL)					\
292 		(head)->cstqh_last = &(elm)->field.cstqe_next;			\
293 } while (0)
294 
295 #define	CK_STAILQ_INSERT_HEAD(head, elm, field) do {				\
296 	(elm)->field.cstqe_next = (head)->cstqh_first;				\
297 	ck_pr_fence_store();							\
298 	ck_pr_store_ptr(&(head)->cstqh_first, elm);				\
299 	if ((elm)->field.cstqe_next == NULL)					\
300 		(head)->cstqh_last = &(elm)->field.cstqe_next;			\
301 } while (0)
302 
303 #define	CK_STAILQ_INSERT_TAIL(head, elm, field) do {				\
304 	(elm)->field.cstqe_next = NULL;						\
305 	ck_pr_fence_store();							\
306 	ck_pr_store_ptr((head)->cstqh_last, (elm));				\
307 	(head)->cstqh_last = &(elm)->field.cstqe_next;				\
308 } while (0)
309 
310 #define	CK_STAILQ_NEXT(elm, field)						\
311 	(ck_pr_load_ptr(&(elm)->field.cstqe_next))
312 
313 #define	CK_STAILQ_REMOVE(head, elm, type, field) do {				\
314 	if ((head)->cstqh_first == (elm)) {					\
315 		CK_STAILQ_REMOVE_HEAD((head), field);				\
316 	} else {								\
317 		struct type *curelm = (head)->cstqh_first;			\
318 		while (curelm->field.cstqe_next != (elm))			\
319 			curelm = curelm->field.cstqe_next;			\
320 		CK_STAILQ_REMOVE_AFTER(head, curelm, field);			\
321 	}									\
322 } while (0)
323 
324 #define CK_STAILQ_REMOVE_AFTER(head, elm, field) do {				\
325 	ck_pr_store_ptr(&(elm)->field.cstqe_next,				\
326 	    (elm)->field.cstqe_next->field.cstqe_next);				\
327 	if ((elm)->field.cstqe_next == NULL)					\
328 		(head)->cstqh_last = &(elm)->field.cstqe_next;			\
329 } while (0)
330 
331 #define	CK_STAILQ_REMOVE_HEAD(head, field) do {					\
332 	ck_pr_store_ptr(&(head)->cstqh_first,					\
333 	    (head)->cstqh_first->field.cstqe_next);				\
334 	if ((head)->cstqh_first == NULL)						\
335 		(head)->cstqh_last = &(head)->cstqh_first;			\
336 } while (0)
337 
338 #define CK_STAILQ_MOVE(head1, head2, field) do {				\
339 	ck_pr_store_ptr(&(head1)->cstqh_first, (head2)->cstqh_first);		\
340 	(head1)->cstqh_last = (head2)->cstqh_last;				\
341 	if ((head2)->cstqh_last == &(head2)->cstqh_first)				\
342 		(head1)->cstqh_last = &(head1)->cstqh_first;			\
343 } while (0)
344 
345 /*
346  * This operation is not applied atomically.
347  */
348 #define CK_STAILQ_SWAP(head1, head2, type) do {				\
349 	struct type *swap_first = CK_STAILQ_FIRST(head1);		\
350 	struct type **swap_last = (head1)->cstqh_last;			\
351 	CK_STAILQ_FIRST(head1) = CK_STAILQ_FIRST(head2);		\
352 	(head1)->cstqh_last = (head2)->cstqh_last;			\
353 	CK_STAILQ_FIRST(head2) = swap_first;				\
354 	(head2)->cstqh_last = swap_last;					\
355 	if (CK_STAILQ_EMPTY(head1))					\
356 		(head1)->cstqh_last = &(head1)->cstqh_first;		\
357 	if (CK_STAILQ_EMPTY(head2))					\
358 		(head2)->cstqh_last = &(head2)->cstqh_first;		\
359 } while (0)
360 
361 /*
362  * List declarations.
363  */
364 #define	CK_LIST_HEAD(name, type)						\
365 struct name {									\
366 	struct type *clh_first;	/* first element */				\
367 }
368 
369 #define	CK_LIST_HEAD_INITIALIZER(head)						\
370 	{ NULL }
371 
372 #define	CK_LIST_ENTRY(type)							\
373 struct {									\
374 	struct type *cle_next;	/* next element */				\
375 	struct type **cle_prev;	/* address of previous next element */		\
376 }
377 
378 #define	CK_LIST_FIRST(head)		ck_pr_load_ptr(&(head)->clh_first)
379 #define	CK_LIST_EMPTY(head)		(CK_LIST_FIRST(head) == NULL)
380 #define	CK_LIST_NEXT(elm, field)	ck_pr_load_ptr(&(elm)->field.cle_next)
381 
382 #define	CK_LIST_FOREACH(var, head, field)					\
383 	for ((var) = CK_LIST_FIRST((head));					\
384 	    (var);								\
385 	    (var) = CK_LIST_NEXT((var), field))
386 
387 #define	CK_LIST_FOREACH_FROM(var, head, field)					\
388 	for ((var) = ((var) != NULL ? (var) : CK_LIST_FIRST((head)));		\
389 	    (var);								\
390 	    (var) = CK_LIST_NEXT((var), field))
391 
392 #define	CK_LIST_FOREACH_SAFE(var, head, field, tvar)				  \
393 	for ((var) = CK_LIST_FIRST((head));					  \
394 	    (var) && ((tvar) = CK_LIST_NEXT((var), field), 1);			  \
395 	    (var) = (tvar))
396 
397 #define	CK_LIST_INIT(head) do {							\
398 	ck_pr_store_ptr(&(head)->clh_first, NULL);				\
399 	ck_pr_fence_store();							\
400 } while (0)
401 
402 #define	CK_LIST_INSERT_AFTER(listelm, elm, field) do {				\
403 	(elm)->field.cle_next = (listelm)->field.cle_next;			\
404 	(elm)->field.cle_prev = &(listelm)->field.cle_next;			\
405 	ck_pr_fence_store();							\
406 	if ((listelm)->field.cle_next != NULL)					\
407 		(listelm)->field.cle_next->field.cle_prev = &(elm)->field.cle_next;\
408 	ck_pr_store_ptr(&(listelm)->field.cle_next, elm);			\
409 } while (0)
410 
411 #define	CK_LIST_INSERT_BEFORE(listelm, elm, field) do {				\
412 	(elm)->field.cle_prev = (listelm)->field.cle_prev;			\
413 	(elm)->field.cle_next = (listelm);					\
414 	ck_pr_fence_store();							\
415 	ck_pr_store_ptr((listelm)->field.cle_prev, (elm));			\
416 	(listelm)->field.cle_prev = &(elm)->field.cle_next;			\
417 } while (0)
418 
419 #define	CK_LIST_INSERT_HEAD(head, elm, field) do {				\
420 	(elm)->field.cle_next = (head)->clh_first;				\
421 	ck_pr_fence_store();							\
422 	if ((elm)->field.cle_next != NULL)					\
423 		(head)->clh_first->field.cle_prev =  &(elm)->field.cle_next;	\
424 	ck_pr_store_ptr(&(head)->clh_first, elm);				\
425 	(elm)->field.cle_prev = &(head)->clh_first;				\
426 } while (0)
427 
428 #define	CK_LIST_REMOVE(elm, field) do {						\
429 	ck_pr_store_ptr((elm)->field.cle_prev, (elm)->field.cle_next);		\
430 	if ((elm)->field.cle_next != NULL)					\
431 		(elm)->field.cle_next->field.cle_prev = (elm)->field.cle_prev;	\
432 } while (0)
433 
434 #define CK_LIST_MOVE(head1, head2, field) do {				\
435 	ck_pr_store_ptr(&(head1)->clh_first, (head2)->clh_first);		\
436 	if ((head1)->clh_first != NULL)					\
437 		(head1)->clh_first->field.cle_prev = &(head1)->clh_first;	\
438 } while (0)
439 
440 /*
441  * This operation is not applied atomically.
442  */
443 #define CK_LIST_SWAP(head1, head2, type, field) do {			\
444 	struct type *swap_tmp = (head1)->clh_first;			\
445 	(head1)->clh_first = (head2)->clh_first;				\
446 	(head2)->clh_first = swap_tmp;					\
447 	if ((swap_tmp = (head1)->clh_first) != NULL)			\
448 		swap_tmp->field.cle_prev = &(head1)->clh_first;		\
449 	if ((swap_tmp = (head2)->clh_first) != NULL)			\
450 		swap_tmp->field.cle_prev = &(head2)->clh_first;		\
451 } while (0)
452 
453 #endif /* CK_QUEUE_H */
454