Developer World
Spresense SDK Library v3.3.0-375c679
BasicQueue.h
1/****************************************************************************
2 * modules/include/memutils/message/BasicQueue.h
3 *
4 * Copyright 2018 Sony Semiconductor Solutions Corporation
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided with the
15 * distribution.
16 * 3. Neither the name of Sony Semiconductor Solutions Corporation nor
17 * the names of its contributors may be used to endorse or promote
18 * products derived from this software without specific prior written
19 * permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
28 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
33 *
34 ****************************************************************************/
35
36#ifndef BASIC_QUEUE_H_INCLUDED
37#define BASIC_QUEUE_H_INCLUDED
38
39#include <new> /* placement new */
40#include <stdio.h> /* printf */
41#include <string.h> /* memcpy, memset */
42#include "memutils/common_utils/common_types.h" /* uint8_t, drm_t, INVALID_DRM */
43#include "memutils/common_utils/common_assert.h" /* D_ASSERT, F_ASSERT */
44#include "memutils/os_utils/cpp_util.h" /* CopyGuard */
45#include "memutils/message/AssertInfo.h" /* SizeErrorLog */
46
47/****************************************************************************
48 * Pre-processor Definitions
49 ****************************************************************************/
50
51#define DRM_TO_CACHED_VA(drm) (void*)(drm)
52
53/*****************************************************************
54 * Type characteristic
55 *****************************************************************/
56template<typename> struct BasicQueueAddrTraits;
57
58template<> struct BasicQueueAddrTraits<void*> {
59 /* In static const, initialization of non-integer (pointer)
60 * can not be performed, so it is set as enum.
61 */
62
63 enum { init_value = 0 };
64};
65
66template<> struct BasicQueueAddrTraits<drm_t> {
67 enum { init_value = INVALID_DRM };
68};
69
70/*****************************************************************
71 * Basic matrix class
72 *****************************************************************/
73template<typename AddrT, /* queue address type. drm_t or void* */
74 typename SizeT, /* element size type. uintN_t */
75 typename NumT, /* element num type. uintN_t */
76 uint8_t FillAfterPop = 0x00> /* The value to fill after pop.
77 * When it is 0, no filling is done.
78 */
79class BasicQueue : CopyGuard {
80public:
81 BasicQueue() :
82 m_data_area(AddrT(BasicQueueAddrTraits<AddrT>::init_value)),
83 m_elem_size(0), m_capacity(0),
84 m_put(0), m_get(0), m_count(0) {}
85
86 BasicQueue(AddrT data_area, SizeT elem, NumT num) :
87 m_data_area(data_area), m_elem_size(elem), m_capacity(num),
88 m_put(0), m_get(0), m_count(0) {
89 D_ASSERT(data_area != AddrT(BasicQueueAddrTraits<AddrT>::init_value) && elem && num);
90 }
91
92 ~BasicQueue() { D_ASSERT(empty()); }
93
94 /* Initialization by this function is required for the instance created
95 * by default constructor.
96 */
97
98 void init(AddrT data_area, SizeT elem, NumT num) {
99 D_ASSERT(data_area != AddrT(BasicQueueAddrTraits<AddrT>::init_value) && elem && num);
100 D_ASSERT(is_init() == false); /* Reinitialization prohibited. */
101 m_data_area = data_area;
102 m_elem_size = elem;
103 m_capacity = num;
104 }
105
106 bool is_init() const { return m_data_area != AddrT(BasicQueueAddrTraits<AddrT>::init_value); }
107 SizeT elem_size() const { return m_elem_size; }
108 NumT capacity() const { return m_capacity; }
109 NumT size() const { return m_count; }
110 NumT rest() const { return static_cast<NumT>(capacity() - size()); }
111 bool empty() const { return size() == 0; }
112 bool full() const { return size() == capacity(); }
113
114 void dump() const {
115 printf("dump: put=%u, get=%u, capa=%u, elem=%u, size=%u, rest=%u, empty=%d, full=%d\n",
116 m_put, m_get, capacity(), elem_size(), size(), rest(), empty(), full());
117 printf(" 0 1 2 3 4 5 6 7 8 9 a b c d e f\n");
118 for (NumT i = 0; i < capacity(); ++i) {
119 printf("%3u: ", i);
120 for (NumT j = 0; j < MIN(elem_size(), 16); ++j) {
121 printf("%02x ", static_cast<uint8_t*>(getAddr(i))[j]);
122 }
123 printf("\n");
124 }
125 }
126
127 void dump_active() const {
128 printf("dump: size=%u, rest=%u\n", size(), rest());
129 printf(" 0 1 2 3 4 5 6 7 8 9 a b c d e f\n");
130 for (NumT i = 0; i < size(); ++i) {
131 printf("% 3u: ", i);
132 for (NumT j = 0; j < MIN(elem_size(), 16); ++j) {
133 printf("%02x ", static_cast<uint8_t*>(getAddr(getIndex(i)))[j]);
134 }
135 printf("\n");
136 }
137 }
138
139 /* Clear the queue without destructor invocation. */
140
141 void clear() {
142 while (pop()) ;
143 m_put = m_get = 0;
144 }
145
146 /* Inserting data at the end of the queue (using memcpy). */
147
148 bool push(const void* data, SizeT len) {
149 D_ASSERT2(len <= elem_size(), AssertParamLog(AssertIdSizeError, len, elem_size()));
150 if (full()) return false;
151 memcpy(getAddr(m_put), data, len);
152 postPush();
153 return true;
154 }
155
156 /* Inserting data at the end of the queue (using copy constructor). */
157
158 template<typename T>
159 bool push(const T& data) {
160 D_ASSERT2(sizeof(T) <= elem_size(), AssertParamLog(AssertIdSizeError, sizeof(T), elem_size()));
161 if (full()) return false;
162 ::new(getAddr(m_put)) T(data); /* call copy constructor */
163 postPush();
164 return true;
165 }
166
167 /* Remove queue head data without destructor call. */
168
169 bool pop() {
170 if (empty()) return false;
171 postPop();
172 return true;
173 }
174
175 /* Remove the data at the head of the queue after calling the destructor. */
176
177 template<typename T>
178 bool pop() {
179 D_ASSERT2(sizeof(T) <= elem_size(), AssertParamLog(AssertIdSizeError, sizeof(T), elem_size()));
180 if (empty()) return false;
181 static_cast<T*>(getAddr(m_get))->~T(); /* call destructor */
182 postPop();
183 return true;
184 }
185
186 /* Refer to the data at the head of the queue. */
187
188 template<typename T>
189 const T& top() const { return at<T>(0); }
190
191 /* Refer to the data of the Nth (head data is 0) of the queue */
192
193 template<typename T>
194 const T& at(NumT n) const {
195 D_ASSERT2(sizeof(T) <= elem_size(), AssertParamLog(AssertIdSizeError, sizeof(T), elem_size()));
196 D_ASSERT2(n < m_count, AssertParamLog(AssertIdBadParam, n, m_count));
197 return *static_cast<T*>(getAddr(getIndex(n)));
198 }
199
200 template<typename T>
201 T& writable_at(NumT n) { return const_cast<T&>(at<T>(n)); }
202
203 /* Refer to the data at the head of the queue. */
204
205 template<typename T>
206 const T& front() const { return at<T>(0); }
207
208 template<typename T>
209 T& front() { return writable_at<T>(0); }
210
211 /* Reference data at the end of the queue. */
212
213 template<typename T>
214 const T& back() const { return at<T>(static_cast<NumT>(m_count - 1)); }
215
216 template<typename T>
217 T& back() { return writable_at<T>(static_cast<NumT>(m_count - 1)); }
218
219protected:
220 void postPush() {
221 ++m_count;
222 if (++m_put == capacity()) {
223 m_put = 0;
224 }
225 }
226
227 void postPop() {
228 if (FillAfterPop) {
229 memset(getAddr(m_get), FillAfterPop, elem_size());
230 }
231 --m_count;
232 if (++m_get == capacity()) {
233 m_get = 0;
234 }
235 }
236
237 NumT getIndex(NumT n) const {
238 return static_cast<NumT>((m_get + n < capacity()) ? m_get + n : m_get + n - capacity());
239 }
240
241 /* Call separation by tag and dispatch. */
242
243 void* getAddr(NumT n) const { return getAddr(n, AddrT()); }
244
245 void* getAddr(NumT n, drm_t /* dummy */) const {
246 return static_cast<uint8_t*>(DRM_TO_CACHED_VA(m_data_area)) + n * elem_size();
247 }
248
249 void* getAddr(NumT n, void* /* dummy */) const {
250 return static_cast<uint8_t*>(m_data_area) + n * elem_size();
251 }
252
253private:
254 AddrT m_data_area; /* point to data area */
255 SizeT m_elem_size; /* element size */
256 NumT m_capacity; /* number of elements */
257 NumT m_put; /* data put position. 0 origin */
258 NumT m_get; /* data get position. 0 origin */
259 NumT m_count; /* data count in queue */
260}; /* class BasicQueue */
261
262
263#ifdef TEST_BASIC_QUEUE
264//typedef BasicQueue<void*, uint8_t, uint8_t, 0x55> TestQue;
265//typedef BasicQueue<void*, uint16_t, uint8_t, 0x55> TestQue;
266//typedef BasicQueue<void*, uint8_t, uint16_t, 0x55> TestQue;
267typedef BasicQueue<void*, uint16_t, uint16_t, 0x55> TestQue;
268//typedef BasicQueue<void*, uint32_t, uint32_t, 0x55> TestQue;
269
270static void testQueOperation(TestQue& que)
271{
272 for (uint32_t i = 0; i <= que.capacity(); ++i) {
273 que.dump_active();
274
275 F_ASSERT(que.size() == i);
276 F_ASSERT(que.rest() == que.capacity() - i);
277 F_ASSERT(que.empty() == (i == 0));
278 F_ASSERT(que.full() == (i == que.capacity()));
279
280 uint32_t n = 'a' + i;
281 if (i % 2 == 0) {
282 F_ASSERT(que.push(n) == (i < que.capacity()));
283 } else {
284 F_ASSERT(que.push(&n, sizeof(n)) == (i < que.capacity()));
285 }
286 F_ASSERT(que.top<uint32_t>() == 'a');
287 F_ASSERT(que.front<uint32_t>() == 'a');
288 F_ASSERT(que.back<uint32_t>() == static_cast<uint32_t>('a' + MIN(i, static_cast<uint32_t>(que.capacity() - 1))));
289 }
290 que.dump();
291
292 for (uint32_t i = 0; i <= que.capacity(); ++i) {
293 F_ASSERT(que.size() == que.capacity() - i);
294 F_ASSERT(que.rest() == i);
295 F_ASSERT(que.empty() == (i == que.capacity()));
296 F_ASSERT(que.full() == (i == 0));
297
298 if (i % 2 == 0) {
299 F_ASSERT(que.pop() == (i < que.capacity()));
300 } else {
301 F_ASSERT(que.pop<uint32_t>() == (i < que.capacity()));
302 }
303 if (i < static_cast<uint32_t>(que.capacity() - 1)) {
304 F_ASSERT(que.top<uint32_t>() == 'b' + i);
305 F_ASSERT(que.front<uint32_t>() == 'b' + i);
306 F_ASSERT(que.back<uint32_t>() == static_cast<uint32_t>('a' + que.capacity() - 1));
307 }
308 que.dump_active();
309 }
310 que.dump();
311}
312
313void testBasicQueue()
314{
315 printf("Start TestBasicQueue()\n");
316
317 const uint32_t QueElemSize = 64;
318 const uint32_t QueElemNum = 16;
319 static uint8_t s_queue_data[QueElemSize * QueElemNum];
320
321 {
322 TestQue que;
323 F_ASSERT(que.is_init() == false);
324 que.init(s_queue_data, QueElemSize, QueElemNum);
325 F_ASSERT(que.is_init());
326 F_ASSERT(que.elem_size() == QueElemSize);
327 F_ASSERT(que.capacity() == QueElemNum);
328 testQueOperation(que);
329 que.clear();
330 }
331 {
332 TestQue que(s_queue_data, QueElemSize, QueElemNum);
333 F_ASSERT(que.is_init());
334 F_ASSERT(que.elem_size() == QueElemSize);
335 F_ASSERT(que.capacity() == QueElemNum);
336 testQueOperation(que);
337 que.clear();
338 }
339
340 printf("End TestBasicQueue()\n");
341}
342#endif /* TEST_BASIC_QUEUE */
343
344#endif /* BASIC_QUEUE_H_INCLUDED */
BasicQueue
Definition: BasicQueue.h:79
CopyGuard
Definition: cpp_util.h:45
AssertParamLog
Definition: AssertInfo.h:210
BasicQueueAddrTraits
Definition: BasicQueue.h:56