Blender V5.3
BLI_array_store_test.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: Apache-2.0 */
4
5#include "testing/testing.h"
6
7#include "MEM_guardedalloc.h"
8
9#include "BLI_array_store.hh"
10#include "BLI_array_utils_c.hh"
11#include "BLI_listbase.hh"
12#include "BLI_rand_c.hh"
14#include "BLI_string.hh"
15#include "BLI_sys_types.hh"
16#include "BLI_utildefines.hh"
17
18namespace blender {
19
20/* print memory savings */
21// #define DEBUG_PRINT
22
23/* Print time. */
24// #define DEBUG_TIME
25#ifdef DEBUG_TIME
26# include "BLI_time.hh"
28#endif
29
30/* -------------------------------------------------------------------- */
31/* Helper functions */
32
33#ifdef DEBUG_PRINT
34static void print_mem_saved(const char *id, const BArrayStore *bs)
35{
36 const double size_real = BLI_array_store_calc_size_compacted_get(bs);
37 const double size_expand = BLI_array_store_calc_size_expanded_get(bs);
38 const double percent = size_expand ? ((size_real / size_expand) * 100.0) : -1.0;
39 printf("%s: %.8f%%\n", id, percent);
40}
41#endif
42
43/* -------------------------------------------------------------------- */
44/* Test Chunks (building data from list of chunks) */
45
46struct TestChunk {
48 const void *data;
49 size_t data_len;
50};
51
52static TestChunk *testchunk_list_add(ListBaseT<TestChunk> *lb, const void *data, size_t data_len)
53{
55 tc->data = data;
56 tc->data_len = data_len;
57 BLI_addtail(lb, tc);
58
59 return tc;
60}
61
62#if 0
63static TestChunk *testchunk_list_add_copydata(ListBaseT<TestChunk> *lb, const void *data, size_t data_len)
64{
65 void *data_copy = MEM_new_uninitialized(data_len, __func__);
66 memcpy(data_copy, data, data_len);
67 return testchunk_list_add(lb, data_copy, data_len);
68}
69#endif
70
71static void testchunk_list_free(ListBaseT<TestChunk> *lb)
72{
73 for (TestChunk *tc = lb->first(), *tb_next; tc; tc = tb_next) {
74 tb_next = tc->next;
75 MEM_delete_void(const_cast<void *>(tc->data));
76 MEM_delete(tc);
77 }
78 lb->clear_no_delete();
79}
80
81#if 0
82static char *testchunk_as_data(ListBaseT<TestChunk> *lb, size_t *r_data_len)
83{
84 size_t data_len = 0;
85 for (TestChunk *tc = (TestChunk *)lb->first; tc; tc = tc->next) {
86 data_len += tc->data_len;
87 }
88 char *data = MEM_new_array_uninitialized<char>(data_len, __func__);
89 size_t i = 0;
90 for (TestChunk *tc = (TestChunk *)lb->first; tc; tc = tc->next) {
91 memcpy(&data[i], tc->data, tc->data_len);
92 data_len += tc->data_len;
93 i += tc->data_len;
94 }
95 if (r_data_len) {
96 *r_data_len = i;
97 }
98 return data;
99}
100#endif
101
102static char *testchunk_as_data_array(TestChunk **tc_array, int tc_array_len, size_t *r_data_len)
103{
104 size_t data_len = 0;
105 for (int tc_index = 0; tc_index < tc_array_len; tc_index++) {
106 data_len += tc_array[tc_index]->data_len;
107 }
108 char *data = MEM_new_array_uninitialized<char>(data_len, __func__);
109 size_t i = 0;
110 for (int tc_index = 0; tc_index < tc_array_len; tc_index++) {
111 TestChunk *tc = tc_array[tc_index];
112 memcpy(&data[i], tc->data, tc->data_len);
113 i += tc->data_len;
114 }
115 if (r_data_len) {
116 *r_data_len = i;
117 }
118 return data;
119}
120
121/* -------------------------------------------------------------------- */
122/* Test Buffer */
123
124/* API to handle local allocation of data so we can compare it with the data in the array_store */
127 const void *data;
128 size_t data_len;
129
130 /* for reference */
132};
133
134static TestBuffer *testbuffer_list_add(ListBaseT<TestBuffer> *lb,
135 const void *data,
136 size_t data_len)
137{
139 tb->data = data;
140 tb->data_len = data_len;
141 tb->state = nullptr;
142 BLI_addtail(lb, tb);
143 return tb;
144}
145
146static TestBuffer *testbuffer_list_add_copydata(ListBaseT<TestBuffer> *lb,
147 const void *data,
148 size_t data_len)
149{
150 void *data_copy = MEM_new_uninitialized(data_len, __func__);
151 memcpy(data_copy, data, data_len);
152 return testbuffer_list_add(lb, data_copy, data_len);
153}
154
155static void testbuffer_list_state_from_data(ListBaseT<TestBuffer> *lb,
156 const char *data,
157 const size_t data_len)
158{
159 testbuffer_list_add_copydata(lb, static_cast<const void *>(data), data_len);
160}
161
166static void testbuffer_list_state_from_data__stride_expand(ListBaseT<TestBuffer> *lb,
167 const char *data,
168 const size_t data_len,
169 const size_t stride)
170{
171 if (stride == 1) {
173 }
174 else {
175 const size_t data_stride_len = data_len * stride;
176 char *data_stride = MEM_new_array_uninitialized<char>(data_stride_len, __func__);
177
178 for (size_t i = 0, i_stride = 0; i < data_len; i += 1, i_stride += stride) {
179 memset(&data_stride[i_stride], data[i], stride);
180 }
181
182 testbuffer_list_add(lb, static_cast<const void *>(data_stride), data_stride_len);
183 }
184}
185
186#define testbuffer_list_state_from_string_array(lb, data_array) \
187 { \
188 uint i_ = 0; \
189 const char *data; \
190 while ((data = data_array[i_++])) { \
191 testbuffer_list_state_from_data(lb, data, strlen(data)); \
192 } \
193 } \
194 ((void)0)
195
196//
197
198#define TESTBUFFER_STRINGS_CREATE(lb, ...) \
199 { \
200 BLI_listbase_clear(lb); \
201 const char *data_array[] = {__VA_ARGS__ nullptr}; \
202 testbuffer_list_state_from_string_array((lb), data_array); \
203 } \
204 ((void)0)
205
206/* test in both directions */
207#define TESTBUFFER_STRINGS(stride, chunk_count, ...) \
208 { \
209 ListBaseT<TestBuffer> lb; \
210 TESTBUFFER_STRINGS_CREATE(&lb, __VA_ARGS__); \
211\
212 testbuffer_run_tests_simple(&lb, stride, chunk_count); \
213\
214 testbuffer_list_free(&lb); \
215 } \
216 ((void)0)
217
219{
220 size_t data_state_len;
221 bool ok = true;
222 void *data_state = BLI_array_store_state_data_get_alloc(tb->state, &data_state_len);
223 if (tb->data_len != data_state_len) {
224 ok = false;
225 }
226 else if (memcmp(data_state, tb->data, data_state_len) != 0) {
227 ok = false;
228 }
229 MEM_delete_void(data_state);
230 return ok;
231}
232
233static bool testbuffer_list_validate(const ListBaseT<TestBuffer> *lb)
234{
235 for (TestBuffer &tb : *lb) {
236 if (!testbuffer_item_validate(&tb)) {
237 return false;
238 }
239 }
240
241 return true;
242}
243
244static void testbuffer_list_data_randomize(ListBaseT<TestBuffer> *lb, uint random_seed)
245{
246 for (TestBuffer &tb : *lb) {
247 BLI_array_randomize((void *)tb.data, 1, tb.data_len, random_seed++);
248 }
249}
250
251static void testbuffer_list_store_populate(BArrayStore *bs, ListBaseT<TestBuffer> *lb)
252{
253 for (TestBuffer *tb = lb->first(), *tb_prev = nullptr; tb; tb_prev = tb, tb = tb->next) {
254 tb->state = BLI_array_store_state_add(
255 bs, tb->data, tb->data_len, (tb_prev ? tb_prev->state : nullptr));
256 }
257}
258
259static void testbuffer_list_store_clear(BArrayStore *bs, ListBaseT<TestBuffer> *lb)
260{
261 for (TestBuffer &tb : *lb) {
262 BLI_array_store_state_remove(bs, tb.state);
263 tb.state = nullptr;
264 }
265}
266
267static void testbuffer_list_free(ListBaseT<TestBuffer> *lb)
268{
269 for (TestBuffer *tb = lb->first(), *tb_next; tb; tb = tb_next) {
270 tb_next = tb->next;
271 MEM_delete_void(const_cast<void *>(tb->data));
272 MEM_delete(tb);
273 }
274 lb->clear_no_delete();
275}
276
277static void testbuffer_run_tests_single(BArrayStore *bs, ListBaseT<TestBuffer> *lb)
278{
282#ifdef DEBUG_PRINT
283 print_mem_saved("data", bs);
284#endif
285}
286
287/* avoid copy-paste code to run tests */
288static void testbuffer_run_tests(BArrayStore *bs, ListBaseT<TestBuffer> *lb)
289{
290 /* forwards */
293
295
296 /* backwards */
299}
300
301static void testbuffer_run_tests_simple(ListBaseT<TestBuffer> *lb,
302 const int stride,
303 const int chunk_count)
304{
305 BArrayStore *bs = BLI_array_store_create(stride, chunk_count);
306 testbuffer_run_tests(bs, lb);
308}
309
310/* -------------------------------------------------------------------- */
311/* Basic Tests */
312
313TEST(array_store, Nop)
314{
317}
318
319TEST(array_store, NopState)
320{
322 const uchar data[] = "test";
323 BArrayState *state = BLI_array_store_state_add(bs, data, sizeof(data) - 1, nullptr);
327}
328
329TEST(array_store, Single)
330{
332 const char data_src[] = "test";
333 const char *data_dst;
334 BArrayState *state = BLI_array_store_state_add(bs, data_src, sizeof(data_src), nullptr);
335 size_t data_dst_len;
336 data_dst = static_cast<char *>(BLI_array_store_state_data_get_alloc(state, &data_dst_len));
337 EXPECT_STREQ(data_src, data_dst);
338 EXPECT_EQ(data_dst_len, sizeof(data_src));
340 MEM_delete(data_dst);
341}
342
343TEST(array_store, DoubleNop)
344{
346 const char data_src[] = "test";
347 const char *data_dst;
348
349 BArrayState *state_a = BLI_array_store_state_add(bs, data_src, sizeof(data_src), nullptr);
350 BArrayState *state_b = BLI_array_store_state_add(bs, data_src, sizeof(data_src), state_a);
351
353 EXPECT_EQ(BLI_array_store_calc_size_expanded_get(bs), sizeof(data_src) * 2);
354
355 size_t data_dst_len;
356
357 data_dst = static_cast<char *>(BLI_array_store_state_data_get_alloc(state_a, &data_dst_len));
358 EXPECT_STREQ(data_src, data_dst);
359 MEM_delete(data_dst);
360
361 data_dst = static_cast<char *>(BLI_array_store_state_data_get_alloc(state_b, &data_dst_len));
362 EXPECT_STREQ(data_src, data_dst);
363 MEM_delete(data_dst);
364
365 EXPECT_EQ(data_dst_len, sizeof(data_src));
367}
368
369TEST(array_store, DoubleDiff)
370{
372 const char data_src_a[] = "test";
373 const char data_src_b[] = "####";
374 const char *data_dst;
375
376 BArrayState *state_a = BLI_array_store_state_add(bs, data_src_a, sizeof(data_src_a), nullptr);
377 BArrayState *state_b = BLI_array_store_state_add(bs, data_src_b, sizeof(data_src_b), state_a);
378 size_t data_dst_len;
379
380 EXPECT_EQ(BLI_array_store_calc_size_compacted_get(bs), sizeof(data_src_a) * 2);
381 EXPECT_EQ(BLI_array_store_calc_size_expanded_get(bs), sizeof(data_src_a) * 2);
382
383 data_dst = static_cast<char *>(BLI_array_store_state_data_get_alloc(state_a, &data_dst_len));
384 EXPECT_STREQ(data_src_a, data_dst);
385 MEM_delete(data_dst);
386
387 data_dst = static_cast<char *>(BLI_array_store_state_data_get_alloc(state_b, &data_dst_len));
388 EXPECT_STREQ(data_src_b, data_dst);
389 MEM_delete(data_dst);
390
392}
393
394TEST(array_store, TextMixed)
395{
396 TESTBUFFER_STRINGS(1, 4, "", );
397 TESTBUFFER_STRINGS(1, 4, "test", );
398 TESTBUFFER_STRINGS(1, 4, "", "test", );
399 TESTBUFFER_STRINGS(1, 4, "test", "", );
400 TESTBUFFER_STRINGS(1, 4, "test", "", "test", );
401 TESTBUFFER_STRINGS(1, 4, "", "test", "", );
402}
403
404TEST(array_store, TextDupeIncreaseDecrease)
405{
406 ListBaseT<TestBuffer> lb;
407
408#define D "#1#2#3#4"
409 TESTBUFFER_STRINGS_CREATE(&lb, D, D D, D D D, D D D D, );
410
412
413 /* forward */
418
421
422 /* backwards */
426 /* larger since first block doesn't de-duplicate */
428
429#undef D
431
433}
434
435/* -------------------------------------------------------------------- */
436/* Plain Text Tests */
437
442static void plain_text_helper(const char *words,
443 int words_len,
444 const char word_delim,
445 const int stride,
446 const int chunk_count,
447 const int random_seed)
448{
449
450 ListBaseT<TestBuffer> lb;
451 lb.clear_no_delete();
452
453 for (int i = 0, i_prev = 0; i < words_len; i++) {
454 if (ELEM(words[i], word_delim, '\0')) {
455 if (i != i_prev) {
456 testbuffer_list_state_from_data__stride_expand(&lb, &words[i_prev], i - i_prev, stride);
457 }
458 i_prev = i;
459 }
460 }
461
462 if (random_seed) {
463 testbuffer_list_data_randomize(&lb, random_seed);
464 }
465
466 testbuffer_run_tests_simple(&lb, stride, chunk_count);
467
469}
470
471/* split by '.' (multiple words) */
472#define WORDS words10k, sizeof(words10k)
473TEST(array_store, TextSentences_Chunk1)
474{
475 plain_text_helper(WORDS, '.', 1, 1, 0);
476}
477TEST(array_store, TextSentences_Chunk2)
478{
479 plain_text_helper(WORDS, '.', 1, 2, 0);
480}
481TEST(array_store, TextSentences_Chunk8)
482{
483 plain_text_helper(WORDS, '.', 1, 8, 0);
484}
485TEST(array_store, TextSentences_Chunk32)
486{
487 plain_text_helper(WORDS, '.', 1, 32, 0);
488}
489TEST(array_store, TextSentences_Chunk128)
490{
491 plain_text_helper(WORDS, '.', 1, 128, 0);
492}
493TEST(array_store, TextSentences_Chunk1024)
494{
495 plain_text_helper(WORDS, '.', 1, 1024, 0);
496}
497/* odd numbers */
498TEST(array_store, TextSentences_Chunk3)
499{
500 plain_text_helper(WORDS, '.', 1, 3, 0);
501}
502TEST(array_store, TextSentences_Chunk13)
503{
504 plain_text_helper(WORDS, '.', 1, 13, 0);
505}
506TEST(array_store, TextSentences_Chunk131)
507{
508 plain_text_helper(WORDS, '.', 1, 131, 0);
509}
510
511/* split by ' ', individual words */
512TEST(array_store, TextWords_Chunk1)
513{
514 plain_text_helper(WORDS, ' ', 1, 1, 0);
515}
516TEST(array_store, TextWords_Chunk2)
517{
518 plain_text_helper(WORDS, ' ', 1, 2, 0);
519}
520TEST(array_store, TextWords_Chunk8)
521{
522 plain_text_helper(WORDS, ' ', 1, 8, 0);
523}
524TEST(array_store, TextWords_Chunk32)
525{
526 plain_text_helper(WORDS, ' ', 1, 32, 0);
527}
528TEST(array_store, TextWords_Chunk128)
529{
530 plain_text_helper(WORDS, ' ', 1, 128, 0);
531}
532TEST(array_store, TextWords_Chunk1024)
533{
534 plain_text_helper(WORDS, ' ', 1, 1024, 0);
535}
536/* odd numbers */
537TEST(array_store, TextWords_Chunk3)
538{
539 plain_text_helper(WORDS, ' ', 1, 3, 0);
540}
541TEST(array_store, TextWords_Chunk13)
542{
543 plain_text_helper(WORDS, ' ', 1, 13, 0);
544}
545TEST(array_store, TextWords_Chunk131)
546{
547 plain_text_helper(WORDS, ' ', 1, 131, 0);
548}
549
550/* various tests with different strides & randomizing */
551TEST(array_store, TextSentencesRandom_Stride3_Chunk3)
552{
553 plain_text_helper(WORDS, 'q', 3, 3, 7337);
554}
555TEST(array_store, TextSentencesRandom_Stride8_Chunk8)
556{
557 plain_text_helper(WORDS, 'n', 8, 8, 5667);
558}
559TEST(array_store, TextSentencesRandom_Stride32_Chunk1)
560{
561 plain_text_helper(WORDS, 'a', 1, 32, 1212);
562}
563TEST(array_store, TextSentencesRandom_Stride12_Chunk512)
564{
565 plain_text_helper(WORDS, 'g', 12, 512, 9999);
566}
567TEST(array_store, TextSentencesRandom_Stride128_Chunk6)
568{
569 plain_text_helper(WORDS, 'b', 20, 6, 1000);
570}
571
572#undef WORDS
573
574/* -------------------------------------------------------------------- */
575/* Random Data Tests */
576
577static uint rand_range_i(RNG *rng, uint min_i, uint max_i, uint step)
578{
579 if (min_i == max_i) {
580 return min_i;
581 }
582 BLI_assert(min_i <= max_i);
583 BLI_assert(((min_i % step) == 0) && ((max_i % step) == 0));
584 uint range = (max_i - min_i);
585 uint value = BLI_rng_get_uint(rng) % range;
586 value = (value / step) * step;
587 return min_i + value;
588}
589
590static void testbuffer_list_state_random_data(ListBaseT<TestBuffer> *lb,
591 const size_t stride,
592 const size_t data_min_len,
593 const size_t data_max_len,
594
595 const uint mutate,
596 RNG *rng)
597{
598 size_t data_len = rand_range_i(rng, data_min_len, data_max_len + stride, stride);
599 char *data = MEM_new_array_uninitialized<char>(data_len, __func__);
600
601 if (lb->last_ == nullptr) {
602 BLI_rng_get_char_n(rng, data, data_len);
603 }
604 else {
605 TestBuffer *tb_last = static_cast<TestBuffer *>(lb->last_);
606 if (tb_last->data_len >= data_len) {
607 memcpy(data, tb_last->data, data_len);
608 }
609 else {
610 memcpy(data, tb_last->data, tb_last->data_len);
611 BLI_rng_get_char_n(rng, &data[tb_last->data_len], data_len - tb_last->data_len);
612 }
613
614 /* perform multiple small mutations to the array. */
615 for (int i = 0; i < mutate; i++) {
616 enum {
617 MUTATE_NOP = 0,
618 MUTATE_ADD,
619 MUTATE_REMOVE,
620 MUTATE_ROTATE,
621 MUTATE_RANDOMIZE,
622 MUTATE_TOTAL,
623 };
624
625 switch (BLI_rng_get_uint(rng) % MUTATE_TOTAL) {
626 case MUTATE_NOP: {
627 break;
628 }
629 case MUTATE_ADD: {
630 const uint offset = rand_range_i(rng, 0, data_len, stride);
631 if (data_len < data_max_len) {
632 data_len += stride;
633 data = static_cast<char *>(MEM_realloc_uninitialized((void *)data, data_len));
634 memmove(&data[offset + stride], &data[offset], data_len - (offset + stride));
635 BLI_rng_get_char_n(rng, &data[offset], stride);
636 }
637 break;
638 }
639 case MUTATE_REMOVE: {
640 const uint offset = rand_range_i(rng, 0, data_len, stride);
641 if (data_len > data_min_len) {
642 memmove(&data[offset], &data[offset + stride], data_len - (offset + stride));
643 data_len -= stride;
644 }
645 break;
646 }
647 case MUTATE_ROTATE: {
648 int items = data_len / stride;
649 if (items > 1) {
650 _bli_array_wrap(data, items, stride, (BLI_rng_get_uint(rng) % 2) ? -1 : 1);
651 }
652 break;
653 }
654 case MUTATE_RANDOMIZE: {
655 if (data_len > 0) {
656 const uint offset = rand_range_i(rng, 0, data_len - stride, stride);
657 BLI_rng_get_char_n(rng, &data[offset], stride);
658 }
659 break;
660 }
661 default:
663 }
664 }
665 }
666
667 testbuffer_list_add(lb, static_cast<const void *>(data), data_len);
668}
669
670static void random_data_mutate_helper(const int items_size_min,
671 const int items_size_max,
672 const int items_total,
673 const int stride,
674 const int chunk_count,
675 const int random_seed,
676 const int mutate)
677{
678
679 ListBaseT<TestBuffer> lb;
680 lb.clear_no_delete();
681
682 const size_t data_min_len = items_size_min * stride;
683 const size_t data_max_len = items_size_max * stride;
684
685 {
686 RNG *rng = BLI_rng_new(random_seed);
687 for (int i = 0; i < items_total; i++) {
688 testbuffer_list_state_random_data(&lb, stride, data_min_len, data_max_len, mutate, rng);
689 }
690 BLI_rng_free(rng);
691 }
692
693 testbuffer_run_tests_simple(&lb, stride, chunk_count);
694
696}
697
698TEST(array_store, TestData_Stride1_Chunk32_Mutate2)
699{
700 random_data_mutate_helper(0, 100, 400, 1, 32, 9779, 2);
701}
702TEST(array_store, TestData_Stride8_Chunk512_Mutate2)
703{
704 random_data_mutate_helper(0, 128, 400, 8, 512, 1001, 2);
705}
706TEST(array_store, TestData_Stride12_Chunk48_Mutate2)
707{
708 random_data_mutate_helper(200, 256, 400, 12, 48, 1331, 2);
709}
710TEST(array_store, TestData_Stride32_Chunk64_Mutate1)
711{
712 random_data_mutate_helper(0, 256, 200, 32, 64, 3112, 1);
713}
714TEST(array_store, TestData_Stride32_Chunk64_Mutate8)
715{
716 random_data_mutate_helper(0, 256, 200, 32, 64, 7117, 8);
717}
718
719/* -------------------------------------------------------------------- */
720/* Randomized Chunks Test */
721
722static void random_chunk_generate(ListBaseT<TestChunk> *lb,
723 const int chunks_per_buffer,
724 const int stride,
725 const int chunk_count,
726 const int random_seed)
727{
728 RNG *rng = BLI_rng_new(random_seed);
729 const size_t chunk_size_bytes = stride * chunk_count;
730 for (int i = 0; i < chunks_per_buffer; i++) {
731 char *data_chunk = MEM_new_array_uninitialized<char>(chunk_size_bytes, __func__);
732 BLI_rng_get_char_n(rng, data_chunk, chunk_size_bytes);
733 testchunk_list_add(lb, data_chunk, chunk_size_bytes);
734 }
735 BLI_rng_free(rng);
736}
737
741static void random_chunk_mutate_helper(const int chunks_per_buffer,
742 const int items_total,
743 const int stride,
744 const int chunk_count,
745 const int random_seed)
746{
747 /* generate random chunks */
748
749 ListBaseT<TestChunk> random_chunks;
750 random_chunks.clear_no_delete();
751 random_chunk_generate(&random_chunks, chunks_per_buffer, stride, chunk_count, random_seed);
752 TestChunk **chunks_array = MEM_new_array_uninitialized<TestChunk *>(size_t(chunks_per_buffer),
753 __func__);
754 {
755 TestChunk *tc = random_chunks.first();
756 for (int i = 0; i < chunks_per_buffer; i++, tc = tc->next) {
757 chunks_array[i] = tc;
758 }
759 }
760
761 /* add and re-order each time */
762 ListBaseT<TestBuffer> lb;
763 lb.clear_no_delete();
764
765 {
766 RNG *rng = BLI_rng_new(random_seed);
767 for (int i = 0; i < items_total; i++) {
768 BLI_rng_shuffle_array(rng, chunks_array, sizeof(TestChunk *), chunks_per_buffer);
769 size_t data_len;
770 char *data = testchunk_as_data_array(chunks_array, chunks_per_buffer, &data_len);
771 BLI_assert(data_len == chunks_per_buffer * chunk_count * stride);
772 testbuffer_list_add(&lb, static_cast<const void *>(data), data_len);
773 }
774 BLI_rng_free(rng);
775 }
776
777 testchunk_list_free(&random_chunks);
778 MEM_delete(chunks_array);
779
780 BArrayStore *bs = BLI_array_store_create(stride, chunk_count);
782
783 size_t expected_size = chunks_per_buffer * chunk_count * stride;
785
787
789}
790
791TEST(array_store, TestChunk_Rand8_Stride1_Chunk64)
792{
793 random_chunk_mutate_helper(8, 100, 1, 64, 9779);
794}
795TEST(array_store, TestChunk_Rand32_Stride1_Chunk64)
796{
797 random_chunk_mutate_helper(32, 100, 1, 64, 1331);
798}
799TEST(array_store, TestChunk_Rand64_Stride8_Chunk32)
800{
801 random_chunk_mutate_helper(64, 100, 8, 32, 2772);
802}
803TEST(array_store, TestChunk_Rand31_Stride11_Chunk21)
804{
805 random_chunk_mutate_helper(31, 100, 11, 21, 7117);
806}
807
808/* -------------------------------------------------------------------- */
811
812static bool rle_encode_decode_test(const uint8_t *data_dec,
813 size_t data_dec_len,
814 size_t *r_data_enc_len)
815{
816 size_t data_enc_len;
817 uint8_t *data_enc;
818
819#ifdef DEBUG_TIME
821#endif
822 data_enc = BLI_array_store_rle_encode(data_dec, data_dec_len, 0, &data_enc_len);
823#ifdef DEBUG_TIME
825#endif
826
827 uint8_t *data_dec_copy = MEM_new_array_uninitialized<uint8_t>(data_dec_len, __func__);
828
829#ifdef DEBUG_TIME
831#endif
832 BLI_array_store_rle_decode(data_enc, data_enc_len, data_dec_copy, data_dec_len);
833#ifdef DEBUG_TIME
835#endif
836
837 MEM_delete(data_enc);
838 const bool eq = memcmp(data_dec, data_dec_copy, data_dec_len) == 0;
839 MEM_delete(data_dec_copy);
840 if (r_data_enc_len) {
841 *r_data_enc_len = data_enc_len;
842 }
843 return eq;
844}
845
849static void array_store_test_random_span_rle_encode(const size_t data_size,
850 const size_t span_size,
851 const int permitations)
852{
853 BLI_assert(data_size > span_size);
854
855 RNG *rng = BLI_rng_new(1);
856 uint8_t *data = MEM_new_array_uninitialized<uint8_t>(data_size, __func__);
857 uint8_t *data_pattern = MEM_new_array_uninitialized<uint8_t>(data_size, __func__);
858
859 for (int i = 0; i < data_size; i++) {
860 data_pattern[i] = i % 2;
861 }
862
863 /* Get the size without any RLE. */
864 const size_t data_enc_no_rle_len = [&data_pattern, &data_size]() -> size_t {
865 size_t data_enc_len;
866 rle_encode_decode_test(data_pattern, data_size, &data_enc_len);
867 return data_enc_len;
868 }();
869
870 for (int mutaiton = 0; mutaiton < permitations; mutaiton++) {
871 memcpy(data, data_pattern, data_size);
872
873 /* The first two mutations are always end-points. */
874 int index;
875 if (mutaiton == 0) {
876 index = 0;
877 }
878 else if (mutaiton == 1) {
879 index = int(data_size) - span_size;
880 }
881 else {
882 /* Place the span in a random location. */
883 index = BLI_rng_get_int(rng) % (data_size - span_size);
884 }
885
886 memset(data + index, 0, span_size);
887
888 size_t data_enc_len;
889 rle_encode_decode_test(data, data_size, &data_enc_len);
890
891 /* Ensure the RLE encoded version has at-least the memory reduction of the span. */
892 const size_t data_enc_len_expected_max = (data_enc_no_rle_len - span_size) +
893 (sizeof(size_t[2]) * 2);
894 EXPECT_LE(data_enc_len, data_enc_len_expected_max);
895 }
896 MEM_delete(data);
897 MEM_delete(data_pattern);
898
899 BLI_rng_free(rng);
900}
901
902static void array_store_test_random_data_rle_encode(const size_t data_size,
903 const size_t data_ratio_size,
904 const int permitations)
905{
906 RNG *rng = BLI_rng_new(1);
907 uint8_t *data = MEM_new_array_uninitialized<uint8_t>(data_size, __func__);
908
909 for (int mutaiton = 0; mutaiton < permitations; mutaiton++) {
910 memset(data, 1, data_ratio_size);
911 memset(data + data_ratio_size, 0, data_size - data_ratio_size);
912
913 BLI_rng_shuffle_array(rng, data, 1, data_size);
914
915 size_t data_enc_len;
916 EXPECT_TRUE(rle_encode_decode_test(data, data_size, &data_enc_len));
917 }
918
919 MEM_delete(data);
920 BLI_rng_free(rng);
921}
922
924
925/* -------------------------------------------------------------------- */
928
929TEST(array_store, RLE_Simple)
930{
931 {
932 const uint8_t data[] = {0};
934 }
935 {
936 const uint8_t data[] = {0};
937 EXPECT_TRUE(rle_encode_decode_test(data, sizeof(data), nullptr));
938 }
939 {
940 const uint8_t data[] = {1};
941 EXPECT_TRUE(rle_encode_decode_test(data, sizeof(data), nullptr));
942 }
943}
944
945TEST(array_store, RLE_Uniform)
946{
947 const uint8_t data_uniform[64] = {0};
948 uint8_t data_pattern[64] = {0};
949 for (int i = 0; i < sizeof(data_pattern); i += 2) {
950 data_pattern[i] = 1;
951 }
952
953 size_t data_uniform_enc_len = 0;
954 size_t data_pattern_enc_len = 0;
955
956 EXPECT_TRUE(rle_encode_decode_test(data_uniform, sizeof(data_uniform), &data_uniform_enc_len));
957 EXPECT_TRUE(rle_encode_decode_test(data_pattern, sizeof(data_pattern), &data_pattern_enc_len));
958
959 /* This depends on implementation details of header sizes.
960 * Since there is no intention to change these, allow this.
961 * They can always be updated as needed. */
962 EXPECT_EQ(data_uniform_enc_len, sizeof(size_t) + sizeof(uint8_t) + sizeof(size_t[2]));
963 EXPECT_EQ(data_pattern_enc_len, sizeof(data_uniform) + sizeof(size_t[4]));
964}
965
966TEST(array_store, RLE_Alignment)
967{
968 /* Use a size large enough to detect usable spans
969 * but not so large as to make the tests slow. */
970 const size_t data_len_max = sizeof(void *) * 8;
971 uint8_t *data_pattern = MEM_new_array_zeroed<uint8_t>(data_len_max, __func__);
972 for (size_t i = 0; i < data_len_max; i += 2) {
973 data_pattern[i] = 1;
974 }
975
976 /* Use allocations memory checking tools will report errors on invalid buffer read/writes.
977 * It's important to offset the start of the array so as to ensure searching the array
978 * is performed at different memory alignments.
979 * It's also important to use `malloc` not `MEM_new_uninitialized` since these hide out of bounds
980 * reads. */
981 for (int data_len = 1; data_len < data_len_max; data_len += 1) {
982 uint8_t *data = static_cast<uint8_t *>(malloc(data_len));
983 for (size_t offset = 0; offset < sizeof(void *); offset += 1) {
984 uint8_t *data_offset = data + offset;
985 if (data_len <= offset) {
986 continue;
987 }
988 const size_t data_offset_len = data_len - offset;
989 memset(data, 0, data_offset_len);
990
991 /* Uniform data. */
992 EXPECT_TRUE(rle_encode_decode_test(data_offset, data_offset_len, nullptr));
993
994 /* Non-uniform data. */
995 memcpy(data_offset, data_pattern, data_offset_len);
996 EXPECT_TRUE(rle_encode_decode_test(data_offset, data_offset_len, nullptr));
997 }
998 free(data);
999 }
1000 MEM_delete(data_pattern);
1001}
1002
1003TEST(array_store, RLE_RandomSpan)
1004{
1005 /* Enable if there is suspicion of rare edge cases causing problems. */
1006 const bool do_stress_test = false;
1007
1008 const int permutations = do_stress_test ? 256 : 8;
1009
1010 array_store_test_random_span_rle_encode(63, 31, permutations);
1011 array_store_test_random_span_rle_encode(63, 32, permutations);
1012 array_store_test_random_span_rle_encode(63, 33, permutations);
1013
1014 array_store_test_random_span_rle_encode(64, 31, permutations);
1015 array_store_test_random_span_rle_encode(64, 32, permutations);
1016 array_store_test_random_span_rle_encode(64, 33, permutations);
1017
1018 array_store_test_random_span_rle_encode(65, 31, permutations);
1019 array_store_test_random_span_rle_encode(65, 32, permutations);
1020 array_store_test_random_span_rle_encode(65, 33, permutations);
1021
1022 if (do_stress_test) {
1023 const int data_size_max = 256;
1024 const int margin = sizeof(size_t[2]);
1025 for (int data_size = margin; data_size < data_size_max; data_size++) {
1026 for (int span_size = 1; span_size < data_size - margin; span_size++) {
1027 array_store_test_random_span_rle_encode(data_size, span_size, permutations);
1028 }
1029 }
1030 }
1031}
1032
1033TEST(array_store, RLE_RandomBytes)
1034{
1035 /* Enable if there is suspicion of rare edge cases causing problems. */
1036 const bool do_stress_test = false;
1037
1038 const int permutations = do_stress_test ? 256 : 8;
1039
1040 array_store_test_random_data_rle_encode(128, 16, permutations);
1041 array_store_test_random_data_rle_encode(128, 32, permutations);
1042 array_store_test_random_data_rle_encode(128, 64, permutations);
1043 array_store_test_random_data_rle_encode(128, 128, permutations);
1044
1045 array_store_test_random_data_rle_encode(131, 16, permutations);
1046 array_store_test_random_data_rle_encode(131, 32, permutations);
1047 array_store_test_random_data_rle_encode(131, 64, permutations);
1048 array_store_test_random_data_rle_encode(131, 128, permutations);
1049
1050 if (do_stress_test) {
1051 const int data_size_max = 256;
1052 const int margin = sizeof(size_t[2]);
1053 for (int data_size = margin; data_size < data_size_max; data_size++) {
1054 for (int data_ratio_size = 1; data_ratio_size < data_size - 1; data_ratio_size++) {
1055 array_store_test_random_span_rle_encode(data_size, data_ratio_size, permutations);
1056 }
1057 }
1058 }
1059
1060 if (do_stress_test) {
1061 /* Stress random data, handy for timing (20 million). */
1062 const size_t data_len_large = 32000000;
1063 array_store_test_random_data_rle_encode(data_len_large, data_len_large / 2, 4);
1064 array_store_test_random_data_rle_encode(data_len_large, 0, 4);
1065 }
1066}
1067
1069
1070#if 0
1071
1072/* -------------------------------------------------------------------- */
1077
1078static void *file_read_binary_as_mem(const char *filepath, size_t pad_bytes, size_t *r_size)
1079{
1080 FILE *fp = fopen(filepath, "rb");
1081 void *mem = nullptr;
1082
1083 if (fp) {
1084 long int filelen_read;
1085 fseek(fp, 0L, SEEK_END);
1086 const long int filelen = ftell(fp);
1087 if (filelen == -1) {
1088 goto finally;
1089 }
1090 fseek(fp, 0L, SEEK_SET);
1091
1092 mem = MEM_new_uninitialized(filelen + pad_bytes, __func__);
1093 if (mem == nullptr) {
1094 goto finally;
1095 }
1096
1097 filelen_read = fread(mem, 1, filelen, fp);
1098 if ((filelen_read != filelen) || ferror(fp)) {
1099 MEM_delete_void(mem);
1100 mem = nullptr;
1101 goto finally;
1102 }
1103
1104 *r_size = filelen_read;
1105
1106 finally:
1107 fclose(fp);
1108 }
1109
1110 return mem;
1111}
1112
1113TEST(array_store, PlainTextFiles)
1114{
1115 ListBaseT<TestBuffer> lb;
1116 lb.clear_no_delete();
1117 BArrayStore *bs = BLI_array_store_create(1, 128);
1118
1119 for (int i = 0; i < 629; i++) {
1120 char str[512];
1121 BLI_snprintf(str, sizeof(str), "/src/py_array_cow/test_data/xz_data/%04d.c.xz", i);
1122 // BLI_snprintf(str, sizeof(str), "/src/py_array_cow/test_data/c_code/%04d.c", i);
1123 // printf("%s\n", str);
1124 size_t data_len;
1125 void *data;
1126 data = file_read_binary_as_mem(str, 0, &data_len);
1127
1128 testbuffer_list_add(&lb, (const void *)data, data_len);
1129 }
1130
1131 /* forwards */
1135# ifdef DEBUG_PRINT
1136 print_mem_saved("source code forward", bs);
1137# endif
1138
1141
1142 /* backwards */
1146# ifdef DEBUG_PRINT
1147 print_mem_saved("source code backwards", bs);
1148# endif
1149
1152}
1153
1155
1156#endif
1157
1158} // namespace blender
Efficient in-memory storage of multiple similar arrays.
#define TESTBUFFER_STRINGS(stride, chunk_count,...)
#define TESTBUFFER_STRINGS_CREATE(lb,...)
#define WORDS
Generic array manipulation API.
Random number functions.
Platform independent time functions.
Utility defines for timing/benchmarks.
#define TIMEIT_START(var)
#define TIMEIT_END(var)
Read Blender memory allocation and freeing.
#define BLI_assert_unreachable()
#define ELEM(...)
#define MEM_realloc_uninitialized(vmemh, len)
#define str(s)
VecBase< float, D > step(VecOp< float, D >, VecOp< float, D >) RET
#define EXPECT_TRUE(result)
#define EXPECT_LE(result, expect)
const int state
void * MEM_new_uninitialized(size_t len, const char *str)
Definition mallocn.cc:124
#define L
void free(Subdiv *subdiv)
Definition subdiv.cc:192
BLI_INLINE ColorSceneLinear4f< Alpha > decode(const ColorSceneLinearByteEncoded4b< Alpha > &color)
Definition BLI_color.hh:77
BLI_INLINE ColorSceneLinearByteEncoded4b< Alpha > encode(const ColorSceneLinear4f< Alpha > &color)
Definition BLI_color.hh:50
BMesh Iterators.
void * MEM_new_uninitialized(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
size_t BLI_snprintf(char *__restrict dst, size_t dst_maxncpy, const char *__restrict format,...) ATTR_NONNULL(1
void BLI_array_store_state_remove(BArrayStore *bs, BArrayState *state)
BLI_INLINE float D(const float *data, const int res[3], int x, int y, int z)
Definition voxel.cc:16
unsigned int uint
Definition BKE_text.h:55
static TestChunk * testchunk_list_add(ListBaseT< TestChunk > *lb, const void *data, size_t data_len)
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
static void testbuffer_list_data_randomize(ListBaseT< TestBuffer > *lb, uint random_seed)
BArrayState * BLI_array_store_state_add(BArrayStore *bs, const void *data, size_t data_len, const BArrayState *state_reference)
static void testbuffer_run_tests_single(BArrayStore *bs, ListBaseT< TestBuffer > *lb)
void _bli_array_wrap(void *arr_v, uint arr_len, size_t arr_stride, int dir)
static TestBuffer * testbuffer_list_add_copydata(ListBaseT< TestBuffer > *lb, const void *data, size_t data_len)
void MEM_delete_void(void *vmemh)
struct RNG * BLI_rng_new(unsigned int seed)
Definition rand.cc:41
void * BLI_array_store_state_data_get_alloc(const BArrayState *state, size_t *r_data_len)
static void random_chunk_mutate_helper(const int chunks_per_buffer, const int items_total, const int stride, const int chunk_count, const int random_seed)
void BLI_array_randomize(void *data, unsigned int elem_size, unsigned int elem_num, unsigned int seed)
Definition rand.cc:158
TEST(array_store, Nop)
uint8_t * BLI_array_store_rle_encode(const uint8_t *data_dec, size_t data_dec_len, size_t data_enc_extra_size, size_t *r_data_enc_len)
static uint rand_range_i(RNG *rng, uint min_i, uint max_i, uint step)
bool BLI_array_store_is_valid(BArrayStore *bs)
static void array_store_test_random_data_rle_encode(const size_t data_size, const size_t data_ratio_size, const int permitations)
static void random_data_mutate_helper(const int items_size_min, const int items_size_max, const int items_total, const int stride, const int chunk_count, const int random_seed, const int mutate)
static TestBuffer * testbuffer_list_add(ListBaseT< TestBuffer > *lb, const void *data, size_t data_len)
static bool rle_encode_decode_test(const uint8_t *data_dec, size_t data_dec_len, size_t *r_data_enc_len)
void BLI_rng_get_char_n(RNG *rng, char *bytes, size_t bytes_len) ATTR_NONNULL(1
Definition rand.cc:70
unsigned char uchar
Definition BKE_text.h:58
BArrayStore * BLI_array_store_create(unsigned int stride, unsigned int chunk_count)
BMesh const char void * data
unsigned int BLI_rng_get_uint(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition rand.cc:80
unsigned char uint8_t
Definition BKE_text.h:79
static void plain_text_helper(const char *words, int words_len, const char word_delim, const int stride, const int chunk_count, const int random_seed)
static bool testbuffer_list_validate(const ListBaseT< TestBuffer > *lb)
static void array_store_test_random_span_rle_encode(const size_t data_size, const size_t span_size, const int permitations)
void BLI_rng_free(struct RNG *rng) ATTR_NONNULL(1)
Definition rand.cc:55
static void testbuffer_list_state_random_data(ListBaseT< TestBuffer > *lb, const size_t stride, const size_t data_min_len, const size_t data_max_len, const uint mutate, RNG *rng)
void void void void void void void BLI_listbase_reverse(ListBase *lb) ATTR_NONNULL(1)
Definition listbase.cc:850
size_t BLI_array_store_calc_size_expanded_get(const BArrayStore *bs)
void BLI_rng_shuffle_array(struct RNG *rng, void *data, unsigned int elem_size_i, unsigned int elem_num) ATTR_NONNULL(1
Definition rand.cc:101
static bool testbuffer_item_validate(TestBuffer *tb)
static void testbuffer_list_store_clear(BArrayStore *bs, ListBaseT< TestBuffer > *lb)
static void testbuffer_list_free(ListBaseT< TestBuffer > *lb)
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
void int BLI_rng_get_int(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition rand.cc:75
size_t BLI_array_store_state_size_get(const BArrayState *state)
static void testbuffer_list_store_populate(BArrayStore *bs, ListBaseT< TestBuffer > *lb)
size_t BLI_array_store_calc_size_compacted_get(const BArrayStore *bs)
void BLI_addtail(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:118
static void testbuffer_run_tests_simple(ListBaseT< TestBuffer > *lb, const int stride, const int chunk_count)
static void random_chunk_generate(ListBaseT< TestChunk > *lb, const int chunks_per_buffer, const int stride, const int chunk_count, const int random_seed)
static void testbuffer_list_state_from_data(ListBaseT< TestBuffer > *lb, const char *data, const size_t data_len)
static char * testchunk_as_data_array(TestChunk **tc_array, int tc_array_len, size_t *r_data_len)
static void testchunk_list_free(ListBaseT< TestChunk > *lb)
void BLI_array_store_destroy(BArrayStore *bs)
void BLI_array_store_rle_decode(const uint8_t *data_enc, const size_t data_enc_len, void *data_dec_v, const size_t data_dec_len)
static void testbuffer_run_tests(BArrayStore *bs, ListBaseT< TestBuffer > *lb)
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
static void testbuffer_list_state_from_data__stride_expand(ListBaseT< TestBuffer > *lb, const char *data, const size_t data_len, const size_t stride)