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, prev: head, next: 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, prev: head->prev, next: 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(prev: entry->prev, next: 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 */
214

source code of linux/scripts/mod/list.h