Subversion Repositories Kolibri OS

Rev

Rev 5725 | Blame | Compare with Previous | Last modification | View Log | RSS feed

  1. #ifndef __LIST_H__
  2. #define __LIST_H__
  3.  
  4. typedef struct _list list_t;
  5.  
  6. struct _list
  7. {
  8.     list_t *next, *prev;
  9. };
  10.  
  11. #define LIST_HEAD_INIT(name) { &(name), &(name) }
  12.  
  13. #define LIST_HEAD(name) \
  14.     list_t name = LIST_HEAD_INIT(name)
  15.  
  16. static inline void INIT_LIST_HEAD(list_t *list)
  17. {
  18.     list->next = list;
  19.     list->prev = list;
  20. }
  21.  
  22. /*
  23.  * Insert a new entry between two known consecutive entries.
  24.  *
  25.  * This is only for internal list manipulation where we know
  26.  * the prev/next entries already!
  27.  */
  28. static inline void __list_add(list_t *lnew, list_t *prev, list_t *next)
  29. {
  30.     next->prev = lnew;
  31.     lnew->next = next;
  32.     lnew->prev = prev;
  33.     prev->next = lnew;
  34. }
  35.  
  36. /**
  37.  * list_add - add a new entry
  38.  * @new: new entry to be added
  39.  * @head: list head to add it after
  40.  *
  41.  * Insert a new entry after the specified head.
  42.  * This is good for implementing stacks.
  43.  */
  44. static inline void list_add(list_t *lnew, list_t *head)
  45. {
  46.     __list_add(lnew, head, head->next);
  47. }
  48.  
  49.  
  50. /**
  51.  * list_add_tail - add a new entry
  52.  * @new: new entry to be added
  53.  * @head: list head to add it before
  54.  *
  55.  * Insert a new entry before the specified head.
  56.  * This is useful for implementing queues.
  57.  */
  58. static inline void list_add_tail(list_t *lnew, list_t *head)
  59. {
  60.     __list_add(lnew, head->prev, head);
  61. }
  62.  
  63. /*
  64.  * Delete a list entry by making the prev/next entries
  65.  * point to each other.
  66.  *
  67.  * This is only for internal list manipulation where we know
  68.  * the prev/next entries already!
  69.  */
  70. static inline void __list_del(list_t * prev, list_t * next)
  71. {
  72.     next->prev = prev;
  73.     prev->next = next;
  74. }
  75.  
  76. /**
  77.  * list_del - deletes entry from list.
  78.  * @entry: the element to delete from the list.
  79.  * Note: list_empty() on entry does not return true after this, the entry is
  80.  * in an undefined state.
  81.  */
  82. static inline void __list_del_entry(list_t *entry)
  83. {
  84.     __list_del(entry->prev, entry->next);
  85. }
  86.  
  87. static inline void list_del(list_t *entry)
  88. {
  89.     __list_del(entry->prev, entry->next);
  90.     entry->next = NULL;
  91.     entry->prev = NULL;
  92. }
  93.  
  94. /**
  95.  * list_replace - replace old entry by new one
  96.  * @old : the element to be replaced
  97.  * @new : the new element to insert
  98.  *
  99.  * If @old was empty, it will be overwritten.
  100.  */
  101. static inline void list_replace(list_t *old, list_t *lnew)
  102. {
  103.     lnew->next = old->next;
  104.     lnew->next->prev = lnew;
  105.     lnew->prev = old->prev;
  106.     lnew->prev->next = lnew;
  107. }
  108.  
  109. static inline void list_replace_init(list_t *old, list_t *lnew)
  110. {
  111.     list_replace(old, lnew);
  112.     INIT_LIST_HEAD(old);
  113. }
  114.  
  115. /**
  116.  * list_del_init - deletes entry from list and reinitialize it.
  117.  * @entry: the element to delete from the list.
  118.  */
  119. static inline void list_del_init(list_t *entry)
  120. {
  121.     __list_del_entry(entry);
  122.     INIT_LIST_HEAD(entry);
  123. }
  124.  
  125. /**
  126.  * list_move - delete from one list and add as another's head
  127.  * @list: the entry to move
  128.  * @head: the head that will precede our entry
  129.  */
  130. static inline void list_move(list_t *list, list_t *head)
  131. {
  132.     __list_del_entry(list);
  133.     list_add(list, head);
  134. }
  135.  
  136. /**
  137.  * list_move_tail - delete from one list and add as another's tail
  138.  * @list: the entry to move
  139.  * @head: the head that will follow our entry
  140.  */
  141. static inline void list_move_tail(list_t *list, list_t *head)
  142. {
  143.     __list_del_entry(list);
  144.     list_add_tail(list, head);
  145. }
  146.  
  147. /**
  148.  * list_is_last - tests whether @list is the last entry in list @head
  149.  * @list: the entry to test
  150.  * @head: the head of the list
  151.  */
  152. static inline int list_is_last(const list_t *list, const list_t *head)
  153. {
  154.     return list->next == head;
  155. }
  156.  
  157. /**
  158.  * list_empty - tests whether a list is empty
  159.  * @head: the list to test.
  160.  */
  161. static inline int list_empty(const list_t *head)
  162. {
  163.     return head->next == head;
  164. }
  165.  
  166. #define container_of(ptr, type, member) ({                      \
  167.         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
  168.         (type *)( (char *)__mptr - offsetof(type,member) );})
  169.  
  170.  
  171.  
  172. /**
  173.  * list_entry - get the struct for this entry
  174.  * @ptr:    the &struct list_head pointer.
  175.  * @type:   the type of the struct this is embedded in.
  176.  * @member:     the name of the list_head within the struct.
  177.  */
  178. #define list_entry(ptr, type, member) \
  179.     container_of(ptr, type, member)
  180.  
  181. /**
  182.  * list_first_entry - get the first element from a list
  183.  * @ptr:    the list head to take the element from.
  184.  * @type:   the type of the struct this is embedded in.
  185.  * @member:     the name of the list_head within the struct.
  186.  *
  187.  * Note, that list is expected to be not empty.
  188.  */
  189. #define list_first_entry(ptr, type, member) \
  190.     list_entry((ptr)->next, type, member)
  191.  
  192. /**
  193.  * list_last_entry - get the last element from a list
  194.  * @ptr:        the list head to take the element from.
  195.  * @type:       the type of the struct this is embedded in.
  196.  * @member:     the name of the list_head within the struct.
  197.  *
  198.  * Note, that list is expected to be not empty.
  199.  */
  200. #define list_last_entry(ptr, type, member) \
  201.         list_entry((ptr)->prev, type, member)
  202.  
  203. /**
  204.  * list_first_entry_or_null - get the first element from a list
  205.  * @ptr:        the list head to take the element from.
  206.  * @type:       the type of the struct this is embedded in.
  207.  * @member:     the name of the list_head within the struct.
  208.  *
  209.  * Note that if the list is empty, it returns NULL.
  210.  */
  211. #define list_first_entry_or_null(ptr, type, member) \
  212.         (!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
  213.  
  214. /**
  215.  * list_next_entry - get the next element in list
  216.  * @pos:        the type * to cursor
  217.  * @member:     the name of the list_head within the struct.
  218.  */
  219. #define list_next_entry(pos, member) \
  220.         list_entry((pos)->member.next, typeof(*(pos)), member)
  221.  
  222. /**
  223.  * list_prev_entry - get the prev element in list
  224.  * @pos:        the type * to cursor
  225.  * @member:     the name of the list_head within the struct.
  226.  */
  227. #define list_prev_entry(pos, member) \
  228.         list_entry((pos)->member.prev, typeof(*(pos)), member)
  229.  
  230. /**
  231.  * list_for_each    -   iterate over a list
  232.  * @pos:    the &struct list_head to use as a loop cursor.
  233.  * @head:   the head for your list.
  234.  */
  235. #define list_for_each(pos, head) \
  236.     for (pos = (head)->next; pos != (head); pos = pos->next)
  237.  
  238. /**
  239.  * list_for_each_prev   -   iterate over a list backwards
  240.  * @pos:    the &struct list_head to use as a loop cursor.
  241.  * @head:   the head for your list.
  242.  */
  243. #define list_for_each_prev(pos, head) \
  244.     for (pos = (head)->prev; pos != (head); pos = pos->prev)
  245.  
  246. /**
  247.  * list_for_each_safe - iterate over a list safe against removal of list entry
  248.  * @pos:    the &struct list_head to use as a loop cursor.
  249.  * @n:      another &struct list_head to use as temporary storage
  250.  * @head:   the head for your list.
  251.  */
  252. #define list_for_each_safe(pos, n, head) \
  253.     for (pos = (head)->next, n = pos->next; pos != (head); \
  254.         pos = n, n = pos->next)
  255.  
  256. /**
  257.  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
  258.  * @pos:    the &struct list_head to use as a loop cursor.
  259.  * @n:      another &struct list_head to use as temporary storage
  260.  * @head:   the head for your list.
  261.  */
  262. #define list_for_each_prev_safe(pos, n, head) \
  263.     for (pos = (head)->prev, n = pos->prev; \
  264.          pos != (head); \
  265.          pos = n, n = pos->prev)
  266.  
  267. /**
  268.  * list_for_each_entry  -   iterate over list of given type
  269.  * @pos:    the type * to use as a loop cursor.
  270.  * @head:   the head for your list.
  271.  * @member:     the name of the list_head within the struct.
  272.  */
  273. #define list_for_each_entry(pos, head, member)              \
  274.         for (pos = list_first_entry(head, typeof(*pos), member);        \
  275.          &pos->member != (head);    \
  276.              pos = list_next_entry(pos, member))
  277.  
  278. /**
  279.  * list_for_each_entry_reverse - iterate backwards over list of given type.
  280.  * @pos:    the type * to use as a loop cursor.
  281.  * @head:   the head for your list.
  282.  * @member:     the name of the list_head within the struct.
  283.  */
  284. #define list_for_each_entry_reverse(pos, head, member)          \
  285.         for (pos = list_last_entry(head, typeof(*pos), member);         \
  286.          &pos->member != (head);    \
  287.              pos = list_prev_entry(pos, member))
  288.  
  289. /**
  290.  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
  291.  * @pos:        the type * to use as a start point
  292.  * @head:       the head of the list
  293.  * @member:     the name of the list_head within the struct.
  294.  *
  295.  * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
  296.  */
  297. #define list_prepare_entry(pos, head, member) \
  298.         ((pos) ? : list_entry(head, typeof(*pos), member))
  299.  
  300. /**
  301.  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
  302.  * @pos:    the type * to use as a loop cursor.
  303.  * @n:      another type * to use as temporary storage
  304.  * @head:   the head for your list.
  305.  * @member: the name of the list_head within the struct.
  306.  */
  307. #define list_for_each_entry_safe(pos, n, head, member)          \
  308.     for (pos = list_first_entry(head, typeof(*pos), member),    \
  309.         n = list_next_entry(pos, member);                       \
  310.          &pos->member != (head);                                \
  311.          pos = n, n = list_next_entry(n, member))
  312.  
  313.  
  314. #endif
  315.