linux/include/linux/list.h
<<
>>
Prefs
   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
  19struct 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
  28static 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
  41static 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
  51extern 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 */
  64static inline void list_add(struct list_head *new, struct list_head *head)
  65{
  66        __list_add(new, head, head->next);
  67}
  68
  69
  70/**
  71 * list_add_tail - add a new entry
  72 * @new: new entry to be added
  73 * @head: list head to add it before
  74 *
  75 * Insert a new entry before the specified head.
  76 * This is useful for implementing queues.
  77 */
  78static inline void list_add_tail(struct list_head *new, struct list_head *head)
  79{
  80        __list_add(new, head->prev, head);
  81}
  82
  83/*
  84 * Delete a list entry by making the prev/next entries
  85 * point to each other.
  86 *
  87 * This is only for internal list manipulation where we know
  88 * the prev/next entries already!
  89 */
  90static inline void __list_del(struct list_head * prev, struct list_head * next)
  91{
  92        next->prev = prev;
  93        prev->next = next;
  94}
  95
  96/**
  97 * list_del - deletes entry from list.
  98 * @entry: the element to delete from the list.
  99 * Note: list_empty() on entry does not return true after this, the entry is
 100 * in an undefined state.
 101 */
 102#ifndef CONFIG_DEBUG_LIST
 103static inline void list_del(struct list_head *entry)
 104{
 105        __list_del(entry->prev, entry->next);
 106        entry->next = LIST_POISON1;
 107        entry->prev = LIST_POISON2;
 108}
 109#else
 110extern void list_del(struct list_head *entry);
 111#endif
 112
 113/**
 114 * list_replace - replace old entry by new one
 115 * @old : the element to be replaced
 116 * @new : the new element to insert
 117 *
 118 * If @old was empty, it will be overwritten.
 119 */
 120static inline void list_replace(struct list_head *old,
 121                                struct list_head *new)
 122{
 123        new->next = old->next;
 124        new->next->prev = new;
 125        new->prev = old->prev;
 126        new->prev->next = new;
 127}
 128
 129static inline void list_replace_init(struct list_head *old,
 130                                        struct list_head *new)
 131{
 132        list_replace(old, new);
 133        INIT_LIST_HEAD(old);
 134}
 135
 136/**
 137 * list_del_init - deletes entry from list and reinitialize it.
 138 * @entry: the element to delete from the list.
 139 */
 140static inline void list_del_init(struct list_head *entry)
 141{
 142        __list_del(entry->prev, entry->next);
 143        INIT_LIST_HEAD(entry);
 144}
 145
 146/**
 147 * list_move - delete from one list and add as another's head
 148 * @list: the entry to move
 149 * @head: the head that will precede our entry
 150 */
 151static inline void list_move(struct list_head *list, struct list_head *head)
 152{
 153        __list_del(list->prev, list->next);
 154        list_add(list, head);
 155}
 156
 157/**
 158 * list_move_tail - delete from one list and add as another's tail
 159 * @list: the entry to move
 160 * @head: the head that will follow our entry
 161 */
 162static inline void list_move_tail(struct list_head *list,
 163                                  struct list_head *head)
 164{
 165        __list_del(list->prev, list->next);
 166        list_add_tail(list, head);
 167}
 168
 169/**
 170 * list_is_last - tests whether @list is the last entry in list @head
 171 * @list: the entry to test
 172 * @head: the head of the list
 173 */
 174static inline int list_is_last(const struct list_head *list,
 175                                const struct list_head *head)
 176{
 177        return list->next == head;
 178}
 179
 180/**
 181 * list_empty - tests whether a list is empty
 182 * @head: the list to test.
 183 */
 184static inline int list_empty(const struct list_head *head)
 185{
 186        return head->next == head;
 187}
 188
 189/**
 190 * list_empty_careful - tests whether a list is empty and not being modified
 191 * @head: the list to test
 192 *
 193 * Description:
 194 * tests whether a list is empty _and_ checks that no other CPU might be
 195 * in the process of modifying either member (next or prev)
 196 *
 197 * NOTE: using list_empty_careful() without synchronization
 198 * can only be safe if the only activity that can happen
 199 * to the list entry is list_del_init(). Eg. it cannot be used
 200 * if another CPU could re-list_add() it.
 201 */
 202static inline int list_empty_careful(const struct list_head *head)
 203{
 204        struct list_head *next = head->next;
 205        return (next == head) && (next == head->prev);
 206}
 207
 208/**
 209 * list_is_singular - tests whether a list has just one entry.
 210 * @head: the list to test.
 211 */
 212static inline int list_is_singular(const struct list_head *head)
 213{
 214        return !list_empty(head) && (head->next == head->prev);
 215}
 216
 217static inline void __list_cut_position(struct list_head *list,
 218                struct list_head *head, struct list_head *entry)
 219{
 220        struct list_head *new_first = entry->next;
 221        list->next = head->next;
 222        list->next->prev = list;
 223        list->prev = entry;
 224        entry->next = list;
 225        head->next = new_first;
 226        new_first->prev = head;
 227}
 228
 229/**
 230 * list_cut_position - cut a list into two
 231 * @list: a new list to add all removed entries
 232 * @head: a list with entries
 233 * @entry: an entry within head, could be the head itself
 234 *      and if so we won't cut the list
 235 *
 236 * This helper moves the initial part of @head, up to and
 237 * including @entry, from @head to @list. You should
 238 * pass on @entry an element you know is on @head. @list
 239 * should be an empty list or a list you do not care about
 240 * losing its data.
 241 *
 242 */
 243static inline void list_cut_position(struct list_head *list,
 244                struct list_head *head, struct list_head *entry)
 245{
 246        if (list_empty(head))
 247                return;
 248        if (list_is_singular(head) &&
 249                (head->next != entry && head != entry))
 250                return;
 251        if (entry == head)
 252                INIT_LIST_HEAD(list);
 253        else
 254                __list_cut_position(list, head, entry);
 255}
 256
 257static inline void __list_splice(const struct list_head *list,
 258                                 struct list_head *prev,
 259                                 struct list_head *next)
 260{
 261        struct list_head *first = list->next;
 262        struct list_head *last = list->prev;
 263
 264        first->prev = prev;
 265        prev->next = first;
 266
 267        last->next = next;
 268        next->prev = last;
 269}
 270
 271/**
 272 * list_splice - join two lists, this is designed for stacks
 273 * @list: the new list to add.
 274 * @head: the place to add it in the first list.
 275 */
 276static inline void list_splice(const struct list_head *list,
 277                                struct list_head *head)
 278{
 279        if (!list_empty(list))
 280                __list_splice(list, head, head->next);
 281}
 282
 283/**
 284 * list_splice_tail - join two lists, each list being a queue
 285 * @list: the new list to add.
 286 * @head: the place to add it in the first list.
 287 */
 288static inline void list_splice_tail(struct list_head *list,
 289                                struct list_head *head)
 290{
 291        if (!list_empty(list))
 292                __list_splice(list, head->prev, head);
 293}
 294
 295/**
 296 * list_splice_init - join two lists and reinitialise the emptied list.
 297 * @list: the new list to add.
 298 * @head: the place to add it in the first list.
 299 *
 300 * The list at @list is reinitialised
 301 */
 302static inline void list_splice_init(struct list_head *list,
 303                                    struct list_head *head)
 304{
 305        if (!list_empty(list)) {
 306                __list_splice(list, head, head->next);
 307                INIT_LIST_HEAD(list);
 308        }
 309}
 310
 311/**
 312 * list_splice_tail_init - join two lists and reinitialise the emptied list
 313 * @list: the new list to add.
 314 * @head: the place to add it in the first list.
 315 *
 316 * Each of the lists is a queue.
 317 * The list at @list is reinitialised
 318 */
 319static inline void list_splice_tail_init(struct list_head *list,
 320                                         struct list_head *head)
 321{
 322        if (!list_empty(list)) {
 323                __list_splice(list, head->prev, head);
 324                INIT_LIST_HEAD(list);
 325        }
 326}
 327
 328/**
 329 * list_entry - get the struct for this entry
 330 * @ptr:        the &struct list_head pointer.
 331 * @type:       the type of the struct this is embedded in.
 332 * @member:     the name of the list_struct within the struct.
 333 */
 334#define list_entry(ptr, type, member) \
 335        container_of(ptr, type, member)
 336
 337/**
 338 * list_first_entry - get the first element from a list
 339 * @ptr:        the list head to take the element from.
 340 * @type:       the type of the struct this is embedded in.
 341 * @member:     the name of the list_struct within the struct.
 342 *
 343 * Note, that list is expected to be not empty.
 344 */
 345#define list_first_entry(ptr, type, member) \
 346        list_entry((ptr)->next, type, member)
 347
 348/**
 349 * list_for_each        -       iterate over a list
 350 * @pos:        the &struct list_head to use as a loop cursor.
 351 * @head:       the head for your list.
 352 */
 353#define list_for_each(pos, head) \
 354        for (pos = (head)->next; prefetch(pos->next), pos != (head); \
 355                pos = pos->next)
 356
 357/**
 358 * __list_for_each      -       iterate over a list
 359 * @pos:        the &struct list_head to use as a loop cursor.
 360 * @head:       the head for your list.
 361 *
 362 * This variant differs from list_for_each() in that it's the
 363 * simplest possible list iteration code, no prefetching is done.
 364 * Use this for code that knows the list to be very short (empty
 365 * or 1 entry) most of the time.
 366 */
 367#define __list_for_each(pos, head) \
 368        for (pos = (head)->next; pos != (head); pos = pos->next)
 369
 370/**
 371 * list_for_each_prev   -       iterate over a list backwards
 372 * @pos:        the &struct list_head to use as a loop cursor.
 373 * @head:       the head for your list.
 374 */
 375#define list_for_each_prev(pos, head) \
 376        for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
 377                pos = pos->prev)
 378
 379/**
 380 * list_for_each_safe - iterate over a list safe against removal of list entry
 381 * @pos:        the &struct list_head to use as a loop cursor.
 382 * @n:          another &struct list_head to use as temporary storage
 383 * @head:       the head for your list.
 384 */
 385#define list_for_each_safe(pos, n, head) \
 386        for (pos = (head)->next, n = pos->next; pos != (head); \
 387                pos = n, n = pos->next)
 388
 389/**
 390 * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
 391 * @pos:        the &struct list_head to use as a loop cursor.
 392 * @n:          another &struct list_head to use as temporary storage
 393 * @head:       the head for your list.
 394 */
 395#define list_for_each_prev_safe(pos, n, head) \
 396        for (pos = (head)->prev, n = pos->prev; \
 397             prefetch(pos->prev), pos != (head); \
 398             pos = n, n = pos->prev)
 399
 400/**
 401 * list_for_each_entry  -       iterate over list of given type
 402 * @pos:        the type * to use as a loop cursor.
 403 * @head:       the head for your list.
 404 * @member:     the name of the list_struct within the struct.
 405 */
 406#define list_for_each_entry(pos, head, member)                          \
 407        for (pos = list_entry((head)->next, typeof(*pos), member);      \
 408             prefetch(pos->member.next), &pos->member != (head);        \
 409             pos = list_entry(pos->member.next, typeof(*pos), member))
 410
 411/**
 412 * list_for_each_entry_reverse - iterate backwards over list of given type.
 413 * @pos:        the type * to use as a loop cursor.
 414 * @head:       the head for your list.
 415 * @member:     the name of the list_struct within the struct.
 416 */
 417#define list_for_each_entry_reverse(pos, head, member)                  \
 418        for (pos = list_entry((head)->prev, typeof(*pos), member);      \
 419             prefetch(pos->member.prev), &pos->member != (head);        \
 420             pos = list_entry(pos->member.prev, typeof(*pos), member))
 421
 422/**
 423 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
 424 * @pos:        the type * to use as a start point
 425 * @head:       the head of the list
 426 * @member:     the name of the list_struct within the struct.
 427 *
 428 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
 429 */
 430#define list_prepare_entry(pos, head, member) \
 431        ((pos) ? : list_entry(head, typeof(*pos), member))
 432
 433/**
 434 * list_for_each_entry_continue - continue iteration over list of given type
 435 * @pos:        the type * to use as a loop cursor.
 436 * @head:       the head for your list.
 437 * @member:     the name of the list_struct within the struct.
 438 *
 439 * Continue to iterate over list of given type, continuing after
 440 * the current position.
 441 */
 442#define list_for_each_entry_continue(pos, head, member)                 \
 443        for (pos = list_entry(pos->member.next, typeof(*pos), member);  \
 444             prefetch(pos->member.next), &pos->member != (head);        \
 445             pos = list_entry(pos->member.next, typeof(*pos), member))
 446
 447/**
 448 * list_for_each_entry_continue_reverse - iterate backwards from the given point
 449 * @pos:        the type * to use as a loop cursor.
 450 * @head:       the head for your list.
 451 * @member:     the name of the list_struct within the struct.
 452 *
 453 * Start to iterate over list of given type backwards, continuing after
 454 * the current position.
 455 */
 456#define list_for_each_entry_continue_reverse(pos, head, member)         \
 457        for (pos = list_entry(pos->member.prev, typeof(*pos), member);  \
 458             prefetch(pos->member.prev), &pos->member != (head);        \
 459             pos = list_entry(pos->member.prev, typeof(*pos), member))
 460
 461/**
 462 * list_for_each_entry_from - iterate over list of given type from the current point
 463 * @pos:        the type * to use as a loop cursor.
 464 * @head:       the head for your list.
 465 * @member:     the name of the list_struct within the struct.
 466 *
 467 * Iterate over list of given type, continuing from current position.
 468 */
 469#define list_for_each_entry_from(pos, head, member)                     \
 470        for (; prefetch(pos->member.next), &pos->member != (head);      \
 471             pos = list_entry(pos->member.next, typeof(*pos), member))
 472
 473/**
 474 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 475 * @pos:        the type * to use as a loop cursor.
 476 * @n:          another type * to use as temporary storage
 477 * @head:       the head for your list.
 478 * @member:     the name of the list_struct within the struct.
 479 */
 480#define list_for_each_entry_safe(pos, n, head, member)                  \
 481        for (pos = list_entry((head)->next, typeof(*pos), member),      \
 482                n = list_entry(pos->member.next, typeof(*pos), member); \
 483             &pos->member != (head);                                    \
 484             pos = n, n = list_entry(n->member.next, typeof(*n), member))
 485
 486/**
 487 * list_for_each_entry_safe_continue
 488 * @pos:        the type * to use as a loop cursor.
 489 * @n:          another type * to use as temporary storage
 490 * @head:       the head for your list.
 491 * @member:     the name of the list_struct within the struct.
 492 *
 493 * Iterate over list of given type, continuing after current point,
 494 * safe against removal of list entry.
 495 */
 496#define list_for_each_entry_safe_continue(pos, n, head, member)                 \
 497        for (pos = list_entry(pos->member.next, typeof(*pos), member),          \
 498                n = list_entry(pos->member.next, typeof(*pos), member);         \
 499             &pos->member != (head);                                            \
 500             pos = n, n = list_entry(n->member.next, typeof(*n), member))
 501
 502/**
 503 * list_for_each_entry_safe_from
 504 * @pos:        the type * to use as a loop cursor.
 505 * @n:          another type * to use as temporary storage
 506 * @head:       the head for your list.
 507 * @member:     the name of the list_struct within the struct.
 508 *
 509 * Iterate over list of given type from current point, safe against
 510 * removal of list entry.
 511 */
 512#define list_for_each_entry_safe_from(pos, n, head, member)                     \
 513        for (n = list_entry(pos->member.next, typeof(*pos), member);            \
 514             &pos->member != (head);                                            \
 515             pos = n, n = list_entry(n->member.next, typeof(*n), member))
 516
 517/**
 518 * list_for_each_entry_safe_reverse
 519 * @pos:        the type * to use as a loop cursor.
 520 * @n:          another type * to use as temporary storage
 521 * @head:       the head for your list.
 522 * @member:     the name of the list_struct within the struct.
 523 *
 524 * Iterate backwards over list of given type, safe against removal
 525 * of list entry.
 526 */
 527#define list_for_each_entry_safe_reverse(pos, n, head, member)          \
 528        for (pos = list_entry((head)->prev, typeof(*pos), member),      \
 529                n = list_entry(pos->member.prev, typeof(*pos), member); \
 530             &pos->member != (head);                                    \
 531             pos = n, n = list_entry(n->member.prev, typeof(*n), member))
 532
 533/*
 534 * Double linked lists with a single pointer list head.
 535 * Mostly useful for hash tables where the two pointer list head is
 536 * too wasteful.
 537 * You lose the ability to access the tail in O(1).
 538 */
 539
 540struct hlist_head {
 541        struct hlist_node *first;
 542};
 543
 544struct hlist_node {
 545        struct hlist_node *next, **pprev;
 546};
 547
 548#define HLIST_HEAD_INIT { .first = NULL }
 549#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
 550#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
 551static inline void INIT_HLIST_NODE(struct hlist_node *h)
 552{
 553        h->next = NULL;
 554        h->pprev = NULL;
 555}
 556
 557static inline int hlist_unhashed(const struct hlist_node *h)
 558{
 559        return !h->pprev;
 560}
 561
 562static inline int hlist_empty(const struct hlist_head *h)
 563{
 564        return !h->first;
 565}
 566
 567static inline void __hlist_del(struct hlist_node *n)
 568{
 569        struct hlist_node *next = n->next;
 570        struct hlist_node **pprev = n->pprev;
 571        *pprev = next;
 572        if (next)
 573                next->pprev = pprev;
 574}
 575
 576static inline void hlist_del(struct hlist_node *n)
 577{
 578        __hlist_del(n);
 579        n->next = LIST_POISON1;
 580        n->pprev = LIST_POISON2;
 581}
 582
 583static inline void hlist_del_init(struct hlist_node *n)
 584{
 585        if (!hlist_unhashed(n)) {
 586                __hlist_del(n);
 587                INIT_HLIST_NODE(n);
 588        }
 589}
 590
 591static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 592{
 593        struct hlist_node *first = h->first;
 594        n->next = first;
 595        if (first)
 596                first->pprev = &n->next;
 597        h->first = n;
 598        n->pprev = &h->first;
 599}
 600
 601/* next must be != NULL */
 602static inline void hlist_add_before(struct hlist_node *n,
 603                                        struct hlist_node *next)
 604{
 605        n->pprev = next->pprev;
 606        n->next = next;
 607        next->pprev = &n->next;
 608        *(n->pprev) = n;
 609}
 610
 611static inline void hlist_add_after(struct hlist_node *n,
 612                                        struct hlist_node *next)
 613{
 614        next->next = n->next;
 615        n->next = next;
 616        next->pprev = &n->next;
 617
 618        if(next->next)
 619                next->next->pprev  = &next->next;
 620}
 621
 622/*
 623 * Move a list from one list head to another. Fixup the pprev
 624 * reference of the first entry if it exists.
 625 */
 626static inline void hlist_move_list(struct hlist_head *old,
 627                                   struct hlist_head *new)
 628{
 629        new->first = old->first;
 630        if (new->first)
 631                new->first->pprev = &new->first;
 632        old->first = NULL;
 633}
 634
 635#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
 636
 637#define hlist_for_each(pos, head) \
 638        for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
 639             pos = pos->next)
 640
 641#define hlist_for_each_safe(pos, n, head) \
 642        for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
 643             pos = n)
 644
 645/**
 646 * hlist_for_each_entry - iterate over list of given type
 647 * @tpos:       the type * to use as a loop cursor.
 648 * @pos:        the &struct hlist_node to use as a loop cursor.
 649 * @head:       the head for your list.
 650 * @member:     the name of the hlist_node within the struct.
 651 */
 652#define hlist_for_each_entry(tpos, pos, head, member)                    \
 653        for (pos = (head)->first;                                        \
 654             pos && ({ prefetch(pos->next); 1;}) &&                      \
 655                ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 656             pos = pos->next)
 657
 658/**
 659 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
 660 * @tpos:       the type * to use as a loop cursor.
 661 * @pos:        the &struct hlist_node to use as a loop cursor.
 662 * @member:     the name of the hlist_node within the struct.
 663 */
 664#define hlist_for_each_entry_continue(tpos, pos, member)                 \
 665        for (pos = (pos)->next;                                          \
 666             pos && ({ prefetch(pos->next); 1;}) &&                      \
 667                ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 668             pos = pos->next)
 669
 670/**
 671 * hlist_for_each_entry_from - iterate over a hlist continuing from current point
 672 * @tpos:       the type * to use as a loop cursor.
 673 * @pos:        the &struct hlist_node to use as a loop cursor.
 674 * @member:     the name of the hlist_node within the struct.
 675 */
 676#define hlist_for_each_entry_from(tpos, pos, member)                     \
 677        for (; pos && ({ prefetch(pos->next); 1;}) &&                    \
 678                ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 679             pos = pos->next)
 680
 681/**
 682 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 683 * @tpos:       the type * to use as a loop cursor.
 684 * @pos:        the &struct hlist_node to use as a loop cursor.
 685 * @n:          another &struct hlist_node to use as temporary storage
 686 * @head:       the head for your list.
 687 * @member:     the name of the hlist_node within the struct.
 688 */
 689#define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
 690        for (pos = (head)->first;                                        \
 691             pos && ({ n = pos->next; 1; }) &&                           \
 692                ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 693             pos = n)
 694
 695#endif
 696
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.