1 // Copyright 2023 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14
15 #include "pw_containers/inline_var_len_entry_queue.h"
16
17 #include <cstring>
18 #include <string_view>
19 #include <variant>
20
21 #include "pw_containers_private/inline_var_len_entry_queue_test_oracle.h"
22 #include "pw_unit_test/framework.h"
23
24 namespace {
25
26 struct PushOverwrite {
27 std::string_view data;
28 };
29 struct Push {
30 std::string_view data;
31 };
32 struct TryPush {
33 std::string_view data;
34 bool expected;
35 };
36 struct Pop {};
37 struct Clear {};
38 struct SizeEquals {
39 size_t expected;
40 };
41
42 using TestStep =
43 std::variant<PushOverwrite, Push, TryPush, Pop, Clear, SizeEquals>;
44
45 // Copies an entry, which might be wrapped, to a single std::vector.
ReadEntry(const pw_InlineVarLenEntryQueue_Iterator & it)46 std::vector<std::byte> ReadEntry(const pw_InlineVarLenEntryQueue_Iterator& it) {
47 auto entry = pw_InlineVarLenEntryQueue_GetEntry(&it);
48 std::vector<std::byte> value(entry.size_1 + entry.size_2);
49 EXPECT_EQ(value.size(),
50 pw_InlineVarLenEntryQueue_Entry_Copy(
51 &entry, value.data(), entry.size_1 + entry.size_2));
52 return value;
53 }
54
55 // Declares a test that performs a series of operations on the C and C++
56 // versions of InlineVarLenEntryQueue and the "oracle" class, and checks that
57 // they match after every step.
58 #define DATA_DRIVEN_TEST(program, max_entry_size) \
59 TEST(InlineVarLenEntryQueue, \
60 DataDrivenTest_##program##_MaxSizeBytes##max_entry_size) { \
61 pw::InlineVarLenEntryQueue<max_entry_size> cpp_queue; \
62 PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(c_queue, max_entry_size); \
63 pw::containers::InlineVarLenEntryQueueTestOracle oracle(max_entry_size); \
64 \
65 /* Check the queue sizes */ \
66 static_assert(sizeof(cpp_queue) == sizeof(c_queue)); \
67 ASSERT_EQ(cpp_queue.raw_storage().data(), \
68 reinterpret_cast<const std::byte*>(&cpp_queue)); \
69 ASSERT_EQ(cpp_queue.raw_storage().size_bytes(), \
70 pw_InlineVarLenEntryQueue_RawStorageSizeBytes(c_queue)); \
71 \
72 for (const TestStep& step : program) { \
73 /* Take the action */ \
74 if (auto ow = std::get_if<PushOverwrite>(&step); ow != nullptr) { \
75 cpp_queue.push_overwrite(pw::as_bytes(pw::span(ow->data))); \
76 pw_InlineVarLenEntryQueue_PushOverwrite( \
77 c_queue, ow->data.data(), static_cast<uint32_t>(ow->data.size())); \
78 oracle.push_overwrite(pw::as_bytes(pw::span(ow->data))); \
79 } else if (auto push = std::get_if<Push>(&step); push != nullptr) { \
80 cpp_queue.push(pw::as_bytes(pw::span(push->data))); \
81 pw_InlineVarLenEntryQueue_Push( \
82 c_queue, \
83 push->data.data(), \
84 static_cast<uint32_t>(push->data.size())); \
85 oracle.push(pw::as_bytes(pw::span(push->data))); \
86 } else if (auto try_push = std::get_if<TryPush>(&step); \
87 try_push != nullptr) { \
88 ASSERT_EQ(try_push->expected, \
89 cpp_queue.try_push(pw::as_bytes(pw::span(try_push->data)))); \
90 ASSERT_EQ(try_push->expected, \
91 pw_InlineVarLenEntryQueue_TryPush( \
92 c_queue, \
93 try_push->data.data(), \
94 static_cast<uint32_t>(try_push->data.size()))); \
95 if (try_push->expected) { \
96 oracle.push(pw::as_bytes(pw::span(try_push->data))); \
97 } \
98 } else if (std::holds_alternative<Pop>(step)) { \
99 cpp_queue.pop(); \
100 pw_InlineVarLenEntryQueue_Pop(c_queue); \
101 oracle.pop(); \
102 } else if (auto size = std::get_if<SizeEquals>(&step); \
103 size != nullptr) { \
104 const size_t actual = cpp_queue.size(); \
105 ASSERT_EQ(actual, pw_InlineVarLenEntryQueue_Size(c_queue)); \
106 ASSERT_EQ(oracle.size(), actual); \
107 ASSERT_EQ(size->expected, actual); \
108 } else if (std::holds_alternative<Clear>(step)) { \
109 cpp_queue.clear(); \
110 pw_InlineVarLenEntryQueue_Clear(c_queue); \
111 oracle.clear(); \
112 } else { \
113 FAIL() << "Unhandled case"; \
114 } \
115 /* Check sizes */ \
116 ASSERT_EQ(cpp_queue.size(), oracle.size()); \
117 ASSERT_EQ(cpp_queue.size_bytes(), oracle.size_bytes()); \
118 ASSERT_EQ(cpp_queue.max_size_bytes(), oracle.max_size_bytes()); \
119 \
120 ASSERT_EQ(pw_InlineVarLenEntryQueue_Size(c_queue), oracle.size()); \
121 ASSERT_EQ(pw_InlineVarLenEntryQueue_SizeBytes(c_queue), \
122 oracle.size_bytes()); \
123 ASSERT_EQ(pw_InlineVarLenEntryQueue_MaxSizeBytes(c_queue), \
124 oracle.max_size_bytes()); \
125 \
126 /* Compare the contents */ \
127 auto oracle_it = oracle.begin(); \
128 auto c_queue_it = pw_InlineVarLenEntryQueue_Begin(c_queue); \
129 const auto c_queue_end = pw_InlineVarLenEntryQueue_End(c_queue); \
130 uint32_t entries_compared = 0; \
131 \
132 for (auto entry : cpp_queue) { \
133 entries_compared += 1; \
134 \
135 ASSERT_EQ(*oracle_it, ReadEntry(c_queue_it)); \
136 ASSERT_EQ(*oracle_it, \
137 std::vector<std::byte>(entry.begin(), entry.end())); \
138 \
139 ASSERT_NE(oracle_it, oracle.end()); \
140 ASSERT_FALSE(pw_InlineVarLenEntryQueue_Iterator_Equal(&c_queue_it, \
141 &c_queue_end)); \
142 \
143 ++oracle_it; \
144 pw_InlineVarLenEntryQueue_Iterator_Advance(&c_queue_it); \
145 } \
146 ASSERT_EQ(entries_compared, oracle.size()); \
147 ASSERT_TRUE(pw_InlineVarLenEntryQueue_Iterator_Equal(&c_queue_it, \
148 &c_queue_end)); \
149 ASSERT_EQ(oracle_it, oracle.end()); \
150 } \
151 } \
152 static_assert(true, "use a semicolon")
153
154 constexpr TestStep kPop[] = {
155 SizeEquals{0},
156 PushOverwrite{""},
157 SizeEquals{1},
158 Pop{},
159 SizeEquals{0},
160 };
161
162 DATA_DRIVEN_TEST(kPop, 0); // Only holds one empty entry.
163 DATA_DRIVEN_TEST(kPop, 1);
164 DATA_DRIVEN_TEST(kPop, 6);
165
166 constexpr TestStep kOverwriteLargeEntriesWithSmall[] = {
167 PushOverwrite{"12345"},
168 PushOverwrite{"abcde"},
169 PushOverwrite{""},
170 PushOverwrite{""},
171 PushOverwrite{""},
172 PushOverwrite{""},
173 PushOverwrite{""},
174 PushOverwrite{""},
175 SizeEquals{6},
176 Pop{},
177 Pop{},
178 Pop{},
179 Pop{},
180 Pop{},
181 Pop{},
182 SizeEquals{0},
183 };
184 DATA_DRIVEN_TEST(kOverwriteLargeEntriesWithSmall, 5);
185 DATA_DRIVEN_TEST(kOverwriteLargeEntriesWithSmall, 6);
186 DATA_DRIVEN_TEST(kOverwriteLargeEntriesWithSmall, 7);
187
188 constexpr TestStep kOverwriteVaryingSizes012[] = {
189 PushOverwrite{""}, PushOverwrite{""}, PushOverwrite{""},
190 PushOverwrite{""}, PushOverwrite{""}, PushOverwrite{"1"},
191 PushOverwrite{"2"}, PushOverwrite{""}, PushOverwrite{"3"},
192 PushOverwrite{"4"}, PushOverwrite{""}, PushOverwrite{"5"},
193 PushOverwrite{"6"}, PushOverwrite{"ab"}, PushOverwrite{"cd"},
194 PushOverwrite{""}, PushOverwrite{"ef"}, PushOverwrite{"gh"},
195 PushOverwrite{"ij"},
196 };
197 DATA_DRIVEN_TEST(kOverwriteVaryingSizes012, 2);
198 DATA_DRIVEN_TEST(kOverwriteVaryingSizes012, 3);
199
200 constexpr TestStep kOverwriteVaryingSizesUpTo4[] = {
201 PushOverwrite{""},
202 PushOverwrite{""},
203 PushOverwrite{""},
204 PushOverwrite{"1"},
205 PushOverwrite{"2"},
206 PushOverwrite{"3"},
207 PushOverwrite{"ab"},
208 PushOverwrite{"cd"},
209 PushOverwrite{"ef"},
210 PushOverwrite{"123"},
211 PushOverwrite{"456"},
212 PushOverwrite{"789"},
213 PushOverwrite{"abcd"},
214 PushOverwrite{"efgh"},
215 PushOverwrite{"ijkl"},
216 TryPush{"uhoh", false},
217 Pop{},
218 SizeEquals{0},
219 };
220 DATA_DRIVEN_TEST(kOverwriteVaryingSizesUpTo4, 4);
221 DATA_DRIVEN_TEST(kOverwriteVaryingSizesUpTo4, 5);
222 DATA_DRIVEN_TEST(kOverwriteVaryingSizesUpTo4, 6);
223
224 constexpr char kBigEntryBytes[196]{};
225
226 template <size_t kSizeBytes>
227 constexpr std::string_view kBigEntry(kBigEntryBytes, kSizeBytes);
228
229 constexpr TestStep kTwoBytePrefix[] = {
230 PushOverwrite{kBigEntry<128>},
231 PushOverwrite{kBigEntry<128>},
232 PushOverwrite{kBigEntry<127>},
233 PushOverwrite{kBigEntry<128>},
234 PushOverwrite{kBigEntry<127>},
235 SizeEquals{1},
236 Pop{},
237 SizeEquals{0},
238 };
239 DATA_DRIVEN_TEST(kTwoBytePrefix, 128);
240 DATA_DRIVEN_TEST(kTwoBytePrefix, 129);
241
242 constexpr TestStep kClear[] = {
243 Push{"abcdefg"},
244 PushOverwrite{""},
245 PushOverwrite{""},
246 PushOverwrite{"a"},
247 PushOverwrite{"b"},
248 Clear{},
249 SizeEquals{0},
250 Clear{},
251 };
252 DATA_DRIVEN_TEST(kClear, 7);
253 DATA_DRIVEN_TEST(kClear, 100);
254
255 constexpr TestStep kTryPushMaxSize5[] = {
256 TryPush{"", true},
257 TryPush{"", true},
258 TryPush{"", true},
259 TryPush{"", true},
260 TryPush{"", true},
261 TryPush{"", true}, // max_size_bytes() of 5 => up to 6 empty entries
262 TryPush{"", false},
263 TryPush{"1", false},
264 Clear{},
265 TryPush{"12345", true},
266 TryPush{"", false},
267 };
268 DATA_DRIVEN_TEST(kTryPushMaxSize5, 5);
269
270 constexpr TestStep kPushPopLargeEntry[] = {
271 Push{kBigEntry<196>},
272 TryPush{kBigEntry<196>, false},
273 Pop{},
274 Push{kBigEntry<196>},
275 TryPush{"", true},
276 Pop{},
277 TryPush{"1", true},
278 TryPush{kBigEntry<196>, true},
279 TryPush{"12", true},
280 Pop{},
281 Pop{},
282 Pop{},
283 TryPush{kBigEntry<196>, true},
284 TryPush{kBigEntry<196>, false},
285 };
286 DATA_DRIVEN_TEST(kPushPopLargeEntry, 255);
287 DATA_DRIVEN_TEST(kPushPopLargeEntry, 256);
288 DATA_DRIVEN_TEST(kPushPopLargeEntry, 257);
289
TEST(InlineVarLenEntryQueue,DeclareMacro)290 TEST(InlineVarLenEntryQueue, DeclareMacro) {
291 PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(queue, 123);
292
293 constexpr size_t kArraySizeBytes =
294 123 + 1 /*prefix*/ + 1 /* end */ + 3 /* round up */ +
295 PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32 * 4;
296 static_assert(sizeof(queue) == kArraySizeBytes);
297 EXPECT_EQ(pw_InlineVarLenEntryQueue_RawStorageSizeBytes(queue),
298 kArraySizeBytes - 3 /* padding isn't included */);
299
300 EXPECT_EQ(pw_InlineVarLenEntryQueue_MaxSizeBytes(queue), 123u);
301 EXPECT_EQ(pw_InlineVarLenEntryQueue_SizeBytes(queue), 0u);
302 EXPECT_TRUE(pw_InlineVarLenEntryQueue_Empty(queue));
303 }
304
TEST(InlineVarLenEntryQueue,InitializeExistingBuffer)305 TEST(InlineVarLenEntryQueue, InitializeExistingBuffer) {
306 constexpr size_t kArraySize =
307 10 + PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32;
308 uint32_t queue[kArraySize];
309 pw_InlineVarLenEntryQueue_Init(queue, kArraySize);
310
311 EXPECT_EQ(pw_InlineVarLenEntryQueue_RawStorageSizeBytes(queue),
312 sizeof(queue));
313 EXPECT_EQ(pw_InlineVarLenEntryQueue_MaxSizeBytes(queue),
314 sizeof(uint32_t) * 10u - 1 /*prefix*/ - 1 /*end*/);
315 EXPECT_EQ(pw_InlineVarLenEntryQueue_SizeBytes(queue), 0u);
316 EXPECT_EQ(pw_InlineVarLenEntryQueue_Size(queue), 0u);
317 EXPECT_TRUE(pw_InlineVarLenEntryQueue_Empty(queue));
318 }
319
TEST(InlineVarLenEntryQueue,MaxSizeElement)320 TEST(InlineVarLenEntryQueue, MaxSizeElement) {
321 // Test max size elements for a few sizes. Commented out statements fail an
322 // assert because the elements are too large.
323 PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(q16, 126);
324 PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(q17, 127);
325 PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(q18, 128);
326 PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(q19, 129);
327
328 pw_InlineVarLenEntryQueue_PushOverwrite(q16, kBigEntryBytes, 126);
329 pw_InlineVarLenEntryQueue_PushOverwrite(q17, kBigEntryBytes, 126);
330 pw_InlineVarLenEntryQueue_PushOverwrite(q18, kBigEntryBytes, 126);
331 pw_InlineVarLenEntryQueue_PushOverwrite(q19, kBigEntryBytes, 126);
332
333 // pw_InlineVarLenEntryQueue_PushOverwrite(q16, kBigEntryBytes, 127);
334 pw_InlineVarLenEntryQueue_PushOverwrite(q17, kBigEntryBytes, 127);
335 pw_InlineVarLenEntryQueue_PushOverwrite(q18, kBigEntryBytes, 127);
336 pw_InlineVarLenEntryQueue_PushOverwrite(q19, kBigEntryBytes, 127);
337
338 // pw_InlineVarLenEntryQueue_PushOverwrite(q16, kBigEntryBytes, 128);
339 // pw_InlineVarLenEntryQueue_PushOverwrite(q17, kBigEntryBytes, 128);
340 pw_InlineVarLenEntryQueue_PushOverwrite(q18, kBigEntryBytes, 128);
341 pw_InlineVarLenEntryQueue_PushOverwrite(q19, kBigEntryBytes, 128);
342
343 // pw_InlineVarLenEntryQueue_PushOverwrite(q16, kBigEntryBytes, 129);
344 // pw_InlineVarLenEntryQueue_PushOverwrite(q17, kBigEntryBytes, 129);
345 // pw_InlineVarLenEntryQueue_PushOverwrite(q18, kBigEntryBytes, 129);
346 pw_InlineVarLenEntryQueue_PushOverwrite(q19, kBigEntryBytes, 129);
347
348 EXPECT_EQ(pw_InlineVarLenEntryQueue_Size(q16), 1u);
349 EXPECT_EQ(pw_InlineVarLenEntryQueue_Size(q17), 1u);
350 EXPECT_EQ(pw_InlineVarLenEntryQueue_Size(q18), 1u);
351 EXPECT_EQ(pw_InlineVarLenEntryQueue_Size(q19), 1u);
352 }
353
354 constexpr const char* kStrings[] = {"Haart", "Sandro", "", "Gelu", "Solmyr"};
355
TEST(InlineVarLenEntryQueueClass,Iterate)356 TEST(InlineVarLenEntryQueueClass, Iterate) {
357 pw::BasicInlineVarLenEntryQueue<char, 32> queue;
358
359 for (const char* string : kStrings) {
360 queue.push(std::string_view(string));
361 }
362
363 uint32_t i = 0;
364 for (auto entry : queue) {
365 char value[8]{};
366 entry.copy(value, sizeof(value));
367 EXPECT_STREQ(value, kStrings[i++]);
368 }
369 ASSERT_EQ(i, 5u);
370 }
371
TEST(InlineVarLenEntryQueueClass,IterateOverwrittenElements)372 TEST(InlineVarLenEntryQueueClass, IterateOverwrittenElements) {
373 pw::BasicInlineVarLenEntryQueue<char, 6> queue;
374
375 for (const char* string : kStrings) {
376 queue.push_overwrite(std::string_view(string));
377 }
378
379 ASSERT_EQ(queue.size(), 1u);
380
381 for (auto entry : queue) {
382 char value[8]{};
383 EXPECT_EQ(6u, entry.copy(value, sizeof(value)));
384 EXPECT_STREQ(value, "Solmyr");
385 }
386 }
387
TEST(InlineVarLenEntryQueueClass,InitializeExistingBuffer)388 TEST(InlineVarLenEntryQueueClass, InitializeExistingBuffer) {
389 constexpr size_t kArraySize =
390 10 + PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32;
391 uint32_t queue_array[kArraySize]{50, 50, 99};
392 pw::InlineVarLenEntryQueue<>& queue =
393 pw::InlineVarLenEntryQueue<>::Init(queue_array, kArraySize);
394
395 EXPECT_EQ(queue.raw_storage().data(),
396 reinterpret_cast<const std::byte*>(queue_array));
397 EXPECT_EQ(queue.raw_storage().size_bytes(), sizeof(queue_array));
398 EXPECT_EQ(queue.max_size_bytes(),
399 sizeof(uint32_t) * 10u - 1 /*prefix*/ - 1 /*end*/);
400 EXPECT_EQ(queue.size_bytes(), 0u);
401 EXPECT_EQ(queue.size(), 0u);
402 EXPECT_TRUE(queue.empty());
403 }
404
TEST(InlineVarLenEntryQueueClass,MaxSizeOneBytePrefix)405 TEST(InlineVarLenEntryQueueClass, MaxSizeOneBytePrefix) {
406 pw::InlineVarLenEntryQueue<127> queue;
407 EXPECT_EQ(queue.max_size(), 128u);
408
409 while (queue.try_push({})) {
410 }
411 EXPECT_EQ(queue.size(), queue.max_size());
412 EXPECT_EQ(queue.size_bytes(), 0u);
413 }
414
TEST(InlineVarLenEntryQueueClass,MaxSizeTwoBytePrefix)415 TEST(InlineVarLenEntryQueueClass, MaxSizeTwoBytePrefix) {
416 pw::InlineVarLenEntryQueue<128> queue;
417 EXPECT_EQ(queue.max_size(), 130u);
418
419 while (queue.try_push({})) {
420 }
421 EXPECT_EQ(queue.size(), queue.max_size());
422 EXPECT_EQ(queue.size_bytes(), 0u);
423 }
424
TEST(InlineVarLenEntryQueueClass,Entry)425 TEST(InlineVarLenEntryQueueClass, Entry) {
426 pw::BasicInlineVarLenEntryQueue<char, 5> queue;
427 queue.push("12"); // Split the next entry across the end.
428 queue.push_overwrite(std::string_view("ABCDE"));
429
430 decltype(queue)::Entry front = queue.front();
431
432 ASSERT_EQ(front.size(), 5u);
433 EXPECT_EQ(front[0], 'A');
434 EXPECT_EQ(front[1], 'B');
435 EXPECT_EQ(front[2], 'C');
436 EXPECT_EQ(front[3], 'D');
437 EXPECT_EQ(front[4], 'E');
438
439 EXPECT_EQ(front.at(0), 'A');
440 EXPECT_EQ(front.at(1), 'B');
441 EXPECT_EQ(front.at(2), 'C');
442 EXPECT_EQ(front.at(3), 'D');
443 EXPECT_EQ(front.at(4), 'E');
444
445 const auto [span_1, span_2] = front.contiguous_data();
446 EXPECT_EQ(span_1.size(), 2u);
447 EXPECT_EQ(std::memcmp(span_1.data(), "AB", 2u), 0);
448 EXPECT_EQ(span_2.size(), 3u);
449 EXPECT_EQ(std::memcmp(span_2.data(), "CDE", 3u), 0);
450
451 const char* expected_ptr = "ABCDE";
452 for (char c : front) {
453 EXPECT_EQ(*expected_ptr, c);
454 ++expected_ptr;
455 }
456
457 // Check the iterators with std::copy and std::equal.
458 char value[6] = {};
459 std::copy(front.begin(), front.end(), value);
460 EXPECT_STREQ(value, "ABCDE");
461
462 EXPECT_TRUE(std::equal(front.begin(), front.end(), "ABCDE"));
463 }
464
TEST(InlineVarLenEntryQueueClass,Construct_Constexpr)465 TEST(InlineVarLenEntryQueueClass, Construct_Constexpr) {
466 constexpr pw::InlineVarLenEntryQueue<127> queue(pw::kConstexpr);
467 EXPECT_TRUE(queue.empty());
468 EXPECT_EQ(queue.max_size(), 128u);
469 EXPECT_EQ(queue.size(), 0u);
470 }
471
472 } // namespace
473