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 | /* returns if the queue became non empty */ |
91 | static inline bool |
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(e: 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 |
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 |
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 |
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 |
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 |
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(e: 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(e: 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 |
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 |
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 | |