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