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.4 (Berkeley) 01/04/94 8 */ 9 10 #ifndef _SYS_QUEUE_H_ 11 #define _SYS_QUEUE_H_ 12 13 /* 14 * This file defines three types of data structures: lists, tail queues, 15 * and circular queues. 16 * 17 * A list is headed by a single forward pointer (or an array of forward 18 * pointers for a hash table header). The elements are doubly linked 19 * so that an arbitrary element can be removed without a need to 20 * traverse the list. New elements can be added to the list after 21 * an existing element or at the head of the list. A list may only be 22 * traversed in the forward direction. 23 * 24 * A tail queue is headed by a pair of pointers, one to the head of the 25 * list and the other to the tail of the list. The elements are doubly 26 * linked so that an arbitrary element can be removed without a need to 27 * traverse the list. New elements can be added to the list after 28 * an existing element, at the head of the list, or at the end of the 29 * list. A tail queue may only be traversed in the forward direction. 30 * 31 * A circle queue is headed by a pair of pointers, one to the head of the 32 * list and the other to the tail of the list. The elements are doubly 33 * linked so that an arbitrary element can be removed without a need to 34 * traverse the list. New elements can be added to the list before or after 35 * an existing element, at the head of the list, or at the end of the list. 36 * A circle queue may be traversed in either direction, but has a more 37 * complex end of list detection. 38 * 39 * For details on the use of these macros, see the queue(3) manual page. 40 */ 41 42 /* 43 * List definitions. 44 */ 45 #define LIST_HEAD(name, type) \ 46 struct name { \ 47 struct type *lh_first; /* first element */ \ 48 } 49 50 #define LIST_ENTRY(type) \ 51 struct { \ 52 struct type *le_next; /* next element */ \ 53 struct type **le_prev; /* address of previous next element */ \ 54 } 55 56 /* 57 * List functions. 58 */ 59 #define LIST_INIT(head) { \ 60 (head)->lh_first = NULL; \ 61 } 62 63 #define LIST_INSERT_AFTER(listelm, elm, field) { \ 64 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ 65 (listelm)->field.le_next->field.le_prev = \ 66 &(elm)->field.le_next; \ 67 (listelm)->field.le_next = (elm); \ 68 (elm)->field.le_prev = &(listelm)->field.le_next; \ 69 } 70 71 #define LIST_INSERT_HEAD(head, elm, field) { \ 72 if (((elm)->field.le_next = (head)->lh_first) != NULL) \ 73 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ 74 (head)->lh_first = (elm); \ 75 (elm)->field.le_prev = &(head)->lh_first; \ 76 } 77 78 #define LIST_REMOVE(elm, field) { \ 79 if ((elm)->field.le_next != NULL) \ 80 (elm)->field.le_next->field.le_prev = \ 81 (elm)->field.le_prev; \ 82 *(elm)->field.le_prev = (elm)->field.le_next; \ 83 } 84 85 /* 86 * Tail queue definitions. 87 */ 88 #define TAILQ_HEAD(name, type) \ 89 struct name { \ 90 struct type *tqh_first; /* first element */ \ 91 struct type **tqh_last; /* addr of last next element */ \ 92 } 93 94 #define TAILQ_ENTRY(type) \ 95 struct { \ 96 struct type *tqe_next; /* next element */ \ 97 struct type **tqe_prev; /* address of previous next element */ \ 98 } 99 100 /* 101 * Tail queue functions. 102 */ 103 #define TAILQ_INIT(head) { \ 104 (head)->tqh_first = NULL; \ 105 (head)->tqh_last = &(head)->tqh_first; \ 106 } 107 108 #define TAILQ_INSERT_HEAD(head, elm, field) { \ 109 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 110 (elm)->field.tqe_next->field.tqe_prev = \ 111 &(elm)->field.tqe_next; \ 112 else \ 113 (head)->tqh_last = &(elm)->field.tqe_next; \ 114 (head)->tqh_first = (elm); \ 115 (elm)->field.tqe_prev = &(head)->tqh_first; \ 116 } 117 118 #define TAILQ_INSERT_TAIL(head, elm, field) { \ 119 (elm)->field.tqe_next = NULL; \ 120 (elm)->field.tqe_prev = (head)->tqh_last; \ 121 *(head)->tqh_last = (elm); \ 122 (head)->tqh_last = &(elm)->field.tqe_next; \ 123 } 124 125 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) { \ 126 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 127 (elm)->field.tqe_next->field.tqe_prev = \ 128 &(elm)->field.tqe_next; \ 129 else \ 130 (head)->tqh_last = &(elm)->field.tqe_next; \ 131 (listelm)->field.tqe_next = (elm); \ 132 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 133 } 134 135 #define TAILQ_REMOVE(head, elm, field) { \ 136 if (((elm)->field.tqe_next) != NULL) \ 137 (elm)->field.tqe_next->field.tqe_prev = \ 138 (elm)->field.tqe_prev; \ 139 else \ 140 (head)->tqh_last = (elm)->field.tqe_prev; \ 141 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 142 } 143 144 /* 145 * Circular queue definitions. 146 */ 147 #define CIRCLEQ_HEAD(name, type) \ 148 struct name { \ 149 struct type *cqh_first; /* first element */ \ 150 struct type *cqh_last; /* last element */ \ 151 } 152 153 #define CIRCLEQ_ENTRY(type) \ 154 struct { \ 155 struct type *cqe_next; /* next element */ \ 156 struct type *cqe_prev; /* previous element */ \ 157 } 158 159 /* 160 * Circular queue functions. 161 */ 162 #define CIRCLEQ_INIT(head) { \ 163 (head)->cqh_first = (void *)(head); \ 164 (head)->cqh_last = (void *)(head); \ 165 } 166 167 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) { \ 168 (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 169 (elm)->field.cqe_prev = (listelm); \ 170 if ((listelm)->field.cqe_next == (void *)(head)) \ 171 (head)->cqh_last = (elm); \ 172 else \ 173 (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 174 (listelm)->field.cqe_next = (elm); \ 175 } 176 177 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) { \ 178 (elm)->field.cqe_next = (listelm); \ 179 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 180 if ((listelm)->field.cqe_prev == (void *)(head)) \ 181 (head)->cqh_first = (elm); \ 182 else \ 183 (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 184 (listelm)->field.cqe_prev = (elm); \ 185 } 186 187 #define CIRCLEQ_INSERT_HEAD(head, elm, field) { \ 188 (elm)->field.cqe_next = (head)->cqh_first; \ 189 (elm)->field.cqe_prev = (void *)(head); \ 190 if ((head)->cqh_last == (void *)(head)) \ 191 (head)->cqh_last = (elm); \ 192 else \ 193 (head)->cqh_first->field.cqe_prev = (elm); \ 194 (head)->cqh_first = (elm); \ 195 } 196 197 #define CIRCLEQ_INSERT_TAIL(head, elm, field) { \ 198 (elm)->field.cqe_next = (void *)(head); \ 199 (elm)->field.cqe_prev = (head)->cqh_last; \ 200 if ((head)->cqh_first == (void *)(head)) \ 201 (head)->cqh_first = (elm); \ 202 else \ 203 (head)->cqh_last->field.cqe_next = (elm); \ 204 (head)->cqh_last = (elm); \ 205 } 206 207 #define CIRCLEQ_REMOVE(head, elm, field) { \ 208 if ((elm)->field.cqe_next == (void *)(head)) \ 209 (head)->cqh_last = (elm)->field.cqe_prev; \ 210 else \ 211 (elm)->field.cqe_next->field.cqe_prev = \ 212 (elm)->field.cqe_prev; \ 213 if ((elm)->field.cqe_prev == (void *)(head)) \ 214 (head)->cqh_first = (elm)->field.cqe_next; \ 215 else \ 216 (elm)->field.cqe_prev->field.cqe_next = \ 217 (elm)->field.cqe_next; \ 218 } 219 #endif /* !_SYS_QUEUE_H_ */ 220