File:
[ELWIX - Embedded LightWeight unIX -] /
libelwix /
inc /
elwix /
aqueue.h
Revision
1.2:
download - view:
text,
annotated -
select for diffs -
revision graph
Wed May 18 12:47:42 2016 UTC (8 years, 2 months ago) by
misho
Branches:
MAIN
CVS tags:
elwix6_1,
elwix5_9,
elwix5_8,
elwix5_7,
elwix5_6,
elwix5_5,
elwix5_4,
elwix5_3,
elwix5_2,
elwix5_12,
elwix5_11,
elwix5_10,
elwix5_1,
elwix5_0,
elwix4_9,
elwix4_8,
elwix4_7,
elwix4_6,
elwix4_5,
elwix4_4,
elwix4_3,
elwix4_26,
elwix4_25,
elwix4_24,
elwix4_23,
elwix4_22,
elwix4_21,
elwix4_20,
elwix4_2,
elwix4_19,
elwix4_18,
elwix4_17,
elwix4_16,
elwix4_15,
elwix4_14,
elwix4_13,
elwix4_12,
elwix4_11,
elwix4_10,
elwix4_1,
HEAD,
ELWIX6_0,
ELWIX5_9,
ELWIX5_8,
ELWIX5_7,
ELWIX5_6,
ELWIX5_5,
ELWIX5_4,
ELWIX5_3,
ELWIX5_2,
ELWIX5_11,
ELWIX5_10,
ELWIX5_1,
ELWIX5_0,
ELWIX4_9,
ELWIX4_8,
ELWIX4_7,
ELWIX4_6,
ELWIX4_5,
ELWIX4_4,
ELWIX4_3,
ELWIX4_26,
ELWIX4_25,
ELWIX4_24,
ELWIX4_23,
ELWIX4_22,
ELWIX4_21,
ELWIX4_20,
ELWIX4_2,
ELWIX4_19,
ELWIX4_18,
ELWIX4_17,
ELWIX4_16,
ELWIX4_15,
ELWIX4_14,
ELWIX4_13,
ELWIX4_12,
ELWIX4_11,
ELWIX4_10,
ELWIX4_1,
ELWIX4_0
version 4.0
1: /*************************************************************************
2: * (C) 2015 AITNET ltd - Sofia/Bulgaria - <misho@aitnet.org>
3: * by Michael Pounov <misho@elwix.org>
4: *
5: * $Author: misho $
6: * $Id: aqueue.h,v 1.2 2016/05/18 12:47:42 misho Exp $
7: *
8: **************************************************************************
9: The ELWIX and AITNET software is distributed under the following
10: terms:
11:
12: All of the documentation and software included in the ELWIX and AITNET
13: Releases is copyrighted by ELWIX - Sofia/Bulgaria <info@elwix.org>
14:
15: Copyright 2004 - 2015
16: by Michael Pounov <misho@elwix.org>. All rights reserved.
17:
18: Redistribution and use in source and binary forms, with or without
19: modification, are permitted provided that the following conditions
20: are met:
21: 1. Redistributions of source code must retain the above copyright
22: notice, this list of conditions and the following disclaimer.
23: 2. Redistributions in binary form must reproduce the above copyright
24: notice, this list of conditions and the following disclaimer in the
25: documentation and/or other materials provided with the distribution.
26: 3. All advertising materials mentioning features or use of this software
27: must display the following acknowledgement:
28: This product includes software developed by Michael Pounov <misho@elwix.org>
29: ELWIX - Embedded LightWeight unIX and its contributors.
30: 4. Neither the name of AITNET nor the names of its contributors
31: may be used to endorse or promote products derived from this software
32: without specific prior written permission.
33:
34: THIS SOFTWARE IS PROVIDED BY AITNET AND CONTRIBUTORS ``AS IS'' AND
35: ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
36: IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
37: ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
38: FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
39: DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
40: OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
41: HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
42: LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
43: OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
44: SUCH DAMAGE.
45: */
46: /*-
47: * Copyright (c) 1991, 1993
48: * The Regents of the University of California. All rights reserved.
49: *
50: * Redistribution and use in source and binary forms, with or without
51: * modification, are permitted provided that the following conditions
52: * are met:
53: * 1. Redistributions of source code must retain the above copyright
54: * notice, this list of conditions and the following disclaimer.
55: * 2. Redistributions in binary form must reproduce the above copyright
56: * notice, this list of conditions and the following disclaimer in the
57: * documentation and/or other materials provided with the distribution.
58: * 4. Neither the name of the University nor the names of its contributors
59: * may be used to endorse or promote products derived from this software
60: * without specific prior written permission.
61: *
62: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
63: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
64: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
65: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
66: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
67: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
68: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
69: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
70: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
71: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
72: * SUCH DAMAGE.
73: *
74: * @(#)queue.h 8.5 (Berkeley) 8/20/94
75: * $FreeBSD: head/sys/sys/queue.h 279242 2015-02-24 17:36:44Z hselasky $
76: */
77:
78: #ifndef _SYS_QUEUE_H_
79: #define _SYS_QUEUE_H_
80:
81: //#include <sys/cdefs.h>
82:
83: /*
84: * This file defines four types of data structures: singly-linked lists,
85: * singly-linked tail queues, lists and tail queues.
86: *
87: * A singly-linked list is headed by a single forward pointer. The elements
88: * are singly linked for minimum space and pointer manipulation overhead at
89: * the expense of O(n) removal for arbitrary elements. New elements can be
90: * added to the list after an existing element or at the head of the list.
91: * Elements being removed from the head of the list should use the explicit
92: * macro for this purpose for optimum efficiency. A singly-linked list may
93: * only be traversed in the forward direction. Singly-linked lists are ideal
94: * for applications with large datasets and few or no removals or for
95: * implementing a LIFO queue.
96: *
97: * A singly-linked tail queue is headed by a pair of pointers, one to the
98: * head of the list and the other to the tail of the list. The elements are
99: * singly linked for minimum space and pointer manipulation overhead at the
100: * expense of O(n) removal for arbitrary elements. New elements can be added
101: * to the list after an existing element, at the head of the list, or at the
102: * end of the list. Elements being removed from the head of the tail queue
103: * should use the explicit macro for this purpose for optimum efficiency.
104: * A singly-linked tail queue may only be traversed in the forward direction.
105: * Singly-linked tail queues are ideal for applications with large datasets
106: * and few or no removals or for implementing a FIFO queue.
107: *
108: * A list is headed by a single forward pointer (or an array of forward
109: * pointers for a hash table header). The elements are doubly linked
110: * so that an arbitrary element can be removed without a need to
111: * traverse the list. New elements can be added to the list before
112: * or after an existing element or at the head of the list. A list
113: * may be traversed in either direction.
114: *
115: * A tail queue is headed by a pair of pointers, one to the head of the
116: * list and the other to the tail of the list. The elements are doubly
117: * linked so that an arbitrary element can be removed without a need to
118: * traverse the list. New elements can be added to the list before or
119: * after an existing element, at the head of the list, or at the end of
120: * the list. A tail queue may be traversed in either direction.
121: *
122: * For details on the use of these macros, see the queue(3) manual page.
123: *
124: *
125: * SLIST LIST STAILQ TAILQ
126: * _HEAD + + + +
127: * _HEAD_INITIALIZER + + + +
128: * _ENTRY + + + +
129: * _INIT + + + +
130: * _EMPTY + + + +
131: * _FIRST + + + +
132: * _NEXT + + + +
133: * _PREV - + - +
134: * _LAST - - + +
135: * _FOREACH + + + +
136: * _FOREACH_FROM + + + +
137: * _FOREACH_SAFE + + + +
138: * _FOREACH_FROM_SAFE + + + +
139: * _FOREACH_REVERSE - - - +
140: * _FOREACH_REVERSE_FROM - - - +
141: * _FOREACH_REVERSE_SAFE - - - +
142: * _FOREACH_REVERSE_FROM_SAFE - - - +
143: * _INSERT_HEAD + + + +
144: * _INSERT_BEFORE - + - +
145: * _INSERT_AFTER + + + +
146: * _INSERT_TAIL - - + +
147: * _CONCAT - - + +
148: * _REMOVE_AFTER + - + -
149: * _REMOVE_HEAD + - + -
150: * _REMOVE + + + +
151: * _SWAP + + + +
152: *
153: */
154: #ifdef QUEUE_MACRO_DEBUG
155: /* Store the last 2 places the queue element or head was altered */
156: struct qm_trace {
157: unsigned long lastline;
158: unsigned long prevline;
159: const char *lastfile;
160: const char *prevfile;
161: };
162:
163: #define TRACEBUF struct qm_trace trace;
164: #define TRACEBUF_INITIALIZER { __LINE__, 0, __FILE__, NULL } ,
165: #define TRASHIT(x) do {(x) = (void *)-1;} while (0)
166: #define QMD_SAVELINK(name, link) void **name = (void *)&(link)
167:
168: #define QMD_TRACE_HEAD(head) do { \
169: (head)->trace.prevline = (head)->trace.lastline; \
170: (head)->trace.prevfile = (head)->trace.lastfile; \
171: (head)->trace.lastline = __LINE__; \
172: (head)->trace.lastfile = __FILE__; \
173: } while (0)
174:
175: #define QMD_TRACE_ELEM(elem) do { \
176: (elem)->trace.prevline = (elem)->trace.lastline; \
177: (elem)->trace.prevfile = (elem)->trace.lastfile; \
178: (elem)->trace.lastline = __LINE__; \
179: (elem)->trace.lastfile = __FILE__; \
180: } while (0)
181:
182: #else
183: #define QMD_TRACE_ELEM(elem)
184: #define QMD_TRACE_HEAD(head)
185: #define QMD_SAVELINK(name, link)
186: #define TRACEBUF
187: #define TRACEBUF_INITIALIZER
188: #define TRASHIT(x)
189: #endif /* QUEUE_MACRO_DEBUG */
190:
191: /*
192: * Singly-linked List declarations.
193: */
194: #define SLIST_HEAD(name, type) \
195: struct name { \
196: struct type *slh_first; /* first element */ \
197: }
198:
199: #define SLIST_HEAD_INITIALIZER(head) \
200: { NULL }
201:
202: #define SLIST_ENTRY(type) \
203: struct { \
204: struct type *sle_next; /* next element */ \
205: }
206:
207: /*
208: * Singly-linked List functions.
209: */
210: #define SLIST_EMPTY(head) ((head)->slh_first == NULL)
211:
212: #define SLIST_FIRST(head) ((head)->slh_first)
213:
214: #define SLIST_FOREACH(var, head, field) \
215: for ((var) = SLIST_FIRST((head)); \
216: (var); \
217: (var) = SLIST_NEXT((var), field))
218:
219: #define SLIST_FOREACH_FROM(var, head, field) \
220: for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \
221: (var); \
222: (var) = SLIST_NEXT((var), field))
223:
224: #define SLIST_FOREACH_SAFE(var, head, field, tvar) \
225: for ((var) = SLIST_FIRST((head)); \
226: (var) && ((tvar) = SLIST_NEXT((var), field), 1); \
227: (var) = (tvar))
228:
229: #define SLIST_FOREACH_FROM_SAFE(var, head, field, tvar) \
230: for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \
231: (var) && ((tvar) = SLIST_NEXT((var), field), 1); \
232: (var) = (tvar))
233:
234: #define SLIST_FOREACH_PREVPTR(var, varp, head, field) \
235: for ((varp) = &SLIST_FIRST((head)); \
236: ((var) = *(varp)) != NULL; \
237: (varp) = &SLIST_NEXT((var), field))
238:
239: #define SLIST_INIT(head) do { \
240: SLIST_FIRST((head)) = NULL; \
241: } while (0)
242:
243: #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
244: SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
245: SLIST_NEXT((slistelm), field) = (elm); \
246: } while (0)
247:
248: #define SLIST_INSERT_HEAD(head, elm, field) do { \
249: SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
250: SLIST_FIRST((head)) = (elm); \
251: } while (0)
252:
253: #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
254:
255: #define SLIST_REMOVE(head, elm, type, field) do { \
256: QMD_SAVELINK(oldnext, (elm)->field.sle_next); \
257: if (SLIST_FIRST((head)) == (elm)) { \
258: SLIST_REMOVE_HEAD((head), field); \
259: } \
260: else { \
261: struct type *curelm = SLIST_FIRST((head)); \
262: while (SLIST_NEXT(curelm, field) != (elm)) \
263: curelm = SLIST_NEXT(curelm, field); \
264: SLIST_REMOVE_AFTER(curelm, field); \
265: } \
266: TRASHIT(*oldnext); \
267: } while (0)
268:
269: #define SLIST_REMOVE_AFTER(elm, field) do { \
270: SLIST_NEXT(elm, field) = \
271: SLIST_NEXT(SLIST_NEXT(elm, field), field); \
272: } while (0)
273:
274: #define SLIST_REMOVE_HEAD(head, field) do { \
275: SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \
276: } while (0)
277:
278: #define SLIST_SWAP(head1, head2, type) do { \
279: struct type *swap_first = SLIST_FIRST(head1); \
280: SLIST_FIRST(head1) = SLIST_FIRST(head2); \
281: SLIST_FIRST(head2) = swap_first; \
282: } while (0)
283:
284: /*
285: * Singly-linked Tail queue declarations.
286: */
287: #define STAILQ_HEAD(name, type) \
288: struct name { \
289: struct type *stqh_first;/* first element */ \
290: struct type **stqh_last;/* addr of last next element */ \
291: }
292:
293: #define STAILQ_HEAD_INITIALIZER(head) \
294: { NULL, &(head).stqh_first }
295:
296: #define STAILQ_ENTRY(type) \
297: struct { \
298: struct type *stqe_next; /* next element */ \
299: }
300:
301: /*
302: * Singly-linked Tail queue functions.
303: */
304: #define STAILQ_CONCAT(head1, head2) do { \
305: if (!STAILQ_EMPTY((head2))) { \
306: *(head1)->stqh_last = (head2)->stqh_first; \
307: (head1)->stqh_last = (head2)->stqh_last; \
308: STAILQ_INIT((head2)); \
309: } \
310: } while (0)
311:
312: #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
313:
314: #define STAILQ_FIRST(head) ((head)->stqh_first)
315:
316: #define STAILQ_FOREACH(var, head, field) \
317: for((var) = STAILQ_FIRST((head)); \
318: (var); \
319: (var) = STAILQ_NEXT((var), field))
320:
321: #define STAILQ_FOREACH_FROM(var, head, field) \
322: for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \
323: (var); \
324: (var) = STAILQ_NEXT((var), field))
325:
326: #define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
327: for ((var) = STAILQ_FIRST((head)); \
328: (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
329: (var) = (tvar))
330:
331: #define STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \
332: for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \
333: (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
334: (var) = (tvar))
335:
336: #define STAILQ_INIT(head) do { \
337: STAILQ_FIRST((head)) = NULL; \
338: (head)->stqh_last = &STAILQ_FIRST((head)); \
339: } while (0)
340:
341: #define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
342: if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
343: (head)->stqh_last = &STAILQ_NEXT((elm), field); \
344: STAILQ_NEXT((tqelm), field) = (elm); \
345: } while (0)
346:
347: #define STAILQ_INSERT_HEAD(head, elm, field) do { \
348: if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
349: (head)->stqh_last = &STAILQ_NEXT((elm), field); \
350: STAILQ_FIRST((head)) = (elm); \
351: } while (0)
352:
353: #define STAILQ_INSERT_TAIL(head, elm, field) do { \
354: STAILQ_NEXT((elm), field) = NULL; \
355: *(head)->stqh_last = (elm); \
356: (head)->stqh_last = &STAILQ_NEXT((elm), field); \
357: } while (0)
358:
359: #define STAILQ_LAST(head, type, field) \
360: (STAILQ_EMPTY((head)) ? NULL : \
361: __containerof((head)->stqh_last, struct type, field.stqe_next))
362:
363: #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
364:
365: #define STAILQ_REMOVE(head, elm, type, field) do { \
366: QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \
367: if (STAILQ_FIRST((head)) == (elm)) { \
368: STAILQ_REMOVE_HEAD((head), field); \
369: } \
370: else { \
371: struct type *curelm = STAILQ_FIRST((head)); \
372: while (STAILQ_NEXT(curelm, field) != (elm)) \
373: curelm = STAILQ_NEXT(curelm, field); \
374: STAILQ_REMOVE_AFTER(head, curelm, field); \
375: } \
376: TRASHIT(*oldnext); \
377: } while (0)
378:
379: #define STAILQ_REMOVE_AFTER(head, elm, field) do { \
380: if ((STAILQ_NEXT(elm, field) = \
381: STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \
382: (head)->stqh_last = &STAILQ_NEXT((elm), field); \
383: } while (0)
384:
385: #define STAILQ_REMOVE_HEAD(head, field) do { \
386: if ((STAILQ_FIRST((head)) = \
387: STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \
388: (head)->stqh_last = &STAILQ_FIRST((head)); \
389: } while (0)
390:
391: #define STAILQ_SWAP(head1, head2, type) do { \
392: struct type *swap_first = STAILQ_FIRST(head1); \
393: struct type **swap_last = (head1)->stqh_last; \
394: STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \
395: (head1)->stqh_last = (head2)->stqh_last; \
396: STAILQ_FIRST(head2) = swap_first; \
397: (head2)->stqh_last = swap_last; \
398: if (STAILQ_EMPTY(head1)) \
399: (head1)->stqh_last = &STAILQ_FIRST(head1); \
400: if (STAILQ_EMPTY(head2)) \
401: (head2)->stqh_last = &STAILQ_FIRST(head2); \
402: } while (0)
403:
404:
405: /*
406: * List declarations.
407: */
408: #define LIST_HEAD(name, type) \
409: struct name { \
410: struct type *lh_first; /* first element */ \
411: }
412:
413: #define LIST_HEAD_INITIALIZER(head) \
414: { NULL }
415:
416: #define LIST_ENTRY(type) \
417: struct { \
418: struct type *le_next; /* next element */ \
419: struct type **le_prev; /* address of previous next element */ \
420: }
421:
422: /*
423: * List functions.
424: */
425:
426: #if (defined(_KERNEL) && defined(INVARIANTS))
427: #define QMD_LIST_CHECK_HEAD(head, field) do { \
428: if (LIST_FIRST((head)) != NULL && \
429: LIST_FIRST((head))->field.le_prev != \
430: &LIST_FIRST((head))) \
431: panic("Bad list head %p first->prev != head", (head)); \
432: } while (0)
433:
434: #define QMD_LIST_CHECK_NEXT(elm, field) do { \
435: if (LIST_NEXT((elm), field) != NULL && \
436: LIST_NEXT((elm), field)->field.le_prev != \
437: &((elm)->field.le_next)) \
438: panic("Bad link elm %p next->prev != elm", (elm)); \
439: } while (0)
440:
441: #define QMD_LIST_CHECK_PREV(elm, field) do { \
442: if (*(elm)->field.le_prev != (elm)) \
443: panic("Bad link elm %p prev->next != elm", (elm)); \
444: } while (0)
445: #else
446: #define QMD_LIST_CHECK_HEAD(head, field)
447: #define QMD_LIST_CHECK_NEXT(elm, field)
448: #define QMD_LIST_CHECK_PREV(elm, field)
449: #endif /* (_KERNEL && INVARIANTS) */
450:
451: #define LIST_EMPTY(head) ((head)->lh_first == NULL)
452:
453: #define LIST_FIRST(head) ((head)->lh_first)
454:
455: #define LIST_FOREACH(var, head, field) \
456: for ((var) = LIST_FIRST((head)); \
457: (var); \
458: (var) = LIST_NEXT((var), field))
459:
460: #define LIST_FOREACH_FROM(var, head, field) \
461: for ((var) = ((var) ? (var) : LIST_FIRST((head))); \
462: (var); \
463: (var) = LIST_NEXT((var), field))
464:
465: #define LIST_FOREACH_SAFE(var, head, field, tvar) \
466: for ((var) = LIST_FIRST((head)); \
467: (var) && ((tvar) = LIST_NEXT((var), field), 1); \
468: (var) = (tvar))
469:
470: #define LIST_FOREACH_FROM_SAFE(var, head, field, tvar) \
471: for ((var) = ((var) ? (var) : LIST_FIRST((head))); \
472: (var) && ((tvar) = LIST_NEXT((var), field), 1); \
473: (var) = (tvar))
474:
475: #define LIST_INIT(head) do { \
476: LIST_FIRST((head)) = NULL; \
477: } while (0)
478:
479: #define LIST_INSERT_AFTER(listelm, elm, field) do { \
480: QMD_LIST_CHECK_NEXT(listelm, field); \
481: if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
482: LIST_NEXT((listelm), field)->field.le_prev = \
483: &LIST_NEXT((elm), field); \
484: LIST_NEXT((listelm), field) = (elm); \
485: (elm)->field.le_prev = &LIST_NEXT((listelm), field); \
486: } while (0)
487:
488: #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
489: QMD_LIST_CHECK_PREV(listelm, field); \
490: (elm)->field.le_prev = (listelm)->field.le_prev; \
491: LIST_NEXT((elm), field) = (listelm); \
492: *(listelm)->field.le_prev = (elm); \
493: (listelm)->field.le_prev = &LIST_NEXT((elm), field); \
494: } while (0)
495:
496: #define LIST_INSERT_HEAD(head, elm, field) do { \
497: QMD_LIST_CHECK_HEAD((head), field); \
498: if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
499: LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
500: LIST_FIRST((head)) = (elm); \
501: (elm)->field.le_prev = &LIST_FIRST((head)); \
502: } while (0)
503:
504: #define LIST_NEXT(elm, field) ((elm)->field.le_next)
505:
506: #define LIST_PREV(elm, head, type, field) \
507: ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \
508: __containerof((elm)->field.le_prev, struct type, field.le_next))
509:
510: #define LIST_REMOVE(elm, field) do { \
511: QMD_SAVELINK(oldnext, (elm)->field.le_next); \
512: QMD_SAVELINK(oldprev, (elm)->field.le_prev); \
513: QMD_LIST_CHECK_NEXT(elm, field); \
514: QMD_LIST_CHECK_PREV(elm, field); \
515: if (LIST_NEXT((elm), field) != NULL) \
516: LIST_NEXT((elm), field)->field.le_prev = \
517: (elm)->field.le_prev; \
518: *(elm)->field.le_prev = LIST_NEXT((elm), field); \
519: TRASHIT(*oldnext); \
520: TRASHIT(*oldprev); \
521: } while (0)
522:
523: #define LIST_SWAP(head1, head2, type, field) do { \
524: struct type *swap_tmp = LIST_FIRST((head1)); \
525: LIST_FIRST((head1)) = LIST_FIRST((head2)); \
526: LIST_FIRST((head2)) = swap_tmp; \
527: if ((swap_tmp = LIST_FIRST((head1))) != NULL) \
528: swap_tmp->field.le_prev = &LIST_FIRST((head1)); \
529: if ((swap_tmp = LIST_FIRST((head2))) != NULL) \
530: swap_tmp->field.le_prev = &LIST_FIRST((head2)); \
531: } while (0)
532:
533: /*
534: * Tail queue declarations.
535: */
536: #define TAILQ_HEAD(name, type) \
537: struct name { \
538: struct type *tqh_first; /* first element */ \
539: struct type **tqh_last; /* addr of last next element */ \
540: TRACEBUF \
541: }
542:
543: #define TAILQ_HEAD_INITIALIZER(head) \
544: { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER }
545:
546: #define TAILQ_ENTRY(type) \
547: struct { \
548: struct type *tqe_next; /* next element */ \
549: struct type **tqe_prev; /* address of previous next element */ \
550: TRACEBUF \
551: }
552:
553: /*
554: * Tail queue functions.
555: */
556: #if (defined(_KERNEL) && defined(INVARIANTS))
557: #define QMD_TAILQ_CHECK_HEAD(head, field) do { \
558: if (!TAILQ_EMPTY(head) && \
559: TAILQ_FIRST((head))->field.tqe_prev != \
560: &TAILQ_FIRST((head))) \
561: panic("Bad tailq head %p first->prev != head", (head)); \
562: } while (0)
563:
564: #define QMD_TAILQ_CHECK_TAIL(head, field) do { \
565: if (*(head)->tqh_last != NULL) \
566: panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \
567: } while (0)
568:
569: #define QMD_TAILQ_CHECK_NEXT(elm, field) do { \
570: if (TAILQ_NEXT((elm), field) != NULL && \
571: TAILQ_NEXT((elm), field)->field.tqe_prev != \
572: &((elm)->field.tqe_next)) \
573: panic("Bad link elm %p next->prev != elm", (elm)); \
574: } while (0)
575:
576: #define QMD_TAILQ_CHECK_PREV(elm, field) do { \
577: if (*(elm)->field.tqe_prev != (elm)) \
578: panic("Bad link elm %p prev->next != elm", (elm)); \
579: } while (0)
580: #else
581: #define QMD_TAILQ_CHECK_HEAD(head, field)
582: #define QMD_TAILQ_CHECK_TAIL(head, headname)
583: #define QMD_TAILQ_CHECK_NEXT(elm, field)
584: #define QMD_TAILQ_CHECK_PREV(elm, field)
585: #endif /* (_KERNEL && INVARIANTS) */
586:
587: #define TAILQ_CONCAT(head1, head2, field) do { \
588: if (!TAILQ_EMPTY(head2)) { \
589: *(head1)->tqh_last = (head2)->tqh_first; \
590: (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
591: (head1)->tqh_last = (head2)->tqh_last; \
592: TAILQ_INIT((head2)); \
593: QMD_TRACE_HEAD(head1); \
594: QMD_TRACE_HEAD(head2); \
595: } \
596: } while (0)
597:
598: #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
599:
600: #define TAILQ_FIRST(head) ((head)->tqh_first)
601:
602: #define TAILQ_FOREACH(var, head, field) \
603: for ((var) = TAILQ_FIRST((head)); \
604: (var); \
605: (var) = TAILQ_NEXT((var), field))
606:
607: #define TAILQ_FOREACH_FROM(var, head, field) \
608: for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \
609: (var); \
610: (var) = TAILQ_NEXT((var), field))
611:
612: #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
613: for ((var) = TAILQ_FIRST((head)); \
614: (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
615: (var) = (tvar))
616:
617: #define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \
618: for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \
619: (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
620: (var) = (tvar))
621:
622: #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
623: for ((var) = TAILQ_LAST((head), headname); \
624: (var); \
625: (var) = TAILQ_PREV((var), headname, field))
626:
627: #define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \
628: for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \
629: (var); \
630: (var) = TAILQ_PREV((var), headname, field))
631:
632: #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
633: for ((var) = TAILQ_LAST((head), headname); \
634: (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
635: (var) = (tvar))
636:
637: #define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \
638: for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \
639: (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
640: (var) = (tvar))
641:
642: #define TAILQ_INIT(head) do { \
643: TAILQ_FIRST((head)) = NULL; \
644: (head)->tqh_last = &TAILQ_FIRST((head)); \
645: QMD_TRACE_HEAD(head); \
646: } while (0)
647:
648: #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
649: QMD_TAILQ_CHECK_NEXT(listelm, field); \
650: if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
651: TAILQ_NEXT((elm), field)->field.tqe_prev = \
652: &TAILQ_NEXT((elm), field); \
653: else { \
654: (head)->tqh_last = &TAILQ_NEXT((elm), field); \
655: QMD_TRACE_HEAD(head); \
656: } \
657: TAILQ_NEXT((listelm), field) = (elm); \
658: (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
659: QMD_TRACE_ELEM(&(elm)->field); \
660: QMD_TRACE_ELEM(&(listelm)->field); \
661: } while (0)
662:
663: #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
664: QMD_TAILQ_CHECK_PREV(listelm, field); \
665: (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
666: TAILQ_NEXT((elm), field) = (listelm); \
667: *(listelm)->field.tqe_prev = (elm); \
668: (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
669: QMD_TRACE_ELEM(&(elm)->field); \
670: QMD_TRACE_ELEM(&(listelm)->field); \
671: } while (0)
672:
673: #define TAILQ_INSERT_HEAD(head, elm, field) do { \
674: QMD_TAILQ_CHECK_HEAD(head, field); \
675: if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
676: TAILQ_FIRST((head))->field.tqe_prev = \
677: &TAILQ_NEXT((elm), field); \
678: else \
679: (head)->tqh_last = &TAILQ_NEXT((elm), field); \
680: TAILQ_FIRST((head)) = (elm); \
681: (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
682: QMD_TRACE_HEAD(head); \
683: QMD_TRACE_ELEM(&(elm)->field); \
684: } while (0)
685:
686: #define TAILQ_INSERT_TAIL(head, elm, field) do { \
687: QMD_TAILQ_CHECK_TAIL(head, field); \
688: TAILQ_NEXT((elm), field) = NULL; \
689: (elm)->field.tqe_prev = (head)->tqh_last; \
690: *(head)->tqh_last = (elm); \
691: (head)->tqh_last = &TAILQ_NEXT((elm), field); \
692: QMD_TRACE_HEAD(head); \
693: QMD_TRACE_ELEM(&(elm)->field); \
694: } while (0)
695:
696: #define TAILQ_LAST(head, headname) \
697: (*(((struct headname *)((head)->tqh_last))->tqh_last))
698:
699: #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
700:
701: #define TAILQ_PREV(elm, headname, field) \
702: (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
703:
704: #define TAILQ_REMOVE(head, elm, field) do { \
705: QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \
706: QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \
707: QMD_TAILQ_CHECK_NEXT(elm, field); \
708: QMD_TAILQ_CHECK_PREV(elm, field); \
709: if ((TAILQ_NEXT((elm), field)) != NULL) \
710: TAILQ_NEXT((elm), field)->field.tqe_prev = \
711: (elm)->field.tqe_prev; \
712: else { \
713: (head)->tqh_last = (elm)->field.tqe_prev; \
714: QMD_TRACE_HEAD(head); \
715: } \
716: *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
717: TRASHIT(*oldnext); \
718: TRASHIT(*oldprev); \
719: QMD_TRACE_ELEM(&(elm)->field); \
720: } while (0)
721:
722: #define TAILQ_SWAP(head1, head2, type, field) do { \
723: struct type *swap_first = (head1)->tqh_first; \
724: struct type **swap_last = (head1)->tqh_last; \
725: (head1)->tqh_first = (head2)->tqh_first; \
726: (head1)->tqh_last = (head2)->tqh_last; \
727: (head2)->tqh_first = swap_first; \
728: (head2)->tqh_last = swap_last; \
729: if ((swap_first = (head1)->tqh_first) != NULL) \
730: swap_first->field.tqe_prev = &(head1)->tqh_first; \
731: else \
732: (head1)->tqh_last = &(head1)->tqh_first; \
733: if ((swap_first = (head2)->tqh_first) != NULL) \
734: swap_first->field.tqe_prev = &(head2)->tqh_first; \
735: else \
736: (head2)->tqh_last = &(head2)->tqh_first; \
737: } while (0)
738:
739: #endif /* !_SYS_QUEUE_H_ */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>