--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/stack.c Tue Oct 17 16:15:41 2017 +0200
@@ -0,0 +1,144 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
+ *
+ * Copyright 2017 Olaf Wintermann. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "ucx/stack.h"
+
+#include <string.h>
+
+static size_t ucx_stack_align(size_t n) {
+ int align = n % sizeof(void*);
+ if (align) {
+ n += sizeof(void*) - align;
+ }
+ return n;
+}
+
+void ucx_stack_init(UcxStack *stack, char* space, size_t size) {
+ stack->size = size - size % sizeof(void*);
+ stack->space = space;
+ stack->top = NULL;
+
+ stack->allocator.pool = stack;
+ stack->allocator.malloc = (ucx_allocator_malloc) ucx_stack_malloc;
+ stack->allocator.calloc = (ucx_allocator_calloc) ucx_stack_calloc;
+ stack->allocator.realloc = (ucx_allocator_realloc) ucx_stack_realloc;
+ stack->allocator.free = (ucx_allocator_free) ucx_stack_free;
+}
+
+void *ucx_stack_malloc(UcxStack *stack, size_t n) {
+
+ if (ucx_stack_avail(stack) < ucx_stack_align(n)) {
+ return NULL;
+ } else {
+ char *prev = stack->top;
+ if (stack->top) {
+ stack->top += ucx_stack_align(ucx_stack_topsize(stack));
+ } else {
+ stack->top = stack->space;
+ }
+
+ ((struct ucx_stack_metadata*)stack->top)->prev = prev;
+ ((struct ucx_stack_metadata*)stack->top)->size = n;
+ stack->top += sizeof(struct ucx_stack_metadata);
+
+ return stack->top;
+ }
+}
+
+void *ucx_stack_calloc(UcxStack *stack, size_t nelem, size_t elsize) {
+ void *mem = ucx_stack_malloc(stack, nelem*elsize);
+ memset(mem, 0, nelem*elsize);
+ return mem;
+}
+
+void *ucx_stack_realloc(UcxStack *stack, void *ptr, size_t n) {
+ if (ptr == stack->top) {
+ if (stack->size - (stack->top - stack->space) < ucx_stack_align(n)) {
+ return NULL;
+ } else {
+ ((struct ucx_stack_metadata*)stack->top - 1)->size = n;
+ return ptr;
+ }
+ } else {
+ if (ucx_stack_align(((struct ucx_stack_metadata*)ptr - 1)->size) <
+ ucx_stack_align(n)) {
+ void *nptr = ucx_stack_malloc(stack, n);
+ if (nptr) {
+ memcpy(nptr, ptr, n);
+ ucx_stack_free(stack, ptr);
+
+ return nptr;
+ } else {
+ return NULL;
+ }
+ } else {
+ ((struct ucx_stack_metadata*)ptr - 1)->size = n;
+ return ptr;
+ }
+ }
+}
+
+void ucx_stack_free(UcxStack *stack, void *ptr) {
+ if (ptr == stack->top) {
+ stack->top = ((struct ucx_stack_metadata*) stack->top - 1)->prev;
+ } else {
+ struct ucx_stack_metadata *next = (struct ucx_stack_metadata*)(
+ (char*)ptr +
+ ucx_stack_align(((struct ucx_stack_metadata*) ptr - 1)->size)
+ );
+ next->prev = ((struct ucx_stack_metadata*) ptr - 1)->prev;
+ }
+}
+
+void ucx_stack_popn(UcxStack *stack, void *dest, size_t n) {
+ if (ucx_stack_empty(stack)) {
+ return;
+ }
+
+ size_t len = ucx_stack_topsize(stack);
+ if (len > n) {
+ len = n;
+ }
+
+ memcpy(dest, stack->top, len);
+
+ ucx_stack_free(stack, stack->top);
+}
+
+size_t ucx_stack_avail(UcxStack *stack) {
+ size_t avail = ((stack->top ? (stack->size
+ - (stack->top - stack->space)
+ - ucx_stack_align(ucx_stack_topsize(stack)))
+ : stack->size));
+
+ if (avail > sizeof(struct ucx_stack_metadata)) {
+ return avail - sizeof(struct ucx_stack_metadata);
+ } else {
+ return 0;
+ }
+}