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