Subversion Repositories Kolibri OS

Rev

Go to most recent revision | 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 - __builtin_offsetof(type,member) );})
  169.  
  170.  
  171. /**
  172.  * list_entry - get the struct for this entry
  173.  * @ptr:    the &struct list_head pointer.
  174.  * @type:   the type of the struct this is embedded in.
  175.  * @member: the name of the list_struct within the struct.
  176.  */
  177. #define list_entry(ptr, type, member) \
  178.     container_of(ptr, type, member)
  179.  
  180. /**
  181.  * list_first_entry - get the first element from a list
  182.  * @ptr:    the list head to take the element from.
  183.  * @type:   the type of the struct this is embedded in.
  184.  * @member: the name of the list_struct within the struct.
  185.  *
  186.  * Note, that list is expected to be not empty.
  187.  */
  188. #define list_first_entry(ptr, type, member) \
  189.     list_entry((ptr)->next, type, member)
  190.  
  191. /**
  192.  * list_for_each    -   iterate over a list
  193.  * @pos:    the &struct list_head to use as a loop cursor.
  194.  * @head:   the head for your list.
  195.  */
  196. #define list_for_each(pos, head) \
  197.     for (pos = (head)->next; pos != (head); pos = pos->next)
  198.  
  199.  
  200. /**
  201.  * list_for_each_prev   -   iterate over a list backwards
  202.  * @pos:    the &struct list_head to use as a loop cursor.
  203.  * @head:   the head for your list.
  204.  */
  205. #define list_for_each_prev(pos, head) \
  206.     for (pos = (head)->prev; pos != (head); pos = pos->prev)
  207.  
  208. /**
  209.  * list_for_each_safe - iterate over a list safe against removal of list entry
  210.  * @pos:    the &struct list_head to use as a loop cursor.
  211.  * @n:      another &struct list_head to use as temporary storage
  212.  * @head:   the head for your list.
  213.  */
  214. #define list_for_each_safe(pos, n, head) \
  215.     for (pos = (head)->next, n = pos->next; pos != (head); \
  216.         pos = n, n = pos->next)
  217.  
  218. /**
  219.  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
  220.  * @pos:    the &struct list_head to use as a loop cursor.
  221.  * @n:      another &struct list_head to use as temporary storage
  222.  * @head:   the head for your list.
  223.  */
  224. #define list_for_each_prev_safe(pos, n, head) \
  225.     for (pos = (head)->prev, n = pos->prev; \
  226.          pos != (head); \
  227.          pos = n, n = pos->prev)
  228.  
  229. /**
  230.  * list_for_each_entry  -   iterate over list of given type
  231.  * @pos:    the type * to use as a loop cursor.
  232.  * @head:   the head for your list.
  233.  * @member: the name of the list_struct within the struct.
  234.  */
  235. #define list_for_each_entry(pos, head, member)              \
  236.     for (pos = list_entry((head)->next, typeof(*pos), member);  \
  237.          &pos->member != (head);    \
  238.          pos = list_entry(pos->member.next, typeof(*pos), member))
  239.  
  240. /**
  241.  * list_for_each_entry_reverse - iterate backwards over list of given type.
  242.  * @pos:    the type * to use as a loop cursor.
  243.  * @head:   the head for your list.
  244.  * @member: the name of the list_struct within the struct.
  245.  */
  246. #define list_for_each_entry_reverse(pos, head, member)          \
  247.     for (pos = list_entry((head)->prev, typeof(*pos), member);  \
  248.          &pos->member != (head);    \
  249.          pos = list_entry(pos->member.prev, typeof(*pos), member))
  250.  
  251.  
  252.  
  253. #endif
  254.