root / audio / sys-queue.h @ 43057ab1
History | View | Annotate | Download (8.2 kB)
1 | 1d14ffa9 | bellard | /*
|
---|---|---|---|
2 | 1d14ffa9 | bellard | * Copyright (c) 1991, 1993
|
3 | 1d14ffa9 | bellard | * The Regents of the University of California. All rights reserved.
|
4 | 1d14ffa9 | bellard | *
|
5 | 1d14ffa9 | bellard | * Redistribution and use in source and binary forms, with or without
|
6 | 1d14ffa9 | bellard | * modification, are permitted provided that the following conditions
|
7 | 1d14ffa9 | bellard | * are met:
|
8 | 1d14ffa9 | bellard | * 1. Redistributions of source code must retain the above copyright
|
9 | 1d14ffa9 | bellard | * notice, this list of conditions and the following disclaimer.
|
10 | 1d14ffa9 | bellard | * 2. Redistributions in binary form must reproduce the above copyright
|
11 | 1d14ffa9 | bellard | * notice, this list of conditions and the following disclaimer in the
|
12 | 1d14ffa9 | bellard | * documentation and/or other materials provided with the distribution.
|
13 | 1d14ffa9 | bellard | * 4. Neither the name of the University nor the names of its contributors
|
14 | 1d14ffa9 | bellard | * may be used to endorse or promote products derived from this software
|
15 | 1d14ffa9 | bellard | * without specific prior written permission.
|
16 | 1d14ffa9 | bellard | *
|
17 | 1d14ffa9 | bellard | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
|
18 | 1d14ffa9 | bellard | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
|
19 | 1d14ffa9 | bellard | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
|
20 | 1d14ffa9 | bellard | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
|
21 | 1d14ffa9 | bellard | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
|
22 | 1d14ffa9 | bellard | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
|
23 | 1d14ffa9 | bellard | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
|
24 | 1d14ffa9 | bellard | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
|
25 | 1d14ffa9 | bellard | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
|
26 | 1d14ffa9 | bellard | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
|
27 | 1d14ffa9 | bellard | * SUCH DAMAGE.
|
28 | 1d14ffa9 | bellard | *
|
29 | 1d14ffa9 | bellard | * @(#)queue.h 8.3 (Berkeley) 12/13/93
|
30 | 1d14ffa9 | bellard | */
|
31 | 1d14ffa9 | bellard | |
32 | 1d14ffa9 | bellard | #ifndef _SYS_QUEUE_H
|
33 | 1d14ffa9 | bellard | #define _SYS_QUEUE_H 1 |
34 | 1d14ffa9 | bellard | |
35 | 1d14ffa9 | bellard | /*
|
36 | 1d14ffa9 | bellard | * This file defines three types of data structures: lists, tail queues,
|
37 | 1d14ffa9 | bellard | * and circular queues.
|
38 | 1d14ffa9 | bellard | *
|
39 | 1d14ffa9 | bellard | * A list is headed by a single forward pointer (or an array of forward
|
40 | 1d14ffa9 | bellard | * pointers for a hash table header). The elements are doubly linked
|
41 | 1d14ffa9 | bellard | * so that an arbitrary element can be removed without a need to
|
42 | 1d14ffa9 | bellard | * traverse the list. New elements can be added to the list after
|
43 | 1d14ffa9 | bellard | * an existing element or at the head of the list. A list may only be
|
44 | 1d14ffa9 | bellard | * traversed in the forward direction.
|
45 | 1d14ffa9 | bellard | *
|
46 | 1d14ffa9 | bellard | * A tail queue is headed by a pair of pointers, one to the head of the
|
47 | 1d14ffa9 | bellard | * list and the other to the tail of the list. The elements are doubly
|
48 | 1d14ffa9 | bellard | * linked so that an arbitrary element can be removed without a need to
|
49 | 1d14ffa9 | bellard | * traverse the list. New elements can be added to the list after
|
50 | 1d14ffa9 | bellard | * an existing element, at the head of the list, or at the end of the
|
51 | 1d14ffa9 | bellard | * list. A tail queue may only be traversed in the forward direction.
|
52 | 1d14ffa9 | bellard | *
|
53 | 1d14ffa9 | bellard | * A circle queue is headed by a pair of pointers, one to the head of the
|
54 | 1d14ffa9 | bellard | * list and the other to the tail of the list. The elements are doubly
|
55 | 1d14ffa9 | bellard | * linked so that an arbitrary element can be removed without a need to
|
56 | 1d14ffa9 | bellard | * traverse the list. New elements can be added to the list before or after
|
57 | 1d14ffa9 | bellard | * an existing element, at the head of the list, or at the end of the list.
|
58 | 1d14ffa9 | bellard | * A circle queue may be traversed in either direction, but has a more
|
59 | 1d14ffa9 | bellard | * complex end of list detection.
|
60 | 1d14ffa9 | bellard | *
|
61 | 1d14ffa9 | bellard | * For details on the use of these macros, see the queue(3) manual page.
|
62 | 1d14ffa9 | bellard | */
|
63 | 1d14ffa9 | bellard | |
64 | 1d14ffa9 | bellard | /*
|
65 | 1d14ffa9 | bellard | * List definitions.
|
66 | 1d14ffa9 | bellard | */
|
67 | 1d14ffa9 | bellard | #define LIST_HEAD(name, type) \
|
68 | 1d14ffa9 | bellard | struct name { \
|
69 | 1d14ffa9 | bellard | struct type *lh_first; /* first element */ \ |
70 | 1d14ffa9 | bellard | } |
71 | 1d14ffa9 | bellard | |
72 | 1d14ffa9 | bellard | #define LIST_ENTRY(type) \
|
73 | 1d14ffa9 | bellard | struct { \
|
74 | 1d14ffa9 | bellard | struct type *le_next; /* next element */ \ |
75 | 1d14ffa9 | bellard | struct type **le_prev; /* address of previous next element */ \ |
76 | 1d14ffa9 | bellard | } |
77 | 1d14ffa9 | bellard | |
78 | 1d14ffa9 | bellard | /*
|
79 | 1d14ffa9 | bellard | * List functions.
|
80 | 1d14ffa9 | bellard | */
|
81 | 1d14ffa9 | bellard | #define LIST_INIT(head) { \
|
82 | 1d14ffa9 | bellard | (head)->lh_first = NULL; \
|
83 | 1d14ffa9 | bellard | } |
84 | 1d14ffa9 | bellard | |
85 | 1d14ffa9 | bellard | #define LIST_INSERT_AFTER(listelm, elm, field) { \
|
86 | 1d14ffa9 | bellard | if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ |
87 | 1d14ffa9 | bellard | (listelm)->field.le_next->field.le_prev = \ |
88 | 1d14ffa9 | bellard | &(elm)->field.le_next; \ |
89 | 1d14ffa9 | bellard | (listelm)->field.le_next = (elm); \ |
90 | 1d14ffa9 | bellard | (elm)->field.le_prev = &(listelm)->field.le_next; \ |
91 | 1d14ffa9 | bellard | } |
92 | 1d14ffa9 | bellard | |
93 | 1d14ffa9 | bellard | #define LIST_INSERT_HEAD(head, elm, field) { \
|
94 | 1d14ffa9 | bellard | if (((elm)->field.le_next = (head)->lh_first) != NULL) \ |
95 | 1d14ffa9 | bellard | (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ |
96 | 1d14ffa9 | bellard | (head)->lh_first = (elm); \ |
97 | 1d14ffa9 | bellard | (elm)->field.le_prev = &(head)->lh_first; \ |
98 | 1d14ffa9 | bellard | } |
99 | 1d14ffa9 | bellard | |
100 | 1d14ffa9 | bellard | #define LIST_REMOVE(elm, field) { \
|
101 | 1d14ffa9 | bellard | if ((elm)->field.le_next != NULL) \ |
102 | 1d14ffa9 | bellard | (elm)->field.le_next->field.le_prev = \ |
103 | 1d14ffa9 | bellard | (elm)->field.le_prev; \ |
104 | 1d14ffa9 | bellard | *(elm)->field.le_prev = (elm)->field.le_next; \ |
105 | 1d14ffa9 | bellard | } |
106 | 1d14ffa9 | bellard | |
107 | 1d14ffa9 | bellard | /*
|
108 | 1d14ffa9 | bellard | * Tail queue definitions.
|
109 | 1d14ffa9 | bellard | */
|
110 | 1d14ffa9 | bellard | #define TAILQ_HEAD(name, type) \
|
111 | 1d14ffa9 | bellard | struct name { \
|
112 | 1d14ffa9 | bellard | struct type *tqh_first; /* first element */ \ |
113 | 1d14ffa9 | bellard | struct type **tqh_last; /* addr of last next element */ \ |
114 | 1d14ffa9 | bellard | } |
115 | 1d14ffa9 | bellard | |
116 | 1d14ffa9 | bellard | #define TAILQ_ENTRY(type) \
|
117 | 1d14ffa9 | bellard | struct { \
|
118 | 1d14ffa9 | bellard | struct type *tqe_next; /* next element */ \ |
119 | 1d14ffa9 | bellard | struct type **tqe_prev; /* address of previous next element */ \ |
120 | 1d14ffa9 | bellard | } |
121 | 1d14ffa9 | bellard | |
122 | 1d14ffa9 | bellard | /*
|
123 | 1d14ffa9 | bellard | * Tail queue functions.
|
124 | 1d14ffa9 | bellard | */
|
125 | 1d14ffa9 | bellard | #define TAILQ_INIT(head) { \
|
126 | 1d14ffa9 | bellard | (head)->tqh_first = NULL; \
|
127 | 1d14ffa9 | bellard | (head)->tqh_last = &(head)->tqh_first; \ |
128 | 1d14ffa9 | bellard | } |
129 | 1d14ffa9 | bellard | |
130 | 1d14ffa9 | bellard | #define TAILQ_INSERT_HEAD(head, elm, field) { \
|
131 | 1d14ffa9 | bellard | if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ |
132 | 1d14ffa9 | bellard | (elm)->field.tqe_next->field.tqe_prev = \ |
133 | 1d14ffa9 | bellard | &(elm)->field.tqe_next; \ |
134 | 1d14ffa9 | bellard | else \
|
135 | 1d14ffa9 | bellard | (head)->tqh_last = &(elm)->field.tqe_next; \ |
136 | 1d14ffa9 | bellard | (head)->tqh_first = (elm); \ |
137 | 1d14ffa9 | bellard | (elm)->field.tqe_prev = &(head)->tqh_first; \ |
138 | 1d14ffa9 | bellard | } |
139 | 1d14ffa9 | bellard | |
140 | 1d14ffa9 | bellard | #define TAILQ_INSERT_TAIL(head, elm, field) { \
|
141 | 1d14ffa9 | bellard | (elm)->field.tqe_next = NULL; \
|
142 | 1d14ffa9 | bellard | (elm)->field.tqe_prev = (head)->tqh_last; \ |
143 | 1d14ffa9 | bellard | *(head)->tqh_last = (elm); \ |
144 | 1d14ffa9 | bellard | (head)->tqh_last = &(elm)->field.tqe_next; \ |
145 | 1d14ffa9 | bellard | } |
146 | 1d14ffa9 | bellard | |
147 | 1d14ffa9 | bellard | #define TAILQ_INSERT_AFTER(head, listelm, elm, field) { \
|
148 | 1d14ffa9 | bellard | if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ |
149 | 1d14ffa9 | bellard | (elm)->field.tqe_next->field.tqe_prev = \ |
150 | 1d14ffa9 | bellard | &(elm)->field.tqe_next; \ |
151 | 1d14ffa9 | bellard | else \
|
152 | 1d14ffa9 | bellard | (head)->tqh_last = &(elm)->field.tqe_next; \ |
153 | 1d14ffa9 | bellard | (listelm)->field.tqe_next = (elm); \ |
154 | 1d14ffa9 | bellard | (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ |
155 | 1d14ffa9 | bellard | } |
156 | 1d14ffa9 | bellard | |
157 | 1d14ffa9 | bellard | #define TAILQ_REMOVE(head, elm, field) { \
|
158 | 1d14ffa9 | bellard | if (((elm)->field.tqe_next) != NULL) \ |
159 | 1d14ffa9 | bellard | (elm)->field.tqe_next->field.tqe_prev = \ |
160 | 1d14ffa9 | bellard | (elm)->field.tqe_prev; \ |
161 | 1d14ffa9 | bellard | else \
|
162 | 1d14ffa9 | bellard | (head)->tqh_last = (elm)->field.tqe_prev; \ |
163 | 1d14ffa9 | bellard | *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ |
164 | 1d14ffa9 | bellard | } |
165 | 1d14ffa9 | bellard | |
166 | 1d14ffa9 | bellard | /*
|
167 | 1d14ffa9 | bellard | * Circular queue definitions.
|
168 | 1d14ffa9 | bellard | */
|
169 | 1d14ffa9 | bellard | #define CIRCLEQ_HEAD(name, type) \
|
170 | 1d14ffa9 | bellard | struct name { \
|
171 | 1d14ffa9 | bellard | struct type *cqh_first; /* first element */ \ |
172 | 1d14ffa9 | bellard | struct type *cqh_last; /* last element */ \ |
173 | 1d14ffa9 | bellard | } |
174 | 1d14ffa9 | bellard | |
175 | 1d14ffa9 | bellard | #define CIRCLEQ_ENTRY(type) \
|
176 | 1d14ffa9 | bellard | struct { \
|
177 | 1d14ffa9 | bellard | struct type *cqe_next; /* next element */ \ |
178 | 1d14ffa9 | bellard | struct type *cqe_prev; /* previous element */ \ |
179 | 1d14ffa9 | bellard | } |
180 | 1d14ffa9 | bellard | |
181 | 1d14ffa9 | bellard | /*
|
182 | 1d14ffa9 | bellard | * Circular queue functions.
|
183 | 1d14ffa9 | bellard | */
|
184 | 1d14ffa9 | bellard | #define CIRCLEQ_INIT(head) { \
|
185 | 1d14ffa9 | bellard | (head)->cqh_first = (void *)(head); \
|
186 | 1d14ffa9 | bellard | (head)->cqh_last = (void *)(head); \
|
187 | 1d14ffa9 | bellard | } |
188 | 1d14ffa9 | bellard | |
189 | 1d14ffa9 | bellard | #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) { \
|
190 | 1d14ffa9 | bellard | (elm)->field.cqe_next = (listelm)->field.cqe_next; \ |
191 | 1d14ffa9 | bellard | (elm)->field.cqe_prev = (listelm); \ |
192 | 1d14ffa9 | bellard | if ((listelm)->field.cqe_next == (void *)(head)) \ |
193 | 1d14ffa9 | bellard | (head)->cqh_last = (elm); \ |
194 | 1d14ffa9 | bellard | else \
|
195 | 1d14ffa9 | bellard | (listelm)->field.cqe_next->field.cqe_prev = (elm); \ |
196 | 1d14ffa9 | bellard | (listelm)->field.cqe_next = (elm); \ |
197 | 1d14ffa9 | bellard | } |
198 | 1d14ffa9 | bellard | |
199 | 1d14ffa9 | bellard | #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) { \
|
200 | 1d14ffa9 | bellard | (elm)->field.cqe_next = (listelm); \ |
201 | 1d14ffa9 | bellard | (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ |
202 | 1d14ffa9 | bellard | if ((listelm)->field.cqe_prev == (void *)(head)) \ |
203 | 1d14ffa9 | bellard | (head)->cqh_first = (elm); \ |
204 | 1d14ffa9 | bellard | else \
|
205 | 1d14ffa9 | bellard | (listelm)->field.cqe_prev->field.cqe_next = (elm); \ |
206 | 1d14ffa9 | bellard | (listelm)->field.cqe_prev = (elm); \ |
207 | 1d14ffa9 | bellard | } |
208 | 1d14ffa9 | bellard | |
209 | 1d14ffa9 | bellard | #define CIRCLEQ_INSERT_HEAD(head, elm, field) { \
|
210 | 1d14ffa9 | bellard | (elm)->field.cqe_next = (head)->cqh_first; \ |
211 | 1d14ffa9 | bellard | (elm)->field.cqe_prev = (void *)(head); \
|
212 | 1d14ffa9 | bellard | if ((head)->cqh_last == (void *)(head)) \ |
213 | 1d14ffa9 | bellard | (head)->cqh_last = (elm); \ |
214 | 1d14ffa9 | bellard | else \
|
215 | 1d14ffa9 | bellard | (head)->cqh_first->field.cqe_prev = (elm); \ |
216 | 1d14ffa9 | bellard | (head)->cqh_first = (elm); \ |
217 | 1d14ffa9 | bellard | } |
218 | 1d14ffa9 | bellard | |
219 | 1d14ffa9 | bellard | #define CIRCLEQ_INSERT_TAIL(head, elm, field) { \
|
220 | 1d14ffa9 | bellard | (elm)->field.cqe_next = (void *)(head); \
|
221 | 1d14ffa9 | bellard | (elm)->field.cqe_prev = (head)->cqh_last; \ |
222 | 1d14ffa9 | bellard | if ((head)->cqh_first == (void *)(head)) \ |
223 | 1d14ffa9 | bellard | (head)->cqh_first = (elm); \ |
224 | 1d14ffa9 | bellard | else \
|
225 | 1d14ffa9 | bellard | (head)->cqh_last->field.cqe_next = (elm); \ |
226 | 1d14ffa9 | bellard | (head)->cqh_last = (elm); \ |
227 | 1d14ffa9 | bellard | } |
228 | 1d14ffa9 | bellard | |
229 | 1d14ffa9 | bellard | #define CIRCLEQ_REMOVE(head, elm, field) { \
|
230 | 1d14ffa9 | bellard | if ((elm)->field.cqe_next == (void *)(head)) \ |
231 | 1d14ffa9 | bellard | (head)->cqh_last = (elm)->field.cqe_prev; \ |
232 | 1d14ffa9 | bellard | else \
|
233 | 1d14ffa9 | bellard | (elm)->field.cqe_next->field.cqe_prev = \ |
234 | 1d14ffa9 | bellard | (elm)->field.cqe_prev; \ |
235 | 1d14ffa9 | bellard | if ((elm)->field.cqe_prev == (void *)(head)) \ |
236 | 1d14ffa9 | bellard | (head)->cqh_first = (elm)->field.cqe_next; \ |
237 | 1d14ffa9 | bellard | else \
|
238 | 1d14ffa9 | bellard | (elm)->field.cqe_prev->field.cqe_next = \ |
239 | 1d14ffa9 | bellard | (elm)->field.cqe_next; \ |
240 | 1d14ffa9 | bellard | } |
241 | 1d14ffa9 | bellard | #endif /* sys/queue.h */ |