1 /* 2 * SPDX-FileCopyrightText: 2015-2022 The Apache Software Foundation (ASF) 3 * 4 * SPDX-License-Identifier: Apache-2.0 5 * 6 * SPDX-FileContributor: 2019-2022 Espressif Systems (Shanghai) CO LTD 7 */ 8 /* 9 * Licensed to the Apache Software Foundation (ASF) under one 10 * or more contributor license agreements. See the NOTICE file 11 * distributed with this work for additional information 12 * regarding copyright ownership. The ASF licenses this file 13 * to you under the Apache License, Version 2.0 (the 14 * "License"); you may not use this file except in compliance 15 * with the License. You may obtain a copy of the License at 16 * 17 * http://www.apache.org/licenses/LICENSE-2.0 18 * 19 * Unless required by applicable law or agreed to in writing, 20 * software distributed under the License is distributed on an 21 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 22 * KIND, either express or implied. See the License for the 23 * specific language governing permissions and limitations 24 * under the License. 25 */ 26 27 #ifndef _QUEUE_H_ 28 #define _QUEUE_H_ 29 30 /* The common BSD linked list queue macros are already defined here for ESP-IDF */ 31 #include <sys/queue.h> 32 33 #ifdef __cplusplus 34 extern "C" { 35 #endif 36 37 /* 38 * This file defines circular queues. The other types of data structures: 39 * singly-linked lists, singly-linked tail queues, lists and tail queues 40 * are used from sys/queue.h 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 singly-linked tail queue is headed by a pair of pointers, one to the 53 * head of the list and the other to the tail of the list. The elements are 54 * singly linked for minimum space and pointer manipulation overhead at the 55 * expense of O(n) removal for arbitrary elements. New elements can be added 56 * to the list after an existing element, at the head of the list, or at the 57 * end of the list. Elements being removed from the head of the tail queue 58 * should use the explicit macro for this purpose for optimum efficiency. 59 * A singly-linked tail queue may only be traversed in the forward direction. 60 * Singly-linked tail queues are ideal for applications with large datasets 61 * and few or no removals or for implementing a FIFO queue. 62 * 63 * A list is headed by a single forward pointer (or an array of forward 64 * pointers for a hash table header). The elements are doubly linked 65 * so that an arbitrary element can be removed without a need to 66 * traverse the list. New elements can be added to the list before 67 * or after an existing element or at the head of the list. A list 68 * may only be traversed in the forward direction. 69 * 70 * A tail queue is headed by a pair of pointers, one to the head of the 71 * list and the other to the tail of the list. The elements are doubly 72 * linked so that an arbitrary element can be removed without a need to 73 * traverse the list. New elements can be added to the list before or 74 * after an existing element, at the head of the list, or at the end of 75 * the list. A tail queue may be traversed in either direction. 76 * 77 * A circle queue is headed by a pair of pointers, one to the head of the 78 * list and the other to the tail of the list. The elements are doubly 79 * linked so that an arbitrary element can be removed without a need to 80 * traverse the list. New elements can be added to the list before or after 81 * an existing element, at the head of the list, or at the end of the list. 82 * A circle queue may be traversed in either direction, but has a more 83 * complex end of list detection. 84 * 85 * For details on the use of these macros, see the queue(3) manual page. 86 * 87 * 88 * SLIST LIST STAILQ TAILQ CIRCLEQ 89 * _HEAD + + + + + 90 * _HEAD_INITIALIZER + + + + + 91 * _ENTRY + + + + + 92 * _INIT + + + + + 93 * _EMPTY + + + + + 94 * _FIRST + + + + + 95 * _NEXT + + + + + 96 * _PREV - - - + + 97 * _LAST - - + + + 98 * _FOREACH + + + + + 99 * _FOREACH_REVERSE - - - + + 100 * _INSERT_HEAD + + + + + 101 * _INSERT_BEFORE - + - + + 102 * _INSERT_AFTER + + + + + 103 * _INSERT_TAIL - - + + + 104 * _REMOVE_HEAD + - + - - 105 * _REMOVE + + + + + 106 * 107 */ 108 109 /* 110 * Circular queue declarations. 111 */ 112 #define CIRCLEQ_HEAD(name, type) \ 113 struct name { \ 114 struct type *cqh_first; /* first element */ \ 115 struct type *cqh_last; /* last element */ \ 116 } 117 118 #define CIRCLEQ_HEAD_INITIALIZER(head) \ 119 { (void *)&(head), (void *)&(head) } 120 121 #define CIRCLEQ_ENTRY(type) \ 122 struct { \ 123 struct type *cqe_next; /* next element */ \ 124 struct type *cqe_prev; /* previous element */ \ 125 } 126 127 /* 128 * Circular queue functions. 129 */ 130 #define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head)) 131 132 #define CIRCLEQ_FIRST(head) ((head)->cqh_first) 133 134 #define CIRCLEQ_FOREACH(var, head, field) \ 135 for ((var) = CIRCLEQ_FIRST((head)); \ 136 (var) != (void *)(head) || ((var) = NULL); \ 137 (var) = CIRCLEQ_NEXT((var), field)) 138 139 #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ 140 for ((var) = CIRCLEQ_LAST((head)); \ 141 (var) != (void *)(head) || ((var) = NULL); \ 142 (var) = CIRCLEQ_PREV((var), field)) 143 144 #define CIRCLEQ_INIT(head) do { \ 145 CIRCLEQ_FIRST((head)) = (void *)(head); \ 146 CIRCLEQ_LAST((head)) = (void *)(head); \ 147 } while (0) 148 149 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 150 CIRCLEQ_NEXT((elm), field) = CIRCLEQ_NEXT((listelm), field); \ 151 CIRCLEQ_PREV((elm), field) = (listelm); \ 152 if (CIRCLEQ_NEXT((listelm), field) == (void *)(head)) \ 153 CIRCLEQ_LAST((head)) = (elm); \ 154 else \ 155 CIRCLEQ_PREV(CIRCLEQ_NEXT((listelm), field), field) = (elm);\ 156 CIRCLEQ_NEXT((listelm), field) = (elm); \ 157 } while (0) 158 159 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ 160 CIRCLEQ_NEXT((elm), field) = (listelm); \ 161 CIRCLEQ_PREV((elm), field) = CIRCLEQ_PREV((listelm), field); \ 162 if (CIRCLEQ_PREV((listelm), field) == (void *)(head)) \ 163 CIRCLEQ_FIRST((head)) = (elm); \ 164 else \ 165 CIRCLEQ_NEXT(CIRCLEQ_PREV((listelm), field), field) = (elm);\ 166 CIRCLEQ_PREV((listelm), field) = (elm); \ 167 } while (0) 168 169 #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ 170 CIRCLEQ_NEXT((elm), field) = CIRCLEQ_FIRST((head)); \ 171 CIRCLEQ_PREV((elm), field) = (void *)(head); \ 172 if (CIRCLEQ_LAST((head)) == (void *)(head)) \ 173 CIRCLEQ_LAST((head)) = (elm); \ 174 else \ 175 CIRCLEQ_PREV(CIRCLEQ_FIRST((head)), field) = (elm); \ 176 CIRCLEQ_FIRST((head)) = (elm); \ 177 } while (0) 178 179 #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ 180 CIRCLEQ_NEXT((elm), field) = (void *)(head); \ 181 CIRCLEQ_PREV((elm), field) = CIRCLEQ_LAST((head)); \ 182 if (CIRCLEQ_FIRST((head)) == (void *)(head)) \ 183 CIRCLEQ_FIRST((head)) = (elm); \ 184 else \ 185 CIRCLEQ_NEXT(CIRCLEQ_LAST((head)), field) = (elm); \ 186 CIRCLEQ_LAST((head)) = (elm); \ 187 } while (0) 188 189 #define CIRCLEQ_LAST(head) ((head)->cqh_last) 190 191 #define CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next) 192 193 #define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev) 194 195 #define CIRCLEQ_REMOVE(head, elm, field) do { \ 196 if (CIRCLEQ_NEXT((elm), field) == (void *)(head)) \ 197 CIRCLEQ_LAST((head)) = CIRCLEQ_PREV((elm), field); \ 198 else \ 199 CIRCLEQ_PREV(CIRCLEQ_NEXT((elm), field), field) = \ 200 CIRCLEQ_PREV((elm), field); \ 201 if (CIRCLEQ_PREV((elm), field) == (void *)(head)) \ 202 CIRCLEQ_FIRST((head)) = CIRCLEQ_NEXT((elm), field); \ 203 else \ 204 CIRCLEQ_NEXT(CIRCLEQ_PREV((elm), field), field) = \ 205 CIRCLEQ_NEXT((elm), field); \ 206 } while (0) 207 208 #ifdef __cplusplus 209 } 210 #endif 211 212 #endif /* !_SYS_QUEUE_H_ */ 213
