elist.h 7.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256
  1. #ifndef _LINUX_LIST_H
  2. #define _LINUX_LIST_H
  3. /*
  4. * Simple doubly linked list implementation.
  5. *
  6. * Some of the internal functions ("__xxx") are useful when
  7. * manipulating whole lists rather than single entries, as
  8. * sometimes we already know the next/prev entries and we can
  9. * generate better code by using them directly rather than
  10. * using the generic single-entry routines.
  11. */
  12. struct list_head {
  13. struct list_head *next, *prev;
  14. };
  15. #define LIST_HEAD_INIT(name) { &(name), &(name) }
  16. #define LIST_HEAD(name) \
  17. struct list_head name = LIST_HEAD_INIT(name)
  18. #define INIT_LIST_HEAD(ptr) do { \
  19. (ptr)->next = (ptr); (ptr)->prev = (ptr); \
  20. } while (0)
  21. /*
  22. * Insert a new entry between two known consecutive entries.
  23. *
  24. * This is only for internal list manipulation where we know
  25. * the prev/next entries already!
  26. */
  27. static inline void __list_add(struct list_head *new,
  28. struct list_head *prev,
  29. struct list_head *next)
  30. {
  31. next->prev = new;
  32. new->next = next;
  33. new->prev = prev;
  34. prev->next = new;
  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(struct list_head *new, struct list_head *head)
  45. {
  46. __list_add(new, head, head->next);
  47. }
  48. /**
  49. * list_add_tail - add a new entry
  50. * @new: new entry to be added
  51. * @head: list head to add it before
  52. *
  53. * Insert a new entry before the specified head.
  54. * This is useful for implementing queues.
  55. */
  56. static inline void list_add_tail(struct list_head *new, struct list_head *head)
  57. {
  58. __list_add(new, head->prev, head);
  59. }
  60. /*
  61. * Delete a list entry by making the prev/next entries
  62. * point to each other.
  63. *
  64. * This is only for internal list manipulation where we know
  65. * the prev/next entries already!
  66. */
  67. static inline void __list_del(struct list_head *prev, struct list_head *next)
  68. {
  69. next->prev = prev;
  70. prev->next = next;
  71. }
  72. /**
  73. * list_del - deletes entry from list.
  74. * @entry: the element to delete from the list.
  75. * Note: list_empty on entry does not return true after this, the entry is in an undefined state.
  76. */
  77. static inline void list_del(struct list_head *entry)
  78. {
  79. __list_del(entry->prev, entry->next);
  80. entry->next = (void *) 0;
  81. entry->prev = (void *) 0;
  82. }
  83. /**
  84. * list_del_init - deletes entry from list and reinitialize it.
  85. * @entry: the element to delete from the list.
  86. */
  87. static inline void list_del_init(struct list_head *entry)
  88. {
  89. __list_del(entry->prev, entry->next);
  90. INIT_LIST_HEAD(entry);
  91. }
  92. /**
  93. * list_move - delete from one list and add as another's head
  94. * @list: the entry to move
  95. * @head: the head that will precede our entry
  96. */
  97. static inline void list_move(struct list_head *list, struct list_head *head)
  98. {
  99. __list_del(list->prev, list->next);
  100. list_add(list, head);
  101. }
  102. /**
  103. * list_move_tail - delete from one list and add as another's tail
  104. * @list: the entry to move
  105. * @head: the head that will follow our entry
  106. */
  107. static inline void list_move_tail(struct list_head *list,
  108. struct list_head *head)
  109. {
  110. __list_del(list->prev, list->next);
  111. list_add_tail(list, head);
  112. }
  113. /**
  114. * list_empty - tests whether a list is empty
  115. * @head: the list to test.
  116. */
  117. static inline int list_empty(struct list_head *head)
  118. {
  119. return head->next == head;
  120. }
  121. static inline void __list_splice(struct list_head *list,
  122. struct list_head *head)
  123. {
  124. struct list_head *first = list->next;
  125. struct list_head *last = list->prev;
  126. struct list_head *at = head->next;
  127. first->prev = head;
  128. head->next = first;
  129. last->next = at;
  130. at->prev = last;
  131. }
  132. /**
  133. * list_splice - join two lists
  134. * @list: the new list to add.
  135. * @head: the place to add it in the first list.
  136. */
  137. static inline void list_splice(struct list_head *list, struct list_head *head)
  138. {
  139. if (!list_empty(list))
  140. __list_splice(list, head);
  141. }
  142. /**
  143. * list_splice_init - join two lists and reinitialise the emptied list.
  144. * @list: the new list to add.
  145. * @head: the place to add it in the first list.
  146. *
  147. * The list at @list is reinitialised
  148. */
  149. static inline void list_splice_init(struct list_head *list,
  150. struct list_head *head)
  151. {
  152. if (!list_empty(list)) {
  153. __list_splice(list, head);
  154. INIT_LIST_HEAD(list);
  155. }
  156. }
  157. /**
  158. * list_entry - get the struct for this entry
  159. * @ptr: the &struct list_head pointer.
  160. * @type: the type of the struct this is embedded in.
  161. * @member: the name of the list_struct within the struct.
  162. */
  163. #ifndef _WIN64
  164. #define list_entry(ptr, type, member) \
  165. ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
  166. #else
  167. #define list_entry(ptr, type, member) \
  168. ((type *)((char *)(ptr)-(unsigned long long)(&((type *)0)->member)))
  169. #endif
  170. /**
  171. * list_for_each - iterate over a list
  172. * @pos: the &struct list_head to use as a loop counter.
  173. * @head: the head for your list.
  174. */
  175. #define list_for_each(pos, head) \
  176. for (pos = (head)->next; pos != (head); \
  177. pos = pos->next)
  178. /**
  179. * list_for_each_prev - iterate over a list backwards
  180. * @pos: the &struct list_head to use as a loop counter.
  181. * @head: the head for your list.
  182. */
  183. #define list_for_each_prev(pos, head) \
  184. for (pos = (head)->prev; pos != (head); \
  185. pos = pos->prev)
  186. /**
  187. * list_for_each_safe - iterate over a list safe against removal of list entry
  188. * @pos: the &struct list_head to use as a loop counter.
  189. * @n: another &struct list_head to use as temporary storage
  190. * @head: the head for your list.
  191. */
  192. #define list_for_each_safe(pos, n, head) \
  193. for (pos = (head)->next, n = pos->next; pos != (head); \
  194. pos = n, n = pos->next)
  195. /**
  196. * list_for_each_entry - iterate over list of given type
  197. * @pos: the type * to use as a loop counter.
  198. * @head: the head for your list.
  199. * @member: the name of the list_struct within the struct.
  200. */
  201. #define list_for_each_entry(pos, head, member) \
  202. for (pos = list_entry((head)->next, typeof(*pos), member); \
  203. &pos->member != (head); \
  204. pos = list_entry(pos->member.next, typeof(*pos), member))
  205. /**
  206. * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
  207. * @pos: the type * to use as a loop counter.
  208. * @n: another type * to use as temporary storage
  209. * @head: the head for your list.
  210. * @member: the name of the list_struct within the struct.
  211. */
  212. #define list_for_each_entry_safe(pos, n, head, member) \
  213. for (pos = list_entry((head)->next, typeof(*pos), member), \
  214. n = list_entry(pos->member.next, typeof(*pos), member); \
  215. &pos->member != (head); \
  216. pos = n, n = list_entry(n->member.next, typeof(*n), member))
  217. /**
  218. * list_for_each_entry_continue - iterate over list of given type
  219. * continuing after existing point
  220. * @pos: the type * to use as a loop counter.
  221. * @head: the head for your list.
  222. * @member: the name of the list_struct within the struct.
  223. */
  224. #define list_for_each_entry_continue(pos, head, member) \
  225. for (pos = list_entry(pos->member.next, typeof(*pos), member), \
  226. prefetch(pos->member.next); \
  227. &pos->member != (head); \
  228. pos = list_entry(pos->member.next, typeof(*pos), member), \
  229. prefetch(pos->member.next))
  230. #endif