sys_queue.h 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290
  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_QUEUE_H_INCLUDED
  43. #define SYS_QUEUE_H_INCLUDED
  44. #include <stdbool.h>
  45. #include <stdint.h>
  46. /** @file
  47. * This file contains declarations of the primitives to work with queues and necessary types.
  48. *
  49. * @defgroup sys_queues Queue API
  50. * @ingroup sys_15_4
  51. * @{
  52. * @brief Module to declare the queue API.
  53. * @details The queue module implements a set of routines to deal with queues. Before
  54. * any calls to its API are issued, a queue must be initialized using sys_queue_init(). The following routines
  55. * return queue items from different parts of an initialized queue without removing it from the queue:
  56. * sys_queue_front(), sys_queue_back(), sys_queue_next(), and sys_queue_at().
  57. * The following routines insert elements to the queue: sys_queue_push_front(),
  58. * sys_queue_push_back(), sys_queue_push_predicated(), sys_queue_push_predicated_force(), and sys_queue_insert().
  59. * The following routines remove elements from the queue: sys_queue_pop_front(), sys_queue_remove(),
  60. * sys_queue_remove_after(). These helper routines get information about a queue: sys_queue_size() and
  61. * sys_queue_is_empty(). The module also supports an iterator macro implemented by SYS_QUEUE_FOR_EACH().
  62. */
  63. /**@brief Queue item descriptor.
  64. *
  65. * @details In order to store any user data struct in a queue, the user struct should contain
  66. * a field of type 'sys_queue_item_t'. This field may be at any offset.
  67. * The user data item can be cast from the queue item,
  68. * by the \ref GET_PARENT_BY_FIELD() macro from sys_utils.h.
  69. */
  70. typedef struct sys_queue_item_s
  71. {
  72. struct sys_queue_item_s * next;
  73. } sys_queue_item_t;
  74. /**@brief Queue descriptor.
  75. */
  76. typedef sys_queue_item_t sys_queue_t;
  77. /**@brief Prototype of a predicate function for pushing an item into the queue.
  78. *
  79. * @details As a user of the queue library, implement the predicate function and pass it
  80. * as a parameter to \ref sys_queue_push_predicated(). You can choose
  81. * whether insertion of a new item should be done before the given existing item of
  82. * the queue, or not.
  83. *
  84. * @param[in] p_before_item Pointer to the existing item before which a new item
  85. * should be inserted.
  86. * @param[in] p_new_item Pointer to the item to be inserted into the queue.
  87. *
  88. * @retval true Insertion is to be done before the given item, false otherwise.
  89. */
  90. typedef bool (* sys_queue_push_predicate_t)(
  91. sys_queue_item_t * p_before_item,
  92. sys_queue_item_t * p_new_item);
  93. /**@brief Function for initializing the queue before any other usage of the queue.
  94. *
  95. * @details Initialize (reset) the queue to its initial state. The queue becomes empty.
  96. *
  97. * @param[in] p_queue Queue to be initialized.
  98. */
  99. void sys_queue_init(sys_queue_t * p_queue);
  100. /**@brief Function for getting the front (head) item of the queue without removing it.
  101. *
  102. * @details Return a pointer to the item from the head of the queue but leave it in the queue.
  103. *
  104. * @param[in] p_queue Queue to get the item from.
  105. *
  106. * @retval Pointer to the head item of the queue, or NULL if the queue is empty.
  107. */
  108. sys_queue_item_t * sys_queue_front(const sys_queue_t * p_queue);
  109. /**@brief Function for getting the back (tail) item of the queue without removing it.
  110. *
  111. * @details Return a pointer to the item from the tail of the queue but leave it in the queue.
  112. *
  113. * @param[in] p_queue Queue to get the item from.
  114. *
  115. * @retval Pointer to the tail item of the queue, or NULL if the queue is empty.
  116. */
  117. sys_queue_item_t * sys_queue_back(const sys_queue_t * p_queue);
  118. /**@brief Function for getting the item, next to the given item of the queue.
  119. *
  120. * @details Return a pointer to the next item after the given one, or NULL if the
  121. * given item is the last item of the queue.
  122. *
  123. * @param[in] p_queue Pointer to the queue.
  124. * @param[in] p_item Pointer to the item.
  125. *
  126. * @retval Pointer to the next item after the given one, or NULL if the
  127. * given item is the last item of the queue.
  128. */
  129. sys_queue_item_t * sys_queue_next(const sys_queue_t * p_queue, const sys_queue_item_t * p_item);
  130. /**@brief Function for pushing an item to the front (head) of the queue.
  131. *
  132. * @details This function inserts an item to the head of the queue.
  133. *
  134. * @param[in] p_queue Queue to push the item to.
  135. * @param[in] p_item Item to insert to the front of the queue.
  136. */
  137. void sys_queue_push_front(sys_queue_t * p_queue, sys_queue_item_t * p_item);
  138. /**@brief Function for pushing an item to the back (tail) of the queue.
  139. *
  140. * @details This function inserts an item to the tail of the queue.
  141. *
  142. * @param[in] p_queue Queue to push the item to.
  143. * @param[in] p_item Item to insert to the tail of the queue.
  144. */
  145. void sys_queue_push_back(sys_queue_t * p_queue, sys_queue_item_t * p_item);
  146. /**@brief Function for pushing an item to the queue with a predicate.
  147. *
  148. * @details Conditionally push an item to the queue using the given predicate that tries to determine
  149. * the insertion position.
  150. *
  151. * @param[in] p_queue Queue to push the item to.
  152. * @param[in] p_item Item to be pushed.
  153. * @param[in] predicate Predicate to be used to find the insertion position.
  154. *
  155. * @retval true The item was inserted into the queue, false otherwise.
  156. */
  157. bool sys_queue_push_predicated(
  158. sys_queue_t * p_queue,
  159. sys_queue_item_t * p_item,
  160. sys_queue_push_predicate_t predicate);
  161. /**@brief Function for pushing an item to the queue with a predicate forcing insertion to the tail if the predicate
  162. * fails.
  163. *
  164. * @details Unconditionally push an item to the queue using the given predicate that tries to
  165. * determine the insertion position.
  166. * If predicate returns false, then force the insertion to the tail of the queue.
  167. *
  168. * @param[in] p_queue Queue to push item to.
  169. * @param[in] p_item Item to be pushed.
  170. * @param[in] predicate Predicate to be used to find the insertion position.
  171. */
  172. void sys_queue_push_predicated_force(
  173. sys_queue_t * p_queue,
  174. sys_queue_item_t * p_item,
  175. sys_queue_push_predicate_t predicate);
  176. /**@brief Function for getting and removing the front (head) item from the queue.
  177. *
  178. * @details Get an item from the head of the queue and remove it from the queue.
  179. *
  180. * @param[in] p_queue Queue to get and remove the head item from.
  181. *
  182. * @retval Pointer to the head item of queue or NULL if the queue is empty.
  183. */
  184. sys_queue_item_t * sys_queue_pop_front(sys_queue_t * p_queue);
  185. /**@brief Function for removing an item from the queue.
  186. *
  187. * @details The given item will be removed from the queue.
  188. *
  189. * @note The complexity of this function is O(n). Use function \ref sys_queue_remove_after()
  190. * whenever the previous item of the queue is known.
  191. *
  192. * @param[in] p_queue Queue to remove the item from.
  193. * @param[in] p_item Item to remove from the queue.
  194. */
  195. void sys_queue_remove(sys_queue_t * p_queue, sys_queue_item_t * p_item);
  196. /**@brief Function for removing the item after the given item from the queue.
  197. *
  198. * @details The item next to the given one will be removed from the queue.
  199. *
  200. * @param[in] p_queue Queue to remove the item from.
  201. * @param[in] p_after_item Next to this item will be removed.
  202. */
  203. void sys_queue_remove_after(sys_queue_t * p_queue, sys_queue_item_t * p_after_item);
  204. /**@brief Function for returning the current size of a queue, i.e. number of elements inside it.
  205. *
  206. * @details This function goes through the whole queue, so it is relatively slow.
  207. *
  208. * @param[in] p_queue Queue to work with.
  209. *
  210. * @retval Number of items currently inserted into the queue.
  211. */
  212. uint8_t sys_queue_size(const sys_queue_t * p_queue);
  213. /**@brief Function for returning a pointer to the item inside a queue represented by an index.
  214. *
  215. * @details This function searches through the whole queue, so it is relatively slow.
  216. *
  217. * @param[in] p_queue Queue to work with.
  218. * @param[in] index Requested index.
  219. *
  220. * @retval Pointer to the requested item or NULL if the queue size is less
  221. * than \a index.
  222. */
  223. sys_queue_item_t * sys_queue_at(const sys_queue_t * p_queue, const uint8_t index);
  224. /**@brief Function for inserting an item at the specified position represented by an index in the queue.
  225. * If this position is too big, it is inserted to the tail of the queue.
  226. *
  227. * @details This function searches through the whole queue, so it is relatively slow.
  228. *
  229. * @param[in] p_queue Queue to insert to.
  230. * @param[in] p_item Item to be inserted.
  231. * @param[in] pos Position inside the queue (0 is the front).
  232. */
  233. void sys_queue_insert(sys_queue_t * p_queue, sys_queue_item_t * p_item, const uint8_t pos);
  234. /**@brief Function for determining if a queue is empty.
  235. *
  236. * @param[in] p_queue Queue to be checked.
  237. *
  238. * @retval True if queue is empty, false otherwise.
  239. */
  240. bool sys_queue_is_empty(const sys_queue_t * p_queue);
  241. /**@brief Macro for iterating through all items in the queue.
  242. *
  243. * @param[in] p_queue Pointer to the queue (sys_queue_t *).
  244. * @param[in] p_iterator Variable to be used as an iterator (sys_queue_item_t *).
  245. */
  246. #define SYS_QUEUE_FOR_EACH(p_queue, p_iterator) \
  247. for (sys_queue_item_t * p_iterator = sys_queue_front(p_queue); \
  248. p_iterator != NULL; \
  249. p_iterator = sys_queue_next(p_queue, p_iterator))
  250. /** @} */
  251. #endif // SYS_QUEUE_H_INCLUDED