1 /* 2 * Copyright (c) 1991, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 4. Neither the name of the University nor the names of its contributors 14 * may be used to endorse or promote products derived from this software 15 * without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 * 29 * @(#)queue.h 8.3 (Berkeley) 12/13/93 30 */ 31 32 #ifndef _SYS_QUEUE_H 33 #define _SYS_QUEUE_H 1 34 35 /* 36 * This file defines three types of data structures: lists, tail queues, 37 * and circular queues. 38 * 39 * A list is headed by a single forward pointer (or an array of forward 40 * pointers for a hash table header). The elements are doubly linked 41 * so that an arbitrary element can be removed without a need to 42 * traverse the list. New elements can be added to the list after 43 * an existing element or at the head of the list. A list may only be 44 * traversed in the forward direction. 45 * 46 * A tail queue is headed by a pair of pointers, one to the head of the 47 * list and the other to the tail of the list. The elements are doubly 48 * linked so that an arbitrary element can be removed without a need to 49 * traverse the list. New elements can be added to the list after 50 * an existing element, at the head of the list, or at the end of the 51 * list. A tail queue may only be traversed in the forward direction. 52 * 53 * A circle queue is headed by a pair of pointers, one to the head of the 54 * list and the other to the tail of the list. The elements are doubly 55 * linked so that an arbitrary element can be removed without a need to 56 * traverse the list. New elements can be added to the list before or after 57 * an existing element, at the head of the list, or at the end of the list. 58 * A circle queue may be traversed in either direction, but has a more 59 * complex end of list detection. 60 * 61 * For details on the use of these macros, see the queue(3) manual page. 62 */ 63 64 /* 65 * List definitions. 66 */ 67 #define LIST_HEAD(name, type) \ 68 struct name { \ 69 struct type *lh_first; /* first element */ \ 70 } 71 72 #define LIST_ENTRY(type) \ 73 struct { \ 74 struct type *le_next; /* next element */ \ 75 struct type **le_prev; /* address of previous next element */ \ 76 } 77 78 /* 79 * List functions. 80 */ 81 #define LIST_INIT(head) { \ 82 (head)->lh_first = NULL; \ 83 } 84 85 #define LIST_INSERT_AFTER(listelm, elm, field) { \ 86 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ 87 (listelm)->field.le_next->field.le_prev = \ 88 &(elm)->field.le_next; \ 89 (listelm)->field.le_next = (elm); \ 90 (elm)->field.le_prev = &(listelm)->field.le_next; \ 91 } 92 93 #define LIST_INSERT_HEAD(head, elm, field) { \ 94 if (((elm)->field.le_next = (head)->lh_first) != NULL) \ 95 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ 96 (head)->lh_first = (elm); \ 97 (elm)->field.le_prev = &(head)->lh_first; \ 98 } 99 100 #define LIST_REMOVE(elm, field) { \ 101 if ((elm)->field.le_next != NULL) \ 102 (elm)->field.le_next->field.le_prev = \ 103 (elm)->field.le_prev; \ 104 *(elm)->field.le_prev = (elm)->field.le_next; \ 105 } 106 107 /* 108 * Tail queue definitions. 109 */ 110 #define TAILQ_HEAD(name, type) \ 111 struct name { \ 112 struct type *tqh_first; /* first element */ \ 113 struct type **tqh_last; /* addr of last next element */ \ 114 } 115 116 #define TAILQ_ENTRY(type) \ 117 struct { \ 118 struct type *tqe_next; /* next element */ \ 119 struct type **tqe_prev; /* address of previous next element */ \ 120 } 121 122 /* 123 * Tail queue functions. 124 */ 125 #define TAILQ_INIT(head) { \ 126 (head)->tqh_first = NULL; \ 127 (head)->tqh_last = &(head)->tqh_first; \ 128 } 129 130 #define TAILQ_INSERT_HEAD(head, elm, field) { \ 131 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 132 (elm)->field.tqe_next->field.tqe_prev = \ 133 &(elm)->field.tqe_next; \ 134 else \ 135 (head)->tqh_last = &(elm)->field.tqe_next; \ 136 (head)->tqh_first = (elm); \ 137 (elm)->field.tqe_prev = &(head)->tqh_first; \ 138 } 139 140 #define TAILQ_INSERT_TAIL(head, elm, field) { \ 141 (elm)->field.tqe_next = NULL; \ 142 (elm)->field.tqe_prev = (head)->tqh_last; \ 143 *(head)->tqh_last = (elm); \ 144 (head)->tqh_last = &(elm)->field.tqe_next; \ 145 } 146 147 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) { \ 148 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 149 (elm)->field.tqe_next->field.tqe_prev = \ 150 &(elm)->field.tqe_next; \ 151 else \ 152 (head)->tqh_last = &(elm)->field.tqe_next; \ 153 (listelm)->field.tqe_next = (elm); \ 154 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 155 } 156 157 #define TAILQ_REMOVE(head, elm, field) { \ 158 if (((elm)->field.tqe_next) != NULL) \ 159 (elm)->field.tqe_next->field.tqe_prev = \ 160 (elm)->field.tqe_prev; \ 161 else \ 162 (head)->tqh_last = (elm)->field.tqe_prev; \ 163 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 164 } 165 166 /* 167 * Circular queue definitions. 168 */ 169 #define CIRCLEQ_HEAD(name, type) \ 170 struct name { \ 171 struct type *cqh_first; /* first element */ \ 172 struct type *cqh_last; /* last element */ \ 173 } 174 175 #define CIRCLEQ_ENTRY(type) \ 176 struct { \ 177 struct type *cqe_next; /* next element */ \ 178 struct type *cqe_prev; /* previous element */ \ 179 } 180 181 /* 182 * Circular queue functions. 183 */ 184 #define CIRCLEQ_INIT(head) { \ 185 (head)->cqh_first = (void *)(head); \ 186 (head)->cqh_last = (void *)(head); \ 187 } 188 189 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) { \ 190 (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 191 (elm)->field.cqe_prev = (listelm); \ 192 if ((listelm)->field.cqe_next == (void *)(head)) \ 193 (head)->cqh_last = (elm); \ 194 else \ 195 (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 196 (listelm)->field.cqe_next = (elm); \ 197 } 198 199 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) { \ 200 (elm)->field.cqe_next = (listelm); \ 201 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 202 if ((listelm)->field.cqe_prev == (void *)(head)) \ 203 (head)->cqh_first = (elm); \ 204 else \ 205 (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 206 (listelm)->field.cqe_prev = (elm); \ 207 } 208 209 #define CIRCLEQ_INSERT_HEAD(head, elm, field) { \ 210 (elm)->field.cqe_next = (head)->cqh_first; \ 211 (elm)->field.cqe_prev = (void *)(head); \ 212 if ((head)->cqh_last == (void *)(head)) \ 213 (head)->cqh_last = (elm); \ 214 else \ 215 (head)->cqh_first->field.cqe_prev = (elm); \ 216 (head)->cqh_first = (elm); \ 217 } 218 219 #define CIRCLEQ_INSERT_TAIL(head, elm, field) { \ 220 (elm)->field.cqe_next = (void *)(head); \ 221 (elm)->field.cqe_prev = (head)->cqh_last; \ 222 if ((head)->cqh_first == (void *)(head)) \ 223 (head)->cqh_first = (elm); \ 224 else \ 225 (head)->cqh_last->field.cqe_next = (elm); \ 226 (head)->cqh_last = (elm); \ 227 } 228 229 #define CIRCLEQ_REMOVE(head, elm, field) { \ 230 if ((elm)->field.cqe_next == (void *)(head)) \ 231 (head)->cqh_last = (elm)->field.cqe_prev; \ 232 else \ 233 (elm)->field.cqe_next->field.cqe_prev = \ 234 (elm)->field.cqe_prev; \ 235 if ((elm)->field.cqe_prev == (void *)(head)) \ 236 (head)->cqh_first = (elm)->field.cqe_next; \ 237 else \ 238 (elm)->field.cqe_prev->field.cqe_next = \ 239 (elm)->field.cqe_next; \ 240 } 241 #endif /* sys/queue.h */ 242