5#include "testing/testing.h"
34static void print_mem_saved(
const char *
id,
const BArrayStore *bs)
38 const double percent = size_expand ? ((size_real / size_expand) * 100.0) : -1.0;
39 printf(
"%s: %.8f%%\n",
id, percent);
63static TestChunk *testchunk_list_add_copydata(ListBaseT<TestChunk> *lb,
const void *
data,
size_t data_len)
66 memcpy(data_copy,
data, data_len);
73 for (
TestChunk *tc = lb->first(), *tb_next; tc; tc = tb_next) {
78 lb->clear_no_delete();
82static char *testchunk_as_data(ListBaseT<TestChunk> *lb,
size_t *r_data_len)
85 for (TestChunk *tc = (TestChunk *)lb->first; tc; tc = tc->next) {
86 data_len += tc->data_len;
91 memcpy(&
data[i], tc->data, tc->data_len);
92 data_len += tc->data_len;
105 for (
int tc_index = 0; tc_index < tc_array_len; tc_index++) {
106 data_len += tc_array[tc_index]->
data_len;
110 for (
int tc_index = 0; tc_index < tc_array_len; tc_index++) {
151 memcpy(data_copy,
data, data_len);
157 const size_t data_len)
168 const size_t data_len,
175 const size_t data_stride_len = data_len * stride;
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);
186#define testbuffer_list_state_from_string_array(lb, data_array) \
190 while ((data = data_array[i_++])) { \
191 testbuffer_list_state_from_data(lb, data, strlen(data)); \
198#define TESTBUFFER_STRINGS_CREATE(lb, ...) \
200 BLI_listbase_clear(lb); \
201 const char *data_array[] = {__VA_ARGS__ nullptr}; \
202 testbuffer_list_state_from_string_array((lb), data_array); \
207#define TESTBUFFER_STRINGS(stride, chunk_count, ...) \
209 ListBaseT<TestBuffer> lb; \
210 TESTBUFFER_STRINGS_CREATE(&lb, __VA_ARGS__); \
212 testbuffer_run_tests_simple(&lb, stride, chunk_count); \
214 testbuffer_list_free(&lb); \
220 size_t data_state_len;
223 if (tb->
data_len != data_state_len) {
226 else if (memcmp(data_state, tb->
data, data_state_len) != 0) {
253 for (
TestBuffer *tb = lb->first(), *tb_prev =
nullptr; tb; tb_prev = tb, tb = tb->
next) {
255 bs, tb->data, tb->data_len, (tb_prev ? tb_prev->state :
nullptr));
269 for (
TestBuffer *tb = lb->first(), *tb_next; tb; tb = tb_next) {
274 lb->clear_no_delete();
283 print_mem_saved(
"data", bs);
303 const int chunk_count)
332 const char data_src[] =
"test";
333 const char *data_dst;
337 EXPECT_STREQ(data_src, data_dst);
338 EXPECT_EQ(data_dst_len,
sizeof(data_src));
340 MEM_delete(data_dst);
346 const char data_src[] =
"test";
347 const char *data_dst;
358 EXPECT_STREQ(data_src, data_dst);
359 MEM_delete(data_dst);
362 EXPECT_STREQ(data_src, data_dst);
363 MEM_delete(data_dst);
365 EXPECT_EQ(data_dst_len,
sizeof(data_src));
372 const char data_src_a[] =
"test";
373 const char data_src_b[] =
"####";
374 const char *data_dst;
384 EXPECT_STREQ(data_src_a, data_dst);
385 MEM_delete(data_dst);
388 EXPECT_STREQ(data_src_b, data_dst);
389 MEM_delete(data_dst);
404TEST(array_store, TextDupeIncreaseDecrease)
406 ListBaseT<TestBuffer> lb;
444 const char word_delim,
446 const int chunk_count,
447 const int random_seed)
450 ListBaseT<TestBuffer> lb;
451 lb.clear_no_delete();
453 for (
int i = 0, i_prev = 0; i < words_len; i++) {
454 if (
ELEM(words[i], word_delim,
'\0')) {
472#define WORDS words10k, sizeof(words10k)
473TEST(array_store, TextSentences_Chunk1)
477TEST(array_store, TextSentences_Chunk2)
481TEST(array_store, TextSentences_Chunk8)
485TEST(array_store, TextSentences_Chunk32)
489TEST(array_store, TextSentences_Chunk128)
493TEST(array_store, TextSentences_Chunk1024)
498TEST(array_store, TextSentences_Chunk3)
502TEST(array_store, TextSentences_Chunk13)
506TEST(array_store, TextSentences_Chunk131)
512TEST(array_store, TextWords_Chunk1)
516TEST(array_store, TextWords_Chunk2)
520TEST(array_store, TextWords_Chunk8)
524TEST(array_store, TextWords_Chunk32)
528TEST(array_store, TextWords_Chunk128)
532TEST(array_store, TextWords_Chunk1024)
537TEST(array_store, TextWords_Chunk3)
541TEST(array_store, TextWords_Chunk13)
545TEST(array_store, TextWords_Chunk131)
551TEST(array_store, TextSentencesRandom_Stride3_Chunk3)
555TEST(array_store, TextSentencesRandom_Stride8_Chunk8)
559TEST(array_store, TextSentencesRandom_Stride32_Chunk1)
563TEST(array_store, TextSentencesRandom_Stride12_Chunk512)
567TEST(array_store, TextSentencesRandom_Stride128_Chunk6)
579 if (min_i == max_i) {
584 uint range = (max_i - min_i);
587 return min_i + value;
592 const size_t data_min_len,
593 const size_t data_max_len,
598 size_t data_len =
rand_range_i(rng, data_min_len, data_max_len + stride, stride);
601 if (lb->last_ ==
nullptr) {
606 if (tb_last->
data_len >= data_len) {
607 memcpy(
data, tb_last->
data, data_len);
615 for (
int i = 0; i < mutate; i++) {
631 if (data_len < data_max_len) {
634 memmove(&
data[offset + stride], &
data[offset], data_len - (offset + stride));
639 case MUTATE_REMOVE: {
641 if (data_len > data_min_len) {
642 memmove(&
data[offset], &
data[offset + stride], data_len - (offset + stride));
647 case MUTATE_ROTATE: {
648 int items = data_len / stride;
654 case MUTATE_RANDOMIZE: {
671 const int items_size_max,
672 const int items_total,
674 const int chunk_count,
675 const int random_seed,
679 ListBaseT<TestBuffer> lb;
680 lb.clear_no_delete();
682 const size_t data_min_len = items_size_min * stride;
683 const size_t data_max_len = items_size_max * stride;
687 for (
int i = 0; i < items_total; i++) {
698TEST(array_store, TestData_Stride1_Chunk32_Mutate2)
702TEST(array_store, TestData_Stride8_Chunk512_Mutate2)
706TEST(array_store, TestData_Stride12_Chunk48_Mutate2)
710TEST(array_store, TestData_Stride32_Chunk64_Mutate1)
714TEST(array_store, TestData_Stride32_Chunk64_Mutate8)
723 const int chunks_per_buffer,
725 const int chunk_count,
726 const int random_seed)
729 const size_t chunk_size_bytes = stride * chunk_count;
730 for (
int i = 0; i < chunks_per_buffer; i++) {
742 const int items_total,
744 const int chunk_count,
745 const int random_seed)
749 ListBaseT<TestChunk> random_chunks;
750 random_chunks.clear_no_delete();
756 for (
int i = 0; i < chunks_per_buffer; i++, tc = tc->
next) {
757 chunks_array[i] = tc;
762 ListBaseT<TestBuffer> lb;
763 lb.clear_no_delete();
767 for (
int i = 0; i < items_total; i++) {
771 BLI_assert(data_len == chunks_per_buffer * chunk_count * stride);
778 MEM_delete(chunks_array);
783 size_t expected_size = chunks_per_buffer * chunk_count * stride;
791TEST(array_store, TestChunk_Rand8_Stride1_Chunk64)
795TEST(array_store, TestChunk_Rand32_Stride1_Chunk64)
799TEST(array_store, TestChunk_Rand64_Stride8_Chunk32)
803TEST(array_store, TestChunk_Rand31_Stride11_Chunk21)
814 size_t *r_data_enc_len)
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;
850 const size_t span_size,
851 const int permitations)
859 for (
int i = 0; i < data_size; i++) {
860 data_pattern[i] = i % 2;
864 const size_t data_enc_no_rle_len = [&data_pattern, &data_size]() ->
size_t {
870 for (
int mutaiton = 0; mutaiton < permitations; mutaiton++) {
871 memcpy(
data, data_pattern, data_size);
878 else if (mutaiton == 1) {
879 index = int(data_size) - span_size;
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);
897 MEM_delete(data_pattern);
903 const size_t data_ratio_size,
904 const int permitations)
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);
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) {
953 size_t data_uniform_enc_len = 0;
954 size_t data_pattern_enc_len = 0;
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]));
966TEST(array_store, RLE_Alignment)
970 const size_t data_len_max =
sizeof(
void *) * 8;
972 for (
size_t i = 0; i < data_len_max; i += 2) {
981 for (
int data_len = 1; data_len < data_len_max; data_len += 1) {
983 for (
size_t offset = 0; offset <
sizeof(
void *); offset += 1) {
985 if (data_len <= offset) {
988 const size_t data_offset_len = data_len - offset;
989 memset(
data, 0, data_offset_len);
995 memcpy(data_offset, data_pattern, data_offset_len);
1000 MEM_delete(data_pattern);
1006 const bool do_stress_test =
false;
1008 const int permutations = do_stress_test ? 256 : 8;
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++) {
1036 const bool do_stress_test =
false;
1038 const int permutations = do_stress_test ? 256 : 8;
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++) {
1060 if (do_stress_test) {
1062 const size_t data_len_large = 32000000;
1078static void *file_read_binary_as_mem(
const char *filepath,
size_t pad_bytes,
size_t *r_size)
1080 FILE *fp = fopen(filepath,
"rb");
1081 void *mem =
nullptr;
1084 long int filelen_read;
1085 fseek(fp, 0
L, SEEK_END);
1086 const long int filelen = ftell(fp);
1087 if (filelen == -1) {
1090 fseek(fp, 0
L, SEEK_SET);
1093 if (mem ==
nullptr) {
1097 filelen_read = fread(mem, 1, filelen, fp);
1098 if ((filelen_read != filelen) || ferror(fp)) {
1104 *r_size = filelen_read;
1113TEST(array_store, PlainTextFiles)
1115 ListBaseT<TestBuffer> lb;
1116 lb.clear_no_delete();
1119 for (
int i = 0; i < 629; i++) {
1126 data = file_read_binary_as_mem(
str, 0, &data_len);
1136 print_mem_saved(
"source code forward", bs);
1147 print_mem_saved(
"source code backwards", bs);
Efficient in-memory storage of multiple similar arrays.
#define TESTBUFFER_STRINGS(stride, chunk_count,...)
#define TESTBUFFER_STRINGS_CREATE(lb,...)
Generic array manipulation API.
Platform independent time functions.
Utility defines for timing/benchmarks.
#define TIMEIT_START(var)
Read Blender memory allocation and freeing.
#define BLI_assert_unreachable()
#define MEM_realloc_uninitialized(vmemh, len)
VecBase< float, D > step(VecOp< float, D >, VecOp< float, D >) RET
#define EXPECT_TRUE(result)
#define EXPECT_LE(result, expect)
void * MEM_new_uninitialized(size_t len, const char *str)
void free(Subdiv *subdiv)
BLI_INLINE ColorSceneLinear4f< Alpha > decode(const ColorSceneLinearByteEncoded4b< Alpha > &color)
BLI_INLINE ColorSceneLinearByteEncoded4b< Alpha > encode(const ColorSceneLinear4f< Alpha > &color)
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)
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)
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)
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
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)
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)
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)
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
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)
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)
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)