Blender V5.3
array_store.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
89
90#include <algorithm>
91#include <bit>
92#include <cstdlib>
93#include <cstring>
94#include <type_traits>
95
96#include "MEM_guardedalloc.h"
97
98#include "BLI_assert.hh"
99#include "BLI_listbase.hh"
100#include "BLI_map.hh"
101#include "BLI_mempool.hh"
102#include "BLI_utildefines.hh"
103
104#include "BLI_array_store.hh" /* Own include. */
105
106#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
107
108namespace blender {
109
110struct BArrayState;
111struct BChunkList;
112struct BChunkRef;
113
114/* -------------------------------------------------------------------- */
120
127#define USE_FASTPATH_CHUNKS_FIRST
128
137#ifdef USE_FASTPATH_CHUNKS_FIRST
138# define USE_FASTPATH_CHUNKS_LAST
139#endif
140
147#define USE_ALIGN_CHUNKS_TEST
148
153#define USE_HASH_TABLE_ACCUMULATE
154
155#ifdef USE_HASH_TABLE_ACCUMULATE
156/* Number of times to propagate hashes back.
157 * Effectively a 'triangle-number'.
158 * so 3 -> 7, 4 -> 11, 5 -> 16, 6 -> 22, 7 -> 29, ... etc.
159 *
160 * \note additional steps are expensive, so avoid high values unless necessary
161 * (with low strides, between 1-4) where a low value would cause the hashes to
162 * be un-evenly distributed.
163 */
164# define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_DEFAULT 3
165# define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_32BITS 4
166# define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_16BITS 5
175# define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_8BITS 6
176#else
181# define BCHUNK_HASH_LEN 16
182#endif
183
187#define USE_HASH_TABLE_KEY_CACHE
188#ifdef USE_HASH_TABLE_KEY_CACHE
189# define HASH_TABLE_KEY_UNSET ((hash_key) - 1)
190# define HASH_TABLE_KEY_FALLBACK ((hash_key) - 2)
191#endif
192
201#define USE_HASH_TABLE_DEDUPLICATE
202
206#define BCHUNK_HASH_TABLE_MUL 3
207
219#define USE_MERGE_CHUNKS
220
221#ifdef USE_MERGE_CHUNKS
223# define BCHUNK_SIZE_MIN_DIV 8
224
232# define BCHUNK_SIZE_MAX_MUL 2
233#endif /* USE_MERGE_CHUNKS */
234
236// #define USE_VALIDATE_LIST_SIZE
237
238// #define USE_VALIDATE_LIST_DATA_PARTIAL
239
240// #define USE_PARANOID_CHECKS
241
243
244/* -------------------------------------------------------------------- */
247
249
250/* Support larger hash type for fast hashing of arrays of small data types
251 * which use a fast-path when the stride is 1.
252 *
253 * Used structs for hashing values above `uint32_t`
254 * since the output of the hash is a `uint32_t`,
255 * there isn't a significant advantage to using larger types natively. */
256
259};
262};
265};
266
267enum class HashSize : uint8_t {
268 U8 = sizeof(uint8_t),
269 U16 = sizeof(uint16_t),
270 U32 = sizeof(uint32_t),
271 U64 = sizeof(UInt64_Data),
272 U96 = sizeof(UInt96_Data),
273 U128 = sizeof(UInt128_Data),
274};
275
278 // uint chunk_count; /* UNUSED (other values are derived from this) */
279
282
283 /* Pre-calculated. */
285 /* Min/max limits (inclusive) */
293#ifdef USE_HASH_TABLE_ACCUMULATE
296#endif
297};
298
300 BLI_mempool *chunk_list; /* #BChunkList. */
301 BLI_mempool *chunk_ref; /* #BChunkRef. */
302 BLI_mempool *chunk; /* #BChunk. */
303};
304
309 /* Static. */
311
314
318 ListBaseT<BArrayState> states;
319};
320
337
340 ListBaseT<BChunkRef> chunk_refs;
345
347 int users;
348};
349
351struct BChunk {
352 const uchar *data;
353 size_t data_len;
355 int users;
356
357#ifdef USE_HASH_TABLE_KEY_CACHE
359#endif
360};
361
369
382
384
385static size_t bchunk_list_size(const BChunkList *chunk_list);
386
387/* -------------------------------------------------------------------- */
390
391static BChunk *bchunk_new(BArrayMemory *bs_mem, const uchar *data, const size_t data_len)
392{
393 BChunk *chunk = static_cast<BChunk *>(BLI_mempool_alloc(bs_mem->chunk));
394 chunk->data = data;
395 chunk->data_len = data_len;
396 chunk->users = 0;
397#ifdef USE_HASH_TABLE_KEY_CACHE
398 chunk->key = HASH_TABLE_KEY_UNSET;
399#endif
400 return chunk;
401}
402
403static BChunk *bchunk_new_copydata(BArrayMemory *bs_mem, const uchar *data, const size_t data_len)
404{
405 uchar *data_copy = MEM_new_array_uninitialized<uchar>(data_len, __func__);
406 memcpy(data_copy, data, data_len);
407 return bchunk_new(bs_mem, data_copy, data_len);
408}
409
410static void bchunk_decref(BArrayMemory *bs_mem, BChunk *chunk)
411{
412 BLI_assert(chunk->users > 0);
413 if (chunk->users == 1) {
414 MEM_delete(chunk->data);
415 BLI_mempool_free(bs_mem->chunk, chunk);
416 }
417 else {
418 chunk->users -= 1;
419 }
420}
421
423 const uchar *data_base,
424 const size_t data_base_len,
425 const size_t offset)
426{
427 BLI_assert(offset + size_t(chunk->data_len) <= data_base_len);
428 UNUSED_VARS_NDEBUG(data_base_len);
429 return (memcmp(&data_base[offset], chunk->data, chunk->data_len) == 0);
430}
431
432static bool bchunk_data_compare(const BChunk *chunk,
433 const uchar *data_base,
434 const size_t data_base_len,
435 const size_t offset)
436{
437 if (offset + size_t(chunk->data_len) <= data_base_len) {
438 return bchunk_data_compare_unchecked(chunk, data_base, data_base_len, offset);
439 }
440 return false;
441}
442
444
445/* -------------------------------------------------------------------- */
448
449static BChunkList *bchunk_list_new(BArrayMemory *bs_mem, size_t total_expanded_size)
450{
451 BChunkList *chunk_list = static_cast<BChunkList *>(BLI_mempool_alloc(bs_mem->chunk_list));
452
453 chunk_list->chunk_refs.clear_no_delete();
454 chunk_list->chunk_refs_len = 0;
455 chunk_list->total_expanded_size = total_expanded_size;
456 chunk_list->users = 0;
457 return chunk_list;
458}
459
460static void bchunk_list_decref(BArrayMemory *bs_mem, BChunkList *chunk_list)
461{
462 BLI_assert(chunk_list->users > 0);
463 if (chunk_list->users == 1) {
464 for (BChunkRef *cref = chunk_list->chunk_refs.first(), *cref_next; cref; cref = cref_next) {
465 cref_next = cref->next;
466 bchunk_decref(bs_mem, cref->link);
467 BLI_mempool_free(bs_mem->chunk_ref, cref);
468 }
469
470 BLI_mempool_free(bs_mem->chunk_list, chunk_list);
471 }
472 else {
473 chunk_list->users -= 1;
474 }
475}
476
477#ifdef USE_VALIDATE_LIST_SIZE
478# ifndef NDEBUG
479# define ASSERT_CHUNKLIST_SIZE(chunk_list, n) BLI_assert(bchunk_list_size(chunk_list) == n)
480# endif
481#endif
482#ifndef ASSERT_CHUNKLIST_SIZE
483# define ASSERT_CHUNKLIST_SIZE(chunk_list, n) (EXPR_NOP(chunk_list), EXPR_NOP(n))
484#endif
485
486#ifdef USE_VALIDATE_LIST_DATA_PARTIAL
487static size_t bchunk_list_data_check(const BChunkList *chunk_list, const uchar *data)
488{
489 size_t offset = 0;
490 for (BChunkRef &cref : chunk_list->chunk_refs) {
491 if (memcmp(&data[offset], cref.link->data, cref.link->data_len) != 0) {
492 return false;
493 }
494 offset += cref.link->data_len;
495 }
496 return true;
497}
498# define ASSERT_CHUNKLIST_DATA(chunk_list, data) \
499 BLI_assert(bchunk_list_data_check(chunk_list, data))
500#else
501# define ASSERT_CHUNKLIST_DATA(chunk_list, data) (EXPR_NOP(chunk_list), EXPR_NOP(data))
502#endif
503
504#ifdef USE_MERGE_CHUNKS
506 BArrayMemory *bs_mem,
507 BChunkList *chunk_list)
508{
509 BChunkRef *cref = chunk_list->chunk_refs.last();
510 if (cref && cref->prev) {
511 /* Both are decrefed after use (end of this block). */
512 BChunk *chunk_curr = cref->link;
513 BChunk *chunk_prev = cref->prev->link;
514
515 if (std::min(chunk_prev->data_len, chunk_curr->data_len) < info->chunk_byte_size_min) {
516 const size_t data_merge_len = chunk_prev->data_len + chunk_curr->data_len;
517 /* We could pass, but no need. */
518 if (data_merge_len <= info->chunk_byte_size_max) {
519 /* We have enough space to merge. */
520
521 /* Remove last from the linked-list. */
522 BLI_assert(chunk_list->chunk_refs.last() != chunk_list->chunk_refs.first());
523 cref->prev->next = nullptr;
524 chunk_list->chunk_refs.last_ = cref->prev;
525 chunk_list->chunk_refs_len -= 1;
526
527 uchar *data_merge = MEM_new_array_uninitialized<uchar>(data_merge_len, __func__);
528 memcpy(data_merge, chunk_prev->data, chunk_prev->data_len);
529 memcpy(&data_merge[chunk_prev->data_len], chunk_curr->data, chunk_curr->data_len);
530
531 cref->prev->link = bchunk_new(bs_mem, data_merge, data_merge_len);
532 cref->prev->link->users += 1;
533
534 BLI_mempool_free(bs_mem->chunk_ref, cref);
535 }
536 else {
537 /* If we always merge small slices, we should _almost_
538 * never end up having very large chunks.
539 * Gradual expanding on contracting will cause this.
540 *
541 * if we do, the code below works (test by setting 'BCHUNK_SIZE_MAX_MUL = 1.2') */
542
543 /* Keep chunk on the left hand side a regular size. */
544 const size_t split = info->chunk_byte_size;
545
546 /* Merge and split. */
547 const size_t data_prev_len = split;
548 const size_t data_curr_len = data_merge_len - split;
549 uchar *data_prev = MEM_new_array_uninitialized<uchar>(data_prev_len, __func__);
550 uchar *data_curr = MEM_new_array_uninitialized<uchar>(data_curr_len, __func__);
551
552 if (data_prev_len <= chunk_prev->data_len) {
553 const size_t data_curr_shrink_len = chunk_prev->data_len - data_prev_len;
554
555 /* Setup 'data_prev'. */
556 memcpy(data_prev, chunk_prev->data, data_prev_len);
557
558 /* Setup 'data_curr'. */
559 memcpy(data_curr, &chunk_prev->data[data_prev_len], data_curr_shrink_len);
560 memcpy(&data_curr[data_curr_shrink_len], chunk_curr->data, chunk_curr->data_len);
561 }
562 else {
563 BLI_assert(data_curr_len <= chunk_curr->data_len);
564 BLI_assert(data_prev_len >= chunk_prev->data_len);
565
566 const size_t data_prev_grow_len = data_prev_len - chunk_prev->data_len;
567
568 /* Setup 'data_prev'. */
569 memcpy(data_prev, chunk_prev->data, chunk_prev->data_len);
570 memcpy(&data_prev[chunk_prev->data_len], chunk_curr->data, data_prev_grow_len);
571
572 /* Setup 'data_curr'. */
573 memcpy(data_curr, &chunk_curr->data[data_prev_grow_len], data_curr_len);
574 }
575
576 cref->prev->link = bchunk_new(bs_mem, data_prev, data_prev_len);
577 cref->prev->link->users += 1;
578
579 cref->link = bchunk_new(bs_mem, data_curr, data_curr_len);
580 cref->link->users += 1;
581 }
582
583 /* Free zero users. */
584 bchunk_decref(bs_mem, chunk_curr);
585 bchunk_decref(bs_mem, chunk_prev);
586 }
587 }
588}
589#endif /* USE_MERGE_CHUNKS */
590
599static void bchunk_list_calc_trim_len(const BArrayInfo *info,
600 const size_t data_len,
601 size_t *r_data_trim_len,
602 size_t *r_data_last_chunk_len)
603{
604 size_t data_last_chunk_len = 0;
605 size_t data_trim_len = data_len;
606
607#ifdef USE_MERGE_CHUNKS
608 /* Avoid creating too-small chunks more efficient than merging after. */
609 if (data_len > info->chunk_byte_size) {
610 data_last_chunk_len = (data_trim_len % info->chunk_byte_size);
611 data_trim_len = data_trim_len - data_last_chunk_len;
612 if (data_last_chunk_len) {
613 if (data_last_chunk_len < info->chunk_byte_size_min) {
614 /* May be zero and that's OK. */
615 data_trim_len -= info->chunk_byte_size;
616 data_last_chunk_len += info->chunk_byte_size;
617 }
618 }
619 }
620 else {
621 data_trim_len = 0;
622 data_last_chunk_len = data_len;
623 }
624
625 BLI_assert((data_trim_len == 0) || (data_trim_len >= info->chunk_byte_size));
626#else
627 data_last_chunk_len = (data_trim_len % info->chunk_byte_size);
628 data_trim_len = data_trim_len - data_last_chunk_len;
629#endif
630
631 BLI_assert(data_trim_len + data_last_chunk_len == data_len);
632
633 *r_data_trim_len = data_trim_len;
634 *r_data_last_chunk_len = data_last_chunk_len;
635}
636
640static void bchunk_list_append_only(BArrayMemory *bs_mem, BChunkList *chunk_list, BChunk *chunk)
641{
642 BChunkRef *cref = static_cast<BChunkRef *>(BLI_mempool_alloc(bs_mem->chunk_ref));
643 BLI_addtail(&chunk_list->chunk_refs, cref);
644 cref->link = chunk;
645 chunk_list->chunk_refs_len += 1;
646 chunk->users += 1;
647}
648
653static void bchunk_list_append_data(const BArrayInfo *info,
654 BArrayMemory *bs_mem,
655 BChunkList *chunk_list,
656 const uchar *data,
657 const size_t data_len)
658{
659 BLI_assert(data_len != 0);
660
661#ifdef USE_MERGE_CHUNKS
662 BLI_assert(data_len <= info->chunk_byte_size_max);
663
664 if (!chunk_list->chunk_refs.is_empty()) {
665 BChunkRef *cref = chunk_list->chunk_refs.last();
666 BChunk *chunk_prev = cref->link;
667
668 if (std::min(chunk_prev->data_len, data_len) < info->chunk_byte_size_min) {
669 const size_t data_merge_len = chunk_prev->data_len + data_len;
670 /* Re-allocate for single user. */
671 if (cref->link->users == 1) {
672 uchar *data_merge = static_cast<uchar *>(
673 MEM_realloc_uninitialized((void *)cref->link->data, data_merge_len));
674 memcpy(&data_merge[chunk_prev->data_len], data, data_len);
675 cref->link->data = data_merge;
676 cref->link->data_len = data_merge_len;
677 }
678 else {
679 uchar *data_merge = MEM_new_array_uninitialized<uchar>(data_merge_len, __func__);
680 memcpy(data_merge, chunk_prev->data, chunk_prev->data_len);
681 memcpy(&data_merge[chunk_prev->data_len], data, data_len);
682 cref->link = bchunk_new(bs_mem, data_merge, data_merge_len);
683 cref->link->users += 1;
684 bchunk_decref(bs_mem, chunk_prev);
685 }
686 return;
687 }
688 }
689#else
690 UNUSED_VARS(info);
691#endif /* USE_MERGE_CHUNKS */
692
693 BChunk *chunk = bchunk_new_copydata(bs_mem, data, data_len);
694 bchunk_list_append_only(bs_mem, chunk_list, chunk);
695
696 /* Don't run this, instead preemptively avoid creating a chunk only to merge it (above). */
697#if 0
698# ifdef USE_MERGE_CHUNKS
699 bchunk_list_ensure_min_size_last(info, bs_mem, chunk_list);
700# endif
701#endif
702}
703
711static void bchunk_list_append_data_n(const BArrayInfo *info,
712 BArrayMemory *bs_mem,
713 BChunkList *chunk_list,
714 const uchar *data,
715 size_t data_len)
716{
717 size_t data_trim_len, data_last_chunk_len;
718 bchunk_list_calc_trim_len(info, data_len, &data_trim_len, &data_last_chunk_len);
719
720 if (data_trim_len != 0) {
721 size_t i_prev;
722
723 {
724 const size_t i = info->chunk_byte_size;
725 bchunk_list_append_data(info, bs_mem, chunk_list, data, i);
726 i_prev = i;
727 }
728
729 while (i_prev != data_trim_len) {
730 const size_t i = i_prev + info->chunk_byte_size;
731 BChunk *chunk = bchunk_new_copydata(bs_mem, &data[i_prev], i - i_prev);
732 bchunk_list_append_only(bs_mem, chunk_list, chunk);
733 i_prev = i;
734 }
735
736 if (data_last_chunk_len) {
737 BChunk *chunk = bchunk_new_copydata(bs_mem, &data[i_prev], data_last_chunk_len);
738 bchunk_list_append_only(bs_mem, chunk_list, chunk);
739 // i_prev = data_len; /* UNUSED */
740 }
741 }
742 else {
743 /* If we didn't write any chunks previously, we may need to merge with the last. */
744 if (data_last_chunk_len) {
745 bchunk_list_append_data(info, bs_mem, chunk_list, data, data_last_chunk_len);
746 // i_prev = data_len; /* UNUSED */
747 }
748 }
749
750#ifdef USE_MERGE_CHUNKS
751 if (data_len > info->chunk_byte_size) {
752 BLI_assert((chunk_list->chunk_refs.last())->link->data_len >= info->chunk_byte_size_min);
753 }
754#endif
755}
756
757static void bchunk_list_append(const BArrayInfo *info,
758 BArrayMemory *bs_mem,
759 BChunkList *chunk_list,
760 BChunk *chunk)
761{
762 bchunk_list_append_only(bs_mem, chunk_list, chunk);
763
764#ifdef USE_MERGE_CHUNKS
765 bchunk_list_ensure_min_size_last(info, bs_mem, chunk_list);
766#else
767 UNUSED_VARS(info);
768#endif
769}
770
772 BArrayMemory *bs_mem,
773 BChunkList *chunk_list,
774 const uchar *data,
775 const size_t data_len)
776{
777 BLI_assert(chunk_list->chunk_refs.is_empty());
778
779 size_t data_trim_len, data_last_chunk_len;
780 bchunk_list_calc_trim_len(info, data_len, &data_trim_len, &data_last_chunk_len);
781
782 size_t i_prev = 0;
783 while (i_prev != data_trim_len) {
784 const size_t i = i_prev + info->chunk_byte_size;
785 BChunk *chunk = bchunk_new_copydata(bs_mem, &data[i_prev], i - i_prev);
786 bchunk_list_append_only(bs_mem, chunk_list, chunk);
787 i_prev = i;
788 }
789
790 if (data_last_chunk_len) {
791 BChunk *chunk = bchunk_new_copydata(bs_mem, &data[i_prev], data_last_chunk_len);
792 bchunk_list_append_only(bs_mem, chunk_list, chunk);
793 // i_prev = data_len;
794 }
795
796#ifdef USE_MERGE_CHUNKS
797 if (data_len > info->chunk_byte_size) {
798 BLI_assert((chunk_list->chunk_refs.last())->link->data_len >= info->chunk_byte_size_min);
799 }
800#endif
801
802 /* Works but better avoid redundant re-allocation. */
803#if 0
804# ifdef USE_MERGE_CHUNKS
805 bchunk_list_ensure_min_size_last(info, bs_mem, chunk_list);
806# endif
807#endif
808
809 ASSERT_CHUNKLIST_SIZE(chunk_list, data_len);
810 ASSERT_CHUNKLIST_DATA(chunk_list, data);
811}
812
814
815/*
816 * Internal Table Lookup Functions.
817 */
818
819/* -------------------------------------------------------------------- */
841
842#define HASH_INIT (5381)
843
849#define HASH_VALUE_IMPL_ADD_BYTES(h, value) \
850 { \
851 h = hash_key(int32_t((h << 5) + h) + (value)); \
852 } \
853 ((void)0)
854
855#define HASH_VALUE_IMPL_ADD(h, value) \
856 { \
857 h = std::rotl(h, 5) + (value); \
858 } \
859 ((void)0)
860
864template<typename T> BLI_INLINE void hash_value_generic(hash_key &h, const T &value)
865{
866 static_assert(std::is_same<T, uint8_t>() || std::is_same<T, uint16_t>() ||
867 std::is_same<T, uint32_t>() || std::is_same<T, UInt64_Data>() ||
868 std::is_same<T, UInt96_Data>() || std::is_same<T, UInt128_Data>());
869
870 if constexpr (std::is_same_v<T, uint8_t>) {
872 }
873 else if constexpr (std::is_same_v<T, uint16_t>) {
874 HASH_VALUE_IMPL_ADD(h, value);
875 }
876 else if constexpr (std::is_same_v<T, uint32_t>) {
877 HASH_VALUE_IMPL_ADD(h, value);
878 }
879 else if constexpr (std::is_same_v<T, UInt64_Data>) {
880 h ^= value.u0;
881 HASH_VALUE_IMPL_ADD(h, value.u1);
882 }
883 else if constexpr (std::is_same_v<T, UInt96_Data>) {
884 h += value.u0;
885 h ^= value.u1;
886 HASH_VALUE_IMPL_ADD(h, value.u2);
887 }
888 else if constexpr (std::is_same_v<T, UInt128_Data>) {
889 h += value.u0;
890 h ^= value.u1;
891 h += value.u2;
892 HASH_VALUE_IMPL_ADD(h, value.u3);
893 }
894 else {
896 }
897}
898
902template<typename T> BLI_INLINE hash_key hash_data_single_generic(const T &value)
903{
905 hash_value_generic(h, value);
906 return h;
907}
908
912template<typename T> static hash_key hash_data_generic(const T *data, size_t data_len)
913{
915 for (size_t i = 0; i < data_len; i++) {
917 }
918 return h;
919}
920
921#undef HASH_INIT
922
923#ifdef USE_HASH_TABLE_ACCUMULATE
924
928template<typename T>
929static void hash_array_from_data_generic(const size_t stride,
930 const T *data_slice,
931 const size_t data_slice_len,
932 hash_key *hash_array)
933{
934 if (stride == 1) {
935 /* Fast-path for single element per stride. */
936 for (size_t i = 0; i < data_slice_len; i++) {
937 hash_array[i] = hash_data_single_generic(data_slice[i]);
938 }
939 }
940 else {
941 /* Multiple elements per stride. */
942 for (size_t i = 0, i_step = 0; i_step < data_slice_len; i++, i_step += stride) {
943 hash_array[i] = hash_data_generic(&data_slice[i_step], stride);
944 }
945 }
946}
947
948static void hash_array_from_data(const BArrayInfo *info,
949 const uchar *data_slice,
950 const size_t data_slice_len,
951 hash_key *hash_array)
952{
953 /* Dispatch based on `hash_size` for optimized hashing. */
954 BLI_assert((data_slice_len % size_t(info->hash_size)) == 0);
955
956# define HASH_ARRAY_FROM_DATA_GENERIC(ty) \
957 { \
958 const ty *data_slice_typed = reinterpret_cast<const ty *>(data_slice); \
959 hash_array_from_data_generic(info->chunk_stride / sizeof(*data_slice_typed), \
960 data_slice_typed, \
961 data_slice_len / sizeof(*data_slice_typed), \
962 hash_array); \
963 } \
964 ((void)0)
965
966 switch (info->hash_size) {
967 case HashSize::U8: {
969 break;
970 }
971 case HashSize::U16: {
973 break;
974 }
975 case HashSize::U32: {
977 break;
978 }
979 case HashSize::U64: {
981 break;
982 }
983 case HashSize::U96: {
985 break;
986 }
987 case HashSize::U128: {
989 break;
990 }
991 }
992# undef HASH_ARRAY_FROM_DATA_GENERIC
993}
994
999static void hash_array_from_cref(const BArrayInfo *info,
1000 const BChunkRef *cref,
1001 const size_t data_len,
1002 hash_key *hash_array)
1003{
1004 const size_t hash_array_len = data_len / info->chunk_stride;
1005 size_t i = 0;
1006 do {
1007 size_t i_next = hash_array_len - i;
1008 size_t data_trim_len = i_next * info->chunk_stride;
1009 if (data_trim_len > cref->link->data_len) {
1010 data_trim_len = cref->link->data_len;
1011 i_next = data_trim_len / info->chunk_stride;
1012 }
1013 BLI_assert(data_trim_len <= cref->link->data_len);
1014 hash_array_from_data(info, cref->link->data, data_trim_len, &hash_array[i]);
1015 i += i_next;
1016 cref = cref->next;
1017 } while ((i < hash_array_len) && (cref != nullptr));
1018
1019 /* If this isn't equal, the caller didn't properly check
1020 * that there was enough data left in all chunks. */
1021 BLI_assert(i == hash_array_len);
1022}
1023
1024BLI_INLINE void hash_accum_impl(hash_key *hash_array, const size_t i_dst, const size_t i_ahead)
1025{
1026 /* Tested to give good results when accumulating unique values from an array of booleans.
1027 * (least unused cells in the `BTableRef **table`). */
1028 BLI_assert(i_dst < i_ahead);
1029 hash_array[i_dst] = std::rotl(hash_array[i_dst], 3) + hash_array[i_ahead];
1030}
1031
1032static void hash_accum(hash_key *hash_array, const size_t hash_array_len, size_t iter_steps)
1033{
1034 /* _very_ unlikely, can happen if you select a chunk-size of 1 for example. */
1035 if (iter_steps > hash_array_len) [[unlikely]] {
1036 iter_steps = hash_array_len;
1037 }
1038
1039 const size_t hash_array_search_len = hash_array_len - iter_steps;
1040 while (iter_steps != 0) {
1041 const size_t hash_offset = iter_steps;
1042 for (size_t i = 0; i < hash_array_search_len; i++) {
1043 hash_accum_impl(hash_array, i, i + hash_offset);
1044 }
1045 iter_steps -= 1;
1046 }
1047}
1048
1053static void hash_accum_single(hash_key *hash_array, const size_t hash_array_len, size_t iter_steps)
1054{
1055 BLI_assert(iter_steps <= hash_array_len);
1056 if (!(iter_steps <= hash_array_len)) [[unlikely]] {
1057 /* While this shouldn't happen, avoid crashing. */
1058 iter_steps = hash_array_len;
1059 }
1060 /* We can increase this value each step to avoid accumulating quite as much
1061 * while getting the same results as hash_accum. */
1062 size_t iter_steps_sub = iter_steps;
1063
1064 while (iter_steps != 0) {
1065 const size_t hash_array_search_len = hash_array_len - iter_steps_sub;
1066 const size_t hash_offset = iter_steps;
1067 for (uint i = 0; i < hash_array_search_len; i++) {
1068 hash_accum_impl(hash_array, i, i + hash_offset);
1069 }
1070 iter_steps -= 1;
1071 iter_steps_sub += iter_steps;
1072 }
1073}
1074
1076 const BChunkRef *cref,
1077 /* Avoid reallocating each time. */
1078 hash_key *hash_store,
1079 const size_t hash_store_len)
1080{
1081 /* In C, will fill in a reusable array. */
1082 BChunk *chunk = cref->link;
1083 BLI_assert((info->accum_read_ahead_bytes * info->chunk_stride) != 0);
1084
1085 if (info->accum_read_ahead_bytes <= chunk->data_len) {
1086 hash_key key;
1087
1088# ifdef USE_HASH_TABLE_KEY_CACHE
1089 key = chunk->key;
1090 if (key != HASH_TABLE_KEY_UNSET) {
1091 /* Using key cache!
1092 * avoids calculating every time. */
1093 }
1094 else {
1095 hash_array_from_cref(info, cref, info->accum_read_ahead_bytes, hash_store);
1096 hash_accum_single(hash_store, hash_store_len, info->accum_steps);
1097 key = hash_store[0];
1098
1099 /* Cache the key. */
1100 if (key == HASH_TABLE_KEY_UNSET) [[unlikely]] {
1102 }
1103 chunk->key = key;
1104 }
1105# else
1106 hash_array_from_cref(info, cref, info->accum_read_ahead_bytes, hash_store);
1107 hash_accum_single(hash_store, hash_store_len, info->accum_steps);
1108 key = hash_store[0];
1109# endif
1110 return key;
1111 }
1112 /* Corner case - we're too small, calculate the key each time. */
1113
1114 hash_array_from_cref(info, cref, info->accum_read_ahead_bytes, hash_store);
1115 hash_accum_single(hash_store, hash_store_len, info->accum_steps);
1116 hash_key key = hash_store[0];
1117
1118# ifdef USE_HASH_TABLE_KEY_CACHE
1119 if (key == HASH_TABLE_KEY_UNSET) [[unlikely]] {
1121 }
1122# endif
1123 return key;
1124}
1125
1126static const BChunkRef *table_lookup(const BArrayInfo *info,
1127 BTableRef **table,
1128 const size_t table_len,
1129 const size_t i_table_start,
1130 const uchar *data,
1131 const size_t data_len,
1132 const size_t offset,
1133 const hash_key *table_hash_array)
1134{
1135 const hash_key key = table_hash_array[((offset - i_table_start) / info->chunk_stride)];
1136 const uint key_index = uint(key % hash_key(table_len));
1137 const BTableRef *tref = table[key_index];
1138 if (tref != nullptr) {
1139 const size_t size_left = data_len - offset;
1140 do {
1141 const BChunkRef *cref = tref->cref;
1142# ifdef USE_HASH_TABLE_KEY_CACHE
1143 if (cref->link->key == key)
1144# endif
1145 {
1146 const BChunk *chunk_test = cref->link;
1147 if (chunk_test->data_len <= size_left) {
1148 if (bchunk_data_compare_unchecked(chunk_test, data, data_len, offset)) {
1149 /* We could remove the chunk from the table, to avoid multiple hits. */
1150 return cref;
1151 }
1152 }
1153 }
1154 } while ((tref = tref->next));
1155 }
1156 return nullptr;
1157}
1158
1159#else /* USE_HASH_TABLE_ACCUMULATE */
1160
1161/* NON USE_HASH_TABLE_ACCUMULATE code (simply hash each chunk). */
1162
1166static hash_key hash_data(const uchar *data, const size_t data_len, HashSize hash_size)
1167{
1168 const size_t data_len_for_type = data_len / size_t(hash_size);
1169 switch (hash_size) {
1170 case HashSize::U8: {
1171 return hash_data_generic(data, data_len);
1172 }
1173 case HashSize::U16: {
1174 return hash_data_generic(reinterpret_cast<const uint16_t *>(data), data_len_for_type);
1175 }
1176 case HashSize::U32: {
1177 return hash_data_generic(reinterpret_cast<const uint32_t *>(data), data_len_for_type);
1178 }
1179 case HashSize::U64: {
1180 return hash_data_generic(reinterpret_cast<const UInt64_Data *>(data), data_len_for_type);
1181 }
1182 case HashSize::U96: {
1183 return hash_data_generic(reinterpret_cast<const UInt96_Data *>(data), data_len_for_type);
1184 }
1185 case HashSize::U128: {
1186 return hash_data_generic(reinterpret_cast<const UInt128_Data *>(data), data_len_for_type);
1187 }
1188 }
1190 return 0;
1191}
1192
1193static hash_key key_from_chunk_ref(const BArrayInfo *info, const BChunkRef *cref)
1194{
1195 hash_key key;
1196 BChunk *chunk = cref->link;
1197 const size_t data_hash_len = std::min(chunk->data_len, BCHUNK_HASH_LEN * info->chunk_stride);
1198
1199# ifdef USE_HASH_TABLE_KEY_CACHE
1200 key = chunk->key;
1201 if (key != HASH_TABLE_KEY_UNSET) {
1202 /* Using key cache!
1203 * avoids calculating every time. */
1204 }
1205 else {
1206 /* Cache the key. */
1207 key = hash_data(chunk->data, data_hash_len, info->hash_size);
1208 if (key == HASH_TABLE_KEY_UNSET) {
1210 }
1211 chunk->key = key;
1212 }
1213# else
1214 key = hash_data(chunk->data, data_hash_len, info->hash_size);
1215# endif
1216
1217 return key;
1218}
1219
1220static const BChunkRef *table_lookup(const BArrayInfo *info,
1221 BTableRef **table,
1222 const size_t table_len,
1223 const uint /*i_table_start*/,
1224 const uchar *data,
1225 const size_t data_len,
1226 const size_t offset,
1227 const hash_key * /*table_hash_array*/)
1228{
1229 const size_t data_hash_len = BCHUNK_HASH_LEN * info->chunk_stride; /* TODO: cache. */
1230
1231 const size_t size_left = data_len - offset;
1232 const hash_key key = hash_data(
1233 &data[offset], std::min(data_hash_len, size_left), info->hash_size);
1234 const uint key_index = uint(key % (hash_key)table_len);
1235 for (BTableRef *tref = table[key_index]; tref; tref = tref->next) {
1236 const BChunkRef *cref = tref->cref;
1237# ifdef USE_HASH_TABLE_KEY_CACHE
1238 if (cref->link->key == key)
1239# endif
1240 {
1241 BChunk *chunk_test = cref->link;
1242 if (chunk_test->data_len <= size_left) {
1243 if (bchunk_data_compare_unchecked(chunk_test, data, data_len, offset)) {
1244 /* We could remove the chunk from the table, to avoid multiple hits. */
1245 return cref;
1246 }
1247 }
1248 }
1249 }
1250 return nullptr;
1251}
1252
1253#endif /* USE_HASH_TABLE_ACCUMULATE */
1254
1255/* End Table Lookup
1256 * ---------------- */
1257
1259
1260/* -------------------------------------------------------------------- */
1263
1271 BArrayMemory *bs_mem,
1272 const uchar *data,
1273 const size_t data_len_original,
1274 const BChunkList *chunk_list_reference)
1275{
1276 ASSERT_CHUNKLIST_SIZE(chunk_list_reference, chunk_list_reference->total_expanded_size);
1277
1278 /* -----------------------------------------------------------------------
1279 * Fast-Path for exact match
1280 * Check for exact match, if so, return the current list.
1281 */
1282
1283 const BChunkRef *cref_match_first = nullptr;
1284
1285 uint chunk_list_reference_skip_len = 0;
1286 size_t chunk_list_reference_skip_bytes = 0;
1287 size_t i_prev = 0;
1288
1289#ifdef USE_FASTPATH_CHUNKS_FIRST
1290 {
1291 bool full_match = true;
1292
1293 const BChunkRef *cref = chunk_list_reference->chunk_refs.first();
1294 while (i_prev < data_len_original) {
1295 if (cref != nullptr && bchunk_data_compare(cref->link, data, data_len_original, i_prev)) {
1296 cref_match_first = cref;
1297 chunk_list_reference_skip_len += 1;
1298 chunk_list_reference_skip_bytes += cref->link->data_len;
1299 i_prev += cref->link->data_len;
1300 cref = cref->next;
1301 }
1302 else {
1303 full_match = false;
1304 break;
1305 }
1306 }
1307
1308 if (full_match) {
1309 if (chunk_list_reference->total_expanded_size == data_len_original) {
1310 return const_cast<BChunkList *>(chunk_list_reference);
1311 }
1312 }
1313 }
1314
1315 /* End Fast-Path (first)
1316 * --------------------- */
1317
1318#endif /* USE_FASTPATH_CHUNKS_FIRST */
1319
1320 /* Copy until we have a mismatch. */
1321 BChunkList *chunk_list = bchunk_list_new(bs_mem, data_len_original);
1322 if (cref_match_first != nullptr) {
1323 size_t chunk_size_step = 0;
1324 const BChunkRef *cref = chunk_list_reference->chunk_refs.first();
1325 while (true) {
1326 BChunk *chunk = cref->link;
1327 chunk_size_step += chunk->data_len;
1328 bchunk_list_append_only(bs_mem, chunk_list, chunk);
1329 ASSERT_CHUNKLIST_SIZE(chunk_list, chunk_size_step);
1330 ASSERT_CHUNKLIST_DATA(chunk_list, data);
1331 if (cref == cref_match_first) {
1332 break;
1333 }
1334 cref = cref->next;
1335 }
1336 /* Happens when bytes are removed from the end of the array. */
1337 if (chunk_size_step == data_len_original) {
1338 return chunk_list;
1339 }
1340
1341 i_prev = chunk_size_step;
1342 }
1343 else {
1344 i_prev = 0;
1345 }
1346
1347 /* ------------------------------------------------------------------------
1348 * Fast-Path for end chunks
1349 *
1350 * Check for trailing chunks.
1351 */
1352
1353 /* In this case use 'chunk_list_reference_last' to define the last index
1354 * `index_match_last = -1`. */
1355
1356 /* Warning, from now on don't use len(data) since we want to ignore chunks already matched. */
1357 size_t data_len = data_len_original;
1358#define data_len_original invalid_usage
1359#ifdef data_len_original
1360 /* Quiet warning. */
1361#endif
1362
1363 const BChunkRef *chunk_list_reference_last = nullptr;
1364
1365#ifdef USE_FASTPATH_CHUNKS_LAST
1366 if (!chunk_list_reference->chunk_refs.is_empty()) {
1367 const BChunkRef *cref = chunk_list_reference->chunk_refs.last();
1368 while ((cref->prev != nullptr) && (cref != cref_match_first) &&
1369 (cref->link->data_len <= data_len - i_prev))
1370 {
1371 const BChunk *chunk_test = cref->link;
1372 size_t offset = data_len - chunk_test->data_len;
1373 if (bchunk_data_compare(chunk_test, data, data_len, offset)) {
1374 data_len = offset;
1375 chunk_list_reference_last = cref;
1376 chunk_list_reference_skip_len += 1;
1377 chunk_list_reference_skip_bytes += cref->link->data_len;
1378 cref = cref->prev;
1379 }
1380 else {
1381 break;
1382 }
1383 }
1384 }
1385
1386 /* End Fast-Path (last)
1387 * -------------------- */
1388#endif /* USE_FASTPATH_CHUNKS_LAST */
1389
1390 /* -----------------------------------------------------------------------
1391 * Check for aligned chunks
1392 *
1393 * This saves a lot of searching, so use simple heuristics to detect aligned arrays.
1394 * (may need to tweak exact method).
1395 */
1396
1397 bool use_aligned = false;
1398
1399#ifdef USE_ALIGN_CHUNKS_TEST
1400 if (chunk_list->total_expanded_size == chunk_list_reference->total_expanded_size) {
1401 /* If we're already a quarter aligned. */
1402 if (data_len - i_prev <= chunk_list->total_expanded_size / 4) {
1403 use_aligned = true;
1404 }
1405 else {
1406 /* TODO: walk over chunks and check if some arbitrary amount align. */
1407 }
1408 }
1409#endif /* USE_ALIGN_CHUNKS_TEST */
1410
1411 /* End Aligned Chunk Case
1412 * ----------------------- */
1413
1414 if (use_aligned) {
1415 /* Copy matching chunks, creates using the same 'layout' as the reference. */
1416 const BChunkRef *cref = cref_match_first ? cref_match_first->next :
1417 static_cast<const BChunkRef *>(
1418 chunk_list_reference->chunk_refs.first_);
1419 while (i_prev != data_len) {
1420 const size_t i = i_prev + cref->link->data_len;
1421 BLI_assert(i != i_prev);
1422
1423 if ((cref != chunk_list_reference_last) &&
1424 bchunk_data_compare(cref->link, data, data_len, i_prev))
1425 {
1426 bchunk_list_append(info, bs_mem, chunk_list, cref->link);
1427 ASSERT_CHUNKLIST_SIZE(chunk_list, i);
1428 ASSERT_CHUNKLIST_DATA(chunk_list, data);
1429 }
1430 else {
1431 bchunk_list_append_data(info, bs_mem, chunk_list, &data[i_prev], i - i_prev);
1432 ASSERT_CHUNKLIST_SIZE(chunk_list, i);
1433 ASSERT_CHUNKLIST_DATA(chunk_list, data);
1434 }
1435
1436 cref = cref->next;
1437
1438 i_prev = i;
1439 }
1440 }
1441 else if ((data_len - i_prev >= info->chunk_byte_size) &&
1442 (chunk_list_reference->chunk_refs_len >= chunk_list_reference_skip_len) &&
1443 (chunk_list_reference->chunk_refs.first() != nullptr))
1444 {
1445
1446 /* --------------------------------------------------------------------
1447 * Non-Aligned Chunk De-Duplication. */
1448
1449 /* Only create a table if we have at least one chunk to search
1450 * otherwise just make a new one.
1451 *
1452 * Support re-arranged chunks. */
1453
1454#ifdef USE_HASH_TABLE_ACCUMULATE
1455 size_t i_table_start = i_prev;
1456 const size_t table_hash_array_len = (data_len - i_prev) / info->chunk_stride;
1457 hash_key *table_hash_array = MEM_new_array_uninitialized<hash_key>(table_hash_array_len,
1458 __func__);
1459 hash_array_from_data(info, &data[i_prev], data_len - i_prev, table_hash_array);
1460
1461 hash_accum(table_hash_array, table_hash_array_len, info->accum_steps);
1462#else
1463 /* Dummy vars. */
1464 uint i_table_start = 0;
1465 hash_key *table_hash_array = nullptr;
1466#endif
1467
1468 const uint chunk_list_reference_remaining_len = (chunk_list_reference->chunk_refs_len -
1469 chunk_list_reference_skip_len) +
1470 1;
1472 chunk_list_reference_remaining_len, __func__);
1473 uint table_ref_stack_n = 0;
1474
1475 const size_t table_len = chunk_list_reference_remaining_len * BCHUNK_HASH_TABLE_MUL;
1476 BTableRef **table = MEM_new_array_zeroed<BTableRef *>(table_len, __func__);
1477
1478 /* Table_make - inline
1479 * include one matching chunk, to allow for repeating values. */
1480 {
1481#ifdef USE_HASH_TABLE_ACCUMULATE
1482 const size_t hash_store_len = info->accum_read_ahead_len;
1483 hash_key *hash_store = MEM_new_array_uninitialized<hash_key>(hash_store_len, __func__);
1484#endif
1485
1486 const BChunkRef *cref;
1487 size_t chunk_list_reference_bytes_remaining = chunk_list_reference->total_expanded_size -
1488 chunk_list_reference_skip_bytes;
1489
1490 if (cref_match_first) {
1491 cref = cref_match_first;
1492 chunk_list_reference_bytes_remaining += cref->link->data_len;
1493 }
1494 else {
1495 cref = chunk_list_reference->chunk_refs.first();
1496 }
1497
1498#ifdef USE_PARANOID_CHECKS
1499 {
1500 size_t test_bytes_len = 0;
1501 const BChunkRef *cr = cref;
1502 while (cr != chunk_list_reference_last) {
1503 test_bytes_len += cr->link->data_len;
1504 cr = cr->next;
1505 }
1506 BLI_assert(test_bytes_len == chunk_list_reference_bytes_remaining);
1507 }
1508#endif
1509
1510 while ((cref != chunk_list_reference_last) &&
1511 (chunk_list_reference_bytes_remaining >= info->accum_read_ahead_bytes))
1512 {
1513 hash_key key = key_from_chunk_ref(info,
1514 cref
1515
1517 ,
1518 hash_store,
1519 hash_store_len
1520#endif
1521 );
1522 const uint key_index = uint(key % hash_key(table_len));
1523 BTableRef *tref_prev = table[key_index];
1524 BLI_assert(table_ref_stack_n < chunk_list_reference_remaining_len);
1525#ifdef USE_HASH_TABLE_DEDUPLICATE
1526 bool is_duplicate = false;
1527 if (tref_prev) {
1528 const BChunk *chunk_a = cref->link;
1529 const BTableRef *tref = tref_prev;
1530 do {
1531 /* Not an error, it just isn't expected the links are ever shared. */
1532 BLI_assert(tref->cref != cref);
1533 const BChunk *chunk_b = tref->cref->link;
1534# ifdef USE_HASH_TABLE_KEY_CACHE
1535 if (key == chunk_b->key)
1536# endif
1537 {
1538 if (chunk_a != chunk_b) {
1539 if (chunk_a->data_len == chunk_b->data_len) {
1540 if (memcmp(chunk_a->data, chunk_b->data, chunk_a->data_len) == 0) {
1541 is_duplicate = true;
1542 break;
1543 }
1544 }
1545 }
1546 }
1547 } while ((tref = tref->next));
1548 }
1549
1550 if (!is_duplicate)
1551#endif /* USE_HASH_TABLE_DEDUPLICATE */
1552 {
1553 BTableRef *tref = &table_ref_stack[table_ref_stack_n++];
1554 tref->cref = cref;
1555 tref->next = tref_prev;
1556 table[key_index] = tref;
1557 }
1558
1559 chunk_list_reference_bytes_remaining -= cref->link->data_len;
1560 cref = cref->next;
1561 }
1562
1563 BLI_assert(table_ref_stack_n <= chunk_list_reference_remaining_len);
1564
1565#ifdef USE_HASH_TABLE_ACCUMULATE
1566 MEM_delete(hash_store);
1567#endif
1568 }
1569 /* Done making the table. */
1570
1571 BLI_assert(i_prev <= data_len);
1572 for (size_t i = i_prev; i < data_len;) {
1573 /* Assumes exiting chunk isn't a match! */
1574
1575 const BChunkRef *cref_found = table_lookup(
1576 info, table, table_len, i_table_start, data, data_len, i, table_hash_array);
1577 if (cref_found != nullptr) {
1578 BLI_assert(i < data_len);
1579 if (i != i_prev) {
1580 bchunk_list_append_data_n(info, bs_mem, chunk_list, &data[i_prev], i - i_prev);
1581 i_prev = i;
1582 }
1583
1584 /* Now add the reference chunk. */
1585 {
1586 BChunk *chunk_found = cref_found->link;
1587 i += chunk_found->data_len;
1588 bchunk_list_append(info, bs_mem, chunk_list, chunk_found);
1589 }
1590 i_prev = i;
1591 BLI_assert(i_prev <= data_len);
1592 ASSERT_CHUNKLIST_SIZE(chunk_list, i_prev);
1593 ASSERT_CHUNKLIST_DATA(chunk_list, data);
1594
1595 /* Its likely that the next chunk in the list will be a match, so check it! */
1596 while (!ELEM(cref_found->next, nullptr, chunk_list_reference_last)) {
1597 cref_found = cref_found->next;
1598 BChunk *chunk_found = cref_found->link;
1599
1600 if (bchunk_data_compare(chunk_found, data, data_len, i_prev)) {
1601 /* May be useful to remove table data, assuming we don't have
1602 * repeating memory where it would be useful to re-use chunks. */
1603 i += chunk_found->data_len;
1604 bchunk_list_append(info, bs_mem, chunk_list, chunk_found);
1605 /* Chunk_found may be freed! */
1606 i_prev = i;
1607 BLI_assert(i_prev <= data_len);
1608 ASSERT_CHUNKLIST_SIZE(chunk_list, i_prev);
1609 ASSERT_CHUNKLIST_DATA(chunk_list, data);
1610 }
1611 else {
1612 break;
1613 }
1614 }
1615 }
1616 else {
1617 i = i + info->chunk_stride;
1618 }
1619 }
1620
1621#ifdef USE_HASH_TABLE_ACCUMULATE
1622 MEM_delete(table_hash_array);
1623#endif
1624 MEM_delete(table);
1625 MEM_delete(table_ref_stack);
1626
1627 /* End Table Lookup
1628 * ---------------- */
1629 }
1630
1631 ASSERT_CHUNKLIST_SIZE(chunk_list, i_prev);
1632 ASSERT_CHUNKLIST_DATA(chunk_list, data);
1633
1634 /* -----------------------------------------------------------------------
1635 * No Duplicates to copy, write new chunks
1636 *
1637 * Trailing chunks, no matches found in table lookup above.
1638 * Write all new data. */
1639 if (i_prev != data_len) {
1640 bchunk_list_append_data_n(info, bs_mem, chunk_list, &data[i_prev], data_len - i_prev);
1641 i_prev = data_len;
1642 }
1643
1644 BLI_assert(i_prev == data_len);
1645 UNUSED_VARS_NDEBUG(i_prev);
1646
1647#ifdef USE_FASTPATH_CHUNKS_LAST
1648 if (chunk_list_reference_last != nullptr) {
1649 /* Write chunk_list_reference_last since it hasn't been written yet. */
1650 const BChunkRef *cref = chunk_list_reference_last;
1651 while (cref != nullptr) {
1652 BChunk *chunk = cref->link;
1653 // BLI_assert(bchunk_data_compare(chunk, data, data_len, i_prev));
1654 i_prev += chunk->data_len;
1655 /* Use simple since we assume the references chunks have already been sized correctly. */
1656 bchunk_list_append_only(bs_mem, chunk_list, chunk);
1657 ASSERT_CHUNKLIST_DATA(chunk_list, data);
1658 cref = cref->next;
1659 }
1660 }
1661#endif
1662
1663#undef data_len_original
1664
1665 BLI_assert(i_prev == data_len_original);
1666 UNUSED_VARS_NDEBUG(i_prev);
1667
1668 /* Check we're the correct size and that we didn't accidentally modify the reference. */
1670 ASSERT_CHUNKLIST_SIZE(chunk_list_reference, chunk_list_reference->total_expanded_size);
1671
1672 ASSERT_CHUNKLIST_DATA(chunk_list, data);
1673
1674 return chunk_list;
1675}
1676/* End private API. */
1677
1679
1680/* -------------------------------------------------------------------- */
1683
1685{
1686 HashSize hash_size;
1687 if ((stride % uint(HashSize::U128)) == 0) {
1688 hash_size = HashSize::U128;
1689 }
1690 else if ((stride % uint(HashSize::U96)) == 0) {
1691 hash_size = HashSize::U96;
1692 }
1693 else if ((stride % uint(HashSize::U64)) == 0) {
1694 hash_size = HashSize::U64;
1695 }
1696 else if ((stride % uint(HashSize::U32)) == 0) {
1697 hash_size = HashSize::U32;
1698 }
1699 else if ((stride % uint(HashSize::U16)) == 0) {
1700 hash_size = HashSize::U16;
1701 }
1702 else {
1703 hash_size = HashSize::U8;
1704 }
1705
1706 BLI_assert(stride > 0 && chunk_count > 0);
1707 BLI_assert(stride % uint(hash_size) == 0); /* Stride must be a multiple of `hash_size`. */
1708
1710
1711 bs->info.chunk_stride = stride;
1712
1713 bs->info.hash_size = hash_size;
1714 // bs->info.chunk_count = chunk_count;
1715
1716 bs->info.chunk_byte_size = chunk_count * stride;
1717#ifdef USE_MERGE_CHUNKS
1718 bs->info.chunk_byte_size_min = std::max(1u, chunk_count / BCHUNK_SIZE_MIN_DIV) * stride;
1719 bs->info.chunk_byte_size_max = (chunk_count * BCHUNK_SIZE_MAX_MUL) * stride;
1720#endif
1721
1722#ifdef USE_HASH_TABLE_ACCUMULATE
1723 /* One is always subtracted from this `accum_steps`, this is intentional
1724 * as it results in reading ahead the expected amount. */
1725 if (stride <= sizeof(int8_t)) {
1727 }
1728 else if (stride <= sizeof(int16_t)) {
1730 }
1731 else if (stride <= sizeof(int32_t)) {
1733 }
1734 else {
1736 }
1737
1738 do {
1739 bs->info.accum_steps -= 1;
1740 /* Triangle number, identifying now much read-ahead we need:
1741 * https://en.wikipedia.org/wiki/Triangular_number (+ 1) */
1742 bs->info.accum_read_ahead_len = ((bs->info.accum_steps * (bs->info.accum_steps + 1)) / 2) + 1;
1743 /* Only small chunk counts are likely to exceed the read-ahead length. */
1744 } while (UNLIKELY(chunk_count < bs->info.accum_read_ahead_len));
1745
1747#else
1748 bs->info.accum_read_ahead_bytes = size_t(std::min(uint(BCHUNK_HASH_LEN), chunk_count)) * stride;
1749#endif
1750
1753 /* Allow iteration to simplify freeing, otherwise its not needed
1754 * (we could loop over all states as an alternative). */
1756
1758
1759 return bs;
1760}
1761
1763{
1764 /* Free chunk data. */
1765 {
1766 BLI_mempool_iter iter;
1767 BChunk *chunk;
1768 BLI_mempool_iternew(bs->memory.chunk, &iter);
1769 while ((chunk = static_cast<BChunk *>(BLI_mempool_iterstep(&iter)))) {
1770 BLI_assert(chunk->users > 0);
1771 MEM_delete(chunk->data);
1772 }
1773 }
1774
1775 /* Free states. */
1776 for (BArrayState *state = bs->states.first(), *state_next; state; state = state_next) {
1777 state_next = state->next;
1778 MEM_delete(state);
1779 }
1780}
1781
1783{
1785
1789
1790 MEM_delete(bs);
1791}
1792
1794{
1796
1797 bs->states.clear_no_delete();
1798
1802}
1803
1805
1806/* -------------------------------------------------------------------- */
1809
1811{
1812 size_t size_accum = 0;
1813 for (const BArrayState &state : bs->states) {
1814 size_accum += state.chunk_list->total_expanded_size;
1815 }
1816 return size_accum;
1817}
1818
1820{
1821 size_t size_total = 0;
1822 BLI_mempool_iter iter;
1823 const BChunk *chunk;
1824 BLI_mempool_iternew(bs->memory.chunk, &iter);
1825 while ((chunk = static_cast<BChunk *>(BLI_mempool_iterstep(&iter)))) {
1826 BLI_assert(chunk->users > 0);
1827 size_total += size_t(chunk->data_len);
1828 }
1829 return size_total;
1830}
1831
1833
1834/* -------------------------------------------------------------------- */
1837
1839 const void *data,
1840 const size_t data_len,
1841 const BArrayState *state_reference)
1842{
1843 /* Ensure we're aligned to the stride. */
1844 BLI_assert((data_len % bs->info.chunk_stride) == 0);
1845
1846#ifdef USE_PARANOID_CHECKS
1847 if (state_reference) {
1848 BLI_assert(BLI_findindex(&bs->states, state_reference) != -1);
1849 }
1850#endif
1851
1852 BChunkList *chunk_list;
1853 if (state_reference) {
1854 chunk_list = bchunk_list_from_data_merge(&bs->info,
1855 &bs->memory,
1856 static_cast<const uchar *>(data),
1857 data_len,
1858 /* Re-use reference chunks. */
1859 state_reference->chunk_list);
1860 }
1861 else {
1862 chunk_list = bchunk_list_new(&bs->memory, data_len);
1864 &bs->info, &bs->memory, chunk_list, static_cast<const uchar *>(data), data_len);
1865 }
1866
1867 chunk_list->users += 1;
1868
1870 state->chunk_list = chunk_list;
1871
1872 BLI_addtail(&bs->states, state);
1873
1874#ifdef USE_PARANOID_CHECKS
1875 {
1876 size_t data_test_len;
1877 void *data_test = BLI_array_store_state_data_get_alloc(state, &data_test_len);
1878 BLI_assert(data_test_len == data_len);
1879 BLI_assert(memcmp(data_test, data, data_len) == 0);
1880 MEM_delete(data_test);
1881 }
1882#endif
1883
1884 return state;
1885}
1886
1888{
1889#ifdef USE_PARANOID_CHECKS
1890 BLI_assert(BLI_findindex(&bs->states, state) != -1);
1891#endif
1892
1893 bchunk_list_decref(&bs->memory, state->chunk_list);
1894 BLI_remlink(&bs->states, state);
1895
1896 MEM_delete(state);
1897}
1898
1900{
1901 return state->chunk_list->total_expanded_size;
1902}
1903
1905{
1906#ifdef USE_PARANOID_CHECKS
1907 size_t data_test_len = 0;
1908 for (BChunkRef &cref : state->chunk_list->chunk_refs) {
1909 data_test_len += cref.link->data_len;
1910 }
1911 BLI_assert(data_test_len == state->chunk_list->total_expanded_size);
1912#endif
1913
1914 uchar *data_step = static_cast<uchar *>(data);
1915 for (BChunkRef &cref : state->chunk_list->chunk_refs) {
1916 BLI_assert(cref.link->users > 0);
1917 memcpy(data_step, cref.link->data, cref.link->data_len);
1918 data_step += cref.link->data_len;
1919 }
1920}
1921
1923{
1924 void *data = MEM_new_uninitialized(state->chunk_list->total_expanded_size, __func__);
1926 *r_data_len = state->chunk_list->total_expanded_size;
1927 return data;
1928}
1929
1931
1932/* -------------------------------------------------------------------- */
1935
1936/* Only for test validation. */
1937static size_t bchunk_list_size(const BChunkList *chunk_list)
1938{
1939 size_t total_expanded_size = 0;
1940 for (BChunkRef &cref : chunk_list->chunk_refs) {
1941 total_expanded_size += cref.link->data_len;
1942 }
1943 return total_expanded_size;
1944}
1945
1947{
1948 bool ok = true;
1949
1950 /* Check Length
1951 * ------------ */
1952
1953 for (BArrayState &state : bs->states) {
1954 BChunkList *chunk_list = state.chunk_list;
1955 if (!(bchunk_list_size(chunk_list) == chunk_list->total_expanded_size)) {
1956 return false;
1957 }
1958
1959 if (chunk_list->chunk_refs.count() != int(chunk_list->chunk_refs_len)) {
1960 return false;
1961 }
1962
1963#ifdef USE_MERGE_CHUNKS
1964 /* Ensure we merge all chunks that could be merged. */
1965 if (chunk_list->total_expanded_size > bs->info.chunk_byte_size_min) {
1966 for (BChunkRef &cref : chunk_list->chunk_refs) {
1967 if (cref.link->data_len < bs->info.chunk_byte_size_min) {
1968 return false;
1969 }
1970 }
1971 }
1972#endif
1973 }
1974
1975 /* Check User Count & Lost References
1976 * ---------------------------------- */
1977 {
1978 /* Count chunk_list's. */
1979 Map<BChunkList *, int> chunk_list_map;
1980 Map<BChunk *, int> chunk_map;
1981
1982 int totrefs = 0;
1983 for (BArrayState &state : bs->states) {
1984 chunk_list_map.lookup_or_add(state.chunk_list, 0)++;
1985 }
1986 for (const auto &item : chunk_list_map.items()) {
1987 const BChunkList *chunk_list = item.key;
1988 const int users = item.value;
1989 if (!(chunk_list->users == users)) {
1990 ok = false;
1991 goto user_finally;
1992 }
1993 }
1994 if (!(BLI_mempool_len(bs->memory.chunk_list) == chunk_list_map.size())) {
1995 ok = false;
1996 goto user_finally;
1997 }
1998
1999 /* Count chunk's. */
2000 for (const BChunkList *chunk_list : chunk_list_map.keys()) {
2001 for (const BChunkRef &cref : chunk_list->chunk_refs) {
2002 chunk_map.lookup_or_add(cref.link, 0)++;
2003 totrefs += 1;
2004 }
2005 }
2006 if (!(BLI_mempool_len(bs->memory.chunk) == chunk_map.size())) {
2007 ok = false;
2008 goto user_finally;
2009 }
2010 if (!(BLI_mempool_len(bs->memory.chunk_ref) == totrefs)) {
2011 ok = false;
2012 goto user_finally;
2013 }
2014
2015 for (const auto &item : chunk_map.items()) {
2016 const BChunk *chunk = item.key;
2017 const int users = item.value;
2018 if (!(chunk->users == users)) {
2019 ok = false;
2020 goto user_finally;
2021 }
2022 }
2023 }
2024
2025user_finally:
2026 return ok;
2027 /* TODO: dangling pointer checks. */
2028}
2029
2031
2032} // namespace blender
Efficient in-memory storage of multiple similar arrays.
Read Blender memory allocation and freeing.
#define BCHUNK_HASH_TABLE_MUL
#define USE_HASH_TABLE_ACCUMULATE
#define HASH_ARRAY_FROM_DATA_GENERIC(ty)
#define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_DEFAULT
#define ASSERT_CHUNKLIST_DATA(chunk_list, data)
#define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_8BITS
#define HASH_TABLE_KEY_UNSET
#define BCHUNK_SIZE_MAX_MUL
#define HASH_VALUE_IMPL_ADD_BYTES(h, value)
#define HASH_TABLE_KEY_FALLBACK
#define data_len_original
#define ASSERT_CHUNKLIST_SIZE(chunk_list, n)
#define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_32BITS
#define HASH_VALUE_IMPL_ADD(h, value)
#define HASH_INIT
#define BCHUNK_SIZE_MIN_DIV
#define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_16BITS
#define BLI_assert_unreachable()
#define UNUSED_VARS(...)
#define UNUSED_VARS_NDEBUG(...)
#define BLI_INLINE
#define UNLIKELY(x)
#define ELEM(...)
#define MEM_realloc_uninitialized(vmemh, len)
int64_t size() const
Definition BLI_map.hh:976
KeyIterator keys() const &
Definition BLI_map.hh:875
ItemIterator items() const &
Definition BLI_map.hh:902
Value & lookup_or_add(const Key &key, const Value &value)
Definition BLI_map.hh:588
unsigned int uchar
const int state
#define T
void split(const std::string &s, const char delim, std::vector< std::string > &tokens)
Definition abc_util.cc:68
BMesh Iterators.
void * MEM_new_uninitialized(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
static hash_key key_from_chunk_ref(const BArrayInfo *info, const BChunkRef *cref, hash_key *hash_store, const size_t hash_store_len)
static void hash_array_from_cref(const BArrayInfo *info, const BChunkRef *cref, const size_t data_len, hash_key *hash_array)
void BLI_array_store_state_remove(BArrayStore *bs, BArrayState *state)
static void hash_accum_single(hash_key *hash_array, const size_t hash_array_len, size_t iter_steps)
static void bchunk_list_append_data(const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, const uchar *data, const size_t data_len)
static size_t bchunk_list_size(const BChunkList *chunk_list)
static void bchunk_list_ensure_min_size_last(const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list)
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
static void hash_array_from_data(const BArrayInfo *info, const uchar *data_slice, const size_t data_slice_len, hash_key *hash_array)
static hash_key hash_data_generic(const T *data, size_t data_len)
BArrayState * BLI_array_store_state_add(BArrayStore *bs, const void *data, size_t data_len, const BArrayState *state_reference)
static void array_store_free_data(BArrayStore *bs)
static void hash_accum(hash_key *hash_array, const size_t hash_array_len, size_t iter_steps)
void * BLI_array_store_state_data_get_alloc(const BArrayState *state, size_t *r_data_len)
static void hash_array_from_data_generic(const size_t stride, const T *data_slice, const size_t data_slice_len, hash_key *hash_array)
void BLI_mempool_free(BLI_mempool *pool, void *addr) ATTR_NONNULL(1
unsigned short uint16_t
Definition BKE_text.h:80
bool BLI_array_store_is_valid(BArrayStore *bs)
BLI_INLINE void hash_value_generic(hash_key &h, const T &value)
unsigned int uint32_t
Definition BKE_text.h:81
void BLI_mempool_destroy(BLI_mempool *pool) ATTR_NONNULL(1)
int BLI_findindex(const ListBase *listbase, const void *vlink) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition listbase.cc:593
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)
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
unsigned char uchar
Definition BKE_text.h:58
void BLI_remlink(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:138
BArrayStore * BLI_array_store_create(unsigned int stride, unsigned int chunk_count)
BMesh const char void * data
void BLI_array_store_clear(BArrayStore *bs)
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
unsigned char uint8_t
Definition BKE_text.h:79
static void bchunk_decref(BArrayMemory *bs_mem, BChunk *chunk)
static void bchunk_list_append_only(BArrayMemory *bs_mem, BChunkList *chunk_list, BChunk *chunk)
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)
void BLI_mempool_iternew(BLI_mempool *pool, BLI_mempool_iter *iter) ATTR_NONNULL()
void BLI_mempool_clear(BLI_mempool *pool) ATTR_NONNULL(1)
void * BLI_mempool_iterstep(BLI_mempool_iter *iter) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void BLI_array_store_state_data_get(const BArrayState *state, void *data)
static void bchunk_list_fill_from_array(const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, const uchar *data, const size_t data_len)
static void bchunk_list_decref(BArrayMemory *bs_mem, BChunkList *chunk_list)
size_t BLI_array_store_calc_size_expanded_get(const BArrayStore *bs)
static BChunk * bchunk_new_copydata(BArrayMemory *bs_mem, const uchar *data, const size_t data_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)
uint32_t hash_key
size_t BLI_array_store_state_size_get(const BArrayState *state)
size_t BLI_array_store_calc_size_compacted_get(const BArrayStore *bs)
void BLI_addtail(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:118
@ BLI_MEMPOOL_NOP
@ BLI_MEMPOOL_ALLOW_ITER
static void bchunk_list_append(const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, BChunk *chunk)
BLI_INLINE hash_key hash_data_single_generic(const T &value)
signed int int32_t
Definition BKE_text.h:78
static BChunk * bchunk_new(BArrayMemory *bs_mem, const uchar *data, const size_t data_len)
void * BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
static bool bchunk_data_compare(const BChunk *chunk, const uchar *data_base, const size_t data_base_len, const size_t offset)
int BLI_mempool_len(const BLI_mempool *pool) ATTR_NONNULL(1)
void BLI_array_store_destroy(BArrayStore *bs)
BLI_INLINE bool bchunk_data_compare_unchecked(const BChunk *chunk, const uchar *data_base, const size_t data_base_len, const size_t offset)
BLI_INLINE void hash_accum_impl(hash_key *hash_array, const size_t i_dst, const size_t i_ahead)
static void bchunk_list_append_data_n(const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, const uchar *data, size_t data_len)
signed char int8_t
Definition BKE_text.h:76
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
signed short int16_t
Definition BKE_text.h:77
static BChunkList * bchunk_list_new(BArrayMemory *bs_mem, size_t total_expanded_size)
BLI_mempool * chunk_ref
BLI_mempool * chunk_list
BChunkList * chunk_list
ListBaseT< BArrayState > states
ListBaseT< BChunkRef > chunk_refs
const uchar * data
const BChunkRef * cref