1/* SPDX-License-Identifier: GPL-2.0 */
  2#ifndef LIST_H
  3#define LIST_H
  4
  5#include <stdbool.h>
  6#include <stddef.h>
  7
  8/* Are two types/vars the same type (ignoring qualifiers)? */
  9#define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
 10
 11/**
 12 * container_of - cast a member of a structure out to the containing structure
 13 * @ptr:	the pointer to the member.
 14 * @type:	the type of the container struct this is embedded in.
 15 * @member:	the name of the member within the struct.
 16 *
 17 */
 18#define container_of(ptr, type, member) ({				\
 19	void *__mptr = (void *)(ptr);					\
 20	_Static_assert(__same_type(*(ptr), ((type *)0)->member) ||	\
 21		      __same_type(*(ptr), void),			\
 22		      "pointer type mismatch in container_of()");	\
 23	((type *)(__mptr - offsetof(type, member))); })
 24
 25#define LIST_POISON1  ((void *) 0x100)
 26#define LIST_POISON2  ((void *) 0x122)
 27
 28/*
 29 * Circular doubly linked list implementation.
 30 *
 31 * Some of the internal functions ("__xxx") are useful when
 32 * manipulating whole lists rather than single entries, as
 33 * sometimes we already know the next/prev entries and we can
 34 * generate better code by using them directly rather than
 35 * using the generic single-entry routines.
 36 */
 37
 38struct list_head {
 39	struct list_head *next, *prev;
 40};
 41
 42#define LIST_HEAD_INIT(name) { &(name), &(name) }
 43
 44#define LIST_HEAD(name) \
 45	struct list_head name = LIST_HEAD_INIT(name)
 46
 47/**
 48 * INIT_LIST_HEAD - Initialize a list_head structure
 49 * @list: list_head structure to be initialized.
 50 *
 51 * Initializes the list_head to point to itself.  If it is a list header,
 52 * the result is an empty list.
 53 */
 54static inline void INIT_LIST_HEAD(struct list_head *list)
 55{
 56	list->next = list;
 57	list->prev = list;
 58}
 59
 60/*
 61 * Insert a new entry between two known consecutive entries.
 62 *
 63 * This is only for internal list manipulation where we know
 64 * the prev/next entries already!
 65 */
 66static inline void __list_add(struct list_head *new,
 67			      struct list_head *prev,
 68			      struct list_head *next)
 69{
 70	next->prev = new;
 71	new->next = next;
 72	new->prev = prev;
 73	prev->next = new;
 74}
 75
 76/**
 77 * list_add - add a new entry
 78 * @new: new entry to be added
 79 * @head: list head to add it after
 80 *
 81 * Insert a new entry after the specified head.
 82 * This is good for implementing stacks.
 83 */
 84static inline void list_add(struct list_head *new, struct list_head *head)
 85{
 86	__list_add(new, head, head->next);
 87}
 88
 89/**
 90 * list_add_tail - add a new entry
 91 * @new: new entry to be added
 92 * @head: list head to add it before
 93 *
 94 * Insert a new entry before the specified head.
 95 * This is useful for implementing queues.
 96 */
 97static inline void list_add_tail(struct list_head *new, struct list_head *head)
 98{
 99	__list_add(new, head->prev, head);
100}
101
102/*
103 * Delete a list entry by making the prev/next entries
104 * point to each other.
105 *
106 * This is only for internal list manipulation where we know
107 * the prev/next entries already!
108 */
109static inline void __list_del(struct list_head *prev, struct list_head *next)
110{
111	next->prev = prev;
112	prev->next = next;
113}
114
115static inline void __list_del_entry(struct list_head *entry)
116{
117	__list_del(entry->prev, entry->next);
118}
119
120/**
121 * list_del - deletes entry from list.
122 * @entry: the element to delete from the list.
123 * Note: list_empty() on entry does not return true after this, the entry is
124 * in an undefined state.
125 */
126static inline void list_del(struct list_head *entry)
127{
128	__list_del_entry(entry);
129	entry->next = LIST_POISON1;
130	entry->prev = LIST_POISON2;
131}
132
133/**
134 * list_is_head - tests whether @list is the list @head
135 * @list: the entry to test
136 * @head: the head of the list
137 */
138static inline int list_is_head(const struct list_head *list, const struct list_head *head)
139{
140	return list == head;
141}
142
143/**
144 * list_empty - tests whether a list is empty
145 * @head: the list to test.
146 */
147static inline int list_empty(const struct list_head *head)
148{
149	return head->next == head;
150}
151
152/**
153 * list_entry - get the struct for this entry
154 * @ptr:	the &struct list_head pointer.
155 * @type:	the type of the struct this is embedded in.
156 * @member:	the name of the list_head within the struct.
157 */
158#define list_entry(ptr, type, member) \
159	container_of(ptr, type, member)
160
161/**
162 * list_first_entry - get the first element from a list
163 * @ptr:	the list head to take the element from.
164 * @type:	the type of the struct this is embedded in.
165 * @member:	the name of the list_head within the struct.
166 *
167 * Note, that list is expected to be not empty.
168 */
169#define list_first_entry(ptr, type, member) \
170	list_entry((ptr)->next, type, member)
171
172/**
173 * list_next_entry - get the next element in list
174 * @pos:	the type * to cursor
175 * @member:	the name of the list_head within the struct.
176 */
177#define list_next_entry(pos, member) \
178	list_entry((pos)->member.next, typeof(*(pos)), member)
179
180/**
181 * list_entry_is_head - test if the entry points to the head of the list
182 * @pos:	the type * to cursor
183 * @head:	the head for your list.
184 * @member:	the name of the list_head within the struct.
185 */
186#define list_entry_is_head(pos, head, member)				\
187	(&pos->member == (head))
188
189/**
190 * list_for_each_entry - iterate over list of given type
191 * @pos:	the type * to use as a loop cursor.
192 * @head:	the head for your list.
193 * @member:	the name of the list_head within the struct.
194 */
195#define list_for_each_entry(pos, head, member)				\
196	for (pos = list_first_entry(head, typeof(*pos), member);	\
197	     !list_entry_is_head(pos, head, member);			\
198	     pos = list_next_entry(pos, member))
199
200/**
201 * list_for_each_entry_safe - iterate over list of given type. Safe against removal of list entry
202 * @pos:	the type * to use as a loop cursor.
203 * @n:		another type * to use as temporary storage
204 * @head:	the head for your list.
205 * @member:	the name of the list_head within the struct.
206 */
207#define list_for_each_entry_safe(pos, n, head, member)			\
208	for (pos = list_first_entry(head, typeof(*pos), member),	\
209		n = list_next_entry(pos, member);			\
210	     !list_entry_is_head(pos, head, member);			\
211	     pos = n, n = list_next_entry(n, member))
212
213#endif /* LIST_H */