^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) * Copyright (c) 1991, 1993
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * The Regents of the University of California. All rights reserved.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * Redistribution and use in source and binary forms, with or without
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * modification, are permitted provided that the following conditions
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * are met:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) * 1. Redistributions of source code must retain the above copyright
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) * notice, this list of conditions and the following disclaimer.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) * 2. Redistributions in binary form must reproduce the above copyright
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) * notice, this list of conditions and the following disclaimer in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) * documentation and/or other materials provided with the distribution.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) * SUCH DAMAGE.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) * @(#)queue.h 8.5 (Berkeley) 8/20/94
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) * $FreeBSD: src/sys/sys/queue.h,v 1.38 2000/05/26 02:06:56 jake Exp $
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) #ifndef _SYS_QUEUE_H_
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) #define _SYS_QUEUE_H_
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) * This file defines five types of data structures: singly-linked lists,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) * singly-linked tail queues, lists, tail queues, and circular queues.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) * A singly-linked list is headed by a single forward pointer. The elements
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) * are singly linked for minimum space and pointer manipulation overhead at
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) * the expense of O(n) removal for arbitrary elements. New elements can be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) * added to the list after an existing element or at the head of the list.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) * Elements being removed from the head of the list should use the explicit
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) * macro for this purpose for optimum efficiency. A singly-linked list may
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) * only be traversed in the forward direction. Singly-linked lists are ideal
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) * for applications with large datasets and few or no removals or for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) * implementing a LIFO queue.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) * A singly-linked tail queue is headed by a pair of pointers, one to the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) * head of the list and the other to the tail of the list. The elements are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) * singly linked for minimum space and pointer manipulation overhead at the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) * expense of O(n) removal for arbitrary elements. New elements can be added
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) * to the list after an existing element, at the head of the list, or at the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) * end of the list. Elements being removed from the head of the tail queue
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) * should use the explicit macro for this purpose for optimum efficiency.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) * A singly-linked tail queue may only be traversed in the forward direction.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) * Singly-linked tail queues are ideal for applications with large datasets
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) * and few or no removals or for implementing a FIFO queue.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) * A list is headed by a single forward pointer (or an array of forward
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) * pointers for a hash table header). The elements are doubly linked
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) * so that an arbitrary element can be removed without a need to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) * traverse the list. New elements can be added to the list before
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) * or after an existing element or at the head of the list. A list
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) * may only be traversed in the forward direction.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) * A tail queue is headed by a pair of pointers, one to the head of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) * list and the other to the tail of the list. The elements are doubly
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) * linked so that an arbitrary element can be removed without a need to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) * traverse the list. New elements can be added to the list before or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) * after an existing element, at the head of the list, or at the end of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) * the list. A tail queue may be traversed in either direction.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) * A circle queue is headed by a pair of pointers, one to the head of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) * list and the other to the tail of the list. The elements are doubly
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) * linked so that an arbitrary element can be removed without a need to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) * traverse the list. New elements can be added to the list before or after
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) * an existing element, at the head of the list, or at the end of the list.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) * A circle queue may be traversed in either direction, but has a more
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) * complex end of list detection.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) * For details on the use of these macros, see the queue(3) manual page.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) * SLIST LIST STAILQ TAILQ CIRCLEQ
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) * _HEAD + + + + +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) * _HEAD_INITIALIZER + + + + +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) * _ENTRY + + + + +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) * _INIT + + + + +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) * _EMPTY + + + + +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) * _FIRST + + + + +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) * _NEXT + + + + +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) * _PREV - - - + +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) * _LAST - - + + +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) * _FOREACH + + + + +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) * _FOREACH_REVERSE - - - + +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) * _INSERT_HEAD + + + + +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) * _INSERT_BEFORE - + - + +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) * _INSERT_AFTER + + + + +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) * _INSERT_TAIL - - + + +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) * _REMOVE_HEAD + - + - -
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) * _REMOVE + + + + +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) * Singly-linked List declarations.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) #define SLIST_HEAD(name, type) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) struct name { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) struct type *slh_first; /* first element */ \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) #define SLIST_HEAD_INITIALIZER(head) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) { NULL }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) #define SLIST_ENTRY(type) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) struct { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) struct type *sle_next; /* next element */ \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) * Singly-linked List functions.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) #define SLIST_EMPTY(head) ((head)->slh_first == NULL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) #define SLIST_FIRST(head) ((head)->slh_first)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) #define SLIST_FOREACH(var, head, field) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) for ((var) = SLIST_FIRST((head)); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) (var); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) (var) = SLIST_NEXT((var), field))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) #define SLIST_INIT(head) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) SLIST_FIRST((head)) = NULL; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) SLIST_NEXT((slistelm), field) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) #define SLIST_INSERT_HEAD(head, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) SLIST_FIRST((head)) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) #define SLIST_REMOVE(head, elm, type, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) if (SLIST_FIRST((head)) == (elm)) { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) SLIST_REMOVE_HEAD((head), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) } \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) else { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) struct type *curelm = SLIST_FIRST((head)); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) while (SLIST_NEXT(curelm, field) != (elm)) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) curelm = SLIST_NEXT(curelm, field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) SLIST_NEXT(curelm, field) = \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) SLIST_NEXT(SLIST_NEXT(curelm, field), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) } \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) #define SLIST_REMOVE_HEAD(head, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) * Singly-linked Tail queue declarations.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) #define STAILQ_HEAD(name, type) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) struct name { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) struct type *stqh_first;/* first element */ \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) struct type **stqh_last;/* addr of last next element */ \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) #define STAILQ_HEAD_INITIALIZER(head) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) { NULL, &(head).stqh_first }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) #define STAILQ_ENTRY(type) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) struct { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) struct type *stqe_next; /* next element */ \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) * Singly-linked Tail queue functions.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) #define STAILQ_FIRST(head) ((head)->stqh_first)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) #define STAILQ_FOREACH(var, head, field) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) for((var) = STAILQ_FIRST((head)); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) (var); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) (var) = STAILQ_NEXT((var), field))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) #define STAILQ_INIT(head) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) STAILQ_FIRST((head)) = NULL; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) (head)->stqh_last = &STAILQ_FIRST((head)); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) #define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) (head)->stqh_last = &STAILQ_NEXT((elm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) STAILQ_NEXT((tqelm), field) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) #define STAILQ_INSERT_HEAD(head, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) (head)->stqh_last = &STAILQ_NEXT((elm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) STAILQ_FIRST((head)) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) #define STAILQ_INSERT_TAIL(head, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) STAILQ_NEXT((elm), field) = NULL; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) STAILQ_LAST((head)) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) (head)->stqh_last = &STAILQ_NEXT((elm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) #define STAILQ_LAST(head) (*(head)->stqh_last)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) #define STAILQ_REMOVE(head, elm, type, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) if (STAILQ_FIRST((head)) == (elm)) { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) STAILQ_REMOVE_HEAD(head, field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) } \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) else { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) struct type *curelm = STAILQ_FIRST((head)); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) while (STAILQ_NEXT(curelm, field) != (elm)) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) curelm = STAILQ_NEXT(curelm, field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) if ((STAILQ_NEXT(curelm, field) = \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) (head)->stqh_last = &STAILQ_NEXT((curelm), field);\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) } \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) #define STAILQ_REMOVE_HEAD(head, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) if ((STAILQ_FIRST((head)) = \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) (head)->stqh_last = &STAILQ_FIRST((head)); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) #define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) (head)->stqh_last = &STAILQ_FIRST((head)); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) * List declarations.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) #define BSD_LIST_HEAD(name, type) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) struct name { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) struct type *lh_first; /* first element */ \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) #define LIST_HEAD_INITIALIZER(head) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) { NULL }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) #define LIST_ENTRY(type) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) struct { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) struct type *le_next; /* next element */ \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) struct type **le_prev; /* address of previous next element */ \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) * List functions.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) #define LIST_EMPTY(head) ((head)->lh_first == NULL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) #define LIST_FIRST(head) ((head)->lh_first)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) #define LIST_FOREACH(var, head, field) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) for ((var) = LIST_FIRST((head)); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) (var); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) (var) = LIST_NEXT((var), field))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) #define LIST_INIT(head) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) LIST_FIRST((head)) = NULL; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) #define LIST_INSERT_AFTER(listelm, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) LIST_NEXT((listelm), field)->field.le_prev = \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) &LIST_NEXT((elm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) LIST_NEXT((listelm), field) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) (elm)->field.le_prev = &LIST_NEXT((listelm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) (elm)->field.le_prev = (listelm)->field.le_prev; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) LIST_NEXT((elm), field) = (listelm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) *(listelm)->field.le_prev = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) (listelm)->field.le_prev = &LIST_NEXT((elm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) #define LIST_INSERT_HEAD(head, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) LIST_FIRST((head)) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) (elm)->field.le_prev = &LIST_FIRST((head)); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) #define LIST_NEXT(elm, field) ((elm)->field.le_next)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) #define LIST_REMOVE(elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) if (LIST_NEXT((elm), field) != NULL) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) LIST_NEXT((elm), field)->field.le_prev = \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) (elm)->field.le_prev; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) *(elm)->field.le_prev = LIST_NEXT((elm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) * Tail queue declarations.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) #define TAILQ_HEAD(name, type) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) struct name { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) struct type *tqh_first; /* first element */ \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) struct type **tqh_last; /* addr of last next element */ \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) #define TAILQ_HEAD_INITIALIZER(head) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) { NULL, &(head).tqh_first }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) #define TAILQ_ENTRY(type) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) struct { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) struct type *tqe_next; /* next element */ \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) struct type **tqe_prev; /* address of previous next element */ \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) * Tail queue functions.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) #define TAILQ_FIRST(head) ((head)->tqh_first)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) #define TAILQ_FOREACH(var, head, field) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) for ((var) = TAILQ_FIRST((head)); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) (var); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) (var) = TAILQ_NEXT((var), field))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) for ((var) = TAILQ_LAST((head), headname); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343) (var); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) (var) = TAILQ_PREV((var), headname, field))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) #define TAILQ_INIT(head) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) TAILQ_FIRST((head)) = NULL; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) (head)->tqh_last = &TAILQ_FIRST((head)); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) TAILQ_NEXT((elm), field)->field.tqe_prev = \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) &TAILQ_NEXT((elm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) else \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) (head)->tqh_last = &TAILQ_NEXT((elm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) TAILQ_NEXT((listelm), field) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) TAILQ_NEXT((elm), field) = (listelm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) *(listelm)->field.tqe_prev = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) #define TAILQ_INSERT_HEAD(head, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) TAILQ_FIRST((head))->field.tqe_prev = \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) &TAILQ_NEXT((elm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) else \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) (head)->tqh_last = &TAILQ_NEXT((elm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) TAILQ_FIRST((head)) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) #define TAILQ_INSERT_TAIL(head, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) TAILQ_NEXT((elm), field) = NULL; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) (elm)->field.tqe_prev = (head)->tqh_last; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) *(head)->tqh_last = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) (head)->tqh_last = &TAILQ_NEXT((elm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) #define TAILQ_LAST(head, headname) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) (*(((struct headname *)((head)->tqh_last))->tqh_last))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388) #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) #define TAILQ_PREV(elm, headname, field) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) #define TAILQ_REMOVE(head, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) if ((TAILQ_NEXT((elm), field)) != NULL) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) TAILQ_NEXT((elm), field)->field.tqe_prev = \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) (elm)->field.tqe_prev; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397) else \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) (head)->tqh_last = (elm)->field.tqe_prev; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399) *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) * Circular queue declarations.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) #define CIRCLEQ_HEAD(name, type) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) struct name { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) struct type *cqh_first; /* first element */ \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) struct type *cqh_last; /* last element */ \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) #define CIRCLEQ_HEAD_INITIALIZER(head) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412) { (void *)&(head), (void *)&(head) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) #define CIRCLEQ_ENTRY(type) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) struct { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) struct type *cqe_next; /* next element */ \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) struct type *cqe_prev; /* previous element */ \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421) * Circular queue functions.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) #define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425) #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427) #define CIRCLEQ_FOREACH(var, head, field) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) for ((var) = CIRCLEQ_FIRST((head)); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429) (var) != (void *)(head); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) (var) = CIRCLEQ_NEXT((var), field))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) for ((var) = CIRCLEQ_LAST((head)); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434) (var) != (void *)(head); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) (var) = CIRCLEQ_PREV((var), field))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437) #define CIRCLEQ_INIT(head) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438) CIRCLEQ_FIRST((head)) = (void *)(head); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439) CIRCLEQ_LAST((head)) = (void *)(head); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443) CIRCLEQ_NEXT((elm), field) = CIRCLEQ_NEXT((listelm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444) CIRCLEQ_PREV((elm), field) = (listelm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445) if (CIRCLEQ_NEXT((listelm), field) == (void *)(head)) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446) CIRCLEQ_LAST((head)) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447) else \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448) CIRCLEQ_PREV(CIRCLEQ_NEXT((listelm), field), field) = (elm);\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449) CIRCLEQ_NEXT((listelm), field) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453) CIRCLEQ_NEXT((elm), field) = (listelm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454) CIRCLEQ_PREV((elm), field) = CIRCLEQ_PREV((listelm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) if (CIRCLEQ_PREV((listelm), field) == (void *)(head)) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456) CIRCLEQ_FIRST((head)) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457) else \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458) CIRCLEQ_NEXT(CIRCLEQ_PREV((listelm), field), field) = (elm);\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) CIRCLEQ_PREV((listelm), field) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463) CIRCLEQ_NEXT((elm), field) = CIRCLEQ_FIRST((head)); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464) CIRCLEQ_PREV((elm), field) = (void *)(head); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465) if (CIRCLEQ_LAST((head)) == (void *)(head)) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466) CIRCLEQ_LAST((head)) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467) else \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468) CIRCLEQ_PREV(CIRCLEQ_FIRST((head)), field) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469) CIRCLEQ_FIRST((head)) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472) #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473) CIRCLEQ_NEXT((elm), field) = (void *)(head); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474) CIRCLEQ_PREV((elm), field) = CIRCLEQ_LAST((head)); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) if (CIRCLEQ_FIRST((head)) == (void *)(head)) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476) CIRCLEQ_FIRST((head)) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477) else \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478) CIRCLEQ_NEXT(CIRCLEQ_LAST((head)), field) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479) CIRCLEQ_LAST((head)) = (elm); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482) #define CIRCLEQ_LAST(head) ((head)->cqh_last)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484) #define CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486) #define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) #define CIRCLEQ_REMOVE(head, elm, field) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489) if (CIRCLEQ_NEXT((elm), field) == (void *)(head)) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490) CIRCLEQ_LAST((head)) = CIRCLEQ_PREV((elm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491) else \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492) CIRCLEQ_PREV(CIRCLEQ_NEXT((elm), field), field) = \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) CIRCLEQ_PREV((elm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) if (CIRCLEQ_PREV((elm), field) == (void *)(head)) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495) CIRCLEQ_FIRST((head)) = CIRCLEQ_NEXT((elm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) else \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497) CIRCLEQ_NEXT(CIRCLEQ_PREV((elm), field), field) = \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498) CIRCLEQ_NEXT((elm), field); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501) #endif /* !_SYS_QUEUE_H_ */
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags