lib.rs:

数组存储以最小化重复。

这是通过将数组分割成块并使用写时复制（COW）来去重块实现的，从用户的角度来看，这是一个实现细节。

概述

数据结构

此图是单个数组存储结构的概述。

注意：这里只有两种结构被外部引用。

• BArrayStore：整个数组存储。
• BArrayState：表示数据的一个状态（数组）。这些可以通过引用状态添加，虽然这可以被认为是前一个或父状态。不保持任何关系，因此调用者可以自由添加来自同一BArrayStore的任何状态作为引用。

<+> 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 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.

去重

在创建新状态时，可以提供一个前一个状态作为引用，从该状态匹配的块将重新用于新状态。

检测到数组的两端匹配。对于相同的数组，这已经足够。

对剩余的块进行去重，通过哈希块的前几个字节（见：BCHUNK_HASH_TABLE_ACCUMULATE_STEPS）。

注意：由于引用数据永远不会更改，因此这被缓存以供重用。

创建一个数组来存储每个'步长'的哈希值，然后遍历以搜索匹配的块。

一旦找到匹配项，下一个块也很有可能匹配，因此这被检查以避免执行过多的哈希查找。否则将创建新的块。

示例

let mut bs = array_cow::BArrayStore::new(1, 8);
let data_src_a = b"The quick brown fox jumps over the lazy dog";
let data_src_b = b"The quick brown fox almost jumps over the lazy dog";
let data_src_c = b"The little quick brown fox jumps over the lazy dog!";

let state_a = bs.state_add(data_src_a, None);
let state_b = bs.state_add(data_src_b, Some(state_a));
let state_c = bs.state_add(data_src_c, Some(state_b));

// Check the data is stored correctly
let data_dst = array_cow::BArrayStore::state_data_get_alloc(state_a);
assert_eq!(&data_src_a[..], &data_dst[..]);

let data_dst = array_cow::BArrayStore::state_data_get_alloc(state_b);
assert_eq!(&data_src_b[..], &data_dst[..]);

let data_dst = array_cow::BArrayStore::state_data_get_alloc(state_c);
assert_eq!(&data_src_c[..], &data_dst[..]);