]> git.sur5r.net Git - i3/i3/blob - include/queue.h
Detect base 16 in cmd criteria
[i3/i3] / include / queue.h
1 /*      $OpenBSD: queue.h,v 1.1 2007/10/26 03:14:08 niallo 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 #pragma once
36
37 /*
38  * This file defines five types of data structures: singly-linked lists,
39  * lists, simple queues, tail queues, and circular queues.
40  *
41  *
42  * A singly-linked list is headed by a single forward pointer. The elements
43  * are singly linked for minimum space and pointer manipulation overhead at
44  * the expense of O(n) removal for arbitrary elements. New elements can be
45  * added to the list after an existing element or at the head of the list.
46  * Elements being removed from the head of the list should use the explicit
47  * macro for this purpose for optimum efficiency. A singly-linked list may
48  * only be traversed in the forward direction.  Singly-linked lists are ideal
49  * for applications with large datasets and few or no removals or for
50  * implementing a LIFO queue.
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 before
56  * or after an existing element or at the head of the list. A list
57  * may only be traversed in the forward direction.
58  *
59  * A simple queue is headed by a pair of pointers, one the head of the
60  * list and the other to the tail of the list. The elements are singly
61  * linked to save space, so elements can only be removed from the
62  * head of the list. New elements can be added to the list before or after
63  * an existing element, at the head of the list, or at the end of the
64  * list. A simple queue may only be traversed in the forward direction.
65  *
66  * A tail 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
70  * after an existing element, at the head of the list, or at the end of
71  * the list. A tail queue may be traversed in either direction.
72  *
73  * A circle queue is headed by a pair of pointers, one to the head of the
74  * list and the other to the tail of the list. The elements are doubly
75  * linked so that an arbitrary element can be removed without a need to
76  * traverse the list. New elements can be added to the list before or after
77  * an existing element, at the head of the list, or at the end of the list.
78  * A circle queue may be traversed in either direction, but has a more
79  * complex end of list detection.
80  *
81  * For details on the use of these macros, see the queue(3) manual page.
82  */
83
84 #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
85 #define _Q_INVALIDATE(a) (a) = ((void *)-1)
86 #else
87 #define _Q_INVALIDATE(a)
88 #endif
89
90 /*
91  * Singly-linked List definitions.
92  */
93 #define SLIST_HEAD(name, type)                      \
94     struct name {                                   \
95         struct type *slh_first; /* first element */ \
96     }
97
98 #define SLIST_HEAD_INITIALIZER(head) \
99     { NULL }
100
101 #define SLIST_ENTRY(type)                         \
102     struct {                                      \
103         struct type *sle_next; /* next element */ \
104     }
105
106 /*
107  * Singly-linked List access methods.
108  */
109 #define SLIST_FIRST(head) ((head)->slh_first)
110 #define SLIST_END(head) NULL
111 #define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head))
112 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
113
114 #define SLIST_FOREACH(var, head, field) \
115     for ((var) = SLIST_FIRST(head);     \
116          (var) != SLIST_END(head);      \
117          (var) = SLIST_NEXT(var, field))
118
119 #define SLIST_FOREACH_PREVPTR(var, varp, head, field) \
120     for ((varp) = &SLIST_FIRST((head));               \
121          ((var) = *(varp)) != SLIST_END(head);        \
122          (varp) = &SLIST_NEXT((var), field))
123
124 /*
125  * Singly-linked List functions.
126  */
127 #define SLIST_INIT(head)                     \
128     {                                        \
129         SLIST_FIRST(head) = SLIST_END(head); \
130     }
131
132 #define SLIST_INSERT_AFTER(slistelm, elm, field)            \
133     do {                                                    \
134         (elm)->field.sle_next = (slistelm)->field.sle_next; \
135         (slistelm)->field.sle_next = (elm);                 \
136     } while (0)
137
138 #define SLIST_INSERT_HEAD(head, elm, field)        \
139     do {                                           \
140         (elm)->field.sle_next = (head)->slh_first; \
141         (head)->slh_first = (elm);                 \
142     } while (0)
143
144 #define SLIST_REMOVE_NEXT(head, elm, field)                            \
145     do {                                                               \
146         (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \
147     } while (0)
148
149 #define SLIST_REMOVE_HEAD(head, field)                         \
150     do {                                                       \
151         (head)->slh_first = (head)->slh_first->field.sle_next; \
152     } while (0)
153
154 #define SLIST_REMOVE(head, elm, type, field)                                 \
155     do {                                                                     \
156         if ((head)->slh_first == (elm)) {                                    \
157             SLIST_REMOVE_HEAD((head), field);                                \
158         } else {                                                             \
159             struct type *curelm = (head)->slh_first;                         \
160                                                                              \
161             while (curelm->field.sle_next != (elm))                          \
162                 curelm = curelm->field.sle_next;                             \
163             curelm->field.sle_next = curelm->field.sle_next->field.sle_next; \
164             _Q_INVALIDATE((elm)->field.sle_next);                            \
165         }                                                                    \
166     } while (0)
167
168 /*
169  * List definitions.
170  */
171 #define LIST_HEAD(name, type)                      \
172     struct name {                                  \
173         struct type *lh_first; /* first element */ \
174     }
175
176 #define LIST_HEAD_INITIALIZER(head) \
177     { NULL }
178
179 #define LIST_ENTRY(type)                                              \
180     struct {                                                          \
181         struct type *le_next;  /* next element */                     \
182         struct type **le_prev; /* address of previous next element */ \
183     }
184
185 /*
186  * List access methods
187  */
188 #define LIST_FIRST(head) ((head)->lh_first)
189 #define LIST_END(head) NULL
190 #define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))
191 #define LIST_NEXT(elm, field) ((elm)->field.le_next)
192
193 #define LIST_FOREACH(var, head, field) \
194     for ((var) = LIST_FIRST(head);     \
195          (var) != LIST_END(head);      \
196          (var) = LIST_NEXT(var, field))
197
198 /*
199  * List functions.
200  */
201 #define LIST_INIT(head)                    \
202     do {                                   \
203         LIST_FIRST(head) = LIST_END(head); \
204     } while (0)
205
206 #define LIST_INSERT_AFTER(listelm, elm, field)                               \
207     do {                                                                     \
208         if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)       \
209             (listelm)->field.le_next->field.le_prev = &(elm)->field.le_next; \
210         (listelm)->field.le_next = (elm);                                    \
211         (elm)->field.le_prev = &(listelm)->field.le_next;                    \
212     } while (0)
213
214 #define LIST_INSERT_BEFORE(listelm, elm, field)           \
215     do {                                                  \
216         (elm)->field.le_prev = (listelm)->field.le_prev;  \
217         (elm)->field.le_next = (listelm);                 \
218         *(listelm)->field.le_prev = (elm);                \
219         (listelm)->field.le_prev = &(elm)->field.le_next; \
220     } while (0)
221
222 #define LIST_INSERT_HEAD(head, elm, field)                           \
223     do {                                                             \
224         if (((elm)->field.le_next = (head)->lh_first) != NULL)       \
225             (head)->lh_first->field.le_prev = &(elm)->field.le_next; \
226         (head)->lh_first = (elm);                                    \
227         (elm)->field.le_prev = &(head)->lh_first;                    \
228     } while (0)
229
230 #define LIST_REMOVE(elm, field)                                         \
231     do {                                                                \
232         if ((elm)->field.le_next != NULL)                               \
233             (elm)->field.le_next->field.le_prev = (elm)->field.le_prev; \
234         *(elm)->field.le_prev = (elm)->field.le_next;                   \
235         _Q_INVALIDATE((elm)->field.le_prev);                            \
236         _Q_INVALIDATE((elm)->field.le_next);                            \
237     } while (0)
238
239 #define LIST_REPLACE(elm, elm2, field)                                     \
240     do {                                                                   \
241         if (((elm2)->field.le_next = (elm)->field.le_next) != NULL)        \
242             (elm2)->field.le_next->field.le_prev = &(elm2)->field.le_next; \
243         (elm2)->field.le_prev = (elm)->field.le_prev;                      \
244         *(elm2)->field.le_prev = (elm2);                                   \
245         _Q_INVALIDATE((elm)->field.le_prev);                               \
246         _Q_INVALIDATE((elm)->field.le_next);                               \
247     } while (0)
248
249 /*
250  * Simple queue definitions.
251  */
252 #define SIMPLEQ_HEAD(name, type)                                \
253     struct name {                                               \
254         struct type *sqh_first; /* first element */             \
255         struct type **sqh_last; /* addr of last next element */ \
256     }
257
258 #define SIMPLEQ_HEAD_INITIALIZER(head) \
259     { NULL, &(head).sqh_first }
260
261 #define SIMPLEQ_ENTRY(type)                       \
262     struct {                                      \
263         struct type *sqe_next; /* next element */ \
264     }
265
266 /*
267  * Simple queue access methods.
268  */
269 #define SIMPLEQ_FIRST(head) ((head)->sqh_first)
270 #define SIMPLEQ_END(head) NULL
271 #define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
272 #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
273
274 #define SIMPLEQ_FOREACH(var, head, field) \
275     for ((var) = SIMPLEQ_FIRST(head);     \
276          (var) != SIMPLEQ_END(head);      \
277          (var) = SIMPLEQ_NEXT(var, field))
278
279 /*
280  * Simple queue functions.
281  */
282 #define SIMPLEQ_INIT(head)                     \
283     do {                                       \
284         (head)->sqh_first = NULL;              \
285         (head)->sqh_last = &(head)->sqh_first; \
286     } while (0)
287
288 #define SIMPLEQ_INSERT_HEAD(head, elm, field)                    \
289     do {                                                         \
290         if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
291             (head)->sqh_last = &(elm)->field.sqe_next;           \
292         (head)->sqh_first = (elm);                               \
293     } while (0)
294
295 #define SIMPLEQ_INSERT_TAIL(head, elm, field)      \
296     do {                                           \
297         (elm)->field.sqe_next = NULL;              \
298         *(head)->sqh_last = (elm);                 \
299         (head)->sqh_last = &(elm)->field.sqe_next; \
300     } while (0)
301
302 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field)                  \
303     do {                                                                 \
304         if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL) \
305             (head)->sqh_last = &(elm)->field.sqe_next;                   \
306         (listelm)->field.sqe_next = (elm);                               \
307     } while (0)
308
309 #define SIMPLEQ_REMOVE_HEAD(head, field)                                     \
310     do {                                                                     \
311         if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
312             (head)->sqh_last = &(head)->sqh_first;                           \
313     } while (0)
314
315 /*
316  * Tail queue definitions.
317  */
318 #define TAILQ_HEAD(name, type)                                  \
319     struct name {                                               \
320         struct type *tqh_first; /* first element */             \
321         struct type **tqh_last; /* addr of last next element */ \
322     }
323
324 #define TAILQ_HEAD_INITIALIZER(head) \
325     { NULL, &(head).tqh_first }
326
327 #define TAILQ_ENTRY(type)                                              \
328     struct {                                                           \
329         struct type *tqe_next;  /* next element */                     \
330         struct type **tqe_prev; /* address of previous next element */ \
331     }
332
333 /*
334  * tail queue access methods
335  */
336 #define TAILQ_FIRST(head) ((head)->tqh_first)
337 #define TAILQ_END(head) NULL
338 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
339 #define TAILQ_LAST(head, headname) \
340     (*(((struct headname *)((head)->tqh_last))->tqh_last))
341 /* XXX */
342 #define TAILQ_PREV(elm, headname, field) \
343     (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
344 #define TAILQ_EMPTY(head) \
345     (TAILQ_FIRST(head) == TAILQ_END(head))
346
347 #define TAILQ_FOREACH(var, head, field) \
348     for ((var) = TAILQ_FIRST(head);     \
349          (var) != TAILQ_END(head);      \
350          (var) = TAILQ_NEXT(var, field))
351
352 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
353     for ((var) = TAILQ_LAST(head, headname);              \
354          (var) != TAILQ_END(head);                        \
355          (var) = TAILQ_PREV(var, headname, field))
356
357 /*
358  * Tail queue functions.
359  */
360 #define TAILQ_INIT(head)                       \
361     do {                                       \
362         (head)->tqh_first = NULL;              \
363         (head)->tqh_last = &(head)->tqh_first; \
364     } while (0)
365
366 #define TAILQ_INSERT_HEAD(head, elm, field)                             \
367     do {                                                                \
368         if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)        \
369             (head)->tqh_first->field.tqe_prev = &(elm)->field.tqe_next; \
370         else                                                            \
371             (head)->tqh_last = &(elm)->field.tqe_next;                  \
372         (head)->tqh_first = (elm);                                      \
373         (elm)->field.tqe_prev = &(head)->tqh_first;                     \
374     } while (0)
375
376 #define TAILQ_INSERT_TAIL(head, elm, field)        \
377     do {                                           \
378         (elm)->field.tqe_next = NULL;              \
379         (elm)->field.tqe_prev = (head)->tqh_last;  \
380         *(head)->tqh_last = (elm);                 \
381         (head)->tqh_last = &(elm)->field.tqe_next; \
382     } while (0)
383
384 #define TAILQ_INSERT_AFTER(head, listelm, elm, field)                       \
385     do {                                                                    \
386         if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)    \
387             (elm)->field.tqe_next->field.tqe_prev = &(elm)->field.tqe_next; \
388         else                                                                \
389             (head)->tqh_last = &(elm)->field.tqe_next;                      \
390         (listelm)->field.tqe_next = (elm);                                  \
391         (elm)->field.tqe_prev = &(listelm)->field.tqe_next;                 \
392     } while (0)
393
394 #define TAILQ_INSERT_BEFORE(listelm, elm, field)            \
395     do {                                                    \
396         (elm)->field.tqe_prev = (listelm)->field.tqe_prev;  \
397         (elm)->field.tqe_next = (listelm);                  \
398         *(listelm)->field.tqe_prev = (elm);                 \
399         (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
400     } while (0)
401
402 #define TAILQ_REMOVE(head, elm, field)                                     \
403     do {                                                                   \
404         if (((elm)->field.tqe_next) != NULL)                               \
405             (elm)->field.tqe_next->field.tqe_prev = (elm)->field.tqe_prev; \
406         else                                                               \
407             (head)->tqh_last = (elm)->field.tqe_prev;                      \
408         *(elm)->field.tqe_prev = (elm)->field.tqe_next;                    \
409         _Q_INVALIDATE((elm)->field.tqe_prev);                              \
410         _Q_INVALIDATE((elm)->field.tqe_next);                              \
411     } while (0)
412
413 #define TAILQ_REPLACE(head, elm, elm2, field)                                 \
414     do {                                                                      \
415         if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)         \
416             (elm2)->field.tqe_next->field.tqe_prev = &(elm2)->field.tqe_next; \
417         else                                                                  \
418             (head)->tqh_last = &(elm2)->field.tqe_next;                       \
419         (elm2)->field.tqe_prev = (elm)->field.tqe_prev;                       \
420         *(elm2)->field.tqe_prev = (elm2);                                     \
421         _Q_INVALIDATE((elm)->field.tqe_prev);                                 \
422         _Q_INVALIDATE((elm)->field.tqe_next);                                 \
423     } while (0)
424
425 /* Swaps two consecutive elements. 'second' *MUST* follow 'first' */
426 #define TAILQ_SWAP(first, second, head, field)                                     \
427     do {                                                                           \
428         *((first)->field.tqe_prev) = (second);                                     \
429         (second)->field.tqe_prev = (first)->field.tqe_prev;                        \
430         (first)->field.tqe_prev = &((second)->field.tqe_next);                     \
431         (first)->field.tqe_next = (second)->field.tqe_next;                        \
432         if ((second)->field.tqe_next)                                              \
433             (second)->field.tqe_next->field.tqe_prev = &((first)->field.tqe_next); \
434         (second)->field.tqe_next = first;                                          \
435         if ((head)->tqh_last == &((second)->field.tqe_next))                       \
436             (head)->tqh_last = &((first)->field.tqe_next);                         \
437     } while (0)
438
439 /*
440  * Circular queue definitions.
441  */
442 #define CIRCLEQ_HEAD(name, type)                    \
443     struct name {                                   \
444         struct type *cqh_first; /* first element */ \
445         struct type *cqh_last;  /* last element */  \
446     }
447
448 #define CIRCLEQ_HEAD_INITIALIZER(head) \
449     { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
450
451 #define CIRCLEQ_ENTRY(type)                           \
452     struct {                                          \
453         struct type *cqe_next; /* next element */     \
454         struct type *cqe_prev; /* previous element */ \
455     }
456
457 /*
458  * Circular queue access methods
459  */
460 #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
461 #define CIRCLEQ_LAST(head) ((head)->cqh_last)
462 #define CIRCLEQ_END(head) ((void *)(head))
463 #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
464 #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
465 #define CIRCLEQ_EMPTY(head) \
466     (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
467
468 #define CIRCLEQ_FOREACH(var, head, field) \
469     for ((var) = CIRCLEQ_FIRST(head);     \
470          (var) != CIRCLEQ_END(head);      \
471          (var) = CIRCLEQ_NEXT(var, field))
472
473 #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
474     for ((var) = CIRCLEQ_LAST(head);              \
475          (var) != CIRCLEQ_END(head);              \
476          (var) = CIRCLEQ_PREV(var, field))
477
478 /*
479  * Circular queue functions.
480  */
481 #define CIRCLEQ_INIT(head)                     \
482     do {                                       \
483         (head)->cqh_first = CIRCLEQ_END(head); \
484         (head)->cqh_last = CIRCLEQ_END(head);  \
485     } while (0)
486
487 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field)        \
488     do {                                                       \
489         (elm)->field.cqe_next = (listelm)->field.cqe_next;     \
490         (elm)->field.cqe_prev = (listelm);                     \
491         if ((listelm)->field.cqe_next == CIRCLEQ_END(head))    \
492             (head)->cqh_last = (elm);                          \
493         else                                                   \
494             (listelm)->field.cqe_next->field.cqe_prev = (elm); \
495         (listelm)->field.cqe_next = (elm);                     \
496     } while (0)
497
498 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field)       \
499     do {                                                       \
500         (elm)->field.cqe_next = (listelm);                     \
501         (elm)->field.cqe_prev = (listelm)->field.cqe_prev;     \
502         if ((listelm)->field.cqe_prev == CIRCLEQ_END(head))    \
503             (head)->cqh_first = (elm);                         \
504         else                                                   \
505             (listelm)->field.cqe_prev->field.cqe_next = (elm); \
506         (listelm)->field.cqe_prev = (elm);                     \
507     } while (0)
508
509 #define CIRCLEQ_INSERT_HEAD(head, elm, field)          \
510     do {                                               \
511         (elm)->field.cqe_next = (head)->cqh_first;     \
512         (elm)->field.cqe_prev = CIRCLEQ_END(head);     \
513         if ((head)->cqh_last == CIRCLEQ_END(head))     \
514             (head)->cqh_last = (elm);                  \
515         else                                           \
516             (head)->cqh_first->field.cqe_prev = (elm); \
517         (head)->cqh_first = (elm);                     \
518     } while (0)
519
520 #define CIRCLEQ_INSERT_TAIL(head, elm, field)         \
521     do {                                              \
522         (elm)->field.cqe_next = CIRCLEQ_END(head);    \
523         (elm)->field.cqe_prev = (head)->cqh_last;     \
524         if ((head)->cqh_first == CIRCLEQ_END(head))   \
525             (head)->cqh_first = (elm);                \
526         else                                          \
527             (head)->cqh_last->field.cqe_next = (elm); \
528         (head)->cqh_last = (elm);                     \
529     } while (0)
530
531 #define CIRCLEQ_REMOVE(head, elm, field)                                   \
532     do {                                                                   \
533         if ((elm)->field.cqe_next == CIRCLEQ_END(head))                    \
534             (head)->cqh_last = (elm)->field.cqe_prev;                      \
535         else                                                               \
536             (elm)->field.cqe_next->field.cqe_prev = (elm)->field.cqe_prev; \
537         if ((elm)->field.cqe_prev == CIRCLEQ_END(head))                    \
538             (head)->cqh_first = (elm)->field.cqe_next;                     \
539         else                                                               \
540             (elm)->field.cqe_prev->field.cqe_next = (elm)->field.cqe_next; \
541         _Q_INVALIDATE((elm)->field.cqe_prev);                              \
542         _Q_INVALIDATE((elm)->field.cqe_next);                              \
543     } while (0)
544
545 #define CIRCLEQ_REPLACE(head, elm, elm2, field)                                    \
546     do {                                                                           \
547         if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == CIRCLEQ_END(head)) \
548             (head)->cqh_last = (elm2);                                             \
549         else                                                                       \
550             (elm2)->field.cqe_next->field.cqe_prev = (elm2);                       \
551         if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == CIRCLEQ_END(head)) \
552             (head)->cqh_first = (elm2);                                            \
553         else                                                                       \
554             (elm2)->field.cqe_prev->field.cqe_next = (elm2);                       \
555         _Q_INVALIDATE((elm)->field.cqe_prev);                                      \
556         _Q_INVALIDATE((elm)->field.cqe_next);                                      \
557     } while (0)