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
circle_queue_empty(circle_queue_t cq)50 circle_queue_empty(circle_queue_t cq)
51 {
52 return cq->head == NULL;
53 }
54
55 static inline queue_entry_t
circle_queue_first(circle_queue_t cq)56 circle_queue_first(circle_queue_t cq)
57 {
58 return cq->head;
59 }
60
61 static inline queue_entry_t
circle_queue_last(circle_queue_t cq)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
circle_queue_next(circle_queue_t cq,queue_entry_t elt)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
circle_queue_length(circle_queue_t cq)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
circle_enqueue_tail(circle_queue_t cq,queue_entry_t elt)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
circle_enqueue_head(circle_queue_t cq,queue_entry_t elt)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
circle_dequeue(circle_queue_t cq,queue_entry_t elt)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
circle_dequeue_head(circle_queue_t cq)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
circle_dequeue_tail(circle_queue_t cq)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
circle_queue_rotate_head_forward(circle_queue_t cq)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
circle_queue_rotate_head_backward(circle_queue_t cq)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_ */
327