Array storage to minimize duplication. More...

#include <algorithm>
#include <cstdlib>
#include <cstring>
#include "MEM_guardedalloc.h"
#include "BLI_listbase.h"
#include "BLI_mempool.h"
#include "BLI_array_store.h"
#include "BLI_ghash.h"
#include "BLI_strict_flags.h"

Classes
struct	BArrayInfo

struct	BArrayMemory

struct	BArrayStore

struct	BArrayState

struct	BChunkList

struct	BChunk

struct	BChunkRef

struct	BTableRef

Macros
#define	data_len_original invalid_usage

#define	GHASH_PTR_ADD_USER(gh, pt)

Defines
Some of the logic for merging is quite involved, support disabling some parts of this.
#define	USE_FASTPATH_CHUNKS_FIRST

#define	USE_FASTPATH_CHUNKS_LAST

#define	USE_ALIGN_CHUNKS_TEST

#define	USE_HASH_TABLE_ACCUMULATE

#define	BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_DEFAULT 3

#define	BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_32BITS 4

#define	BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_16BITS 5

#define	BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_8BITS 6

#define	USE_HASH_TABLE_KEY_CACHE

#define	HASH_TABLE_KEY_UNSET ((hash_key)-1)

#define	HASH_TABLE_KEY_FALLBACK ((hash_key)-2)

#define	USE_HASH_TABLE_DEDUPLICATE

#define	BCHUNK_HASH_TABLE_MUL 3

#define	USE_MERGE_CHUNKS

#define	BCHUNK_SIZE_MIN_DIV 8

#define	BCHUNK_SIZE_MAX_MUL 2

Typedefs
Internal Structs
Slow (keep disabled), but handy for debugging.
using	hash_key = uint32_t

Functions
Debugging API (for testing).
static size_t	bchunk_list_size (const BChunkList *chunk_list)

bool	BLI_array_store_is_valid (BArrayStore *bs)

Internal BChunk API
static BChunk *	bchunk_new (BArrayMemory bs_mem, const uchar data, const size_t data_len)

static BChunk *	bchunk_new_copydata (BArrayMemory bs_mem, const uchar data, const size_t data_len)

static void	bchunk_decref (BArrayMemory bs_mem, BChunk chunk)

BLI_INLINE bool	bchunk_data_compare_unchecked (const BChunk chunk, const uchar data_base, const size_t data_base_len, const size_t offset)

static bool	bchunk_data_compare (const BChunk chunk, const uchar data_base, const size_t data_base_len, const size_t offset)

Main Data De-Duplication Function
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)

Main Array Storage API
BArrayStore *	BLI_array_store_create (uint stride, uint chunk_count)

static void	array_store_free_data (BArrayStore *bs)

void	BLI_array_store_destroy (BArrayStore *bs)

void	BLI_array_store_clear (BArrayStore *bs)

BArrayStore Statistics
size_t	BLI_array_store_calc_size_expanded_get (const BArrayStore *bs)

size_t	BLI_array_store_calc_size_compacted_get (const BArrayStore *bs)

BArrayState Access
BArrayState *	BLI_array_store_state_add (BArrayStore bs, const void data, const size_t data_len, const BArrayState *state_reference)

void	BLI_array_store_state_remove (BArrayStore bs, BArrayState state)

size_t	BLI_array_store_state_size_get (BArrayState *state)

void	BLI_array_store_state_data_get (const BArrayState state, void data)

void *	BLI_array_store_state_data_get_alloc (BArrayState state, size_t r_data_len)

Internal BChunkList API
#define	ASSERT_CHUNKLIST_SIZE(chunk_list, n) (EXPR_NOP(chunk_list), EXPR_NOP(n))

#define	ASSERT_CHUNKLIST_DATA(chunk_list, data) (EXPR_NOP(chunk_list), EXPR_NOP(data))

static BChunkList *	bchunk_list_new (BArrayMemory *bs_mem, size_t total_expanded_size)

static void	bchunk_list_decref (BArrayMemory bs_mem, BChunkList chunk_list)

static void	bchunk_list_ensure_min_size_last (const BArrayInfo info, BArrayMemory bs_mem, BChunkList *chunk_list)

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)

static void	bchunk_list_append_only (BArrayMemory bs_mem, BChunkList chunk_list, BChunk *chunk)

static void	bchunk_list_append_data (const BArrayInfo info, BArrayMemory bs_mem, BChunkList chunk_list, const uchar data, const size_t data_len)

static void	bchunk_list_append_data_n (const BArrayInfo info, BArrayMemory bs_mem, BChunkList chunk_list, const uchar data, size_t data_len)

static void	bchunk_list_append (const BArrayInfo info, BArrayMemory bs_mem, BChunkList chunk_list, BChunk chunk)

static void	bchunk_list_fill_from_array (const BArrayInfo info, BArrayMemory bs_mem, BChunkList chunk_list, const uchar data, const size_t data_len)

Internal Hashing/De-Duplication API
Only used by bchunk_list_from_data_merge
#define	HASH_INIT (5381)

BLI_INLINE hash_key	hash_data_single (const uchar p)

static hash_key	hash_data (const uchar *key, size_t n)

static void	hash_array_from_data (const BArrayInfo info, const uchar data_slice, const size_t data_slice_len, hash_key *hash_array)

static void	hash_array_from_cref (const BArrayInfo info, const BChunkRef cref, const size_t data_len, hash_key *hash_array)

BLI_INLINE void	hash_accum_impl (hash_key *hash_array, const size_t i_dst, const size_t i_ahead)

static void	hash_accum (hash_key *hash_array, const size_t hash_array_len, size_t iter_steps)

static void	hash_accum_single (hash_key *hash_array, const size_t hash_array_len, size_t iter_steps)

static hash_key	key_from_chunk_ref (const BArrayInfo info, const BChunkRef cref, hash_key *hash_store, const size_t hash_store_len)

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)

Detailed Description

Array storage to minimize duplication.

This is done by splitting arrays into chunks and using copy-on-evaluation, to de-duplicate chunks, from the users perspective this is an implementation detail.

Overview

Data Structure

This diagram is an overview of the structure of a single array-store.

Note: The only 2 structures here which are referenced externally are the.

BArrayStore: The whole array store.
BArrayState: Represents a single state (array) of data. These can be add using a reference state, while this could be considered the previous or parent state. no relationship is kept, so the caller is free to add any state from the same BArrayStore as a reference.

<+> BArrayStore: root data-structure,
 |  can store many 'states', which share memory.
 |
 |  This can store many arrays, however they must share the same 'stride'.
 |  Arrays of different types will need to use a new BArrayStore.
 |
 +- <+> states (Collection of BArrayState's):
 |   |  Each represents an array added by the user of this API.
 |   |  and references a chunk_list (each state is a chunk_list user).
 |   |  Note that the list order has no significance.
 |   |
 |   +- <+> chunk_list (BChunkList):
 |       |  The chunks that make up this state.
 |       |  Each state is a chunk_list user,
 |       |  avoids duplicating lists when there is no change between states.
 |       |
 |       +- chunk_refs (List of BChunkRef): Each chunk_ref links to a BChunk.
 |          Each reference is a chunk user,
 |          avoids duplicating smaller chunks of memory found in multiple states.
 |
 +- info (BArrayInfo):
 |  Sizes and offsets for this array-store.
 |  Also caches some variables for reuse.
 |
 +- <+> memory (BArrayMemory):
     |  Memory pools for storing BArrayStore data.
     |
     +- chunk_list (Pool of BChunkList):
     |  All chunk_lists, (reference counted, used by BArrayState).
     |
     +- chunk_ref (Pool of BChunkRef):
     |  All chunk_refs (link between BChunkList & BChunk).
     |
     +- chunks (Pool of BChunk):
        All chunks, (reference counted, used by BChunkList).
        These have their headers hashed for reuse so we can quickly check for duplicates.

D<h2>e-Duplication

When creating a new state, a previous state can be given as a reference, matching chunks from this state are re-used in the new state.

First matches at either end of the array are detected. For identical arrays this is all that's needed.

De-duplication is performed on any remaining chunks, by hashing the first few bytes of the chunk (see: #BCHUNK_HASH_TABLE_ACCUMULATE_STEPS).

Note: This is cached for reuse since the referenced data never changes.

An array is created to store hash values at every 'stride', then stepped over to search for matching chunks.

Once a match is found, there is a high chance next chunks match too, so this is checked to avoid performing so many hash-lookups. Otherwise new chunks are created.

Definition in file array_store.cc.

Macro Definition Documentation

◆ ASSERT_CHUNKLIST_DATA

#define ASSERT_CHUNKLIST_DATA	(		chunk_list,
			data ) (EXPR_NOP(chunk_list), EXPR_NOP(data))

Definition at line 467 of file array_store.cc.

Referenced by bchunk_list_fill_from_array(), and bchunk_list_from_data_merge().

◆ ASSERT_CHUNKLIST_SIZE

#define ASSERT_CHUNKLIST_SIZE	(		chunk_list,
			n ) (EXPR_NOP(chunk_list), EXPR_NOP(n))

Definition at line 449 of file array_store.cc.

Referenced by bchunk_list_fill_from_array(), and bchunk_list_from_data_merge().

◆ BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_16BITS

#define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_16BITS 5

Definition at line 158 of file array_store.cc.

Referenced by BLI_array_store_create().

◆ BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_32BITS

#define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_32BITS 4

Definition at line 157 of file array_store.cc.

Referenced by BLI_array_store_create().

◆ BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_8BITS

#define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_8BITS 6

Single bytes (or boolean) arrays need a higher number of steps because the resulting values are not unique enough to result in evenly distributed values. Use more accumulation when the size of the structs is small, see: #105046.

With 6 -> 22, one byte each - means an array of booleans can be combined into 22 bits representing 4,194,303 different combinations.

Definition at line 167 of file array_store.cc.

Referenced by BLI_array_store_create().

◆ BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_DEFAULT

#define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_DEFAULT 3

Definition at line 156 of file array_store.cc.

Referenced by BLI_array_store_create().

◆ BCHUNK_HASH_TABLE_MUL

#define BCHUNK_HASH_TABLE_MUL 3

How much larger the table is then the total number of chunks.

Definition at line 198 of file array_store.cc.

Referenced by bchunk_list_from_data_merge().

◆ BCHUNK_SIZE_MAX_MUL

#define BCHUNK_SIZE_MAX_MUL 2

Disallow chunks bigger than the regular chunk size scaled by this value.

Note: must be at least 2! however, this code runs won't run in tests unless it's ~1.1 ugh. so lower only to check splitting works.

Definition at line 224 of file array_store.cc.

Referenced by BLI_array_store_create().

◆ BCHUNK_SIZE_MIN_DIV

#define BCHUNK_SIZE_MIN_DIV 8

Merge chunks smaller then: (BArrayInfo::chunk_byte_size / BCHUNK_SIZE_MIN_DIV).

Definition at line 215 of file array_store.cc.

Referenced by BLI_array_store_create().

◆ data_len_original

#define data_len_original invalid_usage

Referenced by bchunk_list_from_data_merge().

◆ GHASH_PTR_ADD_USER

#define GHASH_PTR_ADD_USER	(		gh,
			pt )

Value:

  { \
    void **val; \
    if (BLI_ghash_ensure_p((gh), (pt), &val)) { \
      *((int *)val) += 1; \
    } \
    else { \
      *((int *)val) = 1; \
    } \
  } \
  ((void)0)

Referenced by BLI_array_store_is_valid().

◆ HASH_INIT

#define HASH_INIT (5381)

Definition at line 793 of file array_store.cc.

Referenced by hash_data(), and hash_data_single().

◆ HASH_TABLE_KEY_FALLBACK

#define HASH_TABLE_KEY_FALLBACK ((hash_key)-2)

Definition at line 182 of file array_store.cc.

Referenced by key_from_chunk_ref().

◆ HASH_TABLE_KEY_UNSET

#define HASH_TABLE_KEY_UNSET ((hash_key)-1)

Definition at line 181 of file array_store.cc.

Referenced by bchunk_new(), and key_from_chunk_ref().

◆ USE_ALIGN_CHUNKS_TEST

#define USE_ALIGN_CHUNKS_TEST

For arrays of matching length, test that enough of the chunks are aligned, and simply step over both arrays, using matching chunks. This avoids overhead of using a lookup table for cases when we can assume they're mostly aligned.

Definition at line 139 of file array_store.cc.

◆ USE_FASTPATH_CHUNKS_FIRST

#define USE_FASTPATH_CHUNKS_FIRST

Scan first chunks (happy path when beginning of the array matches). When the array is a perfect match, we can re-use the entire list.

Note that disabling makes some tests fail that check for output-size.

Definition at line 119 of file array_store.cc.

◆ USE_FASTPATH_CHUNKS_LAST

#define USE_FASTPATH_CHUNKS_LAST

Scan last chunks (happy path when end of the array matches). When the end of the array matches, we can quickly add these chunks. note that we will add contiguous matching chunks so this isn't as useful as USE_FASTPATH_CHUNKS_FIRST, however it avoids adding matching chunks into the lookup table, so creating the lookup table won't be as expensive.

Definition at line 130 of file array_store.cc.

◆ USE_HASH_TABLE_ACCUMULATE

#define USE_HASH_TABLE_ACCUMULATE

Accumulate hashes from right to left so we can create a hash for the chunk-start. This serves to increase uniqueness and will help when there is many values which are the same.

Definition at line 145 of file array_store.cc.

Referenced by bchunk_list_from_data_merge().

◆ USE_HASH_TABLE_DEDUPLICATE

#define USE_HASH_TABLE_DEDUPLICATE

Ensure duplicate entries aren't added to temporary hash table needed for arrays where many values match (an array of booleans all true/false for e.g.).

Without this, a huge number of duplicates are added a single bucket, making hash lookups slow. While de-duplication adds some cost, it's only performed with other chunks in the same bucket so cases when all chunks are unique will quickly detect and exit the memcmp in most cases.

Definition at line 193 of file array_store.cc.

◆ USE_HASH_TABLE_KEY_CACHE

#define USE_HASH_TABLE_KEY_CACHE

Calculate the key once and reuse it.

Definition at line 179 of file array_store.cc.

◆ USE_MERGE_CHUNKS

#define USE_MERGE_CHUNKS

Merge too small/large chunks:

Using this means chunks below a threshold will be merged together. Even though short term this uses more memory, long term the overhead of maintaining many small chunks is reduced. This is defined by setting the minimum chunk size (as a fraction of the regular chunk size).

Chunks may also become too large (when incrementally growing an array), this also enables chunk splitting.

Definition at line 211 of file array_store.cc.

Typedef Documentation

◆ hash_key

using hash_key = uint32_t

Definition at line 240 of file array_store.cc.

Function Documentation

◆ array_store_free_data()

static void array_store_free_data ( BArrayStore * bs )

static

Definition at line 1549 of file array_store.cc.

References BLI_assert, BLI_mempool_iternew(), BLI_mempool_iterstep(), BArrayMemory::chunk, BChunk::data, ListBase::first, MEM_freeN(), BArrayStore::memory, state, BArrayStore::states, and BChunk::users.

Referenced by BLI_array_store_clear(), and BLI_array_store_destroy().

◆ bchunk_data_compare()

static bool bchunk_data_compare	(	const BChunk *	chunk,
		const uchar *	data_base,
		const size_t	data_base_len,
		const size_t	offset )

static

Definition at line 395 of file array_store.cc.

References bchunk_data_compare_unchecked(), and BChunk::data_len.

Referenced by bchunk_list_from_data_merge().

◆ bchunk_data_compare_unchecked()

BLI_INLINE bool bchunk_data_compare_unchecked	(	const BChunk *	chunk,
		const uchar *	data_base,
		const size_t	data_base_len,
		const size_t	offset )

Definition at line 385 of file array_store.cc.

References BLI_assert, BChunk::data, BChunk::data_len, and UNUSED_VARS_NDEBUG.

Referenced by bchunk_data_compare(), and table_lookup().

◆ bchunk_decref()

static void bchunk_decref	(	BArrayMemory *	bs_mem,
		BChunk *	chunk )

static

Definition at line 373 of file array_store.cc.

References BLI_assert, BLI_mempool_free(), BArrayMemory::chunk, BChunk::data, MEM_freeN(), and BChunk::users.

Referenced by bchunk_list_append_data(), bchunk_list_decref(), and bchunk_list_ensure_min_size_last().

◆ bchunk_list_append()

static void bchunk_list_append	(	const BArrayInfo *	info,
		BArrayMemory *	bs_mem,
		BChunkList *	chunk_list,
		BChunk *	chunk )

static

Definition at line 724 of file array_store.cc.

References bchunk_list_append_only(), bchunk_list_ensure_min_size_last(), and UNUSED_VARS.

Referenced by bchunk_list_from_data_merge().

◆ bchunk_list_append_data()

static void bchunk_list_append_data	(	const BArrayInfo *	info,
		BArrayMemory *	bs_mem,
		BChunkList *	chunk_list,
		const uchar *	data,
		const size_t	data_len )

static

Note: This is for writing single chunks, use bchunk_list_append_data_n when writing large blocks of memory into many chunks.

Definition at line 619 of file array_store.cc.

References bchunk_decref(), bchunk_list_append_only(), bchunk_list_ensure_min_size_last(), bchunk_new(), bchunk_new_copydata(), BLI_assert, BLI_listbase_is_empty(), BArrayInfo::chunk_byte_size_min, BChunkList::chunk_refs, BChunk::data, BChunk::data_len, ListBase::last, BChunkRef::link, MEM_mallocN, MEM_reallocN, UNUSED_VARS, and BChunk::users.

Referenced by bchunk_list_append_data_n(), and bchunk_list_from_data_merge().

◆ bchunk_list_append_data_n()

static void bchunk_list_append_data_n	(	const BArrayInfo *	info,
		BArrayMemory *	bs_mem,
		BChunkList *	chunk_list,
		const uchar *	data,
		size_t	data_len )

static

Similar to bchunk_list_append_data, but handle multiple chunks. Use for adding arrays of arbitrary sized memory at once.

Note: This function takes care not to perform redundant chunk-merging checks, so we can write successive fixed size chunks quickly.

Definition at line 677 of file array_store.cc.

References bchunk_list_append_data(), bchunk_list_append_only(), bchunk_list_calc_trim_len(), bchunk_new_copydata(), BLI_assert, BArrayInfo::chunk_byte_size, BArrayInfo::chunk_byte_size_min, BChunkList::chunk_refs, and ListBase::last.

Referenced by bchunk_list_from_data_merge().

◆ bchunk_list_append_only()

static void bchunk_list_append_only	(	BArrayMemory *	bs_mem,
		BChunkList *	chunk_list,
		BChunk *	chunk )

static

Append and don't manage merging small chunks.

Definition at line 606 of file array_store.cc.

References BLI_addtail(), BLI_mempool_alloc(), BArrayMemory::chunk_ref, BChunkList::chunk_refs, BChunkList::chunk_refs_len, BChunkRef::link, and BChunk::users.

Referenced by bchunk_list_append(), bchunk_list_append_data(), bchunk_list_append_data_n(), bchunk_list_fill_from_array(), and bchunk_list_from_data_merge().

◆ bchunk_list_calc_trim_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 )

static

Split length into 2 values

Parameters

r_data_trim_len	Length which is aligned to the BArrayInfo.chunk_byte_size
r_data_last_chunk_len	The remaining bytes.

Note: This function ensures the size of r_data_last_chunk_len is larger than BArrayInfo.chunk_byte_size_min.

Definition at line 565 of file array_store.cc.

References BLI_assert, and BArrayInfo::chunk_byte_size.

Referenced by bchunk_list_append_data_n(), and bchunk_list_fill_from_array().

◆ bchunk_list_decref()

static void bchunk_list_decref	(	BArrayMemory *	bs_mem,
		BChunkList *	chunk_list )

static

Definition at line 423 of file array_store.cc.

References bchunk_decref(), BLI_assert, BLI_mempool_free(), BArrayMemory::chunk_list, BArrayMemory::chunk_ref, BChunkList::chunk_refs, ListBase::first, and BChunkList::users.

Referenced by BLI_array_store_state_remove().

◆ bchunk_list_ensure_min_size_last()

static void bchunk_list_ensure_min_size_last	(	const BArrayInfo *	info,
		BArrayMemory *	bs_mem,
		BChunkList *	chunk_list )

static

Definition at line 471 of file array_store.cc.

References bchunk_decref(), bchunk_new(), BLI_assert, BLI_mempool_free(), BArrayInfo::chunk_byte_size, BArrayInfo::chunk_byte_size_min, BArrayMemory::chunk_ref, BChunkList::chunk_refs, BChunkList::chunk_refs_len, BChunk::data, BChunk::data_len, ListBase::first, ListBase::last, BChunkRef::link, MEM_mallocN, BChunkRef::next, BChunkRef::prev, split(), and BChunk::users.

Referenced by bchunk_list_append(), bchunk_list_append_data(), and bchunk_list_fill_from_array().

◆ bchunk_list_fill_from_array()

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

Definition at line 738 of file array_store.cc.

References ASSERT_CHUNKLIST_DATA, ASSERT_CHUNKLIST_SIZE, bchunk_list_append_only(), bchunk_list_calc_trim_len(), bchunk_list_ensure_min_size_last(), bchunk_new_copydata(), BLI_assert, BLI_listbase_is_empty(), BArrayInfo::chunk_byte_size, BArrayInfo::chunk_byte_size_min, BChunkList::chunk_refs, and ListBase::last.

Referenced by BLI_array_store_state_add().

◆ bchunk_list_from_data_merge()

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 )

static

Parameters

data	Data to store in the returned value.
data_len_original	Length of data in bytes.
chunk_list_reference	Reuse this list or chunks within it, don't modify its content.

Note: Caller is responsible for adding the user.

Definition at line 1078 of file array_store.cc.

References BArrayInfo::accum_read_ahead_bytes, BArrayInfo::accum_read_ahead_len, BArrayInfo::accum_steps, ASSERT_CHUNKLIST_DATA, ASSERT_CHUNKLIST_SIZE, bchunk_data_compare(), BCHUNK_HASH_TABLE_MUL, bchunk_list_append(), bchunk_list_append_data(), bchunk_list_append_data_n(), bchunk_list_append_only(), bchunk_list_new(), BLI_assert, BLI_listbase_is_empty(), BArrayInfo::chunk_byte_size, BChunkList::chunk_refs, BChunkList::chunk_refs_len, BArrayInfo::chunk_stride, BTableRef::cref, BChunk::data, BChunk::data_len, data_len_original, ELEM, ListBase::first, hash_accum(), hash_array_from_data(), BChunk::key, key_from_chunk_ref(), ListBase::last, BChunkRef::link, MEM_callocN, MEM_freeN(), MEM_mallocN, BChunkRef::next, BTableRef::next, BChunkRef::prev, table_lookup(), BChunkList::total_expanded_size, UNUSED_VARS_NDEBUG, and USE_HASH_TABLE_ACCUMULATE.

Referenced by BLI_array_store_state_add().

◆ bchunk_list_new()

static BChunkList * bchunk_list_new	(	BArrayMemory *	bs_mem,
		size_t	total_expanded_size )

static

Definition at line 412 of file array_store.cc.

References BLI_listbase_clear(), BLI_mempool_alloc(), BArrayMemory::chunk_list, BChunkList::chunk_refs, BChunkList::chunk_refs_len, BChunkList::total_expanded_size, and BChunkList::users.

Referenced by bchunk_list_from_data_merge(), and BLI_array_store_state_add().

◆ bchunk_list_size()

static size_t bchunk_list_size ( const BChunkList * chunk_list )

static

Definition at line 1725 of file array_store.cc.

References BChunkList::chunk_refs, BChunk::data_len, BChunkRef::link, and LISTBASE_FOREACH.

Referenced by BLI_array_store_is_valid().

◆ bchunk_new()

static BChunk * bchunk_new	(	BArrayMemory *	bs_mem,
		const uchar *	data,
		const size_t	data_len )

static

Definition at line 354 of file array_store.cc.

References BLI_mempool_alloc(), BArrayMemory::chunk, BChunk::data, data, BChunk::data_len, HASH_TABLE_KEY_UNSET, BChunk::key, and BChunk::users.

Referenced by bchunk_list_append_data(), bchunk_list_ensure_min_size_last(), and bchunk_new_copydata().

◆ bchunk_new_copydata()

static BChunk * bchunk_new_copydata	(	BArrayMemory *	bs_mem,
		const uchar *	data,
		const size_t	data_len )

static

Definition at line 366 of file array_store.cc.

References bchunk_new(), and MEM_mallocN.

Referenced by bchunk_list_append_data(), bchunk_list_append_data_n(), and bchunk_list_fill_from_array().

◆ BLI_array_store_calc_size_compacted_get()

size_t BLI_array_store_calc_size_compacted_get ( const BArrayStore * bs )

Returns: the amount of memory used by all BChunk.data (duplicate chunks are only counted once).

Definition at line 1608 of file array_store.cc.

References BLI_assert, BLI_mempool_iternew(), BLI_mempool_iterstep(), BArrayMemory::chunk, BChunk::data_len, BArrayStore::memory, and BChunk::users.

Referenced by BLI_array_store_at_size_calc_memory_usage(), random_chunk_mutate_helper(), TEST(), TEST(), TEST(), and text_undosys_step_encode_to_state().

◆ BLI_array_store_calc_size_expanded_get()

size_t BLI_array_store_calc_size_expanded_get ( const BArrayStore * bs )

Find the memory used by all states (expanded & real).

Returns: the total amount of memory that would be used by getting the arrays for all states.

Definition at line 1599 of file array_store.cc.

References LISTBASE_FOREACH, state, and BArrayStore::states.

Referenced by BLI_array_store_at_size_calc_memory_usage(), TEST(), and TEST().

◆ BLI_array_store_clear()

void BLI_array_store_clear ( BArrayStore * bs )

Clear all contents, allowing reuse of bs.

Definition at line 1582 of file array_store.cc.

References array_store_free_data(), BLI_listbase_clear(), BLI_mempool_clear(), BArrayMemory::chunk, BArrayMemory::chunk_list, BArrayMemory::chunk_ref, BArrayStore::memory, and BArrayStore::states.

◆ BLI_array_store_create()

BArrayStore * BLI_array_store_create	(	unsigned int	stride,
		unsigned int	chunk_count )

Create a new array store, which can store any number of arrays as long as their stride matches.

Parameters

stride sizeof() each element,

Note: while a stride of 1 will always work, its less efficient since duplicate chunks of memory will be searched at positions unaligned with the array data.

Parameters

chunk_count

Number of elements to split each chunk into.

A small value increases the ability to de-duplicate chunks, but adds overhead by increasing the number of chunks to look up when searching for duplicates, as well as some overhead constructing the original array again, with more calls to memcpy.
Larger values reduce the book keeping overhead, but increase the chance a small, isolated change will cause a larger amount of data to be duplicated.

Returns: A new array store, to be freed with BLI_array_store_destroy.

Definition at line 1494 of file array_store.cc.

References BArrayInfo::accum_read_ahead_bytes, BArrayInfo::accum_read_ahead_len, BArrayInfo::accum_steps, BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_16BITS, BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_32BITS, BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_8BITS, BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_DEFAULT, BCHUNK_SIZE_MAX_MUL, BCHUNK_SIZE_MIN_DIV, BLI_assert, BLI_MEMPOOL_ALLOW_ITER, BLI_mempool_create(), BLI_MEMPOOL_NOP, BArrayMemory::chunk, BArrayInfo::chunk_byte_size, BArrayInfo::chunk_byte_size_max, BArrayInfo::chunk_byte_size_min, BArrayMemory::chunk_list, BArrayMemory::chunk_ref, BArrayInfo::chunk_stride, BArrayStore::info, BArrayStore::memory, and UNLIKELY.

Referenced by BLI_array_store_at_size_ensure(), random_chunk_mutate_helper(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), testbuffer_run_tests_simple(), and text_undosys_step_encode_to_state().

◆ BLI_array_store_destroy()

void BLI_array_store_destroy ( BArrayStore * bs )

Free the BArrayStore, including all states and chunks.

Definition at line 1571 of file array_store.cc.

References array_store_free_data(), BLI_mempool_destroy(), BArrayMemory::chunk, BArrayMemory::chunk_list, BArrayMemory::chunk_ref, MEM_freeN(), and BArrayStore::memory.

Referenced by BLI_array_store_at_size_clear(), random_chunk_mutate_helper(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), testbuffer_run_tests_simple(), and text_undosys_step_free().

◆ BLI_array_store_is_valid()

bool BLI_array_store_is_valid ( BArrayStore * bs )

◆ BLI_array_store_state_add()

BArrayState * BLI_array_store_state_add	(	BArrayStore *	bs,
		const void *	data,
		size_t	data_len,
		const BArrayState *	state_reference )

Parameters

data	Data used to create
state_reference	The state to use as a reference when adding the new state, typically this is the previous state, however it can be any previously created state from this bs.

Returns: The new state, which is used by the caller as a handle to get back the contents of data. This may be removed using BLI_array_store_state_remove, otherwise it will be removed with BLI_array_store_destroy.

Definition at line 1627 of file array_store.cc.

References bchunk_list_fill_from_array(), bchunk_list_from_data_merge(), bchunk_list_new(), BLI_addtail(), BLI_array_store_state_data_get_alloc(), BLI_assert, BLI_findindex(), BArrayState::chunk_list, BArrayInfo::chunk_stride, BArrayStore::info, MEM_freeN(), BArrayStore::memory, state, BArrayStore::states, and BChunkList::users.

Referenced by TEST(), TEST(), TEST(), TEST(), testbuffer_list_store_populate(), text_state_encode(), and um_arraystore_cd_compact().

◆ BLI_array_store_state_data_get()

void BLI_array_store_state_data_get	(	const BArrayState *	state,
		void *	data )

Fill in existing allocated memory with the contents of state.

Definition at line 1692 of file array_store.cc.

References BLI_assert, BChunk::data, BChunk::data_len, BChunkRef::link, LISTBASE_FOREACH, state, and BChunk::users.

Referenced by BLI_array_store_state_data_get_alloc().

◆ BLI_array_store_state_data_get_alloc()

void * BLI_array_store_state_data_get_alloc	(	BArrayState *	state,
		size_t *	r_data_len )

Allocate an array for state and return it.

Definition at line 1710 of file array_store.cc.

References BLI_array_store_state_data_get(), data, MEM_mallocN, and state.

Referenced by BLI_array_store_state_add(), TEST(), TEST(), TEST(), testbuffer_item_validate(), text_state_decode(), um_arraystore_cd_expand(), and um_arraystore_expand().

◆ BLI_array_store_state_remove()

void BLI_array_store_state_remove	(	BArrayStore *	bs,
		BArrayState *	state )

Remove a state and free any unused BChunk data.

The states can be freed in any order.

Definition at line 1675 of file array_store.cc.

References bchunk_list_decref(), BLI_assert, BLI_findindex(), BLI_remlink(), BArrayMemory::chunk_list, MEM_freeN(), BArrayStore::memory, state, and BArrayStore::states.

Referenced by TEST(), testbuffer_list_store_clear(), text_undosys_step_free(), um_arraystore_cd_free(), and um_arraystore_free().

◆ BLI_array_store_state_size_get()

size_t BLI_array_store_state_size_get ( BArrayState * state )

Returns: the expanded size of the array, use this to know how much memory to allocate BLI_array_store_state_data_get's argument.

Definition at line 1687 of file array_store.cc.

References state.

Referenced by TEST().

◆ hash_accum()

static void hash_accum	(	hash_key *	hash_array,
		const size_t	hash_array_len,
		size_t	iter_steps )

static

Definition at line 871 of file array_store.cc.

References hash_accum_impl(), and UNLIKELY.

Referenced by bchunk_list_from_data_merge().

◆ hash_accum_impl()

BLI_INLINE void hash_accum_impl	(	hash_key *	hash_array,
		const size_t	i_dst,
		const size_t	i_ahead )

Definition at line 863 of file array_store.cc.

References BLI_assert.

Referenced by hash_accum(), and hash_accum_single().

◆ hash_accum_single()

static void hash_accum_single	(	hash_key *	hash_array,
		const size_t	hash_array_len,
		size_t	iter_steps )

static

When we only need a single value, can use a small optimization. we can avoid accumulating the tail of the array a little, each iteration.

Definition at line 892 of file array_store.cc.

References BLI_assert, hash_accum_impl(), and UNLIKELY.

Referenced by key_from_chunk_ref().

◆ hash_array_from_cref()

static void hash_array_from_cref	(	const BArrayInfo *	info,
		const BChunkRef *	cref,
		const size_t	data_len,
		hash_key *	hash_array )

static

Similar to hash_array_from_data, but able to step into the next chunk if we run-out of data.

Definition at line 838 of file array_store.cc.

References BLI_assert, BArrayInfo::chunk_stride, BChunk::data, BChunk::data_len, hash_array_from_data(), BChunkRef::link, and BChunkRef::next.

Referenced by key_from_chunk_ref().

◆ hash_array_from_data()

static void hash_array_from_data	(	const BArrayInfo *	info,
		const uchar *	data_slice,
		const size_t	data_slice_len,
		hash_key *	hash_array )

static

Definition at line 816 of file array_store.cc.

References BArrayInfo::chunk_stride, hash_data(), and hash_data_single().

Referenced by bchunk_list_from_data_merge(), and hash_array_from_cref().

◆ hash_data()

static hash_key hash_data	(	const uchar *	key,
		size_t	n )

static

Definition at line 801 of file array_store.cc.

References HASH_INIT.

Referenced by hash_array_from_data().

◆ hash_data_single()

BLI_INLINE hash_key hash_data_single ( const uchar p )

Definition at line 795 of file array_store.cc.

References HASH_INIT.

Referenced by hash_array_from_data().

◆ key_from_chunk_ref()

static hash_key key_from_chunk_ref	(	const BArrayInfo *	info,
		const BChunkRef *	cref,
		hash_key *	hash_store,
		const size_t	hash_store_len )

static

Definition at line 914 of file array_store.cc.

References BArrayInfo::accum_read_ahead_bytes, BArrayInfo::accum_steps, BLI_assert, BArrayInfo::chunk_stride, BChunk::data_len, hash_accum_single(), hash_array_from_cref(), HASH_TABLE_KEY_FALLBACK, HASH_TABLE_KEY_UNSET, BChunk::key, BChunkRef::link, and UNLIKELY.

Referenced by bchunk_list_from_data_merge().

◆ table_lookup()

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 )

static

Definition at line 965 of file array_store.cc.

References bchunk_data_compare_unchecked(), BArrayInfo::chunk_stride, BTableRef::cref, BChunk::data_len, BChunk::key, BChunkRef::link, and BTableRef::next.

Referenced by bchunk_list_from_data_merge().

Classes

Macros

Typedefs

Functions

Internal BChunkList API

Internal Hashing/De-Duplication API

Detailed Description

Overview

Data Structure

Macro Definition Documentation

◆ ASSERT_CHUNKLIST_DATA

◆ ASSERT_CHUNKLIST_SIZE

◆ BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_16BITS

◆ BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_32BITS

◆ BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_8BITS

◆ BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_DEFAULT

◆ BCHUNK_HASH_TABLE_MUL

◆ BCHUNK_SIZE_MAX_MUL

◆ BCHUNK_SIZE_MIN_DIV

◆ data_len_original

◆ GHASH_PTR_ADD_USER

◆ HASH_INIT

◆ HASH_TABLE_KEY_FALLBACK

◆ HASH_TABLE_KEY_UNSET

◆ USE_ALIGN_CHUNKS_TEST

◆ USE_FASTPATH_CHUNKS_FIRST

◆ USE_FASTPATH_CHUNKS_LAST

◆ USE_HASH_TABLE_ACCUMULATE

◆ USE_HASH_TABLE_DEDUPLICATE

◆ USE_HASH_TABLE_KEY_CACHE

◆ USE_MERGE_CHUNKS

Typedef Documentation

◆ hash_key

Function Documentation

◆ array_store_free_data()

◆ bchunk_data_compare()

◆ bchunk_data_compare_unchecked()

◆ bchunk_decref()

◆ bchunk_list_append()

◆ bchunk_list_append_data()

◆ bchunk_list_append_data_n()

◆ bchunk_list_append_only()

◆ bchunk_list_calc_trim_len()

◆ bchunk_list_decref()

◆ bchunk_list_ensure_min_size_last()

◆ bchunk_list_fill_from_array()

◆ bchunk_list_from_data_merge()

◆ bchunk_list_new()

◆ bchunk_list_size()

◆ bchunk_new()

◆ bchunk_new_copydata()

◆ BLI_array_store_calc_size_compacted_get()

◆ BLI_array_store_calc_size_expanded_get()

◆ BLI_array_store_clear()

◆ BLI_array_store_create()

◆ BLI_array_store_destroy()

◆ BLI_array_store_is_valid()

◆ BLI_array_store_state_add()

◆ BLI_array_store_state_data_get()

◆ BLI_array_store_state_data_get_alloc()

◆ BLI_array_store_state_remove()

◆ BLI_array_store_state_size_get()

◆ hash_accum()

◆ hash_accum_impl()

◆ hash_accum_single()

◆ hash_array_from_cref()

◆ hash_array_from_data()

◆ hash_data()

◆ hash_data_single()

◆ key_from_chunk_ref()

◆ table_lookup()