include/linux/list.h

   1 #ifndef _LINUX_LIST_H
   2 #define _LINUX_LIST_H
   3
   4 #include <linux/stddef.h>
   5 #include <linux/poison.h>
   6 #include <linux/prefetch.h>
   7 #include <asm/system.h>
   8
   9 /*
  10  * Simple doubly linked list implementation.
  11  *
  12  * Some of the internal functions ("__xxx") are useful when
  13  * manipulating whole lists rather than single entries, as
  14  * sometimes we already know the next/prev entries and we can
  15  * generate better code by using them directly rather than
  16  * using the generic single-entry routines.
  17  */
  18
  19 struct list_head {
  20         struct list_head *next, *prev;
  21 };
  22
  23 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  24
  25 #define LIST_HEAD(name) \
  26         struct list_head name = LIST_HEAD_INIT(name)
  27
  28 static inline void INIT_LIST_HEAD(struct list_head *list)
  29 {
  30         list->next = list;
  31         list->prev = list;
  32 }
  33
  34 /*
  35  * Insert a new entry between two known consecutive entries.
  36  *
  37  * This is only for internal list manipulation where we know
  38  * the prev/next entries already!
  39  */
  40 #ifndef CONFIG_DEBUG_LIST
  41 static inline void __list_add(struct list_head *new,
  42                               struct list_head *prev,
  43                               struct list_head *next)
  44 {
  45         next->prev = new;
  46         new->next = next;
  47         new->prev = prev;
  48         prev->next = new;
  49 }
  50 #else
  51 extern void __list_add(struct list_head *new,
  52                               struct list_head *prev,
  53                               struct list_head *next);
  54 #endif
  55
  56 /**
  57  * list_add - add a new entry
  58  * @new: new entry to be added
  59  * @head: list head to add it after
  60  *
  61  * Insert a new entry after the specified head.
  62  * This is good for implementing stacks.
  63  */
  64 #ifndef CONFIG_DEBUG_LIST
  65 static inline void list_add(struct list_head *new, struct list_head *head)
  66 {
  67         __list_add(new, head, head->next);
  68 }
  69 #else
  70 extern void list_add(struct list_head *new, struct list_head *head);
  71 #endif
  72
  73
  74 /**
  75  * list_add_tail - add a new entry
  76  * @new: new entry to be added
  77  * @head: list head to add it before
  78  *
  79  * Insert a new entry before the specified head.
  80  * This is useful for implementing queues.
  81  */
  82 static inline void list_add_tail(struct list_head *new, struct list_head *head)
  83 {
  84         __list_add(new, head->prev, head);
  85 }
  86
  87 /*
  88  * Insert a new entry between two known consecutive entries.
  89  *
  90  * This is only for internal list manipulation where we know
  91  * the prev/next entries already!
  92  */
  93 static inline void __list_add_rcu(struct list_head * new,
  94                 struct list_head * prev, struct list_head * next)
  95 {
  96         new->next = next;
  97         new->prev = prev;
  98         smp_wmb();
  99         next->prev = new;
 100         prev->next = new;
 101 }
 102
 103 /**
 104  * list_add_rcu - add a new entry to rcu-protected list
 105  * @new: new entry to be added
 106  * @head: list head to add it after
 107  *
 108  * Insert a new entry after the specified head.
 109  * This is good for implementing stacks.
 110  *
 111  * The caller must take whatever precautions are necessary
 112  * (such as holding appropriate locks) to avoid racing
 113  * with another list-mutation primitive, such as list_add_rcu()
 114  * or list_del_rcu(), running on this same list.
 115  * However, it is perfectly legal to run concurrently with
 116  * the _rcu list-traversal primitives, such as
 117  * list_for_each_entry_rcu().
 118  */
 119 static inline void list_add_rcu(struct list_head *new, struct list_head *head)
 120 {
 121         __list_add_rcu(new, head, head->next);
 122 }
 123
 124 /**
 125  * list_add_tail_rcu - add a new entry to rcu-protected list
 126  * @new: new entry to be added
 127  * @head: list head to add it before
 128  *
 129  * Insert a new entry before the specified head.
 130  * This is useful for implementing queues.
 131  *
 132  * The caller must take whatever precautions are necessary
 133  * (such as holding appropriate locks) to avoid racing
 134  * with another list-mutation primitive, such as list_add_tail_rcu()
 135  * or list_del_rcu(), running on this same list.
 136  * However, it is perfectly legal to run concurrently with
 137  * the _rcu list-traversal primitives, such as
 138  * list_for_each_entry_rcu().
 139  */
 140 static inline void list_add_tail_rcu(struct list_head *new,
 141                                         struct list_head *head)
 142 {
 143         __list_add_rcu(new, head->prev, head);
 144 }
 145
 146 /*
 147  * Delete a list entry by making the prev/next entries
 148  * point to each other.
 149  *
 150  * This is only for internal list manipulation where we know
 151  * the prev/next entries already!
 152  */
 153 static inline void __list_del(struct list_head * prev, struct list_head * next)
 154 {
 155         next->prev = prev;
 156         prev->next = next;
 157 }
 158
 159 /**
 160  * list_del - deletes entry from list.
 161  * @entry: the element to delete from the list.
 162  * Note: list_empty() on entry does not return true after this, the entry is
 163  * in an undefined state.
 164  */
 165 #ifndef CONFIG_DEBUG_LIST
 166 static inline void list_del(struct list_head *entry)
 167 {
 168         __list_del(entry->prev, entry->next);
 169         entry->next = LIST_POISON1;
 170         entry->prev = LIST_POISON2;
 171 }
 172 #else
 173 extern void list_del(struct list_head *entry);
 174 #endif
 175
 176 /**
 177  * list_del_rcu - deletes entry from list without re-initialization
 178  * @entry: the element to delete from the list.
 179  *
 180  * Note: list_empty() on entry does not return true after this,
 181  * the entry is in an undefined state. It is useful for RCU based
 182  * lockfree traversal.
 183  *
 184  * In particular, it means that we can not poison the forward
 185  * pointers that may still be used for walking the list.
 186  *
 187  * The caller must take whatever precautions are necessary
 188  * (such as holding appropriate locks) to avoid racing
 189  * with another list-mutation primitive, such as list_del_rcu()
 190  * or list_add_rcu(), running on this same list.
 191  * However, it is perfectly legal to run concurrently with
 192  * the _rcu list-traversal primitives, such as
 193  * list_for_each_entry_rcu().
 194  *
 195  * Note that the caller is not permitted to immediately free
 196  * the newly deleted entry.  Instead, either synchronize_rcu()
 197  * or call_rcu() must be used to defer freeing until an RCU
 198  * grace period has elapsed.
 199  */
 200 static inline void list_del_rcu(struct list_head *entry)
 201 {
 202         __list_del(entry->prev, entry->next);
 203         entry->prev = LIST_POISON2;
 204 }
 205
 206 /**
 207  * list_replace - replace old entry by new one
 208  * @old : the element to be replaced
 209  * @new : the new element to insert
 210  *
 211  * If @old was empty, it will be overwritten.
 212  */
 213 static inline void list_replace(struct list_head *old,
 214                                 struct list_head *new)
 215 {
 216         new->next = old->next;
 217         new->next->prev = new;
 218         new->prev = old->prev;
 219         new->prev->next = new;
 220 }
 221
 222 static inline void list_replace_init(struct list_head *old,
 223                                         struct list_head *new)
 224 {
 225         list_replace(old, new);
 226         INIT_LIST_HEAD(old);
 227 }
 228
 229 /**
 230  * list_replace_rcu - replace old entry by new one
 231  * @old : the element to be replaced
 232  * @new : the new element to insert
 233  *
 234  * The @old entry will be replaced with the @new entry atomically.
 235  * Note: @old should not be empty.
 236  */
 237 static inline void list_replace_rcu(struct list_head *old,
 238                                 struct list_head *new)
 239 {
 240         new->next = old->next;
 241         new->prev = old->prev;
 242         smp_wmb();
 243         new->next->prev = new;
 244         new->prev->next = new;
 245         old->prev = LIST_POISON2;
 246 }
 247
 248 /**
 249  * list_del_init - deletes entry from list and reinitialize it.
 250  * @entry: the element to delete from the list.
 251  */
 252 static inline void list_del_init(struct list_head *entry)
 253 {
 254         __list_del(entry->prev, entry->next);
 255         INIT_LIST_HEAD(entry);
 256 }
 257
 258 /**
 259  * list_move - delete from one list and add as another's head
 260  * @list: the entry to move
 261  * @head: the head that will precede our entry
 262  */
 263 static inline void list_move(struct list_head *list, struct list_head *head)
 264 {
 265         __list_del(list->prev, list->next);
 266         list_add(list, head);
 267 }
 268
 269 /**
 270  * list_move_tail - delete from one list and add as another's tail
 271  * @list: the entry to move
 272  * @head: the head that will follow our entry
 273  */
 274 static inline void list_move_tail(struct list_head *list,
 275                                   struct list_head *head)
 276 {
 277         __list_del(list->prev, list->next);
 278         list_add_tail(list, head);
 279 }
 280
 281 /**
 282  * list_is_last - tests whether @list is the last entry in list @head
 283  * @list: the entry to test
 284  * @head: the head of the list
 285  */
 286 static inline int list_is_last(const struct list_head *list,
 287                                 const struct list_head *head)
 288 {
 289         return list->next == head;
 290 }
 291
 292 /**
 293  * list_empty - tests whether a list is empty
 294  * @head: the list to test.
 295  */
 296 static inline int list_empty(const struct list_head *head)
 297 {
 298         return head->next == head;
 299 }
 300
 301 /**
 302  * list_empty_careful - tests whether a list is empty and not being modified
 303  * @head: the list to test
 304  *
 305  * Description:
 306  * tests whether a list is empty _and_ checks that no other CPU might be
 307  * in the process of modifying either member (next or prev)
 308  *
 309  * NOTE: using list_empty_careful() without synchronization
 310  * can only be safe if the only activity that can happen
 311  * to the list entry is list_del_init(). Eg. it cannot be used
 312  * if another CPU could re-list_add() it.
 313  */
 314 static inline int list_empty_careful(const struct list_head *head)
 315 {
 316         struct list_head *next = head->next;
 317         return (next == head) && (next == head->prev);
 318 }
 319
 320 /**
 321  * list_is_singular - tests whether a list has just one entry.
 322  * @head: the list to test.
 323  */
 324 static inline int list_is_singular(const struct list_head *head)
 325 {
 326         return !list_empty(head) && (head->next == head->prev);
 327 }
 328
 329 static inline void __list_splice(const struct list_head *list,
 330                                  struct list_head *head)
 331 {
 332         struct list_head *first = list->next;
 333         struct list_head *last = list->prev;
 334         struct list_head *at = head->next;
 335
 336         first->prev = head;
 337         head->next = first;
 338
 339         last->next = at;
 340         at->prev = last;
 341 }
 342
 343 /**
 344  * list_splice - join two lists
 345  * @list: the new list to add.
 346  * @head: the place to add it in the first list.
 347  */
 348 static inline void list_splice(const struct list_head *list,
 349                                 struct list_head *head)
 350 {
 351         if (!list_empty(list))
 352                 __list_splice(list, head);
 353 }
 354
 355 /**
 356  * list_splice_init - join two lists and reinitialise the emptied list.
 357  * @list: the new list to add.
 358  * @head: the place to add it in the first list.
 359  *
 360  * The list at @list is reinitialised
 361  */
 362 static inline void list_splice_init(struct list_head *list,
 363                                     struct list_head *head)
 364 {
 365         if (!list_empty(list)) {
 366                 __list_splice(list, head);
 367                 INIT_LIST_HEAD(list);
 368         }
 369 }
 370
 371 /**
 372  * list_splice_init_rcu - splice an RCU-protected list into an existing list.
 373  * @list:       the RCU-protected list to splice
 374  * @head:       the place in the list to splice the first list into
 375  * @sync:       function to sync: synchronize_rcu(), synchronize_sched(), ...
 376  *
 377  * @head can be RCU-read traversed concurrently with this function.
 378  *
 379  * Note that this function blocks.
 380  *
 381  * Important note: the caller must take whatever action is necessary to
 382  *      prevent any other updates to @head.  In principle, it is possible
 383  *      to modify the list as soon as sync() begins execution.
 384  *      If this sort of thing becomes necessary, an alternative version
 385  *      based on call_rcu() could be created.  But only if -really-
 386  *      needed -- there is no shortage of RCU API members.
 387  */
 388 static inline void list_splice_init_rcu(struct list_head *list,
 389                                         struct list_head *head,
 390                                         void (*sync)(void))
 391 {
 392         struct list_head *first = list->next;
 393         struct list_head *last = list->prev;
 394         struct list_head *at = head->next;
 395
 396         if (list_empty(head))
 397                 return;
 398
 399         /* "first" and "last" tracking list, so initialize it. */
 400
 401         INIT_LIST_HEAD(list);
 402
 403         /*
 404          * At this point, the list body still points to the source list.
 405          * Wait for any readers to finish using the list before splicing
 406          * the list body into the new list.  Any new readers will see
 407          * an empty list.
 408          */
 409
 410         sync();
 411
 412         /*
 413          * Readers are finished with the source list, so perform splice.
 414          * The order is important if the new list is global and accessible
 415          * to concurrent RCU readers.  Note that RCU readers are not
 416          * permitted to traverse the prev pointers without excluding
 417          * this function.
 418          */
 419
 420         last->next = at;
 421         smp_wmb();
 422         head->next = first;
 423         first->prev = head;
 424         at->prev = last;
 425 }
 426
 427 /**
 428  * list_entry - get the struct for this entry
 429  * @ptr:        the &struct list_head pointer.
 430  * @type:       the type of the struct this is embedded in.
 431  * @member:     the name of the list_struct within the struct.
 432  */
 433 #define list_entry(ptr, type, member) \
 434         container_of(ptr, type, member)
 435
 436 /**
 437  * list_first_entry - get the first element from a list
 438  * @ptr:        the list head to take the element from.
 439  * @type:       the type of the struct this is embedded in.
 440  * @member:     the name of the list_struct within the struct.
 441  *
 442  * Note, that list is expected to be not empty.
 443  */
 444 #define list_first_entry(ptr, type, member) \
 445         list_entry((ptr)->next, type, member)
 446
 447 /**
 448  * list_for_each        -       iterate over a list
 449  * @pos:        the &struct list_head to use as a loop cursor.
 450  * @head:       the head for your list.
 451  */
 452 #define list_for_each(pos, head) \
 453         for (pos = (head)->next; prefetch(pos->next), pos != (head); \
 454                 pos = pos->next)
 455
 456 /**
 457  * __list_for_each      -       iterate over a list
 458  * @pos:        the &struct list_head to use as a loop cursor.
 459  * @head:       the head for your list.
 460  *
 461  * This variant differs from list_for_each() in that it's the
 462  * simplest possible list iteration code, no prefetching is done.
 463  * Use this for code that knows the list to be very short (empty
 464  * or 1 entry) most of the time.
 465  */
 466 #define __list_for_each(pos, head) \
 467         for (pos = (head)->next; pos != (head); pos = pos->next)
 468
 469 /**
 470  * list_for_each_prev   -       iterate over a list backwards
 471  * @pos:        the &struct list_head to use as a loop cursor.
 472  * @head:       the head for your list.
 473  */
 474 #define list_for_each_prev(pos, head) \
 475         for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
 476                 pos = pos->prev)
 477
 478 /**
 479  * list_for_each_safe - iterate over a list safe against removal of list entry
 480  * @pos:        the &struct list_head to use as a loop cursor.
 481  * @n:          another &struct list_head to use as temporary storage
 482  * @head:       the head for your list.
 483  */
 484 #define list_for_each_safe(pos, n, head) \
 485         for (pos = (head)->next, n = pos->next; pos != (head); \
 486                 pos = n, n = pos->next)
 487
 488 /**
 489  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
 490  * @pos:        the &struct list_head to use as a loop cursor.
 491  * @n:          another &struct list_head to use as temporary storage
 492  * @head:       the head for your list.
 493  */
 494 #define list_for_each_prev_safe(pos, n, head) \
 495         for (pos = (head)->prev, n = pos->prev; \
 496              prefetch(pos->prev), pos != (head); \
 497              pos = n, n = pos->prev)
 498
 499 /**
 500  * list_for_each_entry  -       iterate over list of given type
 501  * @pos:        the type * to use as a loop cursor.
 502  * @head:       the head for your list.
 503  * @member:     the name of the list_struct within the struct.
 504  */
 505 #define list_for_each_entry(pos, head, member)                          \
 506         for (pos = list_entry((head)->next, typeof(*pos), member);      \
 507              prefetch(pos->member.next), &pos->member != (head);        \
 508              pos = list_entry(pos->member.next, typeof(*pos), member))
 509
 510 /**
 511  * list_for_each_entry_reverse - iterate backwards over list of given type.
 512  * @pos:        the type * to use as a loop cursor.
 513  * @head:       the head for your list.
 514  * @member:     the name of the list_struct within the struct.
 515  */
 516 #define list_for_each_entry_reverse(pos, head, member)                  \
 517         for (pos = list_entry((head)->prev, typeof(*pos), member);      \
 518              prefetch(pos->member.prev), &pos->member != (head);        \
 519              pos = list_entry(pos->member.prev, typeof(*pos), member))
 520
 521 /**
 522  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
 523  * @pos:        the type * to use as a start point
 524  * @head:       the head of the list
 525  * @member:     the name of the list_struct within the struct.
 526  *
 527  * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
 528  */
 529 #define list_prepare_entry(pos, head, member) \
 530         ((pos) ? : list_entry(head, typeof(*pos), member))
 531
 532 /**
 533  * list_for_each_entry_continue - continue iteration over list of given type
 534  * @pos:        the type * to use as a loop cursor.
 535  * @head:       the head for your list.
 536  * @member:     the name of the list_struct within the struct.
 537  *
 538  * Continue to iterate over list of given type, continuing after
 539  * the current position.
 540  */
 541 #define list_for_each_entry_continue(pos, head, member)                 \
 542         for (pos = list_entry(pos->member.next, typeof(*pos), member);  \
 543              prefetch(pos->member.next), &pos->member != (head);        \
 544              pos = list_entry(pos->member.next, typeof(*pos), member))
 545
 546 /**
 547  * list_for_each_entry_continue_reverse - iterate backwards from the given point
 548  * @pos:        the type * to use as a loop cursor.
 549  * @head:       the head for your list.
 550  * @member:     the name of the list_struct within the struct.
 551  *
 552  * Start to iterate over list of given type backwards, continuing after
 553  * the current position.
 554  */
 555 #define list_for_each_entry_continue_reverse(pos, head, member)         \
 556         for (pos = list_entry(pos->member.prev, typeof(*pos), member);  \
 557              prefetch(pos->member.prev), &pos->member != (head);        \
 558              pos = list_entry(pos->member.prev, typeof(*pos), member))
 559
 560 /**
 561  * list_for_each_entry_from - iterate over list of given type from the current point
 562  * @pos:        the type * to use as a loop cursor.
 563  * @head:       the head for your list.
 564  * @member:     the name of the list_struct within the struct.
 565  *
 566  * Iterate over list of given type, continuing from current position.
 567  */
 568 #define list_for_each_entry_from(pos, head, member)                     \
 569         for (; prefetch(pos->member.next), &pos->member != (head);      \
 570              pos = list_entry(pos->member.next, typeof(*pos), member))
 571
 572 /**
 573  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 574  * @pos:        the type * to use as a loop cursor.
 575  * @n:          another type * to use as temporary storage
 576  * @head:       the head for your list.
 577  * @member:     the name of the list_struct within the struct.
 578  */
 579 #define list_for_each_entry_safe(pos, n, head, member)                  \
 580         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 581                 n = list_entry(pos->member.next, typeof(*pos), member); \
 582              &pos->member != (head);                                    \
 583              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 584
 585 /**
 586  * list_for_each_entry_safe_continue
 587  * @pos:        the type * to use as a loop cursor.
 588  * @n:          another type * to use as temporary storage
 589  * @head:       the head for your list.
 590  * @member:     the name of the list_struct within the struct.
 591  *
 592  * Iterate over list of given type, continuing after current point,
 593  * safe against removal of list entry.
 594  */
 595 #define list_for_each_entry_safe_continue(pos, n, head, member)                 \
 596         for (pos = list_entry(pos->member.next, typeof(*pos), member),          \
 597                 n = list_entry(pos->member.next, typeof(*pos), member);         \
 598              &pos->member != (head);                                            \
 599              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 600
 601 /**
 602  * list_for_each_entry_safe_from
 603  * @pos:        the type * to use as a loop cursor.
 604  * @n:          another type * to use as temporary storage
 605  * @head:       the head for your list.
 606  * @member:     the name of the list_struct within the struct.
 607  *
 608  * Iterate over list of given type from current point, safe against
 609  * removal of list entry.
 610  */
 611 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
 612         for (n = list_entry(pos->member.next, typeof(*pos), member);            \
 613              &pos->member != (head);                                            \
 614              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 615
 616 /**
 617  * list_for_each_entry_safe_reverse
 618  * @pos:        the type * to use as a loop cursor.
 619  * @n:          another type * to use as temporary storage
 620  * @head:       the head for your list.
 621  * @member:     the name of the list_struct within the struct.
 622  *
 623  * Iterate backwards over list of given type, safe against removal
 624  * of list entry.
 625  */
 626 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
 627         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
 628                 n = list_entry(pos->member.prev, typeof(*pos), member); \
 629              &pos->member != (head);                                    \
 630              pos = n, n = list_entry(n->member.prev, typeof(*n), member))
 631
 632 /**
 633  * list_for_each_rcu    -       iterate over an rcu-protected list
 634  * @pos:        the &struct list_head to use as a loop cursor.
 635  * @head:       the head for your list.
 636  *
 637  * This list-traversal primitive may safely run concurrently with
 638  * the _rcu list-mutation primitives such as list_add_rcu()
 639  * as long as the traversal is guarded by rcu_read_lock().
 640  */
 641 #define list_for_each_rcu(pos, head) \
 642         for (pos = rcu_dereference((head)->next); \
 643                 prefetch(pos->next), pos != (head); \
 644                 pos = rcu_dereference(pos->next))
 645
 646 #define __list_for_each_rcu(pos, head) \
 647         for (pos = rcu_dereference((head)->next); \
 648                 pos != (head); \
 649                 pos = rcu_dereference(pos->next))
 650
 651 /**
 652  * list_for_each_entry_rcu      -       iterate over rcu list of given type
 653  * @pos:        the type * to use as a loop cursor.
 654  * @head:       the head for your list.
 655  * @member:     the name of the list_struct within the struct.
 656  *
 657  * This list-traversal primitive may safely run concurrently with
 658  * the _rcu list-mutation primitives such as list_add_rcu()
 659  * as long as the traversal is guarded by rcu_read_lock().
 660  */
 661 #define list_for_each_entry_rcu(pos, head, member) \
 662         for (pos = list_entry(rcu_dereference((head)->next), typeof(*pos), member); \
 663                 prefetch(pos->member.next), &pos->member != (head); \
 664                 pos = list_entry(rcu_dereference(pos->member.next), typeof(*pos), member))
 665
 666
 667 /**
 668  * list_for_each_continue_rcu
 669  * @pos:        the &struct list_head to use as a loop cursor.
 670  * @head:       the head for your list.
 671  *
 672  * Iterate over an rcu-protected list, continuing after current point.
 673  *
 674  * This list-traversal primitive may safely run concurrently with
 675  * the _rcu list-mutation primitives such as list_add_rcu()
 676  * as long as the traversal is guarded by rcu_read_lock().
 677  */
 678 #define list_for_each_continue_rcu(pos, head) \
 679         for ((pos) = rcu_dereference((pos)->next); \
 680                 prefetch((pos)->next), (pos) != (head); \
 681                 (pos) = rcu_dereference((pos)->next))
 682
 683 /*
 684  * Double linked lists with a single pointer list head.
 685  * Mostly useful for hash tables where the two pointer list head is
 686  * too wasteful.
 687  * You lose the ability to access the tail in O(1).
 688  */
 689
 690 struct hlist_head {
 691         struct hlist_node *first;
 692 };
 693
 694 struct hlist_node {
 695         struct hlist_node *next, **pprev;
 696 };
 697
 698 #define HLIST_HEAD_INIT { .first = NULL }
 699 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
 700 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
 701 static inline void INIT_HLIST_NODE(struct hlist_node *h)
 702 {
 703         h->next = NULL;
 704         h->pprev = NULL;
 705 }
 706
 707 static inline int hlist_unhashed(const struct hlist_node *h)
 708 {
 709         return !h->pprev;
 710 }
 711
 712 static inline int hlist_empty(const struct hlist_head *h)
 713 {
 714         return !h->first;
 715 }
 716
 717 static inline void __hlist_del(struct hlist_node *n)
 718 {
 719         struct hlist_node *next = n->next;
 720         struct hlist_node **pprev = n->pprev;
 721         *pprev = next;
 722         if (next)
 723                 next->pprev = pprev;
 724 }
 725
 726 static inline void hlist_del(struct hlist_node *n)
 727 {
 728         __hlist_del(n);
 729         n->next = LIST_POISON1;
 730         n->pprev = LIST_POISON2;
 731 }
 732
 733 /**
 734  * hlist_del_rcu - deletes entry from hash list without re-initialization
 735  * @n: the element to delete from the hash list.
 736  *
 737  * Note: list_unhashed() on entry does not return true after this,
 738  * the entry is in an undefined state. It is useful for RCU based
 739  * lockfree traversal.
 740  *
 741  * In particular, it means that we can not poison the forward
 742  * pointers that may still be used for walking the hash list.
 743  *
 744  * The caller must take whatever precautions are necessary
 745  * (such as holding appropriate locks) to avoid racing
 746  * with another list-mutation primitive, such as hlist_add_head_rcu()
 747  * or hlist_del_rcu(), running on this same list.
 748  * However, it is perfectly legal to run concurrently with
 749  * the _rcu list-traversal primitives, such as
 750  * hlist_for_each_entry().
 751  */
 752 static inline void hlist_del_rcu(struct hlist_node *n)
 753 {
 754         __hlist_del(n);
 755         n->pprev = LIST_POISON2;
 756 }
 757
 758 static inline void hlist_del_init(struct hlist_node *n)
 759 {
 760         if (!hlist_unhashed(n)) {
 761                 __hlist_del(n);
 762                 INIT_HLIST_NODE(n);
 763         }
 764 }
 765
 766 /**
 767  * hlist_replace_rcu - replace old entry by new one
 768  * @old : the element to be replaced
 769  * @new : the new element to insert
 770  *
 771  * The @old entry will be replaced with the @new entry atomically.
 772  */
 773 static inline void hlist_replace_rcu(struct hlist_node *old,
 774                                         struct hlist_node *new)
 775 {
 776         struct hlist_node *next = old->next;
 777
 778         new->next = next;
 779         new->pprev = old->pprev;
 780         smp_wmb();
 781         if (next)
 782                 new->next->pprev = &new->next;
 783         *new->pprev = new;
 784         old->pprev = LIST_POISON2;
 785 }
 786
 787 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 788 {
 789         struct hlist_node *first = h->first;
 790         n->next = first;
 791         if (first)
 792                 first->pprev = &n->next;
 793         h->first = n;
 794         n->pprev = &h->first;
 795 }
 796
 797
 798 /**
 799  * hlist_add_head_rcu
 800  * @n: the element to add to the hash list.
 801  * @h: the list to add to.
 802  *
 803  * Description:
 804  * Adds the specified element to the specified hlist,
 805  * while permitting racing traversals.
 806  *
 807  * The caller must take whatever precautions are necessary
 808  * (such as holding appropriate locks) to avoid racing
 809  * with another list-mutation primitive, such as hlist_add_head_rcu()
 810  * or hlist_del_rcu(), running on this same list.
 811  * However, it is perfectly legal to run concurrently with
 812  * the _rcu list-traversal primitives, such as
 813  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 814  * problems on Alpha CPUs.  Regardless of the type of CPU, the
 815  * list-traversal primitive must be guarded by rcu_read_lock().
 816  */
 817 static inline void hlist_add_head_rcu(struct hlist_node *n,
 818                                         struct hlist_head *h)
 819 {
 820         struct hlist_node *first = h->first;
 821         n->next = first;
 822         n->pprev = &h->first;
 823         smp_wmb();
 824         if (first)
 825                 first->pprev = &n->next;
 826         h->first = n;
 827 }
 828
 829 /* next must be != NULL */
 830 static inline void hlist_add_before(struct hlist_node *n,
 831                                         struct hlist_node *next)
 832 {
 833         n->pprev = next->pprev;
 834         n->next = next;
 835         next->pprev = &n->next;
 836         *(n->pprev) = n;
 837 }
 838
 839 static inline void hlist_add_after(struct hlist_node *n,
 840                                         struct hlist_node *next)
 841 {
 842         next->next = n->next;
 843         n->next = next;
 844         next->pprev = &n->next;
 845
 846         if(next->next)
 847                 next->next->pprev  = &next->next;
 848 }
 849
 850 /**
 851  * hlist_add_before_rcu
 852  * @n: the new element to add to the hash list.
 853  * @next: the existing element to add the new element before.
 854  *
 855  * Description:
 856  * Adds the specified element to the specified hlist
 857  * before the specified node while permitting racing traversals.
 858  *
 859  * The caller must take whatever precautions are necessary
 860  * (such as holding appropriate locks) to avoid racing
 861  * with another list-mutation primitive, such as hlist_add_head_rcu()
 862  * or hlist_del_rcu(), running on this same list.
 863  * However, it is perfectly legal to run concurrently with
 864  * the _rcu list-traversal primitives, such as
 865  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 866  * problems on Alpha CPUs.
 867  */
 868 static inline void hlist_add_before_rcu(struct hlist_node *n,
 869                                         struct hlist_node *next)
 870 {
 871         n->pprev = next->pprev;
 872         n->next = next;
 873         smp_wmb();
 874         next->pprev = &n->next;
 875         *(n->pprev) = n;
 876 }
 877
 878 /**
 879  * hlist_add_after_rcu
 880  * @prev: the existing element to add the new element after.
 881  * @n: the new element to add to the hash list.
 882  *
 883  * Description:
 884  * Adds the specified element to the specified hlist
 885  * after the specified node while permitting racing traversals.
 886  *
 887  * The caller must take whatever precautions are necessary
 888  * (such as holding appropriate locks) to avoid racing
 889  * with another list-mutation primitive, such as hlist_add_head_rcu()
 890  * or hlist_del_rcu(), running on this same list.
 891  * However, it is perfectly legal to run concurrently with
 892  * the _rcu list-traversal primitives, such as
 893  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 894  * problems on Alpha CPUs.
 895  */
 896 static inline void hlist_add_after_rcu(struct hlist_node *prev,
 897                                        struct hlist_node *n)
 898 {
 899         n->next = prev->next;
 900         n->pprev = &prev->next;
 901         smp_wmb();
 902         prev->next = n;
 903         if (n->next)
 904                 n->next->pprev = &n->next;
 905 }
 906
 907 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
 908
 909 #define hlist_for_each(pos, head) \
 910         for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
 911              pos = pos->next)
 912
 913 #define hlist_for_each_safe(pos, n, head) \
 914         for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
 915              pos = n)
 916
 917 /**
 918  * hlist_for_each_entry - iterate over list of given type
 919  * @tpos:       the type * to use as a loop cursor.
 920  * @pos:        the &struct hlist_node to use as a loop cursor.
 921  * @head:       the head for your list.
 922  * @member:     the name of the hlist_node within the struct.
 923  */
 924 #define hlist_for_each_entry(tpos, pos, head, member)                    \
 925         for (pos = (head)->first;                                        \
 926              pos && ({ prefetch(pos->next); 1;}) &&                      \
 927                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 928              pos = pos->next)
 929
 930 /**
 931  * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
 932  * @tpos:       the type * to use as a loop cursor.
 933  * @pos:        the &struct hlist_node to use as a loop cursor.
 934  * @member:     the name of the hlist_node within the struct.
 935  */
 936 #define hlist_for_each_entry_continue(tpos, pos, member)                 \
 937         for (pos = (pos)->next;                                          \
 938              pos && ({ prefetch(pos->next); 1;}) &&                      \
 939                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 940              pos = pos->next)
 941
 942 /**
 943  * hlist_for_each_entry_from - iterate over a hlist continuing from current point
 944  * @tpos:       the type * to use as a loop cursor.
 945  * @pos:        the &struct hlist_node to use as a loop cursor.
 946  * @member:     the name of the hlist_node within the struct.
 947  */
 948 #define hlist_for_each_entry_from(tpos, pos, member)                     \
 949         for (; pos && ({ prefetch(pos->next); 1;}) &&                    \
 950                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 951              pos = pos->next)
 952
 953 /**
 954  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 955  * @tpos:       the type * to use as a loop cursor.
 956  * @pos:        the &struct hlist_node to use as a loop cursor.
 957  * @n:          another &struct hlist_node to use as temporary storage
 958  * @head:       the head for your list.
 959  * @member:     the name of the hlist_node within the struct.
 960  */
 961 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
 962         for (pos = (head)->first;                                        \
 963              pos && ({ n = pos->next; 1; }) &&                           \
 964                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 965              pos = n)
 966
 967 /**
 968  * hlist_for_each_entry_rcu - iterate over rcu list of given type
 969  * @tpos:       the type * to use as a loop cursor.
 970  * @pos:        the &struct hlist_node to use as a loop cursor.
 971  * @head:       the head for your list.
 972  * @member:     the name of the hlist_node within the struct.
 973  *
 974  * This list-traversal primitive may safely run concurrently with
 975  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
 976  * as long as the traversal is guarded by rcu_read_lock().
 977  */
 978 #define hlist_for_each_entry_rcu(tpos, pos, head, member)                \
 979         for (pos = rcu_dereference((head)->first);                       \
 980                 pos && ({ prefetch(pos->next); 1;}) &&                   \
 981                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 982              pos = rcu_dereference(pos->next))
 983
 984 #endif