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 * 3. 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 /***************************************************************************** 33 * File: hqueue.h 34 * 35 * This is a modfied version of the original Berkley code for 36 * manipulating a memory pool. This version however is not 37 * compatible with the original Berkley version. 38 * 39 * Author: George V.- 9/3/96 40 * 41 *****************************************************************************/ 42 43 /* $Id$ */ 44 45 #ifndef _HQUEUE_H_ 46 #define _HQUEUE_H_ 47 48 /* 49 * This file defines three types of data structures: lists, tail queues, 50 * and circular queues. 51 * 52 * A list is headed by a single forward pointer (or an array of forward 53 * pointers for a hash table header). The elements are doubly linked 54 * so that an arbitrary element can be removed without a need to 55 * traverse the list. New elements can be added to the list after 56 * an existing element or at the head of the list. A list may only be 57 * traversed in the forward direction. 58 * 59 * A tail queue is headed by a pair of pointers, one to the head of the 60 * list and the other to the tail of the list. The elements are doubly 61 * linked so that an arbitrary element can be removed without a need to 62 * traverse the list. New elements can be added to the list after 63 * an existing element, at the head of the list, or at the end of the 64 * list. A tail queue may only be traversed in the forward direction. 65 * 66 * A circle queue is headed by a pair of pointers, one to the head of the 67 * list and the other to the tail of the list. The elements are doubly 68 * linked so that an arbitrary element can be removed without a need to 69 * traverse the list. New elements can be added to the list before or after 70 * an existing element, at the head of the list, or at the end of the list. 71 * A circle queue may be traversed in either direction, but has a more 72 * complex end of list detection. 73 * 74 * For details on the use of these macros, see the queue(3) manual page. 75 * (BSD4.3 manual set - GeorgeV) 76 * 77 */ 78 79 /* 80 * List definitions. 81 */ 82 #define LIST_HEAD(name, type) \ 83 struct name { \ 84 struct type *lh_first; /* first element */ \ 85 } 86 87 #define LIST_ENTRY(type) \ 88 struct { \ 89 struct type *le_next; /* next element */ \ 90 struct type **le_prev; /* address of previous next element */ \ 91 } 92 93 /* 94 * List functions. 95 */ 96 #define LIST_INIT(head) { \ 97 (head)->lh_first = NULL; \ 98 } 99 100 #define LIST_INSERT_AFTER(listelm, elm, field) { \ 101 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ 102 (listelm)->field.le_next->field.le_prev = \ 103 &(elm)->field.le_next; \ 104 (listelm)->field.le_next = (elm); \ 105 (elm)->field.le_prev = &(listelm)->field.le_next; \ 106 } 107 108 #define LIST_INSERT_HEAD(head, elm, field) { \ 109 if (((elm)->field.le_next = (head)->lh_first) != NULL) \ 110 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ 111 (head)->lh_first = (elm); \ 112 (elm)->field.le_prev = &(head)->lh_first; \ 113 } 114 115 #define LIST_REMOVE(elm, field) { \ 116 if ((elm)->field.le_next != NULL) \ 117 (elm)->field.le_next->field.le_prev = \ 118 (elm)->field.le_prev; \ 119 *(elm)->field.le_prev = (elm)->field.le_next; \ 120 } 121 122 123 /* 124 * Tail queue definitions. 125 */ 126 #define TAILQ_HEAD(name, type) \ 127 struct name { \ 128 struct type *tqh_first; /* first element */ \ 129 struct type **tqh_last; /* addr of last next element */ \ 130 } 131 132 #define TAILQ_ENTRY(type) \ 133 struct { \ 134 struct type *tqe_next; /* next element */ \ 135 struct type **tqe_prev; /* address of previous next element */ \ 136 } 137 138 /* 139 * Tail queue functions. 140 */ 141 #define TAILQ_INIT(head) { \ 142 (head)->tqh_first = NULL; \ 143 (head)->tqh_last = &(head)->tqh_first; \ 144 } 145 146 #define TAILQ_INSERT_HEAD(head, elm, field) { \ 147 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 148 (elm)->field.tqe_next->field.tqe_prev = \ 149 &(elm)->field.tqe_next; \ 150 else \ 151 (head)->tqh_last = &(elm)->field.tqe_next; \ 152 (head)->tqh_first = (elm); \ 153 (elm)->field.tqe_prev = &(head)->tqh_first; \ 154 } 155 156 #define TAILQ_INSERT_TAIL(head, elm, field) { \ 157 (elm)->field.tqe_next = NULL; \ 158 (elm)->field.tqe_prev = (head)->tqh_last; \ 159 *(head)->tqh_last = (elm); \ 160 (head)->tqh_last = &(elm)->field.tqe_next; \ 161 } 162 163 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) { \ 164 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 165 (elm)->field.tqe_next->field.tqe_prev = \ 166 &(elm)->field.tqe_next; \ 167 else \ 168 (head)->tqh_last = &(elm)->field.tqe_next; \ 169 (listelm)->field.tqe_next = (elm); \ 170 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 171 } 172 173 #define TAILQ_REMOVE(head, elm, field) { \ 174 if (((elm)->field.tqe_next) != NULL) \ 175 (elm)->field.tqe_next->field.tqe_prev = \ 176 (elm)->field.tqe_prev; \ 177 else \ 178 (head)->tqh_last = (elm)->field.tqe_prev; \ 179 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 180 } 181 182 /* 183 * Circular queue definitions. 184 */ 185 #define CIRCLEQ_HEAD(name, type) \ 186 struct name { \ 187 struct type *cqh_first; /* first element */ \ 188 struct type *cqh_last; /* last element */ \ 189 } 190 191 #define CIRCLEQ_ENTRY(type) \ 192 struct { \ 193 struct type *cqe_next; /* next element */ \ 194 struct type *cqe_prev; /* previous element */ \ 195 } 196 197 /* 198 * Circular queue functions. 199 */ 200 #define CIRCLEQ_INIT(head) { \ 201 (head)->cqh_first = (void *)(head); \ 202 (head)->cqh_last = (void *)(head); \ 203 } 204 205 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) { \ 206 (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 207 (elm)->field.cqe_prev = (listelm); \ 208 if ((listelm)->field.cqe_next == (void *)(head)) \ 209 (head)->cqh_last = (elm); \ 210 else \ 211 (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 212 (listelm)->field.cqe_next = (elm); \ 213 } 214 215 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) { \ 216 (elm)->field.cqe_next = (listelm); \ 217 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 218 if ((listelm)->field.cqe_prev == (void *)(head)) \ 219 (head)->cqh_first = (elm); \ 220 else \ 221 (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 222 (listelm)->field.cqe_prev = (elm); \ 223 } 224 225 #define CIRCLEQ_INSERT_HEAD(head, elm, field) { \ 226 (elm)->field.cqe_next = (head)->cqh_first; \ 227 (elm)->field.cqe_prev = (void *)(head); \ 228 if ((head)->cqh_last == (void *)(head)) \ 229 (head)->cqh_last = (elm); \ 230 else \ 231 (head)->cqh_first->field.cqe_prev = (elm); \ 232 (head)->cqh_first = (elm); \ 233 } 234 235 #define CIRCLEQ_INSERT_TAIL(head, elm, field) { \ 236 (elm)->field.cqe_next = (void *)(head); \ 237 (elm)->field.cqe_prev = (head)->cqh_last; \ 238 if ((head)->cqh_first == (void *)(head)) \ 239 (head)->cqh_first = (elm); \ 240 else \ 241 (head)->cqh_last->field.cqe_next = (elm); \ 242 (head)->cqh_last = (elm); \ 243 } 244 245 #define CIRCLEQ_REMOVE(head, elm, field) { \ 246 if ((elm)->field.cqe_next == (void *)(head)) \ 247 (head)->cqh_last = (elm)->field.cqe_prev; \ 248 else \ 249 (elm)->field.cqe_next->field.cqe_prev = \ 250 (elm)->field.cqe_prev; \ 251 if ((elm)->field.cqe_prev == (void *)(head)) \ 252 (head)->cqh_first = (elm)->field.cqe_next; \ 253 else \ 254 (elm)->field.cqe_prev->field.cqe_next = \ 255 (elm)->field.cqe_next; \ 256 } 257 #endif /* !_HQUEUE_H_ */ 258