list.h 9.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340
  1. #ifndef AOS_LIST_H
  2. #define AOS_LIST_H
  3. #ifdef __cplusplus
  4. extern "C" {
  5. #endif
  6. /*
  7. * Get offset of a member variable.
  8. *
  9. * @param[in] type the type of the struct this is embedded in.
  10. * @param[in] member the name of the variable within the struct.
  11. */
  12. #define aos_offsetof(type, member) ((size_t)&(((type *)0)->member))
  13. /*
  14. * Get the struct for this entry.
  15. *
  16. * @param[in] ptr the list head to take the element from.
  17. * @param[in] type the type of the struct this is embedded in.
  18. * @param[in] member the name of the variable within the struct.
  19. */
  20. #define aos_container_of(ptr, type, member) \
  21. ((type *) ((char *) (ptr) - aos_offsetof(type, member)))
  22. /* for double link list */
  23. typedef struct dlist_s {
  24. struct dlist_s *prev;
  25. struct dlist_s *next;
  26. } dlist_t;
  27. static inline void __dlist_add(dlist_t *node, dlist_t *prev, dlist_t *next)
  28. {
  29. node->next = next;
  30. node->prev = prev;
  31. prev->next = node;
  32. next->prev = node;
  33. }
  34. /*
  35. * Get the struct for this entry.
  36. *
  37. * @param[in] addr the list head to take the element from.
  38. * @param[in] type the type of the struct this is embedded in.
  39. * @param[in] member the name of the dlist_t within the struct.
  40. */
  41. #define dlist_entry(addr, type, member) \
  42. ((type *)((long)addr - aos_offsetof(type, member)))
  43. static inline void dlist_add(dlist_t *node, dlist_t *queue)
  44. {
  45. __dlist_add(node, queue, queue->next);
  46. }
  47. static inline void dlist_add_tail(dlist_t *node, dlist_t *queue)
  48. {
  49. __dlist_add(node, queue->prev, queue);
  50. }
  51. static inline void dlist_del(dlist_t *node)
  52. {
  53. dlist_t *prev = node->prev;
  54. dlist_t *next = node->next;
  55. prev->next = next;
  56. next->prev = prev;
  57. }
  58. static inline void dlist_init(dlist_t *node)
  59. {
  60. node->next = node->prev = node;
  61. }
  62. static inline void INIT_AOS_DLIST_HEAD(dlist_t *list)
  63. {
  64. list->next = list;
  65. list->prev = list;
  66. }
  67. static inline int dlist_empty(const dlist_t *head)
  68. {
  69. return head->next == head;
  70. }
  71. /*
  72. * Initialise the list.
  73. *
  74. * @param[in] list the list to be inited.
  75. */
  76. #define AOS_DLIST_INIT(list) {&(list), &(list)}
  77. /*
  78. * Get the first element from a list
  79. *
  80. * @param[in] ptr the list head to take the element from.
  81. * @param[in] type the type of the struct this is embedded in.
  82. * @param[in] member the name of the dlist_t within the struct.
  83. */
  84. #define dlist_first_entry(ptr, type, member) \
  85. dlist_entry((ptr)->next, type, member)
  86. /*
  87. * Iterate over a list.
  88. *
  89. * @param[in] pos the &struct dlist_t to use as a loop cursor.
  90. * @param[in] head he head for your list.
  91. */
  92. #define dlist_for_each(pos, head) \
  93. for (pos = (head)->next; pos != (head); pos = pos->next)
  94. /*
  95. * Iterate over a list safe against removal of list entry.
  96. *
  97. * @param[in] pos the &struct dlist_t to use as a loop cursor.
  98. * @param[in] n another &struct dlist_t to use as temporary storage.
  99. * @param[in] head he head for your list.
  100. */
  101. #define dlist_for_each_safe(pos, n, head) \
  102. for (pos = (head)->next, n = pos->next; pos != (head); \
  103. pos = n, n = pos->next)
  104. /*
  105. * Iterate over list of given type.
  106. *
  107. * @param[in] queue he head for your list.
  108. * @param[in] node the &struct dlist_t to use as a loop cursor.
  109. * @param[in] type the type of the struct this is embedded in.
  110. * @param[in] member the name of the dlist_t within the struct.
  111. */
  112. #define dlist_for_each_entry(queue, node, type, member) \
  113. for (node = aos_container_of((queue)->next, type, member); \
  114. &node->member != (queue); \
  115. node = aos_container_of(node->member.next, type, member))
  116. /*
  117. * Iterate over list of given type safe against removal of list entry.
  118. *
  119. * @param[in] queue the head for your list.
  120. * @param[in] n the type * to use as a temp.
  121. * @param[in] node the type * to use as a loop cursor.
  122. * @param[in] type the type of the struct this is embedded in.
  123. * @param[in] member the name of the dlist_t within the struct.
  124. */
  125. #define dlist_for_each_entry_safe(queue, n, node, type, member) \
  126. for (node = aos_container_of((queue)->next, type, member), \
  127. n = (queue)->next ? (queue)->next->next : NULL; \
  128. &node->member != (queue); \
  129. node = aos_container_of(n, type, member), n = n ? n->next : NULL)
  130. /*
  131. * Get the struct for this entry.
  132. * @param[in] ptr the list head to take the element from.
  133. * @param[in] type the type of the struct this is embedded in.
  134. * @param[in] member the name of the variable within the struct.
  135. */
  136. #define list_entry(ptr, type, member) \
  137. aos_container_of(ptr, type, member)
  138. /*
  139. * Iterate backwards over list of given type.
  140. *
  141. * @param[in] pos the type * to use as a loop cursor.
  142. * @param[in] head he head for your list.
  143. * @param[in] member the name of the dlist_t within the struct.
  144. * @param[in] type the type of the struct this is embedded in.
  145. */
  146. #define dlist_for_each_entry_reverse(pos, head, member, type) \
  147. for (pos = list_entry((head)->prev, type, member); \
  148. &pos->member != (head); \
  149. pos = list_entry(pos->member.prev, type, member))
  150. /*
  151. * Get the list length.
  152. *
  153. * @param[in] queue the head for your list.
  154. */
  155. int dlist_entry_number(dlist_t *queue);
  156. /*
  157. * Initialise the list.
  158. *
  159. * @param[in] name the list to be initialized.
  160. */
  161. #define AOS_DLIST_HEAD_INIT(name) { &(name), &(name) }
  162. /*
  163. * Initialise the list.
  164. *
  165. * @param[in] name the list to be initialized.
  166. */
  167. #define AOS_DLIST_HEAD(name) \
  168. dlist_t name = AOS_DLIST_HEAD_INIT(name)
  169. /* for single link list */
  170. typedef struct slist_s {
  171. struct slist_s *next;
  172. } slist_t;
  173. static inline void slist_add(slist_t *node, slist_t *head)
  174. {
  175. node->next = head->next;
  176. head->next = node;
  177. }
  178. void slist_add_tail(slist_t *node, slist_t *head);
  179. void slist_del(slist_t *node, slist_t *head);
  180. static inline int slist_empty(const slist_t *head)
  181. {
  182. return !head->next;
  183. }
  184. static inline void slist_init(slist_t *head)
  185. {
  186. head->next = 0;
  187. }
  188. static inline slist_t *slist_remove(slist_t *l, slist_t *n)
  189. {
  190. /* remove slist head */
  191. struct slist_s *node = l;
  192. while (node->next && node->next != n) node = node->next;
  193. /* remove node */
  194. if (node->next != (slist_t *)0) node->next = node->next->next;
  195. return l;
  196. }
  197. static inline slist_t *slist_first(slist_t *l)
  198. {
  199. return l->next;
  200. }
  201. static inline slist_t *slist_tail(slist_t *l)
  202. {
  203. while (l->next) l = l->next;
  204. return l;
  205. }
  206. static inline slist_t *slist_next(slist_t *n)
  207. {
  208. return n->next;
  209. }
  210. /*
  211. * Iterate over list of given type.
  212. *
  213. * @param[in] queue he head for your list.
  214. * @param[in] node the type * to use as a loop cursor.
  215. * @param[in] type the type of the struct this is embedded in.
  216. * @param[in] member the name of the slist_t within the struct.
  217. */
  218. #define slist_for_each_entry(queue, node, type, member) \
  219. for (node = (queue)->next? aos_container_of((queue)->next, type, member) : NULL; \
  220. node; \
  221. node = node->member.next ? aos_container_of(node->member.next, type, member) : NULL)
  222. /*
  223. * Iterate over list of given type safe against removal of list entry.
  224. *
  225. * @param[in] queue the head for your list.
  226. * @param[in] tmp the type * to use as a temp.
  227. * @param[in] node the type * to use as a loop cursor.
  228. * @param[in] type the type of the struct this is embedded in.
  229. * @param[in] member the name of the slist_t within the struct.
  230. */
  231. #define slist_for_each_entry_safe(queue, tmp, node, type, member) \
  232. for (node = (queue)->next? aos_container_of((queue)->next, type, member) : NULL, \
  233. tmp = (queue)->next ? (queue)->next->next : NULL; \
  234. node; \
  235. node = tmp ? aos_container_of(tmp, type, member) : NULL, tmp = tmp ? tmp->next : NULL)
  236. /*
  237. * Initialise the list.
  238. *
  239. * @param[in] name the list to be initialized.
  240. */
  241. #define AOS_SLIST_HEAD_INIT(name) {0}
  242. /*
  243. * Initialise the list.
  244. *
  245. * @param[in] name the list to be initialized.
  246. */
  247. #define AOS_SLIST_HEAD(name) \
  248. slist_t name = AOS_SLIST_HEAD_INIT(name)
  249. /*
  250. * Get the struct for this entry.
  251. * @param[in] addr the list head to take the element from.
  252. * @param[in] type the type of the struct this is embedded in.
  253. * @param[in] member the name of the slist_t within the struct.
  254. */
  255. #define slist_entry(addr, type, member) ( \
  256. addr ? (type *)((long)addr - aos_offsetof(type, member)) : (type *)addr \
  257. )
  258. /*
  259. * Get the first element from a list.
  260. *
  261. * @param[in] ptr the list head to take the element from.
  262. * @param[in] type the type of the struct this is embedded in.
  263. * @param[in] member the name of the slist_t within the struct.
  264. */
  265. #define slist_first_entry(ptr, type, member) \
  266. slist_entry((ptr)->next, type, member)
  267. /**
  268. * slist_tail_entry - get the tail element from a slist
  269. * @ptr: the slist head to take the element from.
  270. * @type: the type of the struct this is embedded in.
  271. * @member: the name of the slist_struct within the struct.
  272. *
  273. * Note, that slist is expected to be not empty.
  274. */
  275. #define slist_tail_entry(ptr, type, member) \
  276. slist_entry(slist_tail(ptr), type, member)
  277. /*
  278. * Get the list length.
  279. *
  280. * @param[in] queue the head for your list.
  281. */
  282. int slist_entry_number(slist_t *queue);
  283. #ifdef __cplusplus
  284. }
  285. #endif
  286. #endif /* AOS_LIST_H */