sys_list.h 8.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248
  1. /**
  2. * Copyright (c) 2016 - 2020 Nordic Semiconductor ASA and Luxoft Global Operations Gmbh.
  3. *
  4. * All Rights Reserved.
  5. *
  6. * Redistribution and use in source and binary forms, with or without modification,
  7. * are permitted provided that the following conditions are met:
  8. *
  9. *
  10. * 1. Redistributions of source code must retain the above copyright notice, this
  11. * list of conditions and the following disclaimer.
  12. *
  13. * 2. Redistributions in binary form, except as embedded into a Nordic
  14. * Semiconductor ASA integrated circuit in a product or a software update for
  15. * such product, must reproduce the above copyright notice, this list of
  16. * conditions and the following disclaimer in the documentation and/or other
  17. * materials provided with the distribution.
  18. *
  19. * 3. Neither the name of Nordic Semiconductor ASA nor the names of its
  20. * contributors may be used to endorse or promote products derived from this
  21. * software without specific prior written permission.
  22. *
  23. * 4. This software, with or without modification, must only be used with a
  24. * Nordic Semiconductor ASA integrated circuit.
  25. *
  26. * 5. Any software provided in binary form under this license must not be reverse
  27. * engineered, decompiled, modified and/or disassembled.
  28. *
  29. *
  30. * THIS SOFTWARE IS PROVIDED BY NORDIC SEMICONDUCTOR ASA "AS IS" AND ANY EXPRESS
  31. * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  32. * OF MERCHANTABILITY, NONINFRINGEMENT, AND FITNESS FOR A PARTICULAR PURPOSE ARE
  33. * DISCLAIMED. IN NO EVENT SHALL NORDIC SEMICONDUCTOR ASA OR CONTRIBUTORS BE
  34. * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  35. * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
  36. * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  37. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  38. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  39. * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  40. *
  41. */
  42. #ifndef SYS_LIST_H_INCLUDED
  43. #define SYS_LIST_H_INCLUDED
  44. /** @file
  45. * This file contains declarations of the doubly linked list primitives and necessary types.
  46. * This implementation is Linux-proven and used in the memory management module.
  47. *
  48. * @defgroup sys_list Doubly linked list API.
  49. * @ingroup sys_15_4
  50. * @{
  51. * @brief Module to declare the doubly linked list API.
  52. */
  53. /**
  54. * Internal list "head" struct.
  55. */
  56. struct sys_list_head
  57. {
  58. struct sys_list_head * next;
  59. struct sys_list_head * prev;
  60. };
  61. typedef struct sys_list_head sys_list_head_t;
  62. /**
  63. * @brief Initializes a list by variable name.
  64. * @warning this macro assumes that a list "head" (sys_list_head_t) variable
  65. * with name \a name is already created.
  66. *
  67. * @param[inout] name The "head" struct name.
  68. */
  69. #define LIST_HEAD_INIT(name) { &(name), &(name) }
  70. /**
  71. * @brief Defines and initializes a new list.
  72. * @details A call to this macro creates a new variable with the given name and
  73. * initializes it as a list "head".
  74. *
  75. * @param[inout] name The "head" struct name.
  76. */
  77. #define LIST_HEAD(name) sys_list_head_t name = { &(name), &(name) }
  78. /**
  79. * @brief Initializes a list by pointer.
  80. *
  81. * @param[inout] ptr Pointer to a list.
  82. */
  83. #define INIT_LIST_HEAD(ptr) \
  84. do \
  85. { \
  86. (ptr)->prev = (ptr); \
  87. (ptr)->next = (ptr); \
  88. } while (0)
  89. /**
  90. * @brief Checks if a list is empty.
  91. *
  92. * @param[in] sys_list_head Pointer to a list.
  93. * @return 0 if not empty, non-zero otherwise.
  94. */
  95. #define IS_EMPTY(sys_list_head) (sys_list_head)->next == (sys_list_head)
  96. /**
  97. * @brief Adds a new item to the list between \a l_prev and \a l_next elements.
  98. * @warning This routine assumes that \a l_next is next to \a l_prev in the list.
  99. * @note This is an internal helper routine which is not intended to be used by the user.
  100. *
  101. * @param[in] l_prev Pointer to the previous element.
  102. * @param[in] l_next Pointer to the next element.
  103. * @param[in] l_new Pointer to a new element.
  104. */
  105. static inline void sys_ll_list_add(sys_list_head_t * l_prev,
  106. sys_list_head_t * l_next,
  107. sys_list_head_t * l_new)
  108. {
  109. l_new->prev = l_prev;
  110. l_prev->next = l_new;
  111. l_next->prev = l_new;
  112. l_new->next = l_next;
  113. }
  114. /**
  115. * @brief Deletes an element between \a l_prev and \a l_next elements.
  116. * @warning This macro assumes that \a l_next is next to \a l_prev in the list.
  117. * @note This is an internal helper routine which is not intended to be used by the user.
  118. *
  119. * @param[in] l_prev Pointer to the previous element.
  120. * @param[in] l_next Pointer to the next element.
  121. */
  122. static inline void sys_ll_list_del(sys_list_head_t * l_next,
  123. sys_list_head_t * l_prev)
  124. {
  125. l_next->prev = l_prev;
  126. l_prev->next = l_next;
  127. }
  128. /**
  129. * @brief Function for adding a new item to the head of the list.
  130. *
  131. * @param[in] new Pointer to a new element.
  132. * @param[in] head Pointer to the list head.
  133. */
  134. static inline void sys_list_add(sys_list_head_t * new, sys_list_head_t * head)
  135. {
  136. sys_ll_list_add(head, head->next, new);
  137. }
  138. /**
  139. * @brief Function for adding a new item to the tail of the list.
  140. *
  141. * @param[in] new Pointer to a new element.
  142. * @param[in] head Pointer to the list head.
  143. */
  144. static inline void sys_list_add_tail(sys_list_head_t * new, sys_list_head_t * head)
  145. {
  146. sys_ll_list_add(head->prev, head, new);
  147. }
  148. /**
  149. * @brief Function for deleting an entry from list.
  150. *
  151. * @param[in] entry The element to delete from the list.
  152. */
  153. static inline void sys_list_del(sys_list_head_t * entry)
  154. {
  155. sys_ll_list_del(entry->next, entry->prev);
  156. }
  157. /**
  158. * @brief Function for deleting an entry from the list and reinitializing it.
  159. *
  160. * @param[in] entry The element to delete from the list.
  161. */
  162. static inline void sys_list_del_init(sys_list_head_t * entry)
  163. {
  164. sys_ll_list_del(entry->next, entry->prev);
  165. INIT_LIST_HEAD(entry);
  166. }
  167. /**
  168. * @brief Function for testing if a list is empty.
  169. * @param[in] head The list to test.
  170. * @return 0 if not empty, non-zero otherwise.
  171. */
  172. static inline unsigned int sys_list_empty(sys_list_head_t * head)
  173. {
  174. return IS_EMPTY(head);
  175. }
  176. /**
  177. * @brief Sets a pointer to a variable to the parent structure pointer using a
  178. * pointer to a field in this structure.
  179. *
  180. * @note This is a version of @ref GET_PARENT_BY_FIELD() extended by setting to a variable.
  181. *
  182. * @param[out] ll_ret_var Variable pointer name to return.
  183. * @param[in] ll_ptr Pointer to the structure field.
  184. * @param[in] ll_type Name of the parent structure.
  185. * @param[in] ll_member Name of the structure field.
  186. */
  187. #define SYS_LIST_ENTRY(ll_ret_var, ll_ptr, ll_type, ll_member) \
  188. do \
  189. { \
  190. size_t p = (size_t) ll_ptr; \
  191. size_t off = offsetof(ll_type, ll_member); \
  192. ll_ret_var = (ll_type *) (p - off); \
  193. } while (0)
  194. /**
  195. * @brief Iterates through the list.
  196. * @note Use @ref SYS_LIST_FOR_EACH_SAFE() for thread-safe cases.
  197. *
  198. * @param[out] pos Iterator variable.
  199. * @param[in] head Pointer to the list head.
  200. */
  201. #define SYS_LIST_FOR_EACH(pos, head) \
  202. for (pos = ((head)->next); \
  203. ((pos) != (head)); \
  204. pos = (pos)->next)
  205. /**
  206. * @brief Thread-safe version of @ref SYS_LIST_FOR_EACH().
  207. *
  208. * @param[out] ll_pos Iterator variable.
  209. * @param[out] ll_pos_n Temporary iterator variable (next entry).
  210. * @param[in] ll_head Pointer to the list head.
  211. */
  212. #define SYS_LIST_FOR_EACH_SAFE(ll_pos, ll_pos_n, ll_head) \
  213. for (ll_pos = (ll_head)->next, ll_pos_n = (ll_head)->next->next; \
  214. (ll_pos) != (ll_head); \
  215. ll_pos = ll_pos_n, ll_pos_n = ll_pos->next)
  216. /** @} */
  217. #endif /* SYS_LIST_H_INCLUDED */