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