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