1 /* 2 * Copyright (c) 1991 Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * The Mach Operating System project at Carnegie-Mellon University. 7 * 8 * %sccs.include.redist.c% 9 * 10 * @(#)queue.h 7.3 (Berkeley) 04/21/91 11 * 12 * 13 * Copyright (c) 1987, 1990 Carnegie-Mellon University. 14 * All rights reserved. 15 * 16 * Author: Avadis Tevanian, Jr. 17 * 18 * Permission to use, copy, modify and distribute this software and 19 * its documentation is hereby granted, provided that both the copyright 20 * notice and this permission notice appear in all copies of the 21 * software, derivative works or modified versions, and any portions 22 * thereof, and that both notices appear in supporting documentation. 23 * 24 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" 25 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND 26 * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. 27 * 28 * Carnegie Mellon requests users of this software to return to 29 * 30 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU 31 * School of Computer Science 32 * Carnegie Mellon University 33 * Pittsburgh PA 15213-3890 34 * 35 * any improvements or extensions that they make and grant Carnegie the 36 * rights to redistribute these changes. 37 */ 38 39 /* 40 * Type definitions for generic queues. 41 */ 42 43 #ifndef _QUEUE_H_ 44 #define _QUEUE_H_ 45 46 struct queue_entry { 47 struct queue_entry *next; /* next element */ 48 struct queue_entry *prev; /* previous element */ 49 }; 50 51 typedef struct queue_entry *queue_t; 52 typedef struct queue_entry queue_head_t; 53 typedef struct queue_entry queue_chain_t; 54 typedef struct queue_entry *queue_entry_t; 55 56 #define round_queue(size) (((size)+7) & (~7)) 57 58 #define enqueue(queue,elt) enqueue_tail(queue, elt) 59 #define dequeue(queue) dequeue_head(queue) 60 61 #define enqueue_head(queue,elt) insque(elt,queue) 62 #define enqueue_tail(queue,elt) insque(elt,(queue)->prev) 63 #define remqueue(queue,elt) remque(elt) 64 65 #define queue_init(q) ((q)->next = (q)->prev = q) 66 #define queue_first(q) ((q)->next) 67 #define queue_next(qc) ((qc)->next) 68 #define queue_end(q, qe) ((q) == (qe)) 69 #define queue_empty(q) queue_end((q), queue_first(q)) 70 71 #define queue_enter(head, elt, type, field) { \ 72 if (queue_empty((head))) { \ 73 (head)->next = (queue_entry_t) elt; \ 74 (head)->prev = (queue_entry_t) elt; \ 75 (elt)->field.next = head; \ 76 (elt)->field.prev = head; \ 77 } else { \ 78 register queue_entry_t prev = (head)->prev; \ 79 (elt)->field.prev = prev; \ 80 (elt)->field.next = head; \ 81 (head)->prev = (queue_entry_t)(elt); \ 82 ((type)prev)->field.next = (queue_entry_t)(elt);\ 83 } \ 84 } 85 86 #define queue_field(head, thing, type, field) \ 87 (((head) == (thing)) ? (head) : &((type)(thing))->field) 88 89 #define queue_remove(head, elt, type, field) { \ 90 register queue_entry_t next = (elt)->field.next; \ 91 register queue_entry_t prev = (elt)->field.prev; \ 92 queue_field((head), next, type, field)->prev = prev; \ 93 queue_field((head), prev, type, field)->next = next; \ 94 } 95 96 #define queue_assign(to, from, type, field) { \ 97 ((type)((from)->prev))->field.next = (to); \ 98 ((type)((from)->next))->field.prev = (to); \ 99 *to = *from; \ 100 } 101 102 #define queue_remove_first(h, e, t, f) { \ 103 e = (t) queue_first((h)); \ 104 queue_remove((h), (e), t, f); \ 105 } 106 107 #endif /* !_QUEUE_H_ */ 108