1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/dbm/include/queue.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,243 @@
1.4 +/*
1.5 + * Copyright (c) 1991, 1993
1.6 + * The Regents of the University of California. All rights reserved.
1.7 + *
1.8 + * Redistribution and use in source and binary forms, with or without
1.9 + * modification, are permitted provided that the following conditions
1.10 + * are met:
1.11 + * 1. Redistributions of source code must retain the above copyright
1.12 + * notice, this list of conditions and the following disclaimer.
1.13 + * 2. Redistributions in binary form must reproduce the above copyright
1.14 + * notice, this list of conditions and the following disclaimer in the
1.15 + * documentation and/or other materials provided with the distribution.
1.16 + * 3. ***REMOVED*** - see
1.17 + * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change
1.18 + * 4. Neither the name of the University nor the names of its contributors
1.19 + * may be used to endorse or promote products derived from this software
1.20 + * without specific prior written permission.
1.21 + *
1.22 + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
1.23 + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.24 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.25 + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
1.26 + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1.27 + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
1.28 + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
1.29 + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
1.30 + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
1.31 + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
1.32 + * SUCH DAMAGE.
1.33 + *
1.34 + * @(#)queue.h 8.3 (Berkeley) 12/13/93
1.35 + */
1.36 +
1.37 +#ifndef _QUEUE_H_
1.38 +#define _QUEUE_H_
1.39 +
1.40 +/*
1.41 + * This file defines three types of data structures: lists, tail queues,
1.42 + * and circular queues.
1.43 + *
1.44 + * A list is headed by a single forward pointer (or an array of forward
1.45 + * pointers for a hash table header). The elements are doubly linked
1.46 + * so that an arbitrary element can be removed without a need to
1.47 + * traverse the list. New elements can be added to the list after
1.48 + * an existing element or at the head of the list. A list may only be
1.49 + * traversed in the forward direction.
1.50 + *
1.51 + * A tail queue is headed by a pair of pointers, one to the head of the
1.52 + * list and the other to the tail of the list. The elements are doubly
1.53 + * linked so that an arbitrary element can be removed without a need to
1.54 + * traverse the list. New elements can be added to the list after
1.55 + * an existing element, at the head of the list, or at the end of the
1.56 + * list. A tail queue may only be traversed in the forward direction.
1.57 + *
1.58 + * A circle queue is headed by a pair of pointers, one to the head of the
1.59 + * list and the other to the tail of the list. The elements are doubly
1.60 + * linked so that an arbitrary element can be removed without a need to
1.61 + * traverse the list. New elements can be added to the list before or after
1.62 + * an existing element, at the head of the list, or at the end of the list.
1.63 + * A circle queue may be traversed in either direction, but has a more
1.64 + * complex end of list detection.
1.65 + *
1.66 + * For details on the use of these macros, see the queue(3) manual page.
1.67 + */
1.68 +
1.69 +/*
1.70 + * List definitions.
1.71 + */
1.72 +#define LIST_HEAD(name, type) \
1.73 +struct name { \
1.74 + struct type *lh_first; /* first element */ \
1.75 +}
1.76 +
1.77 +#define LIST_ENTRY(type) \
1.78 +struct { \
1.79 + struct type *le_next; /* next element */ \
1.80 + struct type **le_prev; /* address of previous next element */ \
1.81 +}
1.82 +
1.83 +/*
1.84 + * List functions.
1.85 + */
1.86 +#define LIST_INIT(head) { \
1.87 + (head)->lh_first = NULL; \
1.88 +}
1.89 +
1.90 +#define LIST_INSERT_AFTER(listelm, elm, field) { \
1.91 + if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
1.92 + (listelm)->field.le_next->field.le_prev = \
1.93 + &(elm)->field.le_next; \
1.94 + (listelm)->field.le_next = (elm); \
1.95 + (elm)->field.le_prev = &(listelm)->field.le_next; \
1.96 +}
1.97 +
1.98 +#define LIST_INSERT_HEAD(head, elm, field) { \
1.99 + if (((elm)->field.le_next = (head)->lh_first) != NULL) \
1.100 + (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
1.101 + (head)->lh_first = (elm); \
1.102 + (elm)->field.le_prev = &(head)->lh_first; \
1.103 +}
1.104 +
1.105 +#define LIST_REMOVE(elm, field) { \
1.106 + if ((elm)->field.le_next != NULL) \
1.107 + (elm)->field.le_next->field.le_prev = \
1.108 + (elm)->field.le_prev; \
1.109 + *(elm)->field.le_prev = (elm)->field.le_next; \
1.110 +}
1.111 +
1.112 +/*
1.113 + * Tail queue definitions.
1.114 + */
1.115 +#define TAILQ_HEAD(name, type) \
1.116 +struct name { \
1.117 + struct type *tqh_first; /* first element */ \
1.118 + struct type **tqh_last; /* addr of last next element */ \
1.119 +}
1.120 +
1.121 +#define TAILQ_ENTRY(type) \
1.122 +struct { \
1.123 + struct type *tqe_next; /* next element */ \
1.124 + struct type **tqe_prev; /* address of previous next element */ \
1.125 +}
1.126 +
1.127 +/*
1.128 + * Tail queue functions.
1.129 + */
1.130 +#define TAILQ_INIT(head) { \
1.131 + (head)->tqh_first = NULL; \
1.132 + (head)->tqh_last = &(head)->tqh_first; \
1.133 +}
1.134 +
1.135 +#define TAILQ_INSERT_HEAD(head, elm, field) { \
1.136 + if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
1.137 + (elm)->field.tqe_next->field.tqe_prev = \
1.138 + &(elm)->field.tqe_next; \
1.139 + else \
1.140 + (head)->tqh_last = &(elm)->field.tqe_next; \
1.141 + (head)->tqh_first = (elm); \
1.142 + (elm)->field.tqe_prev = &(head)->tqh_first; \
1.143 +}
1.144 +
1.145 +#define TAILQ_INSERT_TAIL(head, elm, field) { \
1.146 + (elm)->field.tqe_next = NULL; \
1.147 + (elm)->field.tqe_prev = (head)->tqh_last; \
1.148 + *(head)->tqh_last = (elm); \
1.149 + (head)->tqh_last = &(elm)->field.tqe_next; \
1.150 +}
1.151 +
1.152 +#define TAILQ_INSERT_AFTER(head, listelm, elm, field) { \
1.153 + if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
1.154 + (elm)->field.tqe_next->field.tqe_prev = \
1.155 + &(elm)->field.tqe_next; \
1.156 + else \
1.157 + (head)->tqh_last = &(elm)->field.tqe_next; \
1.158 + (listelm)->field.tqe_next = (elm); \
1.159 + (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
1.160 +}
1.161 +
1.162 +#define TAILQ_REMOVE(head, elm, field) { \
1.163 + if (((elm)->field.tqe_next) != NULL) \
1.164 + (elm)->field.tqe_next->field.tqe_prev = \
1.165 + (elm)->field.tqe_prev; \
1.166 + else \
1.167 + (head)->tqh_last = (elm)->field.tqe_prev; \
1.168 + *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
1.169 +}
1.170 +
1.171 +/*
1.172 + * Circular queue definitions.
1.173 + */
1.174 +#define CIRCLEQ_HEAD(name, type) \
1.175 +struct name { \
1.176 + struct type *cqh_first; /* first element */ \
1.177 + struct type *cqh_last; /* last element */ \
1.178 +}
1.179 +
1.180 +#define CIRCLEQ_ENTRY(type) \
1.181 +struct { \
1.182 + struct type *cqe_next; /* next element */ \
1.183 + struct type *cqe_prev; /* previous element */ \
1.184 +}
1.185 +
1.186 +/*
1.187 + * Circular queue functions.
1.188 + */
1.189 +#define CIRCLEQ_INIT(head) { \
1.190 + (head)->cqh_first = (void *)(head); \
1.191 + (head)->cqh_last = (void *)(head); \
1.192 +}
1.193 +
1.194 +#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) { \
1.195 + (elm)->field.cqe_next = (listelm)->field.cqe_next; \
1.196 + (elm)->field.cqe_prev = (listelm); \
1.197 + if ((listelm)->field.cqe_next == (void *)(head)) \
1.198 + (head)->cqh_last = (elm); \
1.199 + else \
1.200 + (listelm)->field.cqe_next->field.cqe_prev = (elm); \
1.201 + (listelm)->field.cqe_next = (elm); \
1.202 +}
1.203 +
1.204 +#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) { \
1.205 + (elm)->field.cqe_next = (listelm); \
1.206 + (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
1.207 + if ((listelm)->field.cqe_prev == (void *)(head)) \
1.208 + (head)->cqh_first = (elm); \
1.209 + else \
1.210 + (listelm)->field.cqe_prev->field.cqe_next = (elm); \
1.211 + (listelm)->field.cqe_prev = (elm); \
1.212 +}
1.213 +
1.214 +#define CIRCLEQ_INSERT_HEAD(head, elm, field) { \
1.215 + (elm)->field.cqe_next = (head)->cqh_first; \
1.216 + (elm)->field.cqe_prev = (void *)(head); \
1.217 + if ((head)->cqh_last == (void *)(head)) \
1.218 + (head)->cqh_last = (elm); \
1.219 + else \
1.220 + (head)->cqh_first->field.cqe_prev = (elm); \
1.221 + (head)->cqh_first = (elm); \
1.222 +}
1.223 +
1.224 +#define CIRCLEQ_INSERT_TAIL(head, elm, field) { \
1.225 + (elm)->field.cqe_next = (void *)(head); \
1.226 + (elm)->field.cqe_prev = (head)->cqh_last; \
1.227 + if ((head)->cqh_first == (void *)(head)) \
1.228 + (head)->cqh_first = (elm); \
1.229 + else \
1.230 + (head)->cqh_last->field.cqe_next = (elm); \
1.231 + (head)->cqh_last = (elm); \
1.232 +}
1.233 +
1.234 +#define CIRCLEQ_REMOVE(head, elm, field) { \
1.235 + if ((elm)->field.cqe_next == (void *)(head)) \
1.236 + (head)->cqh_last = (elm)->field.cqe_prev; \
1.237 + else \
1.238 + (elm)->field.cqe_next->field.cqe_prev = \
1.239 + (elm)->field.cqe_prev; \
1.240 + if ((elm)->field.cqe_prev == (void *)(head)) \
1.241 + (head)->cqh_first = (elm)->field.cqe_next; \
1.242 + else \
1.243 + (elm)->field.cqe_prev->field.cqe_next = \
1.244 + (elm)->field.cqe_next; \
1.245 +}
1.246 +#endif /* !_QUEUE_H_ */
