circle_queue.h
1 /* 2 * Copyright (c) 2019 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28 29 #ifndef _KERN_CIRCLE_QUEUE_H_ 30 #define _KERN_CIRCLE_QUEUE_H_ 31 32 #include <kern/queue.h> 33 #include <kern/assert.h> 34 35 __BEGIN_DECLS 36 37 /* 38 * Circle Queue Management APIs 39 * 40 * These are similar to the queues from queue.h, 41 * but the circle queue head is a single pointer to the first element 42 * of the queue. 43 */ 44 45 typedef struct circle_queue_head { 46 queue_entry_t head; 47 } circle_queue_head_t, *circle_queue_t; 48 49 static inline bool 50 circle_queue_empty(circle_queue_t cq) 51 { 52 return cq->head == NULL; 53 } 54 55 static inline queue_entry_t 56 circle_queue_first(circle_queue_t cq) 57 { 58 return cq->head; 59 } 60 61 static inline queue_entry_t 62 circle_queue_last(circle_queue_t cq) 63 { 64 queue_entry_t elt = circle_queue_first(cq); 65 if (elt) { 66 __builtin_assume(elt->prev != NULL); 67 return elt->prev; 68 } 69 return NULL; 70 } 71 72 static inline queue_entry_t 73 circle_queue_next(circle_queue_t cq, queue_entry_t elt) 74 { 75 return elt->next == cq->head ? NULL : elt->next; 76 } 77 78 static inline size_t 79 circle_queue_length(circle_queue_t cq) 80 { 81 queue_entry_t elt = circle_queue_first(cq); 82 size_t n = 0; 83 84 for (; elt; elt = circle_queue_next(cq, elt)) { 85 n++; 86 } 87 return n; 88 } 89 90 static inline void 91 circle_enqueue_tail(circle_queue_t cq, queue_entry_t elt) 92 { 93 queue_entry_t head = circle_queue_first(cq); 94 queue_entry_t tail = circle_queue_last(cq); 95 96 if (head == NULL) { 97 cq->head = elt->next = elt->prev = elt; 98 } else { 99 elt->next = head; 100 elt->prev = tail; 101 tail->next = elt; 102 head->prev = elt; 103 } 104 } 105 106 static inline void 107 circle_enqueue_head(circle_queue_t cq, queue_entry_t elt) 108 { 109 circle_enqueue_tail(cq, elt); 110 cq->head = elt; 111 } 112 113 static inline void 114 circle_dequeue(circle_queue_t cq, queue_entry_t elt) 115 { 116 queue_entry_t elt_prev = elt->prev; 117 queue_entry_t elt_next = elt->next; 118 119 if (elt == elt_next) { 120 assert(cq->head == elt); 121 cq->head = NULL; 122 } else { 123 elt_prev->next = elt_next; 124 elt_next->prev = elt_prev; 125 if (cq->head == elt) { 126 cq->head = elt_next; 127 } 128 } 129 __DEQUEUE_ELT_CLEANUP(elt); 130 } 131 132 static inline queue_entry_t 133 circle_dequeue_head(circle_queue_t cq) 134 { 135 queue_entry_t elt = circle_queue_first(cq); 136 if (elt) { 137 circle_dequeue(cq, elt); 138 } 139 return elt; 140 } 141 142 static inline queue_entry_t 143 circle_dequeue_tail(circle_queue_t cq) 144 { 145 queue_entry_t elt = circle_queue_last(cq); 146 if (elt) { 147 circle_dequeue(cq, elt); 148 } 149 return elt; 150 } 151 152 static inline void 153 circle_queue_rotate_head_forward(circle_queue_t cq) 154 { 155 queue_entry_t first = circle_queue_first(cq); 156 if (first != NULL) { 157 cq->head = first->next; 158 } 159 } 160 161 static inline void 162 circle_queue_rotate_head_backward(circle_queue_t cq) 163 { 164 queue_entry_t last = circle_queue_last(cq); 165 if (last != NULL) { 166 cq->head = last; 167 } 168 } 169 170 /* 171 * Macro: cqe_element 172 * Function: 173 * Convert a cirle_queue_entry_t pointer to a queue element pointer. 174 * Get a pointer to the user-defined element containing 175 * a given cirle_queue_entry_t 176 * Header: 177 * <type> * cqe_element(cirle_queue_entry_t qe, <type>, field) 178 * qe - queue entry to convert 179 * <type> - what's in the queue (e.g., struct some_data) 180 * <field> - is the chain field in <type> 181 * Note: 182 * Do not use pointer types for <type> 183 */ 184 #define cqe_element(qe, type, field) __container_of(qe, type, field) 185 186 /* 187 * Macro: cqe_foreach 188 * Function: 189 * Iterate over each queue_entry_t structure. 190 * Generates a 'for' loop, setting 'qe' to 191 * each queue_entry_t in the queue. 192 * Header: 193 * cqe_foreach(queue_entry_t qe, queue_t head) 194 * qe - iteration variable 195 * head - pointer to queue_head_t (head of queue) 196 * Note: 197 * This should only be used with Method 1 queue iteration (linkage chains) 198 */ 199 #define cqe_foreach(qe, head) \ 200 for (qe = circle_queue_first(head); qe; qe = circle_queue_next(head, qe)) 201 202 /* 203 * Macro: cqe_foreach_safe 204 * Function: 205 * Safely iterate over each queue_entry_t structure. 206 * 207 * Use this iterator macro if you plan to remove the 208 * queue_entry_t, qe, from the queue during the 209 * iteration. 210 * Header: 211 * cqe_foreach_safe(queue_entry_t qe, queue_t head) 212 * qe - iteration variable 213 * head - pointer to queue_head_t (head of queue) 214 * Note: 215 * This should only be used with Method 1 queue iteration (linkage chains) 216 */ 217 #define cqe_foreach_safe(qe, head) \ 218 for (queue_entry_t _ne, _qe = circle_queue_first(head); \ 219 (qe = _qe) && (_ne = circle_queue_next(head, _qe), 1); \ 220 _qe = _ne) 221 222 /* 223 * Macro: cqe_foreach_element 224 * Function: 225 * Iterate over each _element_ in a queue 226 * where each queue_entry_t points to another 227 * queue_entry_t, i.e., managed by the [de|en]queue_head/ 228 * [de|en]queue_tail / remqueue / etc. function. 229 * Header: 230 * cqe_foreach_element(<type> *elt, queue_t head, <field>) 231 * elt - iteration variable 232 * <type> - what's in the queue (e.g., struct some_data) 233 * <field> - is the chain field in <type> 234 * Note: 235 * This should only be used with Method 1 queue iteration (linkage chains) 236 */ 237 #define cqe_foreach_element(elt, head, field) \ 238 for (queue_entry_t _qe = circle_queue_first(head); \ 239 _qe && (elt = cqe_element(_qe, typeof(*(elt)), field), 1); \ 240 _qe = circle_queue_next(head, _qe)) 241 242 /* 243 * Macro: cqe_foreach_element_safe 244 * Function: 245 * Safely iterate over each _element_ in a queue 246 * where each queue_entry_t points to another 247 * queue_entry_t, i.e., managed by the [de|en]queue_head/ 248 * [de|en]queue_tail / remqueue / etc. function. 249 * 250 * Use this iterator macro if you plan to remove the 251 * element, elt, from the queue during the iteration. 252 * Header: 253 * cqe_foreach_element_safe(<type> *elt, queue_t head, <field>) 254 * elt - iteration variable 255 * <type> - what's in the queue (e.g., struct some_data) 256 * <field> - is the chain field in <type> 257 * Note: 258 * This should only be used with Method 1 queue iteration (linkage chains) 259 */ 260 #define cqe_foreach_element_safe(elt, head, field) \ 261 for (queue_entry_t _ne, _qe = circle_queue_first(head); \ 262 _qe && (elt = cqe_element(_qe, typeof(*(elt)), field), \ 263 _ne = circle_queue_next(head, _qe), 1); \ 264 _qe = _ne) 265 266 /* Dequeue an element from head, or return NULL if the queue is empty */ 267 #define cqe_dequeue_head(head, type, field) ({ \ 268 queue_entry_t _tmp_entry = circle_dequeue_head((head)); \ 269 type *_tmp_element = (type*) NULL; \ 270 if (_tmp_entry != (queue_entry_t) NULL) \ 271 _tmp_element = cqe_element(_tmp_entry, type, field); \ 272 _tmp_element; \ 273 }) 274 275 /* Dequeue an element from tail, or return NULL if the queue is empty */ 276 #define cqe_dequeue_tail(head, type, field) ({ \ 277 queue_entry_t _tmp_entry = circle_dequeue_tail((head)); \ 278 type *_tmp_element = (type*) NULL; \ 279 if (_tmp_entry != (queue_entry_t) NULL) \ 280 _tmp_element = cqe_element(_tmp_entry, type, field); \ 281 _tmp_element; \ 282 }) 283 284 /* Peek at the first element, or return NULL if the queue is empty */ 285 #define cqe_queue_first(head, type, field) ({ \ 286 queue_entry_t _tmp_entry = circle_queue_first((head)); \ 287 type *_tmp_element = (type*) NULL; \ 288 if (_tmp_entry != (queue_entry_t) NULL) \ 289 _tmp_element = cqe_element(_tmp_entry, type, field); \ 290 _tmp_element; \ 291 }) 292 293 /* Peek at the next element, or return NULL if it is last */ 294 #define cqe_queue_next(elt, head, type, field) ({ \ 295 queue_entry_t _tmp_entry = circle_queue_next((head), (elt)); \ 296 type *_tmp_element = (type*) NULL; \ 297 if (_tmp_entry != (queue_entry_t) NULL) \ 298 _tmp_element = cqe_element(_tmp_entry, type, field); \ 299 _tmp_element; \ 300 }) 301 302 /* Peek at the tail element, or return NULL if the queue is empty */ 303 #define cqe_queue_last(head, type, field) ({ \ 304 queue_entry_t _tmp_entry = circle_queue_last((head)); \ 305 type *_tmp_element = (type*) NULL; \ 306 if (_tmp_entry != (queue_entry_t) NULL) \ 307 _tmp_element = cqe_element(_tmp_entry, type, field); \ 308 _tmp_element; \ 309 }) 310 311 /* 312 * Macro: circle_queue_init 313 * Function: 314 * Initialize the given circle queue. 315 * Header: 316 * void circle_queue_init(q) 317 * circle_queue_t q; \* MODIFIED *\ 318 */ 319 #define circle_queue_init(q) \ 320 MACRO_BEGIN \ 321 (q)->head = NULL; \ 322 MACRO_END 323 324 __END_DECLS 325 326 #endif /* _KERN_QUEUE_H_ */