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_replace - replace old entry by new one 132 * @old : the element to be replaced 133 * @new : the new element to insert 134 * 135 * If @old was empty, it will be overwritten. 136 */ 137 static inline void list_replace(struct list_head *old, 138 struct list_head *new) 139 { 140 new->next = old->next; 141 new->next->prev = new; 142 new->prev = old->prev; 143 new->prev->next = new; 144 } 145 146 /** 147 * list_replace_init - replace old entry by new one and initialize the old one 148 * @old : the element to be replaced 149 * @new : the new element to insert 150 * 151 * If @old was empty, it will be overwritten. 152 */ 153 static inline void list_replace_init(struct list_head *old, 154 struct list_head *new) 155 { 156 list_replace(old, new); 157 INIT_LIST_HEAD(old); 158 } 159 160 /** 161 * list_move - delete from one list and add as another's head 162 * @list: the entry to move 163 * @head: the head that will precede our entry 164 */ 165 static inline void list_move(struct list_head *list, struct list_head *head) 166 { 167 __list_del_entry(list); 168 list_add(list, head); 169 } 170 171 /** 172 * list_move_tail - delete from one list and add as another's tail 173 * @list: the entry to move 174 * @head: the head that will follow our entry 175 */ 176 static inline void list_move_tail(struct list_head *list, 177 struct list_head *head) 178 { 179 __list_del_entry(list); 180 list_add_tail(list, head); 181 } 182 183 /** 184 * list_is_first -- tests whether @list is the first entry in list @head 185 * @list: the entry to test 186 * @head: the head of the list 187 */ 188 static inline int list_is_first(const struct list_head *list, const struct list_head *head) 189 { 190 return list->prev == head; 191 } 192 193 /** 194 * list_is_last - tests whether @list is the last entry in list @head 195 * @list: the entry to test 196 * @head: the head of the list 197 */ 198 static inline int list_is_last(const struct list_head *list, const struct list_head *head) 199 { 200 return list->next == head; 201 } 202 203 /** 204 * list_is_head - tests whether @list is the list @head 205 * @list: the entry to test 206 * @head: the head of the list 207 */ 208 static inline int list_is_head(const struct list_head *list, const struct list_head *head) 209 { 210 return list == head; 211 } 212 213 /** 214 * list_empty - tests whether a list is empty 215 * @head: the list to test. 216 */ 217 static inline int list_empty(const struct list_head *head) 218 { 219 return head->next == head; 220 } 221 222 /** 223 * list_entry - get the struct for this entry 224 * @ptr: the &struct list_head pointer. 225 * @type: the type of the struct this is embedded in. 226 * @member: the name of the list_head within the struct. 227 */ 228 #define list_entry(ptr, type, member) \ 229 container_of(ptr, type, member) 230 231 /** 232 * list_first_entry - get the first element from a list 233 * @ptr: the list head to take the element from. 234 * @type: the type of the struct this is embedded in. 235 * @member: the name of the list_head within the struct. 236 * 237 * Note, that list is expected to be not empty. 238 */ 239 #define list_first_entry(ptr, type, member) \ 240 list_entry((ptr)->next, type, member) 241 242 /** 243 * list_last_entry - get the last element from a list 244 * @ptr: the list head to take the element from. 245 * @type: the type of the struct this is embedded in. 246 * @member: the name of the list_head within the struct. 247 * 248 * Note, that list is expected to be not empty. 249 */ 250 #define list_last_entry(ptr, type, member) \ 251 list_entry((ptr)->prev, type, member) 252 253 /** 254 * list_next_entry - get the next element in list 255 * @pos: the type * to cursor 256 * @member: the name of the list_head within the struct. 257 */ 258 #define list_next_entry(pos, member) \ 259 list_entry((pos)->member.next, typeof(*(pos)), member) 260 261 /** 262 * list_prev_entry - get the prev element in list 263 * @pos: the type * to cursor 264 * @member: the name of the list_head within the struct. 265 */ 266 #define list_prev_entry(pos, member) \ 267 list_entry((pos)->member.prev, typeof(*(pos)), member) 268 269 /** 270 * list_entry_is_head - test if the entry points to the head of the list 271 * @pos: the type * to cursor 272 * @head: the head for your list. 273 * @member: the name of the list_head within the struct. 274 */ 275 #define list_entry_is_head(pos, head, member) \ 276 (&pos->member == (head)) 277 278 /** 279 * list_for_each_entry - iterate over list of given type 280 * @pos: the type * to use as a loop cursor. 281 * @head: the head for your list. 282 * @member: the name of the list_head within the struct. 283 */ 284 #define list_for_each_entry(pos, head, member) \ 285 for (pos = list_first_entry(head, typeof(*pos), member); \ 286 !list_entry_is_head(pos, head, member); \ 287 pos = list_next_entry(pos, member)) 288 289 /** 290 * list_for_each_entry_reverse - iterate backwards over list of given type. 291 * @pos: the type * to use as a loop cursor. 292 * @head: the head for your list. 293 * @member: the name of the list_head within the struct. 294 */ 295 #define list_for_each_entry_reverse(pos, head, member) \ 296 for (pos = list_last_entry(head, typeof(*pos), member); \ 297 !list_entry_is_head(pos, head, member); \ 298 pos = list_prev_entry(pos, member)) 299 300 /** 301 * list_for_each_entry_safe - iterate over list of given type. Safe against removal of list entry 302 * @pos: the type * to use as a loop cursor. 303 * @n: another type * to use as temporary storage 304 * @head: the head for your list. 305 * @member: the name of the list_head within the struct. 306 */ 307 #define list_for_each_entry_safe(pos, n, head, member) \ 308 for (pos = list_first_entry(head, typeof(*pos), member), \ 309 n = list_next_entry(pos, member); \ 310 !list_entry_is_head(pos, head, member); \ 311 pos = n, n = list_next_entry(n, member)) 312 313 /* 314 * Double linked lists with a single pointer list head. 315 * Mostly useful for hash tables where the two pointer list head is 316 * too wasteful. 317 * You lose the ability to access the tail in O(1). 318 */ 319 320 #define HLIST_HEAD_INIT { .first = NULL } 321 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) 322 static inline void INIT_HLIST_NODE(struct hlist_node *h) 323 { 324 h->next = NULL; 325 h->pprev = NULL; 326 } 327 328 /** 329 * hlist_unhashed - Has node been removed from list and reinitialized? 330 * @h: Node to be checked 331 * 332 * Not that not all removal functions will leave a node in unhashed 333 * state. For example, hlist_nulls_del_init_rcu() does leave the 334 * node in unhashed state, but hlist_nulls_del() does not. 335 */ 336 static inline int hlist_unhashed(const struct hlist_node *h) 337 { 338 return !h->pprev; 339 } 340 341 static inline void __hlist_del(struct hlist_node *n) 342 { 343 struct hlist_node *next = n->next; 344 struct hlist_node **pprev = n->pprev; 345 346 *pprev = next; 347 if (next) 348 next->pprev = pprev; 349 } 350 351 /** 352 * hlist_del - Delete the specified hlist_node from its list 353 * @n: Node to delete. 354 * 355 * Note that this function leaves the node in hashed state. Use 356 * hlist_del_init() or similar instead to unhash @n. 357 */ 358 static inline void hlist_del(struct hlist_node *n) 359 { 360 __hlist_del(n); 361 n->next = LIST_POISON1; 362 n->pprev = LIST_POISON2; 363 } 364 365 /** 366 * hlist_del_init - Delete the specified hlist_node from its list and initialize 367 * @n: Node to delete. 368 * 369 * Note that this function leaves the node in unhashed state. 370 */ 371 static inline void hlist_del_init(struct hlist_node *n) 372 { 373 if (!hlist_unhashed(n)) { 374 __hlist_del(n); 375 INIT_HLIST_NODE(n); 376 } 377 } 378 379 /** 380 * hlist_add_head - add a new entry at the beginning of the hlist 381 * @n: new entry to be added 382 * @h: hlist head to add it after 383 * 384 * Insert a new entry after the specified head. 385 * This is good for implementing stacks. 386 */ 387 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) 388 { 389 struct hlist_node *first = h->first; 390 391 n->next = first; 392 if (first) 393 first->pprev = &n->next; 394 h->first = n; 395 n->pprev = &h->first; 396 } 397 398 #define hlist_entry(ptr, type, member) container_of(ptr, type, member) 399 400 #define hlist_entry_safe(ptr, type, member) \ 401 ({ typeof(ptr) ____ptr = (ptr); \ 402 ____ptr ? hlist_entry(____ptr, type, member) : NULL; \ 403 }) 404 405 /** 406 * hlist_for_each_entry - iterate over list of given type 407 * @pos: the type * to use as a loop cursor. 408 * @head: the head for your list. 409 * @member: the name of the hlist_node within the struct. 410 */ 411 #define hlist_for_each_entry(pos, head, member) \ 412 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\ 413 pos; \ 414 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)) 415 416 /** 417 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry 418 * @pos: the type * to use as a loop cursor. 419 * @n: a &struct hlist_node to use as temporary storage 420 * @head: the head for your list. 421 * @member: the name of the hlist_node within the struct. 422 */ 423 #define hlist_for_each_entry_safe(pos, n, head, member) \ 424 for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\ 425 pos && ({ n = pos->member.next; 1; }); \ 426 pos = hlist_entry_safe(n, typeof(*pos), member)) 427 428 #endif /* LIST_H */ 429