1 /* 2 * Copyright (c) 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 * 7 * @(#)queue.h 8.2 (Berkeley) 11/23/93 8 */ 9 10 #ifndef _QUEUE_H_ 11 #define _QUEUE_H_ 12 13 /* 14 * List definitions. 15 */ 16 #define LIST_HEAD(name, type) \ 17 struct name { \ 18 struct type *lh_first; /* first element */ \ 19 } 20 21 #define LIST_ENTRY(type) \ 22 struct { \ 23 struct type *le_next; /* next element */ \ 24 struct type **le_prev; /* address of previous next element */ \ 25 } 26 27 /* 28 * List functions. 29 */ 30 #define LIST_INIT(head) { \ 31 (head)->lh_first = NULL; \ 32 } 33 34 #define LIST_INSERT_AFTER(listelm, elm, field) { \ 35 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ 36 (listelm)->field.le_next->field.le_prev = \ 37 &(elm)->field.le_next; \ 38 (listelm)->field.le_next = (elm); \ 39 (elm)->field.le_prev = &(listelm)->field.le_next; \ 40 } 41 42 #define LIST_INSERT_HEAD(head, elm, field) { \ 43 if (((elm)->field.le_next = (head)->lh_first) != NULL) \ 44 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ 45 (head)->lh_first = (elm); \ 46 (elm)->field.le_prev = &(head)->lh_first; \ 47 } 48 49 #define LIST_REMOVE(elm, field) { \ 50 if ((elm)->field.le_next != NULL) \ 51 (elm)->field.le_next->field.le_prev = \ 52 (elm)->field.le_prev; \ 53 *(elm)->field.le_prev = (elm)->field.le_next; \ 54 } 55 56 /* 57 * Tail queue definitions. 58 */ 59 #define TAILQ_HEAD(name, type) \ 60 struct name { \ 61 struct type *tqh_first; /* first element */ \ 62 struct type **tqh_last; /* addr of last next element */ \ 63 } 64 65 #define TAILQ_ENTRY(type) \ 66 struct { \ 67 struct type *tqe_next; /* next element */ \ 68 struct type **tqe_prev; /* address of previous next element */ \ 69 } 70 71 /* 72 * Tail queue functions. 73 */ 74 #define TAILQ_INIT(head) { \ 75 (head)->tqh_first = NULL; \ 76 (head)->tqh_last = &(head)->tqh_first; \ 77 } 78 79 #define TAILQ_INSERT_HEAD(head, elm, field) { \ 80 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 81 (elm)->field.tqe_next->field.tqe_prev = \ 82 &(elm)->field.tqe_next; \ 83 else \ 84 (head)->tqh_last = &(elm)->field.tqe_next; \ 85 (head)->tqh_first = (elm); \ 86 (elm)->field.tqe_prev = &(head)->tqh_first; \ 87 } 88 89 #define TAILQ_INSERT_TAIL(head, elm, field) { \ 90 (elm)->field.tqe_next = NULL; \ 91 (elm)->field.tqe_prev = (head)->tqh_last; \ 92 *(head)->tqh_last = (elm); \ 93 (head)->tqh_last = &(elm)->field.tqe_next; \ 94 } 95 96 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) { \ 97 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 98 (elm)->field.tqe_next->field.tqe_prev = \ 99 &(elm)->field.tqe_next; \ 100 else \ 101 (head)->tqh_last = &(elm)->field.tqe_next; \ 102 (listelm)->field.tqe_next = (elm); \ 103 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 104 } 105 106 #define TAILQ_REMOVE(head, elm, field) { \ 107 if (((elm)->field.tqe_next) != NULL) \ 108 (elm)->field.tqe_next->field.tqe_prev = \ 109 (elm)->field.tqe_prev; \ 110 else \ 111 (head)->tqh_last = (elm)->field.tqe_prev; \ 112 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 113 } 114 115 /* 116 * Circular queue definitions. 117 */ 118 #define CIRCLEQ_HEAD(name, type) \ 119 struct name { \ 120 struct type *cqh_first; /* first element */ \ 121 struct type *cqh_last; /* last element */ \ 122 } 123 124 #define CIRCLEQ_ENTRY(type) \ 125 struct { \ 126 struct type *cqe_next; /* next element */ \ 127 struct type *cqe_prev; /* previous element */ \ 128 } 129 130 /* 131 * Circular queue functions. 132 */ 133 #define CIRCLEQ_INIT(head) { \ 134 (head)->cqh_first = (void *)(head); \ 135 (head)->cqh_last = (void *)(head); \ 136 } 137 138 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) { \ 139 (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 140 (elm)->field.cqe_prev = (listelm); \ 141 if ((listelm)->field.cqe_next == (void *)(head)) \ 142 (head)->cqh_last = (elm); \ 143 else \ 144 (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 145 (listelm)->field.cqe_next = (elm); \ 146 } 147 148 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) { \ 149 (elm)->field.cqe_next = (listelm); \ 150 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 151 if ((listelm)->field.cqe_prev == (void *)(head)) \ 152 (head)->cqh_first = (elm); \ 153 else \ 154 (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 155 (listelm)->field.cqe_prev = (elm); \ 156 } 157 158 #define CIRCLEQ_INSERT_HEAD(head, elm, field) { \ 159 (elm)->field.cqe_next = (head)->cqh_first; \ 160 (elm)->field.cqe_prev = (void *)(head); \ 161 if ((head)->cqh_last == (void *)(head)) \ 162 (head)->cqh_last = (elm); \ 163 else \ 164 (head)->cqh_first->field.cqe_prev = (elm); \ 165 (head)->cqh_first = (elm); \ 166 } 167 168 #define CIRCLEQ_INSERT_TAIL(head, elm, field) { \ 169 (elm)->field.cqe_next = (void *)(head); \ 170 (elm)->field.cqe_prev = (head)->cqh_last; \ 171 if ((head)->cqh_first == (void *)(head)) \ 172 (head)->cqh_first = (elm); \ 173 else \ 174 (head)->cqh_last->field.cqe_next = (elm); \ 175 (head)->cqh_last = (elm); \ 176 } 177 178 #define CIRCLEQ_REMOVE(head, elm, field) { \ 179 if ((elm)->field.cqe_next == (void *)(head)) \ 180 (head)->cqh_last = (elm)->field.cqe_prev; \ 181 else \ 182 (elm)->field.cqe_next->field.cqe_prev = \ 183 (elm)->field.cqe_prev; \ 184 if ((elm)->field.cqe_prev == (void *)(head)) \ 185 (head)->cqh_first = (elm)->field.cqe_next; \ 186 else \ 187 (elm)->field.cqe_prev->field.cqe_next = \ 188 (elm)->field.cqe_next; \ 189 } 190 #endif /* !_QUEUE_H_ */ 191