1ab71945rwatson/*-
2ab71945rwatson * Copyright (c) 1991, 1993
3ab71945rwatson *	The Regents of the University of California.  All rights reserved.
4ab71945rwatson *
5ab71945rwatson * Redistribution and use in source and binary forms, with or without
6ab71945rwatson * modification, are permitted provided that the following conditions
7ab71945rwatson * are met:
8ab71945rwatson * 1. Redistributions of source code must retain the above copyright
9ab71945rwatson *    notice, this list of conditions and the following disclaimer.
10ab71945rwatson * 2. Redistributions in binary form must reproduce the above copyright
11ab71945rwatson *    notice, this list of conditions and the following disclaimer in the
12ab71945rwatson *    documentation and/or other materials provided with the distribution.
137e6cabdimp * 3. Neither the name of the University nor the names of its contributors
14ab71945rwatson *    may be used to endorse or promote products derived from this software
15ab71945rwatson *    without specific prior written permission.
16ab71945rwatson *
17ab71945rwatson * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18ab71945rwatson * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19ab71945rwatson * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20ab71945rwatson * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21ab71945rwatson * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22ab71945rwatson * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23ab71945rwatson * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24ab71945rwatson * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25ab71945rwatson * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26ab71945rwatson * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27ab71945rwatson * SUCH DAMAGE.
28ab71945rwatson *
29ab71945rwatson *	@(#)queue.h	8.5 (Berkeley) 8/20/94
30ab71945rwatson *
31ab71945rwatson * Derived from FreeBSD src/sys/sys/queue.h:1.63.
32ab71945rwatson */
33ab71945rwatson
34ab71945rwatson#ifndef _COMPAT_QUEUE_H_
35ab71945rwatson#define	_COMPAT_QUEUE_H_
36ab71945rwatson
37ab71945rwatson#include <sys/cdefs.h>
38ab71945rwatson
39ab71945rwatson/*
40ab71945rwatson * This file defines four types of data structures: singly-linked lists,
41ab71945rwatson * singly-linked tail queues, lists and tail queues.
42ab71945rwatson *
43ab71945rwatson * A singly-linked list is headed by a single forward pointer. The elements
44ab71945rwatson * are singly linked for minimum space and pointer manipulation overhead at
45ab71945rwatson * the expense of O(n) removal for arbitrary elements. New elements can be
46ab71945rwatson * added to the list after an existing element or at the head of the list.
47ab71945rwatson * Elements being removed from the head of the list should use the explicit
48ab71945rwatson * macro for this purpose for optimum efficiency. A singly-linked list may
49ab71945rwatson * only be traversed in the forward direction.  Singly-linked lists are ideal
50ab71945rwatson * for applications with large datasets and few or no removals or for
51ab71945rwatson * implementing a LIFO queue.
52ab71945rwatson *
53ab71945rwatson * A singly-linked tail queue is headed by a pair of pointers, one to the
54ab71945rwatson * head of the list and the other to the tail of the list. The elements are
55ab71945rwatson * singly linked for minimum space and pointer manipulation overhead at the
56ab71945rwatson * expense of O(n) removal for arbitrary elements. New elements can be added
57ab71945rwatson * to the list after an existing element, at the head of the list, or at the
58ab71945rwatson * end of the list. Elements being removed from the head of the tail queue
59ab71945rwatson * should use the explicit macro for this purpose for optimum efficiency.
60ab71945rwatson * A singly-linked tail queue may only be traversed in the forward direction.
61ab71945rwatson * Singly-linked tail queues are ideal for applications with large datasets
62ab71945rwatson * and few or no removals or for implementing a FIFO queue.
63ab71945rwatson *
64ab71945rwatson * A list is headed by a single forward pointer (or an array of forward
65ab71945rwatson * pointers for a hash table header). The elements are doubly linked
66ab71945rwatson * so that an arbitrary element can be removed without a need to
67ab71945rwatson * traverse the list. New elements can be added to the list before
68ab71945rwatson * or after an existing element or at the head of the list. A list
69ab71945rwatson * may only be traversed in the forward direction.
70ab71945rwatson *
71ab71945rwatson * A tail queue is headed by a pair of pointers, one to the head of the
72ab71945rwatson * list and the other to the tail of the list. The elements are doubly
73ab71945rwatson * linked so that an arbitrary element can be removed without a need to
74ab71945rwatson * traverse the list. New elements can be added to the list before or
75ab71945rwatson * after an existing element, at the head of the list, or at the end of
76ab71945rwatson * the list. A tail queue may be traversed in either direction.
77ab71945rwatson *
78ab71945rwatson * For details on the use of these macros, see the queue(3) manual page.
79ab71945rwatson *
80ab71945rwatson *
81ab71945rwatson *				SLIST	LIST	STAILQ	TAILQ
82ab71945rwatson * _HEAD			+	+	+	+
83ab71945rwatson * _HEAD_INITIALIZER		+	+	+	+
84ab71945rwatson * _ENTRY			+	+	+	+
85ab71945rwatson * _INIT			+	+	+	+
86ab71945rwatson * _EMPTY			+	+	+	+
87ab71945rwatson * _FIRST			+	+	+	+
88ab71945rwatson * _NEXT			+	+	+	+
89ab71945rwatson * _PREV			-	-	-	+
90ab71945rwatson * _LAST			-	-	+	+
91ab71945rwatson * _FOREACH			+	+	+	+
92ab71945rwatson * _FOREACH_SAFE		+	+	+	+
93ab71945rwatson * _FOREACH_REVERSE		-	-	-	+
94ab71945rwatson * _FOREACH_REVERSE_SAFE	-	-	-	+
95ab71945rwatson * _INSERT_HEAD			+	+	+	+
96ab71945rwatson * _INSERT_BEFORE		-	+	-	+
97ab71945rwatson * _INSERT_AFTER		+	+	+	+
98ab71945rwatson * _INSERT_TAIL			-	-	+	+
99ab71945rwatson * _CONCAT			-	-	+	+
100ab71945rwatson * _REMOVE_HEAD			+	-	+	-
101ab71945rwatson * _REMOVE			+	+	+	+
102ab71945rwatson *
103ab71945rwatson */
104ab71945rwatson#ifdef QUEUE_MACRO_DEBUG
105ab71945rwatson/* Store the last 2 places the queue element or head was altered */
106ab71945rwatsonstruct qm_trace {
107ab71945rwatson	char * lastfile;
108ab71945rwatson	int lastline;
109ab71945rwatson	char * prevfile;
110ab71945rwatson	int prevline;
111ab71945rwatson};
112ab71945rwatson
113ab71945rwatson#define	TRACEBUF	struct qm_trace trace;
114ab71945rwatson#define	TRASHIT(x)	do {(x) = (void *)-1;} while (0)
115ab71945rwatson
116ab71945rwatson#define	QMD_TRACE_HEAD(head) do {					\
117ab71945rwatson	(head)->trace.prevline = (head)->trace.lastline;		\
118ab71945rwatson	(head)->trace.prevfile = (head)->trace.lastfile;		\
119ab71945rwatson	(head)->trace.lastline = __LINE__;				\
120ab71945rwatson	(head)->trace.lastfile = __FILE__;				\
121ab71945rwatson} while (0)
122ab71945rwatson
123ab71945rwatson#define	QMD_TRACE_ELEM(elem) do {					\
124ab71945rwatson	(elem)->trace.prevline = (elem)->trace.lastline;		\
125ab71945rwatson	(elem)->trace.prevfile = (elem)->trace.lastfile;		\
126ab71945rwatson	(elem)->trace.lastline = __LINE__;				\
127ab71945rwatson	(elem)->trace.lastfile = __FILE__;				\
128ab71945rwatson} while (0)
129ab71945rwatson
130ab71945rwatson#else
131ab71945rwatson#define	QMD_TRACE_ELEM(elem)
132ab71945rwatson#define	QMD_TRACE_HEAD(head)
133ab71945rwatson#define	TRACEBUF
134ab71945rwatson#define	TRASHIT(x)
135ab71945rwatson#endif	/* QUEUE_MACRO_DEBUG */
136ab71945rwatson
137ab71945rwatson/*
138ab71945rwatson * Singly-linked List declarations.
139ab71945rwatson */
140ab71945rwatson#define	SLIST_HEAD(name, type)						\
141ab71945rwatsonstruct name {								\
142ab71945rwatson	struct type *slh_first;	/* first element */			\
143ab71945rwatson}
144ab71945rwatson
145ab71945rwatson#define	SLIST_HEAD_INITIALIZER(head)					\
146ab71945rwatson	{ NULL }
147ab71945rwatson
148ab71945rwatson#define	SLIST_ENTRY(type)						\
149ab71945rwatsonstruct {								\
150ab71945rwatson	struct type *sle_next;	/* next element */			\
151ab71945rwatson}
152ab71945rwatson
153ab71945rwatson/*
154ab71945rwatson * Singly-linked List functions.
155ab71945rwatson */
156ab71945rwatson#define	SLIST_EMPTY(head)	((head)->slh_first == NULL)
157ab71945rwatson
158ab71945rwatson#define	SLIST_FIRST(head)	((head)->slh_first)
159ab71945rwatson
160ab71945rwatson#define	SLIST_FOREACH(var, head, field)					\
161ab71945rwatson	for ((var) = SLIST_FIRST((head));				\
162ab71945rwatson	    (var);							\
163ab71945rwatson	    (var) = SLIST_NEXT((var), field))
164ab71945rwatson
165ab71945rwatson#define	SLIST_FOREACH_SAFE(var, head, field, tvar)			\
166ab71945rwatson	for ((var) = SLIST_FIRST((head));				\
167ab71945rwatson	    (var) && ((tvar) = SLIST_NEXT((var), field), 1);		\
168ab71945rwatson	    (var) = (tvar))
169ab71945rwatson
170ab71945rwatson#define	SLIST_FOREACH_PREVPTR(var, varp, head, field)			\
171ab71945rwatson	for ((varp) = &SLIST_FIRST((head));				\
172ab71945rwatson	    ((var) = *(varp)) != NULL;					\
173ab71945rwatson	    (varp) = &SLIST_NEXT((var), field))
174ab71945rwatson
175ab71945rwatson#define	SLIST_INIT(head) do {						\
176ab71945rwatson	SLIST_FIRST((head)) = NULL;					\
177ab71945rwatson} while (0)
178ab71945rwatson
179ab71945rwatson#define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
180ab71945rwatson	SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field);	\
181ab71945rwatson	SLIST_NEXT((slistelm), field) = (elm);				\
182ab71945rwatson} while (0)
183ab71945rwatson
184ab71945rwatson#define	SLIST_INSERT_HEAD(head, elm, field) do {			\
185ab71945rwatson	SLIST_NEXT((elm), field) = SLIST_FIRST((head));			\
186ab71945rwatson	SLIST_FIRST((head)) = (elm);					\
187ab71945rwatson} while (0)
188ab71945rwatson
189ab71945rwatson#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
190ab71945rwatson
191ab71945rwatson#define	SLIST_REMOVE(head, elm, type, field) do {			\
192ab71945rwatson	if (SLIST_FIRST((head)) == (elm)) {				\
193ab71945rwatson		SLIST_REMOVE_HEAD((head), field);			\
194ab71945rwatson	}								\
195ab71945rwatson	else {								\
196ab71945rwatson		struct type *curelm = SLIST_FIRST((head));		\
197ab71945rwatson		while (SLIST_NEXT(curelm, field) != (elm))		\
198ab71945rwatson			curelm = SLIST_NEXT(curelm, field);		\
199ab71945rwatson		SLIST_NEXT(curelm, field) =				\
200ab71945rwatson		    SLIST_NEXT(SLIST_NEXT(curelm, field), field);	\
201ab71945rwatson	}								\
202ab71945rwatson	TRASHIT((elm)->field.sle_next);					\
203ab71945rwatson} while (0)
204ab71945rwatson
205ab71945rwatson#define	SLIST_REMOVE_HEAD(head, field) do {				\
206ab71945rwatson	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);	\
207ab71945rwatson} while (0)
208ab71945rwatson
209ab71945rwatson/*
210ab71945rwatson * Singly-linked Tail queue declarations.
211ab71945rwatson */
212ab71945rwatson#define	STAILQ_HEAD(name, type)						\
213ab71945rwatsonstruct name {								\
214ab71945rwatson	struct type *stqh_first;/* first element */			\
215ab71945rwatson	struct type **stqh_last;/* addr of last next element */		\
216ab71945rwatson}
217ab71945rwatson
218ab71945rwatson#define	STAILQ_HEAD_INITIALIZER(head)					\
219ab71945rwatson	{ NULL, &(head).stqh_first }
220ab71945rwatson
221ab71945rwatson#define	STAILQ_ENTRY(type)						\
222ab71945rwatsonstruct {								\
223ab71945rwatson	struct type *stqe_next;	/* next element */			\
224ab71945rwatson}
225ab71945rwatson
226ab71945rwatson/*
227ab71945rwatson * Singly-linked Tail queue functions.
228ab71945rwatson */
229ab71945rwatson#define	STAILQ_CONCAT(head1, head2) do {				\
230ab71945rwatson	if (!STAILQ_EMPTY((head2))) {					\
231ab71945rwatson		*(head1)->stqh_last = (head2)->stqh_first;		\
232