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