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