Blender  V3.3
array_store.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
86 #include <stdlib.h>
87 #include <string.h>
88 
89 #include "MEM_guardedalloc.h"
90 
91 #include "BLI_listbase.h"
92 #include "BLI_mempool.h"
93 
94 #include "BLI_strict_flags.h"
95 
96 #include "BLI_array_store.h" /* own include */
97 
98 /* only for BLI_array_store_is_valid */
99 #include "BLI_ghash.h"
100 
101 /* -------------------------------------------------------------------- */
108 /* Scan first chunks (happy path when beginning of the array matches).
109  * When the array is a perfect match, we can re-use the entire list.
110  *
111  * Note that disabling makes some tests fail that check for output-size.
112  */
113 #define USE_FASTPATH_CHUNKS_FIRST
114 
115 /* Scan last chunks (happy path when end of the array matches).
116  * When the end of the array matches, we can quickly add these chunks.
117  * note that we will add contiguous matching chunks
118  * so this isn't as useful as USE_FASTPATH_CHUNKS_FIRST,
119  * however it avoids adding matching chunks into the lookup table,
120  * so creating the lookup table won't be as expensive.
121  */
122 #ifdef USE_FASTPATH_CHUNKS_FIRST
123 # define USE_FASTPATH_CHUNKS_LAST
124 #endif
125 
126 /* For arrays of matching length, test that *enough* of the chunks are aligned,
127  * and simply step over both arrays, using matching chunks.
128  * This avoids overhead of using a lookup table for cases
129  * when we can assume they're mostly aligned.
130  */
131 #define USE_ALIGN_CHUNKS_TEST
132 
133 /* Accumulate hashes from right to left so we can create a hash for the chunk-start.
134  * This serves to increase uniqueness and will help when there is many values which are the same.
135  */
136 #define USE_HASH_TABLE_ACCUMULATE
137 
138 #ifdef USE_HASH_TABLE_ACCUMULATE
139 /* Number of times to propagate hashes back.
140  * Effectively a 'triangle-number'.
141  * so 4 -> 7, 5 -> 10, 6 -> 15... etc.
142  */
143 # define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS 4
144 #else
145 /* How many items to hash (multiplied by stride)
146  */
147 # define BCHUNK_HASH_LEN 4
148 #endif
149 
150 /* Calculate the key once and reuse it
151  */
152 #define USE_HASH_TABLE_KEY_CACHE
153 #ifdef USE_HASH_TABLE_KEY_CACHE
154 # define HASH_TABLE_KEY_UNSET ((uint64_t)-1)
155 # define HASH_TABLE_KEY_FALLBACK ((uint64_t)-2)
156 #endif
157 
158 /* How much larger the table is then the total number of chunks.
159  */
160 #define BCHUNK_HASH_TABLE_MUL 3
161 
162 /* Merge too small/large chunks:
163  *
164  * Using this means chunks below a threshold will be merged together.
165  * Even though short term this uses more memory,
166  * long term the overhead of maintaining many small chunks is reduced.
167  * This is defined by setting the minimum chunk size (as a fraction of the regular chunk size).
168  *
169  * Chunks may also become too large (when incrementally growing an array),
170  * this also enables chunk splitting.
171  */
172 #define USE_MERGE_CHUNKS
173 
174 #ifdef USE_MERGE_CHUNKS
175 /* Merge chunks smaller then: (chunk_size / BCHUNK_MIN_SIZE_DIV)
176  */
177 # define BCHUNK_SIZE_MIN_DIV 8
178 
179 /* Disallow chunks bigger than the regular chunk size scaled by this value
180  * NOTE: must be at least 2!
181  * however, this code runs won't run in tests unless it's ~1.1 ugh.
182  * so lower only to check splitting works.
183  */
184 # define BCHUNK_SIZE_MAX_MUL 2
185 #endif /* USE_MERGE_CHUNKS */
186 
187 /* slow (keep disabled), but handy for debugging */
188 // #define USE_VALIDATE_LIST_SIZE
189 
190 // #define USE_VALIDATE_LIST_DATA_PARTIAL
191 
192 // #define USE_PARANOID_CHECKS
193 
196 /* -------------------------------------------------------------------- */
201 
202 typedef struct BArrayInfo {
203  size_t chunk_stride;
204  // uint chunk_count; /* UNUSED (other values are derived from this) */
205 
206  /* pre-calculated */
208  /* min/max limits (inclusive) */
211 
213 #ifdef USE_HASH_TABLE_ACCUMULATE
214  size_t accum_steps;
216 #endif
218 
219 typedef struct BArrayMemory {
220  BLI_mempool *chunk_list; /* BChunkList */
221  BLI_mempool *chunk_ref; /* BChunkRef */
222  BLI_mempool *chunk; /* BChunk */
224 
228 struct BArrayStore {
229  /* static */
231 
232  /* memory storage */
234 
239 };
240 
251 struct BArrayState {
253  struct BArrayState *next, *prev;
254 
255  struct BChunkList *chunk_list; /* BChunkList's */
256 };
257 
258 typedef struct BChunkList {
259  ListBase chunk_refs; /* BChunkRef's */
260  uint chunk_refs_len; /* BLI_listbase_count(chunks), store for reuse. */
261  size_t total_size; /* size of all chunks */
262 
264  int users;
266 
267 /* a chunk of an array */
268 typedef struct BChunk {
269  const uchar *data;
270  size_t data_len;
272  int users;
273 
274 #ifdef USE_HASH_TABLE_KEY_CACHE
276 #endif
278 
282 typedef struct BChunkRef {
283  struct BChunkRef *next, *prev;
286 
295 typedef struct BTableRef {
296  struct BTableRef *next;
297  const BChunkRef *cref;
299 
302 static size_t bchunk_list_size(const BChunkList *chunk_list);
303 
304 /* -------------------------------------------------------------------- */
308 static BChunk *bchunk_new(BArrayMemory *bs_mem, const uchar *data, const size_t data_len)
309 {
310  BChunk *chunk = BLI_mempool_alloc(bs_mem->chunk);
311  chunk->data = data;
312  chunk->data_len = data_len;
313  chunk->users = 0;
314 #ifdef USE_HASH_TABLE_KEY_CACHE
315  chunk->key = HASH_TABLE_KEY_UNSET;
316 #endif
317  return chunk;
318 }
319 
320 static BChunk *bchunk_new_copydata(BArrayMemory *bs_mem, const uchar *data, const size_t data_len)
321 {
322  uchar *data_copy = MEM_mallocN(data_len, __func__);
323  memcpy(data_copy, data, data_len);
324  return bchunk_new(bs_mem, data_copy, data_len);
325 }
326 
327 static void bchunk_decref(BArrayMemory *bs_mem, BChunk *chunk)
328 {
329  BLI_assert(chunk->users > 0);
330  if (chunk->users == 1) {
331  MEM_freeN((void *)chunk->data);
332  BLI_mempool_free(bs_mem->chunk, chunk);
333  }
334  else {
335  chunk->users -= 1;
336  }
337 }
338 
339 static bool bchunk_data_compare(const BChunk *chunk,
340  const uchar *data_base,
341  const size_t data_base_len,
342  const size_t offset)
343 {
344  if (offset + (size_t)chunk->data_len <= data_base_len) {
345  return (memcmp(&data_base[offset], chunk->data, chunk->data_len) == 0);
346  }
347  return false;
348 }
349 
352 /* -------------------------------------------------------------------- */
356 static BChunkList *bchunk_list_new(BArrayMemory *bs_mem, size_t total_size)
357 {
358  BChunkList *chunk_list = BLI_mempool_alloc(bs_mem->chunk_list);
359 
360  BLI_listbase_clear(&chunk_list->chunk_refs);
361  chunk_list->chunk_refs_len = 0;
362  chunk_list->total_size = total_size;
363  chunk_list->users = 0;
364  return chunk_list;
365 }
366 
367 static void bchunk_list_decref(BArrayMemory *bs_mem, BChunkList *chunk_list)
368 {
369  BLI_assert(chunk_list->users > 0);
370  if (chunk_list->users == 1) {
371  for (BChunkRef *cref = chunk_list->chunk_refs.first, *cref_next; cref; cref = cref_next) {
372  cref_next = cref->next;
373  bchunk_decref(bs_mem, cref->link);
374  BLI_mempool_free(bs_mem->chunk_ref, cref);
375  }
376 
377  BLI_mempool_free(bs_mem->chunk_list, chunk_list);
378  }
379  else {
380  chunk_list->users -= 1;
381  }
382 }
383 
384 #ifdef USE_VALIDATE_LIST_SIZE
385 # ifndef NDEBUG
386 # define ASSERT_CHUNKLIST_SIZE(chunk_list, n) BLI_assert(bchunk_list_size(chunk_list) == n)
387 # endif
388 #endif
389 #ifndef ASSERT_CHUNKLIST_SIZE
390 # define ASSERT_CHUNKLIST_SIZE(chunk_list, n) (EXPR_NOP(chunk_list), EXPR_NOP(n))
391 #endif
392 
393 #ifdef USE_VALIDATE_LIST_DATA_PARTIAL
394 static size_t bchunk_list_data_check(const BChunkList *chunk_list, const uchar *data)
395 {
396  size_t offset = 0;
397  LISTBASE_FOREACH (BChunkRef *, cref, &chunk_list->chunk_refs) {
398  if (memcmp(&data[offset], cref->link->data, cref->link->data_len) != 0) {
399  return false;
400  }
401  offset += cref->link->data_len;
402  }
403  return true;
404 }
405 # define ASSERT_CHUNKLIST_DATA(chunk_list, data) \
406  BLI_assert(bchunk_list_data_check(chunk_list, data))
407 #else
408 # define ASSERT_CHUNKLIST_DATA(chunk_list, data) (EXPR_NOP(chunk_list), EXPR_NOP(data))
409 #endif
410 
411 #ifdef USE_MERGE_CHUNKS
413  BArrayMemory *bs_mem,
414  BChunkList *chunk_list)
415 {
416  BChunkRef *cref = chunk_list->chunk_refs.last;
417  if (cref && cref->prev) {
418  /* both are decref'd after use (end of this block) */
419  BChunk *chunk_curr = cref->link;
420  BChunk *chunk_prev = cref->prev->link;
421 
422  if (MIN2(chunk_prev->data_len, chunk_curr->data_len) < info->chunk_byte_size_min) {
423  const size_t data_merge_len = chunk_prev->data_len + chunk_curr->data_len;
424  /* we could pass, but no need */
425  if (data_merge_len <= info->chunk_byte_size_max) {
426  /* we have enough space to merge */
427 
428  /* Remove last from the linked-list. */
429  BLI_assert(chunk_list->chunk_refs.last != chunk_list->chunk_refs.first);
430  cref->prev->next = NULL;
431  chunk_list->chunk_refs.last = cref->prev;
432  chunk_list->chunk_refs_len -= 1;
433 
434  uchar *data_merge = MEM_mallocN(data_merge_len, __func__);
435  memcpy(data_merge, chunk_prev->data, chunk_prev->data_len);
436  memcpy(&data_merge[chunk_prev->data_len], chunk_curr->data, chunk_curr->data_len);
437 
438  cref->prev->link = bchunk_new(bs_mem, data_merge, data_merge_len);
439  cref->prev->link->users += 1;
440 
441  BLI_mempool_free(bs_mem->chunk_ref, cref);
442  }
443  else {
444  /* If we always merge small slices, we should _almost_
445  * never end up having very large chunks.
446  * Gradual expanding on contracting will cause this.
447  *
448  * if we do, the code below works (test by setting 'BCHUNK_SIZE_MAX_MUL = 1.2') */
449 
450  /* keep chunk on the left hand side a regular size */
451  const size_t split = info->chunk_byte_size;
452 
453  /* merge and split */
454  const size_t data_prev_len = split;
455  const size_t data_curr_len = data_merge_len - split;
456  uchar *data_prev = MEM_mallocN(data_prev_len, __func__);
457  uchar *data_curr = MEM_mallocN(data_curr_len, __func__);
458 
459  if (data_prev_len <= chunk_prev->data_len) {
460  const size_t data_curr_shrink_len = chunk_prev->data_len - data_prev_len;
461 
462  /* setup 'data_prev' */
463  memcpy(data_prev, chunk_prev->data, data_prev_len);
464 
465  /* setup 'data_curr' */
466  memcpy(data_curr, &chunk_prev->data[data_prev_len], data_curr_shrink_len);
467  memcpy(&data_curr[data_curr_shrink_len], chunk_curr->data, chunk_curr->data_len);
468  }
469  else {
470  BLI_assert(data_curr_len <= chunk_curr->data_len);
471  BLI_assert(data_prev_len >= chunk_prev->data_len);
472 
473  const size_t data_prev_grow_len = data_prev_len - chunk_prev->data_len;
474 
475  /* setup 'data_prev' */
476  memcpy(data_prev, chunk_prev->data, chunk_prev->data_len);
477  memcpy(&data_prev[chunk_prev->data_len], chunk_curr->data, data_prev_grow_len);
478 
479  /* setup 'data_curr' */
480  memcpy(data_curr, &chunk_curr->data[data_prev_grow_len], data_curr_len);
481  }
482 
483  cref->prev->link = bchunk_new(bs_mem, data_prev, data_prev_len);
484  cref->prev->link->users += 1;
485 
486  cref->link = bchunk_new(bs_mem, data_curr, data_curr_len);
487  cref->link->users += 1;
488  }
489 
490  /* free zero users */
491  bchunk_decref(bs_mem, chunk_curr);
492  bchunk_decref(bs_mem, chunk_prev);
493  }
494  }
495 }
496 #endif /* USE_MERGE_CHUNKS */
497 
506 static void bchunk_list_calc_trim_len(const BArrayInfo *info,
507  const size_t data_len,
508  size_t *r_data_trim_len,
509  size_t *r_data_last_chunk_len)
510 {
511  size_t data_last_chunk_len = 0;
512  size_t data_trim_len = data_len;
513 
514 #ifdef USE_MERGE_CHUNKS
515  /* avoid creating too-small chunks
516  * more efficient than merging after */
517  if (data_len > info->chunk_byte_size) {
518  data_last_chunk_len = (data_trim_len % info->chunk_byte_size);
519  data_trim_len = data_trim_len - data_last_chunk_len;
520  if (data_last_chunk_len) {
521  if (data_last_chunk_len < info->chunk_byte_size_min) {
522  /* May be zero and that's OK. */
523  data_trim_len -= info->chunk_byte_size;
524  data_last_chunk_len += info->chunk_byte_size;
525  }
526  }
527  }
528  else {
529  data_trim_len = 0;
530  data_last_chunk_len = data_len;
531  }
532 
533  BLI_assert((data_trim_len == 0) || (data_trim_len >= info->chunk_byte_size));
534 #else
535  data_last_chunk_len = (data_trim_len % info->chunk_byte_size);
536  data_trim_len = data_trim_len - data_last_chunk_len;
537 #endif
538 
539  BLI_assert(data_trim_len + data_last_chunk_len == data_len);
540 
541  *r_data_trim_len = data_trim_len;
542  *r_data_last_chunk_len = data_last_chunk_len;
543 }
544 
548 static void bchunk_list_append_only(BArrayMemory *bs_mem, BChunkList *chunk_list, BChunk *chunk)
549 {
551  BLI_addtail(&chunk_list->chunk_refs, cref);
552  cref->link = chunk;
553  chunk_list->chunk_refs_len += 1;
554  chunk->users += 1;
555 }
556 
561 static void bchunk_list_append_data(const BArrayInfo *info,
562  BArrayMemory *bs_mem,
563  BChunkList *chunk_list,
564  const uchar *data,
565  const size_t data_len)
566 {
567  BLI_assert(data_len != 0);
568 
569 #ifdef USE_MERGE_CHUNKS
570  BLI_assert(data_len <= info->chunk_byte_size_max);
571 
572  if (!BLI_listbase_is_empty(&chunk_list->chunk_refs)) {
573  BChunkRef *cref = chunk_list->chunk_refs.last;
574  BChunk *chunk_prev = cref->link;
575 
576  if (MIN2(chunk_prev->data_len, data_len) < info->chunk_byte_size_min) {
577  const size_t data_merge_len = chunk_prev->data_len + data_len;
578  /* realloc for single user */
579  if (cref->link->users == 1) {
580  uchar *data_merge = MEM_reallocN((void *)cref->link->data, data_merge_len);
581  memcpy(&data_merge[chunk_prev->data_len], data, data_len);
582  cref->link->data = data_merge;
583  cref->link->data_len = data_merge_len;
584  }
585  else {
586  uchar *data_merge = MEM_mallocN(data_merge_len, __func__);
587  memcpy(data_merge, chunk_prev->data, chunk_prev->data_len);
588  memcpy(&data_merge[chunk_prev->data_len], data, data_len);
589  cref->link = bchunk_new(bs_mem, data_merge, data_merge_len);
590  cref->link->users += 1;
591  bchunk_decref(bs_mem, chunk_prev);
592  }
593  return;
594  }
595  }
596 #else
597  UNUSED_VARS(info);
598 #endif /* USE_MERGE_CHUNKS */
599 
600  BChunk *chunk = bchunk_new_copydata(bs_mem, data, data_len);
601  bchunk_list_append_only(bs_mem, chunk_list, chunk);
602 
603  /* don't run this, instead preemptively avoid creating a chunk only to merge it (above). */
604 #if 0
605 # ifdef USE_MERGE_CHUNKS
606  bchunk_list_ensure_min_size_last(info, bs_mem, chunk_list);
607 # endif
608 #endif
609 }
610 
618 static void bchunk_list_append_data_n(const BArrayInfo *info,
619  BArrayMemory *bs_mem,
620  BChunkList *chunk_list,
621  const uchar *data,
622  size_t data_len)
623 {
624  size_t data_trim_len, data_last_chunk_len;
625  bchunk_list_calc_trim_len(info, data_len, &data_trim_len, &data_last_chunk_len);
626 
627  if (data_trim_len != 0) {
628  size_t i_prev;
629 
630  {
631  const size_t i = info->chunk_byte_size;
632  bchunk_list_append_data(info, bs_mem, chunk_list, data, i);
633  i_prev = i;
634  }
635 
636  while (i_prev != data_trim_len) {
637  const size_t i = i_prev + info->chunk_byte_size;
638  BChunk *chunk = bchunk_new_copydata(bs_mem, &data[i_prev], i - i_prev);
639  bchunk_list_append_only(bs_mem, chunk_list, chunk);
640  i_prev = i;
641  }
642 
643  if (data_last_chunk_len) {
644  BChunk *chunk = bchunk_new_copydata(bs_mem, &data[i_prev], data_last_chunk_len);
645  bchunk_list_append_only(bs_mem, chunk_list, chunk);
646  // i_prev = data_len; /* UNUSED */
647  }
648  }
649  else {
650  /* if we didn't write any chunks previously,
651  * we may need to merge with the last. */
652  if (data_last_chunk_len) {
653  bchunk_list_append_data(info, bs_mem, chunk_list, data, data_last_chunk_len);
654  // i_prev = data_len; /* UNUSED */
655  }
656  }
657 
658 #ifdef USE_MERGE_CHUNKS
659  if (data_len > info->chunk_byte_size) {
660  BLI_assert(((BChunkRef *)chunk_list->chunk_refs.last)->link->data_len >=
661  info->chunk_byte_size_min);
662  }
663 #endif
664 }
665 
666 static void bchunk_list_append(const BArrayInfo *info,
667  BArrayMemory *bs_mem,
668  BChunkList *chunk_list,
669  BChunk *chunk)
670 {
671  bchunk_list_append_only(bs_mem, chunk_list, chunk);
672 
673 #ifdef USE_MERGE_CHUNKS
674  bchunk_list_ensure_min_size_last(info, bs_mem, chunk_list);
675 #else
676  UNUSED_VARS(info);
677 #endif
678 }
679 
680 static void bchunk_list_fill_from_array(const BArrayInfo *info,
681  BArrayMemory *bs_mem,
682  BChunkList *chunk_list,
683  const uchar *data,
684  const size_t data_len)
685 {
687 
688  size_t data_trim_len, data_last_chunk_len;
689  bchunk_list_calc_trim_len(info, data_len, &data_trim_len, &data_last_chunk_len);
690 
691  size_t i_prev = 0;
692  while (i_prev != data_trim_len) {
693  const size_t i = i_prev + info->chunk_byte_size;
694  BChunk *chunk = bchunk_new_copydata(bs_mem, &data[i_prev], i - i_prev);
695  bchunk_list_append_only(bs_mem, chunk_list, chunk);
696  i_prev = i;
697  }
698 
699  if (data_last_chunk_len) {
700  BChunk *chunk = bchunk_new_copydata(bs_mem, &data[i_prev], data_last_chunk_len);
701  bchunk_list_append_only(bs_mem, chunk_list, chunk);
702  // i_prev = data_len;
703  }
704 
705 #ifdef USE_MERGE_CHUNKS
706  if (data_len > info->chunk_byte_size) {
707  BLI_assert(((BChunkRef *)chunk_list->chunk_refs.last)->link->data_len >=
708  info->chunk_byte_size_min);
709  }
710 #endif
711 
712  /* works but better avoid redundant re-alloc */
713 #if 0
714 # ifdef USE_MERGE_CHUNKS
715  bchunk_list_ensure_min_size_last(info, bs_mem, chunk_list);
716 # endif
717 #endif
718 
719  ASSERT_CHUNKLIST_SIZE(chunk_list, data_len);
720  ASSERT_CHUNKLIST_DATA(chunk_list, data);
721 }
722 
725 /*
726  * Internal Table Lookup Functions
727  */
728 
729 /* -------------------------------------------------------------------- */
735 #define HASH_INIT (5381)
736 
738 {
739  return ((HASH_INIT << 5) + HASH_INIT) + (unsigned int)(*((signed char *)&p));
740 }
741 
742 /* hash bytes, from BLI_ghashutil_strhash_n */
743 static uint hash_data(const uchar *key, size_t n)
744 {
745  const signed char *p;
746  unsigned int h = HASH_INIT;
747 
748  for (p = (const signed char *)key; n--; p++) {
749  h = ((h << 5) + h) + (unsigned int)*p;
750  }
751 
752  return h;
753 }
754 
755 #undef HASH_INIT
756 
757 #ifdef USE_HASH_TABLE_ACCUMULATE
758 static void hash_array_from_data(const BArrayInfo *info,
759  const uchar *data_slice,
760  const size_t data_slice_len,
761  hash_key *hash_array)
762 {
763  if (info->chunk_stride != 1) {
764  for (size_t i = 0, i_step = 0; i_step < data_slice_len; i++, i_step += info->chunk_stride) {
765  hash_array[i] = hash_data(&data_slice[i_step], info->chunk_stride);
766  }
767  }
768  else {
769  /* fast-path for bytes */
770  for (size_t i = 0; i < data_slice_len; i++) {
771  hash_array[i] = hash_data_single(data_slice[i]);
772  }
773  }
774 }
775 
776 /*
777  * Similar to hash_array_from_data,
778  * but able to step into the next chunk if we run-out of data.
779  */
780 static void hash_array_from_cref(const BArrayInfo *info,
781  const BChunkRef *cref,
782  const size_t data_len,
783  hash_key *hash_array)
784 {
785  const size_t hash_array_len = data_len / info->chunk_stride;
786  size_t i = 0;
787  do {
788  size_t i_next = hash_array_len - i;
789  size_t data_trim_len = i_next * info->chunk_stride;
790  if (data_trim_len > cref->link->data_len) {
791  data_trim_len = cref->link->data_len;
792  i_next = data_trim_len / info->chunk_stride;
793  }
794  BLI_assert(data_trim_len <= cref->link->data_len);
795  hash_array_from_data(info, cref->link->data, data_trim_len, &hash_array[i]);
796  i += i_next;
797  cref = cref->next;
798  } while ((i < hash_array_len) && (cref != NULL));
799 
800  /* If this isn't equal, the caller didn't properly check
801  * that there was enough data left in all chunks */
802  BLI_assert(i == hash_array_len);
803 }
804 
805 static void hash_accum(hash_key *hash_array, const size_t hash_array_len, size_t iter_steps)
806 {
807  /* _very_ unlikely, can happen if you select a chunk-size of 1 for example. */
808  if (UNLIKELY((iter_steps > hash_array_len))) {
809  iter_steps = hash_array_len;
810  }
811 
812  const size_t hash_array_search_len = hash_array_len - iter_steps;
813  while (iter_steps != 0) {
814  const size_t hash_offset = iter_steps;
815  for (uint i = 0; i < hash_array_search_len; i++) {
816  hash_array[i] += (hash_array[i + hash_offset]) * ((hash_array[i] & 0xff) + 1);
817  }
818  iter_steps -= 1;
819  }
820 }
821 
826 static void hash_accum_single(hash_key *hash_array, const size_t hash_array_len, size_t iter_steps)
827 {
828  BLI_assert(iter_steps <= hash_array_len);
829  if (UNLIKELY(!(iter_steps <= hash_array_len))) {
830  /* while this shouldn't happen, avoid crashing */
831  iter_steps = hash_array_len;
832  }
833  /* We can increase this value each step to avoid accumulating quite as much
834  * while getting the same results as hash_accum */
835  size_t iter_steps_sub = iter_steps;
836 
837  while (iter_steps != 0) {
838  const size_t hash_array_search_len = hash_array_len - iter_steps_sub;
839  const size_t hash_offset = iter_steps;
840  for (uint i = 0; i < hash_array_search_len; i++) {
841  hash_array[i] += (hash_array[i + hash_offset]) * ((hash_array[i] & 0xff) + 1);
842  }
843  iter_steps -= 1;
844  iter_steps_sub += iter_steps;
845  }
846 }
847 
849  const BChunkRef *cref,
850  /* avoid reallocating each time */
851  hash_key *hash_store,
852  const size_t hash_store_len)
853 {
854  /* in C, will fill in a reusable array */
855  BChunk *chunk = cref->link;
856  BLI_assert((info->accum_read_ahead_bytes * info->chunk_stride) != 0);
857 
858  if (info->accum_read_ahead_bytes <= chunk->data_len) {
859  hash_key key;
860 
861 # ifdef USE_HASH_TABLE_KEY_CACHE
862  key = chunk->key;
863  if (key != HASH_TABLE_KEY_UNSET) {
864  /* Using key cache!
865  * avoids calculating every time */
866  }
867  else {
868  hash_array_from_cref(info, cref, info->accum_read_ahead_bytes, hash_store);
869  hash_accum_single(hash_store, hash_store_len, info->accum_steps);
870  key = hash_store[0];
871 
872  /* cache the key */
873  if (UNLIKELY(key == HASH_TABLE_KEY_UNSET)) {
875  }
876  chunk->key = key;
877  }
878 # else
879  hash_array_from_cref(info, cref, info->accum_read_ahead_bytes, hash_store);
880  hash_accum_single(hash_store, hash_store_len, info->accum_steps);
881  key = hash_store[0];
882 # endif
883  return key;
884  }
885  /* corner case - we're too small, calculate the key each time. */
886 
887  hash_array_from_cref(info, cref, info->accum_read_ahead_bytes, hash_store);
888  hash_accum_single(hash_store, hash_store_len, info->accum_steps);
889  hash_key key = hash_store[0];
890 
891 # ifdef USE_HASH_TABLE_KEY_CACHE
892  if (UNLIKELY(key == HASH_TABLE_KEY_UNSET)) {
894  }
895 # endif
896  return key;
897 }
898 
899 static const BChunkRef *table_lookup(const BArrayInfo *info,
900  BTableRef **table,
901  const size_t table_len,
902  const size_t i_table_start,
903  const uchar *data,
904  const size_t data_len,
905  const size_t offset,
906  const hash_key *table_hash_array)
907 {
908  size_t size_left = data_len - offset;
909  hash_key key = table_hash_array[((offset - i_table_start) / info->chunk_stride)];
910  size_t key_index = (size_t)(key % (hash_key)table_len);
911  for (const BTableRef *tref = table[key_index]; tref; tref = tref->next) {
912  const BChunkRef *cref = tref->cref;
913 # ifdef USE_HASH_TABLE_KEY_CACHE
914  if (cref->link->key == key)
915 # endif
916  {
917  BChunk *chunk_test = cref->link;
918  if (chunk_test->data_len <= size_left) {
919  if (bchunk_data_compare(chunk_test, data, data_len, offset)) {
920  /* we could remove the chunk from the table, to avoid multiple hits */
921  return cref;
922  }
923  }
924  }
925  }
926  return NULL;
927 }
928 
929 #else /* USE_HASH_TABLE_ACCUMULATE */
930 
931 /* NON USE_HASH_TABLE_ACCUMULATE code (simply hash each chunk) */
932 
933 static hash_key key_from_chunk_ref(const BArrayInfo *info, const BChunkRef *cref)
934 {
935  const size_t data_hash_len = BCHUNK_HASH_LEN * info->chunk_stride;
936  hash_key key;
937  BChunk *chunk = cref->link;
938 
939 # ifdef USE_HASH_TABLE_KEY_CACHE
940  key = chunk->key;
941  if (key != HASH_TABLE_KEY_UNSET) {
942  /* Using key cache!
943  * avoids calculating every time */
944  }
945  else {
946  /* cache the key */
947  key = hash_data(chunk->data, data_hash_len);
948  if (key == HASH_TABLE_KEY_UNSET) {
950  }
951  chunk->key = key;
952  }
953 # else
954  key = hash_data(chunk->data, data_hash_len);
955 # endif
956 
957  return key;
958 }
959 
960 static const BChunkRef *table_lookup(const BArrayInfo *info,
961  BTableRef **table,
962  const size_t table_len,
963  const uint UNUSED(i_table_start),
964  const uchar *data,
965  const size_t data_len,
966  const size_t offset,
967  const hash_key *UNUSED(table_hash_array))
968 {
969  const size_t data_hash_len = BCHUNK_HASH_LEN * info->chunk_stride; /* TODO: cache. */
970 
971  size_t size_left = data_len - offset;
972  hash_key key = hash_data(&data[offset], MIN2(data_hash_len, size_left));
973  size_t key_index = (size_t)(key % (hash_key)table_len);
974  for (BTableRef *tref = table[key_index]; tref; tref = tref->next) {
975  const BChunkRef *cref = tref->cref;
976 # ifdef USE_HASH_TABLE_KEY_CACHE
977  if (cref->link->key == key)
978 # endif
979  {
980  BChunk *chunk_test = cref->link;
981  if (chunk_test->data_len <= size_left) {
982  if (bchunk_data_compare(chunk_test, data, data_len, offset)) {
983  /* we could remove the chunk from the table, to avoid multiple hits */
984  return cref;
985  }
986  }
987  }
988  }
989  return NULL;
990 }
991 
992 #endif /* USE_HASH_TABLE_ACCUMULATE */
993 
994 /* End Table Lookup
995  * ---------------- */
996 
999 /* -------------------------------------------------------------------- */
1010  BArrayMemory *bs_mem,
1011  const uchar *data,
1012  const size_t data_len_original,
1013  const BChunkList *chunk_list_reference)
1014 {
1015  ASSERT_CHUNKLIST_SIZE(chunk_list_reference, chunk_list_reference->total_size);
1016 
1017  /* -----------------------------------------------------------------------
1018  * Fast-Path for exact match
1019  * Check for exact match, if so, return the current list.
1020  */
1021 
1022  const BChunkRef *cref_match_first = NULL;
1023 
1024  uint chunk_list_reference_skip_len = 0;
1025  size_t chunk_list_reference_skip_bytes = 0;
1026  size_t i_prev = 0;
1027 
1028 #ifdef USE_FASTPATH_CHUNKS_FIRST
1029  {
1030  bool full_match = true;
1031 
1032  const BChunkRef *cref = chunk_list_reference->chunk_refs.first;
1033  while (i_prev < data_len_original) {
1034  if (cref != NULL && bchunk_data_compare(cref->link, data, data_len_original, i_prev)) {
1035  cref_match_first = cref;
1036  chunk_list_reference_skip_len += 1;
1037  chunk_list_reference_skip_bytes += cref->link->data_len;
1038  i_prev += cref->link->data_len;
1039  cref = cref->next;
1040  }
1041  else {
1042  full_match = false;
1043  break;
1044  }
1045  }
1046 
1047  if (full_match) {
1048  if (chunk_list_reference->total_size == data_len_original) {
1049  return (BChunkList *)chunk_list_reference;
1050  }
1051  }
1052  }
1053 
1054  /* End Fast-Path (first)
1055  * --------------------- */
1056 
1057 #endif /* USE_FASTPATH_CHUNKS_FIRST */
1058 
1059  /* Copy until we have a mismatch */
1060  BChunkList *chunk_list = bchunk_list_new(bs_mem, data_len_original);
1061  if (cref_match_first != NULL) {
1062  size_t chunk_size_step = 0;
1063  const BChunkRef *cref = chunk_list_reference->chunk_refs.first;
1064  while (true) {
1065  BChunk *chunk = cref->link;
1066  chunk_size_step += chunk->data_len;
1067  bchunk_list_append_only(bs_mem, chunk_list, chunk);
1068  ASSERT_CHUNKLIST_SIZE(chunk_list, chunk_size_step);
1069  ASSERT_CHUNKLIST_DATA(chunk_list, data);
1070  if (cref == cref_match_first) {
1071  break;
1072  }
1073  cref = cref->next;
1074  }
1075  /* happens when bytes are removed from the end of the array */
1076  if (chunk_size_step == data_len_original) {
1077  return chunk_list;
1078  }
1079 
1080  i_prev = chunk_size_step;
1081  }
1082  else {
1083  i_prev = 0;
1084  }
1085 
1086  /* ------------------------------------------------------------------------
1087  * Fast-Path for end chunks
1088  *
1089  * Check for trailing chunks
1090  */
1091 
1092  /* In this case use 'chunk_list_reference_last' to define the last index
1093  * index_match_last = -1 */
1094 
1095  /* warning, from now on don't use len(data)
1096  * since we want to ignore chunks already matched */
1097  size_t data_len = data_len_original;
1098 #define data_len_original invalid_usage
1099 #ifdef data_len_original /* quiet warning */
1100 #endif
1101 
1102  const BChunkRef *chunk_list_reference_last = NULL;
1103 
1104 #ifdef USE_FASTPATH_CHUNKS_LAST
1105  if (!BLI_listbase_is_empty(&chunk_list_reference->chunk_refs)) {
1106  const BChunkRef *cref = chunk_list_reference->chunk_refs.last;
1107  while ((cref->prev != NULL) && (cref != cref_match_first) &&
1108  (cref->link->data_len <= data_len - i_prev)) {
1109  BChunk *chunk_test = cref->link;
1110  size_t offset = data_len - chunk_test->data_len;
1111  if (bchunk_data_compare(chunk_test, data, data_len, offset)) {
1112  data_len = offset;
1113  chunk_list_reference_last = cref;
1114  chunk_list_reference_skip_len += 1;
1115  chunk_list_reference_skip_bytes += cref->link->data_len;
1116  cref = cref->prev;
1117  }
1118  else {
1119  break;
1120  }
1121  }
1122  }
1123 
1124  /* End Fast-Path (last)
1125  * -------------------- */
1126 #endif /* USE_FASTPATH_CHUNKS_LAST */
1127 
1128  /* -----------------------------------------------------------------------
1129  * Check for aligned chunks
1130  *
1131  * This saves a lot of searching, so use simple heuristics to detect aligned arrays.
1132  * (may need to tweak exact method).
1133  */
1134 
1135  bool use_aligned = false;
1136 
1137 #ifdef USE_ALIGN_CHUNKS_TEST
1138  if (chunk_list->total_size == chunk_list_reference->total_size) {
1139  /* if we're already a quarter aligned */
1140  if (data_len - i_prev <= chunk_list->total_size / 4) {
1141  use_aligned = true;
1142  }
1143  else {
1144  /* TODO: walk over chunks and check if some arbitrary amount align. */
1145  }
1146  }
1147 #endif /* USE_ALIGN_CHUNKS_TEST */
1148 
1149  /* End Aligned Chunk Case
1150  * ----------------------- */
1151 
1152  if (use_aligned) {
1153  /* Copy matching chunks, creates using the same 'layout' as the reference */
1154  const BChunkRef *cref = cref_match_first ? cref_match_first->next :
1155  chunk_list_reference->chunk_refs.first;
1156  while (i_prev != data_len) {
1157  const size_t i = i_prev + cref->link->data_len;
1158  BLI_assert(i != i_prev);
1159 
1160  if ((cref != chunk_list_reference_last) &&
1161  bchunk_data_compare(cref->link, data, data_len, i_prev)) {
1162  bchunk_list_append(info, bs_mem, chunk_list, cref->link);
1163  ASSERT_CHUNKLIST_SIZE(chunk_list, i);
1164  ASSERT_CHUNKLIST_DATA(chunk_list, data);
1165  }
1166  else {
1167  bchunk_list_append_data(info, bs_mem, chunk_list, &data[i_prev], i - i_prev);
1168  ASSERT_CHUNKLIST_SIZE(chunk_list, i);
1169  ASSERT_CHUNKLIST_DATA(chunk_list, data);
1170  }
1171 
1172  cref = cref->next;
1173 
1174  i_prev = i;
1175  }
1176  }
1177  else if ((data_len - i_prev >= info->chunk_byte_size) &&
1178  (chunk_list_reference->chunk_refs_len >= chunk_list_reference_skip_len) &&
1179  (chunk_list_reference->chunk_refs.first != NULL)) {
1180 
1181  /* --------------------------------------------------------------------
1182  * Non-Aligned Chunk De-Duplication */
1183 
1184  /* only create a table if we have at least one chunk to search
1185  * otherwise just make a new one.
1186  *
1187  * Support re-arranged chunks */
1188 
1189 #ifdef USE_HASH_TABLE_ACCUMULATE
1190  size_t i_table_start = i_prev;
1191  const size_t table_hash_array_len = (data_len - i_prev) / info->chunk_stride;
1192  hash_key *table_hash_array = MEM_mallocN(sizeof(*table_hash_array) * table_hash_array_len,
1193  __func__);
1194  hash_array_from_data(info, &data[i_prev], data_len - i_prev, table_hash_array);
1195 
1196  hash_accum(table_hash_array, table_hash_array_len, info->accum_steps);
1197 #else
1198  /* dummy vars */
1199  uint i_table_start = 0;
1200  hash_key *table_hash_array = NULL;
1201 #endif
1202 
1203  const uint chunk_list_reference_remaining_len = (chunk_list_reference->chunk_refs_len -
1204  chunk_list_reference_skip_len) +
1205  1;
1206  BTableRef *table_ref_stack = MEM_mallocN(
1207  chunk_list_reference_remaining_len * sizeof(BTableRef), __func__);
1208  uint table_ref_stack_n = 0;
1209 
1210  const size_t table_len = chunk_list_reference_remaining_len * BCHUNK_HASH_TABLE_MUL;
1211  BTableRef **table = MEM_callocN(table_len * sizeof(*table), __func__);
1212 
1213  /* table_make - inline
1214  * include one matching chunk, to allow for repeating values */
1215  {
1216 #ifdef USE_HASH_TABLE_ACCUMULATE
1217  const size_t hash_store_len = info->accum_read_ahead_len;
1218  hash_key *hash_store = MEM_mallocN(sizeof(hash_key) * hash_store_len, __func__);
1219 #endif
1220 
1221  const BChunkRef *cref;
1222  size_t chunk_list_reference_bytes_remaining = chunk_list_reference->total_size -
1223  chunk_list_reference_skip_bytes;
1224 
1225  if (cref_match_first) {
1226  cref = cref_match_first;
1227  chunk_list_reference_bytes_remaining += cref->link->data_len;
1228  }
1229  else {
1230  cref = chunk_list_reference->chunk_refs.first;
1231  }
1232 
1233 #ifdef USE_PARANOID_CHECKS
1234  {
1235  size_t test_bytes_len = 0;
1236  const BChunkRef *cr = cref;
1237  while (cr != chunk_list_reference_last) {
1238  test_bytes_len += cr->link->data_len;
1239  cr = cr->next;
1240  }
1241  BLI_assert(test_bytes_len == chunk_list_reference_bytes_remaining);
1242  }
1243 #endif
1244 
1245  while ((cref != chunk_list_reference_last) &&
1246  (chunk_list_reference_bytes_remaining >= info->accum_read_ahead_bytes)) {
1247  hash_key key = key_from_chunk_ref(info,
1248  cref
1249 
1251  ,
1252  hash_store,
1253  hash_store_len
1254 #endif
1255  );
1256  size_t key_index = (size_t)(key % (hash_key)table_len);
1257  BTableRef *tref_prev = table[key_index];
1258  BLI_assert(table_ref_stack_n < chunk_list_reference_remaining_len);
1259  BTableRef *tref = &table_ref_stack[table_ref_stack_n++];
1260  tref->cref = cref;
1261  tref->next = tref_prev;
1262  table[key_index] = tref;
1263 
1264  chunk_list_reference_bytes_remaining -= cref->link->data_len;
1265  cref = cref->next;
1266  }
1267 
1268  BLI_assert(table_ref_stack_n <= chunk_list_reference_remaining_len);
1269 
1270 #ifdef USE_HASH_TABLE_ACCUMULATE
1271  MEM_freeN(hash_store);
1272 #endif
1273  }
1274  /* done making the table */
1275 
1276  BLI_assert(i_prev <= data_len);
1277  for (size_t i = i_prev; i < data_len;) {
1278  /* Assumes exiting chunk isn't a match! */
1279 
1280  const BChunkRef *cref_found = table_lookup(
1281  info, table, table_len, i_table_start, data, data_len, i, table_hash_array);
1282  if (cref_found != NULL) {
1283  BLI_assert(i < data_len);
1284  if (i != i_prev) {
1285  bchunk_list_append_data_n(info, bs_mem, chunk_list, &data[i_prev], i - i_prev);
1286  i_prev = i;
1287  }
1288 
1289  /* now add the reference chunk */
1290  {
1291  BChunk *chunk_found = cref_found->link;
1292  i += chunk_found->data_len;
1293  bchunk_list_append(info, bs_mem, chunk_list, chunk_found);
1294  }
1295  i_prev = i;
1296  BLI_assert(i_prev <= data_len);
1297  ASSERT_CHUNKLIST_SIZE(chunk_list, i_prev);
1298  ASSERT_CHUNKLIST_DATA(chunk_list, data);
1299 
1300  /* its likely that the next chunk in the list will be a match, so check it! */
1301  while (!ELEM(cref_found->next, NULL, chunk_list_reference_last)) {
1302  cref_found = cref_found->next;
1303  BChunk *chunk_found = cref_found->link;
1304 
1305  if (bchunk_data_compare(chunk_found, data, data_len, i_prev)) {
1306  /* May be useful to remove table data, assuming we don't have
1307  * repeating memory where it would be useful to re-use chunks. */
1308  i += chunk_found->data_len;
1309  bchunk_list_append(info, bs_mem, chunk_list, chunk_found);
1310  /* chunk_found may be freed! */
1311  i_prev = i;
1312  BLI_assert(i_prev <= data_len);
1313  ASSERT_CHUNKLIST_SIZE(chunk_list, i_prev);
1314  ASSERT_CHUNKLIST_DATA(chunk_list, data);
1315  }
1316  else {
1317  break;
1318  }
1319  }
1320  }
1321  else {
1322  i = i + info->chunk_stride;
1323  }
1324  }
1325 
1326 #ifdef USE_HASH_TABLE_ACCUMULATE
1327  MEM_freeN(table_hash_array);
1328 #endif
1329  MEM_freeN(table);
1330  MEM_freeN(table_ref_stack);
1331 
1332  /* End Table Lookup
1333  * ---------------- */
1334  }
1335 
1336  ASSERT_CHUNKLIST_SIZE(chunk_list, i_prev);
1337  ASSERT_CHUNKLIST_DATA(chunk_list, data);
1338 
1339  /* -----------------------------------------------------------------------
1340  * No Duplicates to copy, write new chunks
1341  *
1342  * Trailing chunks, no matches found in table lookup above.
1343  * Write all new data. */
1344  if (i_prev != data_len) {
1345  bchunk_list_append_data_n(info, bs_mem, chunk_list, &data[i_prev], data_len - i_prev);
1346  i_prev = data_len;
1347  }
1348 
1349  BLI_assert(i_prev == data_len);
1350 
1351 #ifdef USE_FASTPATH_CHUNKS_LAST
1352  if (chunk_list_reference_last != NULL) {
1353  /* write chunk_list_reference_last since it hasn't been written yet */
1354  const BChunkRef *cref = chunk_list_reference_last;
1355  while (cref != NULL) {
1356  BChunk *chunk = cref->link;
1357  // BLI_assert(bchunk_data_compare(chunk, data, data_len, i_prev));
1358  i_prev += chunk->data_len;
1359  /* use simple since we assume the references chunks
1360  * have already been sized correctly. */
1361  bchunk_list_append_only(bs_mem, chunk_list, chunk);
1362  ASSERT_CHUNKLIST_DATA(chunk_list, data);
1363  cref = cref->next;
1364  }
1365  }
1366 #endif
1367 
1368 #undef data_len_original
1369 
1370  BLI_assert(i_prev == data_len_original);
1371 
1372  /* check we're the correct size and that we didn't accidentally modify the reference */
1374  ASSERT_CHUNKLIST_SIZE(chunk_list_reference, chunk_list_reference->total_size);
1375 
1376  ASSERT_CHUNKLIST_DATA(chunk_list, data);
1377 
1378  return chunk_list;
1379 }
1380 /* end private API */
1381 
1384 /* -------------------------------------------------------------------- */
1389 {
1390  BArrayStore *bs = MEM_callocN(sizeof(BArrayStore), __func__);
1391 
1392  bs->info.chunk_stride = stride;
1393  // bs->info.chunk_count = chunk_count;
1394 
1395  bs->info.chunk_byte_size = chunk_count * stride;
1396 #ifdef USE_MERGE_CHUNKS
1397  bs->info.chunk_byte_size_min = MAX2(1u, chunk_count / BCHUNK_SIZE_MIN_DIV) * stride;
1398  bs->info.chunk_byte_size_max = (chunk_count * BCHUNK_SIZE_MAX_MUL) * stride;
1399 #endif
1400 
1401 #ifdef USE_HASH_TABLE_ACCUMULATE
1403  /* Triangle number, identifying now much read-ahead we need:
1404  * https://en.wikipedia.org/wiki/Triangular_number (+ 1) */
1406  (uint)((((bs->info.accum_steps * (bs->info.accum_steps + 1))) / 2) + 1);
1408 #else
1409  bs->info.accum_read_ahead_bytes = BCHUNK_HASH_LEN * stride;
1410 #endif
1411 
1414  /* allow iteration to simplify freeing, otherwise its not needed
1415  * (we could loop over all states as an alternative). */
1417 
1418  return bs;
1419 }
1420 
1422 {
1423  /* free chunk data */
1424  {
1425  BLI_mempool_iter iter;
1426  BChunk *chunk;
1427  BLI_mempool_iternew(bs->memory.chunk, &iter);
1428  while ((chunk = BLI_mempool_iterstep(&iter))) {
1429  BLI_assert(chunk->users > 0);
1430  MEM_freeN((void *)chunk->data);
1431  }
1432  }
1433 
1434  /* free states */
1435  for (BArrayState *state = bs->states.first, *state_next; state; state = state_next) {
1436  state_next = state->next;
1437  MEM_freeN(state);
1438  }
1439 }
1440 
1442 {
1444 
1448 
1449  MEM_freeN(bs);
1450 }
1451 
1453 {
1455 
1456  BLI_listbase_clear(&bs->states);
1457 
1461 }
1462 
1465 /* -------------------------------------------------------------------- */
1470 {
1471  size_t size_accum = 0;
1472  LISTBASE_FOREACH (const BArrayState *, state, &bs->states) {
1473  size_accum += state->chunk_list->total_size;
1474  }
1475  return size_accum;
1476 }
1477 
1479 {
1480  size_t size_total = 0;
1481  BLI_mempool_iter iter;
1482  BChunk *chunk;
1483  BLI_mempool_iternew(bs->memory.chunk, &iter);
1484  while ((chunk = BLI_mempool_iterstep(&iter))) {
1485  BLI_assert(chunk->users > 0);
1486  size_total += (size_t)chunk->data_len;
1487  }
1488  return size_total;
1489 }
1490 
1493 /* -------------------------------------------------------------------- */
1498  const void *data,
1499  const size_t data_len,
1500  const BArrayState *state_reference)
1501 {
1502  /* ensure we're aligned to the stride */
1503  BLI_assert((data_len % bs->info.chunk_stride) == 0);
1504 
1505 #ifdef USE_PARANOID_CHECKS
1506  if (state_reference) {
1507  BLI_assert(BLI_findindex(&bs->states, state_reference) != -1);
1508  }
1509 #endif
1510 
1511  BChunkList *chunk_list;
1512  if (state_reference) {
1513  chunk_list = bchunk_list_from_data_merge(&bs->info,
1514  &bs->memory,
1515  (const uchar *)data,
1516  data_len,
1517  /* re-use reference chunks */
1518  state_reference->chunk_list);
1519  }
1520  else {
1521  chunk_list = bchunk_list_new(&bs->memory, data_len);
1522  bchunk_list_fill_from_array(&bs->info, &bs->memory, chunk_list, (const uchar *)data, data_len);
1523  }
1524 
1525  chunk_list->users += 1;
1526 
1527  BArrayState *state = MEM_callocN(sizeof(BArrayState), __func__);
1528  state->chunk_list = chunk_list;
1529 
1530  BLI_addtail(&bs->states, state);
1531 
1532 #ifdef USE_PARANOID_CHECKS
1533  {
1534  size_t data_test_len;
1535  void *data_test = BLI_array_store_state_data_get_alloc(state, &data_test_len);
1536  BLI_assert(data_test_len == data_len);
1537  BLI_assert(memcmp(data_test, data, data_len) == 0);
1538  MEM_freeN(data_test);
1539  }
1540 #endif
1541 
1542  return state;
1543 }
1544 
1546 {
1547 #ifdef USE_PARANOID_CHECKS
1548  BLI_assert(BLI_findindex(&bs->states, state) != -1);
1549 #endif
1550 
1551  bchunk_list_decref(&bs->memory, state->chunk_list);
1552  BLI_remlink(&bs->states, state);
1553 
1554  MEM_freeN(state);
1555 }
1556 
1558 {
1559  return state->chunk_list->total_size;
1560 }
1561 
1563 {
1564 #ifdef USE_PARANOID_CHECKS
1565  size_t data_test_len = 0;
1566  LISTBASE_FOREACH (BChunkRef *, cref, &state->chunk_list->chunk_refs) {
1567  data_test_len += cref->link->data_len;
1568  }
1569  BLI_assert(data_test_len == state->chunk_list->total_size);
1570 #endif
1571 
1572  uchar *data_step = (uchar *)data;
1573  LISTBASE_FOREACH (BChunkRef *, cref, &state->chunk_list->chunk_refs) {
1574  BLI_assert(cref->link->users > 0);
1575  memcpy(data_step, cref->link->data, cref->link->data_len);
1576  data_step += cref->link->data_len;
1577  }
1578 }
1579 
1581 {
1582  void *data = MEM_mallocN(state->chunk_list->total_size, __func__);
1584  *r_data_len = state->chunk_list->total_size;
1585  return data;
1586 }
1587 
1590 /* -------------------------------------------------------------------- */
1594 /* only for test validation */
1595 static size_t bchunk_list_size(const BChunkList *chunk_list)
1596 {
1597  size_t total_size = 0;
1598  LISTBASE_FOREACH (BChunkRef *, cref, &chunk_list->chunk_refs) {
1599  total_size += cref->link->data_len;
1600  }
1601  return total_size;
1602 }
1603 
1605 {
1606  bool ok = true;
1607 
1608  /* Check Length
1609  * ------------ */
1610 
1612  BChunkList *chunk_list = state->chunk_list;
1613  if (!(bchunk_list_size(chunk_list) == chunk_list->total_size)) {
1614  return false;
1615  }
1616 
1617  if (BLI_listbase_count(&chunk_list->chunk_refs) != (int)chunk_list->chunk_refs_len) {
1618  return false;
1619  }
1620 
1621 #ifdef USE_MERGE_CHUNKS
1622  /* ensure we merge all chunks that could be merged */
1623  if (chunk_list->total_size > bs->info.chunk_byte_size_min) {
1624  LISTBASE_FOREACH (BChunkRef *, cref, &chunk_list->chunk_refs) {
1625  if (cref->link->data_len < bs->info.chunk_byte_size_min) {
1626  return false;
1627  }
1628  }
1629  }
1630 #endif
1631  }
1632 
1633  {
1634  BLI_mempool_iter iter;
1635  BChunk *chunk;
1636  BLI_mempool_iternew(bs->memory.chunk, &iter);
1637  while ((chunk = BLI_mempool_iterstep(&iter))) {
1638  if (!(MEM_allocN_len(chunk->data) >= chunk->data_len)) {
1639  return false;
1640  }
1641  }
1642  }
1643 
1644  /* Check User Count & Lost References
1645  * ---------------------------------- */
1646  {
1647  GHashIterator gh_iter;
1648 
1649 #define GHASH_PTR_ADD_USER(gh, pt) \
1650  { \
1651  void **val; \
1652  if (BLI_ghash_ensure_p((gh), (pt), &val)) { \
1653  *((int *)val) += 1; \
1654  } \
1655  else { \
1656  *((int *)val) = 1; \
1657  } \
1658  } \
1659  ((void)0)
1660 
1661  /* count chunk_list's */
1662  GHash *chunk_list_map = BLI_ghash_ptr_new(__func__);
1663  GHash *chunk_map = BLI_ghash_ptr_new(__func__);
1664 
1665  int totrefs = 0;
1667  GHASH_PTR_ADD_USER(chunk_list_map, state->chunk_list);
1668  }
1669  GHASH_ITER (gh_iter, chunk_list_map) {
1670  const struct BChunkList *chunk_list = BLI_ghashIterator_getKey(&gh_iter);
1671  const int users = POINTER_AS_INT(BLI_ghashIterator_getValue(&gh_iter));
1672  if (!(chunk_list->users == users)) {
1673  ok = false;
1674  goto user_finally;
1675  }
1676  }
1677  if (!(BLI_mempool_len(bs->memory.chunk_list) == (int)BLI_ghash_len(chunk_list_map))) {
1678  ok = false;
1679  goto user_finally;
1680  }
1681 
1682  /* count chunk's */
1683  GHASH_ITER (gh_iter, chunk_list_map) {
1684  const struct BChunkList *chunk_list = BLI_ghashIterator_getKey(&gh_iter);
1685  LISTBASE_FOREACH (const BChunkRef *, cref, &chunk_list->chunk_refs) {
1686  GHASH_PTR_ADD_USER(chunk_map, cref->link);
1687  totrefs += 1;
1688  }
1689  }
1690  if (!(BLI_mempool_len(bs->memory.chunk) == (int)BLI_ghash_len(chunk_map))) {
1691  ok = false;
1692  goto user_finally;
1693  }
1694  if (!(BLI_mempool_len(bs->memory.chunk_ref) == totrefs)) {
1695  ok = false;
1696  goto user_finally;
1697  }
1698 
1699  GHASH_ITER (gh_iter, chunk_map) {
1700  const struct BChunk *chunk = BLI_ghashIterator_getKey(&gh_iter);
1701  const int users = POINTER_AS_INT(BLI_ghashIterator_getValue(&gh_iter));
1702  if (!(chunk->users == users)) {
1703  ok = false;
1704  goto user_finally;
1705  }
1706  }
1707 
1708 #undef GHASH_PTR_ADD_USER
1709 
1710  user_finally:
1711  BLI_ghash_free(chunk_list_map, NULL, NULL);
1712  BLI_ghash_free(chunk_map, NULL, NULL);
1713  }
1714 
1715  return ok;
1716  /* TODO: dangling pointer checks. */
1717 }
1718 
Efficient in-memory storage of multiple similar arrays.
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_INLINE
BLI_INLINE void * BLI_ghashIterator_getKey(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.h:298
BLI_INLINE void * BLI_ghashIterator_getValue(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.h:302
#define GHASH_ITER(gh_iter_, ghash_)
Definition: BLI_ghash.h:321
unsigned int BLI_ghash_len(const GHash *gh) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:705
void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition: BLI_ghash.c:863
GHash * BLI_ghash_ptr_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
BLI_INLINE bool BLI_listbase_is_empty(const struct ListBase *lb)
Definition: BLI_listbase.h:269
#define LISTBASE_FOREACH(type, var, list)
Definition: BLI_listbase.h:336
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 BLI_remlink(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition: listbase.c:100
int BLI_findindex(const struct ListBase *listbase, const void *vlink) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
int BLI_listbase_count(const struct ListBase *listbase) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void BLI_mempool_iternew(BLI_mempool *pool, BLI_mempool_iter *iter) ATTR_NONNULL()
Definition: BLI_mempool.c:498
@ BLI_MEMPOOL_ALLOW_ITER
Definition: BLI_mempool.h:107
@ BLI_MEMPOOL_NOP
Definition: BLI_mempool.h:99
void * BLI_mempool_iterstep(BLI_mempool_iter *iter) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition: BLI_mempool.c:577
void BLI_mempool_free(BLI_mempool *pool, void *addr) ATTR_NONNULL(1
int BLI_mempool_len(const BLI_mempool *pool) ATTR_NONNULL(1)
Definition: BLI_mempool.c:434
BLI_mempool * BLI_mempool_create(unsigned int esize, unsigned int elem_num, unsigned int pchunk, unsigned int flag) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL
Definition: BLI_mempool.c:253
void * BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
Definition: BLI_mempool.c:319
void BLI_mempool_destroy(BLI_mempool *pool) ATTR_NONNULL(1)
Definition: BLI_mempool.c:707
void BLI_mempool_clear(BLI_mempool *pool) ATTR_NONNULL(1)
Definition: BLI_mempool.c:702
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
unsigned char uchar
Definition: BLI_sys_types.h:70
unsigned int uint
Definition: BLI_sys_types.h:67
#define UNUSED_VARS(...)
#define UNUSED(x)
#define POINTER_AS_INT(i)
#define MAX2(a, b)
#define UNLIKELY(x)
#define ELEM(...)
#define MIN2(a, b)
_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)
static void bchunk_list_calc_trim_len(const BArrayInfo *info, const size_t data_len, size_t *r_data_trim_len, size_t *r_data_last_chunk_len)
Definition: array_store.c:506
#define BCHUNK_HASH_TABLE_MUL
Definition: array_store.c:160
static BChunk * bchunk_new_copydata(BArrayMemory *bs_mem, const uchar *data, const size_t data_len)
Definition: array_store.c:320
static hash_key key_from_chunk_ref(const BArrayInfo *info, const BChunkRef *cref, hash_key *hash_store, const size_t hash_store_len)
Definition: array_store.c:848
static BChunkList * bchunk_list_from_data_merge(const BArrayInfo *info, BArrayMemory *bs_mem, const uchar *data, const size_t data_len_original, const BChunkList *chunk_list_reference)
Definition: array_store.c:1009
static void array_store_free_data(BArrayStore *bs)
Definition: array_store.c:1421
#define USE_HASH_TABLE_ACCUMULATE
Definition: array_store.c:136
struct BArrayMemory BArrayMemory
struct BChunkRef BChunkRef
BArrayStore * BLI_array_store_create(uint stride, uint chunk_count)
Definition: array_store.c:1388
static BChunkList * bchunk_list_new(BArrayMemory *bs_mem, size_t total_size)
Definition: array_store.c:356
struct BArrayInfo BArrayInfo
static void hash_array_from_cref(const BArrayInfo *info, const BChunkRef *cref, const size_t data_len, hash_key *hash_array)
Definition: array_store.c:780
BLI_INLINE uint hash_data_single(const uchar p)
Definition: array_store.c:737
void * BLI_array_store_state_data_get_alloc(BArrayState *state, size_t *r_data_len)
Definition: array_store.c:1580
#define GHASH_PTR_ADD_USER(gh, pt)
struct BChunk BChunk
static bool bchunk_data_compare(const BChunk *chunk, const uchar *data_base, const size_t data_base_len, const size_t offset)
Definition: array_store.c:339
static void bchunk_list_fill_from_array(const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, const uchar *data, const size_t data_len)
Definition: array_store.c:680
static const BChunkRef * table_lookup(const BArrayInfo *info, BTableRef **table, const size_t table_len, const size_t i_table_start, const uchar *data, const size_t data_len, const size_t offset, const hash_key *table_hash_array)
Definition: array_store.c:899
void BLI_array_store_state_remove(BArrayStore *bs, BArrayState *state)
Definition: array_store.c:1545
#define ASSERT_CHUNKLIST_DATA(chunk_list, data)
Definition: array_store.c:408
static void bchunk_decref(BArrayMemory *bs_mem, BChunk *chunk)
Definition: array_store.c:327
static void hash_accum_single(hash_key *hash_array, const size_t hash_array_len, size_t iter_steps)
Definition: array_store.c:826
static uint hash_data(const uchar *key, size_t n)
Definition: array_store.c:743
uint64_t hash_key
Definition: array_store.c:200
static void bchunk_list_append_data_n(const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, const uchar *data, size_t data_len)
Definition: array_store.c:618
size_t BLI_array_store_calc_size_expanded_get(const BArrayStore *bs)
Definition: array_store.c:1469
#define HASH_TABLE_KEY_UNSET
Definition: array_store.c:154
void BLI_array_store_state_data_get(BArrayState *state, void *data)
Definition: array_store.c:1562
void BLI_array_store_clear(BArrayStore *bs)
Definition: array_store.c:1452
static void bchunk_list_decref(BArrayMemory *bs_mem, BChunkList *chunk_list)
Definition: array_store.c:367
static size_t bchunk_list_size(const BChunkList *chunk_list)
Definition: array_store.c:1595
#define BCHUNK_SIZE_MAX_MUL
Definition: array_store.c:184
bool BLI_array_store_is_valid(BArrayStore *bs)
Definition: array_store.c:1604
BArrayState * BLI_array_store_state_add(BArrayStore *bs, const void *data, const size_t data_len, const BArrayState *state_reference)
Definition: array_store.c:1497
#define HASH_TABLE_KEY_FALLBACK
Definition: array_store.c:155
size_t BLI_array_store_state_size_get(BArrayState *state)
Definition: array_store.c:1557
#define data_len_original
struct BChunkList BChunkList
static void bchunk_list_ensure_min_size_last(const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list)
Definition: array_store.c:412
static void hash_accum(hash_key *hash_array, const size_t hash_array_len, size_t iter_steps)
Definition: array_store.c:805
#define ASSERT_CHUNKLIST_SIZE(chunk_list, n)
Definition: array_store.c:390
static void hash_array_from_data(const BArrayInfo *info, const uchar *data_slice, const size_t data_slice_len, hash_key *hash_array)
Definition: array_store.c:758
static void bchunk_list_append_only(BArrayMemory *bs_mem, BChunkList *chunk_list, BChunk *chunk)
Definition: array_store.c:548
void BLI_array_store_destroy(BArrayStore *bs)
Definition: array_store.c:1441
static BChunk * bchunk_new(BArrayMemory *bs_mem, const uchar *data, const size_t data_len)
Definition: array_store.c:308
size_t BLI_array_store_calc_size_compacted_get(const BArrayStore *bs)
Definition: array_store.c:1478
#define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS
Definition: array_store.c:143
static void bchunk_list_append(const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, BChunk *chunk)
Definition: array_store.c:666
#define HASH_INIT
Definition: array_store.c:735
static void bchunk_list_append_data(const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, const uchar *data, const size_t data_len)
Definition: array_store.c:561
#define BCHUNK_SIZE_MIN_DIV
Definition: array_store.c:177
struct BTableRef BTableRef
int users
Definition: editfont_undo.c:76
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
size_t(* MEM_allocN_len)(const void *vmemh)
Definition: mallocn.c:26
void *(* MEM_callocN)(size_t len, const char *str)
Definition: mallocn.c:31
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
void split(const std::string &s, const char delim, std::vector< std::string > &tokens)
Definition: abc_util.cc:92
unsigned __int64 uint64_t
Definition: stdint.h:90
size_t chunk_byte_size_max
Definition: array_store.c:210
size_t accum_steps
Definition: array_store.c:214
size_t chunk_byte_size_min
Definition: array_store.c:209
size_t chunk_stride
Definition: array_store.c:203
size_t accum_read_ahead_bytes
Definition: array_store.c:212
size_t chunk_byte_size
Definition: array_store.c:207
size_t accum_read_ahead_len
Definition: array_store.c:215
BLI_mempool * chunk_list
Definition: array_store.c:220
BLI_mempool * chunk
Definition: array_store.c:222
BLI_mempool * chunk_ref
Definition: array_store.c:221
struct BArrayState * next
Definition: array_store.c:253
struct BChunkList * chunk_list
Definition: array_store.c:255
struct BArrayState * prev
Definition: array_store.c:253
BArrayMemory memory
Definition: array_store.c:233
ListBase states
Definition: array_store.c:238
BArrayInfo info
Definition: array_store.c:230
uint chunk_refs_len
Definition: array_store.c:260
ListBase chunk_refs
Definition: array_store.c:259
size_t total_size
Definition: array_store.c:261
BChunk * link
Definition: array_store.c:284
struct BChunkRef * prev
Definition: array_store.c:283
struct BChunkRef * next
Definition: array_store.c:283
const uchar * data
Definition: array_store.c:269
size_t data_len
Definition: array_store.c:270
int users
Definition: array_store.c:272
hash_key key
Definition: array_store.c:275
struct BTableRef * next
Definition: array_store.c:296
const BChunkRef * cref
Definition: array_store.c:297
void * last
Definition: DNA_listBase.h:31
void * first
Definition: DNA_listBase.h:31