listqueue.h

/* SPDX-License-Identifier: GPL-2.0-or-later */
/*
 *	mimic skb_queue_head to facilitate the queue-style list manipulation.
 */

struct queue_head {
	/* must be first. */
	struct list_head	list;
	u32			qlen;
	spinlock_t		lock;
};

/**
 * queue_empty - check if a queue is empty
 * @list: queue head
 *
 * Returns true if the queue is empty, false otherwise.
 */
static inline int queue_empty(const struct queue_head *q)
{
	return list_empty(&q->list);
}

/**
 * queue_peek - peek at the head of a queue_head
 * @q: queue to peek at
 */
static inline struct list_head *queue_peek(const struct queue_head *q)
{
	struct list_head *next = READ_ONCE(q->list.next);

	if (queue_empty(q))
		return NULL;
	return next;
}

/**
 * queue_peek_tail - peek at the tail of an queue_head
 * @q: queue to peek at
 */
static inline struct list_head *queue_peek_tail(const struct queue_head *q)
{
	struct list_head *prev = READ_ONCE(q->list.prev);

	if (prev == &q->list)
		return NULL;
	return prev;
}

/**
 * queue_len - get queue length
 * @q: queue to measure
 *
 * Return the length of a queue.
 */
static inline __u32 queue_len(const struct queue_head *q)
{
	return q->qlen;
}

/**
 * __scm_queue_head_init - initialize non-spinlock portions of queue_head
 * @q: queue to initialize
 */
static inline void __queue_head_init(struct queue_head *q)
{
	INIT_LIST_HEAD(&q->list);
	q->qlen = 0;
}

static inline void queue_head_init(struct queue_head *q)
{
	spin_lock_init(&q->lock);
	__queue_head_init(q);
}

static inline void __queue_insert(struct list_head *new,
				  struct list_head *prev,
				  struct list_head *next,
				  struct queue_head *q)
{
	__list_add(new, prev, next);
	WRITE_ONCE(q->qlen, q->qlen + 1);
}

static inline void __queue_splice(const struct queue_head *q,
				  struct list_head *prev,
				  struct list_head *next)
{
	__list_splice(&q->list, prev, next);
}

/**
 * _queue_splice - join two skb lists, this is designed for stacks
 * @list: the new list to add
 * @head: the place to add it in the first list
 */
static inline void _queue_splice(const struct queue_head *new_q,
				 struct queue_head *q)
{
	if (!queue_empty(new_q)) {
		__queue_splice(new_q, &q->list, q->list.next);
		WRITE_ONCE(q->qlen, q->qlen + new_q->qlen);
	}
}

static inline void queue_splice(const struct queue_head *new_q,
				struct queue_head *q)
{
	unsigned long flags;

	spin_lock_irqsave(&q->lock, flags);
	_queue_splice(new_q, q);
	spin_unlock_irqrestore(&q->lock, flags);
}

static inline void queue_splice_from(struct queue_head *new_q,
				     struct queue_head *q)
{
	unsigned long flags;

	spin_lock_irqsave(&new_q->lock, flags);
	_queue_splice(new_q, q);
	spin_unlock_irqrestore(&new_q->lock, flags);
}

static inline void queue_splice_to(const struct queue_head *new_q,
				   struct queue_head *q)
{
	queue_splice(new_q, q);
}

/**
 * queue_splice_init - join two skb lists and reinitialise the emptied list
 * @list: the new list to add
 * @head: the place to add it in the first list
 *
 * The list at @list is reinitialised
 */
static inline void __queue_splice_init(struct queue_head *new_q,
				       struct queue_head *q)
{
	_queue_splice(new_q, q);
	__queue_head_init(new_q);
}

static inline void queue_splice_init(struct queue_head *new_q,
				     struct queue_head *q)
{
	unsigned long flags;

	spin_lock_irqsave(&q->lock, flags);
	__queue_splice_init(new_q, q);
	spin_unlock_irqrestore(&q->lock, flags);
}

static inline void queue_splice_init_from(struct queue_head *new_q,
					  struct queue_head *q)
{
	unsigned long flags;

	spin_lock_irqsave(&new_q->lock, flags);
	__queue_splice_init(new_q, q);
	spin_unlock_irqrestore(&new_q->lock, flags);
}

static inline void queue_splice_init_to(struct queue_head *new_q,
					struct queue_head *q)
{
	queue_splice_init(new_q, q);
}

/**
 * queue_splice_tail - join two skb lists, each list being a queue
 * @list: the new list to add
 * @head: the place to add it in the first list
 */
static inline void __queue_splice_tail(const struct queue_head *new_q,
				       struct queue_head *q)
{
	if (!queue_empty(new_q)) {
		__queue_splice(new_q, q->list.prev, &q->list);
		WRITE_ONCE(q->qlen, q->qlen + new_q->qlen);
	}
}

static inline void queue_splice_tail(const struct queue_head *new_q,
				     struct queue_head *q)
{
	unsigned long flags;

	spin_lock_irqsave(&q->lock, flags);
	__queue_splice_tail(new_q, q);
	spin_unlock_irqrestore(&q->lock, flags);
}

static inline void queue_splice_tail_from(struct queue_head *new_q,
					  struct queue_head *q)
{
	unsigned long flags;

	spin_lock_irqsave(&new_q->lock, flags);
	__queue_splice_tail(new_q, q);
	spin_unlock_irqrestore(&new_q->lock, flags);
}

static inline void queue_splice_tail_to(const struct queue_head *new_q,
					struct queue_head *q)
{
	queue_splice_tail(new_q, q);
}

/**
 * queue_splice_tail_init - join two skb lists and reinitialise the emptied list
 * @list: the new list to add
 * @head: the place to add it in the first list
 */
static inline void __queue_splice_tail_init(struct queue_head *new_q,
					    struct queue_head *q)
{
	__queue_splice_tail(new_q, q);
	__queue_head_init(new_q);
}

static inline void queue_splice_tail_init(struct queue_head *new_q,
					  struct queue_head *q)
{
	unsigned long flags;

	spin_lock_irqsave(&q->lock, flags);
	__queue_splice_tail_init(new_q, q);
	spin_unlock_irqrestore(&q->lock, flags);
}

static inline void queue_splice_tail_init_from(struct queue_head *new_q,
					       struct queue_head *q)
{
	unsigned long flags;

	spin_lock_irqsave(&new_q->lock, flags);
	__queue_splice_tail_init(new_q, q);
	spin_unlock_irqrestore(&new_q->lock, flags);
}

static inline void queue_splice_tail_init_to(struct queue_head *new_q,
					     struct queue_head *q)
{
	queue_splice_tail_init(new_q, q);
}

/**
 * __queue_after - queue a buffer at the list head
 * @q: list to use
 * @prev: place after this buffer
 * @new: buffer to queue
 */
static inline void __queue_after(struct queue_head *q,
				 struct list_head *prev,
				 struct list_head *new)
{
	__queue_insert(new, prev, prev->next, q);
}

static inline void queue_append(struct list_head *old,
				struct list_head *new,
				struct queue_head *q)
{
	unsigned long flags;

	spin_lock_irqsave(&q->lock, flags);
	__queue_after(q, old, new);
	spin_unlock_irqrestore(&q->lock, flags);
}

static inline void __queue_before(struct queue_head *q,
				  struct list_head *next,
				  struct list_head *new)
{
	__queue_insert(new, next->prev, next, q);
}

/**
 * __queue_head - queue a buffer at the list head
 * @list: list to use
 * @newsk: buffer to queue
 */
static inline void __queue_head(struct queue_head *q,
				struct list_head *new)
{
	__queue_after(q, &q->list, new);
}

static inline void queue_head(struct queue_head *q,
			      struct list_head *new)
{
	unsigned long flags;

	spin_lock_irqsave(&q->lock, flags);
	__queue_head(q, new);
	spin_unlock_irqrestore(&q->lock, flags);
}

static inline void queue_head_nested(struct queue_head *q,
				     struct list_head *new,
				     int subclass)
{
	unsigned long flags;

	spin_lock_irqsave_nested(&q->lock, flags, subclass);
	__queue_head(q, new);
	spin_unlock_irqrestore(&q->lock, flags);
}

/**
 * __queue_tail - queue a buffer at the list tail
 * @list: list to use
 * @newsk: buffer to queue
 */
static inline void __queue_tail(struct queue_head *q,
				struct list_head *new)
{
	__queue_before(q, &q->list, new);
}

static inline void queue_tail(struct queue_head *q,
			      struct list_head *new)
{
	unsigned long flags;

	spin_lock_irqsave(&q->lock, flags);
	__queue_tail(q, new);
	spin_unlock_irqrestore(&q->lock, flags);
}

static inline void __queue_unlink(struct list_head *one, struct queue_head *q)
{
	list_del_init(one);
	WRITE_ONCE(q->qlen, q->qlen - 1);
}

static inline void queue_unlink(struct list_head *one, struct queue_head *q)
{
	unsigned long flags;

	spin_lock_irqsave(&q->lock, flags);
	__queue_unlink(one, q);
	spin_unlock_irqrestore(&q->lock, flags);
}

/**
 * __queue_dequeue - remove from the head of the queue
 * @q: queue to dequeue from.
 */
static inline struct list_head *__queue_dequeue(struct queue_head *q)
{
	struct list_head *one = queue_peek(q);

	if (one)
		__queue_unlink(one, q);
	return one;
}

static inline struct list_head *queue_dequeue(struct queue_head *q)
{
	unsigned long flags;
	struct list_head *one;

	spin_lock_irqsave(&q->lock, flags);
	one = __queue_dequeue(q);
	spin_unlock_irqrestore(&q->lock, flags);
	return one;
}

/**
 * __queue_dequeue - remove from the head of the queue
 * @q: queue to dequeue from.
 */
static inline struct list_head *__queue_dequeue_tail(struct queue_head *q)
{
	struct list_head *one = queue_peek_tail(q);

	if (one)
		__queue_unlink(one, q);
	return one;
}

static inline struct list_head *queue_dequeue_tail(struct queue_head *q)
{
	unsigned long flags;
	struct list_head *one;

	spin_lock_irqsave(&q->lock, flags);
	one = __queue_dequeue_tail(q);
	spin_unlock_irqrestore(&q->lock, flags);
	return one;
}

/**
 * __queue_dequeue_entry - remove from the head of the queue and return one
 * @q:		queue to dequeue from.
 * @type:	the type of your entry.
 * @member:	the name of the queue_head within the struct.
 */
#define __queue_dequeue_entry(q, type, member)	\
({ \
	struct list_head *one = __queue_dequeue(q); \
	one ? list_entry(one, type, member) : NULL; \
})

/**
 * queue_dequeue_entry - remove from the head of the queue and return one
 * lock-protected version of __queue_dequeue_entry
 * @q:		queue to dequeue from.
 * @type:	the type of your entry.
 * @member:	the name of the queue_head within the struct.
 */
#define queue_dequeue_entry(q, type, member)	\
({ \
	struct list_head *one = queue_dequeue(q); \
	one ? list_entry(one, type, member) : NULL; \
})

/**
 * __queue_dequeue_tail_entry - remove from the tail of the queue and return one
 * @q:		queue to dequeue from.
 * @type:	the type of your entry.
 * @member:	the name of the queue_head within the struct.
 */
#define __queue_dequeue_tail_entry(q, type, member)	\
({ \
	struct list_head *one = __queue_dequeue_tail(q); \
	one ? list_entry(one, type, member) : NULL; \
})

/**
 * queue_dequeue_tail_entry - remove from the tail of the queue and return one
 * lock-protected version of __queue_dequeue_tail_entry
 * @q:		queue to dequeue from.
 * @type:	the type of your entry.
 * @member:	the name of the queue_head within the struct.
 */
#define queue_dequeue_tail_entry(q, type, member)	\
({ \
	struct list_head *one = queue_dequeue_tail(q); \
	one ? list_entry(one, type, member) : NULL; \
})

/**
 * queue_dequeue_each_entry - iterate over queue of given type
 * @pos:	the type * to use as a loop cursor.
 * @one:	the list_head of the queued entry
 * @head:	the head for your queue.
 * @member:	the name of the queue_head within the struct.
 */
#define queue_dequeue_each_entry(pos, one, head, member)		\
	while ((one = queue_dequeue(head)) &&				\
	       (pos = list_entry(one, typeof(*pos), member)))

/**
 * list_last_entry_or_null - get the last element from a list
 * @ptr:	the list head to take the element from.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_head within the struct.
 *
 * Note that if the list is empty, it returns NULL.
 */
#define list_last_entry_or_null(ptr, type, member) ({ \
	struct list_head *head__ = (ptr); \
	struct list_head *pos__ = READ_ONCE(head__->prev); \
	pos__ != head__ ? list_entry(pos__, type, member) : NULL; \
})