[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;
}

static inline void
circle_queue_rotate_head_forward(circle_queue_t cq)
{
	queue_entry_t first = circle_queue_first(cq);
	if (first != NULL) {
		cq->head = first->next;
	}
}

static inline void
circle_queue_rotate_head_backward(circle_queue_t cq)
{
	queue_entry_t last = circle_queue_last(cq);
	if (last != NULL) {
		cq->head = last;
	}
}

/*
 *	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
ea3f0419 A	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
cb323159 A	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_ */