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