/* SPDX-License-Identifier: GPL-2.0 */

/** \file list.h Doubly linked list implementation. */

/* Copied from the Linux kernel source tree, version 2.6.13. */

#include <stddef.h> /* offsetof */

/** Get the struct this entry is embedded in. */
#define container_of(ptr, type, member) ({                      \
	const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
	(type *)( (char *)__mptr - offsetof(type,member) );})

/** A list head is just a pair of pointers. */
struct list_head {
	/** Pointer to the next list entry. */
	struct list_head *next;
	/** Pointer to the previous list entry. */
	struct list_head *prev;
};

/** Define an initialized list head. */
#define INITIALIZED_LIST_HEAD(name) struct list_head name = {&(name), &(name)}

/** This must be called before using any other list functions. */
static inline void init_list_head(struct list_head *head)
{
	head->next = head;
	head->prev = head;
}

/**
 * Insert a new entry after the specified head.
 *
 * \param entry The new entry to add.
 * \param head The list head to add it after.
 *
 * This is good for implementing stacks.
 */
static inline void para_list_add(struct list_head *entry, struct list_head *head)
{
	entry->prev = head;
	entry->next = head->next;
	head->next->prev = entry;
	head->next = entry;
}

/**
 * Insert a new entry before the specified head.
 *
 * \param entry The new entry to add.
 * \param head list head to add it before.
 *
 * This is useful for implementing queues.
 */
static inline void list_add_tail(struct list_head *entry, struct list_head *head)
{
	entry->prev = head->prev;
	entry->next = head;
	head->prev->next = entry;
	head->prev = entry;
}

/**
 * Delete an entry from a list.
 *
 * \param entry The element to delete.
 *
 * The list entry is in an undefined state after this and \ref list_empty()
 * does not return true.
 */
static inline void list_del(struct list_head *entry)
{
	entry->prev->next = entry->next;
	entry->next->prev = entry->prev;
	/*
	 * These non-NULL pointers result in page faults when dereferenced.
	 * This helps to catch bugs resulting from using deleted list heads.
	 */
	entry->next = (void *)0x00100100;
	entry->prev = (void *)0x00200200;
}

/**
 * Delete an entry from one list and add it as another list's head.
 *
 * \param entry The entry to move.
 * \param head The head that will precede our entry.
 */
static inline void list_move(struct list_head *entry, struct list_head *head)
{
        list_del(entry);
        para_list_add(entry, head);
}

/**
 * Test whether a list contains no entries.
 *
 * \param head The list to test.
 */
static inline int list_empty(const struct list_head *head)
{
	return head->next == head;
}

/**
 * Test whether a list has just one entry.
 *
 * \param head The list to test.
 */
static inline int list_is_singular(const struct list_head *head)
{
	return !list_empty(head) && (head->next == head->prev);
}

/**
 * Get the struct in which this entry is embedded in.
 *
 * \param ptr The list head pointer.
 * \param type The type of containing structure.
 * \param member The name of the list head member within the structure.
 */
#define list_entry(ptr, type, member) container_of(ptr, type, member)

/**
 * Iterate over a list.
 *
 * \param pos A struct pointer which serves as the iterator.
 * \param head The head of the list.
 * \param member The name of the list head member within the structure.
 */
#define list_for_each_entry(pos, head, member)				\
	for (pos = list_entry((head)->next, typeof(*pos), member);	\
	     &pos->member != (head); 	\
	     pos = list_entry(pos->member.next, typeof(*pos), member))

/**
 * Iterate over list, safe against removal of list entry.
 *
 * \param pos The iterator struct pointer.
 * \param n A second struct pointer which is used as temporary storage.
 * \param head The head of the list.
 * \param member The name of the list head member within the structure.
 */
#define list_for_each_entry_safe(pos, n, head, member)			\
	for (pos = list_entry((head)->next, typeof(*pos), member),	\
		n = list_entry(pos->member.next, typeof(*pos), member);	\
	     &pos->member != (head); 					\
	     pos = n, n = list_entry(n->member.next, typeof(*n), member))

/**
 * Get the first element of a list.
 *
 * \param ptr The list head to take the element from.
 * \param type The type of the struct this is embedded in.
 * \param member The name of the list_struct within the struct.
 *
 * Note that the list is expected to be non-empty.
 */
#define list_first_entry(ptr, type, member) \
	list_entry((ptr)->next, type, member)
#define list_last_entry(ptr, type, member) \
	list_entry((ptr)->prev, type, member)