[apple/xnu.git] / osfmk / kern / circle_queue.h

/*
 * Copyright (c) 2019 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 *
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 *
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 *
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */

#ifndef _KERN_CIRCLE_QUEUE_H_
#define _KERN_CIRCLE_QUEUE_H_

#include <kern/queue.h>
#include <kern/assert.h>

__BEGIN_DECLS

/*
 * Circle Queue Management APIs
 *
 * These are similar to the queues from queue.h,
 * but the circle queue head is a single pointer to the first element
 * of the queue.
 */

typedef struct circle_queue_head {
	queue_entry_t head;
} circle_queue_head_t, *circle_queue_t;

static inline bool
circle_queue_empty(circle_queue_t cq)
{
	return cq->head == NULL;
}

static inline queue_entry_t
circle_queue_first(circle_queue_t cq)
{
	return cq->head;
}

static inline queue_entry_t
circle_queue_last(circle_queue_t cq)
{
	queue_entry_t elt = circle_queue_first(cq);
	if (elt) {
		__builtin_assume(elt->prev != NULL);
		return elt->prev;
	}
	return NULL;
}

static inline queue_entry_t
circle_queue_next(circle_queue_t cq, queue_entry_t elt)
{
	return elt->next == cq->head ? NULL : elt->next;
}

static inline size_t
circle_queue_length(circle_queue_t cq)
{
	queue_entry_t elt = circle_queue_first(cq);
	size_t n = 0;

	for (; elt; elt = circle_queue_next(cq, elt)) {
		n++;
	}
	return n;
}

static inline void
circle_enqueue_tail(circle_queue_t cq, queue_entry_t elt)
{
	queue_entry_t head = circle_queue_first(cq);
	queue_entry_t tail = circle_queue_last(cq);

	if (head == NULL) {
		cq->head = elt->next = elt->prev = elt;
	} else {
		elt->next = head;
		elt->prev = tail;
		tail->next = elt;
		head->prev = elt;
	}
}

static inline void
circle_enqueue_head(circle_queue_t cq, queue_entry_t elt)
{
	circle_enqueue_tail(cq, elt);
	cq->head = elt;
}

static inline void
circle_dequeue(circle_queue_t cq, queue_entry_t elt)
{
	queue_entry_t elt_prev = elt->prev;
	queue_entry_t elt_next = elt->next;

	if (elt == elt_next) {
		assert(cq->head == elt);
		cq->head = NULL;
	} else {
		elt_prev->next = elt_next;
		elt_next->prev = elt_prev;
		if (cq->head == elt) {
			cq->head = elt_next;
		}
	}
	__DEQUEUE_ELT_CLEANUP(elt);
}

static inline queue_entry_t
circle_dequeue_head(circle_queue_t cq)
{
	queue_entry_t elt = circle_queue_first(cq);
	if (elt) {
		circle_dequeue(cq, elt);
	}
	return elt;
}

static inline queue_entry_t
circle_dequeue_tail(circle_queue_t cq)
{
	queue_entry_t elt = circle_queue_last(cq);
	if (elt) {
		circle_dequeue(cq, elt);
	}
	return elt;
}

/*
 *	Macro:		cqe_element
 *	Function:
 *		Convert a cirle_queue_entry_t pointer to a queue element pointer.
 *		Get a pointer to the user-defined element containing
 *		a given cirle_queue_entry_t
 *	Header:
 *		<type> * cqe_element(cirle_queue_entry_t qe, <type>, field)
 *			qe      - queue entry to convert
 *			<type>  - what's in the queue (e.g., struct some_data)
 *			<field> - is the chain field in <type>
 *	Note:
 *		Do not use pointer types for <type>
 */
#define cqe_element(qe, type, field) __container_of(qe, type, field)

/*
 *	Macro:		cqe_foreach
 *	Function:
 *		Iterate over each queue_entry_t structure.
 *		Generates a 'for' loop, setting 'qe' to
 *		each queue_entry_t in the queue.
 *	Header:
 *		cqe_foreach(queue_entry_t qe, queue_t head)
 *			qe   - iteration variable
 *			head - pointer to queue_head_t (head of queue)
 *	Note:
 *		This should only be used with Method 1 queue iteration (linkage chains)
 */
#define cqe_foreach(qe, head) \
	for (qe = circle_queue_first(head); qe; qe = circle_queue_next(head, qe))

/*
 *	Macro:		cqe_foreach_safe
 *	Function:
 *		Safely iterate over each queue_entry_t structure.
 *
 *		Use this iterator macro if you plan to remove the
 *		queue_entry_t, qe, from the queue during the
 *		iteration.
 *	Header:
 *		cqe_foreach_safe(queue_entry_t qe, queue_t head)
 *			qe   - iteration variable
 *			head - pointer to queue_head_t (head of queue)
 *	Note:
 *		This should only be used with Method 1 queue iteration (linkage chains)
 */
#define cqe_foreach_safe(qe, head) \
	for (queue_entry_t _ne, _qe = circle_queue_first(head); \
	     (qe = _qe) && (_ne = circle_queue_next(head, _qe), 1); \
	     _qe = _ne)

/*
 *	Macro:		cqe_foreach_element
 *	Function:
 *		Iterate over each _element_ in a queue
 *		where each queue_entry_t points to another
 *		queue_entry_t, i.e., managed by the [de|en]queue_head/
 *		[de|en]queue_tail / remqueue / etc. function.
 *	Header:
 *		cqe_foreach_element(<type> *elt, queue_t head, <field>)
 *			elt     - iteration variable
 *			<type>  - what's in the queue (e.g., struct some_data)
 *			<field> - is the chain field in <type>
 *	Note:
 *		This should only be used with Method 1 queue iteration (linkage chains)
 */
#define cqe_foreach_element(elt, head, field) \
	for (queue_entry_t _qe = circle_queue_first(head); \
	     _qe && (elt = cqe_element(_qe, typeof(*(elt)), field), 1); \
	     _qe = circle_queue_next(head, _qe))

/*
 *	Macro:		cqe_foreach_element_safe
 *	Function:
 *		Safely iterate over each _element_ in a queue
 *		where each queue_entry_t points to another
 *		queue_entry_t, i.e., managed by the [de|en]queue_head/
 *		[de|en]queue_tail / remqueue / etc. function.
 *
 *		Use this iterator macro if you plan to remove the
 *		element, elt, from the queue during the iteration.
 *	Header:
 *		cqe_foreach_element_safe(<type> *elt, queue_t head, <field>)
 *			elt     - iteration variable
 *			<type>  - what's in the queue (e.g., struct some_data)
 *			<field> - is the chain field in <type>
 *	Note:
 *		This should only be used with Method 1 queue iteration (linkage chains)
 */
#define cqe_foreach_element_safe(elt, head, field) \
	for (queue_entry_t _ne, _qe = circle_queue_first(head); \
	     _qe && (elt = cqe_element(_qe, typeof(*(elt)), field), \
	     _ne = circle_queue_next(head, _qe), 1); \
	     _qe = _ne)

/* Dequeue an element from head, or return NULL if the queue is empty */
#define cqe_dequeue_head(head, type, field) ({ \
	queue_entry_t _tmp_entry = circle_dequeue_head((head)); \
	type *_tmp_element = (type*) NULL; \
	if (_tmp_entry != (queue_entry_t) NULL) \
	        _tmp_element = cqe_element(_tmp_entry, type, field); \
	_tmp_element; \
})

/* Dequeue an element from tail, or return NULL if the queue is empty */
#define cqe_dequeue_tail(head, type, field) ({ \
	queue_entry_t _tmp_entry = circle_dequeue_tail((head)); \
	type *_tmp_element = (type*) NULL; \
	if (_tmp_entry != (queue_entry_t) NULL) \
	        _tmp_element = cqe_element(_tmp_entry, type, field); \
	_tmp_element; \
})

/* Peek at the first element, or return NULL if the queue is empty */
#define cqe_queue_first(head, type, field) ({ \
	queue_entry_t _tmp_entry = circle_queue_first((head)); \
	type *_tmp_element = (type*) NULL; \
	if (_tmp_entry != (queue_entry_t) NULL) \
	        _tmp_element = cqe_element(_tmp_entry, type, field); \
	_tmp_element; \
})

/* Peek at the next element, or return NULL if it is last */
#define cqe_queue_next(elt, head, type, field) ({ \
	queue_entry_t _tmp_entry = circle_queue_next((head), (elt)); \
	type *_tmp_element = (type*) NULL; \
	if (_tmp_entry != (queue_entry_t) NULL) \
	        _tmp_element = cqe_element(_tmp_entry, type, field); \
	_tmp_element; \
})

/* Peek at the tail element, or return NULL if the queue is empty */
#define cqe_queue_last(head, type, field) ({ \
	queue_entry_t _tmp_entry = circle_queue_last((head)); \
	type *_tmp_element = (type*) NULL; \
	if (_tmp_entry != (queue_entry_t) NULL) \
	        _tmp_element = cqe_element(_tmp_entry, type, field); \
	_tmp_element; \
})

/*
 *	Macro:		circle_queue_init
 *	Function:
 *		Initialize the given circle queue.
 *	Header:
 *		void circle_queue_init(q)
 *			circle_queue_t		q;	\* MODIFIED *\
 */
#define circle_queue_init(q)   \
MACRO_BEGIN             \
	(q)->head = NULL; \
MACRO_END

__END_DECLS

#endif  /* _KERN_QUEUE_H_ */
Commit	Line	Data
cb323159 A	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	/*
153	* Macro: cqe_element
154	* Function:
155	* Convert a cirle_queue_entry_t pointer to a queue element pointer.
156	* Get a pointer to the user-defined element containing
157	* a given cirle_queue_entry_t
158	* Header:
159	* <type> * cqe_element(cirle_queue_entry_t qe, <type>, field)
160	* qe - queue entry to convert
161	* <type> - what's in the queue (e.g., struct some_data)
162	* <field> - is the chain field in <type>
163	* Note:
164	* Do not use pointer types for <type>
165	*/
166	#define cqe_element(qe, type, field) __container_of(qe, type, field)
167
168	/*
169	* Macro: cqe_foreach
170	* Function:
171	* Iterate over each queue_entry_t structure.
172	* Generates a 'for' loop, setting 'qe' to
173	* each queue_entry_t in the queue.
174	* Header:
175	* cqe_foreach(queue_entry_t qe, queue_t head)
176	* qe - iteration variable
177	* head - pointer to queue_head_t (head of queue)
178	* Note:
179	* This should only be used with Method 1 queue iteration (linkage chains)
180	*/
181	#define cqe_foreach(qe, head) \
182	for (qe = circle_queue_first(head); qe; qe = circle_queue_next(head, qe))
183
184	/*
185	* Macro: cqe_foreach_safe
186	* Function:
187	* Safely iterate over each queue_entry_t structure.
188	*
189	* Use this iterator macro if you plan to remove the
190	* queue_entry_t, qe, from the queue during the
191	* iteration.
192	* Header:
193	* cqe_foreach_safe(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_safe(qe, head) \
200	for (queue_entry_t _ne, _qe = circle_queue_first(head); \
201	(qe = _qe) && (_ne = circle_queue_next(head, _qe), 1); \
202	_qe = _ne)
203
204	/*
205	* Macro: cqe_foreach_element
206	* Function:
207	* Iterate over each _element_ in a queue
208	* where each queue_entry_t points to another
209	* queue_entry_t, i.e., managed by the [de\|en]queue_head/
210	* [de\|en]queue_tail / remqueue / etc. function.
211	* Header:
212	* cqe_foreach_element(<type> *elt, queue_t head, <field>)
213	* elt - iteration variable
214	* <type> - what's in the queue (e.g., struct some_data)
215	* <field> - is the chain field in <type>
216	* Note:
217	* This should only be used with Method 1 queue iteration (linkage chains)
218	*/
219	#define cqe_foreach_element(elt, head, field) \
220	for (queue_entry_t _qe = circle_queue_first(head); \
221	_qe && (elt = cqe_element(_qe, typeof(*(elt)), field), 1); \
222	_qe = circle_queue_next(head, _qe))
223
224	/*
225	* Macro: cqe_foreach_element_safe
226	* Function:
227	* Safely iterate over each _element_ in a queue
228	* where each queue_entry_t points to another
229	* queue_entry_t, i.e., managed by the [de\|en]queue_head/
230	* [de\|en]queue_tail / remqueue / etc. function.
231	*
232	* Use this iterator macro if you plan to remove the
233	* element, elt, from the queue during the iteration.
234	* Header:
235	* cqe_foreach_element_safe(<type> *elt, queue_t head, <field>)
236	* elt - iteration variable
237	* <type> - what's in the queue (e.g., struct some_data)
238	* <field> - is the chain field in <type>
239	* Note:
240	* This should only be used with Method 1 queue iteration (linkage chains)
241	*/
242	#define cqe_foreach_element_safe(elt, head, field) \
243	for (queue_entry_t _ne, _qe = circle_queue_first(head); \
244	_qe && (elt = cqe_element(_qe, typeof(*(elt)), field), \
245	_ne = circle_queue_next(head, _qe), 1); \
246	_qe = _ne)
247
248	/* Dequeue an element from head, or return NULL if the queue is empty */
249	#define cqe_dequeue_head(head, type, field) ({ \
250	queue_entry_t _tmp_entry = circle_dequeue_head((head)); \
251	type _tmp_element = (type) NULL; \
252	if (_tmp_entry != (queue_entry_t) NULL) \
253	_tmp_element = cqe_element(_tmp_entry, type, field); \
254	_tmp_element; \
255	})
256
257	/* Dequeue an element from tail, or return NULL if the queue is empty */
258	#define cqe_dequeue_tail(head, type, field) ({ \
259	queue_entry_t _tmp_entry = circle_dequeue_tail((head)); \
260	type _tmp_element = (type) NULL; \
261	if (_tmp_entry != (queue_entry_t) NULL) \
262	_tmp_element = cqe_element(_tmp_entry, type, field); \
263	_tmp_element; \
264	})
265
266	/* Peek at the first element, or return NULL if the queue is empty */
267	#define cqe_queue_first(head, type, field) ({ \
268	queue_entry_t _tmp_entry = circle_queue_first((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	/* Peek at the next element, or return NULL if it is last */
276	#define cqe_queue_next(elt, head, type, field) ({ \
277	queue_entry_t _tmp_entry = circle_queue_next((head), (elt)); \
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 tail element, or return NULL if the queue is empty */
285	#define cqe_queue_last(head, type, field) ({ \
286	queue_entry_t _tmp_entry = circle_queue_last((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	/*
294	* Macro: circle_queue_init
295	* Function:
296	* Initialize the given circle queue.
297	* Header:
298	* void circle_queue_init(q)
299	* circle_queue_t q; \* MODIFIED *\
300	*/
301	#define circle_queue_init(q) \
302	MACRO_BEGIN \
303	(q)->head = NULL; \
304	MACRO_END
305
306	__END_DECLS
307
308	#endif /* _KERN_QUEUE_H_ */