include/linux/list.h

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