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
38 struct 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 */
INIT_LIST_HEAD(struct list_head * list)54 static 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 */
__list_add(struct list_head * new,struct list_head * prev,struct list_head * next)66 static 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 */
list_add(struct list_head * new,struct list_head * head)84 static 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 */
list_add_tail(struct list_head * new,struct list_head * head)97 static 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 */
__list_del(struct list_head * prev,struct list_head * next)109 static inline void __list_del(struct list_head *prev, struct list_head *next)
110 {
111 next->prev = prev;
112 prev->next = next;
113 }
114
__list_del_entry(struct list_head * entry)115 static 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 */
list_del(struct list_head * entry)126 static 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 */
list_is_head(const struct list_head * list,const struct list_head * head)138 static 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 */
list_empty(const struct list_head * head)147 static 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