Cleanup: doxygen comments
[blender-staging.git] / source / blender / blenlib / intern / array_store.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * ***** END GPL LICENSE BLOCK *****
19  */
20
21 /** \file blender/blenlib/intern/array_store.c
22  *  \ingroup bli
23  *  \brief Array storage to minimize duplication.
24  *
25  * This is done by splitting arrays into chunks and using copy-on-write (COW),
26  * to de-duplicate chunks,
27  * from the users perspective this is an implementation detail.
28  *
29  *
30  * Overview
31  * ========
32  *
33  *
34  * Data Structure
35  * --------------
36  *
37  * This diagram is an overview of the structure of a single array-store.
38  *
39  * \note The only 2 structures here which are referenced externally are the.
40  *
41  * - BArrayStore: The whole array store.
42  * - BArrayState: Represents a single state (array) of data.
43  *   These can be add using a reference state, while this could be considered the previous or parent state.
44  *   no relationship is kept, so the caller is free to add any state from the same BArrayStore as a reference.
45  *
46  * <pre>
47  * <+> BArrayStore: root data-structure,
48  *  |  can store many 'states', which share memory.
49  *  |
50  *  |  This can store many arrays, however they must share the same 'stride'.
51  *  |  Arrays of different types will need to use a new BArrayStore.
52  *  |
53  *  +- <+> states (Collection of BArrayState's):
54  *  |   |  Each represents an array added by the user of this API.
55  *  |   |  and references a chunk_list (each state is a chunk_list user).
56  *  |   |  Note that the list order has no significance.
57  *  |   |
58  *  |   +- <+> chunk_list (BChunkList):
59  *  |       |  The chunks that make up this state.
60  *  |       |  Each state is a chunk_list user,
61  *  |       |  avoids duplicating lists when there is no change between states.
62  *  |       |
63  *  |       +- chunk_refs (List of BChunkRef): Each chunk_ref links to a a BChunk.
64  *  |          Each reference is a chunk user,
65  *  |          avoids duplicating smaller chunks of memory found in multiple states.
66  *  |
67  *  +- info (BArrayInfo):
68  *  |  Sizes and offsets for this array-store.
69  *  |  Also caches some variables for reuse.
70  *  |
71  *  +- <+> memory (BArrayMemory):
72  *      |  Memory pools for storing BArrayStore data.
73  *      |
74  *      +- chunk_list (Pool of BChunkList):
75  *      |  All chunk_lists, (reference counted, used by BArrayState).
76  *      |
77  *      +- chunk_ref (Pool of BChunkRef):
78  *      |  All chunk_refs (link between BChunkList & BChunk).
79  *      |
80  *      +- chunks (Pool of BChunk):
81  *         All chunks, (reference counted, used by BChunkList).
82  *         These have their headers hashed for reuse so we can quickly check for duplicates.
83  * </pre>
84  *
85  *
86  * De-Duplication
87  * --------------
88  *
89  * When creating a new state, a previous state can be given as a reference,
90  * matching chunks from this state are re-used in the new state.
91  *
92  * First matches at either end of the array are detected.
93  * For identical arrays this is all thats needed.
94  *
95  * De-duplication is performed on any remaining chunks, by hashing the first few bytes of the chunk
96  * (see: BCHUNK_HASH_TABLE_ACCUMULATE_STEPS).
97  *
98  * \note This is cached for reuse since the referenced data never changes.
99  *
100  * An array is created to store hash values at every 'stride',
101  * then stepped over to search for matching chunks.
102  *
103  * Once a match is found, there is a high chance next chunks match too,
104  * so this is checked to avoid performing so many hash-lookups.
105  * Otherwise new chunks are created.
106  */
107
108 #include <stdlib.h>
109 #include <string.h>
110
111 #include "MEM_guardedalloc.h"
112
113 #include "BLI_listbase.h"
114 #include "BLI_mempool.h"
115
116 #include "BLI_strict_flags.h"
117
118 #include "BLI_array_store.h"  /* own include */
119
120 /* only for BLI_array_store_is_valid */
121 #include "BLI_ghash.h"
122
123 /** \name Defines
124  *
125  * Some of the logic for merging is quite involved,
126  * support disabling some parts of this.
127  * \{ */
128
129 /* Scan first chunks (happy path when beginning of the array matches).
130  * When the array is a perfect match, we can re-use the entire list.
131  *
132  * Note that disabling makes some tests fail that check for output-size.
133  */
134 #define USE_FASTPATH_CHUNKS_FIRST
135
136 /* Scan last chunks (happy path when end of the array matches).
137  * When the end of the array matches, we can quickly add these chunks.
138  * note that we will add contiguous matching chunks
139  * so this isn't as useful as USE_FASTPATH_CHUNKS_FIRST,
140  * however it avoids adding matching chunks into the lookup table,
141  * so creating the lookup table won't be as expensive.
142  */
143 #ifdef USE_FASTPATH_CHUNKS_FIRST
144 #  define USE_FASTPATH_CHUNKS_LAST
145 #endif
146
147 /* For arrays of matching length, test that *enough* of the chunks are aligned,
148  * and simply step over both arrays, using matching chunks.
149  * This avoids overhead of using a lookup table for cases when we can assume they're mostly aligned.
150  */
151 #define USE_ALIGN_CHUNKS_TEST
152
153 /* Accumulate hashes from right to left so we can create a hash for the chunk-start.
154  * This serves to increase uniqueness and will help when there is many values which are the same.
155  */
156 #define USE_HASH_TABLE_ACCUMULATE
157
158 #ifdef USE_HASH_TABLE_ACCUMULATE
159 /* Number of times to propagate hashes back.
160  * Effectively a 'triangle-number'.
161  * so 4 -> 7, 5 -> 10, 6 -> 15... etc.
162  */
163 #  define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS 4
164 #else
165 /* How many items to hash (multiplied by stride)
166  */
167 #  define BCHUNK_HASH_LEN 4
168 #endif
169
170 /* Calculate the key once and reuse it
171  */
172 #define USE_HASH_TABLE_KEY_CACHE
173 #ifdef USE_HASH_TABLE_KEY_CACHE
174 #  define HASH_TABLE_KEY_UNSET    ((uint64_t)-1)
175 #  define HASH_TABLE_KEY_FALLBACK ((uint64_t)-2)
176 #endif
177
178 /* How much larger the table is then the total number of chunks.
179  */
180 #define BCHUNK_HASH_TABLE_MUL 3
181
182 /* Merge too small/large chunks:
183  *
184  * Using this means chunks below a threshold will be merged together.
185  * Even though short term this uses more memory,
186  * long term the overhead of maintaining many small chunks is reduced.
187  * This is defined by setting the minimum chunk size (as a fraction of the regular chunk size).
188  *
189  * Chunks may also become too large (when incrementally growing an array),
190  * this also enables chunk splitting.
191  */
192 #define USE_MERGE_CHUNKS
193
194 #ifdef USE_MERGE_CHUNKS
195 /* Merge chunks smaller then: (chunk_size / BCHUNK_MIN_SIZE_DIV)
196  */
197 #  define BCHUNK_SIZE_MIN_DIV 8
198
199 /* Disallow chunks bigger then the regular chunk size scaled by this value
200  * note: must be at least 2!
201  * however, this code runs wont run in tests unless its ~1.1 ugh.
202  * so lower only to check splitting works.
203  */
204 #  define BCHUNK_SIZE_MAX_MUL 2
205 #endif  /* USE_MERGE_CHUNKS */
206
207 /* slow (keep disabled), but handy for debugging */
208 // #define USE_VALIDATE_LIST_SIZE
209
210 // #define USE_VALIDATE_LIST_DATA_PARTIAL
211
212 // #define USE_PARANOID_CHECKS
213
214 /** \} */
215
216
217 /** \name Internal Structs
218  * \{ */
219
220 typedef uint64_t hash_key;
221
222
223 typedef struct BArrayInfo {
224         size_t chunk_stride;
225         // uint chunk_count;  /* UNUSED (other values are derived from this) */
226
227         /* pre-calculated */
228         size_t chunk_byte_size;
229         /* min/max limits (inclusive) */
230         size_t chunk_byte_size_min;
231         size_t chunk_byte_size_max;
232
233         size_t accum_read_ahead_bytes;
234 #ifdef USE_HASH_TABLE_ACCUMULATE
235         size_t accum_steps;
236         size_t accum_read_ahead_len;
237 #endif
238 } BArrayInfo;
239
240 typedef struct BArrayMemory {
241         BLI_mempool *chunk_list;  /* BChunkList */
242         BLI_mempool *chunk_ref;   /* BChunkRef */
243         BLI_mempool *chunk;       /* BChunk */
244 } BArrayMemory;
245
246 /**
247  * Main storage for all states
248  */
249 struct BArrayStore {
250         /* static */
251         BArrayInfo info;
252
253         /* memory storage */
254         BArrayMemory memory;
255
256         /**
257          * #BArrayState may be in any order (logic should never depend on state order).
258          */
259         ListBase states;
260 };
261
262 /**
263  * A single instance of an array.
264  *
265  * This is how external API's hold a reference to an in-memory state,
266  * although the struct is private.
267  *
268  * \note Currently each 'state' is allocated separately.
269  * While this could be moved to a memory pool,
270  * it makes it easier to trace invalid usage, so leave as-is for now.
271  */
272 struct BArrayState {
273         /** linked list in #BArrayStore.states */
274         struct BArrayState *next, *prev;
275
276         struct BChunkList *chunk_list;  /* BChunkList's */
277
278 };
279
280 typedef struct BChunkList {
281         ListBase chunk_refs;      /* BChunkRef's */
282         uint     chunk_refs_len;  /* BLI_listbase_count(chunks), store for reuse. */
283         size_t   total_size;      /* size of all chunks */
284
285         /** number of #BArrayState using this. */
286         int      users;
287 } BChunkList;
288
289 /* a chunk of an array */
290 typedef struct BChunk {
291         const uchar *data;
292         size_t       data_len;
293         /** number of #BChunkList using this. */
294         int          users;
295
296 #ifdef USE_HASH_TABLE_KEY_CACHE
297         hash_key key;
298 #endif
299 } BChunk;
300
301 /**
302  * Links to store #BChunk data in #BChunkList.chunk_refs.
303  */
304 typedef struct BChunkRef {
305         struct BChunkRef *next, *prev;
306         BChunk *link;
307 } BChunkRef;
308
309 /**
310  * Single linked list used when putting chunks into a temporary table,
311  * used for lookups.
312  *
313  * Point to the #BChunkRef, not the #BChunk,
314  * to allow talking down the chunks in-order until a mis-match is found,
315  * this avoids having to do so many table lookups.
316  */
317 typedef struct BTableRef {
318         struct BTableRef *next;
319         const BChunkRef *cref;
320 } BTableRef;
321
322 /** \} */
323
324
325 static size_t bchunk_list_size(const BChunkList *chunk_list);
326
327
328 /** \name Internal BChunk API
329  * \{ */
330
331 static BChunk *bchunk_new(
332         BArrayMemory *bs_mem, const uchar *data, const size_t data_len)
333 {
334         BChunk *chunk = BLI_mempool_alloc(bs_mem->chunk);
335         chunk->data     = data;
336         chunk->data_len = data_len;
337         chunk->users = 0;
338 #ifdef USE_HASH_TABLE_KEY_CACHE
339         chunk->key = HASH_TABLE_KEY_UNSET;
340 #endif
341         return chunk;
342 }
343
344 static BChunk *bchunk_new_copydata(
345         BArrayMemory *bs_mem, const uchar *data, const size_t data_len)
346 {
347         uchar *data_copy = MEM_mallocN(data_len, __func__);
348         memcpy(data_copy, data, data_len);
349         return bchunk_new(bs_mem, data_copy, data_len);
350 }
351
352 static void bchunk_decref(
353         BArrayMemory *bs_mem, BChunk *chunk)
354 {
355         BLI_assert(chunk->users > 0);
356         if (chunk->users == 1) {
357                 MEM_freeN((void *)chunk->data);
358                 BLI_mempool_free(bs_mem->chunk, chunk);
359         }
360         else {
361                 chunk->users -= 1;
362         }
363 }
364
365 static bool bchunk_data_compare(
366         const BChunk *chunk,
367         const uchar *data_base, const size_t data_base_len,
368         const size_t offset)
369 {
370         if (offset + (size_t)chunk->data_len <= data_base_len) {
371                 return (memcmp(&data_base[offset], chunk->data, chunk->data_len) == 0);
372         }
373         else {
374                 return false;
375         }
376 }
377
378 /** \} */
379
380
381 /** \name Internal BChunkList API
382  * \{ */
383
384 static BChunkList *bchunk_list_new(
385         BArrayMemory *bs_mem, size_t total_size)
386 {
387         BChunkList *chunk_list = BLI_mempool_alloc(bs_mem->chunk_list);
388
389         BLI_listbase_clear(&chunk_list->chunk_refs);
390         chunk_list->chunk_refs_len = 0;
391         chunk_list->total_size = total_size;
392         chunk_list->users = 0;
393         return chunk_list;
394 }
395
396 static void bchunk_list_decref(
397         BArrayMemory *bs_mem, BChunkList *chunk_list)
398 {
399         BLI_assert(chunk_list->users > 0);
400         if (chunk_list->users == 1) {
401                 for (BChunkRef *cref = chunk_list->chunk_refs.first, *cref_next; cref; cref = cref_next) {
402                         cref_next = cref->next;
403                         bchunk_decref(bs_mem, cref->link);
404                         BLI_mempool_free(bs_mem->chunk_ref, cref);
405                 }
406
407                 BLI_mempool_free(bs_mem->chunk_list, chunk_list);
408         }
409         else {
410                 chunk_list->users -= 1;
411         }
412 }
413
414 #ifdef USE_VALIDATE_LIST_SIZE
415 #  ifndef NDEBUG
416 #    define ASSERT_CHUNKLIST_SIZE(chunk_list, n) BLI_assert(bchunk_list_size(chunk_list) == n)
417 #  endif
418 #endif
419 #ifndef ASSERT_CHUNKLIST_SIZE
420 #  define ASSERT_CHUNKLIST_SIZE(chunk_list, n) (EXPR_NOP(chunk_list), EXPR_NOP(n))
421 #endif
422
423
424 #ifdef USE_VALIDATE_LIST_DATA_PARTIAL
425 static size_t bchunk_list_data_check(
426         const BChunkList *chunk_list, const uchar *data)
427 {
428         size_t offset = 0;
429         for (BChunkRef *cref = chunk_list->chunk_refs.first; cref; cref = cref->next) {
430                 if (memcmp(&data[offset], cref->link->data, cref->link->data_len) != 0) {
431                         return false;
432                 }
433                 offset += cref->link->data_len;
434         }
435         return true;
436 }
437 #  define ASSERT_CHUNKLIST_DATA(chunk_list, data) BLI_assert(bchunk_list_data_check(chunk_list, data))
438 #else
439 #  define ASSERT_CHUNKLIST_DATA(chunk_list, data) (EXPR_NOP(chunk_list), EXPR_NOP(data))
440 #endif
441
442
443 #ifdef USE_MERGE_CHUNKS
444 static void bchunk_list_ensure_min_size_last(
445         const BArrayInfo *info, BArrayMemory *bs_mem,
446         BChunkList *chunk_list)
447 {
448         BChunkRef *cref = chunk_list->chunk_refs.last;
449         if (cref && cref->prev) {
450                 /* both are decref'd after use (end of this block) */
451                 BChunk *chunk_curr = cref->link;
452                 BChunk *chunk_prev = cref->prev->link;
453
454                 if (MIN2(chunk_prev->data_len, chunk_curr->data_len) < info->chunk_byte_size_min) {
455                         const size_t data_merge_len = chunk_prev->data_len + chunk_curr->data_len;
456                         /* we could pass, but no need */
457                         if (data_merge_len <= info->chunk_byte_size_max) {
458                                 /* we have enough space to merge */
459
460                                 /* remove last from linklist */
461                                 BLI_assert(chunk_list->chunk_refs.last != chunk_list->chunk_refs.first);
462                                 cref->prev->next = NULL;
463                                 chunk_list->chunk_refs.last = cref->prev;
464                                 chunk_list->chunk_refs_len -= 1;
465
466                                 uchar *data_merge   = MEM_mallocN(data_merge_len, __func__);
467                                 memcpy(data_merge,                        chunk_prev->data, chunk_prev->data_len);
468                                 memcpy(&data_merge[chunk_prev->data_len], chunk_curr->data, chunk_curr->data_len);
469
470                                 cref->prev->link = bchunk_new(bs_mem, data_merge, data_merge_len);
471                                 cref->prev->link->users += 1;
472
473                                 BLI_mempool_free(bs_mem->chunk_ref, cref);
474                         }
475                         else {
476                                 /* If we always merge small slices, we should _almost_ never end up having very large chunks.
477                                  * Gradual expanding on contracting will cause this.
478                                  *
479                                  * if we do, the code below works (test by setting 'BCHUNK_SIZE_MAX_MUL = 1.2') */
480
481                                 /* keep chunk on the left hand side a regular size */
482                                 const size_t split = info->chunk_byte_size;
483
484                                 /* merge and split */
485                                 const size_t data_prev_len = split;
486                                 const size_t data_curr_len = data_merge_len - split;
487                                 uchar *data_prev = MEM_mallocN(data_prev_len, __func__);
488                                 uchar *data_curr = MEM_mallocN(data_curr_len, __func__);
489
490                                 if (data_prev_len <= chunk_prev->data_len) {
491                                         const size_t data_curr_shrink_len = chunk_prev->data_len - data_prev_len;
492
493                                         /* setup 'data_prev' */
494                                         memcpy(data_prev, chunk_prev->data, data_prev_len);
495
496                                         /* setup 'data_curr' */
497                                         memcpy(data_curr,                        &chunk_prev->data[data_prev_len], data_curr_shrink_len);
498                                         memcpy(&data_curr[data_curr_shrink_len],  chunk_curr->data, chunk_curr->data_len);
499                                 }
500                                 else {
501                                         BLI_assert(data_curr_len <= chunk_curr->data_len);
502                                         BLI_assert(data_prev_len >= chunk_prev->data_len);
503
504                                         const size_t data_prev_grow_len = data_prev_len - chunk_prev->data_len;
505
506                                         /* setup 'data_prev' */
507                                         memcpy(data_prev,                        chunk_prev->data, chunk_prev->data_len);
508                                         memcpy(&data_prev[chunk_prev->data_len], chunk_curr->data, data_prev_grow_len);
509
510                                         /* setup 'data_curr' */
511                                         memcpy(data_curr, &chunk_curr->data[data_prev_grow_len], data_curr_len);
512                                 }
513
514                                 cref->prev->link = bchunk_new(bs_mem, data_prev, data_prev_len);
515                                 cref->prev->link->users += 1;
516
517                                 cref->link = bchunk_new(bs_mem, data_curr, data_curr_len);
518                                 cref->link->users += 1;
519                         }
520
521                         /* free zero users */
522                         bchunk_decref(bs_mem, chunk_curr);
523                         bchunk_decref(bs_mem, chunk_prev);
524                 }
525         }
526 }
527 #endif  /* USE_MERGE_CHUNKS */
528
529
530 /**
531  * Split length into 2 values
532  * \param r_data_trim_len: Length which is aligned to the #BArrayInfo.chunk_byte_size
533  * \param r_data_last_chunk_len: The remaining bytes.
534  *
535  * \note This function ensures the size of \a r_data_last_chunk_len
536  * is larger than #BArrayInfo.chunk_byte_size_min.
537  */
538 static void bchunk_list_calc_trim_len(
539         const BArrayInfo *info, const size_t data_len,
540         size_t *r_data_trim_len, size_t *r_data_last_chunk_len)
541 {
542         size_t data_last_chunk_len = 0;
543         size_t data_trim_len = data_len;
544
545 #ifdef USE_MERGE_CHUNKS
546         /* avoid creating too-small chunks
547          * more efficient then merging after */
548         if (data_len > info->chunk_byte_size) {
549                 data_last_chunk_len = (data_trim_len % info->chunk_byte_size);
550                 data_trim_len = data_trim_len - data_last_chunk_len;
551                 if (data_last_chunk_len) {
552                         if (data_last_chunk_len < info->chunk_byte_size_min) {
553                                 /* may be zero and thats OK */
554                                 data_trim_len -= info->chunk_byte_size;
555                                 data_last_chunk_len += info->chunk_byte_size;
556                         }
557                 }
558         }
559         else {
560                 data_trim_len = 0;
561                 data_last_chunk_len = data_len;
562         }
563
564         BLI_assert((data_trim_len == 0) || (data_trim_len >= info->chunk_byte_size));
565 #else
566         data_last_chunk_len = (data_trim_len % info->chunk_byte_size);
567         data_trim_len = data_trim_len - data_last_chunk_len;
568 #endif
569
570         BLI_assert(data_trim_len + data_last_chunk_len == data_len);
571
572         *r_data_trim_len = data_trim_len;
573         *r_data_last_chunk_len = data_last_chunk_len;
574 }
575
576 /**
577  * Append and don't manage merging small chunks.
578  */
579 static void bchunk_list_append_only(
580         BArrayMemory *bs_mem,
581         BChunkList *chunk_list, BChunk *chunk)
582 {
583         BChunkRef *cref = BLI_mempool_alloc(bs_mem->chunk_ref);
584         BLI_addtail(&chunk_list->chunk_refs, cref);
585         cref->link = chunk;
586         chunk_list->chunk_refs_len += 1;
587         chunk->users += 1;
588 }
589
590 /**
591  * \note This is for writing single chunks,
592  * use #bchunk_list_append_data_n when writing large blocks of memory into many chunks.
593  */
594 static void bchunk_list_append_data(
595         const BArrayInfo *info, BArrayMemory *bs_mem,
596         BChunkList *chunk_list,
597         const uchar *data, const size_t data_len)
598 {
599         BLI_assert(data_len != 0);
600
601 #ifdef USE_MERGE_CHUNKS
602         BLI_assert(data_len <= info->chunk_byte_size_max);
603
604         if (!BLI_listbase_is_empty(&chunk_list->chunk_refs)) {
605                 BChunkRef *cref = chunk_list->chunk_refs.last;
606                 BChunk *chunk_prev = cref->link;
607
608                 if (MIN2(chunk_prev->data_len, data_len) < info->chunk_byte_size_min) {
609                         const size_t data_merge_len = chunk_prev->data_len + data_len;
610                         /* realloc for single user */
611                         if (cref->link->users == 1) {
612                                 uchar *data_merge = MEM_reallocN((void *)cref->link->data, data_merge_len);
613                                 memcpy(&data_merge[chunk_prev->data_len], data, data_len);
614                                 cref->link->data     = data_merge;
615                                 cref->link->data_len = data_merge_len;
616                         }
617                         else {
618                                 uchar *data_merge = MEM_mallocN(data_merge_len, __func__);
619                                 memcpy(data_merge, chunk_prev->data, chunk_prev->data_len);
620                                 memcpy(&data_merge[chunk_prev->data_len], data, data_len);
621                                 cref->link = bchunk_new(bs_mem, data_merge, data_merge_len);
622                                 cref->link->users += 1;
623                                 bchunk_decref(bs_mem, chunk_prev);
624                         }
625                         return;
626                 }
627         }
628 #else
629         UNUSED_VARS(info);
630 #endif  /* USE_MERGE_CHUNKS */
631
632         BChunk *chunk = bchunk_new_copydata(bs_mem, data, data_len);
633         bchunk_list_append_only(bs_mem, chunk_list, chunk);
634
635         /* don't run this, instead preemptively avoid creating a chunk only to merge it (above). */
636 #if 0
637 #ifdef USE_MERGE_CHUNKS
638         bchunk_list_ensure_min_size_last(info, bs_mem, chunk_list);
639 #endif
640 #endif
641 }
642
643 /**
644  * Similar to #bchunk_list_append_data, but handle multiple chunks.
645  * Use for adding arrays of arbitrary sized memory at once.
646  *
647  * \note This function takes care not to perform redundant chunk-merging checks,
648  * so we can write successive fixed size chunks quickly.
649  */
650 static void bchunk_list_append_data_n(
651         const BArrayInfo *info, BArrayMemory *bs_mem,
652         BChunkList *chunk_list,
653         const uchar *data, size_t data_len)
654 {
655         size_t data_trim_len, data_last_chunk_len;
656         bchunk_list_calc_trim_len(info, data_len, &data_trim_len, &data_last_chunk_len);
657
658         if (data_trim_len != 0) {
659                 size_t i_prev;
660
661                 {
662                         const size_t i = info->chunk_byte_size;
663                         bchunk_list_append_data(info, bs_mem, chunk_list, data, i);
664                         i_prev = i;
665                 }
666
667                 while (i_prev != data_trim_len) {
668                         const size_t i = i_prev + info->chunk_byte_size;
669                         BChunk *chunk = bchunk_new_copydata(bs_mem, &data[i_prev], i - i_prev);
670                         bchunk_list_append_only(bs_mem, chunk_list, chunk);
671                         i_prev = i;
672                 }
673
674                 if (data_last_chunk_len) {
675                         BChunk *chunk = bchunk_new_copydata(bs_mem, &data[i_prev], data_last_chunk_len);
676                         bchunk_list_append_only(bs_mem, chunk_list, chunk);
677                         // i_prev = data_len;  /* UNUSED */
678                 }
679         }
680         else {
681                 /* if we didn't write any chunks previously,
682                  * we may need to merge with the last. */
683                 if (data_last_chunk_len) {
684                         bchunk_list_append_data(info, bs_mem, chunk_list, data, data_last_chunk_len);
685                         // i_prev = data_len;  /* UNUSED */
686                 }
687         }
688
689 #ifdef USE_MERGE_CHUNKS
690         if (data_len > info->chunk_byte_size) {
691                 BLI_assert(((BChunkRef *)chunk_list->chunk_refs.last)->link->data_len >= info->chunk_byte_size_min);
692         }
693 #endif
694 }
695
696 static void bchunk_list_append(
697         const BArrayInfo *info, BArrayMemory *bs_mem,
698         BChunkList *chunk_list,
699         BChunk *chunk)
700 {
701         bchunk_list_append_only(bs_mem, chunk_list, chunk);
702
703 #ifdef USE_MERGE_CHUNKS
704         bchunk_list_ensure_min_size_last(info, bs_mem, chunk_list);
705 #else
706         UNUSED_VARS(info);
707 #endif
708 }
709
710 static void bchunk_list_fill_from_array(
711         const BArrayInfo *info, BArrayMemory *bs_mem,
712         BChunkList *chunk_list,
713         const uchar *data,
714         const size_t data_len)
715 {
716         BLI_assert(BLI_listbase_is_empty(&chunk_list->chunk_refs));
717
718         size_t data_trim_len, data_last_chunk_len;
719         bchunk_list_calc_trim_len(info, data_len, &data_trim_len, &data_last_chunk_len);
720
721         size_t i_prev = 0;
722         while (i_prev != data_trim_len) {
723                 const size_t i = i_prev + info->chunk_byte_size;
724                 BChunk *chunk = bchunk_new_copydata(bs_mem, &data[i_prev], i - i_prev);
725                 bchunk_list_append_only(bs_mem, chunk_list, chunk);
726                 i_prev = i;
727         }
728
729         if (data_last_chunk_len) {
730                 BChunk *chunk = bchunk_new_copydata(bs_mem, &data[i_prev], data_last_chunk_len);
731                 bchunk_list_append_only(bs_mem, chunk_list, chunk);
732                 // i_prev = data_len;
733         }
734
735 #ifdef USE_MERGE_CHUNKS
736         if (data_len > info->chunk_byte_size) {
737                 BLI_assert(((BChunkRef *)chunk_list->chunk_refs.last)->link->data_len >= info->chunk_byte_size_min);
738         }
739 #endif
740
741         /* works but better avoid redundant re-alloc */
742 #if 0
743 #ifdef USE_MERGE_CHUNKS
744         bchunk_list_ensure_min_size_last(info, bs_mem, chunk_list);
745 #endif
746 #endif
747
748         ASSERT_CHUNKLIST_SIZE(chunk_list, data_len);
749         ASSERT_CHUNKLIST_DATA(chunk_list, data);
750 }
751
752 /** \} */
753
754 /* ---------------------------------------------------------------------------
755  * Internal Table Lookup Functions
756  */
757
758 /** \name Internal Hashing/De-Duplication API
759  *
760  * Only used by #bchunk_list_from_data_merge
761  * \{ */
762
763 #define HASH_INIT (5381)
764
765 BLI_INLINE uint hash_data_single(const uchar p)
766 {
767         return ((HASH_INIT << 5) + HASH_INIT) + (unsigned int)(*((signed char *)&p));
768 }
769
770 /* hash bytes, from BLI_ghashutil_strhash_n */
771 static uint hash_data(const uchar *key, size_t n)
772 {
773         const signed char *p;
774         unsigned int h = HASH_INIT;
775
776         for (p = (const signed char *)key; n--; p++) {
777                 h = ((h << 5) + h) + (unsigned int)*p;
778         }
779
780         return h;
781 }
782
783 #undef HASH_INIT
784
785
786 #ifdef USE_HASH_TABLE_ACCUMULATE
787 static void hash_array_from_data(
788         const BArrayInfo *info, const uchar *data_slice, const size_t data_slice_len,
789         hash_key *hash_array)
790 {
791         if (info->chunk_stride != 1) {
792                 for (size_t i = 0, i_step = 0; i_step < data_slice_len; i++, i_step += info->chunk_stride) {
793                         hash_array[i] = hash_data(&data_slice[i_step], info->chunk_stride);
794                 }
795         }
796         else {
797                 /* fast-path for bytes */
798                 for (size_t i = 0; i < data_slice_len; i++) {
799                         hash_array[i] = hash_data_single(data_slice[i]);
800                 }
801         }
802 }
803
804 /*
805  * Similar to hash_array_from_data,
806  * but able to step into the next chunk if we run-out of data.
807  */
808 static void hash_array_from_cref(
809         const BArrayInfo *info, const BChunkRef *cref, const size_t data_len,
810         hash_key *hash_array)
811 {
812         const size_t hash_array_len = data_len / info->chunk_stride;
813         size_t i = 0;
814         do {
815                 size_t i_next = hash_array_len - i;
816                 size_t data_trim_len = i_next * info->chunk_stride;
817                 if (data_trim_len > cref->link->data_len) {
818                         data_trim_len = cref->link->data_len;
819                         i_next = data_trim_len / info->chunk_stride;
820                 }
821                 BLI_assert(data_trim_len <= cref->link->data_len);
822                 hash_array_from_data(info, cref->link->data, data_trim_len, &hash_array[i]);
823                 i += i_next;
824                 cref = cref->next;
825         } while ((i < hash_array_len) && (cref != NULL));
826
827         /* If this isn't equal, the caller didn't properly check
828          * that there was enough data left in all chunks */
829         BLI_assert(i == hash_array_len);
830 }
831
832 static void hash_accum(hash_key *hash_array, const size_t hash_array_len, size_t iter_steps)
833 {
834         /* _very_ unlikely, can happen if you select a chunk-size of 1 for example. */
835         if (UNLIKELY((iter_steps > hash_array_len))) {
836                 iter_steps = hash_array_len;
837         }
838
839         const size_t hash_array_search_len = hash_array_len - iter_steps;
840         while (iter_steps != 0) {
841                 const size_t hash_offset = iter_steps;
842                 for (uint i = 0; i < hash_array_search_len; i++) {
843                         hash_array[i] += (hash_array[i + hash_offset]) * ((hash_array[i] & 0xff) + 1);
844                 }
845                 iter_steps -= 1;
846         }
847 }
848
849 /**
850  * When we only need a single value, can use a small optimization.
851  * we can avoid accumulating the tail of the array a little, each iteration.
852  */
853 static void hash_accum_single(hash_key *hash_array, const size_t hash_array_len, size_t iter_steps)
854 {
855         BLI_assert(iter_steps <= hash_array_len);
856         if (UNLIKELY(!(iter_steps <= hash_array_len))) {
857                 /* while this shouldn't happen, avoid crashing */
858                 iter_steps = hash_array_len;
859         }
860         /* We can increase this value each step to avoid accumulating quite as much
861          * while getting the same results as hash_accum */
862         size_t iter_steps_sub = iter_steps;
863
864         while (iter_steps != 0) {
865                 const size_t hash_array_search_len = hash_array_len - iter_steps_sub;
866                 const size_t hash_offset = iter_steps;
867                 for (uint i = 0; i < hash_array_search_len; i++) {
868                         hash_array[i] += (hash_array[i + hash_offset]) * ((hash_array[i] & 0xff) + 1);
869                 }
870                 iter_steps -= 1;
871                 iter_steps_sub += iter_steps;
872         }
873 }
874
875 static hash_key key_from_chunk_ref(
876         const BArrayInfo *info, const BChunkRef *cref,
877         /* avoid reallocating each time */
878         hash_key *hash_store, const size_t hash_store_len)
879 {
880         /* in C, will fill in a reusable array */
881         BChunk *chunk = cref->link;
882         BLI_assert((info->accum_read_ahead_bytes * info->chunk_stride) != 0);
883
884         if (info->accum_read_ahead_bytes <= chunk->data_len) {
885                 hash_key key;
886
887 #ifdef USE_HASH_TABLE_KEY_CACHE
888                 key = chunk->key;
889                 if (key != HASH_TABLE_KEY_UNSET) {
890                         /* Using key cache!
891                          * avoids calculating every time */
892                 }
893                 else {
894                         hash_array_from_cref(info, cref, info->accum_read_ahead_bytes, hash_store);
895                         hash_accum_single(hash_store, hash_store_len, info->accum_steps);
896                         key = hash_store[0];
897
898                         /* cache the key */
899                         if (UNLIKELY(key == HASH_TABLE_KEY_UNSET)) {
900                                 key = HASH_TABLE_KEY_FALLBACK;
901                         }
902                         chunk->key = key;
903                 }
904 #else
905                 hash_array_from_cref(info, cref, info->accum_read_ahead_bytes, hash_store);
906                 hash_accum_single(hash_store, hash_store_len, info->accum_steps);
907                 key = hash_store[0];
908 #endif
909                 return key;
910         }
911         else {
912                 /* corner case - we're too small, calculate the key each time. */
913
914                 hash_array_from_cref(info, cref, info->accum_read_ahead_bytes, hash_store);
915                 hash_accum_single(hash_store, hash_store_len, info->accum_steps);
916                 hash_key key = hash_store[0];
917
918 #ifdef USE_HASH_TABLE_KEY_CACHE
919                 if (UNLIKELY(key == HASH_TABLE_KEY_UNSET)) {
920                         key = HASH_TABLE_KEY_FALLBACK;
921                 }
922 #endif
923                 return key;
924         }
925 }
926
927 static const BChunkRef *table_lookup(
928         const BArrayInfo *info, BTableRef **table, const size_t table_len, const size_t i_table_start,
929         const uchar *data, const size_t data_len, const size_t offset, const hash_key *table_hash_array)
930 {
931         size_t size_left = data_len - offset;
932         hash_key key = table_hash_array[((offset - i_table_start) / info->chunk_stride)];
933         size_t key_index = (size_t)(key % (hash_key)table_len);
934         for (const BTableRef *tref = table[key_index]; tref; tref = tref->next) {
935                 const BChunkRef *cref = tref->cref;
936 #ifdef USE_HASH_TABLE_KEY_CACHE
937                 if (cref->link->key == key)
938 #endif
939                 {
940                         BChunk *chunk_test = cref->link;
941                         if (chunk_test->data_len <= size_left) {
942                                 if (bchunk_data_compare(chunk_test, data, data_len, offset)) {
943                                         /* we could remove the chunk from the table, to avoid multiple hits */
944                                         return cref;
945                                 }
946                         }
947                 }
948         }
949         return NULL;
950 }
951
952 #else  /* USE_HASH_TABLE_ACCUMULATE */
953
954 /* NON USE_HASH_TABLE_ACCUMULATE code (simply hash each chunk) */
955
956 static hash_key key_from_chunk_ref(const BArrayInfo *info, const BChunkRef *cref)
957 {
958         const size_t data_hash_len = BCHUNK_HASH_LEN * info->chunk_stride;
959         hash_key key;
960         BChunk *chunk = cref->link;
961
962 #ifdef USE_HASH_TABLE_KEY_CACHE
963         key = chunk->key;
964         if (key != HASH_TABLE_KEY_UNSET) {
965                 /* Using key cache!
966                  * avoids calculating every time */
967         }
968         else {
969                 /* cache the key */
970                 key = hash_data(chunk->data, data_hash_len);
971                 if (key == HASH_TABLE_KEY_UNSET) {
972                         key = HASH_TABLE_KEY_FALLBACK;
973                 }
974                 chunk->key = key;
975         }
976 #else
977         key = hash_data(chunk->data, data_hash_len);
978 #endif
979
980         return key;
981 }
982
983 static const BChunkRef *table_lookup(
984         const BArrayInfo *info, BTableRef **table, const size_t table_len, const uint UNUSED(i_table_start),
985         const uchar *data, const size_t data_len, const size_t offset, const hash_key *UNUSED(table_hash_array))
986 {
987         const size_t data_hash_len = BCHUNK_HASH_LEN * info->chunk_stride;  /* TODO, cache */
988
989         size_t size_left = data_len - offset;
990         hash_key key = hash_data(&data[offset], MIN2(data_hash_len, size_left));
991         size_t key_index = (size_t)(key % (hash_key)table_len);
992         for (BTableRef *tref = table[key_index]; tref; tref = tref->next) {
993                 const BChunkRef *cref = tref->cref;
994 #ifdef USE_HASH_TABLE_KEY_CACHE
995                 if (cref->link->key == key)
996 #endif
997                 {
998                         BChunk *chunk_test = cref->link;
999                         if (chunk_test->data_len <= size_left) {
1000                                 if (bchunk_data_compare(chunk_test, data, data_len, offset)) {
1001                                         /* we could remove the chunk from the table, to avoid multiple hits */
1002                                         return cref;
1003                                 }
1004                         }
1005                 }
1006         }
1007         return NULL;
1008 }
1009
1010 #endif  /* USE_HASH_TABLE_ACCUMULATE */
1011
1012 /* End Table Lookup
1013  * ---------------- */
1014
1015 /** \} */
1016
1017 /** \name Main Data De-Duplication Function
1018  *
1019  * \{ */
1020
1021 /**
1022  * \param data: Data to store in the returned value.
1023  * \param data_len_original: Length of data in bytes.
1024  * \param chunk_list_reference: Reuse this list or chunks within it, don't modify its content.
1025  * \note Caller is responsible for adding the user.
1026  */
1027 static BChunkList *bchunk_list_from_data_merge(
1028         const BArrayInfo *info, BArrayMemory *bs_mem,
1029         const uchar *data, const size_t data_len_original,
1030         const BChunkList *chunk_list_reference)
1031 {
1032         ASSERT_CHUNKLIST_SIZE(chunk_list_reference, chunk_list_reference->total_size);
1033
1034         /* -----------------------------------------------------------------------
1035          * Fast-Path for exact match
1036          * Check for exact match, if so, return the current list.
1037          */
1038
1039         const BChunkRef *cref_match_first = NULL;
1040
1041         uint chunk_list_reference_skip_len = 0;
1042         size_t chunk_list_reference_skip_bytes = 0;
1043         size_t i_prev = 0;
1044
1045 #ifdef USE_FASTPATH_CHUNKS_FIRST
1046         {
1047                 bool full_match = true;
1048
1049                 const BChunkRef *cref = chunk_list_reference->chunk_refs.first;
1050                 while (i_prev < data_len_original) {
1051                         if (cref != NULL && bchunk_data_compare(cref->link, data, data_len_original, i_prev)) {
1052                                 cref_match_first = cref;
1053                                 chunk_list_reference_skip_len += 1;
1054                                 chunk_list_reference_skip_bytes += cref->link->data_len;
1055                                 i_prev += cref->link->data_len;
1056                                 cref = cref->next;
1057                         }
1058                         else {
1059                                 full_match = false;
1060                                 break;
1061                         }
1062                 }
1063
1064                 if (full_match) {
1065                         if (chunk_list_reference->total_size == data_len_original) {
1066                                 return (BChunkList *)chunk_list_reference;
1067                         }
1068                 }
1069         }
1070
1071         /* End Fast-Path (first)
1072          * --------------------- */
1073
1074 #endif  /* USE_FASTPATH_CHUNKS_FIRST */
1075
1076         /* Copy until we have a mismatch */
1077         BChunkList *chunk_list = bchunk_list_new(bs_mem, data_len_original);
1078         if (cref_match_first != NULL) {
1079                 size_t chunk_size_step = 0;
1080                 const BChunkRef *cref = chunk_list_reference->chunk_refs.first;
1081                 while (true) {
1082                         BChunk *chunk = cref->link;
1083                         chunk_size_step += chunk->data_len;
1084                         bchunk_list_append_only(bs_mem, chunk_list, chunk);
1085                         ASSERT_CHUNKLIST_SIZE(chunk_list, chunk_size_step);
1086                         ASSERT_CHUNKLIST_DATA(chunk_list, data);
1087                         if (cref == cref_match_first) {
1088                                 break;
1089                         }
1090                         else {
1091                                 cref = cref->next;
1092                         }
1093                 }
1094                 /* happens when bytes are removed from the end of the array */
1095                 if (chunk_size_step == data_len_original) {
1096                         return chunk_list;
1097                 }
1098
1099                 i_prev = chunk_size_step;
1100         }
1101         else {
1102                 i_prev = 0;
1103         }
1104
1105         /* ------------------------------------------------------------------------
1106          * Fast-Path for end chunks
1107          *
1108          * Check for trailing chunks
1109          */
1110
1111         /* In this case use 'chunk_list_reference_last' to define the last index
1112          * index_match_last = -1 */
1113
1114         /* warning, from now on don't use len(data)
1115          * since we want to ignore chunks already matched */
1116         size_t data_len = data_len_original;
1117 #define data_len_original invalid_usage
1118 #ifdef data_len_original  /* quiet warning */
1119 #endif
1120
1121         const BChunkRef *chunk_list_reference_last = NULL;
1122
1123 #ifdef USE_FASTPATH_CHUNKS_LAST
1124         if (!BLI_listbase_is_empty(&chunk_list_reference->chunk_refs)) {
1125                 const BChunkRef *cref = chunk_list_reference->chunk_refs.last;
1126                 while ((cref->prev != NULL) &&
1127                        (cref != cref_match_first) &&
1128                        (cref->link->data_len <= data_len - i_prev))
1129                 {
1130                         BChunk *chunk_test = cref->link;
1131                         size_t offset = data_len - chunk_test->data_len;
1132                         if (bchunk_data_compare(chunk_test, data, data_len, offset)) {
1133                                 data_len = offset;
1134                                 chunk_list_reference_last = cref;
1135                                 chunk_list_reference_skip_len += 1;
1136                                 chunk_list_reference_skip_bytes += cref->link->data_len;
1137                                 cref = cref->prev;
1138                         }
1139                         else {
1140                                 break;
1141                         }
1142                 }
1143         }
1144
1145         /* End Fast-Path (last)
1146          * -------------------- */
1147 #endif  /* USE_FASTPATH_CHUNKS_LAST */
1148
1149         /* -----------------------------------------------------------------------
1150          * Check for aligned chunks
1151          *
1152          * This saves a lot of searching, so use simple heuristics to detect aligned arrays.
1153          * (may need to tweak exact method).
1154          */
1155
1156         bool use_aligned = false;
1157
1158 #ifdef USE_ALIGN_CHUNKS_TEST
1159         if (chunk_list->total_size == chunk_list_reference->total_size) {
1160                 /* if we're already a quarter aligned */
1161                 if (data_len - i_prev <= chunk_list->total_size / 4) {
1162                         use_aligned = true;
1163                 }
1164                 else {
1165                         /* TODO, walk over chunks and check if some arbitrary amount align */
1166                 }
1167         }
1168 #endif  /* USE_ALIGN_CHUNKS_TEST */
1169
1170         /* End Aligned Chunk Case
1171          * ----------------------- */
1172
1173         if (use_aligned) {
1174                 /* Copy matching chunks, creates using the same 'layout' as the reference */
1175                 const BChunkRef *cref = cref_match_first ? cref_match_first->next : chunk_list_reference->chunk_refs.first;
1176                 while (i_prev != data_len) {
1177                         const size_t i = i_prev + cref->link->data_len;
1178                         BLI_assert(i != i_prev);
1179
1180                         if ((cref != chunk_list_reference_last) &&
1181                             bchunk_data_compare(cref->link, data, data_len, i_prev))
1182                         {
1183                                 bchunk_list_append(info, bs_mem, chunk_list, cref->link);
1184                                 ASSERT_CHUNKLIST_SIZE(chunk_list, i);
1185                                 ASSERT_CHUNKLIST_DATA(chunk_list, data);
1186                         }
1187                         else {
1188                                 bchunk_list_append_data(info, bs_mem, chunk_list, &data[i_prev], i - i_prev);
1189                                 ASSERT_CHUNKLIST_SIZE(chunk_list, i);
1190                                 ASSERT_CHUNKLIST_DATA(chunk_list, data);
1191                         }
1192
1193                         cref = cref->next;
1194
1195                         i_prev = i;
1196                 }
1197         }
1198         else if ((data_len - i_prev >= info->chunk_byte_size) &&
1199                  (chunk_list_reference->chunk_refs_len >= chunk_list_reference_skip_len) &&
1200                  (chunk_list_reference->chunk_refs.first != NULL))
1201         {
1202
1203                 /* --------------------------------------------------------------------
1204                  * Non-Aligned Chunk De-Duplication */
1205
1206                 /* only create a table if we have at least one chunk to search
1207                  * otherwise just make a new one.
1208                  *
1209                  * Support re-arranged chunks */
1210
1211 #ifdef USE_HASH_TABLE_ACCUMULATE
1212                 size_t i_table_start = i_prev;
1213                 const size_t table_hash_array_len = (data_len - i_prev) / info->chunk_stride;
1214                 hash_key  *table_hash_array = MEM_mallocN(sizeof(*table_hash_array) * table_hash_array_len, __func__);
1215                 hash_array_from_data(info, &data[i_prev], data_len - i_prev, table_hash_array);
1216
1217                 hash_accum(table_hash_array, table_hash_array_len, info->accum_steps);
1218 #else
1219                 /* dummy vars */
1220                 uint i_table_start = 0;
1221                 hash_key *table_hash_array = NULL;
1222 #endif
1223
1224                 const uint chunk_list_reference_remaining_len =
1225                         (chunk_list_reference->chunk_refs_len - chunk_list_reference_skip_len) + 1;
1226                 BTableRef *table_ref_stack = MEM_mallocN(chunk_list_reference_remaining_len * sizeof(BTableRef), __func__);
1227                 uint       table_ref_stack_n = 0;
1228
1229                 const size_t table_len = chunk_list_reference_remaining_len * BCHUNK_HASH_TABLE_MUL;
1230                 BTableRef **table = MEM_callocN(table_len * sizeof(*table), __func__);
1231
1232                 /* table_make - inline
1233                  * include one matching chunk, to allow for repeating values */
1234                 {
1235 #ifdef USE_HASH_TABLE_ACCUMULATE
1236                         const size_t hash_store_len = info->accum_read_ahead_len;
1237                         hash_key *hash_store = MEM_mallocN(sizeof(hash_key) * hash_store_len, __func__);
1238 #endif
1239
1240                         const BChunkRef *cref;
1241                         size_t chunk_list_reference_bytes_remaining =
1242                                 chunk_list_reference->total_size - chunk_list_reference_skip_bytes;
1243
1244                         if (cref_match_first) {
1245                                 cref = cref_match_first;
1246                                 chunk_list_reference_bytes_remaining += cref->link->data_len;
1247                         }
1248                         else {
1249                                 cref = chunk_list_reference->chunk_refs.first;
1250                         }
1251
1252 #ifdef USE_PARANOID_CHECKS
1253                         {
1254                                 size_t test_bytes_len = 0;
1255                                 const BChunkRef *cr = cref;
1256                                 while (cr != chunk_list_reference_last) {
1257                                         test_bytes_len += cr->link->data_len;
1258                                         cr = cr->next;
1259                                 }
1260                                 BLI_assert(test_bytes_len == chunk_list_reference_bytes_remaining);
1261                         }
1262 #endif
1263
1264                         while ((cref != chunk_list_reference_last) &&
1265                                (chunk_list_reference_bytes_remaining >= info->accum_read_ahead_bytes))
1266                         {
1267                                 hash_key key = key_from_chunk_ref(info, cref
1268
1269 #ifdef USE_HASH_TABLE_ACCUMULATE
1270                                                                   , hash_store, hash_store_len
1271 #endif
1272                                                                   );
1273                                 size_t key_index = (size_t)(key % (hash_key)table_len);
1274                                 BTableRef *tref_prev = table[key_index];
1275                                 BLI_assert(table_ref_stack_n < chunk_list_reference_remaining_len);
1276                                 BTableRef *tref = &table_ref_stack[table_ref_stack_n++];
1277                                 tref->cref = cref;
1278                                 tref->next = tref_prev;
1279                                 table[key_index] = tref;
1280
1281                                 chunk_list_reference_bytes_remaining -= cref->link->data_len;
1282                                 cref = cref->next;
1283                         }
1284
1285                         BLI_assert(table_ref_stack_n <= chunk_list_reference_remaining_len);
1286
1287 #ifdef USE_HASH_TABLE_ACCUMULATE
1288                         MEM_freeN(hash_store);
1289 #endif
1290                 }
1291                 /* done making the table */
1292
1293                 BLI_assert(i_prev <= data_len);
1294                 for (size_t i = i_prev; i < data_len; ) {
1295                         /* Assumes exiting chunk isnt a match! */
1296
1297                         const BChunkRef *cref_found = table_lookup(
1298                                 info,
1299                                 table, table_len, i_table_start,
1300                                 data, data_len, i, table_hash_array);
1301                         if (cref_found != NULL) {
1302                                 BLI_assert(i < data_len);
1303                                 if (i != i_prev) {
1304                                         bchunk_list_append_data_n(info, bs_mem, chunk_list, &data[i_prev], i - i_prev);
1305                                         i_prev = i;
1306                                 }
1307
1308                                 /* now add the reference chunk */
1309                                 {
1310                                         BChunk *chunk_found = cref_found->link;
1311                                         i += chunk_found->data_len;
1312                                         bchunk_list_append(info, bs_mem, chunk_list, chunk_found);
1313                                 }
1314                                 i_prev = i;
1315                                 BLI_assert(i_prev <= data_len);
1316                                 ASSERT_CHUNKLIST_SIZE(chunk_list, i_prev);
1317                                 ASSERT_CHUNKLIST_DATA(chunk_list, data);
1318
1319                                 /* its likely that the next chunk in the list will be a match, so check it! */
1320                                 while ((cref_found->next != NULL) &&
1321                                        (cref_found->next != chunk_list_reference_last))
1322                                 {
1323                                         cref_found = cref_found->next;
1324                                         BChunk *chunk_found = cref_found->link;
1325
1326                                         if (bchunk_data_compare(chunk_found, data, data_len, i_prev)) {
1327                                                 /* may be useful to remove table data, assuming we dont have repeating memory
1328                                                  * where it would be useful to re-use chunks. */
1329                                                 i += chunk_found->data_len;
1330                                                 bchunk_list_append(info, bs_mem, chunk_list, chunk_found);
1331                                                 /* chunk_found may be freed! */
1332                                                 i_prev = i;
1333                                                 BLI_assert(i_prev <= data_len);
1334                                                 ASSERT_CHUNKLIST_SIZE(chunk_list, i_prev);
1335                                                 ASSERT_CHUNKLIST_DATA(chunk_list, data);
1336                                         }
1337                                         else {
1338                                                 break;
1339                                         }
1340                                 }
1341                         }
1342                         else {
1343                                 i = i + info->chunk_stride;
1344                         }
1345                 }
1346
1347 #ifdef USE_HASH_TABLE_ACCUMULATE
1348                 MEM_freeN(table_hash_array);
1349 #endif
1350                 MEM_freeN(table);
1351                 MEM_freeN(table_ref_stack);
1352
1353                 /* End Table Lookup
1354                  * ---------------- */
1355         }
1356
1357         ASSERT_CHUNKLIST_SIZE(chunk_list, i_prev);
1358         ASSERT_CHUNKLIST_DATA(chunk_list, data);
1359
1360         /* -----------------------------------------------------------------------
1361          * No Duplicates to copy, write new chunks
1362          *
1363          * Trailing chunks, no matches found in table lookup above.
1364          * Write all new data. */
1365         if (i_prev != data_len) {
1366                 bchunk_list_append_data_n(info, bs_mem, chunk_list, &data[i_prev], data_len - i_prev);
1367                 i_prev = data_len;
1368         }
1369
1370         BLI_assert(i_prev == data_len);
1371
1372 #ifdef USE_FASTPATH_CHUNKS_LAST
1373         if (chunk_list_reference_last != NULL) {
1374                 /* write chunk_list_reference_last since it hasn't been written yet */
1375                 const BChunkRef *cref = chunk_list_reference_last;
1376                 while (cref != NULL) {
1377                         BChunk *chunk = cref->link;
1378                         // BLI_assert(bchunk_data_compare(chunk, data, data_len, i_prev));
1379                         i_prev += chunk->data_len;
1380                         /* use simple since we assume the references chunks have already been sized correctly. */
1381                         bchunk_list_append_only(bs_mem, chunk_list, chunk);
1382                         ASSERT_CHUNKLIST_DATA(chunk_list, data);
1383                         cref = cref->next;
1384                 }
1385         }
1386 #endif
1387
1388 #undef data_len_original
1389
1390         BLI_assert(i_prev == data_len_original);
1391
1392         /* check we're the correct size and that we didn't accidentally modify the reference */
1393         ASSERT_CHUNKLIST_SIZE(chunk_list, data_len_original);
1394         ASSERT_CHUNKLIST_SIZE(chunk_list_reference, chunk_list_reference->total_size);
1395
1396         ASSERT_CHUNKLIST_DATA(chunk_list, data);
1397
1398         return chunk_list;
1399 }
1400 /* end private API */
1401
1402 /** \} */
1403
1404
1405 /** \name Main Array Storage API
1406  * \{ */
1407
1408
1409 /**
1410  * Create a new array store, which can store any number of arrays
1411  * as long as their stride matches.
1412  *
1413  * \param stride: ``sizeof()`` each element,
1414  *
1415  * \note while a stride of ``1`` will always work,
1416  * its less efficient since duplicate chunks of memory will be searched
1417  * at positions unaligned with the array data.
1418  *
1419  * \param chunk_count: Number of elements to split each chunk into.
1420  * - A small value increases the ability to de-duplicate chunks,
1421  *   but adds overhead by increasing the number of chunks to look-up when searching for duplicates,
1422  *   as well as some overhead constructing the original array again, with more calls to ``memcpy``.
1423  * - Larger values reduce the *book keeping* overhead,
1424  *   but increase the chance a small, isolated change will cause a larger amount of data to be duplicated.
1425  *
1426  * \return A new array store, to be freed with #BLI_array_store_destroy.
1427  */
1428 BArrayStore *BLI_array_store_create(
1429         uint stride,
1430         uint chunk_count)
1431 {
1432         BArrayStore *bs = MEM_callocN(sizeof(BArrayStore), __func__);
1433
1434         bs->info.chunk_stride = stride;
1435         // bs->info.chunk_count = chunk_count;
1436
1437         bs->info.chunk_byte_size = chunk_count * stride;
1438 #ifdef USE_MERGE_CHUNKS
1439         bs->info.chunk_byte_size_min = MAX2(1u, chunk_count / BCHUNK_SIZE_MIN_DIV) * stride;
1440         bs->info.chunk_byte_size_max = (chunk_count * BCHUNK_SIZE_MAX_MUL) * stride;
1441 #endif
1442
1443 #ifdef USE_HASH_TABLE_ACCUMULATE
1444         bs->info.accum_steps = BCHUNK_HASH_TABLE_ACCUMULATE_STEPS - 1;
1445         /* Triangle number, identifying now much read-ahead we need:
1446          * https://en.wikipedia.org/wiki/Triangular_number (+ 1) */
1447         bs->info.accum_read_ahead_len   = (uint)((((bs->info.accum_steps * (bs->info.accum_steps + 1))) / 2) + 1);
1448         bs->info.accum_read_ahead_bytes = bs->info.accum_read_ahead_len * stride;
1449 #else
1450         bs->info.accum_read_ahead_bytes = BCHUNK_HASH_LEN  * stride;
1451 #endif
1452
1453         bs->memory.chunk_list   = BLI_mempool_create(sizeof(BChunkList), 0, 512, BLI_MEMPOOL_NOP);
1454         bs->memory.chunk_ref    = BLI_mempool_create(sizeof(BChunkRef),  0, 512, BLI_MEMPOOL_NOP);
1455         /* allow iteration to simplify freeing, otherwise its not needed
1456          * (we could loop over all states as an alternative). */
1457         bs->memory.chunk        = BLI_mempool_create(sizeof(BChunk),     0, 512, BLI_MEMPOOL_ALLOW_ITER);
1458
1459         return bs;
1460 }
1461
1462 static void array_store_free_data(BArrayStore *bs)
1463 {
1464         /* free chunk data */
1465         {
1466                 BLI_mempool_iter iter;
1467                 BChunk *chunk;
1468                 BLI_mempool_iternew(bs->memory.chunk, &iter);
1469                 while ((chunk = BLI_mempool_iterstep(&iter))) {
1470                         BLI_assert(chunk->users > 0);
1471                         MEM_freeN((void *)chunk->data);
1472                 }
1473         }
1474
1475         /* free states */
1476         for (BArrayState *state = bs->states.first, *state_next; state; state = state_next) {
1477                 state_next = state->next;
1478                 MEM_freeN(state);
1479         }
1480 }
1481
1482 /**
1483  * Free the #BArrayStore, including all states and chunks.
1484  */
1485 void BLI_array_store_destroy(
1486         BArrayStore *bs)
1487 {
1488         array_store_free_data(bs);
1489
1490         BLI_mempool_destroy(bs->memory.chunk_list);
1491         BLI_mempool_destroy(bs->memory.chunk_ref);
1492         BLI_mempool_destroy(bs->memory.chunk);
1493
1494         MEM_freeN(bs);
1495 }
1496
1497 /**
1498  * Clear all contents, allowing reuse of \a bs.
1499  */
1500 void BLI_array_store_clear(
1501         BArrayStore *bs)
1502 {
1503         array_store_free_data(bs);
1504
1505         BLI_listbase_clear(&bs->states);
1506
1507         BLI_mempool_clear(bs->memory.chunk_list);
1508         BLI_mempool_clear(bs->memory.chunk_ref);
1509         BLI_mempool_clear(bs->memory.chunk);
1510 }
1511
1512 /** \} */
1513
1514 /** \name BArrayStore Statistics
1515  * \{ */
1516
1517 /**
1518  * \return the total amount of memory that would be used by getting the arrays for all states.
1519  */
1520 size_t BLI_array_store_calc_size_expanded_get(
1521         const BArrayStore *bs)
1522 {
1523         size_t size_accum = 0;
1524         for (const BArrayState *state = bs->states.first; state; state = state->next) {
1525                 size_accum += state->chunk_list->total_size;
1526         }
1527         return size_accum;
1528 }
1529
1530 /**
1531  * \return the amount of memory used by all #BChunk.data
1532  * (duplicate chunks are only counted once).
1533  */
1534 size_t BLI_array_store_calc_size_compacted_get(
1535         const BArrayStore *bs)
1536 {
1537         size_t size_total = 0;
1538         BLI_mempool_iter iter;
1539         BChunk *chunk;
1540         BLI_mempool_iternew(bs->memory.chunk, &iter);
1541         while ((chunk = BLI_mempool_iterstep(&iter))) {
1542                 BLI_assert(chunk->users > 0);
1543                 size_total += (size_t)chunk->data_len;
1544         }
1545         return size_total;
1546 }
1547
1548 /** \} */
1549
1550
1551 /** \name BArrayState Access
1552  * \{ */
1553
1554 /**
1555  *
1556  * \param data: Data used to create
1557  * \param state_reference: The state to use as a reference when adding the new state,
1558  * typically this is the previous state,
1559  * however it can be any previously created state from this \a bs.
1560  *
1561  * \return The new state, which is used by the caller as a handle to get back the contents of \a data.
1562  * This may be removed using #BLI_array_store_state_remove,
1563  * otherwise it will be removed with #BLI_array_store_destroy.
1564  */
1565 BArrayState *BLI_array_store_state_add(
1566         BArrayStore *bs,
1567         const void *data, const size_t data_len,
1568         const BArrayState *state_reference)
1569 {
1570         /* ensure we're aligned to the stride */
1571         BLI_assert((data_len % bs->info.chunk_stride) == 0);
1572
1573 #ifdef USE_PARANOID_CHECKS
1574         if (state_reference) {
1575                 BLI_assert(BLI_findindex(&bs->states, state_reference) != -1);
1576         }
1577 #endif
1578
1579         BChunkList *chunk_list;
1580         if (state_reference) {
1581                 chunk_list = bchunk_list_from_data_merge(
1582                         &bs->info, &bs->memory,
1583                         (const uchar *)data, data_len,
1584                         /* re-use reference chunks */
1585                         state_reference->chunk_list);
1586         }
1587         else {
1588                 chunk_list = bchunk_list_new(&bs->memory, data_len);
1589                 bchunk_list_fill_from_array(
1590                         &bs->info, &bs->memory,
1591                         chunk_list,
1592                         (const uchar *)data, data_len);
1593         }
1594
1595         chunk_list->users += 1;
1596
1597         BArrayState *state = MEM_callocN(sizeof(BArrayState), __func__);
1598         state->chunk_list = chunk_list;
1599
1600         BLI_addtail(&bs->states, state);
1601
1602 #ifdef USE_PARANOID_CHECKS
1603         {
1604                 size_t data_test_len;
1605                 void *data_test = BLI_array_store_state_data_get_alloc(state, &data_test_len);
1606                 BLI_assert(data_test_len == data_len);
1607                 BLI_assert(memcmp(data_test, data, data_len) == 0);
1608                 MEM_freeN(data_test);
1609         }
1610 #endif
1611
1612         return state;
1613 }
1614
1615 /**
1616  * Remove a state and free any unused #BChunk data.
1617  *
1618  * The states can be freed in any order.
1619  */
1620 void BLI_array_store_state_remove(
1621         BArrayStore *bs,
1622         BArrayState *state)
1623 {
1624 #ifdef USE_PARANOID_CHECKS
1625         BLI_assert(BLI_findindex(&bs->states, state) != -1);
1626 #endif
1627
1628         bchunk_list_decref(&bs->memory, state->chunk_list);
1629         BLI_remlink(&bs->states, state);
1630
1631         MEM_freeN(state);
1632 }
1633
1634 /**
1635  * \return the expanded size of the array,
1636  * use this to know how much memory to allocate #BLI_array_store_state_data_get's argument.
1637  */
1638 size_t BLI_array_store_state_size_get(
1639         BArrayState *state)
1640 {
1641         return state->chunk_list->total_size;
1642 }
1643
1644 /**
1645  * Fill in existing allocated memory with the contents of \a state.
1646  */
1647 void BLI_array_store_state_data_get(
1648         BArrayState *state,
1649         void *data)
1650 {
1651 #ifdef USE_PARANOID_CHECKS
1652         size_t data_test_len = 0;
1653         for (BChunkRef *cref = state->chunk_list->chunk_refs.first; cref; cref = cref->next) {
1654                 data_test_len += cref->link->data_len;
1655         }
1656         BLI_assert(data_test_len == state->chunk_list->total_size);
1657 #endif
1658
1659         uchar *data_step = (uchar *)data;
1660         for (BChunkRef *cref = state->chunk_list->chunk_refs.first; cref; cref = cref->next) {
1661                 BLI_assert(cref->link->users > 0);
1662                 memcpy(data_step, cref->link->data, cref->link->data_len);
1663                 data_step += cref->link->data_len;
1664         }
1665 }
1666
1667 /**
1668  * Allocate an array for \a state and return it.
1669  */
1670 void *BLI_array_store_state_data_get_alloc(
1671         BArrayState *state,
1672         size_t *r_data_len)
1673 {
1674         void *data = MEM_mallocN(state->chunk_list->total_size, __func__);
1675         BLI_array_store_state_data_get(state, data);
1676         *r_data_len = state->chunk_list->total_size;
1677         return data;
1678 }
1679
1680 /** \} */
1681
1682
1683 /** \name Debugging API (for testing).
1684  * \{ */
1685
1686 /* only for test validation */
1687 static size_t bchunk_list_size(const BChunkList *chunk_list)
1688 {
1689         size_t total_size = 0;
1690         for (BChunkRef *cref = chunk_list->chunk_refs.first; cref; cref = cref->next) {
1691                 total_size += cref->link->data_len;
1692         }
1693         return total_size;
1694 }
1695
1696 bool BLI_array_store_is_valid(
1697         BArrayStore *bs)
1698 {
1699         bool ok = true;
1700
1701         /* Check Length
1702          * ------------ */
1703
1704         for (BArrayState *state = bs->states.first; state; state = state->next) {
1705                 BChunkList *chunk_list = state->chunk_list;
1706                 if (!(bchunk_list_size(chunk_list) == chunk_list->total_size)) {
1707                         return false;
1708                 }
1709
1710                 if (BLI_listbase_count(&chunk_list->chunk_refs) != (int)chunk_list->chunk_refs_len) {
1711                         return false;
1712                 }
1713
1714 #ifdef USE_MERGE_CHUNKS
1715                 /* ensure we merge all chunks that could be merged */
1716                 if (chunk_list->total_size > bs->info.chunk_byte_size_min) {
1717                         for (BChunkRef *cref = chunk_list->chunk_refs.first; cref; cref = cref->next) {
1718                                 if (cref->link->data_len < bs->info.chunk_byte_size_min) {
1719                                         return false;
1720                                 }
1721                         }
1722                 }
1723 #endif
1724         }
1725
1726         {
1727                 BLI_mempool_iter iter;
1728                 BChunk *chunk;
1729                 BLI_mempool_iternew(bs->memory.chunk, &iter);
1730                 while ((chunk = BLI_mempool_iterstep(&iter))) {
1731                         if (!(MEM_allocN_len(chunk->data) >= chunk->data_len)) {
1732                                 return false;
1733                         }
1734                 }
1735         }
1736
1737         /* Check User Count & Lost References
1738          * ---------------------------------- */
1739         {
1740                 GHashIterator gh_iter;
1741
1742 #define GHASH_PTR_ADD_USER(gh, pt) \
1743         { \
1744                 void **val; \
1745                 if (BLI_ghash_ensure_p((gh), (pt), &val)) { \
1746                         *((int *)val) += 1; \
1747                 } \
1748                 else { \
1749                         *((int *)val) = 1; \
1750                 } \
1751         } ((void)0)
1752
1753                 /* count chunk_list's */
1754                 GHash *chunk_list_map = BLI_ghash_ptr_new(__func__);
1755                 GHash *chunk_map = BLI_ghash_ptr_new(__func__);
1756
1757                 int totrefs = 0;
1758                 for (BArrayState *state = bs->states.first; state; state = state->next) {
1759                         GHASH_PTR_ADD_USER(chunk_list_map, state->chunk_list);
1760                 }
1761                 GHASH_ITER (gh_iter, chunk_list_map) {
1762                         const struct BChunkList *chunk_list = BLI_ghashIterator_getKey(&gh_iter);
1763                         const int users =  GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(&gh_iter));
1764                         if (!(chunk_list->users == users)) {
1765                                 ok = false;
1766                                 goto user_finally;
1767                         }
1768                 }
1769                 if (!(BLI_mempool_len(bs->memory.chunk_list) == (int)BLI_ghash_len(chunk_list_map))) {
1770                         ok = false;
1771                         goto user_finally;
1772                 }
1773
1774                 /* count chunk's */
1775                 GHASH_ITER (gh_iter, chunk_list_map) {
1776                         const struct BChunkList *chunk_list = BLI_ghashIterator_getKey(&gh_iter);
1777                         for (const BChunkRef *cref = chunk_list->chunk_refs.first; cref; cref = cref->next) {
1778                                 GHASH_PTR_ADD_USER(chunk_map, cref->link);
1779                                 totrefs += 1;
1780                         }
1781                 }
1782                 if (!(BLI_mempool_len(bs->memory.chunk) == (int)BLI_ghash_len(chunk_map))) {
1783                         ok = false;
1784                         goto user_finally;
1785                 }
1786                 if (!(BLI_mempool_len(bs->memory.chunk_ref) == totrefs)) {
1787                         ok = false;
1788                         goto user_finally;
1789                 }
1790
1791                 GHASH_ITER (gh_iter, chunk_map) {
1792                         const struct BChunk *chunk = BLI_ghashIterator_getKey(&gh_iter);
1793                         const int users =  GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(&gh_iter));
1794                         if (!(chunk->users == users)) {
1795                                 ok = false;
1796                                 goto user_finally;
1797                         }
1798                 }
1799
1800 #undef GHASH_PTR_ADD_USER
1801
1802 user_finally:
1803                 BLI_ghash_free(chunk_list_map, NULL, NULL);
1804                 BLI_ghash_free(chunk_map, NULL, NULL);
1805         }
1806
1807
1808         return ok;
1809         /* TODO, dangling pointer checks */
1810 }
1811
1812 /** \} */