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