Context Navigation

queue.h @ 8645c9d7

55-freebsd-126-freebsd-12

Last change on this file since 8645c9d7 was ff36f5e, checked in by Christian Mauderer <christian.mauderer@…>, on 05/30/18 at 12:27:35

Import ipsec-tools 0.8.2.

Import unchanged ipsec-tools sources in the release version 0.8.2. The
homepage of ipsec-tools is http://ipsec-tools.sourceforge.net/. The
sources can be obtained from there.

Property mode set to 100644

File size: 14.3 KB

Line
1	/* $NetBSD: queue.h,v 1.4 2006/09/09 16:22:09 manu 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	* 4. Neither the name of the University nor the names of its contributors
16	* may be used to endorse or promote products derived from this software
17	* without specific prior written permission.
18	*
19	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29	* SUCH DAMAGE.
30	*
31	* @(#)queue.h 8.5 (Berkeley) 8/20/94
32	* $FreeBSD: src/sys/sys/queue.h,v 1.58 2004/04/07 04:19:49 imp Exp $
33	*
34	* 04/24/2004 Backport to v1.45 functionality for ipsec-tools
35	* Heiko Hund <heiko@ist.eigentlich.net>
36	*/
37
38	#ifndef _SYS_QUEUE_H_
39	#define _SYS_QUEUE_H_
40
41	//#include <sys/cdefs.h>
42
43	/*
44	* This file defines four types of data structures: singly-linked lists,
45	* singly-linked tail queues, lists and tail queues.
46	*
47	* A singly-linked list is headed by a single forward pointer. The elements
48	* are singly linked for minimum space and pointer manipulation overhead at
49	* the expense of O(n) removal for arbitrary elements. New elements can be
50	* added to the list after an existing element or at the head of the list.
51	* Elements being removed from the head of the list should use the explicit
52	* macro for this purpose for optimum efficiency. A singly-linked list may
53	* only be traversed in the forward direction. Singly-linked lists are ideal
54	* for applications with large datasets and few or no removals or for
55	* implementing a LIFO queue.
56	*
57	* A singly-linked tail queue is headed by a pair of pointers, one to the
58	* head of the list and the other to the tail of the list. The elements are
59	* singly linked for minimum space and pointer manipulation overhead at the
60	* expense of O(n) removal for arbitrary elements. New elements can be added
61	* to the list after an existing element, at the head of the list, or at the
62	* end of the list. Elements being removed from the head of the tail queue
63	* should use the explicit macro for this purpose for optimum efficiency.
64	* A singly-linked tail queue may only be traversed in the forward direction.
65	* Singly-linked tail queues are ideal for applications with large datasets
66	* and few or no removals or for implementing a FIFO queue.
67	*
68	* A list is headed by a single forward pointer (or an array of forward
69	* pointers for a hash table header). The elements are doubly linked
70	* so that an arbitrary element can be removed without a need to
71	* traverse the list. New elements can be added to the list before
72	* or after an existing element or at the head of the list. A list
73	* may only be traversed in the forward direction.
74	*
75	* A tail queue is headed by a pair of pointers, one to the head of the
76	* list and the other to the tail of the list. The elements are doubly
77	* linked so that an arbitrary element can be removed without a need to
78	* traverse the list. New elements can be added to the list before or
79	* after an existing element, at the head of the list, or at the end of
80	* the list. A tail queue may be traversed in either direction.
81	*
82	* For details on the use of these macros, see the queue(3) manual page.
83	*
84	*
85	* SLIST LIST STAILQ TAILQ
86	* _HEAD + + + +
87	* _HEAD_INITIALIZER + + + +
88	* _ENTRY + + + +
89	* _INIT + + + +
90	* _EMPTY + + + +
91	* _FIRST + + + +
92	* _NEXT + + + +
93	* _PREV - - - +
94	* _LAST - - + +
95	* _FOREACH + + + +
96	* _FOREACH_REVERSE - - - +
97	* _INSERT_HEAD + + + +
98	* _INSERT_BEFORE - + - +
99	* _INSERT_AFTER + + + +
100	* _INSERT_TAIL - - + +
101	* _REMOVE_HEAD + - + -
102	* _REMOVE + + + +
103	*
104	*/
105
106	/*
107	* Singly-linked List declarations.
108	*/
109	#define SLIST_HEAD(name, type) \
110	struct name { \
111	struct type slh_first; / first element */ \
112	}
113
114	#define SLIST_HEAD_INITIALIZER(head) \
115	{ NULL }
116
117	#define SLIST_ENTRY(type) \
118	struct { \
119	struct type sle_next; / next element */ \
120	}
121
122	/*
123	* Singly-linked List functions.
124	*/
125	#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
126
127	#define SLIST_FIRST(head) ((head)->slh_first)
128
129	#define SLIST_FOREACH(var, head, field) \
130	for ((var) = SLIST_FIRST((head)); \
131	(var); \
132	(var) = SLIST_NEXT((var), field))
133
134	#define SLIST_INIT(head) do { \
135	SLIST_FIRST((head)) = NULL; \
136	} while (0)
137
138	#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
139	SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
140	SLIST_NEXT((slistelm), field) = (elm); \
141	} while (0)
142
143	#define SLIST_INSERT_HEAD(head, elm, field) do { \
144	SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
145	SLIST_FIRST((head)) = (elm); \
146	} while (0)
147
148	#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
149
150	#define SLIST_REMOVE(head, elm, type, field) do { \
151	if (SLIST_FIRST((head)) == (elm)) { \
152	SLIST_REMOVE_HEAD((head), field); \
153	} \
154	else { \
155	struct type *curelm = SLIST_FIRST((head)); \
156	while (SLIST_NEXT(curelm, field) != (elm)) \
157	curelm = SLIST_NEXT(curelm, field); \
158	SLIST_NEXT(curelm, field) = \
159	SLIST_NEXT(SLIST_NEXT(curelm, field), field); \
160	} \
161	} while (0)
162
163	#define SLIST_REMOVE_HEAD(head, field) do { \
164	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \
165	} while (0)
166
167	/*
168	* Singly-linked Tail queue declarations.
169	*/
170	#define STAILQ_HEAD(name, type) \
171	struct name { \
172	struct type stqh_first;/ first element */ \
173	struct type *stqh_last;/ addr of last next element */ \
174	}
175
176	#define STAILQ_HEAD_INITIALIZER(head) \
177	{ NULL, &(head).stqh_first }
178
179	#define STAILQ_ENTRY(type) \
180	struct { \
181	struct type stqe_next; / next element */ \
182	}
183
184	/*
185	* Singly-linked Tail queue functions.
186	*/
187	#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
188
189	#define STAILQ_FIRST(head) ((head)->stqh_first)
190
191	#define STAILQ_FOREACH(var, head, field) \
192	for((var) = STAILQ_FIRST((head)); \
193	(var); \
194	(var) = STAILQ_NEXT((var), field))
195
196	#define STAILQ_INIT(head) do { \
197	STAILQ_FIRST((head)) = NULL; \
198	(head)->stqh_last = &STAILQ_FIRST((head)); \
199	} while (0)
200
201	#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
202	if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
203	(head)->stqh_last = &STAILQ_NEXT((elm), field); \
204	STAILQ_NEXT((tqelm), field) = (elm); \
205	} while (0)
206
207	#define STAILQ_INSERT_HEAD(head, elm, field) do { \
208	if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
209	(head)->stqh_last = &STAILQ_NEXT((elm), field); \
210	STAILQ_FIRST((head)) = (elm); \
211	} while (0)
212
213	#define STAILQ_INSERT_TAIL(head, elm, field) do { \
214	STAILQ_NEXT((elm), field) = NULL; \
215	*(head)->stqh_last = (elm); \
216	(head)->stqh_last = &STAILQ_NEXT((elm), field); \
217	} while (0)
218
219	#define STAILQ_LAST(head, type, field) \
220	(STAILQ_EMPTY(head) ? \
221	NULL : \
222	((struct type *) \
223	((char *)((head)->stqh_last) - __offsetof(struct type, field))))
224
225	#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
226
227	#define STAILQ_REMOVE(head, elm, type, field) do { \
228	if (STAILQ_FIRST((head)) == (elm)) { \
229	STAILQ_REMOVE_HEAD(head, field); \
230	} \
231	else { \
232	struct type *curelm = STAILQ_FIRST((head)); \
233	while (STAILQ_NEXT(curelm, field) != (elm)) \
234	curelm = STAILQ_NEXT(curelm, field); \
235	if ((STAILQ_NEXT(curelm, field) = \
236	STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\
237	(head)->stqh_last = &STAILQ_NEXT((curelm), field);\
238	} \
239	} while (0)
240
241	#define STAILQ_REMOVE_HEAD(head, field) do { \
242	if ((STAILQ_FIRST((head)) = \
243	STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \
244	(head)->stqh_last = &STAILQ_FIRST((head)); \
245	} while (0)
246
247	#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \
248	if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \
249	(head)->stqh_last = &STAILQ_FIRST((head)); \
250	} while (0)
251
252	/*
253	* List declarations.
254	*/
255	#define LIST_HEAD(name, type) \
256	struct name { \
257	struct type lh_first; / first element */ \
258	}
259
260	#define LIST_HEAD_INITIALIZER(head) \
261	{ NULL }
262
263	#define LIST_ENTRY(type) \
264	struct { \
265	struct type le_next; / next element */ \
266	struct type *le_prev; / address of previous next element */ \
267	}
268
269	/*
270	* List functions.
271	*/
272
273	#define LIST_EMPTY(head) ((head)->lh_first == NULL)
274
275	#define LIST_FIRST(head) ((head)->lh_first)
276
277	#define LIST_FOREACH(var, head, field) \
278	for ((var) = LIST_FIRST((head)); \
279	(var); \
280	(var) = LIST_NEXT((var), field))
281
282	#define LIST_INIT(head) do { \
283	LIST_FIRST((head)) = NULL; \
284	} while (0)
285
286	#define LIST_INSERT_AFTER(listelm, elm, field) do { \
287	if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
288	LIST_NEXT((listelm), field)->field.le_prev = \
289	&LIST_NEXT((elm), field); \
290	LIST_NEXT((listelm), field) = (elm); \
291	(elm)->field.le_prev = &LIST_NEXT((listelm), field); \
292	} while (0)
293
294	#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
295	(elm)->field.le_prev = (listelm)->field.le_prev; \
296	LIST_NEXT((elm), field) = (listelm); \
297	*(listelm)->field.le_prev = (elm); \
298	(listelm)->field.le_prev = &LIST_NEXT((elm), field); \
299	} while (0)
300
301	#define LIST_INSERT_HEAD(head, elm, field) do { \
302	if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
303	LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
304	LIST_FIRST((head)) = (elm); \
305	(elm)->field.le_prev = &LIST_FIRST((head)); \
306	} while (0)
307
308	#define LIST_NEXT(elm, field) ((elm)->field.le_next)
309
310	#define LIST_REMOVE(elm, field) do { \
311	if (LIST_NEXT((elm), field) != NULL) \
312	LIST_NEXT((elm), field)->field.le_prev = \
313	(elm)->field.le_prev; \
314	*(elm)->field.le_prev = LIST_NEXT((elm), field); \
315	} while (0)
316
317	/*
318	* Tail queue declarations.
319	*/
320	#define TAILQ_HEAD(name, type) \
321	struct name { \
322	struct type tqh_first; / first element */ \
323	struct type *tqh_last; / addr of last next element */ \
324	}
325
326	#define TAILQ_HEAD_INITIALIZER(head) \
327	{ NULL, &(head).tqh_first }
328
329	#define TAILQ_ENTRY(type) \
330	struct { \
331	struct type tqe_next; / next element */ \
332	struct type *tqe_prev; / address of previous next element */ \
333	}
334
335	/*
336	* Tail queue functions.
337	*/
338	#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
339
340	#define TAILQ_FIRST(head) ((head)->tqh_first)
341
342	#define TAILQ_FOREACH(var, head, field) \
343	for ((var) = TAILQ_FIRST((head)); \
344	(var); \
345	(var) = TAILQ_NEXT((var), field))
346
347	#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
348	for ((var) = TAILQ_LAST((head), headname); \
349	(var); \
350	(var) = TAILQ_PREV((var), headname, field))
351
352	#define TAILQ_INIT(head) do { \
353	TAILQ_FIRST((head)) = NULL; \
354	(head)->tqh_last = &TAILQ_FIRST((head)); \
355	} while (0)
356
357	#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
358	if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
359	TAILQ_NEXT((elm), field)->field.tqe_prev = \
360	&TAILQ_NEXT((elm), field); \
361	else \
362	(head)->tqh_last = &TAILQ_NEXT((elm), field); \
363	TAILQ_NEXT((listelm), field) = (elm); \
364	(elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
365	} while (0)
366
367	#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
368	(elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
369	TAILQ_NEXT((elm), field) = (listelm); \
370	*(listelm)->field.tqe_prev = (elm); \
371	(listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
372	} while (0)
373
374	#define TAILQ_INSERT_HEAD(head, elm, field) do { \
375	if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
376	TAILQ_FIRST((head))->field.tqe_prev = \
377	&TAILQ_NEXT((elm), field); \
378	else \
379	(head)->tqh_last = &TAILQ_NEXT((elm), field); \
380	TAILQ_FIRST((head)) = (elm); \
381	(elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
382	} while (0)
383
384	#define TAILQ_INSERT_TAIL(head, elm, field) do { \
385	TAILQ_NEXT((elm), field) = NULL; \
386	(elm)->field.tqe_prev = (head)->tqh_last; \
387	*(head)->tqh_last = (elm); \
388	(head)->tqh_last = &TAILQ_NEXT((elm), field); \
389	} while (0)
390
391	#define TAILQ_LAST(head, headname) \
392	((((struct headname )((head)->tqh_last))->tqh_last))
393
394	#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
395
396	#define TAILQ_PREV(elm, headname, field) \
397	((((struct headname )((elm)->field.tqe_prev))->tqh_last))
398
399	#define TAILQ_REMOVE(head, elm, field) do { \
400	if ((TAILQ_NEXT((elm), field)) != NULL) \
401	TAILQ_NEXT((elm), field)->field.tqe_prev = \
402	(elm)->field.tqe_prev; \
403	else \
404	(head)->tqh_last = (elm)->field.tqe_prev; \
405	*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
406	} while (0)
407
408
409	#ifdef _KERNEL
410
411	/*
412	* XXX insque() and remque() are an old way of handling certain queues.
413	* They bogusly assumes that all queue heads look alike.
414	*/
415
416	struct quehead {
417	struct quehead *qh_link;
418	struct quehead *qh_rlink;
419	};
420
421	#ifdef __GNUC__
422
423	static __inline void
424	insque(void a, void b)
425	{
426	struct quehead element = (struct quehead )a,
427	head = (struct quehead )b;
428
429	element->qh_link = head->qh_link;
430	element->qh_rlink = head;
431	head->qh_link = element;
432	element->qh_link->qh_rlink = element;
433	}
434
435	static __inline void
436	remque(void *a)
437	{
438	struct quehead element = (struct quehead )a;
439
440	element->qh_link->qh_rlink = element->qh_rlink;
441	element->qh_rlink->qh_link = element->qh_link;
442	element->qh_rlink = 0;
443	}
444
445	#else /* !__GNUC__ */
446
447	void insque __P((void a, void b));
448	void remque __P((void *a));
449
450	#endif /* __GNUC__ */
451
452	#endif /* _KERNEL */
453
454	#endif /* !_SYS_QUEUE_H_ */

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: rtems-libbsd/ipsec-tools/src/include-glibc/sys/queue.h @ 8645c9d7

Download in other formats: