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.5 (Berkeley) 08/20/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 before 21 * or after an existing element or at the head of the list. A list 22 * may only be 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 before or 28 * after an existing element, at the head of the list, or at the end of 29 * the 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_BEFORE(listelm, elm, field) { \ 72 (elm)->field.le_prev = (listelm)->field.le_prev; \ 73 (elm)->field.le_next = (listelm); \ 74 *(listelm)->field.le_prev = (elm); \ 75 (listelm)->field.le_prev = &(elm)->field.le_next; \ 76 } 77 78 #define LIST_INSERT_HEAD(head, elm, field) { \ 79 if (((elm)->field.le_next = (head)->lh_first) != NULL) \ 80 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ 81 (head)->lh_first = (elm); \ 82 (elm)->field.le_prev = &(head)->lh_first; \ 83 } 84 85 #define LIST_REMOVE(elm, field) { \ 86 if ((elm)->field.le_next != NULL) \ 87 (elm)->field.le_next->field.le_prev = \ 88 (elm)->field.le_prev; \ 89 *(elm)->field.le_prev = (elm)->field.le_next; \ 90 } 91 92 /* 93 * Tail queue definitions. 94 */ 95 #define TAILQ_HEAD(name, type) \ 96 struct name { \ 97 struct type *tqh_first; /* first element */ \ 98 struct type **tqh_last; /* addr of last next element */ \ 99 } 100 101 #define TAILQ_ENTRY(type) \ 102 struct { \ 103 struct type *tqe_next; /* next element */ \ 104 struct type **tqe_prev; /* address of previous next element */ \ 105 } 106 107 /* 108 * Tail queue functions. 109 */ 110 #define TAILQ_INIT(head) { \ 111 (head)->tqh_first = NULL; \ 112 (head)->tqh_last = &(head)->tqh_first; \ 113 } 114 115 #define TAILQ_INSERT_HEAD(head, elm, field) { \ 116 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 117 (head)->tqh_first->field.tqe_prev = \ 118 &(elm)->field.tqe_next; \ 119 else \ 120 (head)->tqh_last = &(elm)->field.tqe_next; \ 121 (head)->tqh_first = (elm); \ 122 (elm)->field.tqe_prev = &(head)->tqh_first; \ 123 } 124 125 #define TAILQ_INSERT_TAIL(head, elm, field) { \ 126 (elm)->field.tqe_next = NULL; \ 127 (elm)->field.tqe_prev = (head)->tqh_last; \ 128 *(head)->tqh_last = (elm); \ 129 (head)->tqh_last = &(elm)->field.tqe_next; \ 130 } 131 132 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) { \ 133 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 134 (elm)->field.tqe_next->field.tqe_prev = \ 135 &(elm)->field.tqe_next; \ 136 else \ 137 (head)->tqh_last = &(elm)->field.tqe_next; \ 138 (listelm)->field.tqe_next = (elm); \ 139 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 140 } 141 142 #define TAILQ_INSERT_BEFORE(listelm, elm, field) { \ 143 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 144 (elm)->field.tqe_next = (listelm); \ 145 *(listelm)->field.tqe_prev = (elm); \ 146 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ 147 } 148 149 #define TAILQ_REMOVE(head, elm, field) { \ 150 if (((elm)->field.tqe_next) != NULL) \ 151 (elm)->field.tqe_next->field.tqe_prev = \ 152 (elm)->field.tqe_prev; \ 153 else \ 154 (head)->tqh_last = (elm)->field.tqe_prev; \ 155 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 156 } 157 158 /* 159 * Circular queue definitions. 160 */ 161 #define CIRCLEQ_HEAD(name, type) \ 162 struct name { \ 163 struct type *cqh_first; /* first element */ \ 164 struct type *cqh_last; /* last element */ \ 165 } 166 167 #define CIRCLEQ_ENTRY(type) \ 168 struct { \ 169 struct type *cqe_next; /* next element */ \ 170 struct type *cqe_prev; /* previous element */ \ 171 } 172 173 /* 174 * Circular queue functions. 175 */ 176 #define CIRCLEQ_INIT(head) { \ 177 (head)->cqh_first = (void *)(head); \ 178 (head)->cqh_last = (void *)(head); \ 179 } 180 181 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) { \ 182 (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 183 (elm)->field.cqe_prev = (listelm); \ 184 if ((listelm)->field.cqe_next == (void *)(head)) \ 185 (head)->cqh_last = (elm); \ 186 else \ 187 (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 188 (listelm)->field.cqe_next = (elm); \ 189 } 190 191 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) { \ 192 (elm)->field.cqe_next = (listelm); \ 193 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 194 if ((listelm)->field.cqe_prev == (void *)(head)) \ 195 (head)->cqh_first = (elm); \ 196 else \ 197 (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 198 (listelm)->field.cqe_prev = (elm); \ 199 } 200 201 #define CIRCLEQ_INSERT_HEAD(head, elm, field) { \ 202 (elm)->field.cqe_next = (head)->cqh_first; \ 203 (elm)->field.cqe_prev = (void *)(head); \ 204 if ((head)->cqh_last == (void *)(head)) \ 205 (head)->cqh_last = (elm); \ 206 else \ 207 (head)->cqh_first->field.cqe_prev = (elm); \ 208 (head)->cqh_first = (elm); \ 209 } 210 211 #define CIRCLEQ_INSERT_TAIL(head, elm, field) { \ 212 (elm)->field.cqe_next = (void *)(head); \ 213 (elm)->field.cqe_prev = (head)->cqh_last; \ 214 if ((head)->cqh_first == (void *)(head)) \ 215 (head)->cqh_first = (elm); \ 216 else \ 217 (head)->cqh_last->field.cqe_next = (elm); \ 218 (head)->cqh_last = (elm); \ 219 } 220 221 #define CIRCLEQ_REMOVE(head, elm, field) { \ 222 if ((elm)->field.cqe_next == (void *)(head)) \ 223 (head)->cqh_last = (elm)->field.cqe_prev; \ 224 else \ 225 (elm)->field.cqe_next->field.cqe_prev = \ 226 (elm)->field.cqe_prev; \ 227 if ((elm)->field.cqe_prev == (void *)(head)) \ 228 (head)->cqh_first = (elm)->field.cqe_next; \ 229 else \ 230 (elm)->field.cqe_prev->field.cqe_next = \ 231 (elm)->field.cqe_next; \ 232 } 233 #endif /* !_SYS_QUEUE_H_ */ 234