[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [49591] trunk/blender/source/blender/ blenlib: Add an array-based generic stack structure to blenlib
Nicholas Bishop
nicholasbishop at gmail.com
Mon Aug 6 01:29:44 CEST 2012
Revision: 49591
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=49591
Author: nicholasbishop
Date: 2012-08-05 23:29:43 +0000 (Sun, 05 Aug 2012)
Log Message:
-----------
Add an array-based generic stack structure to blenlib
Very simple stack with homogeneous contents. Provides push, pop, and
is-empty operations.
Modified Paths:
--------------
trunk/blender/source/blender/blenlib/CMakeLists.txt
Added Paths:
-----------
trunk/blender/source/blender/blenlib/BLI_stack.h
trunk/blender/source/blender/blenlib/intern/stack.c
Added: trunk/blender/source/blender/blenlib/BLI_stack.h
===================================================================
--- trunk/blender/source/blender/blenlib/BLI_stack.h (rev 0)
+++ trunk/blender/source/blender/blenlib/BLI_stack.h 2012-08-05 23:29:43 UTC (rev 49591)
@@ -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
Modified: trunk/blender/source/blender/blenlib/CMakeLists.txt
===================================================================
--- trunk/blender/source/blender/blenlib/CMakeLists.txt 2012-08-05 22:31:55 UTC (rev 49590)
+++ trunk/blender/source/blender/blenlib/CMakeLists.txt 2012-08-05 23:29:43 UTC (rev 49591)
@@ -81,6 +81,7 @@
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 @@
BLI_rect.h
BLI_scanfill.h
BLI_smallhash.h
+ BLI_stack.h
BLI_string.h
BLI_string_cursor_utf8.h
BLI_string_utf8.h
Added: trunk/blender/source/blender/blenlib/intern/stack.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/stack.c (rev 0)
+++ trunk/blender/source/blender/blenlib/intern/stack.c 2012-08-05 23:29:43 UTC (rev 49591)
@@ -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;
+}
More information about the Bf-blender-cvs
mailing list