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