diff options
Diffstat (limited to 'source/blender/blenlib/intern/stack.c')
-rw-r--r-- | source/blender/blenlib/intern/stack.c | 256 |
1 files changed, 127 insertions, 129 deletions
diff --git a/source/blender/blenlib/intern/stack.c b/source/blender/blenlib/intern/stack.c index 4f6f9024fa5..76aef3761ae 100644 --- a/source/blender/blenlib/intern/stack.c +++ b/source/blender/blenlib/intern/stack.c @@ -19,12 +19,12 @@ */ #include <string.h> -#include <stdlib.h> /* abort() */ +#include <stdlib.h> /* abort() */ #include "BLI_utildefines.h" #include "MEM_guardedalloc.h" -#include "BLI_stack.h" /* own include */ +#include "BLI_stack.h" /* own include */ #include "BLI_strict_flags.h" @@ -34,26 +34,25 @@ /* target chunks size: 64kb */ #define CHUNK_SIZE_DEFAULT (1 << 16) /* ensure we get at least this many elems per chunk */ -#define CHUNK_ELEM_MIN 32 +#define CHUNK_ELEM_MIN 32 /* Gets the last element in the stack */ #define CHUNK_LAST_ELEM(_stack) \ - ((void)0, (((char *)(_stack)->chunk_curr->data) + \ - ((_stack)->elem_size * (_stack)->chunk_index))) + ((void)0, (((char *)(_stack)->chunk_curr->data) + ((_stack)->elem_size * (_stack)->chunk_index))) struct StackChunk { - struct StackChunk *next; - char data[0]; + struct StackChunk *next; + char data[0]; }; struct BLI_Stack { - struct StackChunk *chunk_curr; /* currently active chunk */ - struct StackChunk *chunk_free; /* free chunks */ - size_t chunk_index; /* index into 'chunk_curr' */ - size_t chunk_elem_max; /* number of elements per chunk */ - size_t elem_size; + struct StackChunk *chunk_curr; /* currently active chunk */ + struct StackChunk *chunk_free; /* free chunks */ + size_t chunk_index; /* index into 'chunk_curr' */ + size_t chunk_elem_max; /* number of elements per chunk */ + size_t elem_size; #ifdef USE_TOTELEM - size_t totelem; + size_t totelem; #endif }; @@ -62,32 +61,33 @@ struct BLI_Stack { */ static size_t stack_chunk_elem_max_calc(const size_t elem_size, size_t chunk_size) { - /* get at least this number of elems per chunk */ - const size_t elem_size_min = elem_size * CHUNK_ELEM_MIN; + /* get at least this number of elems per chunk */ + const size_t elem_size_min = elem_size * CHUNK_ELEM_MIN; - BLI_assert((elem_size != 0) && (chunk_size != 0)); + BLI_assert((elem_size != 0) && (chunk_size != 0)); - while (UNLIKELY(chunk_size <= elem_size_min)) { - chunk_size <<= 1; - } + while (UNLIKELY(chunk_size <= elem_size_min)) { + chunk_size <<= 1; + } - /* account for slop-space */ - chunk_size -= (sizeof(struct StackChunk) + MEM_SIZE_OVERHEAD); + /* account for slop-space */ + chunk_size -= (sizeof(struct StackChunk) + MEM_SIZE_OVERHEAD); - return chunk_size / elem_size; + return chunk_size / elem_size; } -BLI_Stack *BLI_stack_new_ex(const size_t elem_size, const char *description, +BLI_Stack *BLI_stack_new_ex(const size_t elem_size, + const char *description, const size_t chunk_size) { - BLI_Stack *stack = MEM_callocN(sizeof(*stack), description); + BLI_Stack *stack = MEM_callocN(sizeof(*stack), description); - stack->chunk_elem_max = stack_chunk_elem_max_calc(elem_size, chunk_size); - stack->elem_size = elem_size; - /* force init */ - stack->chunk_index = stack->chunk_elem_max - 1; + stack->chunk_elem_max = stack_chunk_elem_max_calc(elem_size, chunk_size); + stack->elem_size = elem_size; + /* force init */ + stack->chunk_index = stack->chunk_elem_max - 1; - return stack; + return stack; } /** @@ -95,16 +95,16 @@ BLI_Stack *BLI_stack_new_ex(const size_t elem_size, const char *description, */ BLI_Stack *BLI_stack_new(const size_t elem_size, const char *description) { - return BLI_stack_new_ex(elem_size, description, CHUNK_SIZE_DEFAULT); + return BLI_stack_new_ex(elem_size, description, CHUNK_SIZE_DEFAULT); } static void stack_free_chunks(struct StackChunk *data) { - while (data) { - struct StackChunk *data_next = data->next; - MEM_freeN(data); - data = data_next; - } + while (data) { + struct StackChunk *data_next = data->next; + MEM_freeN(data); + data = data_next; + } } /** @@ -112,9 +112,9 @@ static void stack_free_chunks(struct StackChunk *data) */ void BLI_stack_free(BLI_Stack *stack) { - stack_free_chunks(stack->chunk_curr); - stack_free_chunks(stack->chunk_free); - MEM_freeN(stack); + stack_free_chunks(stack->chunk_curr); + stack_free_chunks(stack->chunk_free); + MEM_freeN(stack); } /** @@ -125,32 +125,30 @@ void BLI_stack_free(BLI_Stack *stack) */ void *BLI_stack_push_r(BLI_Stack *stack) { - stack->chunk_index++; - - if (UNLIKELY(stack->chunk_index == stack->chunk_elem_max)) { - struct StackChunk *chunk; - if (stack->chunk_free) { - chunk = stack->chunk_free; - stack->chunk_free = chunk->next; - } - else { - chunk = MEM_mallocN( - sizeof(*chunk) + (stack->elem_size * stack->chunk_elem_max), - __func__); - } - chunk->next = stack->chunk_curr; - stack->chunk_curr = chunk; - stack->chunk_index = 0; - } - - BLI_assert(stack->chunk_index < stack->chunk_elem_max); + stack->chunk_index++; + + if (UNLIKELY(stack->chunk_index == stack->chunk_elem_max)) { + struct StackChunk *chunk; + if (stack->chunk_free) { + chunk = stack->chunk_free; + stack->chunk_free = chunk->next; + } + else { + chunk = MEM_mallocN(sizeof(*chunk) + (stack->elem_size * stack->chunk_elem_max), __func__); + } + chunk->next = stack->chunk_curr; + stack->chunk_curr = chunk; + stack->chunk_index = 0; + } + + BLI_assert(stack->chunk_index < stack->chunk_elem_max); #ifdef USE_TOTELEM - stack->totelem++; + stack->totelem++; #endif - /* Return end of stack */ - return CHUNK_LAST_ELEM(stack); + /* Return end of stack */ + return CHUNK_LAST_ELEM(stack); } /** @@ -163,8 +161,8 @@ void *BLI_stack_push_r(BLI_Stack *stack) */ void BLI_stack_push(BLI_Stack *stack, const void *src) { - void *dst = BLI_stack_push_r(stack); - memcpy(dst, src, stack->elem_size); + void *dst = BLI_stack_push_r(stack); + memcpy(dst, src, stack->elem_size); } /** @@ -175,11 +173,11 @@ void BLI_stack_push(BLI_Stack *stack, const void *src) */ void BLI_stack_pop(BLI_Stack *stack, void *dst) { - BLI_assert(BLI_stack_is_empty(stack) == false); + BLI_assert(BLI_stack_is_empty(stack) == false); - memcpy(dst, CHUNK_LAST_ELEM(stack), stack->elem_size); + memcpy(dst, CHUNK_LAST_ELEM(stack), stack->elem_size); - BLI_stack_discard(stack); + BLI_stack_discard(stack); } /** @@ -193,12 +191,12 @@ void BLI_stack_pop(BLI_Stack *stack, void *dst) */ void BLI_stack_pop_n(BLI_Stack *stack, void *dst, unsigned int n) { - BLI_assert(n <= BLI_stack_count(stack)); + BLI_assert(n <= BLI_stack_count(stack)); - while (n--) { - BLI_stack_pop(stack, dst); - dst = (void *)((char *)dst + stack->elem_size); - } + while (n--) { + BLI_stack_pop(stack, dst); + dst = (void *)((char *)dst + stack->elem_size); + } } /** @@ -208,21 +206,21 @@ void BLI_stack_pop_n(BLI_Stack *stack, void *dst, unsigned int n) */ void BLI_stack_pop_n_reverse(BLI_Stack *stack, void *dst, unsigned int n) { - BLI_assert(n <= BLI_stack_count(stack)); + BLI_assert(n <= BLI_stack_count(stack)); - dst = (void *)((char *)dst + (stack->elem_size * n)); + dst = (void *)((char *)dst + (stack->elem_size * n)); - while (n--) { - dst = (void *)((char *)dst - stack->elem_size); - BLI_stack_pop(stack, dst); - } + while (n--) { + dst = (void *)((char *)dst - stack->elem_size); + BLI_stack_pop(stack, dst); + } } void *BLI_stack_peek(BLI_Stack *stack) { - BLI_assert(BLI_stack_is_empty(stack) == false); + BLI_assert(BLI_stack_is_empty(stack) == false); - return CHUNK_LAST_ELEM(stack); + return CHUNK_LAST_ELEM(stack); } /** @@ -230,22 +228,22 @@ void *BLI_stack_peek(BLI_Stack *stack) */ void BLI_stack_discard(BLI_Stack *stack) { - BLI_assert(BLI_stack_is_empty(stack) == false); + BLI_assert(BLI_stack_is_empty(stack) == false); #ifdef USE_TOTELEM - stack->totelem--; + stack->totelem--; #endif - if (UNLIKELY(--stack->chunk_index == CHUNK_EMPTY)) { - struct StackChunk *chunk_free; + if (UNLIKELY(--stack->chunk_index == CHUNK_EMPTY)) { + struct StackChunk *chunk_free; - chunk_free = stack->chunk_curr; - stack->chunk_curr = stack->chunk_curr->next; + chunk_free = stack->chunk_curr; + stack->chunk_curr = stack->chunk_curr->next; - chunk_free->next = stack->chunk_free; - stack->chunk_free = chunk_free; + chunk_free->next = stack->chunk_free; + stack->chunk_free = chunk_free; - stack->chunk_index = stack->chunk_elem_max - 1; - } + stack->chunk_index = stack->chunk_elem_max - 1; + } } /** @@ -254,54 +252,54 @@ void BLI_stack_discard(BLI_Stack *stack) void BLI_stack_clear(BLI_Stack *stack) { #ifdef USE_TOTELEM - if (UNLIKELY(stack->totelem == 0)) { - return; - } - stack->totelem = 0; + if (UNLIKELY(stack->totelem == 0)) { + return; + } + stack->totelem = 0; #else - if (UNLIKELY(stack->chunk_curr == NULL)) { - return; - } + if (UNLIKELY(stack->chunk_curr == NULL)) { + return; + } #endif - stack->chunk_index = stack->chunk_elem_max - 1; - - if (stack->chunk_free) { - if (stack->chunk_curr) { - /* move all used chunks into tail of free list */ - struct StackChunk *chunk_free_last = stack->chunk_free; - while (chunk_free_last->next) { - chunk_free_last = chunk_free_last->next; - } - chunk_free_last->next = stack->chunk_curr; - stack->chunk_curr = NULL; - } - } - else { - stack->chunk_free = stack->chunk_curr; - stack->chunk_curr = NULL; - } + stack->chunk_index = stack->chunk_elem_max - 1; + + if (stack->chunk_free) { + if (stack->chunk_curr) { + /* move all used chunks into tail of free list */ + struct StackChunk *chunk_free_last = stack->chunk_free; + while (chunk_free_last->next) { + chunk_free_last = chunk_free_last->next; + } + chunk_free_last->next = stack->chunk_curr; + stack->chunk_curr = NULL; + } + } + else { + stack->chunk_free = stack->chunk_curr; + stack->chunk_curr = NULL; + } } size_t BLI_stack_count(const BLI_Stack *stack) { #ifdef USE_TOTELEM - return stack->totelem; + return stack->totelem; #else - struct StackChunk *data = stack->chunk_curr; - size_t totelem = stack->chunk_index + 1; - size_t i; - if (totelem != stack->chunk_elem_max) { - data = data->next; - } - else { - totelem = 0; - } - for (i = 0; data; data = data->next) { - i++; - } - totelem += stack->chunk_elem_max * i; - return totelem; + struct StackChunk *data = stack->chunk_curr; + size_t totelem = stack->chunk_index + 1; + size_t i; + if (totelem != stack->chunk_elem_max) { + data = data->next; + } + else { + totelem = 0; + } + for (i = 0; data; data = data->next) { + i++; + } + totelem += stack->chunk_elem_max * i; + return totelem; #endif } @@ -311,7 +309,7 @@ size_t BLI_stack_count(const BLI_Stack *stack) bool BLI_stack_is_empty(const BLI_Stack *stack) { #ifdef USE_TOTELEM - BLI_assert((stack->chunk_curr == NULL) == (stack->totelem == 0)); + BLI_assert((stack->chunk_curr == NULL) == (stack->totelem == 0)); #endif - return (stack->chunk_curr == NULL); + return (stack->chunk_curr == NULL); } |