1 /* 2 * Copyright (c) 1991, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 * 7 * @(#)queue.h 8.1 (Berkeley) 06/02/93 8 */ 9 10 #ifndef _QUEUE_H_ 11 #define _QUEUE_H_ 12 13 /* 14 * This file defines two types of data structures, lists and queues. 15 * 16 * A list is headed by a single forward pointer (or an array of forward 17 * pointers for a hash table header). The elements are doubly linked 18 * so that an arbitrary element can be removed without a need to 19 * traverse the list. New elements can be added to the list after 20 * an existing element or at the head of the list. 21 * 22 * A queue is headed by a pair of pointers, one to the head of the list 23 * and the other to the tail of the list. The elements are doubly linked 24 * so that an arbitrary element can be removed without a need to 25 * traverse the list. New elements can be added to the list after 26 * an existing element, at the head of the list, or at the end of 27 * the list. 28 * 29 * Note that the implementation used here avoids the need to special 30 * case inserting into an empty list, deleting the last element from 31 * a list, or inserting at the beginning or end of a list. The drawback 32 * to this method is that it is not possible to traverse a list or 33 * queue backwards. 34 */ 35 36 struct queue_entry { 37 void *qe_next; /* next element */ 38 void **qe_prev; /* address of previous next element */ 39 }; 40 41 struct list_entry { 42 void *le_next; /* next element */ 43 }; 44 45 /* 46 * Value for pointers on removed entries. 47 */ 48 #define NOLIST (void *)0xdead 49 50 /* 51 * Queue functions. 52 */ 53 #define queue_init(head) { \ 54 (head)->qe_next = 0; \ 55 (head)->qe_prev = &(head)->qe_next; \ 56 } 57 58 #define queue_enter_tail(head, elm, type, field) { \ 59 (elm)->field.qe_next = 0; \ 60 (elm)->field.qe_prev = (head)->qe_prev; \ 61 *(head)->qe_prev = (elm); \ 62 (head)->qe_prev = &(elm)->field.qe_next; \ 63 } 64 65 #define queue_enter_head(head, elm, type, field) { \ 66 type queue_ptr; \ 67 if (queue_ptr = (head)->qe_next) \ 68 queue_ptr->field.qe_prev = &(elm)->field.qe_next; \ 69 else \ 70 (head)->qe_prev = &(elm)->field.qe_next; \ 71 (head)->qe_next = (elm); \ 72 (elm)->field.qe_next = queue_ptr; \ 73 (elm)->field.qe_prev = &(head)->qe_next; \ 74 } 75 76 #define queue_insert_after(head, listelm, elm, type, field) { \ 77 type queue_ptr; \ 78 if (queue_ptr = (listelm)->qe_next) \ 79 queue_ptr->field.qe_prev = &(elm)->field.qe_next; \ 80 else \ 81 (head)->qe_prev = &(elm)->field.qe_next; \ 82 (listelm)->qe_next = (elm); \ 83 (elm)->field.qe_next = queue_ptr; \ 84 (elm)->field.qe_prev = &(listelm)->qe_next; \ 85 } 86 87 #define queue_remove(head, elm, type, field) { \ 88 type queue_ptr; \ 89 if (queue_ptr = (elm)->field.qe_next) \ 90 queue_ptr->field.qe_prev = (elm)->field.qe_prev; \ 91 else \ 92 (head)->qe_prev = (elm)->field.qe_prev; \ 93 *(elm)->field.qe_prev = queue_ptr; \ 94 (elm)->field.qe_next = NOLIST; \ 95 (elm)->field.qe_prev = NOLIST; \ 96 } 97 98 /* 99 * List functions. 100 */ 101 #define list_enter_head(head, elm, type, field) { \ 102 type queue_ptr; \ 103 if (queue_ptr = (head)->le_next) \ 104 queue_ptr->field.qe_prev = &(elm)->field.qe_next; \ 105 (head)->le_next = (elm); \ 106 (elm)->field.qe_next = queue_ptr; \ 107 (elm)->field.qe_prev = &(head)->le_next; \ 108 } 109 110 #define list_insert_after(listelm, elm, type, field) { \ 111 type queue_ptr; \ 112 if (queue_ptr = (listelm)->qe_next) \ 113 queue_ptr->field.qe_prev = &(elm)->field.qe_next; \ 114 (listelm)->qe_next = (elm); \ 115 (elm)->field.qe_next = queue_ptr; \ 116 (elm)->field.qe_prev = &(listelm)->qe_next; \ 117 } 118 119 #define list_remove(elm, type, field) { \ 120 type queue_ptr; \ 121 if (queue_ptr = (elm)->field.qe_next) \ 122 queue_ptr->field.qe_prev = (elm)->field.qe_prev; \ 123 *(elm)->field.qe_prev = queue_ptr; \ 124 (elm)->field.qe_next = NOLIST; \ 125 (elm)->field.qe_prev = NOLIST; \ 126 } 127 128 #endif /* !_QUEUE_H_ */ 129