Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/source/blender/blenlib/intern/stack.c
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender/blenlib/intern/stack.c')
-rw-r--r--source/blender/blenlib/intern/stack.c256
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);
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-09 15:54:30 +0300