Blender  V3.3
BLI_array_store_test.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0 */
2 
3 #include "testing/testing.h"
4 
5 #include "MEM_guardedalloc.h"
6 
7 #include "BLI_array_store.h"
8 #include "BLI_array_utils.h"
9 #include "BLI_listbase.h"
10 #include "BLI_rand.h"
11 #include "BLI_ressource_strings.h"
12 #include "BLI_string.h"
13 #include "BLI_sys_types.h"
14 #include "BLI_utildefines.h"
15 
16 /* print memory savings */
17 // #define DEBUG_PRINT
18 
19 /* -------------------------------------------------------------------- */
20 /* Helper functions */
21 
22 #ifdef DEBUG_PRINT
23 static void print_mem_saved(const char *id, const BArrayStore *bs)
24 {
25  const double size_real = BLI_array_store_calc_size_compacted_get(bs);
26  const double size_expand = BLI_array_store_calc_size_expanded_get(bs);
27  const double percent = size_expand ? ((size_real / size_expand) * 100.0) : -1.0;
28  printf("%s: %.8f%%\n", id, percent);
29 }
30 #endif
31 
32 /* -------------------------------------------------------------------- */
33 /* Test Chunks (building data from list of chunks) */
34 
35 struct TestChunk {
36  struct TestChunk *next, *prev;
37  const void *data;
38  size_t data_len;
39 };
40 
41 static TestChunk *testchunk_list_add(ListBase *lb, const void *data, size_t data_len)
42 {
43  TestChunk *tc = (TestChunk *)MEM_mallocN(sizeof(*tc), __func__);
44  tc->data = data;
45  tc->data_len = data_len;
46  BLI_addtail(lb, tc);
47 
48  return tc;
49 }
50 
51 #if 0
52 static TestChunk *testchunk_list_add_copydata(ListBase *lb, const void *data, size_t data_len)
53 {
54  void *data_copy = MEM_mallocN(data_len, __func__);
55  memcpy(data_copy, data, data_len);
56  return testchunk_list_add(lb, data_copy, data_len);
57 }
58 #endif
59 
60 static void testchunk_list_free(ListBase *lb)
61 {
62  for (TestChunk *tc = (TestChunk *)lb->first, *tb_next; tc; tc = tb_next) {
63  tb_next = tc->next;
64  MEM_freeN((void *)tc->data);
65  MEM_freeN(tc);
66  }
68 }
69 
70 #if 0
71 static char *testchunk_as_data(ListBase *lb, size_t *r_data_len)
72 {
73  size_t data_len = 0;
74  for (TestChunk *tc = (TestChunk *)lb->first; tc; tc = tc->next) {
75  data_len += tc->data_len;
76  }
77  char *data = (char *)MEM_mallocN(data_len, __func__);
78  size_t i = 0;
79  for (TestChunk *tc = (TestChunk *)lb->first; tc; tc = tc->next) {
80  memcpy(&data[i], tc->data, tc->data_len);
81  data_len += tc->data_len;
82  i += tc->data_len;
83  }
84  if (r_data_len) {
85  *r_data_len = i;
86  }
87  return data;
88 }
89 #endif
90 
91 static char *testchunk_as_data_array(TestChunk **tc_array, int tc_array_len, size_t *r_data_len)
92 {
93  size_t data_len = 0;
94  for (int tc_index = 0; tc_index < tc_array_len; tc_index++) {
95  data_len += tc_array[tc_index]->data_len;
96  }
97  char *data = (char *)MEM_mallocN(data_len, __func__);
98  size_t i = 0;
99  for (int tc_index = 0; tc_index < tc_array_len; tc_index++) {
100  TestChunk *tc = tc_array[tc_index];
101  memcpy(&data[i], tc->data, tc->data_len);
102  i += tc->data_len;
103  }
104  if (r_data_len) {
105  *r_data_len = i;
106  }
107  return data;
108 }
109 
110 /* -------------------------------------------------------------------- */
111 /* Test Buffer */
112 
113 /* API to handle local allocation of data so we can compare it with the data in the array_store */
114 struct TestBuffer {
115  struct TestBuffer *next, *prev;
116  const void *data;
117  size_t data_len;
118 
119  /* for reference */
121 };
122 
123 static TestBuffer *testbuffer_list_add(ListBase *lb, const void *data, size_t data_len)
124 {
125  TestBuffer *tb = (TestBuffer *)MEM_mallocN(sizeof(*tb), __func__);
126  tb->data = data;
127  tb->data_len = data_len;
128  tb->state = nullptr;
129  BLI_addtail(lb, tb);
130  return tb;
131 }
132 
134 {
135  void *data_copy = MEM_mallocN(data_len, __func__);
136  memcpy(data_copy, data, data_len);
137  return testbuffer_list_add(lb, data_copy, data_len);
138 }
139 
140 static void testbuffer_list_state_from_data(ListBase *lb, const char *data, const size_t data_len)
141 {
142  testbuffer_list_add_copydata(lb, (const void *)data, data_len);
143 }
144 
150  const char *data,
151  const size_t data_len,
152  const size_t stride)
153 {
154  if (stride == 1) {
156  }
157  else {
158  const size_t data_stride_len = data_len * stride;
159  char *data_stride = (char *)MEM_mallocN(data_stride_len, __func__);
160 
161  for (size_t i = 0, i_stride = 0; i < data_len; i += 1, i_stride += stride) {
162  memset(&data_stride[i_stride], data[i], stride);
163  }
164 
165  testbuffer_list_add(lb, (const void *)data_stride, data_stride_len);
166  }
167 }
168 
169 #define testbuffer_list_state_from_string_array(lb, data_array) \
170  { \
171  unsigned int i_ = 0; \
172  const char *data; \
173  while ((data = data_array[i_++])) { \
174  testbuffer_list_state_from_data(lb, data, strlen(data)); \
175  } \
176  } \
177  ((void)0)
178 
179 //
180 
181 #define TESTBUFFER_STRINGS_CREATE(lb, ...) \
182  { \
183  BLI_listbase_clear(lb); \
184  const char *data_array[] = {__VA_ARGS__ NULL}; \
185  testbuffer_list_state_from_string_array((lb), data_array); \
186  } \
187  ((void)0)
188 
189 /* test in both directions */
190 #define TESTBUFFER_STRINGS(stride, chunk_count, ...) \
191  { \
192  ListBase lb; \
193  TESTBUFFER_STRINGS_CREATE(&lb, __VA_ARGS__); \
194 \
195  testbuffer_run_tests_simple(&lb, stride, chunk_count); \
196 \
197  testbuffer_list_free(&lb); \
198  } \
199  ((void)0)
200 
202 {
203  size_t data_state_len;
204  bool ok = true;
205  void *data_state = BLI_array_store_state_data_get_alloc(tb->state, &data_state_len);
206  if (tb->data_len != data_state_len) {
207  ok = false;
208  }
209  else if (memcmp(data_state, tb->data, data_state_len) != 0) {
210  ok = false;
211  }
212  MEM_freeN(data_state);
213  return ok;
214 }
215 
216 static bool testbuffer_list_validate(const ListBase *lb)
217 {
218  for (TestBuffer *tb = (TestBuffer *)lb->first; tb; tb = tb->next) {
219  if (!testbuffer_item_validate(tb)) {
220  return false;
221  }
222  }
223 
224  return true;
225 }
226 
227 static void testbuffer_list_data_randomize(ListBase *lb, unsigned int random_seed)
228 {
229  for (TestBuffer *tb = (TestBuffer *)lb->first; tb; tb = tb->next) {
230  BLI_array_randomize((void *)tb->data, 1, tb->data_len, random_seed++);
231  }
232 }
233 
235 {
236  for (TestBuffer *tb = (TestBuffer *)lb->first, *tb_prev = nullptr; tb;
237  tb_prev = tb, tb = tb->next) {
238  tb->state = BLI_array_store_state_add(
239  bs, tb->data, tb->data_len, (tb_prev ? tb_prev->state : nullptr));
240  }
241 }
242 
244 {
245  for (TestBuffer *tb = (TestBuffer *)lb->first; tb; tb = tb->next) {
246  BLI_array_store_state_remove(bs, tb->state);
247  tb->state = nullptr;
248  }
249 }
250 
252 {
253  for (TestBuffer *tb = (TestBuffer *)lb->first, *tb_next; tb; tb = tb_next) {
254  tb_next = tb->next;
255  MEM_freeN((void *)tb->data);
256  MEM_freeN(tb);
257  }
258  BLI_listbase_clear(lb);
259 }
260 
262 {
264  EXPECT_TRUE(testbuffer_list_validate(lb));
265  EXPECT_TRUE(BLI_array_store_is_valid(bs));
266 #ifdef DEBUG_PRINT
267  print_mem_saved("data", bs);
268 #endif
269 }
270 
271 /* avoid copy-paste code to run tests */
273 {
274  /* forwards */
277 
279 
280  /* backwards */
283 }
284 
285 static void testbuffer_run_tests_simple(ListBase *lb, const int stride, const int chunk_count)
286 {
287  BArrayStore *bs = BLI_array_store_create(stride, chunk_count);
288  testbuffer_run_tests(bs, lb);
290 }
291 
292 /* -------------------------------------------------------------------- */
293 /* Basic Tests */
294 
295 TEST(array_store, Nop)
296 {
297  BArrayStore *bs = BLI_array_store_create(1, 32);
299 }
300 
301 TEST(array_store, NopState)
302 {
303  BArrayStore *bs = BLI_array_store_create(1, 32);
304  const unsigned char data[] = "test";
305  BArrayState *state = BLI_array_store_state_add(bs, data, sizeof(data) - 1, nullptr);
309 }
310 
311 TEST(array_store, Single)
312 {
313  BArrayStore *bs = BLI_array_store_create(1, 32);
314  const char data_src[] = "test";
315  const char *data_dst;
316  BArrayState *state = BLI_array_store_state_add(bs, data_src, sizeof(data_src), nullptr);
317  size_t data_dst_len;
318  data_dst = (char *)BLI_array_store_state_data_get_alloc(state, &data_dst_len);
319  EXPECT_STREQ(data_src, data_dst);
320  EXPECT_EQ(data_dst_len, sizeof(data_src));
322  MEM_freeN((void *)data_dst);
323 }
324 
325 TEST(array_store, DoubleNop)
326 {
327  BArrayStore *bs = BLI_array_store_create(1, 32);
328  const char data_src[] = "test";
329  const char *data_dst;
330 
331  BArrayState *state_a = BLI_array_store_state_add(bs, data_src, sizeof(data_src), nullptr);
332  BArrayState *state_b = BLI_array_store_state_add(bs, data_src, sizeof(data_src), state_a);
333 
334  EXPECT_EQ(BLI_array_store_calc_size_compacted_get(bs), sizeof(data_src));
335  EXPECT_EQ(BLI_array_store_calc_size_expanded_get(bs), sizeof(data_src) * 2);
336 
337  size_t data_dst_len;
338 
339  data_dst = (char *)BLI_array_store_state_data_get_alloc(state_a, &data_dst_len);
340  EXPECT_STREQ(data_src, data_dst);
341  MEM_freeN((void *)data_dst);
342 
343  data_dst = (char *)BLI_array_store_state_data_get_alloc(state_b, &data_dst_len);
344  EXPECT_STREQ(data_src, data_dst);
345  MEM_freeN((void *)data_dst);
346 
347  EXPECT_EQ(data_dst_len, sizeof(data_src));
349 }
350 
351 TEST(array_store, DoubleDiff)
352 {
353  BArrayStore *bs = BLI_array_store_create(1, 32);
354  const char data_src_a[] = "test";
355  const char data_src_b[] = "####";
356  const char *data_dst;
357 
358  BArrayState *state_a = BLI_array_store_state_add(bs, data_src_a, sizeof(data_src_a), nullptr);
359  BArrayState *state_b = BLI_array_store_state_add(bs, data_src_b, sizeof(data_src_b), state_a);
360  size_t data_dst_len;
361 
362  EXPECT_EQ(BLI_array_store_calc_size_compacted_get(bs), sizeof(data_src_a) * 2);
363  EXPECT_EQ(BLI_array_store_calc_size_expanded_get(bs), sizeof(data_src_a) * 2);
364 
365  data_dst = (char *)BLI_array_store_state_data_get_alloc(state_a, &data_dst_len);
366  EXPECT_STREQ(data_src_a, data_dst);
367  MEM_freeN((void *)data_dst);
368 
369  data_dst = (char *)BLI_array_store_state_data_get_alloc(state_b, &data_dst_len);
370  EXPECT_STREQ(data_src_b, data_dst);
371  MEM_freeN((void *)data_dst);
372 
374 }
375 
376 TEST(array_store, TextMixed)
377 {
378  TESTBUFFER_STRINGS(1, 4, "", );
379  TESTBUFFER_STRINGS(1, 4, "test", );
380  TESTBUFFER_STRINGS(1, 4, "", "test", );
381  TESTBUFFER_STRINGS(1, 4, "test", "", );
382  TESTBUFFER_STRINGS(1, 4, "test", "", "test", );
383  TESTBUFFER_STRINGS(1, 4, "", "test", "", );
384 }
385 
386 TEST(array_store, TextDupeIncreaseDecrease)
387 {
388  ListBase lb;
389 
390 #define D "#1#2#3#4"
391  TESTBUFFER_STRINGS_CREATE(&lb, D, D D, D D D, D D D D, );
392 
394 
395  /* forward */
397  EXPECT_TRUE(testbuffer_list_validate(&lb));
398  EXPECT_TRUE(BLI_array_store_is_valid(bs));
400 
403 
404  /* backwards */
406  EXPECT_TRUE(testbuffer_list_validate(&lb));
407  EXPECT_TRUE(BLI_array_store_is_valid(bs));
408  /* larger since first block doesn't de-duplicate */
410 
411 #undef D
413 
415 }
416 
417 /* -------------------------------------------------------------------- */
418 /* Plain Text Tests */
419 
424 static void plain_text_helper(const char *words,
425  int words_len,
426  const char word_delim,
427  const int stride,
428  const int chunk_count,
429  const int random_seed)
430 {
431 
432  ListBase lb;
433  BLI_listbase_clear(&lb);
434 
435  for (int i = 0, i_prev = 0; i < words_len; i++) {
436  if (ELEM(words[i], word_delim, '\0')) {
437  if (i != i_prev) {
438  testbuffer_list_state_from_data__stride_expand(&lb, &words[i_prev], i - i_prev, stride);
439  }
440  i_prev = i;
441  }
442  }
443 
444  if (random_seed) {
445  testbuffer_list_data_randomize(&lb, random_seed);
446  }
447 
448  testbuffer_run_tests_simple(&lb, stride, chunk_count);
449 
451 }
452 
453 /* split by '.' (multiple words) */
454 #define WORDS words10k, sizeof(words10k)
455 TEST(array_store, TextSentences_Chunk1)
456 {
457  plain_text_helper(WORDS, '.', 1, 1, 0);
458 }
459 TEST(array_store, TextSentences_Chunk2)
460 {
461  plain_text_helper(WORDS, '.', 1, 2, 0);
462 }
463 TEST(array_store, TextSentences_Chunk8)
464 {
465  plain_text_helper(WORDS, '.', 1, 8, 0);
466 }
467 TEST(array_store, TextSentences_Chunk32)
468 {
469  plain_text_helper(WORDS, '.', 1, 32, 0);
470 }
471 TEST(array_store, TextSentences_Chunk128)
472 {
473  plain_text_helper(WORDS, '.', 1, 128, 0);
474 }
475 TEST(array_store, TextSentences_Chunk1024)
476 {
477  plain_text_helper(WORDS, '.', 1, 1024, 0);
478 }
479 /* odd numbers */
480 TEST(array_store, TextSentences_Chunk3)
481 {
482  plain_text_helper(WORDS, '.', 1, 3, 0);
483 }
484 TEST(array_store, TextSentences_Chunk13)
485 {
486  plain_text_helper(WORDS, '.', 1, 13, 0);
487 }
488 TEST(array_store, TextSentences_Chunk131)
489 {
490  plain_text_helper(WORDS, '.', 1, 131, 0);
491 }
492 
493 /* split by ' ', individual words */
494 TEST(array_store, TextWords_Chunk1)
495 {
496  plain_text_helper(WORDS, ' ', 1, 1, 0);
497 }
498 TEST(array_store, TextWords_Chunk2)
499 {
500  plain_text_helper(WORDS, ' ', 1, 2, 0);
501 }
502 TEST(array_store, TextWords_Chunk8)
503 {
504  plain_text_helper(WORDS, ' ', 1, 8, 0);
505 }
506 TEST(array_store, TextWords_Chunk32)
507 {
508  plain_text_helper(WORDS, ' ', 1, 32, 0);
509 }
510 TEST(array_store, TextWords_Chunk128)
511 {
512  plain_text_helper(WORDS, ' ', 1, 128, 0);
513 }
514 TEST(array_store, TextWords_Chunk1024)
515 {
516  plain_text_helper(WORDS, ' ', 1, 1024, 0);
517 }
518 /* odd numbers */
519 TEST(array_store, TextWords_Chunk3)
520 {
521  plain_text_helper(WORDS, ' ', 1, 3, 0);
522 }
523 TEST(array_store, TextWords_Chunk13)
524 {
525  plain_text_helper(WORDS, ' ', 1, 13, 0);
526 }
527 TEST(array_store, TextWords_Chunk131)
528 {
529  plain_text_helper(WORDS, ' ', 1, 131, 0);
530 }
531 
532 /* various tests with different strides & randomizing */
533 TEST(array_store, TextSentencesRandom_Stride3_Chunk3)
534 {
535  plain_text_helper(WORDS, 'q', 3, 3, 7337);
536 }
537 TEST(array_store, TextSentencesRandom_Stride8_Chunk8)
538 {
539  plain_text_helper(WORDS, 'n', 8, 8, 5667);
540 }
541 TEST(array_store, TextSentencesRandom_Stride32_Chunk1)
542 {
543  plain_text_helper(WORDS, 'a', 1, 32, 1212);
544 }
545 TEST(array_store, TextSentencesRandom_Stride12_Chunk512)
546 {
547  plain_text_helper(WORDS, 'g', 12, 512, 9999);
548 }
549 TEST(array_store, TextSentencesRandom_Stride128_Chunk6)
550 {
551  plain_text_helper(WORDS, 'b', 20, 6, 1000);
552 }
553 
554 #undef WORDS
555 
556 /* -------------------------------------------------------------------- */
557 /* Random Data Tests */
558 
559 static unsigned int rand_range_i(RNG *rng,
560  unsigned int min_i,
561  unsigned int max_i,
562  unsigned int step)
563 {
564  if (min_i == max_i) {
565  return min_i;
566  }
567  BLI_assert(min_i <= max_i);
568  BLI_assert(((min_i % step) == 0) && ((max_i % step) == 0));
569  unsigned int range = (max_i - min_i);
570  unsigned int value = BLI_rng_get_uint(rng) % range;
571  value = (value / step) * step;
572  return min_i + value;
573 }
574 
576  const size_t stride,
577  const size_t data_min_len,
578  const size_t data_max_len,
579 
580  const unsigned int mutate,
581  RNG *rng)
582 {
583  size_t data_len = rand_range_i(rng, data_min_len, data_max_len + stride, stride);
584  char *data = (char *)MEM_mallocN(data_len, __func__);
585 
586  if (lb->last == nullptr) {
588  }
589  else {
590  TestBuffer *tb_last = (TestBuffer *)lb->last;
591  if (tb_last->data_len >= data_len) {
592  memcpy(data, tb_last->data, data_len);
593  }
594  else {
595  memcpy(data, tb_last->data, tb_last->data_len);
596  BLI_rng_get_char_n(rng, &data[tb_last->data_len], data_len - tb_last->data_len);
597  }
598 
599  /* perform multiple small mutations to the array. */
600  for (int i = 0; i < mutate; i++) {
601  enum {
602  MUTATE_NOP = 0,
603  MUTATE_ADD,
604  MUTATE_REMOVE,
605  MUTATE_ROTATE,
606  MUTATE_RANDOMIZE,
607  MUTATE_TOTAL,
608  };
609 
610  switch ((BLI_rng_get_uint(rng) % MUTATE_TOTAL)) {
611  case MUTATE_NOP: {
612  break;
613  }
614  case MUTATE_ADD: {
615  const unsigned int offset = rand_range_i(rng, 0, data_len, stride);
616  if (data_len < data_max_len) {
617  data_len += stride;
618  data = (char *)MEM_reallocN((void *)data, data_len);
619  memmove(&data[offset + stride], &data[offset], data_len - (offset + stride));
621  }
622  break;
623  }
624  case MUTATE_REMOVE: {
625  const unsigned int offset = rand_range_i(rng, 0, data_len, stride);
626  if (data_len > data_min_len) {
627  memmove(&data[offset], &data[offset + stride], data_len - (offset + stride));
628  data_len -= stride;
629  }
630  break;
631  }
632  case MUTATE_ROTATE: {
633  int items = data_len / stride;
634  if (items > 1) {
635  _bli_array_wrap(data, items, stride, (BLI_rng_get_uint(rng) % 2) ? -1 : 1);
636  }
637  break;
638  }
639  case MUTATE_RANDOMIZE: {
640  if (data_len > 0) {
641  const unsigned int offset = rand_range_i(rng, 0, data_len - stride, stride);
643  }
644  break;
645  }
646  default:
648  }
649  }
650  }
651 
652  testbuffer_list_add(lb, (const void *)data, data_len);
653 }
654 
655 static void random_data_mutate_helper(const int items_size_min,
656  const int items_size_max,
657  const int items_total,
658  const int stride,
659  const int chunk_count,
660  const int random_seed,
661  const int mutate)
662 {
663 
664  ListBase lb;
665  BLI_listbase_clear(&lb);
666 
667  const size_t data_min_len = items_size_min * stride;
668  const size_t data_max_len = items_size_max * stride;
669 
670  {
671  RNG *rng = BLI_rng_new(random_seed);
672  for (int i = 0; i < items_total; i++) {
673  testbuffer_list_state_random_data(&lb, stride, data_min_len, data_max_len, mutate, rng);
674  }
675  BLI_rng_free(rng);
676  }
677 
678  testbuffer_run_tests_simple(&lb, stride, chunk_count);
679 
681 }
682 
683 TEST(array_store, TestData_Stride1_Chunk32_Mutate2)
684 {
685  random_data_mutate_helper(0, 100, 400, 1, 32, 9779, 2);
686 }
687 TEST(array_store, TestData_Stride8_Chunk512_Mutate2)
688 {
689  random_data_mutate_helper(0, 128, 400, 8, 512, 1001, 2);
690 }
691 TEST(array_store, TestData_Stride12_Chunk48_Mutate2)
692 {
693  random_data_mutate_helper(200, 256, 400, 12, 48, 1331, 2);
694 }
695 TEST(array_store, TestData_Stride32_Chunk64_Mutate1)
696 {
697  random_data_mutate_helper(0, 256, 200, 32, 64, 3112, 1);
698 }
699 TEST(array_store, TestData_Stride32_Chunk64_Mutate8)
700 {
701  random_data_mutate_helper(0, 256, 200, 32, 64, 7117, 8);
702 }
703 
704 /* -------------------------------------------------------------------- */
705 /* Randomized Chunks Test */
706 
708  const int chunks_per_buffer,
709  const int stride,
710  const int chunk_count,
711  const int random_seed)
712 {
713  RNG *rng = BLI_rng_new(random_seed);
714  const size_t chunk_size_bytes = stride * chunk_count;
715  for (int i = 0; i < chunks_per_buffer; i++) {
716  char *data_chunk = (char *)MEM_mallocN(chunk_size_bytes, __func__);
717  BLI_rng_get_char_n(rng, data_chunk, chunk_size_bytes);
718  testchunk_list_add(lb, data_chunk, chunk_size_bytes);
719  }
720  BLI_rng_free(rng);
721 }
722 
726 static void random_chunk_mutate_helper(const int chunks_per_buffer,
727  const int items_total,
728  const int stride,
729  const int chunk_count,
730  const int random_seed)
731 {
732  /* generate random chunks */
733 
734  ListBase random_chunks;
735  BLI_listbase_clear(&random_chunks);
736  random_chunk_generate(&random_chunks, chunks_per_buffer, stride, chunk_count, random_seed);
737  TestChunk **chunks_array = (TestChunk **)MEM_mallocN(chunks_per_buffer * sizeof(TestChunk *),
738  __func__);
739  {
740  TestChunk *tc = (TestChunk *)random_chunks.first;
741  for (int i = 0; i < chunks_per_buffer; i++, tc = tc->next) {
742  chunks_array[i] = tc;
743  }
744  }
745 
746  /* add and re-order each time */
747  ListBase lb;
748  BLI_listbase_clear(&lb);
749 
750  {
751  RNG *rng = BLI_rng_new(random_seed);
752  for (int i = 0; i < items_total; i++) {
753  BLI_rng_shuffle_array(rng, chunks_array, sizeof(TestChunk *), chunks_per_buffer);
754  size_t data_len;
755  char *data = testchunk_as_data_array(chunks_array, chunks_per_buffer, &data_len);
756  BLI_assert(data_len == chunks_per_buffer * chunk_count * stride);
757  testbuffer_list_add(&lb, (const void *)data, data_len);
758  }
759  BLI_rng_free(rng);
760  }
761 
762  testchunk_list_free(&random_chunks);
763  MEM_freeN(chunks_array);
764 
765  BArrayStore *bs = BLI_array_store_create(stride, chunk_count);
767 
768  size_t expected_size = chunks_per_buffer * chunk_count * stride;
770 
772 
774 }
775 
776 TEST(array_store, TestChunk_Rand8_Stride1_Chunk64)
777 {
778  random_chunk_mutate_helper(8, 100, 1, 64, 9779);
779 }
780 TEST(array_store, TestChunk_Rand32_Stride1_Chunk64)
781 {
782  random_chunk_mutate_helper(32, 100, 1, 64, 1331);
783 }
784 TEST(array_store, TestChunk_Rand64_Stride8_Chunk32)
785 {
786  random_chunk_mutate_helper(64, 100, 8, 32, 2772);
787 }
788 TEST(array_store, TestChunk_Rand31_Stride11_Chunk21)
789 {
790  random_chunk_mutate_helper(31, 100, 11, 21, 7117);
791 }
792 
793 #if 0
794 /* -------------------------------------------------------------------- */
795 
796 /* Test From Files (disabled, keep for local tests.) */
797 
798 void *file_read_binary_as_mem(const char *filepath, size_t pad_bytes, size_t *r_size)
799 {
800  FILE *fp = fopen(filepath, "rb");
801  void *mem = NULL;
802 
803  if (fp) {
804  long int filelen_read;
805  fseek(fp, 0L, SEEK_END);
806  const long int filelen = ftell(fp);
807  if (filelen == -1) {
808  goto finally;
809  }
810  fseek(fp, 0L, SEEK_SET);
811 
812  mem = MEM_mallocN(filelen + pad_bytes, __func__);
813  if (mem == NULL) {
814  goto finally;
815  }
816 
817  filelen_read = fread(mem, 1, filelen, fp);
818  if ((filelen_read != filelen) || ferror(fp)) {
819  MEM_freeN(mem);
820  mem = NULL;
821  goto finally;
822  }
823 
824  *r_size = filelen_read;
825 
826  finally:
827  fclose(fp);
828  }
829 
830  return mem;
831 }
832 
833 TEST(array_store, PlainTextFiles)
834 {
835  ListBase lb;
836  BLI_listbase_clear(&lb);
837  BArrayStore *bs = BLI_array_store_create(1, 128);
838 
839  for (int i = 0; i < 629; i++) {
840  char str[512];
841  BLI_snprintf(str, sizeof(str), "/src/py_array_cow/test_data/xz_data/%04d.c.xz", i);
842  // BLI_snprintf(str, sizeof(str), "/src/py_array_cow/test_data/c_code/%04d.c", i);
843  // printf("%s\n", str);
844  size_t data_len;
845  void *data;
846  data = file_read_binary_as_mem(str, 0, &data_len);
847 
848  testbuffer_list_add(&lb, (const void *)data, data_len);
849  }
850 
851  /* forwards */
853  EXPECT_TRUE(testbuffer_list_validate(&lb));
854  EXPECT_TRUE(BLI_array_store_is_valid(bs));
855 # ifdef DEBUG_PRINT
856  print_mem_saved("source code forward", bs);
857 # endif
858 
861 
862  /* backwards */
864  EXPECT_TRUE(testbuffer_list_validate(&lb));
865  EXPECT_TRUE(BLI_array_store_is_valid(bs));
866 # ifdef DEBUG_PRINT
867  print_mem_saved("source code backwards", bs);
868 # endif
869 
872 }
873 #endif
Efficient in-memory storage of multiple similar arrays.
void * BLI_array_store_state_data_get_alloc(BArrayState *state, size_t *r_data_len)
Definition: array_store.c:1580
void BLI_array_store_state_remove(BArrayStore *bs, BArrayState *state)
Definition: array_store.c:1545
size_t BLI_array_store_calc_size_expanded_get(const BArrayStore *bs)
Definition: array_store.c:1469
BArrayStore * BLI_array_store_create(unsigned int stride, unsigned int chunk_count)
Definition: array_store.c:1388
BArrayState * BLI_array_store_state_add(BArrayStore *bs, const void *data, size_t data_len, const BArrayState *state_reference)
Definition: array_store.c:1497
bool BLI_array_store_is_valid(BArrayStore *bs)
Definition: array_store.c:1604
size_t BLI_array_store_state_size_get(BArrayState *state)
Definition: array_store.c:1557
void BLI_array_store_destroy(BArrayStore *bs)
Definition: array_store.c:1441
size_t BLI_array_store_calc_size_compacted_get(const BArrayStore *bs)
Definition: array_store.c:1478
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)
#define TESTBUFFER_STRINGS(stride, chunk_count,...)
static void testbuffer_list_state_from_data__stride_expand(ListBase *lb, const char *data, const size_t data_len, const size_t stride)
TEST(array_store, Nop)
#define TESTBUFFER_STRINGS_CREATE(lb,...)
static void testbuffer_list_store_populate(BArrayStore *bs, ListBase *lb)
static void testbuffer_list_store_clear(BArrayStore *bs, ListBase *lb)
static bool testbuffer_item_validate(TestBuffer *tb)
static void testbuffer_list_data_randomize(ListBase *lb, unsigned int random_seed)
static TestBuffer * testbuffer_list_add(ListBase *lb, const void *data, size_t data_len)
static void testbuffer_list_state_random_data(ListBase *lb, const size_t stride, const size_t data_min_len, const size_t data_max_len, const unsigned int mutate, RNG *rng)
static unsigned int rand_range_i(RNG *rng, unsigned int min_i, unsigned int max_i, unsigned int step)
static TestChunk * testchunk_list_add(ListBase *lb, const void *data, size_t 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)
static void testbuffer_run_tests(BArrayStore *bs, ListBase *lb)
static TestBuffer * testbuffer_list_add_copydata(ListBase *lb, const void *data, size_t data_len)
static void testchunk_list_free(ListBase *lb)
static void testbuffer_run_tests_single(BArrayStore *bs, ListBase *lb)
static bool testbuffer_list_validate(const ListBase *lb)
static void random_chunk_generate(ListBase *lb, const int chunks_per_buffer, const int stride, const int chunk_count, const int random_seed)
static void testbuffer_list_state_from_data(ListBase *lb, const char *data, const size_t data_len)
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)
#define WORDS
static void testbuffer_run_tests_simple(ListBase *lb, const int stride, const int chunk_count)
#define D
static void testbuffer_list_free(ListBase *lb)
static char * testchunk_as_data_array(TestChunk **tc_array, int tc_array_len, size_t *r_data_len)
Generic array manipulation API.
void _bli_array_wrap(void *arr, uint arr_len, size_t arr_stride, int dir)
Definition: array_utils.c:40
#define BLI_assert_unreachable()
Definition: BLI_assert.h:93
#define BLI_assert(a)
Definition: BLI_assert.h:46
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
BLI_INLINE void BLI_listbase_clear(struct ListBase *lb)
Definition: BLI_listbase.h:273
void BLI_addtail(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition: listbase.c:80
void void void void void void BLI_listbase_reverse(struct ListBase *lb) ATTR_NONNULL(1)
Definition: listbase.c:797
Random number functions.
void BLI_rng_shuffle_array(struct RNG *rng, void *data, unsigned int elem_size_i, unsigned int elem_num) ATTR_NONNULL(1
void BLI_rng_free(struct RNG *rng) ATTR_NONNULL(1)
Definition: rand.cc:58
unsigned int BLI_rng_get_uint(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition: rand.cc:83
struct RNG * BLI_rng_new(unsigned int seed)
Definition: rand.cc:39
void BLI_rng_get_char_n(RNG *rng, char *bytes, size_t bytes_len) ATTR_NONNULL(1
void BLI_array_randomize(void *data, unsigned int elem_size, unsigned int elem_num, unsigned int seed)
Definition: rand.cc:188
size_t BLI_snprintf(char *__restrict dst, size_t maxncpy, const char *__restrict format,...) ATTR_NONNULL(1
#define ELEM(...)
int max_i(int a, int b)
Definition: Basic.c:10
int min_i(int a, int b)
Definition: Basic.c:6
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei stride
Read Guarded memory(de)allocation.
#define MEM_reallocN(vmemh, len)
#define str(s)
ccl_gpu_kernel_postfix ccl_global float int int int int float bool int offset
const int state
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
#define L
void * last
Definition: DNA_listBase.h:31
void * first
Definition: DNA_listBase.h:31
Definition: rand.cc:33
struct TestBuffer * prev
BArrayState * state
struct TestBuffer * next
const void * data
const void * data
struct TestChunk * prev
struct TestChunk * next