xref: /xnu-10002.1.13/osfmk/kern/circle_queue.h (revision 1031c584a5e37aff177559b9f69dbd3c8c3fd30a)

/*
 * 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;
}

/* returns if the queue became non empty */
static inline bool
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;
		return true;
	} else if (tail->next != head) {
		__queue_element_linkage_invalid(tail);
	} else {
		elt->next = head;
		elt->prev = tail;
		tail->next = elt;
		head->prev = elt;
		return false;
	}
}

/* returns if the queue became non empty */
static inline bool
circle_enqueue_head(circle_queue_t cq, queue_entry_t elt)
{
	bool was_empty = circle_enqueue_tail(cq, elt);

	cq->head = elt;
	return was_empty;
}

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;

	__QUEUE_ELT_VALIDATE(elt);

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

/* returns if the destination queue became non empty */
static inline bool
circle_queue_concat_tail(circle_queue_t dq, circle_queue_t sq)
{
	queue_entry_t d_head, d_tail;
	queue_entry_t s_head, s_tail;

	s_head = sq->head;
	if (!s_head) {
		return false;
	}
	s_tail = s_head->prev;
	if (s_tail->next != s_head) {
		__queue_element_linkage_invalid(s_head);
	}
	sq->head = (queue_entry_t)NULL;

	d_head = dq->head;
	if (!d_head) {
		dq->head = s_head;
		return true;
	}
	d_tail = d_head->prev;
	if (d_tail->next != d_head) {
		__queue_element_linkage_invalid(d_head);
	}

	d_tail->next = s_head;
	s_head->prev = d_tail;

	d_head->prev = s_tail;
	s_tail->next = d_head;
	return false;
}

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_ */