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  * Circular 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         WRITE_ONCE(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, const struct list_head *head)
 260 {
 261         return list->prev == head;
 262 }
 263
 264 /**
 265  * list_is_last - tests whether @list is the last entry in list @head
 266  * @list: the entry to test
 267  * @head: the head of the list
 268  */
 269 static inline int list_is_last(const struct list_head *list, const struct list_head *head)
 270 {
 271         return list->next == head;
 272 }
 273
 274 /**
 275  * list_is_head - tests whether @list is the list @head
 276  * @list: the entry to test
 277  * @head: the head of the list
 278  */
 279 static inline int list_is_head(const struct list_head *list, const struct list_head *head)
 280 {
 281         return list == head;
 282 }
 283
 284 /**
 285  * list_empty - tests whether a list is empty
 286  * @head: the list to test.
 287  */
 288 static inline int list_empty(const struct list_head *head)
 289 {
 290         return READ_ONCE(head->next) == head;
 291 }
 292
 293 /**
 294  * list_del_init_careful - deletes entry from list and reinitialize it.
 295  * @entry: the element to delete from the list.
 296  *
 297  * This is the same as list_del_init(), except designed to be used
 298  * together with list_empty_careful() in a way to guarantee ordering
 299  * of other memory operations.
 300  *
 301  * Any memory operations done before a list_del_init_careful() are
 302  * guaranteed to be visible after a list_empty_careful() test.
 303  */
 304 static inline void list_del_init_careful(struct list_head *entry)
 305 {
 306         __list_del_entry(entry);
 307         WRITE_ONCE(entry->prev, entry);
 308         smp_store_release(&entry->next, entry);
 309 }
 310
 311 /**
 312  * list_empty_careful - tests whether a list is empty and not being modified
 313  * @head: the list to test
 314  *
 315  * Description:
 316  * tests whether a list is empty _and_ checks that no other CPU might be
 317  * in the process of modifying either member (next or prev)
 318  *
 319  * NOTE: using list_empty_careful() without synchronization
 320  * can only be safe if the only activity that can happen
 321  * to the list entry is list_del_init(). Eg. it cannot be used
 322  * if another CPU could re-list_add() it.
 323  */
 324 static inline int list_empty_careful(const struct list_head *head)
 325 {
 326         struct list_head *next = smp_load_acquire(&head->next);
 327         return list_is_head(next, head) && (next == READ_ONCE(head->prev));
 328 }
 329
 330 /**
 331  * list_rotate_left - rotate the list to the left
 332  * @head: the head of the list
 333  */
 334 static inline void list_rotate_left(struct list_head *head)
 335 {
 336         struct list_head *first;
 337
 338         if (!list_empty(head)) {
 339                 first = head->next;
 340                 list_move_tail(first, head);
 341         }
 342 }
 343
 344 /**
 345  * list_rotate_to_front() - Rotate list to specific item.
 346  * @list: The desired new front of the list.
 347  * @head: The head of the list.
 348  *
 349  * Rotates list so that @list becomes the new front of the list.
 350  */
 351 static inline void list_rotate_to_front(struct list_head *list,
 352                                         struct list_head *head)
 353 {
 354         /*
 355          * Deletes the list head from the list denoted by @head and
 356          * places it as the tail of @list, this effectively rotates the
 357          * list so that @list is at the front.
 358          */
 359         list_move_tail(head, list);
 360 }
 361
 362 /**
 363  * list_is_singular - tests whether a list has just one entry.
 364  * @head: the list to test.
 365  */
 366 static inline int list_is_singular(const struct list_head *head)
 367 {
 368         return !list_empty(head) && (head->next == head->prev);
 369 }
 370
 371 static inline void __list_cut_position(struct list_head *list,
 372                 struct list_head *head, struct list_head *entry)
 373 {
 374         struct list_head *new_first = entry->next;
 375         list->next = head->next;
 376         list->next->prev = list;
 377         list->prev = entry;
 378         entry->next = list;
 379         head->next = new_first;
 380         new_first->prev = head;
 381 }
 382
 383 /**
 384  * list_cut_position - cut a list into two
 385  * @list: a new list to add all removed entries
 386  * @head: a list with entries
 387  * @entry: an entry within head, could be the head itself
 388  *      and if so we won't cut the list
 389  *
 390  * This helper moves the initial part of @head, up to and
 391  * including @entry, from @head to @list. You should
 392  * pass on @entry an element you know is on @head. @list
 393  * should be an empty list or a list you do not care about
 394  * losing its data.
 395  *
 396  */
 397 static inline void list_cut_position(struct list_head *list,
 398                 struct list_head *head, struct list_head *entry)
 399 {
 400         if (list_empty(head))
 401                 return;
 402         if (list_is_singular(head) && !list_is_head(entry, head) && (entry != head->next))
 403                 return;
 404         if (list_is_head(entry, head))
 405                 INIT_LIST_HEAD(list);
 406         else
 407                 __list_cut_position(list, head, entry);
 408 }
 409
 410 /**
 411  * list_cut_before - cut a list into two, before given entry
 412  * @list: a new list to add all removed entries
 413  * @head: a list with entries
 414  * @entry: an entry within head, could be the head itself
 415  *
 416  * This helper moves the initial part of @head, up to but
 417  * excluding @entry, from @head to @list.  You should pass
 418  * in @entry an element you know is on @head.  @list should
 419  * be an empty list or a list you do not care about losing
 420  * its data.
 421  * If @entry == @head, all entries on @head are moved to
 422  * @list.
 423  */
 424 static inline void list_cut_before(struct list_head *list,
 425                                    struct list_head *head,
 426                                    struct list_head *entry)
 427 {
 428         if (head->next == entry) {
 429                 INIT_LIST_HEAD(list);
 430                 return;
 431         }
 432         list->next = head->next;
 433         list->next->prev = list;
 434         list->prev = entry->prev;
 435         list->prev->next = list;
 436         head->next = entry;
 437         entry->prev = head;
 438 }
 439
 440 static inline void __list_splice(const struct list_head *list,
 441                                  struct list_head *prev,
 442                                  struct list_head *next)
 443 {
 444         struct list_head *first = list->next;
 445         struct list_head *last = list->prev;
 446
 447         first->prev = prev;
 448         prev->next = first;
 449
 450         last->next = next;
 451         next->prev = last;
 452 }
 453
 454 /**
 455  * list_splice - join two lists, this is designed for stacks
 456  * @list: the new list to add.
 457  * @head: the place to add it in the first list.
 458  */
 459 static inline void list_splice(const struct list_head *list,
 460                                 struct list_head *head)
 461 {
 462         if (!list_empty(list))
 463                 __list_splice(list, head, head->next);
 464 }
 465
 466 /**
 467  * list_splice_tail - join two lists, each list being a queue
 468  * @list: the new list to add.
 469  * @head: the place to add it in the first list.
 470  */
 471 static inline void list_splice_tail(struct list_head *list,
 472                                 struct list_head *head)
 473 {
 474         if (!list_empty(list))
 475                 __list_splice(list, head->prev, head);
 476 }
 477
 478 /**
 479  * list_splice_init - join two lists and reinitialise the emptied list.
 480  * @list: the new list to add.
 481  * @head: the place to add it in the first list.
 482  *
 483  * The list at @list is reinitialised
 484  */
 485 static inline void list_splice_init(struct list_head *list,
 486                                     struct list_head *head)
 487 {
 488         if (!list_empty(list)) {
 489                 __list_splice(list, head, head->next);
 490                 INIT_LIST_HEAD(list);
 491         }
 492 }
 493
 494 /**
 495  * list_splice_tail_init - join two lists and reinitialise the emptied list
 496  * @list: the new list to add.
 497  * @head: the place to add it in the first list.
 498  *
 499  * Each of the lists is a queue.
 500  * The list at @list is reinitialised
 501  */
 502 static inline void list_splice_tail_init(struct list_head *list,
 503                                          struct list_head *head)
 504 {
 505         if (!list_empty(list)) {
 506                 __list_splice(list, head->prev, head);
 507                 INIT_LIST_HEAD(list);
 508         }
 509 }
 510
 511 /**
 512  * list_entry - get the struct for this entry
 513  * @ptr:        the &struct list_head pointer.
 514  * @type:       the type of the struct this is embedded in.
 515  * @member:     the name of the list_head within the struct.
 516  */
 517 #define list_entry(ptr, type, member) \
 518         container_of(ptr, type, member)
 519
 520 /**
 521  * list_first_entry - get the first element from a list
 522  * @ptr:        the list head to take the element from.
 523  * @type:       the type of the struct this is embedded in.
 524  * @member:     the name of the list_head within the struct.
 525  *
 526  * Note, that list is expected to be not empty.
 527  */
 528 #define list_first_entry(ptr, type, member) \
 529         list_entry((ptr)->next, type, member)
 530
 531 /**
 532  * list_last_entry - get the last element from a list
 533  * @ptr:        the list head to take the element from.
 534  * @type:       the type of the struct this is embedded in.
 535  * @member:     the name of the list_head within the struct.
 536  *
 537  * Note, that list is expected to be not empty.
 538  */
 539 #define list_last_entry(ptr, type, member) \
 540         list_entry((ptr)->prev, type, member)
 541
 542 /**
 543  * list_first_entry_or_null - get the first element from a list
 544  * @ptr:        the list head to take the element from.
 545  * @type:       the type of the struct this is embedded in.
 546  * @member:     the name of the list_head within the struct.
 547  *
 548  * Note that if the list is empty, it returns NULL.
 549  */
 550 #define list_first_entry_or_null(ptr, type, member) ({ \
 551         struct list_head *head__ = (ptr); \
 552         struct list_head *pos__ = READ_ONCE(head__->next); \
 553         pos__ != head__ ? list_entry(pos__, type, member) : NULL; \
 554 })
 555
 556 /**
 557  * list_next_entry - get the next element in list
 558  * @pos:        the type * to cursor
 559  * @member:     the name of the list_head within the struct.
 560  */
 561 #define list_next_entry(pos, member) \
 562         list_entry((pos)->member.next, typeof(*(pos)), member)
 563
 564 /**
 565  * list_prev_entry - get the prev element in list
 566  * @pos:        the type * to cursor
 567  * @member:     the name of the list_head within the struct.
 568  */
 569 #define list_prev_entry(pos, member) \
 570         list_entry((pos)->member.prev, typeof(*(pos)), member)
 571
 572 /**
 573  * list_for_each        -       iterate over a list
 574  * @pos:        the &struct list_head to use as a loop cursor.
 575  * @head:       the head for your list.
 576  */
 577 #define list_for_each(pos, head) \
 578         for (pos = (head)->next; !list_is_head(pos, (head)); pos = pos->next)
 579
 580 /**
 581  * list_for_each_rcu - Iterate over a list in an RCU-safe fashion
 582  * @pos:        the &struct list_head to use as a loop cursor.
 583  * @head:       the head for your list.
 584  */
 585 #define list_for_each_rcu(pos, head)              \
 586         for (pos = rcu_dereference((head)->next); \
 587              !list_is_head(pos, (head)); \
 588              pos = rcu_dereference(pos->next))
 589
 590 /**
 591  * list_for_each_continue - continue iteration over a list
 592  * @pos:        the &struct list_head to use as a loop cursor.
 593  * @head:       the head for your list.
 594  *
 595  * Continue to iterate over a list, continuing after the current position.
 596  */
 597 #define list_for_each_continue(pos, head) \
 598         for (pos = pos->next; !list_is_head(pos, (head)); pos = pos->next)
 599
 600 /**
 601  * list_for_each_prev   -       iterate over a list backwards
 602  * @pos:        the &struct list_head to use as a loop cursor.
 603  * @head:       the head for your list.
 604  */
 605 #define list_for_each_prev(pos, head) \
 606         for (pos = (head)->prev; !list_is_head(pos, (head)); pos = pos->prev)
 607
 608 /**
 609  * list_for_each_safe - iterate over a list safe against removal of list entry
 610  * @pos:        the &struct list_head to use as a loop cursor.
 611  * @n:          another &struct list_head to use as temporary storage
 612  * @head:       the head for your list.
 613  */
 614 #define list_for_each_safe(pos, n, head) \
 615         for (pos = (head)->next, n = pos->next; \
 616              !list_is_head(pos, (head)); \
 617              pos = n, n = pos->next)
 618
 619 /**
 620  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
 621  * @pos:        the &struct list_head to use as a loop cursor.
 622  * @n:          another &struct list_head to use as temporary storage
 623  * @head:       the head for your list.
 624  */
 625 #define list_for_each_prev_safe(pos, n, head) \
 626         for (pos = (head)->prev, n = pos->prev; \
 627              !list_is_head(pos, (head)); \
 628              pos = n, n = pos->prev)
 629
 630 /**
 631  * list_entry_is_head - test if the entry points to the head of the list
 632  * @pos:        the type * to cursor
 633  * @head:       the head for your list.
 634  * @member:     the name of the list_head within the struct.
 635  */
 636 #define list_entry_is_head(pos, head, member)                           \
 637         (&pos->member == (head))
 638
 639 /**
 640  * list_for_each_entry  -       iterate over list of given type
 641  * @pos:        the type * to use as a loop cursor.
 642  * @head:       the head for your list.
 643  * @member:     the name of the list_head within the struct.
 644  */
 645 #define list_for_each_entry(pos, head, member)                          \
 646         for (pos = list_first_entry(head, typeof(*pos), member);        \
 647              !list_entry_is_head(pos, head, member);                    \
 648              pos = list_next_entry(pos, member))
 649
 650 /**
 651  * list_for_each_entry_reverse - iterate backwards over list of given type.
 652  * @pos:        the type * to use as a loop cursor.
 653  * @head:       the head for your list.
 654  * @member:     the name of the list_head within the struct.
 655  */
 656 #define list_for_each_entry_reverse(pos, head, member)                  \
 657         for (pos = list_last_entry(head, typeof(*pos), member);         \
 658              !list_entry_is_head(pos, head, member);                    \
 659              pos = list_prev_entry(pos, member))
 660
 661 /**
 662  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
 663  * @pos:        the type * to use as a start point
 664  * @head:       the head of the list
 665  * @member:     the name of the list_head within the struct.
 666  *
 667  * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
 668  */
 669 #define list_prepare_entry(pos, head, member) \
 670         ((pos) ? : list_entry(head, typeof(*pos), member))
 671
 672 /**
 673  * list_for_each_entry_continue - continue iteration over list of given type
 674  * @pos:        the type * to use as a loop cursor.
 675  * @head:       the head for your list.
 676  * @member:     the name of the list_head within the struct.
 677  *
 678  * Continue to iterate over list of given type, continuing after
 679  * the current position.
 680  */
 681 #define list_for_each_entry_continue(pos, head, member)                 \
 682         for (pos = list_next_entry(pos, member);                        \
 683              !list_entry_is_head(pos, head, member);                    \
 684              pos = list_next_entry(pos, member))
 685
 686 /**
 687  * list_for_each_entry_continue_reverse - iterate backwards from the given point
 688  * @pos:        the type * to use as a loop cursor.
 689  * @head:       the head for your list.
 690  * @member:     the name of the list_head within the struct.
 691  *
 692  * Start to iterate over list of given type backwards, continuing after
 693  * the current position.
 694  */
 695 #define list_for_each_entry_continue_reverse(pos, head, member)         \
 696         for (pos = list_prev_entry(pos, member);                        \
 697              !list_entry_is_head(pos, head, member);                    \
 698              pos = list_prev_entry(pos, member))
 699
 700 /**
 701  * list_for_each_entry_from - iterate over list of given type from the current point
 702  * @pos:        the type * to use as a loop cursor.
 703  * @head:       the head for your list.
 704  * @member:     the name of the list_head within the struct.
 705  *
 706  * Iterate over list of given type, continuing from current position.
 707  */
 708 #define list_for_each_entry_from(pos, head, member)                     \
 709         for (; !list_entry_is_head(pos, head, member);                  \
 710              pos = list_next_entry(pos, member))
 711
 712 /**
 713  * list_for_each_entry_from_reverse - iterate backwards over list of given type
 714  *                                    from the current point
 715  * @pos:        the type * to use as a loop cursor.
 716  * @head:       the head for your list.
 717  * @member:     the name of the list_head within the struct.
 718  *
 719  * Iterate backwards over list of given type, continuing from current position.
 720  */
 721 #define list_for_each_entry_from_reverse(pos, head, member)             \
 722         for (; !list_entry_is_head(pos, head, member);                  \
 723              pos = list_prev_entry(pos, member))
 724
 725 /**
 726  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 727  * @pos:        the type * to use as a loop cursor.
 728  * @n:          another type * to use as temporary storage
 729  * @head:       the head for your list.
 730  * @member:     the name of the list_head within the struct.
 731  */
 732 #define list_for_each_entry_safe(pos, n, head, member)                  \
 733         for (pos = list_first_entry(head, typeof(*pos), member),        \
 734                 n = list_next_entry(pos, member);                       \
 735              !list_entry_is_head(pos, head, member);                    \
 736              pos = n, n = list_next_entry(n, member))
 737
 738 /**
 739  * list_for_each_entry_safe_continue - continue list iteration safe against removal
 740  * @pos:        the type * to use as a loop cursor.
 741  * @n:          another type * to use as temporary storage
 742  * @head:       the head for your list.
 743  * @member:     the name of the list_head within the struct.
 744  *
 745  * Iterate over list of given type, continuing after current point,
 746  * safe against removal of list entry.
 747  */
 748 #define list_for_each_entry_safe_continue(pos, n, head, member)                 \
 749         for (pos = list_next_entry(pos, member),                                \
 750                 n = list_next_entry(pos, member);                               \
 751              !list_entry_is_head(pos, head, member);                            \
 752              pos = n, n = list_next_entry(n, member))
 753
 754 /**
 755  * list_for_each_entry_safe_from - iterate over list from current point safe against removal
 756  * @pos:        the type * to use as a loop cursor.
 757  * @n:          another type * to use as temporary storage
 758  * @head:       the head for your list.
 759  * @member:     the name of the list_head within the struct.
 760  *
 761  * Iterate over list of given type from current point, safe against
 762  * removal of list entry.
 763  */
 764 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
 765         for (n = list_next_entry(pos, member);                                  \
 766              !list_entry_is_head(pos, head, member);                            \
 767              pos = n, n = list_next_entry(n, member))
 768
 769 /**
 770  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
 771  * @pos:        the type * to use as a loop cursor.
 772  * @n:          another type * to use as temporary storage
 773  * @head:       the head for your list.
 774  * @member:     the name of the list_head within the struct.
 775  *
 776  * Iterate backwards over list of given type, safe against removal
 777  * of list entry.
 778  */
 779 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
 780         for (pos = list_last_entry(head, typeof(*pos), member),         \
 781                 n = list_prev_entry(pos, member);                       \
 782              !list_entry_is_head(pos, head, member);                    \
 783              pos = n, n = list_prev_entry(n, member))
 784
 785 /**
 786  * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
 787  * @pos:        the loop cursor used in the list_for_each_entry_safe loop
 788  * @n:          temporary storage used in list_for_each_entry_safe
 789  * @member:     the name of the list_head within the struct.
 790  *
 791  * list_safe_reset_next is not safe to use in general if the list may be
 792  * modified concurrently (eg. the lock is dropped in the loop body). An
 793  * exception to this is if the cursor element (pos) is pinned in the list,
 794  * and list_safe_reset_next is called after re-taking the lock and before
 795  * completing the current iteration of the loop body.
 796  */
 797 #define list_safe_reset_next(pos, n, member)                            \
 798         n = list_next_entry(pos, member)
 799
 800 /*
 801  * Double linked lists with a single pointer list head.
 802  * Mostly useful for hash tables where the two pointer list head is
 803  * too wasteful.
 804  * You lose the ability to access the tail in O(1).
 805  */
 806
 807 #define HLIST_HEAD_INIT { .first = NULL }
 808 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
 809 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
 810 static inline void INIT_HLIST_NODE(struct hlist_node *h)
 811 {
 812         h->next = NULL;
 813         h->pprev = NULL;
 814 }
 815
 816 /**
 817  * hlist_unhashed - Has node been removed from list and reinitialized?
 818  * @h: Node to be checked
 819  *
 820  * Not that not all removal functions will leave a node in unhashed
 821  * state.  For example, hlist_nulls_del_init_rcu() does leave the
 822  * node in unhashed state, but hlist_nulls_del() does not.
 823  */
 824 static inline int hlist_unhashed(const struct hlist_node *h)
 825 {
 826         return !h->pprev;
 827 }
 828
 829 /**
 830  * hlist_unhashed_lockless - Version of hlist_unhashed for lockless use
 831  * @h: Node to be checked
 832  *
 833  * This variant of hlist_unhashed() must be used in lockless contexts
 834  * to avoid potential load-tearing.  The READ_ONCE() is paired with the
 835  * various WRITE_ONCE() in hlist helpers that are defined below.
 836  */
 837 static inline int hlist_unhashed_lockless(const struct hlist_node *h)
 838 {
 839         return !READ_ONCE(h->pprev);
 840 }
 841
 842 /**
 843  * hlist_empty - Is the specified hlist_head structure an empty hlist?
 844  * @h: Structure to check.
 845  */
 846 static inline int hlist_empty(const struct hlist_head *h)
 847 {
 848         return !READ_ONCE(h->first);
 849 }
 850
 851 static inline void __hlist_del(struct hlist_node *n)
 852 {
 853         struct hlist_node *next = n->next;
 854         struct hlist_node **pprev = n->pprev;
 855
 856         WRITE_ONCE(*pprev, next);
 857         if (next)
 858                 WRITE_ONCE(next->pprev, pprev);
 859 }
 860
 861 /**
 862  * hlist_del - Delete the specified hlist_node from its list
 863  * @n: Node to delete.
 864  *
 865  * Note that this function leaves the node in hashed state.  Use
 866  * hlist_del_init() or similar instead to unhash @n.
 867  */
 868 static inline void hlist_del(struct hlist_node *n)
 869 {
 870         __hlist_del(n);
 871         n->next = LIST_POISON1;
 872         n->pprev = LIST_POISON2;
 873 }
 874
 875 /**
 876  * hlist_del_init - Delete the specified hlist_node from its list and initialize
 877  * @n: Node to delete.
 878  *
 879  * Note that this function leaves the node in unhashed state.
 880  */
 881 static inline void hlist_del_init(struct hlist_node *n)
 882 {
 883         if (!hlist_unhashed(n)) {
 884                 __hlist_del(n);
 885                 INIT_HLIST_NODE(n);
 886         }
 887 }
 888
 889 /**
 890  * hlist_add_head - add a new entry at the beginning of the hlist
 891  * @n: new entry to be added
 892  * @h: hlist head to add it after
 893  *
 894  * Insert a new entry after the specified head.
 895  * This is good for implementing stacks.
 896  */
 897 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 898 {
 899         struct hlist_node *first = h->first;
 900         WRITE_ONCE(n->next, first);
 901         if (first)
 902                 WRITE_ONCE(first->pprev, &n->next);
 903         WRITE_ONCE(h->first, n);
 904         WRITE_ONCE(n->pprev, &h->first);
 905 }
 906
 907 /**
 908  * hlist_add_before - add a new entry before the one specified
 909  * @n: new entry to be added
 910  * @next: hlist node to add it before, which must be non-NULL
 911  */
 912 static inline void hlist_add_before(struct hlist_node *n,
 913                                     struct hlist_node *next)
 914 {
 915         WRITE_ONCE(n->pprev, next->pprev);
 916         WRITE_ONCE(n->next, next);
 917         WRITE_ONCE(next->pprev, &n->next);
 918         WRITE_ONCE(*(n->pprev), n);
 919 }
 920
 921 /**
 922  * hlist_add_behind - add a new entry after the one specified
 923  * @n: new entry to be added
 924  * @prev: hlist node to add it after, which must be non-NULL
 925  */
 926 static inline void hlist_add_behind(struct hlist_node *n,
 927                                     struct hlist_node *prev)
 928 {
 929         WRITE_ONCE(n->next, prev->next);
 930         WRITE_ONCE(prev->next, n);
 931         WRITE_ONCE(n->pprev, &prev->next);
 932
 933         if (n->next)
 934                 WRITE_ONCE(n->next->pprev, &n->next);
 935 }
 936
 937 /**
 938  * hlist_add_fake - create a fake hlist consisting of a single headless node
 939  * @n: Node to make a fake list out of
 940  *
 941  * This makes @n appear to be its own predecessor on a headless hlist.
 942  * The point of this is to allow things like hlist_del() to work correctly
 943  * in cases where there is no list.
 944  */
 945 static inline void hlist_add_fake(struct hlist_node *n)
 946 {
 947         n->pprev = &n->next;
 948 }
 949
 950 /**
 951  * hlist_fake: Is this node a fake hlist?
 952  * @h: Node to check for being a self-referential fake hlist.
 953  */
 954 static inline bool hlist_fake(struct hlist_node *h)
 955 {
 956         return h->pprev == &h->next;
 957 }
 958
 959 /**
 960  * hlist_is_singular_node - is node the only element of the specified hlist?
 961  * @n: Node to check for singularity.
 962  * @h: Header for potentially singular list.
 963  *
 964  * Check whether the node is the only node of the head without
 965  * accessing head, thus avoiding unnecessary cache misses.
 966  */
 967 static inline bool
 968 hlist_is_singular_node(struct hlist_node *n, struct hlist_head *h)
 969 {
 970         return !n->next && n->pprev == &h->first;
 971 }
 972
 973 /**
 974  * hlist_move_list - Move an hlist
 975  * @old: hlist_head for old list.
 976  * @new: hlist_head for new list.
 977  *
 978  * Move a list from one list head to another. Fixup the pprev
 979  * reference of the first entry if it exists.
 980  */
 981 static inline void hlist_move_list(struct hlist_head *old,
 982                                    struct hlist_head *new)
 983 {
 984         new->first = old->first;
 985         if (new->first)
 986                 new->first->pprev = &new->first;
 987         old->first = NULL;
 988 }
 989
 990 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
 991
 992 #define hlist_for_each(pos, head) \
 993         for (pos = (head)->first; pos ; pos = pos->next)
 994
 995 #define hlist_for_each_safe(pos, n, head) \
 996         for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
 997              pos = n)
 998
 999 #define hlist_entry_safe(ptr, type, member) \
1000         ({ typeof(ptr) ____ptr = (ptr); \
1001            ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
1002         })
1003
1004 /**
1005  * hlist_for_each_entry - iterate over list of given type
1006  * @pos:        the type * to use as a loop cursor.
1007  * @head:       the head for your list.
1008  * @member:     the name of the hlist_node within the struct.
1009  */
1010 #define hlist_for_each_entry(pos, head, member)                         \
1011         for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
1012              pos;                                                       \
1013              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1014
1015 /**
1016  * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
1017  * @pos:        the type * to use as a loop cursor.
1018  * @member:     the name of the hlist_node within the struct.
1019  */
1020 #define hlist_for_each_entry_continue(pos, member)                      \
1021         for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
1022              pos;                                                       \
1023              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1024
1025 /**
1026  * hlist_for_each_entry_from - iterate over a hlist continuing from current point
1027  * @pos:        the type * to use as a loop cursor.
1028  * @member:     the name of the hlist_node within the struct.
1029  */
1030 #define hlist_for_each_entry_from(pos, member)                          \
1031         for (; pos;                                                     \
1032              pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1033
1034 /**
1035  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1036  * @pos:        the type * to use as a loop cursor.
1037  * @n:          a &struct hlist_node to use as temporary storage
1038  * @head:       the head for your list.
1039  * @member:     the name of the hlist_node within the struct.
1040  */
1041 #define hlist_for_each_entry_safe(pos, n, head, member)                 \
1042         for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
1043              pos && ({ n = pos->member.next; 1; });                     \
1044              pos = hlist_entry_safe(n, typeof(*pos), member))
1045
1046 #endif