[Cogl] [PATCH] Adds internal CoglMemoryStack utility API

[Robert Bragg]

From: Robert Bragg <robert at linux.intel.com>

This adds a very minimal internal allocator api that lets us create a
dynamically growable (grow only) stack.

Underlying the allocator is the idea of "sub stacks" which are simply
malloc()'d chunks of memory kept in a linked list. The stack itself
maintains a pointer to the current sub-stack and a current
sub-stack-offset. 99% of the time allocating from the stack is just a
case of returning a pointer to the current sub-stack + sub-stack-offset
and bumping the offset by the allocation size. If there isn't room in
the current sub-stack then we walk through the list of free sub-stacks
looking for one that's big enough for the allocation and if we reach the
end of the list then we allocate a new sub-stack twice as big as the
last (or twice as big as the requested allocation if that's bigger).

Since it's a stack model there is no api to free allocations, just a
function to rewind the stack to the beginning.

We expect this to be useful in multiple places in Cogl as an extremely
fast allocator in cases when we know we can scrap all the allocations
after we're done figuring something out or as a building block for
other allocators.

For example the tessellator used for CoglPath allocates lots of tiny
structures that can all be freed after tessellation.
---
 cogl/Makefile.am                 |    2 +
 cogl/cogl-memory-stack-private.h |   51 ++++++++++++
 cogl/cogl-memory-stack.c         |  162 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 215 insertions(+), 0 deletions(-)
 create mode 100644 cogl/cogl-memory-stack-private.h
 create mode 100644 cogl/cogl-memory-stack.c

diff --git a/cogl/Makefile.am b/cogl/Makefile.am
index c459140..691d50f 100644
--- a/cogl/Makefile.am
+++ b/cogl/Makefile.am
@@ -329,6 +329,8 @@ cogl_sources_c = \
 	$(srcdir)/gl-prototypes/cogl-in-gles2-core-functions.h	\
 	$(srcdir)/gl-prototypes/cogl-fixed-functions.h	\
 	$(srcdir)/gl-prototypes/cogl-glsl-functions.h	\
+	$(srcdir)/cogl-memory-stack-private.h		\
+	$(srcdir)/cogl-memory-stack.c			\
 	$(NULL)
 
 if USE_GLIB
diff --git a/cogl/cogl-memory-stack-private.h b/cogl/cogl-memory-stack-private.h
new file mode 100644
index 0000000..858807a
--- /dev/null
+++ b/cogl/cogl-memory-stack-private.h
@@ -0,0 +1,51 @@
+/*
+ * Cogl
+ *
+ * An object oriented GL/GLES Abstraction/Utility Layer
+ *
+ * Copyright (C) 2011 Intel Corporation.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ *
+ */
+
+#if !defined(__COGL_H_INSIDE__) && !defined(CLUTTER_COMPILATION)
+#error "Only <cogl/cogl.h> can be included directly."
+#endif
+
+#include <glib.h>
+
+#ifndef __COGL_MEMORY_STACK__
+#define __COGL_MEMORY_STACK__
+
+G_BEGIN_DECLS
+
+typedef struct _CoglMemoryStack CoglMemoryStack;
+
+CoglMemoryStack *
+_cogl_memory_stack_new (size_t initial_size_bytes);
+
+void *
+_cogl_memory_stack_alloc (CoglMemoryStack *stack, size_t bytes);
+
+void
+_cogl_memory_stack_rewind (CoglMemoryStack *stack);
+
+void
+_cogl_memory_stack_free (CoglMemoryStack *stack);
+
+G_END_DECLS
+
+#endif /* __COGL_MEMORY_STACK__ */
diff --git a/cogl/cogl-memory-stack.c b/cogl/cogl-memory-stack.c
new file mode 100644
index 0000000..c7e05fd
--- /dev/null
+++ b/cogl/cogl-memory-stack.c
@@ -0,0 +1,162 @@
+/*
+ * Cogl
+ *
+ * An object oriented GL/GLES Abstraction/Utility Layer
+ *
+ * Copyright (C) 2011 Intel Corporation.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ *
+ * CoglMemoryStack provides a really simple, but lightning fast
+ * memory stack allocation strategy:
+ *
+ * - The underlying pool of memory is grow-only.
+ * - The pool is considered to be a stack which may be comprised
+ *   of multiple smaller stacks. Allocation is done as follows:
+ *    - If there enough memory in the current sub-stack then the
+ *      stack-pointer will be returned as the allocation and
+ *      the stack-pointer will be incremented by the allocation
+ *      size.
+ *    - If there isn't enough memory in the current sub-stack
+ *      then a new sub-stack is allocated twice as big as the
+ *      current sub-stack and the stack-pointer is set to the
+ *      start of the new sub-stack.
+ * - Allocations can't be freed in a random-order, you can only
+ *   rewind the entire stack back to the start. There is no
+ *   the concept of stack frames to allow partial rewinds.
+ *
+ * We currently use this in our tesselator which has to allocate
+ * lots of small vertex, edge and face structures but once tesselation
+ * has been finished we just want to free the whole lot in one go.
+ *
+ *
+ * Authors:
+ *   Robert Bragg <robert at linux.intel.com>
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include "cogl-memory-stack-private.h"
+#include <glib.h>
+
+typedef struct _CoglMemorySubStack
+{
+  size_t bytes;
+  guint8 *data;
+} CoglMemorySubStack;
+
+typedef struct _CoglMemoryStack
+{
+  GQueue *sub_stacks;
+
+  GList *sub_stack_link;
+  size_t sub_stack_offset;
+} CoglMemoryStack;
+
+static CoglMemorySubStack *
+_cogl_memory_sub_stack_alloc (size_t bytes)
+{
+  CoglMemorySubStack *sub_stack = g_slice_new (CoglMemorySubStack);
+  sub_stack->bytes = bytes;
+  sub_stack->data = g_malloc (bytes);
+  return sub_stack;
+}
+
+static void
+_cogl_memory_stack_add_sub_stack (CoglMemoryStack *stack,
+                                  size_t sub_stack_bytes)
+{
+  CoglMemorySubStack *sub_stack =
+    _cogl_memory_sub_stack_alloc (sub_stack_bytes);
+  g_queue_push_tail (stack->sub_stacks, sub_stack);
+  stack->sub_stack_link = stack->sub_stacks->tail;
+  stack->sub_stack_offset = 0;
+}
+
+CoglMemoryStack *
+_cogl_memory_stack_new (size_t initial_size_bytes)
+{
+  CoglMemoryStack *stack = g_slice_new0 (CoglMemoryStack);
+
+  stack->sub_stacks = g_queue_new ();
+
+  _cogl_memory_stack_add_sub_stack (stack, initial_size_bytes);
+
+  return stack;
+}
+
+void *
+_cogl_memory_stack_alloc (CoglMemoryStack *stack, size_t bytes)
+{
+  GList *l;
+  CoglMemorySubStack *sub_stack;
+  void *ret;
+
+  sub_stack = stack->sub_stack_link->data;
+  if (G_LIKELY (sub_stack->bytes - stack->sub_stack_offset >= bytes))
+    {
+      ret = sub_stack->data + stack->sub_stack_offset;
+      stack->sub_stack_offset += bytes;
+      return ret;
+    }
+
+  for (l = stack->sub_stack_link->next; l; l = l->next)
+    {
+      sub_stack = l->data;
+
+      if (sub_stack->bytes >= bytes)
+        {
+          ret = sub_stack->data;
+          stack->sub_stack_link = l;
+          stack->sub_stack_offset = bytes;
+          return ret;
+        }
+    }
+
+  sub_stack = stack->sub_stacks->tail->data;
+
+  _cogl_memory_stack_add_sub_stack (stack, MAX (sub_stack->bytes, bytes) * 2);
+  sub_stack = stack->sub_stacks->tail->data;
+
+  stack->sub_stack_offset += bytes;
+
+  return sub_stack->data;
+}
+
+void
+_cogl_memory_stack_rewind (CoglMemoryStack *stack)
+{
+  stack->sub_stack_link = stack->sub_stacks->head;
+  stack->sub_stack_offset = 0;
+}
+
+static void
+free_sub_stack (void *data, void *user_data)
+{
+  CoglMemorySubStack *sub_stack = data;
+  g_free (sub_stack->data);
+  g_slice_free (CoglMemorySubStack, sub_stack);
+}
+
+void
+_cogl_memory_stack_free (CoglMemoryStack *stack)
+{
+  g_queue_foreach (stack->sub_stacks, free_sub_stack, NULL);
+  g_queue_free (stack->sub_stacks);
+  g_slice_free (CoglMemoryStack, stack);
+}
-- 
1.7.7.6