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