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 */ 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 */ 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 */ 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 */ 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 */ 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 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 */ 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 */ 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 */ 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