FreeBSD/Linux Kernel Cross Reference
sys/kern/queue.h
1 /*
2 * Mach Operating System
3 * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
4 * All Rights Reserved.
5 *
6 * Permission to use, copy, modify and distribute this software and its
7 * documentation is hereby granted, provided that both the copyright
8 * notice and this permission notice appear in all copies of the
9 * software, derivative works or modified versions, and any portions
10 * thereof, and that both notices appear in supporting documentation.
11 *
12 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
13 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
14 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
15 *
16 * Carnegie Mellon requests users of this software to return to
17 *
18 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
19 * School of Computer Science
20 * Carnegie Mellon University
21 * Pittsburgh PA 15213-3890
22 *
23 * any improvements or extensions that they make and grant Carnegie Mellon rights
24 * to redistribute these changes.
25 */
26 /*
27 * HISTORY
28 * $Log: queue.h,v $
29 * Revision 2.5 92/05/21 17:15:24 jfriedl
30 * Removed coment starter from within comments to shut up gcc warnings.
31 * [92/05/16 jfriedl]
32 *
33 * Revision 2.4 91/05/14 16:45:55 mrt
34 * Correcting copyright
35 *
36 * Revision 2.3 91/02/05 17:28:43 mrt
37 * Changed to new Mach copyright
38 * [91/02/01 16:16:28 mrt]
39 *
40 * Revision 2.2 89/09/08 11:26:11 dbg
41 * Streamlined generic queue macros.
42 * [89/08/17 dbg]
43 *
44 * 19-Dec-88 David Golub (dbg) at Carnegie-Mellon University
45 * Added queue_remove_last; removed round_queue. [Changes from
46 * mwyoung: 19 Dec 88.]
47 *
48 * 29-Nov-88 David Golub (dbg) at Carnegie-Mellon University
49 * Removed include of cputypes.h. Added queue_iterate.
50 * Split into two groups the macros that operate directly on
51 * queues (or expect the queue chain to be first in a structure)
52 * and those that operate on generic structures (where the chain
53 * may be anywhere).
54 *
55 * 17-Jan-88 Daniel Julin (dpj) at Carnegie-Mellon University
56 * Added queue_enter_first, queue_last and queue_prev for use by
57 * the TCP netport code.
58 *
59 * 12-Jun-85 Avadis Tevanian (avie) at Carnegie-Mellon University
60 * Created.
61 *
62 */
63 /*
64 * File: queue.h
65 * Author: Avadis Tevanian, Jr.
66 * Date: 1985
67 *
68 * Type definitions for generic queues.
69 *
70 */
71
72 #ifndef _KERN_QUEUE_H_
73 #define _KERN_QUEUE_H_
74
75 #include <kern/lock.h>
76
77 /*
78 * Queue of abstract objects. Queue is maintained
79 * within that object.
80 *
81 * Supports fast removal from within the queue.
82 *
83 * How to declare a queue of elements of type "foo_t":
84 * In the "*foo_t" type, you must have a field of
85 * type "queue_chain_t" to hold together this queue.
86 * There may be more than one chain through a
87 * "foo_t", for use by different queues.
88 *
89 * Declare the queue as a "queue_t" type.
90 *
91 * Elements of the queue (of type "foo_t", that is)
92 * are referred to by reference, and cast to type
93 * "queue_entry_t" within this module.
94 */
95
96 /*
97 * A generic doubly-linked list (queue).
98 */
99
100 struct queue_entry {
101 struct queue_entry *next; /* next element */
102 struct queue_entry *prev; /* previous element */
103 };
104
105 typedef struct queue_entry *queue_t;
106 typedef struct queue_entry queue_head_t;
107 typedef struct queue_entry queue_chain_t;
108 typedef struct queue_entry *queue_entry_t;
109
110 /*
111 * enqueue puts "elt" on the "queue".
112 * dequeue returns the first element in the "queue".
113 * remqueue removes the specified "elt" from the specified "queue".
114 */
115
116 #define enqueue(queue,elt) enqueue_tail(queue, elt)
117 #define dequeue(queue) dequeue_head(queue)
118
119 void enqueue_head();
120 void enqueue_tail();
121 queue_entry_t dequeue_head();
122 queue_entry_t dequeue_tail();
123 void remqueue();
124
125 /*
126 * Macro: queue_init
127 * Function:
128 * Initialize the given queue.
129 * Header:
130 * void queue_init(q)
131 * queue_t q; *MODIFIED*
132 */
133 #define queue_init(q) ((q)->next = (q)->prev = q)
134
135 /*
136 * Macro: queue_first
137 * Function:
138 * Returns the first entry in the queue,
139 * Header:
140 * queue_entry_t queue_first(q)
141 * queue_t q; *IN*
142 */
143 #define queue_first(q) ((q)->next)
144
145 /*
146 * Macro: queue_next
147 * Function:
148 * Returns the entry after an item in the queue.
149 * Header:
150 * queue_entry_t queue_next(qc)
151 * queue_t qc;
152 */
153 #define queue_next(qc) ((qc)->next)
154
155 /*
156 * Macro: queue_last
157 * Function:
158 * Returns the last entry in the queue.
159 * Header:
160 * queue_entry_t queue_last(q)
161 * queue_t q; *IN*
162 */
163 #define queue_last(q) ((q)->prev)
164
165 /*
166 * Macro: queue_prev
167 * Function:
168 * Returns the entry before an item in the queue.
169 * Header:
170 * queue_entry_t queue_prev(qc)
171 * queue_t qc;
172 */
173 #define queue_prev(qc) ((qc)->prev)
174
175 /*
176 * Macro: queue_end
177 * Function:
178 * Tests whether a new entry is really the end of
179 * the queue.
180 * Header:
181 * boolean_t queue_end(q, qe)
182 * queue_t q;
183 * queue_entry_t qe;
184 */
185 #define queue_end(q, qe) ((q) == (qe))
186
187 /*
188 * Macro: queue_empty
189 * Function:
190 * Tests whether a queue is empty.
191 * Header:
192 * boolean_t queue_empty(q)
193 * queue_t q;
194 */
195 #define queue_empty(q) queue_end((q), queue_first(q))
196
197
198 /*----------------------------------------------------------------*/
199 /*
200 * Macros that operate on generic structures. The queue
201 * chain may be at any location within the structure, and there
202 * may be more than one chain.
203 */
204
205 /*
206 * Macro: queue_enter
207 * Function:
208 * Insert a new element at the tail of the queue.
209 * Header:
210 * void queue_enter(q, elt, type, field)
211 * queue_t q;
212 * <type> elt;
213 * <type> is what's in our queue
214 * <field> is the chain field in (*<type>)
215 */
216 #define queue_enter(head, elt, type, field) \
217 { \
218 register queue_entry_t prev; \
219 \
220 prev = (head)->prev; \
221 if ((head) == prev) { \
222 (head)->next = (queue_entry_t) (elt); \
223 } \
224 else { \
225 ((type)prev)->field.next = (queue_entry_t)(elt);\
226 } \
227 (elt)->field.prev = prev; \
228 (elt)->field.next = head; \
229 (head)->prev = (queue_entry_t) elt; \
230 }
231
232 /*
233 * Macro: queue_enter_first
234 * Function:
235 * Insert a new element at the head of the queue.
236 * Header:
237 * void queue_enter_first(q, elt, type, field)
238 * queue_t q;
239 * <type> elt;
240 * <type> is what's in our queue
241 * <field> is the chain field in (*<type>)
242 */
243 #define queue_enter_first(head, elt, type, field) \
244 { \
245 register queue_entry_t next; \
246 \
247 next = (head)->next; \
248 if ((head) == next) { \
249 (head)->prev = (queue_entry_t) (elt); \
250 } \
251 else { \
252 ((type)next)->field.prev = (queue_entry_t)(elt);\
253 } \
254 (elt)->field.next = next; \
255 (elt)->field.prev = head; \
256 (head)->next = (queue_entry_t) elt; \
257 }
258
259 /*
260 * Macro: queue_field [internal use only]
261 * Function:
262 * Find the queue_chain_t (or queue_t) for the
263 * given element (thing) in the given queue (head)
264 */
265 #define queue_field(head, thing, type, field) \
266 (((head) == (thing)) ? (head) : &((type)(thing))->field)
267
268 /*
269 * Macro: queue_remove
270 * Function:
271 * Remove an arbitrary item from the queue.
272 * Header:
273 * void queue_remove(q, qe, type, field)
274 * arguments as in queue_enter
275 */
276 #define queue_remove(head, elt, type, field) \
277 { \
278 register queue_entry_t next, prev; \
279 \
280 next = (elt)->field.next; \
281 prev = (elt)->field.prev; \
282 \
283 if ((head) == next) \
284 (head)->prev = prev; \
285 else \
286 ((type)next)->field.prev = prev; \
287 \
288 if ((head) == prev) \
289 (head)->next = next; \
290 else \
291 ((type)prev)->field.next = next; \
292 }
293
294 /*
295 * Macro: queue_remove_first
296 * Function:
297 * Remove and return the entry at the head of
298 * the queue.
299 * Header:
300 * queue_remove_first(head, entry, type, field)
301 * entry is returned by reference
302 */
303 #define queue_remove_first(head, entry, type, field) \
304 { \
305 register queue_entry_t next; \
306 \
307 (entry) = (type) ((head)->next); \
308 next = (entry)->field.next; \
309 \
310 if ((head) == next) \
311 (head)->prev = (head); \
312 else \
313 ((type)(next))->field.prev = (head); \
314 (head)->next = next; \
315 }
316
317 /*
318 * Macro: queue_remove_last
319 * Function:
320 * Remove and return the entry at the tail of
321 * the queue.
322 * Header:
323 * queue_remove_last(head, entry, type, field)
324 * entry is returned by reference
325 */
326 #define queue_remove_last(head, entry, type, field) \
327 { \
328 register queue_entry_t prev; \
329 \
330 (entry) = (type) ((head)->prev); \
331 prev = (entry)->field.prev; \
332 \
333 if ((head) == prev) \
334 (head)->next = (head); \
335 else \
336 ((type)(prev))->field.next = (head); \
337 (head)->prev = prev; \
338 }
339
340 /*
341 * Macro: queue_assign
342 */
343 #define queue_assign(to, from, type, field) \
344 { \
345 ((type)((from)->prev))->field.next = (to); \
346 ((type)((from)->next))->field.prev = (to); \
347 *to = *from; \
348 }
349
350 /*
351 * Macro: queue_iterate
352 * Function:
353 * iterate over each item in the queue.
354 * Generates a 'for' loop, setting elt to
355 * each item in turn (by reference).
356 * Header:
357 * queue_iterate(q, elt, type, field)
358 * queue_t q;
359 * <type> elt;
360 * <type> is what's in our queue
361 * <field> is the chain field in (*<type>)
362 */
363 #define queue_iterate(head, elt, type, field) \
364 for ((elt) = (type) queue_first(head); \
365 !queue_end((head), (queue_entry_t)(elt)); \
366 (elt) = (type) queue_next(&(elt)->field))
367
368
369
370 /*----------------------------------------------------------------*/
371 /*
372 * Define macros for queues with locks.
373 */
374 struct mpqueue_head {
375 struct queue_entry head; /* header for queue */
376 struct slock lock; /* lock for queue */
377 };
378
379 typedef struct mpqueue_head mpqueue_head_t;
380
381 #define round_mpq(size) (size)
382
383 #define mpqueue_init(q) \
384 { \
385 queue_init(&(q)->head); \
386 simple_lock_init(&(q)->lock); \
387 }
388
389 #define mpenqueue_tail(q, elt) \
390 simple_lock(&(q)->lock); \
391 enqueue_tail(&(q)->head, elt); \
392 simple_unlock(&(q)->lock);
393
394 #define mpdequeue_head(q, elt) \
395 simple_lock(&(q)->lock); \
396 if (queue_empty(&(q)->head)) \
397 *(elt) = 0; \
398 else \
399 *(elt) = dequeue_head(&(q)->head); \
400 simple_unlock(&(q)->lock);
401
402 /*
403 * Old queue stuff, will go away soon.
404 */
405
406 #endif _KERN_QUEUE_H_
Cache object: 15fb2caf0a5f1e776173973b27c6844e
|