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