diff options
Diffstat (limited to 'source/blender/blenlib')
| -rw-r--r-- | source/blender/blenlib/BLI_stackdefines.h | 12 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/BLI_ghash.c | 2 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/BLI_mempool.c | 42 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/array_store.c | 187 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/noise.c | 4 |
5 files changed, 176 insertions, 71 deletions
diff --git a/source/blender/blenlib/BLI_stackdefines.h b/source/blender/blenlib/BLI_stackdefines.h index b26dc3e26aa..42b11eb9a2b 100644 --- a/source/blender/blenlib/BLI_stackdefines.h +++ b/source/blender/blenlib/BLI_stackdefines.h @@ -31,28 +31,28 @@ /* only validate array-bounds in debug mode */ #ifdef DEBUG # define STACK_DECLARE(stack) unsigned int _##stack##_index, _##stack##_totalloc -# define STACK_INIT(stack, tot) ((void)stack, (void)((_##stack##_index) = 0), (void)((_##stack##_totalloc) = tot)) -# define _STACK_SIZETEST(stack, off) (BLI_assert((_##stack##_index) + off <= _##stack##_totalloc)) +# define STACK_INIT(stack, tot) ((void)stack, (void)((_##stack##_index) = 0), (void)((_##stack##_totalloc) = (tot))) +# define _STACK_SIZETEST(stack, off) (BLI_assert((_##stack##_index) + (off) <= _##stack##_totalloc)) # define _STACK_SWAP_TOTALLOC(stack_a, stack_b) SWAP(unsigned int, _##stack_a##_totalloc, _##stack_b##_totalloc) #else # define STACK_DECLARE(stack) unsigned int _##stack##_index -# define STACK_INIT(stack, tot) ((void)stack, (void)((_##stack##_index) = 0), (void)(0 ? tot : 0)) +# define STACK_INIT(stack, tot) ((void)stack, (void)((_##stack##_index) = 0), (void)(0 ? (tot) : 0)) # define _STACK_SIZETEST(stack, off) (void)(stack), (void)(off) # define _STACK_SWAP_TOTALLOC(stack_a, stack_b) (void)(stack_a), (void)(stack_b) #endif -#define _STACK_BOUNDSTEST(stack, index) ((void)stack, BLI_assert((unsigned int)index < _##stack##_index)) +#define _STACK_BOUNDSTEST(stack, index) ((void)stack, BLI_assert((unsigned int)(index) < _##stack##_index)) #define STACK_SIZE(stack) ((void)stack, (_##stack##_index)) #define STACK_CLEAR(stack) {(void)stack; _##stack##_index = 0; } ((void)0) /** add item to stack */ -#define STACK_PUSH(stack, val) ((void)stack, _STACK_SIZETEST(stack, 1), ((stack)[(_##stack##_index)++] = val)) +#define STACK_PUSH(stack, val) ((void)stack, _STACK_SIZETEST(stack, 1), ((stack)[(_##stack##_index)++] = (val))) #define STACK_PUSH_RET(stack) ((void)stack, _STACK_SIZETEST(stack, 1), ((stack)[(_##stack##_index)++])) #define STACK_PUSH_RET_PTR(stack) ((void)stack, _STACK_SIZETEST(stack, 1), &((stack)[(_##stack##_index)++])) /** take last item from stack */ #define STACK_POP(stack) ((_##stack##_index) ? ((stack)[--(_##stack##_index)]) : NULL) #define STACK_POP_PTR(stack) ((_##stack##_index) ? &((stack)[--(_##stack##_index)]) : NULL) -#define STACK_POP_DEFAULT(stack, r) ((_##stack##_index) ? ((stack)[--(_##stack##_index)]) : r) +#define STACK_POP_DEFAULT(stack, r) ((_##stack##_index) ? ((stack)[--(_##stack##_index)]) : (r)) /** look at last item (assumes non-empty stack) */ #define STACK_PEEK(stack) (BLI_assert(_##stack##_index), ((stack)[_##stack##_index - 1])) #define STACK_PEEK_PTR(stack) (BLI_assert(_##stack##_index), &((stack)[_##stack##_index - 1])) diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index 05f2d9221ef..06946e520a8 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -1287,7 +1287,7 @@ bool BLI_ghashutil_paircmp(const void *a, const void *b) const GHashPair *A = a; const GHashPair *B = b; - return (BLI_ghashutil_ptrcmp(A->first, B->first) && + return (BLI_ghashutil_ptrcmp(A->first, B->first) || BLI_ghashutil_ptrcmp(A->second, B->second)); } diff --git a/source/blender/blenlib/intern/BLI_mempool.c b/source/blender/blenlib/intern/BLI_mempool.c index 7338804c685..b7a51f2c48e 100644 --- a/source/blender/blenlib/intern/BLI_mempool.c +++ b/source/blender/blenlib/intern/BLI_mempool.c @@ -57,12 +57,29 @@ #ifdef __BIG_ENDIAN__ /* Big Endian */ # define MAKE_ID(a, b, c, d) ( (int)(a) << 24 | (int)(b) << 16 | (c) << 8 | (d) ) +# define MAKE_ID_8(a, b, c, d, e, f, g, h) \ + ((int64_t)(a) << 56 | (int64_t)(b) << 48 | (int64_t)(c) << 40 | (int64_t)(d) << 32 | \ + (int64_t)(e) << 24 | (int64_t)(f) << 16 | (int64_t)(g) << 8 | (h) ) #else /* Little Endian */ # define MAKE_ID(a, b, c, d) ( (int)(d) << 24 | (int)(c) << 16 | (b) << 8 | (a) ) +# define MAKE_ID_8(a, b, c, d, e, f, g, h) \ + ((int64_t)(h) << 56 | (int64_t)(g) << 48 | (int64_t)(f) << 40 | (int64_t)(e) << 32 | \ + (int64_t)(d) << 24 | (int64_t)(c) << 16 | (int64_t)(b) << 8 | (a) ) #endif -#define FREEWORD MAKE_ID('f', 'r', 'e', 'e') +/** + * Important that this value is an is _not_ aligned with ``sizeof(void *)``. + * So having a pointer to 2/4/8... aligned memory is enough to ensure the freeword will never be used. + * To be safe, use a word thats the same in both directions. + */ +#define FREEWORD ((sizeof(void *) > sizeof(int32_t)) ? \ + MAKE_ID_8('e', 'e', 'r', 'f', 'f', 'r', 'e', 'e') : \ + MAKE_ID('e', 'f', 'f', 'e')) + +/** + * The 'used' word just needs to be set to something besides FREEWORD. + */ #define USEDWORD MAKE_ID('u', 's', 'e', 'd') /* currently totalloc isnt used */ @@ -87,7 +104,7 @@ static bool mempool_debug_memset = false; */ typedef struct BLI_freenode { struct BLI_freenode *next; - int freeword; /* used to identify this as a freed node */ + intptr_t freeword; /* used to identify this as a freed node */ } BLI_freenode; /** @@ -588,19 +605,26 @@ void *BLI_mempool_iterstep(BLI_mempool_iter *iter) */ void *BLI_mempool_iterstep(BLI_mempool_iter *iter) { - BLI_freenode *ret; + if (UNLIKELY(iter->curchunk == NULL)) { + return NULL; + } + const unsigned int esize = iter->pool->esize; + BLI_freenode *curnode = POINTER_OFFSET(CHUNK_DATA(iter->curchunk), (esize * iter->curindex)); + BLI_freenode *ret; do { - if (LIKELY(iter->curchunk)) { - ret = (BLI_freenode *)(((char *)CHUNK_DATA(iter->curchunk)) + (iter->pool->esize * iter->curindex)); + ret = curnode; + + if (++iter->curindex != iter->pool->pchunk) { + curnode = POINTER_OFFSET(curnode, esize); } else { - return NULL; - } - - if (UNLIKELY(++iter->curindex == iter->pool->pchunk)) { iter->curindex = 0; iter->curchunk = iter->curchunk->next; + if (iter->curchunk == NULL) { + return NULL; + } + curnode = CHUNK_DATA(iter->curchunk); } } while (ret->freeword == FREEWORD); diff --git a/source/blender/blenlib/intern/array_store.c b/source/blender/blenlib/intern/array_store.c index 7f657f4a048..9baccf38fa3 100644 --- a/source/blender/blenlib/intern/array_store.c +++ b/source/blender/blenlib/intern/array_store.c @@ -229,7 +229,9 @@ typedef struct BArrayInfo { /* pre-calculated */ size_t chunk_byte_size; + /* min/max limits (inclusive) */ size_t chunk_byte_size_min; + size_t chunk_byte_size_max; size_t accum_read_ahead_bytes; #ifdef USE_HASH_TABLE_ACCUMULATE @@ -455,7 +457,7 @@ static void bchunk_list_ensure_min_size_last( if (MIN2(chunk_prev->data_len, chunk_curr->data_len) < info->chunk_byte_size_min) { const size_t data_merge_len = chunk_prev->data_len + chunk_curr->data_len; /* we could pass, but no need */ - if (data_merge_len <= (info->chunk_byte_size * BCHUNK_SIZE_MAX_MUL)) { + if (data_merge_len <= info->chunk_byte_size_max) { /* we have enough space to merge */ /* remove last from linklist */ @@ -527,6 +529,53 @@ static void bchunk_list_ensure_min_size_last( } #endif /* USE_MERGE_CHUNKS */ + +/** + * Split length into 2 values + * \param r_data_trim_len: Length which is aligned to the #BArrayInfo.chunk_byte_size + * \param r_data_last_chunk_len: The remaining bytes. + * + * \note This function ensures the size of \a r_data_last_chunk_len + * is larger than #BArrayInfo.chunk_byte_size_min. + */ +static void bchunk_list_calc_trim_len( + const BArrayInfo *info, const size_t data_len, + size_t *r_data_trim_len, size_t *r_data_last_chunk_len) +{ + size_t data_last_chunk_len = 0; + size_t data_trim_len = data_len; + +#ifdef USE_MERGE_CHUNKS + /* avoid creating too-small chunks + * more efficient then merging after */ + if (data_len > info->chunk_byte_size) { + data_last_chunk_len = (data_trim_len % info->chunk_byte_size); + data_trim_len = data_trim_len - data_last_chunk_len; + if (data_last_chunk_len) { + if (data_last_chunk_len < info->chunk_byte_size_min) { + /* may be zero and thats OK */ + data_trim_len -= info->chunk_byte_size; + data_last_chunk_len += info->chunk_byte_size; + } + } + } + else { + data_trim_len = 0; + data_last_chunk_len = data_len; + } + + BLI_assert((data_trim_len == 0) || (data_trim_len >= info->chunk_byte_size)); +#else + data_last_chunk_len = (data_trim_len % info->chunk_byte_size); + data_trim_len = data_trim_len - data_last_chunk_len; +#endif + + BLI_assert(data_trim_len + data_last_chunk_len == data_len); + + *r_data_trim_len = data_trim_len; + *r_data_last_chunk_len = data_last_chunk_len; +} + /** * Append and don't manage merging small chunks. */ @@ -542,14 +591,21 @@ static bool bchunk_list_append_only( return chunk; } +/** + * \note This is for writing single chunks, + * use #bchunk_list_append_data_n when writing large blocks of memory into many chunks. + */ static void bchunk_list_append_data( const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, const ubyte *data, const size_t data_len) { BLI_assert(data_len != 0); + // printf("data_len: %d\n", data_len); #ifdef USE_MERGE_CHUNKS + BLI_assert(data_len <= info->chunk_byte_size_max); + if (!BLI_listbase_is_empty(&chunk_list->chunk_refs)) { BChunkRef *cref = chunk_list->chunk_refs.last; BChunk *chunk_prev = cref->link; @@ -589,6 +645,59 @@ static void bchunk_list_append_data( #endif } +/** + * Similar to #bchunk_list_append_data, but handle multiple chunks. + * Use for adding arrays of arbitrary sized memory at once. + * + * \note This function takes care not to perform redundant chunk-merging checks, + * so we can write succesive fixed size chunks quickly. + */ +static void bchunk_list_append_data_n( + const BArrayInfo *info, BArrayMemory *bs_mem, + BChunkList *chunk_list, + const ubyte *data, size_t data_len) +{ + size_t data_trim_len, data_last_chunk_len; + bchunk_list_calc_trim_len(info, data_len, &data_trim_len, &data_last_chunk_len); + + if (data_trim_len != 0) { + size_t i_prev; + + { + const size_t i = info->chunk_byte_size; + bchunk_list_append_data(info, bs_mem, chunk_list, data, i); + i_prev = i; + } + + while (i_prev != data_trim_len) { + const size_t i = i_prev + info->chunk_byte_size; + BChunk *chunk = bchunk_new_copydata(bs_mem, &data[i_prev], i - i_prev); + bchunk_list_append_only(bs_mem, chunk_list, chunk); + i_prev = i; + } + + if (data_last_chunk_len) { + BChunk *chunk = bchunk_new_copydata(bs_mem, &data[i_prev], data_last_chunk_len); + bchunk_list_append_only(bs_mem, chunk_list, chunk); + // i_prev = data_len; /* UNUSED */ + } + } + else { + /* if we didn't write any chunks previously, + * we may need to merge with the last. */ + if (data_last_chunk_len) { + bchunk_list_append_data(info, bs_mem, chunk_list, data, data_last_chunk_len); + // i_prev = data_len; /* UNUSED */ + } + } + +#ifdef USE_MERGE_CHUNKS + if (data_len > info->chunk_byte_size) { + BLI_assert(((BChunkRef *)chunk_list->chunk_refs.last)->link->data_len >= info->chunk_byte_size_min); + } +#endif +} + static void bchunk_list_append( const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, @@ -611,37 +720,11 @@ static void bchunk_list_fill_from_array( { BLI_assert(BLI_listbase_is_empty(&chunk_list->chunk_refs)); - size_t data_last_chunk_len = 0; - size_t data_trim_len = data_len; - -#ifdef USE_MERGE_CHUNKS - /* avoid creating too-small chunks - * more efficient then merging after */ - if (data_len > info->chunk_byte_size) { - data_last_chunk_len = (data_trim_len % info->chunk_byte_size); - data_trim_len = data_trim_len - data_last_chunk_len; - if (data_last_chunk_len) { - if (data_last_chunk_len < info->chunk_byte_size_min) { - /* may be zero and thats OK */ - data_trim_len -= info->chunk_byte_size; - data_last_chunk_len += info->chunk_byte_size; - } - } - } - else { - data_trim_len = 0; - data_last_chunk_len = data_len; - } -#else - data_last_chunk_len = (data_trim_len % info->chunk_byte_size); - data_trim_len = data_trim_len - data_last_chunk_len; -#endif - - - BLI_assert(data_trim_len + data_last_chunk_len == data_len); + size_t data_trim_len, data_last_chunk_len; + bchunk_list_calc_trim_len(info, data_len, &data_trim_len, &data_last_chunk_len); size_t i_prev = 0; - while (i_prev < data_trim_len) { + while (i_prev != data_trim_len) { const size_t i = i_prev + info->chunk_byte_size; BChunk *chunk = bchunk_new_copydata(bs_mem, &data[i_prev], i - i_prev); bchunk_list_append_only(bs_mem, chunk_list, chunk); @@ -1220,21 +1303,8 @@ static BChunkList *bchunk_list_from_data_merge( if (cref_found != NULL) { BLI_assert(i < data_len); if (i != i_prev) { - size_t i_step = MIN2(i_prev + info->chunk_byte_size, data_len); - BLI_assert(i_step <= data_len); - - while (i_prev != i) { - i_step = MIN2(i_step, i); - const ubyte *data_slice = &data[i_prev]; - const size_t data_slice_len = i_step - i_prev; - /* First add all previous chunks! */ - i_prev += data_slice_len; - bchunk_list_append_data(info, bs_mem, chunk_list, data_slice, data_slice_len); - BLI_assert(i_prev <= data_len); - ASSERT_CHUNKLIST_SIZE(chunk_list, i_prev); - ASSERT_CHUNKLIST_DATA(chunk_list, data); - i_step += info->chunk_byte_size; - } + bchunk_list_append_data_n(info, bs_mem, chunk_list, &data[i_prev], i - i_prev); + i_prev = i; } /* now add the reference chunk */ @@ -1294,14 +1364,9 @@ static BChunkList *bchunk_list_from_data_merge( * * Trailing chunks, no matches found in table lookup above. * Write all new data. */ - BLI_assert(i_prev <= data_len); - while (i_prev != data_len) { - size_t i = i_prev + info->chunk_byte_size; - i = MIN2(i, data_len); - BLI_assert(i != i_prev); - bchunk_list_append_data(info, bs_mem, chunk_list, &data[i_prev], i - i_prev); - ASSERT_CHUNKLIST_DATA(chunk_list, data); - i_prev = i; + if (i_prev != data_len) { + bchunk_list_append_data_n(info, bs_mem, chunk_list, &data[i_prev], data_len - i_prev); + i_prev = data_len; } BLI_assert(i_prev == data_len); @@ -1374,6 +1439,7 @@ BArrayStore *BLI_array_store_create( bs->info.chunk_byte_size = chunk_count * stride; #ifdef USE_MERGE_CHUNKS bs->info.chunk_byte_size_min = MAX2(1u, chunk_count / BCHUNK_SIZE_MIN_DIV) * stride; + bs->info.chunk_byte_size_max = (chunk_count * BCHUNK_SIZE_MAX_MUL) * stride; #endif #ifdef USE_HASH_TABLE_ACCUMULATE @@ -1640,6 +1706,21 @@ bool BLI_array_store_is_valid( if (!(bchunk_list_size(chunk_list) == chunk_list->total_size)) { return false; } + + if (BLI_listbase_count(&chunk_list->chunk_refs) != (int)chunk_list->chunk_refs_len) { + return false; + } + +#ifdef USE_MERGE_CHUNKS + /* ensure we merge all chunks that could be merged */ + if (chunk_list->total_size > bs->info.chunk_byte_size_min) { + for (BChunkRef *cref = chunk_list->chunk_refs.first; cref; cref = cref->next) { + if (cref->link->data_len < bs->info.chunk_byte_size_min) { + return false; + } + } + } +#endif } { diff --git a/source/blender/blenlib/intern/noise.c b/source/blender/blenlib/intern/noise.c index c3a0c44d7c5..f834c5b4c74 100644 --- a/source/blender/blenlib/intern/noise.c +++ b/source/blender/blenlib/intern/noise.c @@ -1048,8 +1048,8 @@ static float noise3_perlin(float vec[3]) b01 = p[i + by1]; b11 = p[j + by1]; -#define VALUE_AT(rx, ry, rz) (rx * q[0] + ry * q[1] + rz * q[2]) -#define SURVE(t) (t * t * (3.0f - 2.0f * t)) +#define VALUE_AT(rx, ry, rz) ((rx) * q[0] + (ry) * q[1] + (rz) * q[2]) +#define SURVE(t) ((t) * (t) * (3.0f - 2.0f * (t))) /* lerp moved to improved perlin above */ |