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, head, 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, head->prev, 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(entry->prev, 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_move - delete from one list and add as another's head 132 * @list: the entry to move 133 * @head: the head that will precede our entry 134 */ 135 static inline void list_move(struct list_head *list, struct list_head *head) 136 { 137 __list_del_entry(list); 138 list_add(list, head); 139 } 140 141 /** 142 * list_move_tail - delete from one list and add as another's tail 143 * @list: the entry to move 144 * @head: the head that will follow our entry 145 */ 146 static inline void list_move_tail(struct list_head *list, 147 struct list_head *head) 148 { 149 __list_del_entry(list); 150 list_add_tail(list, head); 151 } 152 153 /** 154 * list_is_head - tests whether @list is the list @head 155 * @list: the entry to test 156 * @head: the head of the list 157 */ 158 static inline int list_is_head(const struct list_head *list, const struct list_head *head) 159 { 160 return list == head; 161 } 162 163 /** 164 * list_empty - tests whether a list is empty 165 * @head: the list to test. 166 */ 167 static inline int list_empty(const struct list_head *head) 168 { 169 return head->next == head; 170 } 171 172 /** 173 * list_entry - get the struct for this entry 174 * @ptr: the &struct list_head pointer. 175 * @type: the type of the struct this is embedded in. 176 * @member: the name of the list_head within the struct. 177 */ 178 #define list_entry(ptr, type, member) \ 179 container_of(ptr, type, member) 180 181 /** 182 * list_first_entry - get the first element from a list 183 * @ptr: the list head to take the element from. 184 * @type: the type of the struct this is embedded in. 185 * @member: the name of the list_head within the struct. 186 * 187 * Note, that list is expected to be not empty. 188 */ 189 #define list_first_entry(ptr, type, member) \ 190 list_entry((ptr)->next, type, member) 191 192 /** 193 * list_last_entry - get the last element from a list 194 * @ptr: the list head to take the element from. 195 * @type: the type of the struct this is embedded in. 196 * @member: the name of the list_head within the struct. 197 * 198 * Note, that list is expected to be not empty. 199 */ 200 #define list_last_entry(ptr, type, member) \ 201 list_entry((ptr)->prev, type, member) 202 203 /** 204 * list_next_entry - get the next element in list 205 * @pos: the type * to cursor 206 * @member: the name of the list_head within the struct. 207 */ 208 #define list_next_entry(pos, member) \ 209 list_entry((pos)->member.next, typeof(*(pos)), member) 210 211 /** 212 * list_prev_entry - get the prev element in list 213 * @pos: the type * to cursor 214 * @member: the name of the list_head within the struct. 215 */ 216 #define list_prev_entry(pos, member) \ 217 list_entry((pos)->member.prev, typeof(*(pos)), member) 218 219 /** 220 * list_entry_is_head - test if the entry points to the head of the list 221 * @pos: the type * to cursor 222 * @head: the head for your list. 223 * @member: the name of the list_head within the struct. 224 */ 225 #define list_entry_is_head(pos, head, member) \ 226 (&pos->member == (head)) 227 228 /** 229 * list_for_each_entry - iterate over list of given type 230 * @pos: the type * to use as a loop cursor. 231 * @head: the head for your list. 232 * @member: the name of the list_head within the struct. 233 */ 234 #define list_for_each_entry(pos, head, member) \ 235 for (pos = list_first_entry(head, typeof(*pos), member); \ 236 !list_entry_is_head(pos, head, member); \ 237 pos = list_next_entry(pos, member)) 238 239 /** 240 * list_for_each_entry_reverse - iterate backwards over list of given type. 241 * @pos: the type * to use as a loop cursor. 242 * @head: the head for your list. 243 * @member: the name of the list_head within the struct. 244 */ 245 #define list_for_each_entry_reverse(pos, head, member) \ 246 for (pos = list_last_entry(head, typeof(*pos), member); \ 247 !list_entry_is_head(pos, head, member); \ 248 pos = list_prev_entry(pos, member)) 249 250 /** 251 * list_for_each_entry_safe - iterate over list of given type. Safe against removal of list entry 252 * @pos: the type * to use as a loop cursor. 253 * @n: another type * to use as temporary storage 254 * @head: the head for your list. 255 * @member: the name of the list_head within the struct. 256 */ 257 #define list_for_each_entry_safe(pos, n, head, member) \ 258 for (pos = list_first_entry(head, typeof(*pos), member), \ 259 n = list_next_entry(pos, member); \ 260 !list_entry_is_head(pos, head, member); \ 261 pos = n, n = list_next_entry(n, member)) 262 263 /* 264 * Double linked lists with a single pointer list head. 265 * Mostly useful for hash tables where the two pointer list head is 266 * too wasteful. 267 * You lose the ability to access the tail in O(1). 268 */ 269 270 #define HLIST_HEAD_INIT { .first = NULL } 271 272 /** 273 * hlist_add_head - add a new entry at the beginning of the hlist 274 * @n: new entry to be added 275 * @h: hlist head to add it after 276 * 277 * Insert a new entry after the specified head. 278 * This is good for implementing stacks. 279 */ 280 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) 281 { 282 struct hlist_node *first = h->first; 283 284 n->next = first; 285 if (first) 286 first->pprev = &n->next; 287 h->first = n; 288 n->pprev = &h->first; 289 } 290 291 #define hlist_entry(ptr, type, member) container_of(ptr, type, member) 292 293 #define hlist_entry_safe(ptr, type, member) \ 294 ({ typeof(ptr) ____ptr = (ptr); \ 295 ____ptr ? hlist_entry(____ptr, type, member) : NULL; \ 296 }) 297 298 /** 299 * hlist_for_each_entry - iterate over list of given type 300 * @pos: the type * to use as a loop cursor. 301 * @head: the head for your list. 302 * @member: the name of the hlist_node within the struct. 303 */ 304 #define hlist_for_each_entry(pos, head, member) \ 305 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\ 306 pos; \ 307 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)) 308 309 #endif /* LIST_H */ 310