Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. #ifndef _LINUX_LIST_H
  2. #define _LINUX_LIST_H
  3.  
  4. #define LIST_POISON1  ((void *) 0x80000000)
  5. #define LIST_POISON2  ((void *) 0x80001000)
  6.  
  7.  
  8. #define container_of(ptr, type, member) ({          \
  9.     const __typeof__( ((type *)0)->member ) *__mptr = (ptr);    \
  10.     (type *)( (char *)__mptr - __builtin_offsetof(type,member) );})
  11.  
  12. struct list_head
  13. {
  14.     struct list_head *next;
  15.     struct list_head *prev;
  16. };
  17.  
  18. /*
  19.  * Simple doubly linked list implementation.
  20.  *
  21.  * Some of the internal functions ("__xxx") are useful when
  22.  * manipulating whole lists rather than single entries, as
  23.  * sometimes we already know the next/prev entries and we can
  24.  * generate better code by using them directly rather than
  25.  * using the generic single-entry routines.
  26.  */
  27.  
  28. #define LIST_HEAD_INIT(name) { &(name), &(name) }
  29.  
  30. #define LIST_HEAD(name) \
  31.         struct list_head name = LIST_HEAD_INIT(name)
  32.  
  33. static inline void INIT_LIST_HEAD(struct list_head *list)
  34. {
  35.         list->next = list;
  36.         list->prev = list;
  37. }
  38.  
  39. static inline void __list_add(struct list_head *new,
  40.                               struct list_head *prev,
  41.                               struct list_head *next)
  42. {
  43.         next->prev = new;
  44.         new->next = next;
  45.         new->prev = prev;
  46.         prev->next = new;
  47. }
  48.  
  49. /**
  50.  * list_add - add a new entry
  51.  * @new: new entry to be added
  52.  * @head: list head to add it after
  53.  *
  54.  * Insert a new entry after the specified head.
  55.  * This is good for implementing stacks.
  56.  */
  57. static inline void list_add(struct list_head *new, struct list_head *head)
  58. {
  59.         __list_add(new, head, head->next);
  60. }
  61.  
  62.  
  63. /**
  64.  * list_add_tail - add a new entry
  65.  * @new: new entry to be added
  66.  * @head: list head to add it before
  67.  *
  68.  * Insert a new entry before the specified head.
  69.  * This is useful for implementing queues.
  70.  */
  71. static inline void list_add_tail(struct list_head *new, struct list_head *head)
  72. {
  73.         __list_add(new, head->prev, head);
  74. }
  75.  
  76. /*
  77.  * Delete a list entry by making the prev/next entries
  78.  * point to each other.
  79.  *
  80.  * This is only for internal list manipulation where we know
  81.  * the prev/next entries already!
  82.  */
  83. static inline void __list_del(struct list_head * prev, struct list_head * next)
  84. {
  85.         next->prev = prev;
  86.         prev->next = next;
  87. }
  88.  
  89. /**
  90.  * list_del - deletes entry from list.
  91.  * @entry: the element to delete from the list.
  92.  * Note: list_empty() on entry does not return true after this, the entry is
  93.  * in an undefined state.
  94.  */
  95. static inline void __list_del_entry(struct list_head *entry)
  96. {
  97.         __list_del(entry->prev, entry->next);
  98. }
  99.  
  100. static inline void list_del(struct list_head *entry)
  101. {
  102.         __list_del(entry->prev, entry->next);
  103.         entry->next = LIST_POISON1;
  104.         entry->prev = LIST_POISON2;
  105. }
  106.  
  107. /**
  108.  * list_replace - replace old entry by new one
  109.  * @old : the element to be replaced
  110.  * @new : the new element to insert
  111.  *
  112.  * If @old was empty, it will be overwritten.
  113.  */
  114. static inline void list_replace(struct list_head *old,
  115.                                 struct list_head *new)
  116. {
  117.         new->next = old->next;
  118.         new->next->prev = new;
  119.         new->prev = old->prev;
  120.         new->prev->next = new;
  121. }
  122.  
  123. static inline void list_replace_init(struct list_head *old,
  124.                                         struct list_head *new)
  125. {
  126.         list_replace(old, new);
  127.         INIT_LIST_HEAD(old);
  128. }
  129.  
  130. /**
  131.  * list_del_init - deletes entry from list and reinitialize it.
  132.  * @entry: the element to delete from the list.
  133.  */
  134. static inline void list_del_init(struct list_head *entry)
  135. {
  136.         __list_del_entry(entry);
  137.         INIT_LIST_HEAD(entry);
  138. }
  139.  
  140. /**
  141.  * list_move - delete from one list and add as another's head
  142.  * @list: the entry to move
  143.  * @head: the head that will precede our entry
  144.  */
  145. static inline void list_move(struct list_head *list, struct list_head *head)
  146. {
  147.         __list_del_entry(list);
  148.         list_add(list, head);
  149. }
  150.  
  151. /**
  152.  * list_move_tail - delete from one list and add as another's tail
  153.  * @list: the entry to move
  154.  * @head: the head that will follow our entry
  155.  */
  156. static inline void list_move_tail(struct list_head *list,
  157.                                   struct list_head *head)
  158. {
  159.         __list_del_entry(list);
  160.         list_add_tail(list, head);
  161. }
  162.  
  163. /**
  164.  * list_is_last - tests whether @list is the last entry in list @head
  165.  * @list: the entry to test
  166.  * @head: the head of the list
  167.  */
  168. static inline int list_is_last(const struct list_head *list,
  169.                                 const struct list_head *head)
  170. {
  171.         return list->next == head;
  172. }
  173.  
  174. /**
  175.  * list_empty - tests whether a list is empty
  176.  * @head: the list to test.
  177.  */
  178. static inline int list_empty(const struct list_head *head)
  179. {
  180.         return head->next == head;
  181. }
  182.  
  183. /**
  184.  * list_empty_careful - tests whether a list is empty and not being modified
  185.  * @head: the list to test
  186.  *
  187.  * Description:
  188.  * tests whether a list is empty _and_ checks that no other CPU might be
  189.  * in the process of modifying either member (next or prev)
  190.  *
  191.  * NOTE: using list_empty_careful() without synchronization
  192.  * can only be safe if the only activity that can happen
  193.  * to the list entry is list_del_init(). Eg. it cannot be used
  194.  * if another CPU could re-list_add() it.
  195.  */
  196. static inline int list_empty_careful(const struct list_head *head)
  197. {
  198.         struct list_head *next = head->next;
  199.         return (next == head) && (next == head->prev);
  200. }
  201.  
  202. /**
  203.  * list_rotate_left - rotate the list to the left
  204.  * @head: the head of the list
  205.  */
  206. static inline void list_rotate_left(struct list_head *head)
  207. {
  208.         struct list_head *first;
  209.  
  210.         if (!list_empty(head)) {
  211.                 first = head->next;
  212.                 list_move_tail(first, head);
  213.         }
  214. }
  215.  
  216. /**
  217.  * list_is_singular - tests whether a list has just one entry.
  218.  * @head: the list to test.
  219.  */
  220. static inline int list_is_singular(const struct list_head *head)
  221. {
  222.         return !list_empty(head) && (head->next == head->prev);
  223. }
  224.  
  225. static inline void __list_cut_position(struct list_head *list,
  226.                 struct list_head *head, struct list_head *entry)
  227. {
  228.         struct list_head *new_first = entry->next;
  229.         list->next = head->next;
  230.         list->next->prev = list;
  231.         list->prev = entry;
  232.         entry->next = list;
  233.         head->next = new_first;
  234.         new_first->prev = head;
  235. }
  236.  
  237. /**
  238.  * list_cut_position - cut a list into two
  239.  * @list: a new list to add all removed entries
  240.  * @head: a list with entries
  241.  * @entry: an entry within head, could be the head itself
  242.  *      and if so we won't cut the list
  243.  *
  244.  * This helper moves the initial part of @head, up to and
  245.  * including @entry, from @head to @list. You should
  246.  * pass on @entry an element you know is on @head. @list
  247.  * should be an empty list or a list you do not care about
  248.  * losing its data.
  249.  *
  250.  */
  251. static inline void list_cut_position(struct list_head *list,
  252.                 struct list_head *head, struct list_head *entry)
  253. {
  254.         if (list_empty(head))
  255.                 return;
  256.         if (list_is_singular(head) &&
  257.                 (head->next != entry && head != entry))
  258.                 return;
  259.         if (entry == head)
  260.                 INIT_LIST_HEAD(list);
  261.         else
  262.                 __list_cut_position(list, head, entry);
  263. }
  264.  
  265. static inline void __list_splice(const struct list_head *list,
  266.                                  struct list_head *prev,
  267.                                  struct list_head *next)
  268. {
  269.         struct list_head *first = list->next;
  270.         struct list_head *last = list->prev;
  271.  
  272.         first->prev = prev;
  273.         prev->next = first;
  274.  
  275.         last->next = next;
  276.         next->prev = last;
  277. }
  278.  
  279. /**
  280.  * list_splice - join two lists, this is designed for stacks
  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(const struct list_head *list,
  285.                                 struct list_head *head)
  286. {
  287.         if (!list_empty(list))
  288.                 __list_splice(list, head, head->next);
  289. }
  290.  
  291. /**
  292.  * list_splice_tail - join two lists, each list being a queue
  293.  * @list: the new list to add.
  294.  * @head: the place to add it in the first list.
  295.  */
  296. static inline void list_splice_tail(struct list_head *list,
  297.                                 struct list_head *head)
  298. {
  299.         if (!list_empty(list))
  300.                 __list_splice(list, head->prev, head);
  301. }
  302.  
  303. /**
  304.  * list_splice_init - join two lists and reinitialise the emptied list.
  305.  * @list: the new list to add.
  306.  * @head: the place to add it in the first list.
  307.  *
  308.  * The list at @list is reinitialised
  309.  */
  310. static inline void list_splice_init(struct list_head *list,
  311.                                     struct list_head *head)
  312. {
  313.         if (!list_empty(list)) {
  314.                 __list_splice(list, head, head->next);
  315.                 INIT_LIST_HEAD(list);
  316.         }
  317. }
  318.  
  319. /**
  320.  * list_splice_tail_init - join two lists and reinitialise the emptied list
  321.  * @list: the new list to add.
  322.  * @head: the place to add it in the first list.
  323.  *
  324.  * Each of the lists is a queue.
  325.  * The list at @list is reinitialised
  326.  */
  327. static inline void list_splice_tail_init(struct list_head *list,
  328.                                          struct list_head *head)
  329. {
  330.         if (!list_empty(list)) {
  331.                 __list_splice(list, head->prev, head);
  332.                 INIT_LIST_HEAD(list);
  333.         }
  334. }
  335.  
  336. /**
  337.  * list_entry - get the struct for this entry
  338.  * @ptr:        the &struct list_head pointer.
  339.  * @type:       the type of the struct this is embedded in.
  340.  * @member:     the name of the list_head within the struct.
  341.  */
  342. #define list_entry(ptr, type, member) \
  343.         container_of(ptr, type, member)
  344.  
  345. /**
  346.  * list_first_entry - get the first element from a list
  347.  * @ptr:        the list head to take the element from.
  348.  * @type:       the type of the struct this is embedded in.
  349.  * @member:     the name of the list_head within the struct.
  350.  *
  351.  * Note, that list is expected to be not empty.
  352.  */
  353. #define list_first_entry(ptr, type, member) \
  354.         list_entry((ptr)->next, type, member)
  355.  
  356. /**
  357.  * list_last_entry - get the last element from a list
  358.  * @ptr:        the list head to take the element from.
  359.  * @type:       the type of the struct this is embedded in.
  360.  * @member:     the name of the list_head within the struct.
  361.  *
  362.  * Note, that list is expected to be not empty.
  363.  */
  364. #define list_last_entry(ptr, type, member) \
  365.         list_entry((ptr)->prev, type, member)
  366.  
  367. /**
  368.  * list_first_entry_or_null - get the first element from a list
  369.  * @ptr:        the list head to take the element from.
  370.  * @type:       the type of the struct this is embedded in.
  371.  * @member:     the name of the list_head within the struct.
  372.  *
  373.  * Note that if the list is empty, it returns NULL.
  374.  */
  375. #define list_first_entry_or_null(ptr, type, member) \
  376.         (!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
  377.  
  378. /**
  379.  * list_next_entry - get the next element in list
  380.  * @pos:        the type * to cursor
  381.  * @member:     the name of the list_head within the struct.
  382.  */
  383. #define list_next_entry(pos, member) \
  384.     list_entry((pos)->member.next, __typeof__(*(pos)), member)
  385.  
  386. /**
  387.  * list_prev_entry - get the prev element in list
  388.  * @pos:        the type * to cursor
  389.  * @member:     the name of the list_head within the struct.
  390.  */
  391. #define list_prev_entry(pos, member) \
  392.     list_entry((pos)->member.prev, __typeof__(*(pos)), member)
  393.  
  394. /**
  395.  * list_for_each        -       iterate over a list
  396.  * @pos:        the &struct list_head to use as a loop cursor.
  397.  * @head:       the head for your list.
  398.  */
  399. #define list_for_each(pos, head) \
  400.         for (pos = (head)->next; pos != (head); pos = pos->next)
  401.  
  402. /**
  403.  * list_for_each_prev   -       iterate over a list backwards
  404.  * @pos:        the &struct list_head to use as a loop cursor.
  405.  * @head:       the head for your list.
  406.  */
  407. #define list_for_each_prev(pos, head) \
  408.         for (pos = (head)->prev; pos != (head); pos = pos->prev)
  409.  
  410. /**
  411.  * list_for_each_safe - iterate over a list safe against removal of list entry
  412.  * @pos:        the &struct list_head to use as a loop cursor.
  413.  * @n:          another &struct list_head to use as temporary storage
  414.  * @head:       the head for your list.
  415.  */
  416. #define list_for_each_safe(pos, n, head) \
  417.         for (pos = (head)->next, n = pos->next; pos != (head); \
  418.                 pos = n, n = pos->next)
  419.  
  420. /**
  421.  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
  422.  * @pos:        the &struct list_head to use as a loop cursor.
  423.  * @n:          another &struct list_head to use as temporary storage
  424.  * @head:       the head for your list.
  425.  */
  426. #define list_for_each_prev_safe(pos, n, head) \
  427.         for (pos = (head)->prev, n = pos->prev; \
  428.              pos != (head); \
  429.              pos = n, n = pos->prev)
  430.  
  431. /**
  432.  * list_for_each_entry  -       iterate over list of given type
  433.  * @pos:        the type * to use as a loop cursor.
  434.  * @head:       the head for your list.
  435.  * @member:     the name of the list_head within the struct.
  436.  */
  437. #define list_for_each_entry(pos, head, member)                          \
  438.     for (pos = list_first_entry(head, __typeof__(*pos), member);  \
  439.              &pos->member != (head);                                    \
  440.              pos = list_next_entry(pos, member))
  441.  
  442. /**
  443.  * list_for_each_entry_reverse - iterate backwards over list of given type.
  444.  * @pos:        the type * to use as a loop cursor.
  445.  * @head:       the head for your list.
  446.  * @member:     the name of the list_head within the struct.
  447.  */
  448. #define list_for_each_entry_reverse(pos, head, member)                  \
  449.     for (pos = list_last_entry(head, __typeof__(*pos), member);       \
  450.              &pos->member != (head);                                    \
  451.              pos = list_prev_entry(pos, member))
  452.  
  453. /**
  454.  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
  455.  * @pos:        the type * to use as a start point
  456.  * @head:       the head of the list
  457.  * @member:     the name of the list_head within the struct.
  458.  *
  459.  * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
  460.  */
  461. #define list_prepare_entry(pos, head, member) \
  462.     ((pos) ? : list_entry(head, __typeof__(*pos), member))
  463.  
  464. /**
  465.  * list_for_each_entry_continue - continue iteration over list of given type
  466.  * @pos:        the type * to use as a loop cursor.
  467.  * @head:       the head for your list.
  468.  * @member:     the name of the list_head within the struct.
  469.  *
  470.  * Continue to iterate over list of given type, continuing after
  471.  * the current position.
  472.  */
  473. #define list_for_each_entry_continue(pos, head, member)                 \
  474.         for (pos = list_next_entry(pos, member);                        \
  475.              &pos->member != (head);                                    \
  476.              pos = list_next_entry(pos, member))
  477.  
  478. /**
  479.  * list_for_each_entry_continue_reverse - iterate backwards from the given point
  480.  * @pos:        the type * to use as a loop cursor.
  481.  * @head:       the head for your list.
  482.  * @member:     the name of the list_head within the struct.
  483.  *
  484.  * Start to iterate over list of given type backwards, continuing after
  485.  * the current position.
  486.  */
  487. #define list_for_each_entry_continue_reverse(pos, head, member)         \
  488.         for (pos = list_prev_entry(pos, member);                        \
  489.              &pos->member != (head);                                    \
  490.              pos = list_prev_entry(pos, member))
  491.  
  492. /**
  493.  * list_for_each_entry_from - iterate over list of given type from the current point
  494.  * @pos:        the type * to use as a loop cursor.
  495.  * @head:       the head for your list.
  496.  * @member:     the name of the list_head within the struct.
  497.  *
  498.  * Iterate over list of given type, continuing from current position.
  499.  */
  500. #define list_for_each_entry_from(pos, head, member)                     \
  501.         for (; &pos->member != (head);                                  \
  502.              pos = list_next_entry(pos, member))
  503.  
  504. /**
  505.  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
  506.  * @pos:        the type * to use as a loop cursor.
  507.  * @n:          another type * to use as temporary storage
  508.  * @head:       the head for your list.
  509.  * @member:     the name of the list_head within the struct.
  510.  */
  511. #define list_for_each_entry_safe(pos, n, head, member)                  \
  512.     for (pos = list_first_entry(head, __typeof__(*pos), member),   \
  513.                 n = list_next_entry(pos, member);                       \
  514.              &pos->member != (head);                                    \
  515.              pos = n, n = list_next_entry(n, member))
  516.  
  517. /**
  518.  * list_for_each_entry_safe_continue - continue list iteration safe against removal
  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_head within the struct.
  523.  *
  524.  * Iterate over list of given type, continuing after current point,
  525.  * safe against removal of list entry.
  526.  */
  527. #define list_for_each_entry_safe_continue(pos, n, head, member)                 \
  528.         for (pos = list_next_entry(pos, member),                                \
  529.                 n = list_next_entry(pos, member);                               \
  530.              &pos->member != (head);                                            \
  531.              pos = n, n = list_next_entry(n, member))
  532.  
  533. /**
  534.  * list_for_each_entry_safe_from - iterate over list from current point safe against removal
  535.  * @pos:        the type * to use as a loop cursor.
  536.  * @n:          another type * to use as temporary storage
  537.  * @head:       the head for your list.
  538.  * @member:     the name of the list_head within the struct.
  539.  *
  540.  * Iterate over list of given type from current point, safe against
  541.  * removal of list entry.
  542.  */
  543. #define list_for_each_entry_safe_from(pos, n, head, member)                     \
  544.         for (n = list_next_entry(pos, member);                                  \
  545.              &pos->member != (head);                                            \
  546.              pos = n, n = list_next_entry(n, member))
  547.  
  548. /**
  549.  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
  550.  * @pos:        the type * to use as a loop cursor.
  551.  * @n:          another type * to use as temporary storage
  552.  * @head:       the head for your list.
  553.  * @member:     the name of the list_head within the struct.
  554.  *
  555.  * Iterate backwards over list of given type, safe against removal
  556.  * of list entry.
  557.  */
  558. #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
  559.     for (pos = list_last_entry(head, __typeof__(*pos), member),       \
  560.                 n = list_prev_entry(pos, member);                       \
  561.              &pos->member != (head);                                    \
  562.              pos = n, n = list_prev_entry(n, member))
  563.  
  564. /**
  565.  * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
  566.  * @pos:        the loop cursor used in the list_for_each_entry_safe loop
  567.  * @n:          temporary storage used in list_for_each_entry_safe
  568.  * @member:     the name of the list_head within the struct.
  569.  *
  570.  * list_safe_reset_next is not safe to use in general if the list may be
  571.  * modified concurrently (eg. the lock is dropped in the loop body). An
  572.  * exception to this is if the cursor element (pos) is pinned in the list,
  573.  * and list_safe_reset_next is called after re-taking the lock and before
  574.  * completing the current iteration of the loop body.
  575.  */
  576. #define list_safe_reset_next(pos, n, member)                            \
  577.         n = list_next_entry(pos, member)
  578.  
  579. #endif
  580.