1 /*
2 * Copyright (c) 2020 Raspberry Pi (Trading) Ltd.
3 *
4 * SPDX-License-Identifier: BSD-3-Clause
5 */
6
7 #ifndef _PICO_UTIL_QUEUE_H
8 #define _PICO_UTIL_QUEUE_H
9
10 #include "pico.h"
11 #include "hardware/sync.h"
12
13 // PICO_CONFIG: PICO_QUEUE_MAX_LEVEL, Maintain a field for the highest level that has been reached by a queue, type=bool, default=0, advanced=true, group=queue
14 #ifndef PICO_QUEUE_MAX_LEVEL
15 #define PICO_QUEUE_MAX_LEVEL 0
16 #endif
17
18 /** \file queue.h
19 * \defgroup queue queue
20 * \brief Multi-core and IRQ safe queue implementation
21 *
22 * Note that this queue stores values of a specified size, and pushed values are copied into the queue
23 * \ingroup pico_util
24 */
25
26 #ifdef __cplusplus
27 extern "C" {
28 #endif
29
30 #include "pico/lock_core.h"
31
32 typedef struct {
33 lock_core_t core;
34 uint8_t *data;
35 uint16_t wptr;
36 uint16_t rptr;
37 uint16_t element_size;
38 uint16_t element_count;
39 #if PICO_QUEUE_MAX_LEVEL
40 uint16_t max_level;
41 #endif
42 } queue_t;
43
44 /*! \brief Initialise a queue with a specific spinlock for concurrency protection
45 * \ingroup queue
46 *
47 * \param q Pointer to a queue_t structure, used as a handle
48 * \param element_size Size of each value in the queue
49 * \param element_count Maximum number of entries in the queue
50 * \param spinlock_num The spin ID used to protect the queue
51 */
52 void queue_init_with_spinlock(queue_t *q, uint element_size, uint element_count, uint spinlock_num);
53
54 /*! \brief Initialise a queue, allocating a (possibly shared) spinlock
55 * \ingroup queue
56 *
57 * \param q Pointer to a queue_t structure, used as a handle
58 * \param element_size Size of each value in the queue
59 * \param element_count Maximum number of entries in the queue
60 */
queue_init(queue_t * q,uint element_size,uint element_count)61 static inline void queue_init(queue_t *q, uint element_size, uint element_count) {
62 queue_init_with_spinlock(q, element_size, element_count, next_striped_spin_lock_num());
63 }
64
65 /*! \brief Destroy the specified queue.
66 * \ingroup queue
67 *
68 * \param q Pointer to a queue_t structure, used as a handle
69 *
70 * Does not deallocate the queue_t structure itself.
71 */
72 void queue_free(queue_t *q);
73
74 /*! \brief Unsafe check of level of the specified queue.
75 * \ingroup queue
76 *
77 * \param q Pointer to a queue_t structure, used as a handle
78 * \return Number of entries in the queue
79 *
80 * This does not use the spinlock, so may return incorrect results if the
81 * spin lock is not externally locked
82 */
queue_get_level_unsafe(queue_t * q)83 static inline uint queue_get_level_unsafe(queue_t *q) {
84 int32_t rc = (int32_t)q->wptr - (int32_t)q->rptr;
85 if (rc < 0) {
86 rc += q->element_count + 1;
87 }
88 return (uint)rc;
89 }
90
91 /*! \brief Check of level of the specified queue.
92 * \ingroup queue
93 *
94 * \param q Pointer to a queue_t structure, used as a handle
95 * \return Number of entries in the queue
96 */
queue_get_level(queue_t * q)97 static inline uint queue_get_level(queue_t *q) {
98 uint32_t save = spin_lock_blocking(q->core.spin_lock);
99 uint level = queue_get_level_unsafe(q);
100 spin_unlock(q->core.spin_lock, save);
101 return level;
102 }
103
104 #if PICO_QUEUE_MAX_LEVEL
105 /*! \brief Returns the highest level reached by the specified queue since it was created
106 * or since the max level was reset
107 * \ingroup queue
108 *
109 * \param q Pointer to a queue_t structure, used as a handle
110 * \return Maximum level of the queue
111 */
queue_get_max_level(queue_t * q)112 static inline uint queue_get_max_level(queue_t *q) {
113 return q->max_level;
114 }
115 #endif
116
117 #if PICO_QUEUE_MAX_LEVEL
118 /*! \brief Reset the highest level reached of the specified queue.
119 * \ingroup queue
120 *
121 * \param q Pointer to a queue_t structure, used as a handle
122 */
queue_reset_max_level(queue_t * q)123 static inline void queue_reset_max_level(queue_t *q) {
124 uint32_t save = spin_lock_blocking(q->core.spin_lock);
125 q->max_level = queue_get_level_unsafe(q);
126 spin_unlock(q->core.spin_lock, save);
127 }
128 #endif
129
130 /*! \brief Check if queue is empty
131 * \ingroup queue
132 *
133 * \param q Pointer to a queue_t structure, used as a handle
134 * \return true if queue is empty, false otherwise
135 *
136 * This function is interrupt and multicore safe.
137 */
queue_is_empty(queue_t * q)138 static inline bool queue_is_empty(queue_t *q) {
139 return queue_get_level(q) == 0;
140 }
141
142 /*! \brief Check if queue is full
143 * \ingroup queue
144 *
145 * \param q Pointer to a queue_t structure, used as a handle
146 * \return true if queue is full, false otherwise
147 *
148 * This function is interrupt and multicore safe.
149 */
queue_is_full(queue_t * q)150 static inline bool queue_is_full(queue_t *q) {
151 return queue_get_level(q) == q->element_count;
152 }
153
154 // nonblocking queue access functions:
155
156 /*! \brief Non-blocking add value queue if not full
157 * \ingroup queue
158 *
159 * \param q Pointer to a queue_t structure, used as a handle
160 * \param data Pointer to value to be copied into the queue
161 * \return true if the value was added
162 *
163 * If the queue is full this function will return immediately with false, otherwise
164 * the data is copied into a new value added to the queue, and this function will return true.
165 */
166 bool queue_try_add(queue_t *q, const void *data);
167
168 /*! \brief Non-blocking removal of entry from the queue if non empty
169 * \ingroup queue
170 *
171 * \param q Pointer to a queue_t structure, used as a handle
172 * \param data Pointer to the location to receive the removed value, or NULL if the data isn't required
173 * \return true if a value was removed
174 *
175 * If the queue is not empty function will copy the removed value into the location provided and return
176 * immediately with true, otherwise the function will return immediately with false.
177 */
178 bool queue_try_remove(queue_t *q, void *data);
179
180 /*! \brief Non-blocking peek at the next item to be removed from the queue
181 * \ingroup queue
182 *
183 * \param q Pointer to a queue_t structure, used as a handle
184 * \param data Pointer to the location to receive the peeked value, or NULL if the data isn't required
185 * \return true if there was a value to peek
186 *
187 * If the queue is not empty this function will return immediately with true with the peeked entry
188 * copied into the location specified by the data parameter, otherwise the function will return false.
189 */
190 bool queue_try_peek(queue_t *q, void *data);
191
192 // blocking queue access functions:
193
194 /*! \brief Blocking add of value to queue
195 * \ingroup queue
196 *
197 * \param q Pointer to a queue_t structure, used as a handle
198 * \param data Pointer to value to be copied into the queue
199 *
200 * If the queue is full this function will block, until a removal happens on the queue
201 */
202 void queue_add_blocking(queue_t *q, const void *data);
203
204 /*! \brief Blocking remove entry from queue
205 * \ingroup queue
206 *
207 * \param q Pointer to a queue_t structure, used as a handle
208 * \param data Pointer to the location to receive the removed value, or NULL if the data isn't required
209 *
210 * If the queue is empty this function will block until a value is added.
211 */
212 void queue_remove_blocking(queue_t *q, void *data);
213
214 /*! \brief Blocking peek at next value to be removed from queue
215 * \ingroup queue
216 *
217 * \param q Pointer to a queue_t structure, used as a handle
218 * \param data Pointer to the location to receive the peeked value, or NULL if the data isn't required
219 *
220 * If the queue is empty function will block until a value is added
221 */
222 void queue_peek_blocking(queue_t *q, void *data);
223
224 #ifdef __cplusplus
225 }
226 #endif
227 #endif
228
