diff options
author | Nicholas Bishop <nicholasbishop@gmail.com> | 2012-08-06 03:29:43 +0400 |
---|---|---|
committer | Nicholas Bishop <nicholasbishop@gmail.com> | 2012-08-06 03:29:43 +0400 |
commit | b6bc30837596159f513d3a8ecedea6c835d60aa0 (patch) | |
tree | c6c7bc33fbe9b21e2e674e3fa3059e02d578a993 /source/blender | |
parent | 958dc02774b104123c6124a9185815dfe389a529 (diff) |
Add an array-based generic stack structure to blenlib
Very simple stack with homogeneous contents. Provides push, pop, and
is-empty operations.
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/blenlib/BLI_stack.h | 50 | ||||
-rw-r--r-- | source/blender/blenlib/CMakeLists.txt | 2 | ||||
-rw-r--r-- | source/blender/blenlib/intern/stack.c | 103 |
3 files changed, 155 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_stack.h b/source/blender/blenlib/BLI_stack.h new file mode 100644 index 00000000000..24c2d9359d7 --- /dev/null +++ b/source/blender/blenlib/BLI_stack.h @@ -0,0 +1,50 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * Contributor(s): Nicholas Bishop + * + * ***** END GPL LICENSE BLOCK ***** + * + */ + +#ifndef __BLI_STACK_H__ +#define __BLI_STACK_H__ + +typedef struct BLI_Stack BLI_Stack; + +/* Create a new homogeneous stack with elements of 'elem_size' bytes */ +BLI_Stack *BLI_stack_new(int elem_size, const char *description); + +/* Free the stack's data and the stack itself */ +void BLI_stack_free(BLI_Stack *stack); + +/* Copies the source value onto the stack (note that it copies + * elem_size bytes from 'src', the pointer itself is not stored) */ +void BLI_stack_push(BLI_Stack *stack, void *src); + +/* Retrieves and removes the top element from the stack. The value is + * copies to 'dst', which must be at least elem_size bytes. + * + * Does not reduce amount of allocated memory. + * + * If stack is empty, 'dst' will not be modified. */ +void BLI_stack_pop(BLI_Stack *stack, void *dst); + +/* Returns TRUE if the stack is empty, FALSE otherwise */ +int BLI_stack_empty(const BLI_Stack *stack); + +#endif diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index ac7681e3be7..0175076fab8 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -81,6 +81,7 @@ set(SRC intern/rct.c intern/scanfill.c intern/smallhash.c + intern/stack.c intern/storage.c intern/string.c intern/string_cursor_utf8.c @@ -135,6 +136,7 @@ set(SRC BLI_rect.h BLI_scanfill.h BLI_smallhash.h + BLI_stack.h BLI_string.h BLI_string_cursor_utf8.h BLI_string_utf8.h diff --git a/source/blender/blenlib/intern/stack.c b/source/blender/blenlib/intern/stack.c new file mode 100644 index 00000000000..84af6d29c5a --- /dev/null +++ b/source/blender/blenlib/intern/stack.c @@ -0,0 +1,103 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * Contributor(s): Nicholas Bishop + * + * ***** END GPL LICENSE BLOCK ***** + * + */ + +#include "BLI_stack.h" +#include "BLI_utildefines.h" +#include "MEM_guardedalloc.h" +#include <string.h> + +typedef struct BLI_Stack { + void *data; + + int totelem; + int maxelem; + + int elem_size; +} BLI_Stack; + +BLI_Stack *BLI_stack_new(int elem_size, const char *description) +{ + BLI_Stack *stack = MEM_callocN(sizeof(*stack), description); + + stack->elem_size = elem_size; + + return stack; +} + +void BLI_stack_free(BLI_Stack *stack) +{ + if (stack) { + if (stack->data) + MEM_freeN(stack->data); + MEM_freeN(stack); + } +} + +/* Gets the last element in the stack */ +#define STACK_LAST_ELEM(stack__) \ + (((char*)(stack__)->data) + \ + ((stack__)->elem_size * ((stack__)->totelem - 1))) + +void BLI_stack_push(BLI_Stack *stack, void *src) +{ + /* Ensure stack is large enough */ + if (stack->totelem == stack->maxelem) { + if (stack->maxelem == 0) { + /* Initialize stack with space for a small hardcoded + * number of elements */ + stack->maxelem = 32; + stack->data = MEM_mallocN((stack->elem_size * + stack->maxelem), AT); + } + else { + /* Double stack size */ + int maxelem = stack->maxelem + stack->maxelem; + /* Check for overflow */ + BLI_assert(maxelem > stack->maxelem); + stack->data = MEM_reallocN(stack->data, + (stack->elem_size * + maxelem)); + stack->maxelem = maxelem; + } + } + + BLI_assert(stack->totelem < stack->maxelem); + + /* Copy source to end of stack */ + stack->totelem++; + memcpy(STACK_LAST_ELEM(stack), src, stack->elem_size); +} + +void BLI_stack_pop(BLI_Stack *stack, void *dst) +{ + BLI_assert(stack->totelem > 0); + if (stack->totelem > 0) { + memcpy(dst, STACK_LAST_ELEM(stack), stack->elem_size); + stack->totelem--; + } +} + +int BLI_stack_empty(const BLI_Stack *stack) +{ + return stack->totelem == 0; +} |