1 #ifndef _LINUX_LIST_H  2 #define _LINUX_LIST_H  3   4 struct list_head {  5     struct list_head *next, *prev;  6 };  7   8 struct hlist_head {  9     struct hlist_node *first; 10 }; 11  12 struct hlist_node { 13     struct hlist_node *next, **pprev; 14 }; 15  16 #ifndef offsetof 17 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) 18 #endif 19  20 #ifndef container_of 21 /** 22  * container_of - cast a member of a structure out to the containing structure 23  * @ptr:    the pointer to the member. 24  * @type:    the type of the container struct this is embedded in. 25  * @member:    the name of the member within the struct. 26  * 27  */ 28 #define container_of(ptr, type, member) ({             29     const typeof(((type *)0)->member) * __mptr = (ptr);     30     (type *)((char *)__mptr - offsetof(type, member)); }) 31 #endif 32  33 #define LIST_POISON1 NULL 34 #define LIST_POISON2 NULL 35  36 /* 37  * Simple doubly linked list implementation. 38  * 39  * Some of the internal functions ("__xxx") are useful when 40  * manipulating whole lists rather than single entries, as 41  * sometimes we already know the next/prev entries and we can 42  * generate better code by using them directly rather than 43  * using the generic single-entry routines. 44  */ 45  46 #define LIST_HEAD_INIT(name) { &(name), &(name) } 47  48 #define LIST_HEAD(name)  49     struct list_head name = LIST_HEAD_INIT(name) 50  51 static inline void INIT_LIST_HEAD(struct list_head *list) 52 { 53     list->next = list; 54     list->prev = list; 55 } 56  57 /* 58  * Insert a new entry between two known consecutive entries. 59  * 60  * This is only for internal list manipulation where we know 61  * the prev/next entries already! 62  */ 63 #ifndef CONFIG_DEBUG_LIST 64 static inline void __list_add(struct list_head *new, 65                   struct list_head *prev, 66                   struct list_head *next) 67 { 68     next->prev = new; 69     new->next = next; 70     new->prev = prev; 71     prev->next = new; 72 } 73 #else 74 extern void __list_add(struct list_head *new, 75                   struct list_head *prev, 76                   struct list_head *next); 77 #endif 78  79 /** 80  * list_add - add a new entry 81  * @new: new entry to be added 82  * @head: list head to add it after 83  * 84  * Insert a new entry after the specified head. 85  * This is good for implementing stacks. 86  */ 87 static inline void list_add(struct list_head *new, struct list_head *head) 88 { 89     __list_add(new, head, head->next); 90 } 91  92  93 /** 94  * list_add_tail - add a new entry 95  * @new: new entry to be added 96  * @head: list head to add it before 97  * 98  * Insert a new entry before the specified head. 99  * This is useful for implementing queues.100  */101 static inline void list_add_tail(struct list_head *new, struct list_head *head)102 {103     __list_add(new, head->prev, head);104 }105 106 /*107  * Delete a list entry by making the prev/next entries108  * point to each other.109  *110  * This is only for internal list manipulation where we know111  * the prev/next entries already!112  */113 static inline void __list_del(struct list_head * prev, struct list_head * next)114 {115     next->prev = prev;116     prev->next = next;117 }118 119 /**120  * list_del - deletes entry from list.121  * @entry: the element to delete from the list.122  * Note: list_empty() on entry does not return true after this, the entry is123  * in an undefined state.124  */125 #ifndef CONFIG_DEBUG_LIST126 static inline void __list_del_entry(struct list_head *entry)127 {128     __list_del(entry->prev, entry->next);129 }130 131 static inline void list_del(struct list_head *entry)132 {133     __list_del(entry->prev, entry->next);134     entry->next = LIST_POISON1;135     entry->prev = LIST_POISON2;136 }137 #else138 extern void __list_del_entry(struct list_head *entry);139 extern void list_del(struct list_head *entry);140 #endif141 142 /**143  * list_replace - replace old entry by new one144  * @old : the element to be replaced145  * @new : the new element to insert146  *147  * If @old was empty, it will be overwritten.148  */149 static inline void list_replace(struct list_head *old,150                 struct list_head *new)151 {152     new->next = old->next;153     new->next->prev = new;154     new->prev = old->prev;155     new->prev->next = new;156 }157 158 static inline void list_replace_init(struct list_head *old,159                     struct list_head *new)160 {161     list_replace(old, new);162     INIT_LIST_HEAD(old);163 }164 165 /**166  * list_del_init - deletes entry from list and reinitialize it.167  * @entry: the element to delete from the list.168  */169 static inline void list_del_init(struct list_head *entry)170 {171     __list_del_entry(entry);172     INIT_LIST_HEAD(entry);173 }174 175 /**176  * list_move - delete from one list and add as another‘s head177  * @list: the entry to move178  * @head: the head that will precede our entry179  */180 static inline void list_move(struct list_head *list, struct list_head *head)181 {182     __list_del_entry(list);183     list_add(list, head);184 }185 186 /**187  * list_move_tail - delete from one list and add as another‘s tail188  * @list: the entry to move189  * @head: the head that will follow our entry190  */191 static inline void list_move_tail(struct list_head *list,192                   struct list_head *head)193 {194     __list_del_entry(list);195     list_add_tail(list, head);196 }197 198 /**199  * list_is_last - tests whether @list is the last entry in list @head200  * @list: the entry to test201  * @head: the head of the list202  */203 static inline int list_is_last(const struct list_head *list,204                 const struct list_head *head)205 {206     return list->next == head;207 }208 209 /**210  * list_empty - tests whether a list is empty211  * @head: the list to test.212  */213 static inline int list_empty(const struct list_head *head)214 {215     return head->next == head;216 }217 218 /**219  * list_empty_careful - tests whether a list is empty and not being modified220  * @head: the list to test221  *222  * Description:223  * tests whether a list is empty _and_ checks that no other CPU might be224  * in the process of modifying either member (next or prev)225  *226  * NOTE: using list_empty_careful() without synchronization227  * can only be safe if the only activity that can happen228  * to the list entry is list_del_init(). Eg. it cannot be used229  * if another CPU could re-list_add() it.230  */231 static inline int list_empty_careful(const struct list_head *head)232 {233     struct list_head *next = head->next;234     return (next == head) && (next == head->prev);235 }236 237 /**238  * list_rotate_left - rotate the list to the left239  * @head: the head of the list240  */241 static inline void list_rotate_left(struct list_head *head)242 {243     struct list_head *first;244 245     if (!list_empty(head)) {246         first = head->next;247         list_move_tail(first, head);248     }249 }250 251 /**252  * list_is_singular - tests whether a list has just one entry.253  * @head: the list to test.254  */255 static inline int list_is_singular(const struct list_head *head)256 {257     return !list_empty(head) && (head->next == head->prev);258 }259 260 static inline void __list_cut_position(struct list_head *list,261         struct list_head *head, struct list_head *entry)262 {263     struct list_head *new_first = entry->next;264     list->next = head->next;265     list->next->prev = list;266     list->prev = entry;267     entry->next = list;268     head->next = new_first;269     new_first->prev = head;270 }271 272 /**273  * list_cut_position - cut a list into two274  * @list: a new list to add all removed entries275  * @head: a list with entries276  * @entry: an entry within head, could be the head itself277  *    and if so we won‘t cut the list278  *279  * This helper moves the initial part of @head, up to and280  * including @entry, from @head to @list. You should281  * pass on @entry an element you know is on @head. @list282  * should be an empty list or a list you do not care about283  * losing its data.284  *285  */286 static inline void list_cut_position(struct list_head *list,287         struct list_head *head, struct list_head *entry)288 {289     if (list_empty(head))290         return;291     if (list_is_singular(head) &&292         (head->next != entry && head != entry))293         return;294     if (entry == head)295         INIT_LIST_HEAD(list);296     else297         __list_cut_position(list, head, entry);298 }299 300 static inline void __list_splice(const struct list_head *list,301                  struct list_head *prev,302                  struct list_head *next)303 {304     struct list_head *first = list->next;305     struct list_head *last = list->prev;306 307     first->prev = prev;308     prev->next = first;309 310     last->next = next;311     next->prev = last;312 }313 314 /**315  * list_splice - join two lists, this is designed for stacks316  * @list: the new list to add.317  * @head: the place to add it in the first list.318  */319 static inline void list_splice(const struct list_head *list,320                 struct list_head *head)321 {322     if (!list_empty(list))323         __list_splice(list, head, head->next);324 }325 326 /**327  * list_splice_tail - join two lists, each list being a queue328  * @list: the new list to add.329  * @head: the place to add it in the first list.330  */331 static inline void list_splice_tail(struct list_head *list,332                 struct list_head *head)333 {334     if (!list_empty(list))335         __list_splice(list, head->prev, head);336 }337 338 /**339  * list_splice_init - join two lists and reinitialise the emptied list.340  * @list: the new list to add.341  * @head: the place to add it in the first list.342  *343  * The list at @list is reinitialised344  */345 static inline void list_splice_init(struct list_head *list,346                     struct list_head *head)347 {348     if (!list_empty(list)) {349         __list_splice(list, head, head->next);350         INIT_LIST_HEAD(list);351     }352 }353 354 /**355  * list_splice_tail_init - join two lists and reinitialise the emptied list356  * @list: the new list to add.357  * @head: the place to add it in the first list.358  *359  * Each of the lists is a queue.360  * The list at @list is reinitialised361  */362 static inline void list_splice_tail_init(struct list_head *list,363                      struct list_head *head)364 {365     if (!list_empty(list)) {366         __list_splice(list, head->prev, head);367         INIT_LIST_HEAD(list);368     }369 }370 371 /**372  * list_entry - get the struct for this entry373  * @ptr:    the &struct list_head pointer.374  * @type:    the type of the struct this is embedded in.375  * @member:    the name of the list_struct within the struct.376  */377 #define list_entry(ptr, type, member) 378     container_of(ptr, type, member)379 380 /**381  * list_first_entry - get the first element from a list382  * @ptr:    the list head to take the element from.383  * @type:    the type of the struct this is embedded in.384  * @member:    the name of the list_struct within the struct.385  *386  * Note, that list is expected to be not empty.387  */388 #define list_first_entry(ptr, type, member) 389     list_entry((ptr)->next, type, member)390 391 /**392  * list_for_each    -    iterate over a list393  * @pos:    the &struct list_head to use as a loop cursor.394  * @head:    the head for your list.395  */396 #define list_for_each(pos, head) 397     for (pos = (head)->next; pos != (head); pos = pos->next)398 399 /**400  * __list_for_each    -    iterate over a list401  * @pos:    the &struct list_head to use as a loop cursor.402  * @head:    the head for your list.403  *404  * This variant doesn‘t differ from list_for_each() any more.405  * We don‘t do prefetching in either case.406  */407 #define __list_for_each(pos, head) 408     for (pos = (head)->next; pos != (head); pos = pos->next)409 410 /**411  * list_for_each_prev    -    iterate over a list backwards412  * @pos:    the &struct list_head to use as a loop cursor.413  * @head:    the head for your list.414  */415 #define list_for_each_prev(pos, head) 416     for (pos = (head)->prev; pos != (head); pos = pos->prev)417 418 /**419  * list_for_each_safe - iterate over a list safe against removal of list entry420  * @pos:    the &struct list_head to use as a loop cursor.421  * @n:        another &struct list_head to use as temporary storage422  * @head:    the head for your list.423  */424 #define list_for_each_safe(pos, n, head) 425     for (pos = (head)->next, n = pos->next; pos != (head); 426         pos = n, n = pos->next)427 428 /**429  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry430  * @pos:    the &struct list_head to use as a loop cursor.431  * @n:        another &struct list_head to use as temporary storage432  * @head:    the head for your list.433  */434 #define list_for_each_prev_safe(pos, n, head) 435     for (pos = (head)->prev, n = pos->prev; 436          pos != (head); 437          pos = n, n = pos->prev)438 439 /**440  * list_for_each_entry    -    iterate over list of given type441  * @pos:    the type * to use as a loop cursor.442  * @head:    the head for your list.443  * @member:    the name of the list_struct within the struct.444  */445 #define list_for_each_entry(pos, head, member)                446     for (pos = list_entry((head)->next, typeof(*pos), member);    447          &pos->member != (head);     448          pos = list_entry(pos->member.next, typeof(*pos), member))449 450 /**451  * list_for_each_entry_reverse - iterate backwards over list of given type.452  * @pos:    the type * to use as a loop cursor.453  * @head:    the head for your list.454  * @member:    the name of the list_struct within the struct.455  */456 #define list_for_each_entry_reverse(pos, head, member)            457     for (pos = list_entry((head)->prev, typeof(*pos), member);    458          &pos->member != (head);     459          pos = list_entry(pos->member.prev, typeof(*pos), member))460 461 /**462  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()463  * @pos:    the type * to use as a start point464  * @head:    the head of the list465  * @member:    the name of the list_struct within the struct.466  *467  * Prepares a pos entry for use as a start point in list_for_each_entry_continue().468  */469 #define list_prepare_entry(pos, head, member) 470     ((pos) ? : list_entry(head, typeof(*pos), member))471 472 /**473  * list_for_each_entry_continue - continue iteration over list of given type474  * @pos:    the type * to use as a loop cursor.475  * @head:    the head for your list.476  * @member:    the name of the list_struct within the struct.477  *478  * Continue to iterate over list of given type, continuing after479  * the current position.480  */481 #define list_for_each_entry_continue(pos, head, member)         482     for (pos = list_entry(pos->member.next, typeof(*pos), member);    483          &pos->member != (head);    484          pos = list_entry(pos->member.next, typeof(*pos), member))485 486 /**487  * list_for_each_entry_continue_reverse - iterate backwards from the given point488  * @pos:    the type * to use as a loop cursor.489  * @head:    the head for your list.490  * @member:    the name of the list_struct within the struct.491  *492  * Start to iterate over list of given type backwards, continuing after493  * the current position.494  */495 #define list_for_each_entry_continue_reverse(pos, head, member)        496     for (pos = list_entry(pos->member.prev, typeof(*pos), member);    497          &pos->member != (head);    498          pos = list_entry(pos->member.prev, typeof(*pos), member))499 500 /**501  * list_for_each_entry_from - iterate over list of given type from the current point502  * @pos:    the type * to use as a loop cursor.503  * @head:    the head for your list.504  * @member:    the name of the list_struct within the struct.505  *506  * Iterate over list of given type, continuing from current position.507  */508 #define list_for_each_entry_from(pos, head, member)             509     for (; &pos->member != (head);    510          pos = list_entry(pos->member.next, typeof(*pos), member))511 512 /**513  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry514  * @pos:    the type * to use as a loop cursor.515  * @n:        another type * to use as temporary storage516  * @head:    the head for your list.517  * @member:    the name of the list_struct within the struct.518  */519 #define list_for_each_entry_safe(pos, n, head, member)            520     for (pos = list_entry((head)->next, typeof(*pos), member),    521         n = list_entry(pos->member.next, typeof(*pos), member);    522          &pos->member != (head);                     523          pos = n, n = list_entry(n->member.next, typeof(*n), member))524 525 /**526  * list_for_each_entry_safe_continue - continue list iteration safe against removal527  * @pos:    the type * to use as a loop cursor.528  * @n:        another type * to use as temporary storage529  * @head:    the head for your list.530  * @member:    the name of the list_struct within the struct.531  *532  * Iterate over list of given type, continuing after current point,533  * safe against removal of list entry.534  */535 #define list_for_each_entry_safe_continue(pos, n, head, member)         536     for (pos = list_entry(pos->member.next, typeof(*pos), member),         537         n = list_entry(pos->member.next, typeof(*pos), member);        538          &pos->member != (head);                        539          pos = n, n = list_entry(n->member.next, typeof(*n), member))540 541 /**542  * list_for_each_entry_safe_from - iterate over list from current point safe against removal543  * @pos:    the type * to use as a loop cursor.544  * @n:        another type * to use as temporary storage545  * @head:    the head for your list.546  * @member:    the name of the list_struct within the struct.547  *548  * Iterate over list of given type from current point, safe against549  * removal of list entry.550  */551 #define list_for_each_entry_safe_from(pos, n, head, member)             552     for (n = list_entry(pos->member.next, typeof(*pos), member);        553          &pos->member != (head);                        554          pos = n, n = list_entry(n->member.next, typeof(*n), member))555 556 /**557  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal558  * @pos:    the type * to use as a loop cursor.559  * @n:        another type * to use as temporary storage560  * @head:    the head for your list.561  * @member:    the name of the list_struct within the struct.562  *563  * Iterate backwards over list of given type, safe against removal564  * of list entry.565  */566 #define list_for_each_entry_safe_reverse(pos, n, head, member)        567     for (pos = list_entry((head)->prev, typeof(*pos), member),    568         n = list_entry(pos->member.prev, typeof(*pos), member);    569          &pos->member != (head);                     570          pos = n, n = list_entry(n->member.prev, typeof(*n), member))571 572 /**573  * list_safe_reset_next - reset a stale list_for_each_entry_safe loop574  * @pos:    the loop cursor used in the list_for_each_entry_safe loop575  * @n:        temporary storage used in list_for_each_entry_safe576  * @member:    the name of the list_struct within the struct.577  *578  * list_safe_reset_next is not safe to use in general if the list may be579  * modified concurrently (eg. the lock is dropped in the loop body). An580  * exception to this is if the cursor element (pos) is pinned in the list,581  * and list_safe_reset_next is called after re-taking the lock and before582  * completing the current iteration of the loop body.583  */584 #define list_safe_reset_next(pos, n, member)                585     n = list_entry(pos->member.next, typeof(*pos), member)586 587 /*588  * Double linked lists with a single pointer list head.589  * Mostly useful for hash tables where the two pointer list head is590  * too wasteful.591  * You lose the ability to access the tail in O(1).592  */593 594 #define HLIST_HEAD_INIT { .first = NULL }595 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }596 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)597 static inline void INIT_HLIST_NODE(struct hlist_node *h)598 {599     h->next = NULL;600     h->pprev = NULL;601 }602 603 static inline int hlist_unhashed(const struct hlist_node *h)604 {605     return !h->pprev;606 }607 608 static inline int hlist_empty(const struct hlist_head *h)609 {610     return !h->first;611 }612 613 static inline void __hlist_del(struct hlist_node *n)614 {615     struct hlist_node *next = n->next;616     struct hlist_node **pprev = n->pprev;617     *pprev = next;618     if (next)619         next->pprev = pprev;620 }621 622 static inline void hlist_del(struct hlist_node *n)623 {624     __hlist_del(n);625     n->next = LIST_POISON1;626     n->pprev = LIST_POISON2;627 }628 629 static inline void hlist_del_init(struct hlist_node *n)630 {631     if (!hlist_unhashed(n)) {632         __hlist_del(n);633         INIT_HLIST_NODE(n);634     }635 }636 637 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)638 {639     struct hlist_node *first = h->first;640     n->next = first;641     if (first)642         first->pprev = &n->next;643     h->first = n;644     n->pprev = &h->first;645 }646 647 /* next must be != NULL */648 static inline void hlist_add_before(struct hlist_node *n,649                     struct hlist_node *next)650 {651     n->pprev = next->pprev;652     n->next = next;653     next->pprev = &n->next;654     *(n->pprev) = n;655 }656 657 static inline void hlist_add_after(struct hlist_node *n,658                     struct hlist_node *next)659 {660     next->next = n->next;661     n->next = next;662     next->pprev = &n->next;663 664     if(next->next)665         next->next->pprev  = &next->next;666 }667 668 /* after that we‘ll appear to be on some hlist and hlist_del will work */669 static inline void hlist_add_fake(struct hlist_node *n)670 {671     n->pprev = &n->next;672 }673 674 /*675  * Move a list from one list head to another. Fixup the pprev676  * reference of the first entry if it exists.677  */678 static inline void hlist_move_list(struct hlist_head *old,679                    struct hlist_head *new)680 {681     new->first = old->first;682     if (new->first)683         new->first->pprev = &new->first;684     old->first = NULL;685 }686 687 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)688 689 #define hlist_for_each(pos, head) 690     for (pos = (head)->first; pos ; pos = pos->next)691 692 #define hlist_for_each_safe(pos, n, head) 693     for (pos = (head)->first; pos && ({ n = pos->next; 1; }); 694          pos = n)695 696 /**697  * hlist_for_each_entry    - iterate over list of given type698  * @tpos:    the type * to use as a loop cursor.699  * @pos:    the &struct hlist_node to use as a loop cursor.700  * @head:    the head for your list.701  * @member:    the name of the hlist_node within the struct.702  */703 #define hlist_for_each_entry(tpos, pos, head, member)             704     for (pos = (head)->first;                     705          pos &&                             706         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); 707          pos = pos->next)708 709 /**710  * hlist_for_each_entry_continue - iterate over a hlist continuing after current point711  * @tpos:    the type * to use as a loop cursor.712  * @pos:    the &struct hlist_node to use as a loop cursor.713  * @member:    the name of the hlist_node within the struct.714  */715 #define hlist_for_each_entry_continue(tpos, pos, member)         716     for (pos = (pos)->next;                         717          pos &&                             718         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); 719          pos = pos->next)720 721 /**722  * hlist_for_each_entry_from - iterate over a hlist continuing from current point723  * @tpos:    the type * to use as a loop cursor.724  * @pos:    the &struct hlist_node to use as a loop cursor.725  * @member:    the name of the hlist_node within the struct.726  */727 #define hlist_for_each_entry_from(tpos, pos, member)             728     for (; pos &&                             729         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); 730          pos = pos->next)731 732 /**733  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry734  * @tpos:    the type * to use as a loop cursor.735  * @pos:    the &struct hlist_node to use as a loop cursor.736  * @n:        another &struct hlist_node to use as temporary storage737  * @head:    the head for your list.738  * @member:    the name of the hlist_node within the struct.739  */740 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)          741     for (pos = (head)->first;                     742          pos && ({ n = pos->next; 1; }) &&                  743         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); 744          pos = n)745 746 #endif