1 /* 2 * Copyright (c) 1985, Avadis Tevanian, Jr. 3 * Copyright (c) 1987 Carnegie-Mellon University 4 * Copyright (c) 1991 Regents of the University of California. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * The Mach Operating System project at Carnegie-Mellon University. 9 * 10 * The CMU software License Agreement specifies the terms and conditions 11 * for use and redistribution. 12 * 13 * @(#)queue.h 7.2 (Berkeley) 02/05/91 14 */ 15 16 /* 17 * Type definitions for generic queues. 18 */ 19 20 #ifndef _QUEUE_H_ 21 #define _QUEUE_H_ 22 23 struct queue_entry { 24 struct queue_entry *next; /* next element */ 25 struct queue_entry *prev; /* previous element */ 26 }; 27 28 typedef struct queue_entry *queue_t; 29 typedef struct queue_entry queue_head_t; 30 typedef struct queue_entry queue_chain_t; 31 typedef struct queue_entry *queue_entry_t; 32 33 #define round_queue(size) (((size)+7) & (~7)) 34 35 #define enqueue(queue,elt) enqueue_tail(queue, elt) 36 #define dequeue(queue) dequeue_head(queue) 37 38 #define enqueue_head(queue,elt) insque(elt,queue) 39 #define enqueue_tail(queue,elt) insque(elt,(queue)->prev) 40 #define remqueue(queue,elt) remque(elt) 41 42 #define queue_init(q) ((q)->next = (q)->prev = q) 43 #define queue_first(q) ((q)->next) 44 #define queue_next(qc) ((qc)->next) 45 #define queue_end(q, qe) ((q) == (qe)) 46 #define queue_empty(q) queue_end((q), queue_first(q)) 47 48 #define queue_enter(head, elt, type, field) { \ 49 if (queue_empty((head))) { \ 50 (head)->next = (queue_entry_t) elt; \ 51 (head)->prev = (queue_entry_t) elt; \ 52 (elt)->field.next = head; \ 53 (elt)->field.prev = head; \ 54 } else { \ 55 register queue_entry_t prev = (head)->prev; \ 56 (elt)->field.prev = prev; \ 57 (elt)->field.next = head; \ 58 (head)->prev = (queue_entry_t)(elt); \ 59 ((type)prev)->field.next = (queue_entry_t)(elt);\ 60 } \ 61 } 62 63 #define queue_field(head, thing, type, field) \ 64 (((head) == (thing)) ? (head) : &((type)(thing))->field) 65 66 #define queue_remove(head, elt, type, field) { \ 67 register queue_entry_t next = (elt)->field.next; \ 68 register queue_entry_t prev = (elt)->field.prev; \ 69 queue_field((head), next, type, field)->prev = prev; \ 70 queue_field((head), prev, type, field)->next = next; \ 71 } 72 73 #define queue_assign(to, from, type, field) { \ 74 ((type)((from)->prev))->field.next = (to); \ 75 ((type)((from)->next))->field.prev = (to); \ 76 *to = *from; \ 77 } 78 79 #define queue_remove_first(h, e, t, f) { \ 80 e = (t) queue_first((h)); \ 81 queue_remove((h), (e), t, f); \ 82 } 83 84 #endif /* !_QUEUE_H_ */ 85