git.itanic.dy.fi Git - scan-pagemap/blob - list.h

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