1 /* SPDX-License-Identifier: GPL-2.0 */ 2 #ifndef _LINUX_LIST_H 3 #define _LINUX_LIST_H 4 5 #include <linux/types.h> 6 #include <linux/stddef.h> 7 #include <linux/poison.h> 8 #include <linux/const.h> 9 #include <linux/kernel.h> 10 11 /* 12 * Simple doubly linked list implementation. 13 * 14 * Some of the internal functions ("__xxx") are useful when 15 * manipulating whole lists rather than single entries, as 16 * sometimes we already know the next/prev entries and we can 17 * generate better code by using them directly rather than 18 * using the generic single-entry routines. 19 */ 20 21 #define LIST_HEAD_INIT(name) { &(name), &(name) } 22 23 #define LIST_HEAD(name) \ 24 struct list_head name = LIST_HEAD_INIT(name) 25 26 static inline void INIT_LIST_HEAD(struct list_head *list) 27 { 28 WRITE_ONCE(list->next, list); 29 list->prev = list; 30 } 31 32 #ifdef CONFIG_DEBUG_LIST 33 extern bool __list_add_valid(struct list_head *new, 34 struct list_head *prev, 35 struct list_head *next); 36 extern bool __list_del_entry_valid(struct list_head *entry); 37 #else 38 static inline bool __list_add_valid(struct list_head *new, 39 struct list_head *prev, 40 struct list_head *next) 41 { 42 return true; 43 } 44 static inline bool __list_del_entry_valid(struct list_head *entry) 45 { 46 return true; 47 } 48 #endif 49 50 /* 51 * Insert a new entry between two known consecutive entries. 52 * 53 * This is only for internal list manipulation where we know 54 * the prev/next entries already! 55 */ 56 static inline void __list_add(struct list_head *new, 57 struct list_head *prev, 58 struct list_head *next) 59 { 60 if (!__list_add_valid(new, prev, next)) 61 return; 62 63 next->prev = new; 64 new->next = next; 65 new->prev = prev; 66 WRITE_ONCE(prev->next, new); 67 } 68 69 /** 70 * list_add - add a new entry 71 * @new: new entry to be added 72 * @head: list head to add it after 73 * 74 * Insert a new entry after the specified head. 75 * This is good for implementing stacks. 76 */ 77 static inline void list_add(struct list_head *new, struct list_head *head) 78 { 79 __list_add(new, head, head->next); 80 } 81 82 83 /** 84 * list_add_tail - add a new entry 85 * @new: new entry to be added 86 * @head: list head to add it before 87 * 88 * Insert a new entry before the specified head. 89 * This is useful for implementing queues. 90 */ 91 static inline void list_add_tail(struct list_head *new, struct list_head *head) 92 { 93 __list_add(new, head->prev, head); 94 } 95 96 /* 97 * Delete a list entry by making the prev/next entries 98 * point to each other. 99 * 100 * This is only for internal list manipulation where we know 101 * the prev/next entries already! 102 */ 103 static inline void __list_del(struct list_head * prev, struct list_head * next) 104 { 105 next->prev = prev; 106 WRITE_ONCE(prev->next, next); 107 } 108 109 /* 110 * Delete a list entry and clear the 'prev' pointer. 111 * 112 * This is a special-purpose list clearing method used in the networking code 113 * for lists allocated as per-cpu, where we don't want to incur the extra 114 * WRITE_ONCE() overhead of a regular list_del_init(). The code that uses this 115 * needs to check the node 'prev' pointer instead of calling list_empty(). 116 */ 117 static inline void __list_del_clearprev(struct list_head *entry) 118 { 119 __list_del(entry->prev, entry->next); 120 entry->prev = NULL; 121 } 122 123 /** 124 * list_del - deletes entry from list. 125 * @entry: the element to delete from the list. 126 * Note: list_empty() on entry does not return true after this, the entry is 127 * in an undefined state. 128 */ 129 static inline void __list_del_entry(struct list_head *entry) 130 { 131 if (!__list_del_entry_valid(entry)) 132 return; 133 134 __list_del(entry->prev, entry->next); 135 } 136 137 static inline void list_del(struct list_head *entry) 138 { 139 __list_del_entry(entry); 140 entry->next = LIST_POISON1; 141 entry->prev = LIST_POISON2; 142 } 143 144 /** 145 * list_replace - replace old entry by new one 146 * @old : the element to be replaced 147 * @new : the new element to insert 148 * 149 * If @old was empty, it will be overwritten. 150 */ 151 static inline void list_replace(struct list_head *old, 152 struct list_head *new) 153 { 154 new->next = old->next; 155 new->next->prev = new; 156 new->prev = old->prev; 157 new->prev->next = new; 158 } 159 160 static inline void list_replace_init(struct list_head *old, 161 struct list_head *new) 162 { 163 list_replace(old, new); 164 INIT_LIST_HEAD(old); 165 } 166 167 /** 168 * list_swap - replace entry1 with entry2 and re-add entry1 at entry2's position 169 * @entry1: the location to place entry2 170 * @entry2: the location to place entry1 171 */ 172 static inline void list_swap(struct list_head *entry1, 173 struct list_head *entry2) 174 { 175 struct list_head *pos = entry2->prev; 176 177 list_del(entry2); 178 list_replace(entry1, entry2); 179 if (pos == entry1) 180 pos = entry2; 181 list_add(entry1, pos); 182 } 183 184 /** 185 * list_del_init - deletes entry from list and reinitialize it. 186 * @entry: the element to delete from the list. 187 */ 188 static inline void list_del_init(struct list_head *entry) 189 { 190 __list_del_entry(entry); 191 INIT_LIST_HEAD(entry); 192 } 193 194 /** 195 * list_move - delete from one list and add as another's head 196 * @list: the entry to move 197 * @head: the head that will precede our entry 198 */ 199 static inline void list_move(struct list_head *list, struct list_head *head) 200 { 201 __list_del_entry(list); 202 list_add(list, head); 203 } 204 205 /** 206 * list_move_tail - delete from one list and add as another's tail 207 * @list: the entry to move 208 * @head: the head that will follow our entry 209 */ 210 static inline void list_move_tail(struct list_head *list, 211 struct list_head *head) 212 { 213 __list_del_entry(list); 214 list_add_tail(list, head); 215 } 216 217 /** 218 * list_bulk_move_tail - move a subsection of a list to its tail 219 * @head: the head that will follow our entry 220 * @first: first entry to move 221 * @last: last entry to move, can be the same as first 222 * 223 * Move all entries between @first and including @last before @head. 224 * All three entries must belong to the same linked list. 225 */ 226 static inline void list_bulk_move_tail(struct list_head *head, 227 struct list_head *first, 228 struct list_head *last) 229 { 230 first->prev->next = last->next; 231 last->next->prev = first->prev; 232 233 head->prev->next = first; 234 first->prev = head->prev; 235 236 last->next = head; 237 head->prev = last; 238 } 239 240 /** 241 * list_is_first -- tests whether @list is the first entry in list @head 242 * @list: the entry to test 243 * @head: the head of the list 244 */ 245 static inline int list_is_first(const struct list_head *list, 246 const struct list_head *head) 247 { 248 return list->prev == head; 249 } 250 251 /** 252 * list_is_last - tests whether @list is the last entry in list @head 253 * @list: the entry to test 254 * @head: the head of the list 255 */ 256 static inline int list_is_last(const struct list_head *list, 257 const struct list_head *head) 258 { 259 return list->next == head; 260 } 261 262 /** 263 * list_empty - tests whether a list is empty 264 * @head: the list to test. 265 */ 266 static inline int list_empty(const struct list_head *head) 267 { 268 return READ_ONCE(head->next) == head; 269 } 270 271 /** 272 * list_empty_careful - tests whether a list is empty and not being modified 273 * @head: the list to test 274 * 275 * Description: 276 * tests whether a list is empty _and_ checks that no other CPU might be 277 * in the process of modifying either member (next or prev) 278 * 279 * NOTE: using list_empty_careful() without synchronization 280 * can only be safe if the only activity that can happen 281 * to the list entry is list_del_init(). Eg. it cannot be used 282 * if another CPU could re-list_add() it. 283 */ 284 static inline int list_empty_careful(const struct list_head *head) 285 { 286 struct list_head *next = head->next; 287 return (next == head) && (next == head->prev); 288 } 289 290 /** 291 * list_rotate_left - rotate the list to the left 292 * @head: the head of the list 293 */ 294 static inline void list_rotate_left(struct list_head *head) 295 { 296 struct list_head *first; 297 298 if (!list_empty(head)) { 299 first = head->next; 300 list_move_tail(first, head); 301 } 302 } 303 304 /** 305 * list_rotate_to_front() - Rotate list to specific item. 306 * @list: The desired new front of the list. 307 * @head: The head of the list. 308 * 309 * Rotates list so that @list becomes the new front of the list. 310 */ 311 static inline void list_rotate_to_front(struct list_head *list, 312 struct list_head *head) 313 { 314 /* 315 * Deletes the list head from the list denoted by @head and 316 * places it as the tail of @list, this effectively rotates the 317 * list so that @list is at the front. 318 */ 319 list_move_tail(head, list); 320 } 321 322 /** 323 * list_is_singular - tests whether a list has just one entry. 324 * @head: the list to test. 325 */ 326 static inline int list_is_singular(const struct list_head *head) 327 { 328 return !list_empty(head) && (head->next == head->prev); 329 } 330 331 static inline void __list_cut_position(struct list_head *list, 332 struct list_head *head, struct list_head *entry) 333 { 334 struct list_head *new_first = entry->next; 335 list->next = head->next; 336 list->next->prev = list; 337 list->prev = entry; 338 entry->next = list; 339 head->next = new_first; 340 new_first->prev = head; 341 } 342 343 /** 344 * list_cut_position - cut a list into two 345 * @list: a new list to add all removed entries 346 * @head: a list with entries 347 * @entry: an entry within head, could be the head itself 348 * and if so we won't cut the list 349 * 350 * This helper moves the initial part of @head, up to and 351 * including @entry, from @head to @list. You should 352 * pass on @entry an element you know is on @head. @list 353 * should be an empty list or a list you do not care about 354 * losing its data. 355 * 356 */ 357 static inline void list_cut_position(struct list_head *list, 358 struct list_head *head, struct list_head *entry) 359 { 360 if (list_empty(head)) 361 return; 362 if (list_is_singular(head) && 363 (head->next != entry && head != entry)) 364 return; 365 if (entry == head) 366 INIT_LIST_HEAD(list); 367 else 368 __list_cut_position(list, head, entry); 369 } 370 371 /** 372 * list_cut_before - cut a list into two, before given entry 373 * @list: a new list to add all removed entries 374 * @head: a list with entries 375 * @entry: an entry within head, could be the head itself 376 * 377 * This helper moves the initial part of @head, up to but 378 * excluding @entry, from @head to @list. You should pass 379 * in @entry an element you know is on @head. @list should 380 * be an empty list or a list you do not care about losing 381 * its data. 382 * If @entry == @head, all entries on @head are moved to 383 * @list. 384 */ 385 static inline void list_cut_before(struct list_head *list, 386 struct list_head *head, 387 struct list_head *entry) 388 { 389 if (head->next == entry) { 390 INIT_LIST_HEAD(list); 391 return; 392 } 393 list->next = head->next; 394 list->next->prev = list; 395 list->prev = entry->prev; 396 list->prev->next = list; 397 head->next = entry; 398 entry->prev = head; 399 } 400 401 static inline void __list_splice(const struct list_head *list, 402 struct list_head *prev, 403 struct list_head *next) 404 { 405 struct list_head *first = list->next; 406 struct list_head *last = list->prev; 407 408 first->prev = prev; 409 prev->next = first; 410 411 last->next = next; 412 next->prev = last; 413 } 414 415 /** 416 * list_splice - join two lists, this is designed for stacks 417 * @list: the new list to add. 418 * @head: the place to add it in the first list. 419 */ 420 static inline void list_splice(const struct list_head *list, 421 struct list_head *head) 422 { 423 if (!list_empty(list)) 424 __list_splice(list, head, head->next); 425 } 426 427 /** 428 * list_splice_tail - join two lists, each list being a queue 429 * @list: the new list to add. 430 * @head: the place to add it in the first list. 431 */ 432 static inline void list_splice_tail(struct list_head *list, 433 struct list_head *head) 434 { 435 if (!list_empty(list)) 436 __list_splice(list, head->prev, head); 437 } 438 439 /** 440 * list_splice_init - join two lists and reinitialise the emptied list. 441 * @list: the new list to add. 442 * @head: the place to add it in the first list. 443 * 444 * The list at @list is reinitialised 445 */ 446 static inline void list_splice_init(struct list_head *list, 447 struct list_head *head) 448 { 449 if (!list_empty(list)) { 450 __list_splice(list, head, head->next); 451 INIT_LIST_HEAD(list); 452 } 453 } 454 455 /** 456 * list_splice_tail_init - join two lists and reinitialise the emptied list 457 * @list: the new list to add. 458 * @head: the place to add it in the first list. 459 * 460 * Each of the lists is a queue. 461 * The list at @list is reinitialised 462 */ 463 static inline void list_splice_tail_init(struct list_head *list, 464 struct list_head *head) 465 { 466 if (!list_empty(list)) { 467 __list_splice(list, head->prev, head); 468 INIT_LIST_HEAD(list); 469 } 470 } 471 472 /** 473 * list_entry - get the struct for this entry 474 * @ptr: the &struct list_head pointer. 475 * @type: the type of the struct this is embedded in. 476 * @member: the name of the list_head within the struct. 477 */ 478 #define list_entry(ptr, type, member) \ 479 container_of(ptr, type, member) 480 481 /** 482 * list_first_entry - get the first element from a list 483 * @ptr: the list head to take the element from. 484 * @type: the type of the struct this is embedded in. 485 * @member: the name of the list_head within the struct. 486 * 487 * Note, that list is expected to be not empty. 488 */ 489 #define list_first_entry(ptr, type, member) \ 490 list_entry((ptr)->next, type, member) 491 492 /** 493 * list_last_entry - get the last element from a list 494 * @ptr: the list head to take the element from. 495 * @type: the type of the struct this is embedded in. 496 * @member: the name of the list_head within the struct. 497 * 498 * Note, that list is expected to be not empty. 499 */ 500 #define list_last_entry(ptr, type, member) \ 501 list_entry((ptr)->prev, type, member) 502 503 /** 504 * list_first_entry_or_null - get the first element from a list 505 * @ptr: the list head to take the element from. 506 * @type: the type of the struct this is embedded in. 507 * @member: the name of the list_head within the struct. 508 * 509 * Note that if the list is empty, it returns NULL. 510 */ 511 #define list_first_entry_or_null(ptr, type, member) ({ \ 512 struct list_head *head__ = (ptr); \ 513 struct list_head *pos__ = READ_ONCE(head__->next); \ 514 pos__ != head__ ? list_entry(pos__, type, member) : NULL; \ 515 }) 516 517 /** 518 * list_next_entry - get the next element in list 519 * @pos: the type * to cursor 520 * @member: the name of the list_head within the struct. 521 */ 522 #define list_next_entry(pos, member) \ 523 list_entry((pos)->member.next, typeof(*(pos)), member) 524 525 /** 526 * list_prev_entry - get the prev element in list 527 * @pos: the type * to cursor 528 * @member: the name of the list_head within the struct. 529 */ 530 #define list_prev_entry(pos, member) \ 531 list_entry((pos)->member.prev, typeof(*(pos)), member) 532 533 /** 534 * list_for_each - iterate over a list 535 * @pos: the &struct list_head to use as a loop cursor. 536 * @head: the head for your list. 537 */ 538 #define list_for_each(pos, head) \ 539 for (pos = (head)->next; pos != (head); pos = pos->next) 540 541 /** 542 * list_for_each_prev - iterate over a list backwards 543 * @pos: the &struct list_head to use as a loop cursor. 544 * @head: the head for your list. 545 */ 546 #define list_for_each_prev(pos, head) \ 547 for (pos = (head)->prev; pos != (head); pos = pos->prev) 548 549 /** 550 * list_for_each_safe - iterate over a list safe against removal of list entry 551 * @pos: the &struct list_head to use as a loop cursor. 552 * @n: another &struct list_head to use as temporary storage 553 * @head: the head for your list. 554 */ 555 #define list_for_each_safe(pos, n, head) \ 556 for (pos = (head)->next, n = pos->next; pos != (head); \ 557 pos = n, n = pos->next) 558 559 /** 560 * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry 561 * @pos: the &struct list_head to use as a loop cursor. 562 * @n: another &struct list_head to use as temporary storage 563 * @head: the head for your list. 564 */ 565 #define list_for_each_prev_safe(pos, n, head) \ 566 for (pos = (head)->prev, n = pos->prev; \ 567 pos != (head); \ 568 pos = n, n = pos->prev) 569 570 /** 571 * list_for_each_entry - iterate over list of given type 572 * @pos: the type * to use as a loop cursor. 573 * @head: the head for your list. 574 * @member: the name of the list_head within the struct. 575 */ 576 #define list_for_each_entry(pos, head, member) \ 577 for (pos = list_first_entry(head, typeof(*pos), member); \ 578 &pos->member != (head); \ 579 pos = list_next_entry(pos, member)) 580 581 /** 582 * list_for_each_entry_reverse - iterate backwards over list of given type. 583 * @pos: the type * to use as a loop cursor. 584 * @head: the head for your list. 585 * @member: the name of the list_head within the struct. 586 */ 587 #define list_for_each_entry_reverse(pos, head, member) \ 588 for (pos = list_last_entry(head, typeof(*pos), member); \ 589 &pos->member != (head); \ 590 pos = list_prev_entry(pos, member)) 591 592 /** 593 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue() 594 * @pos: the type * to use as a start point 595 * @head: the head of the list 596 * @member: the name of the list_head within the struct. 597 * 598 * Prepares a pos entry for use as a start point in list_for_each_entry_continue(). 599 */ 600 #define list_prepare_entry(pos, head, member) \ 601 ((pos) ? : list_entry(head, typeof(*pos), member)) 602 603 /** 604 * list_for_each_entry_continue - continue iteration over list of given type 605 * @pos: the type * to use as a loop cursor. 606 * @head: the head for your list. 607 * @member: the name of the list_head within the struct. 608 * 609 * Continue to iterate over list of given type, continuing after 610 * the current position. 611 */ 612 #define list_for_each_entry_continue(pos, head, member) \ 613 for (pos = list_next_entry(pos, member); \ 614 &pos->member != (head); \ 615 pos = list_next_entry(pos, member)) 616 617 /** 618 * list_for_each_entry_continue_reverse - iterate backwards from the given point 619 * @pos: the type * to use as a loop cursor. 620 * @head: the head for your list. 621 * @member: the name of the list_head within the struct. 622 * 623 * Start to iterate over list of given type backwards, continuing after 624 * the current position. 625 */ 626 #define list_for_each_entry_continue_reverse(pos, head, member) \ 627 for (pos = list_prev_entry(pos, member); \ 628 &pos->member != (head); \ 629 pos = list_prev_entry(pos, member)) 630 631 /** 632 * list_for_each_entry_from - iterate over list of given type from the current point 633 * @pos: the type * to use as a loop cursor. 634 * @head: the head for your list. 635 * @member: the name of the list_head within the struct. 636 * 637 * Iterate over list of given type, continuing from current position. 638 */ 639 #define list_for_each_entry_from(pos, head, member) \ 640 for (; &pos->member != (head); \ 641 pos = list_next_entry(pos, member)) 642 643 /** 644 * list_for_each_entry_from_reverse - iterate backwards over list of given type 645 * from the current point 646 * @pos: the type * to use as a loop cursor. 647 * @head: the head for your list. 648 * @member: the name of the list_head within the struct. 649 * 650 * Iterate backwards over list of given type, continuing from current position. 651 */ 652 #define list_for_each_entry_from_reverse(pos, head, member) \ 653 for (; &pos->member != (head); \ 654 pos = list_prev_entry(pos, member)) 655 656 /** 657 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry 658 * @pos: the type * to use as a loop cursor. 659 * @n: another type * to use as temporary storage 660 * @head: the head for your list. 661 * @member: the name of the list_head within the struct. 662 */ 663 #define list_for_each_entry_safe(pos, n, head, member) \ 664 for (pos = list_first_entry(head, typeof(*pos), member), \ 665 n = list_next_entry(pos, member); \ 666 &pos->member != (head); \ 667 pos = n, n = list_next_entry(n, member)) 668 669 /** 670 * list_for_each_entry_safe_continue - continue list iteration safe against removal 671 * @pos: the type * to use as a loop cursor. 672 * @n: another type * to use as temporary storage 673 * @head: the head for your list. 674 * @member: the name of the list_head within the struct. 675 * 676 * Iterate over list of given type, continuing after current point, 677 * safe against removal of list entry. 678 */ 679 #define list_for_each_entry_safe_continue(pos, n, head, member) \ 680 for (pos = list_next_entry(pos, member), \ 681 n = list_next_entry(pos, member); \ 682 &pos->member != (head); \ 683 pos = n, n = list_next_entry(n, member)) 684 685 /** 686 * list_for_each_entry_safe_from - iterate over list from current point safe against removal 687 * @pos: the type * to use as a loop cursor. 688 * @n: another type * to use as temporary storage 689 * @head: the head for your list. 690 * @member: the name of the list_head within the struct. 691 * 692 * Iterate over list of given type from current point, safe against 693 * removal of list entry. 694 */ 695 #define list_for_each_entry_safe_from(pos, n, head, member) \ 696 for (n = list_next_entry(pos, member); \ 697 &pos->member != (head); \ 698 pos = n, n = list_next_entry(n, member)) 699 700 /** 701 * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal 702 * @pos: the type * to use as a loop cursor. 703 * @n: another type * to use as temporary storage 704 * @head: the head for your list. 705 * @member: the name of the list_head within the struct. 706 * 707 * Iterate backwards over list of given type, safe against removal 708 * of list entry. 709 */ 710 #define list_for_each_entry_safe_reverse(pos, n, head, member) \ 711 for (pos = list_last_entry(head, typeof(*pos), member), \ 712 n = list_prev_entry(pos, member); \ 713 &pos->member != (head); \ 714 pos = n, n = list_prev_entry(n, member)) 715 716 /** 717 * list_safe_reset_next - reset a stale list_for_each_entry_safe loop 718 * @pos: the loop cursor used in the list_for_each_entry_safe loop 719 * @n: temporary storage used in list_for_each_entry_safe 720 * @member: the name of the list_head within the struct. 721 * 722 * list_safe_reset_next is not safe to use in general if the list may be 723 * modified concurrently (eg. the lock is dropped in the loop body). An 724 * exception to this is if the cursor element (pos) is pinned in the list, 725 * and list_safe_reset_next is called after re-taking the lock and before 726 * completing the current iteration of the loop body. 727 */ 728 #define list_safe_reset_next(pos, n, member) \ 729 n = list_next_entry(pos, member) 730 731 /* 732 * Double linked lists with a single pointer list head. 733 * Mostly useful for hash tables where the two pointer list head is 734 * too wasteful. 735 * You lose the ability to access the tail in O(1). 736 */ 737 738 #define HLIST_HEAD_INIT { .first = NULL } 739 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL } 740 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) 741 static inline void INIT_HLIST_NODE(struct hlist_node *h) 742 { 743 h->next = NULL; 744 h->pprev = NULL; 745 } 746 747 static inline int hlist_unhashed(const struct hlist_node *h) 748 { 749 return !h->pprev; 750 } 751 752 static inline int hlist_empty(const struct hlist_head *h) 753 { 754 return !READ_ONCE(h->first); 755 } 756 757 static inline void __hlist_del(struct hlist_node *n) 758 { 759 struct hlist_node *next = n->next; 760 struct hlist_node **pprev = n->pprev; 761 762 WRITE_ONCE(*pprev, next); 763 if (next) 764 next->pprev = pprev; 765 } 766 767 static inline void hlist_del(struct hlist_node *n) 768 { 769 __hlist_del(n); 770 n->next = LIST_POISON1; 771 n->pprev = LIST_POISON2; 772 } 773 774 static inline void hlist_del_init(struct hlist_node *n) 775 { 776 if (!hlist_unhashed(n)) { 777 __hlist_del(n); 778 INIT_HLIST_NODE(n); 779 } 780 } 781 782 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) 783 { 784 struct hlist_node *first = h->first; 785 n->next = first; 786 if (first) 787 first->pprev = &n->next; 788 WRITE_ONCE(h->first, n); 789 n->pprev = &h->first; 790 } 791 792 /* next must be != NULL */ 793 static inline void hlist_add_before(struct hlist_node *n, 794 struct hlist_node *next) 795 { 796 n->pprev = next->pprev; 797 n->next = next; 798 next->pprev = &n->next; 799 WRITE_ONCE(*(n->pprev), n); 800 } 801 802 static inline void hlist_add_behind(struct hlist_node *n, 803 struct hlist_node *prev) 804 { 805 n->next = prev->next; 806 prev->next = n; 807 n->pprev = &prev->next; 808 809 if (n->next) 810 n->next->pprev = &n->next; 811 } 812 813 /* after that we'll appear to be on some hlist and hlist_del will work */ 814 static inline void hlist_add_fake(struct hlist_node *n) 815 { 816 n->pprev = &n->next; 817 } 818 819 static inline bool hlist_fake(struct hlist_node *h) 820 { 821 return h->pprev == &h->next; 822 } 823 824 /* 825 * Check whether the node is the only node of the head without 826 * accessing head: 827 */ 828 static inline bool 829 hlist_is_singular_node(struct hlist_node *n, struct hlist_head *h) 830 { 831 return !n->next && n->pprev == &h->first; 832 } 833 834 /* 835 * Move a list from one list head to another. Fixup the pprev 836 * reference of the first entry if it exists. 837 */ 838 static inline void hlist_move_list(struct hlist_head *old, 839 struct hlist_head *new) 840 { 841 new->first = old->first; 842 if (new->first) 843 new->first->pprev = &new->first; 844 old->first = NULL; 845 } 846 847 #define hlist_entry(ptr, type, member) container_of(ptr,type,member) 848 849 #define hlist_for_each(pos, head) \ 850 for (pos = (head)->first; pos ; pos = pos->next) 851 852 #define hlist_for_each_safe(pos, n, head) \ 853 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \ 854 pos = n) 855 856 #define hlist_entry_safe(ptr, type, member) \ 857 ({ typeof(ptr) ____ptr = (ptr); \ 858 ____ptr ? hlist_entry(____ptr, type, member) : NULL; \ 859 }) 860 861 /** 862 * hlist_for_each_entry - iterate over list of given type 863 * @pos: the type * to use as a loop cursor. 864 * @head: the head for your list. 865 * @member: the name of the hlist_node within the struct. 866 */ 867 #define hlist_for_each_entry(pos, head, member) \ 868 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\ 869 pos; \ 870 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)) 871 872 /** 873 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point 874 * @pos: the type * to use as a loop cursor. 875 * @member: the name of the hlist_node within the struct. 876 */ 877 #define hlist_for_each_entry_continue(pos, member) \ 878 for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\ 879 pos; \ 880 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)) 881 882 /** 883 * hlist_for_each_entry_from - iterate over a hlist continuing from current point 884 * @pos: the type * to use as a loop cursor. 885 * @member: the name of the hlist_node within the struct. 886 */ 887 #define hlist_for_each_entry_from(pos, member) \ 888 for (; pos; \ 889 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)) 890 891 /** 892 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry 893 * @pos: the type * to use as a loop cursor. 894 * @n: another &struct hlist_node to use as temporary storage 895 * @head: the head for your list. 896 * @member: the name of the hlist_node within the struct. 897 */ 898 #define hlist_for_each_entry_safe(pos, n, head, member) \ 899 for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\ 900 pos && ({ n = pos->member.next; 1; }); \ 901 pos = hlist_entry_safe(n, typeof(*pos), member)) 902 903 #endif 904