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