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 /* returns if the queue became non empty */
91 static inline bool
circle_enqueue_tail(circle_queue_t cq,queue_entry_t elt)92 circle_enqueue_tail(circle_queue_t cq, queue_entry_t elt)
93 {
94 queue_entry_t head = circle_queue_first(cq);
95 queue_entry_t tail = circle_queue_last(cq);
96
97 if (head == NULL) {
98 cq->head = elt->next = elt->prev = elt;
99 return true;
100 } else if (tail->next != head) {
101 __queue_element_linkage_invalid(tail);
102 } else {
103 elt->next = head;
104 elt->prev = tail;
105 tail->next = elt;
106 head->prev = elt;
107 return false;
108 }
109 }
110
111 /* returns if the queue became non empty */
112 static inline bool
circle_enqueue_head(circle_queue_t cq,queue_entry_t elt)113 circle_enqueue_head(circle_queue_t cq, queue_entry_t elt)
114 {
115 bool was_empty = circle_enqueue_tail(cq, elt);
116
117 cq->head = elt;
118 return was_empty;
119 }
120
121 static inline void
circle_dequeue(circle_queue_t cq,queue_entry_t elt)122 circle_dequeue(circle_queue_t cq, queue_entry_t elt)
123 {
124 queue_entry_t elt_prev = elt->prev;
125 queue_entry_t elt_next = elt->next;
126
127 __QUEUE_ELT_VALIDATE(elt);
128
129 if (elt == elt_next) {
130 assert(cq->head == elt);
131 cq->head = NULL;
132 } else {
133 elt_prev->next = elt_next;
134 elt_next->prev = elt_prev;
135 if (cq->head == elt) {
136 cq->head = elt_next;
137 }
138 }
139
140 __DEQUEUE_ELT_CLEANUP(elt);
141 }
142
143 static inline queue_entry_t
circle_dequeue_head(circle_queue_t cq)144 circle_dequeue_head(circle_queue_t cq)
145 {
146 queue_entry_t elt = circle_queue_first(cq);
147 if (elt) {
148 circle_dequeue(cq, elt);
149 }
150 return elt;
151 }
152
153 static inline queue_entry_t
circle_dequeue_tail(circle_queue_t cq)154 circle_dequeue_tail(circle_queue_t cq)
155 {
156 queue_entry_t elt = circle_queue_last(cq);
157 if (elt) {
158 circle_dequeue(cq, elt);
159 }
160 return elt;
161 }
162
163 /* returns if the destination queue became non empty */
164 static inline bool
circle_queue_concat_tail(circle_queue_t dq,circle_queue_t sq)165 circle_queue_concat_tail(circle_queue_t dq, circle_queue_t sq)
166 {
167 queue_entry_t d_head, d_tail;
168 queue_entry_t s_head, s_tail;
169
170 s_head = sq->head;
171 if (!s_head) {
172 return false;
173 }
174 s_tail = s_head->prev;
175 if (s_tail->next != s_head) {
176 __queue_element_linkage_invalid(s_head);
177 }
178 sq->head = (queue_entry_t)NULL;
179
180 d_head = dq->head;
181 if (!d_head) {
182 dq->head = s_head;
183 return true;
184 }
185 d_tail = d_head->prev;
186 if (d_tail->next != d_head) {
187 __queue_element_linkage_invalid(d_head);
188 }
189
190 d_tail->next = s_head;
191 s_head->prev = d_tail;
192
193 d_head->prev = s_tail;
194 s_tail->next = d_head;
195 return false;
196 }
197
198 static inline void
circle_queue_rotate_head_forward(circle_queue_t cq)199 circle_queue_rotate_head_forward(circle_queue_t cq)
200 {
201 queue_entry_t first = circle_queue_first(cq);
202 if (first != NULL) {
203 cq->head = first->next;
204 }
205 }
206
207 static inline void
circle_queue_rotate_head_backward(circle_queue_t cq)208 circle_queue_rotate_head_backward(circle_queue_t cq)
209 {
210 queue_entry_t last = circle_queue_last(cq);
211 if (last != NULL) {
212 cq->head = last;
213 }
214 }
215
216 /*
217 * Macro: cqe_element
218 * Function:
219 * Convert a cirle_queue_entry_t pointer to a queue element pointer.
220 * Get a pointer to the user-defined element containing
221 * a given cirle_queue_entry_t
222 * Header:
223 * <type> * cqe_element(cirle_queue_entry_t qe, <type>, field)
224 * qe - queue entry to convert
225 * <type> - what's in the queue (e.g., struct some_data)
226 * <field> - is the chain field in <type>
227 * Note:
228 * Do not use pointer types for <type>
229 */
230 #define cqe_element(qe, type, field) __container_of(qe, type, field)
231
232 /*
233 * Macro: cqe_foreach
234 * Function:
235 * Iterate over each queue_entry_t structure.
236 * Generates a 'for' loop, setting 'qe' to
237 * each queue_entry_t in the queue.
238 * Header:
239 * cqe_foreach(queue_entry_t qe, queue_t head)
240 * qe - iteration variable
241 * head - pointer to queue_head_t (head of queue)
242 * Note:
243 * This should only be used with Method 1 queue iteration (linkage chains)
244 */
245 #define cqe_foreach(qe, head) \
246 for (qe = circle_queue_first(head); qe; qe = circle_queue_next(head, qe))
247
248 /*
249 * Macro: cqe_foreach_safe
250 * Function:
251 * Safely iterate over each queue_entry_t structure.
252 *
253 * Use this iterator macro if you plan to remove the
254 * queue_entry_t, qe, from the queue during the
255 * iteration.
256 * Header:
257 * cqe_foreach_safe(queue_entry_t qe, queue_t head)
258 * qe - iteration variable
259 * head - pointer to queue_head_t (head of queue)
260 * Note:
261 * This should only be used with Method 1 queue iteration (linkage chains)
262 */
263 #define cqe_foreach_safe(qe, head) \
264 for (queue_entry_t _ne, _qe = circle_queue_first(head); \
265 (qe = _qe) && (_ne = circle_queue_next(head, _qe), 1); \
266 _qe = _ne)
267
268 /*
269 * Macro: cqe_foreach_element
270 * Function:
271 * Iterate over each _element_ in a queue
272 * where each queue_entry_t points to another
273 * queue_entry_t, i.e., managed by the [de|en]queue_head/
274 * [de|en]queue_tail / remqueue / etc. function.
275 * Header:
276 * cqe_foreach_element(<type> *elt, queue_t head, <field>)
277 * elt - iteration variable
278 * <type> - what's in the queue (e.g., struct some_data)
279 * <field> - is the chain field in <type>
280 * Note:
281 * This should only be used with Method 1 queue iteration (linkage chains)
282 */
283 #define cqe_foreach_element(elt, head, field) \
284 for (queue_entry_t _qe = circle_queue_first(head); \
285 _qe && (elt = cqe_element(_qe, typeof(*(elt)), field), 1); \
286 _qe = circle_queue_next(head, _qe))
287
288 /*
289 * Macro: cqe_foreach_element_safe
290 * Function:
291 * Safely iterate over each _element_ in a queue
292 * where each queue_entry_t points to another
293 * queue_entry_t, i.e., managed by the [de|en]queue_head/
294 * [de|en]queue_tail / remqueue / etc. function.
295 *
296 * Use this iterator macro if you plan to remove the
297 * element, elt, from the queue during the iteration.
298 * Header:
299 * cqe_foreach_element_safe(<type> *elt, queue_t head, <field>)
300 * elt - iteration variable
301 * <type> - what's in the queue (e.g., struct some_data)
302 * <field> - is the chain field in <type>
303 * Note:
304 * This should only be used with Method 1 queue iteration (linkage chains)
305 */
306 #define cqe_foreach_element_safe(elt, head, field) \
307 for (queue_entry_t _ne, _qe = circle_queue_first(head); \
308 _qe && (elt = cqe_element(_qe, typeof(*(elt)), field), \
309 _ne = circle_queue_next(head, _qe), 1); \
310 _qe = _ne)
311
312 /* Dequeue an element from head, or return NULL if the queue is empty */
313 #define cqe_dequeue_head(head, type, field) ({ \
314 queue_entry_t _tmp_entry = circle_dequeue_head((head)); \
315 type *_tmp_element = (type*) NULL; \
316 if (_tmp_entry != (queue_entry_t) NULL) \
317 _tmp_element = cqe_element(_tmp_entry, type, field); \
318 _tmp_element; \
319 })
320
321 /* Dequeue an element from tail, or return NULL if the queue is empty */
322 #define cqe_dequeue_tail(head, type, field) ({ \
323 queue_entry_t _tmp_entry = circle_dequeue_tail((head)); \
324 type *_tmp_element = (type*) NULL; \
325 if (_tmp_entry != (queue_entry_t) NULL) \
326 _tmp_element = cqe_element(_tmp_entry, type, field); \
327 _tmp_element; \
328 })
329
330 /* Peek at the first element, or return NULL if the queue is empty */
331 #define cqe_queue_first(head, type, field) ({ \
332 queue_entry_t _tmp_entry = circle_queue_first((head)); \
333 type *_tmp_element = (type*) NULL; \
334 if (_tmp_entry != (queue_entry_t) NULL) \
335 _tmp_element = cqe_element(_tmp_entry, type, field); \
336 _tmp_element; \
337 })
338
339 /* Peek at the next element, or return NULL if it is last */
340 #define cqe_queue_next(elt, head, type, field) ({ \
341 queue_entry_t _tmp_entry = circle_queue_next((head), (elt)); \
342 type *_tmp_element = (type*) NULL; \
343 if (_tmp_entry != (queue_entry_t) NULL) \
344 _tmp_element = cqe_element(_tmp_entry, type, field); \
345 _tmp_element; \
346 })
347
348 /* Peek at the tail element, or return NULL if the queue is empty */
349 #define cqe_queue_last(head, type, field) ({ \
350 queue_entry_t _tmp_entry = circle_queue_last((head)); \
351 type *_tmp_element = (type*) NULL; \
352 if (_tmp_entry != (queue_entry_t) NULL) \
353 _tmp_element = cqe_element(_tmp_entry, type, field); \
354 _tmp_element; \
355 })
356
357 /*
358 * Macro: circle_queue_init
359 * Function:
360 * Initialize the given circle queue.
361 * Header:
362 * void circle_queue_init(q)
363 * circle_queue_t q; \* MODIFIED *\
364 */
365 #define circle_queue_init(q) \
366 MACRO_BEGIN \
367 (q)->head = NULL; \
368 MACRO_END
369
370 __END_DECLS
371
372 #endif /* _KERN_QUEUE_H_ */
373