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