Tor  0.4.6.0-alpha-dev
tor_queue.h
1 /* $OpenBSD: queue.h,v 1.36 2012/04/11 13:29:14 naddy Exp $ */
2 /* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */
3 
4 /*
5  * Copyright (c) 1991, 1993
6  * The Regents of the University of California. All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  * 1. Redistributions of source code must retain the above copyright
12  * notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  * notice, this list of conditions and the following disclaimer in the
15  * documentation and/or other materials provided with the distribution.
16  * 3. Neither the name of the University nor the names of its contributors
17  * may be used to endorse or promote products derived from this software
18  * without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23  * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30  * SUCH DAMAGE.
31  *
32  * @(#)queue.h 8.5 (Berkeley) 8/20/94
33  */
34 
35 #ifndef TOR_QUEUE_H_
36 #define TOR_QUEUE_H_
37 
38 /*
39  * This file defines five types of data structures: singly-linked lists,
40  * lists, simple queues, tail queues, and circular queues.
41  *
42  *
43  * A singly-linked list is headed by a single forward pointer. The elements
44  * are singly linked for minimum space and pointer manipulation overhead at
45  * the expense of O(n) removal for arbitrary elements. New elements can be
46  * added to the list after an existing element or at the head of the list.
47  * Elements being removed from the head of the list should use the explicit
48  * macro for this purpose for optimum efficiency. A singly-linked list may
49  * only be traversed in the forward direction. Singly-linked lists are ideal
50  * for applications with large datasets and few or no removals or for
51  * implementing a LIFO queue.
52  *
53  * A list is headed by a single forward pointer (or an array of forward
54  * pointers for a hash table header). The elements are doubly linked
55  * 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
57  * or after an existing element or at the head of the list. A list
58  * may only be traversed in the forward direction.
59  *
60  * A simple queue is headed by a pair of pointers, one the head of the
61  * list and the other to the tail of the list. The elements are singly
62  * linked to save space, so elements can only be removed from the
63  * head of the list. New elements can be added to the list before or after
64  * an existing element, at the head of the list, or at the end of the
65  * list. A simple queue may only be traversed in the forward direction.
66  *
67  * A tail queue is headed by a pair of pointers, one to the head of the
68  * list and the other to the tail of the list. The elements are doubly
69  * linked so that an arbitrary element can be removed without a need to
70  * traverse the list. New elements can be added to the list before or
71  * after an existing element, at the head of the list, or at the end of
72  * the list. A tail queue may be traversed in either direction.
73  *
74  * A circle queue is headed by a pair of pointers, one to the head of the
75  * list and the other to the tail of the list. The elements are doubly
76  * linked so that an arbitrary element can be removed without a need to
77  * traverse the list. New elements can be added to the list before or after
78  * an existing element, at the head of the list, or at the end of the list.
79  * A circle queue may be traversed in either direction, but has a more
80  * complex end of list detection.
81  *
82  * For details on the use of these macros, see the queue(3) manual page.
83  */
84 
85 #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
86 #define TOR_Q_INVALIDATE_(a) (a) = ((void *)-1)
87 #else
88 #define TOR_Q_INVALIDATE_(a)
89 #endif
90 
91 /*
92  * Singly-linked List definitions.
93  */
94 #define TOR_SLIST_HEAD(name, type) \
95 struct name { \
96  struct type *slh_first; /* first element */ \
97 }
98 
99 #define TOR_SLIST_HEAD_INITIALIZER(head) \
100  { NULL }
101 
102 #define TOR_SLIST_ENTRY(type) \
103 struct { \
104  struct type *sle_next; /* next element */ \
105 }
106 
107 /*
108  * Singly-linked List access methods.
109  */
110 #define TOR_SLIST_FIRST(head) ((head)->slh_first)
111 #define TOR_SLIST_END(head) NULL
112 /* || 0 is for -Wparentheses-equality (-Wall?) appeasement under clang */
113 #define TOR_SLIST_EMPTY(head) ((SLIST_FIRST(head) == TOR_SLIST_END(head)) || 0)
114 #define TOR_SLIST_NEXT(elm, field) ((elm)->field.sle_next)
115 
116 #define TOR_SLIST_FOREACH(var, head, field) \
117  for((var) = TOR_SLIST_FIRST(head); \
118  (var) != TOR_SLIST_END(head); \
119  (var) = TOR_SLIST_NEXT(var, field))
120 
121 #define TOR_SLIST_FOREACH_SAFE(var, head, field, tvar) \
122  for ((var) = TOR_SLIST_FIRST(head); \
123  (var) && ((tvar) = TOR_SLIST_NEXT(var, field), 1); \
124  (var) = (tvar))
125 
126 /*
127  * Singly-linked List functions.
128  */
129 #define TOR_SLIST_INIT(head) { \
130  TOR_SLIST_FIRST(head) = TOR_SLIST_END(head); \
131 }
132 
133 #define TOR_SLIST_INSERT_AFTER(slistelm, elm, field) do { \
134  (elm)->field.sle_next = (slistelm)->field.sle_next; \
135  (slistelm)->field.sle_next = (elm); \
136 } while (0)
137 
138 #define TOR_SLIST_INSERT_HEAD(head, elm, field) do { \
139  (elm)->field.sle_next = (head)->slh_first; \
140  (head)->slh_first = (elm); \
141 } while (0)
142 
143 #define TOR_SLIST_REMOVE_AFTER(elm, field) do { \
144  (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \
145 } while (0)
146 
147 #define TOR_SLIST_REMOVE_HEAD(head, field) do { \
148  (head)->slh_first = (head)->slh_first->field.sle_next; \
149 } while (0)
150 
151 #define TOR_SLIST_REMOVE(head, elm, type, field) do { \
152  if ((head)->slh_first == (elm)) { \
153  TOR_SLIST_REMOVE_HEAD((head), field); \
154  } else { \
155  struct type *curelm = (head)->slh_first; \
156  \
157  while (curelm->field.sle_next != (elm)) \
158  curelm = curelm->field.sle_next; \
159  curelm->field.sle_next = \
160  curelm->field.sle_next->field.sle_next; \
161  TOR_Q_INVALIDATE_((elm)->field.sle_next); \
162  } \
163 } while (0)
164 
165 /*
166  * List definitions.
167  */
168 #define TOR_LIST_HEAD(name, type) \
169 struct name { \
170  struct type *lh_first; /* first element */ \
171 }
172 
173 #define TOR_LIST_HEAD_INITIALIZER(head) \
174  { NULL }
175 
176 #define TOR_LIST_ENTRY(type) \
177 struct { \
178  struct type *le_next; /* next element */ \
179  struct type **le_prev; /* address of previous next element */ \
180 }
181 
182 /*
183  * List access methods
184  */
185 #define TOR_LIST_FIRST(head) ((head)->lh_first)
186 #define TOR_LIST_END(head) NULL
187 /* || 0 is for -Wparentheses-equality (-Wall?) appeasement under clang */
188 #define TOR_LIST_EMPTY(head) \
189  ((TOR_LIST_FIRST(head) == TOR_LIST_END(head)) || 0)
190 #define TOR_LIST_NEXT(elm, field) ((elm)->field.le_next)
191 
192 #define TOR_LIST_FOREACH(var, head, field) \
193  for((var) = TOR_LIST_FIRST(head); \
194  (var)!= TOR_LIST_END(head); \
195  (var) = TOR_LIST_NEXT(var, field))
196 
197 #define TOR_LIST_FOREACH_SAFE(var, head, field, tvar) \
198  for ((var) = TOR_LIST_FIRST(head); \
199  (var) && ((tvar) = TOR_LIST_NEXT(var, field), 1); \
200  (var) = (tvar))
201 
202 /*
203  * List functions.
204  */
205 #define TOR_LIST_INIT(head) do { \
206  TOR_LIST_FIRST(head) = TOR_LIST_END(head); \
207 } while (0)
208 
209 #define TOR_LIST_INSERT_AFTER(listelm, elm, field) do { \
210  if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
211  (listelm)->field.le_next->field.le_prev = \
212  &(elm)->field.le_next; \
213  (listelm)->field.le_next = (elm); \
214  (elm)->field.le_prev = &(listelm)->field.le_next; \
215 } while (0)
216 
217 #define TOR_LIST_INSERT_BEFORE(listelm, elm, field) do { \
218  (elm)->field.le_prev = (listelm)->field.le_prev; \
219  (elm)->field.le_next = (listelm); \
220  *(listelm)->field.le_prev = (elm); \
221  (listelm)->field.le_prev = &(elm)->field.le_next; \
222 } while (0)
223 
224 #define TOR_LIST_INSERT_HEAD(head, elm, field) do { \
225  if (((elm)->field.le_next = (head)->lh_first) != NULL) \
226  (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
227  (head)->lh_first = (elm); \
228  (elm)->field.le_prev = &(head)->lh_first; \
229 } while (0)
230 
231 #define TOR_LIST_REMOVE(elm, field) do { \
232  if ((elm)->field.le_next != NULL) \
233  (elm)->field.le_next->field.le_prev = \
234  (elm)->field.le_prev; \
235  *(elm)->field.le_prev = (elm)->field.le_next; \
236  TOR_Q_INVALIDATE_((elm)->field.le_prev); \
237  TOR_Q_INVALIDATE_((elm)->field.le_next); \
238 } while (0)
239 
240 #define TOR_LIST_REPLACE(elm, elm2, field) do { \
241  if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \
242  (elm2)->field.le_next->field.le_prev = \
243  &(elm2)->field.le_next; \
244  (elm2)->field.le_prev = (elm)->field.le_prev; \
245  *(elm2)->field.le_prev = (elm2); \
246  TOR_Q_INVALIDATE_((elm)->field.le_prev); \
247  TOR_Q_INVALIDATE_((elm)->field.le_next); \
248 } while (0)
249 
250 /*
251  * Simple queue definitions.
252  */
253 #define TOR_SIMPLEQ_HEAD(name, type) \
254 struct name { \
255  struct type *sqh_first; /* first element */ \
256  struct type **sqh_last; /* addr of last next element */ \
257 }
258 
259 #define TOR_SIMPLEQ_HEAD_INITIALIZER(head) \
260  { NULL, &(head).sqh_first }
261 
262 #define TOR_SIMPLEQ_ENTRY(type) \
263 struct { \
264  struct type *sqe_next; /* next element */ \
265 }
266 
267 /*
268  * Simple queue access methods.
269  */
270 #define TOR_SIMPLEQ_FIRST(head) ((head)->sqh_first)
271 #define TOR_SIMPLEQ_END(head) NULL
272 /* || 0 is for -Wparentheses-equality (-Wall?) appeasement under clang */
273 #define TOR_SIMPLEQ_EMPTY(head) \
274  ((TOR_SIMPLEQ_FIRST(head) == TOR_SIMPLEQ_END(head)) || 0)
275 #define TOR_SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
276 
277 #define TOR_SIMPLEQ_FOREACH(var, head, field) \
278  for((var) = TOR_SIMPLEQ_FIRST(head); \
279  (var) != TOR_SIMPLEQ_END(head); \
280  (var) = TOR_SIMPLEQ_NEXT(var, field))
281 
282 #define TOR_SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \
283  for ((var) = TOR_SIMPLEQ_FIRST(head); \
284  (var) && ((tvar) = TOR_SIMPLEQ_NEXT(var, field), 1); \
285  (var) = (tvar))
286 
287 /*
288  * Simple queue functions.
289  */
290 #define TOR_SIMPLEQ_INIT(head) do { \
291  (head)->sqh_first = NULL; \
292  (head)->sqh_last = &(head)->sqh_first; \
293 } while (0)
294 
295 #define TOR_SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
296  if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
297  (head)->sqh_last = &(elm)->field.sqe_next; \
298  (head)->sqh_first = (elm); \
299 } while (0)
300 
301 #define TOR_SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
302  (elm)->field.sqe_next = NULL; \
303  *(head)->sqh_last = (elm); \
304  (head)->sqh_last = &(elm)->field.sqe_next; \
305 } while (0)
306 
307 #define TOR_SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
308  if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
309  (head)->sqh_last = &(elm)->field.sqe_next; \
310  (listelm)->field.sqe_next = (elm); \
311 } while (0)
312 
313 #define TOR_SIMPLEQ_REMOVE_HEAD(head, field) do { \
314  if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
315  (head)->sqh_last = &(head)->sqh_first; \
316 } while (0)
317 
318 #define TOR_SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
319  if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \
320  == NULL) \
321  (head)->sqh_last = &(elm)->field.sqe_next; \
322 } while (0)
323 
324 /*
325  * Tail queue definitions.
326  */
327 #define TOR_TAILQ_HEAD(name, type) \
328 struct name { \
329  struct type *tqh_first; /* first element */ \
330  struct type **tqh_last; /* addr of last next element */ \
331 }
332 
333 #define TOR_TAILQ_HEAD_INITIALIZER(head) \
334  { NULL, &(head).tqh_first }
335 
336 #define TOR_TAILQ_ENTRY(type) \
337 struct { \
338  struct type *tqe_next; /* next element */ \
339  struct type **tqe_prev; /* address of previous next element */ \
340 }
341 
342 /*
343  * tail queue access methods
344  */
345 #define TOR_TAILQ_FIRST(head) ((head)->tqh_first)
346 #define TOR_TAILQ_END(head) NULL
347 #define TOR_TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
348 #define TOR_TAILQ_LAST(head, headname) \
349  (*(((struct headname *)((head)->tqh_last))->tqh_last))
350 /* XXX */
351 #define TOR_TAILQ_PREV(elm, headname, field) \
352  (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
353 /* || 0 is for -Wparentheses-equality (-Wall?) appeasement under clang */
354 #define TOR_TAILQ_EMPTY(head) \
355  ((TOR_TAILQ_FIRST(head) == TOR_TAILQ_END(head)) || 0)
356 
357 #define TOR_TAILQ_FOREACH(var, head, field) \
358  for((var) = TOR_TAILQ_FIRST(head); \
359  (var) != TOR_TAILQ_END(head); \
360  (var) = TOR_TAILQ_NEXT(var, field))
361 
362 #define TOR_TAILQ_FOREACH_SAFE(var, head, field, tvar) \
363  for ((var) = TOR_TAILQ_FIRST(head); \
364  (var) != TOR_TAILQ_END(head) && \
365  ((tvar) = TOR_TAILQ_NEXT(var, field), 1); \
366  (var) = (tvar))
367 
368 
369 #define TOR_TAILQ_FOREACH_REVERSE(var, head, headname, field) \
370  for((var) = TOR_TAILQ_LAST(head, headname); \
371  (var) != TOR_TAILQ_END(head); \
372  (var) = TOR_TAILQ_PREV(var, headname, field))
373 
374 #define TOR_TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
375  for ((var) = TOR_TAILQ_LAST(head, headname); \
376  (var) != TOR_TAILQ_END(head) && \
377  ((tvar) = TOR_TAILQ_PREV(var, headname, field), 1); \
378  (var) = (tvar))
379 
380 /*
381  * Tail queue functions.
382  */
383 #define TOR_TAILQ_INIT(head) do { \
384  (head)->tqh_first = NULL; \
385  (head)->tqh_last = &(head)->tqh_first; \
386 } while (0)
387 
388 #define TOR_TAILQ_INSERT_HEAD(head, elm, field) do { \
389  if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
390  (head)->tqh_first->field.tqe_prev = \
391  &(elm)->field.tqe_next; \
392  else \
393  (head)->tqh_last = &(elm)->field.tqe_next; \
394  (head)->tqh_first = (elm); \
395  (elm)->field.tqe_prev = &(head)->tqh_first; \
396 } while (0)
397 
398 #define TOR_TAILQ_INSERT_TAIL(head, elm, field) do { \
399  (elm)->field.tqe_next = NULL; \
400  (elm)->field.tqe_prev = (head)->tqh_last; \
401  *(head)->tqh_last = (elm); \
402  (head)->tqh_last = &(elm)->field.tqe_next; \
403 } while (0)
404 
405 #define TOR_TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
406  if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
407  (elm)->field.tqe_next->field.tqe_prev = \
408  &(elm)->field.tqe_next; \
409  else \
410  (head)->tqh_last = &(elm)->field.tqe_next; \
411  (listelm)->field.tqe_next = (elm); \
412  (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
413 } while (0)
414 
415 #define TOR_TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
416  (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
417  (elm)->field.tqe_next = (listelm); \
418  *(listelm)->field.tqe_prev = (elm); \
419  (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
420 } while (0)
421 
422 #define TOR_TAILQ_REMOVE(head, elm, field) do { \
423  if (((elm)->field.tqe_next) != NULL) \
424  (elm)->field.tqe_next->field.tqe_prev = \
425  (elm)->field.tqe_prev; \
426  else \
427  (head)->tqh_last = (elm)->field.tqe_prev; \
428  *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
429  TOR_Q_INVALIDATE_((elm)->field.tqe_prev); \
430  TOR_Q_INVALIDATE_((elm)->field.tqe_next); \
431 } while (0)
432 
433 #define TOR_TAILQ_REPLACE(head, elm, elm2, field) do { \
434  if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \
435  (elm2)->field.tqe_next->field.tqe_prev = \
436  &(elm2)->field.tqe_next; \
437  else \
438  (head)->tqh_last = &(elm2)->field.tqe_next; \
439  (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
440  *(elm2)->field.tqe_prev = (elm2); \
441  TOR_Q_INVALIDATE_((elm)->field.tqe_prev); \
442  TOR_Q_INVALIDATE_((elm)->field.tqe_next); \
443 } while (0)
444 
445 /*
446  * Circular queue definitions.
447  */
448 #define TOR_CIRCLEQ_HEAD(name, type) \
449 struct name { \
450  struct type *cqh_first; /* first element */ \
451  struct type *cqh_last; /* last element */ \
452 }
453 
454 #define TOR_CIRCLEQ_HEAD_INITIALIZER(head) \
455  { TOR_CIRCLEQ_END(&head), TOR_CIRCLEQ_END(&head) }
456 
457 #define TOR_CIRCLEQ_ENTRY(type) \
458 struct { \
459  struct type *cqe_next; /* next element */ \
460  struct type *cqe_prev; /* previous element */ \
461 }
462 
463 /*
464  * Circular queue access methods
465  */
466 #define TOR_CIRCLEQ_FIRST(head) ((head)->cqh_first)
467 #define TOR_CIRCLEQ_LAST(head) ((head)->cqh_last)
468 #define TOR_CIRCLEQ_END(head) ((void *)(head))
469 #define TOR_CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
470 #define TOR_CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
471 /* || 0 is for -Wparentheses-equality (-Wall?) appeasement under clang */
472 #define TOR_CIRCLEQ_EMPTY(head) \
473  ((TOR_CIRCLEQ_FIRST(head) == TOR_CIRCLEQ_END(head)) || 0)
474 
475 #define TOR_CIRCLEQ_FOREACH(var, head, field) \
476  for((var) = TOR_CIRCLEQ_FIRST(head); \
477  (var) != TOR_CIRCLEQ_END(head); \
478  (var) = TOR_CIRCLEQ_NEXT(var, field))
479 
480 #define TOR_CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) \
481  for ((var) = TOR_CIRCLEQ_FIRST(head); \
482  (var) != TOR_CIRCLEQ_END(head) && \
483  ((tvar) = TOR_CIRCLEQ_NEXT(var, field), 1); \
484  (var) = (tvar))
485 
486 #define TOR_CIRCLEQ_FOREACH_REVERSE(var, head, field) \
487  for((var) = TOR_CIRCLEQ_LAST(head); \
488  (var) != TOR_CIRCLEQ_END(head); \
489  (var) = TOR_CIRCLEQ_PREV(var, field))
490 
491 #define TOR_CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
492  for ((var) = TOR_CIRCLEQ_LAST(head, headname); \
493  (var) != TOR_CIRCLEQ_END(head) && \
494  ((tvar) = TOR_CIRCLEQ_PREV(var, headname, field), 1); \
495  (var) = (tvar))
496 
497 /*
498  * Circular queue functions.
499  */
500 #define TOR_CIRCLEQ_INIT(head) do { \
501  (head)->cqh_first = TOR_CIRCLEQ_END(head); \
502  (head)->cqh_last = TOR_CIRCLEQ_END(head); \
503 } while (0)
504 
505 #define TOR_CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
506  (elm)->field.cqe_next = (listelm)->field.cqe_next; \
507  (elm)->field.cqe_prev = (listelm); \
508  if ((listelm)->field.cqe_next == TOR_CIRCLEQ_END(head)) \
509  (head)->cqh_last = (elm); \
510  else \
511  (listelm)->field.cqe_next->field.cqe_prev = (elm); \
512  (listelm)->field.cqe_next = (elm); \
513 } while (0)
514 
515 #define TOR_CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
516  (elm)->field.cqe_next = (listelm); \
517  (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
518  if ((listelm)->field.cqe_prev == TOR_CIRCLEQ_END(head)) \
519  (head)->cqh_first = (elm); \
520  else \
521  (listelm)->field.cqe_prev->field.cqe_next = (elm); \
522  (listelm)->field.cqe_prev = (elm); \
523 } while (0)
524 
525 #define TOR_CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
526  (elm)->field.cqe_next = (head)->cqh_first; \
527  (elm)->field.cqe_prev = TOR_CIRCLEQ_END(head); \
528  if ((head)->cqh_last == TOR_CIRCLEQ_END(head)) \
529  (head)->cqh_last = (elm); \
530  else \
531  (head)->cqh_first->field.cqe_prev = (elm); \
532  (head)->cqh_first = (elm); \
533 } while (0)
534 
535 #define TOR_CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
536  (elm)->field.cqe_next = TOR_CIRCLEQ_END(head); \
537  (elm)->field.cqe_prev = (head)->cqh_last; \
538  if ((head)->cqh_first == TOR_CIRCLEQ_END(head)) \
539  (head)->cqh_first = (elm); \
540  else \
541  (head)->cqh_last->field.cqe_next = (elm); \
542  (head)->cqh_last = (elm); \
543 } while (0)
544 
545 #define TOR_CIRCLEQ_REMOVE(head, elm, field) do { \
546  if ((elm)->field.cqe_next == TOR_CIRCLEQ_END(head)) \
547  (head)->cqh_last = (elm)->field.cqe_prev; \
548  else \
549  (elm)->field.cqe_next->field.cqe_prev = \
550  (elm)->field.cqe_prev; \
551  if ((elm)->field.cqe_prev == TOR_CIRCLEQ_END(head)) \
552  (head)->cqh_first = (elm)->field.cqe_next; \
553  else \
554  (elm)->field.cqe_prev->field.cqe_next = \
555  (elm)->field.cqe_next; \
556  TOR_Q_INVALIDATE_((elm)->field.cqe_prev); \
557  TOR_Q_INVALIDATE_((elm)->field.cqe_next); \
558 } while (0)
559 
560 #define TOR_CIRCLEQ_REPLACE(head, elm, elm2, field) do { \
561  if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \
562  TOR_CIRCLEQ_END(head)) \
563  (head).cqh_last = (elm2); \
564  else \
565  (elm2)->field.cqe_next->field.cqe_prev = (elm2); \
566  if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \
567  TOR_CIRCLEQ_END(head)) \
568  (head).cqh_first = (elm2); \
569  else \
570  (elm2)->field.cqe_prev->field.cqe_next = (elm2); \
571  TOR_Q_INVALIDATE_((elm)->field.cqe_prev); \
572  TOR_Q_INVALIDATE_((elm)->field.cqe_next); \
573 } while (0)
574 
575 #endif /* !_SYS_QUEUE_H_ */