list.h 10 KB

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