1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/stack.c Tue Oct 17 16:15:41 2017 +0200
1.3 @@ -0,0 +1,144 @@
1.4 +/*
1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 + *
1.7 + * Copyright 2017 Olaf Wintermann. All rights reserved.
1.8 + *
1.9 + * Redistribution and use in source and binary forms, with or without
1.10 + * modification, are permitted provided that the following conditions are met:
1.11 + *
1.12 + * 1. Redistributions of source code must retain the above copyright
1.13 + * notice, this list of conditions and the following disclaimer.
1.14 + *
1.15 + * 2. Redistributions in binary form must reproduce the above copyright
1.16 + * notice, this list of conditions and the following disclaimer in the
1.17 + * documentation and/or other materials provided with the distribution.
1.18 + *
1.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
1.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
1.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
1.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
1.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
1.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
1.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
1.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
1.29 + * POSSIBILITY OF SUCH DAMAGE.
1.30 + */
1.31 +
1.32 +#include "ucx/stack.h"
1.33 +
1.34 +#include <string.h>
1.35 +
1.36 +static size_t ucx_stack_align(size_t n) {
1.37 + int align = n % sizeof(void*);
1.38 + if (align) {
1.39 + n += sizeof(void*) - align;
1.40 + }
1.41 + return n;
1.42 +}
1.43 +
1.44 +void ucx_stack_init(UcxStack *stack, char* space, size_t size) {
1.45 + stack->size = size - size % sizeof(void*);
1.46 + stack->space = space;
1.47 + stack->top = NULL;
1.48 +
1.49 + stack->allocator.pool = stack;
1.50 + stack->allocator.malloc = (ucx_allocator_malloc) ucx_stack_malloc;
1.51 + stack->allocator.calloc = (ucx_allocator_calloc) ucx_stack_calloc;
1.52 + stack->allocator.realloc = (ucx_allocator_realloc) ucx_stack_realloc;
1.53 + stack->allocator.free = (ucx_allocator_free) ucx_stack_free;
1.54 +}
1.55 +
1.56 +void *ucx_stack_malloc(UcxStack *stack, size_t n) {
1.57 +
1.58 + if (ucx_stack_avail(stack) < ucx_stack_align(n)) {
1.59 + return NULL;
1.60 + } else {
1.61 + char *prev = stack->top;
1.62 + if (stack->top) {
1.63 + stack->top += ucx_stack_align(ucx_stack_topsize(stack));
1.64 + } else {
1.65 + stack->top = stack->space;
1.66 + }
1.67 +
1.68 + ((struct ucx_stack_metadata*)stack->top)->prev = prev;
1.69 + ((struct ucx_stack_metadata*)stack->top)->size = n;
1.70 + stack->top += sizeof(struct ucx_stack_metadata);
1.71 +
1.72 + return stack->top;
1.73 + }
1.74 +}
1.75 +
1.76 +void *ucx_stack_calloc(UcxStack *stack, size_t nelem, size_t elsize) {
1.77 + void *mem = ucx_stack_malloc(stack, nelem*elsize);
1.78 + memset(mem, 0, nelem*elsize);
1.79 + return mem;
1.80 +}
1.81 +
1.82 +void *ucx_stack_realloc(UcxStack *stack, void *ptr, size_t n) {
1.83 + if (ptr == stack->top) {
1.84 + if (stack->size - (stack->top - stack->space) < ucx_stack_align(n)) {
1.85 + return NULL;
1.86 + } else {
1.87 + ((struct ucx_stack_metadata*)stack->top - 1)->size = n;
1.88 + return ptr;
1.89 + }
1.90 + } else {
1.91 + if (ucx_stack_align(((struct ucx_stack_metadata*)ptr - 1)->size) <
1.92 + ucx_stack_align(n)) {
1.93 + void *nptr = ucx_stack_malloc(stack, n);
1.94 + if (nptr) {
1.95 + memcpy(nptr, ptr, n);
1.96 + ucx_stack_free(stack, ptr);
1.97 +
1.98 + return nptr;
1.99 + } else {
1.100 + return NULL;
1.101 + }
1.102 + } else {
1.103 + ((struct ucx_stack_metadata*)ptr - 1)->size = n;
1.104 + return ptr;
1.105 + }
1.106 + }
1.107 +}
1.108 +
1.109 +void ucx_stack_free(UcxStack *stack, void *ptr) {
1.110 + if (ptr == stack->top) {
1.111 + stack->top = ((struct ucx_stack_metadata*) stack->top - 1)->prev;
1.112 + } else {
1.113 + struct ucx_stack_metadata *next = (struct ucx_stack_metadata*)(
1.114 + (char*)ptr +
1.115 + ucx_stack_align(((struct ucx_stack_metadata*) ptr - 1)->size)
1.116 + );
1.117 + next->prev = ((struct ucx_stack_metadata*) ptr - 1)->prev;
1.118 + }
1.119 +}
1.120 +
1.121 +void ucx_stack_popn(UcxStack *stack, void *dest, size_t n) {
1.122 + if (ucx_stack_empty(stack)) {
1.123 + return;
1.124 + }
1.125 +
1.126 + size_t len = ucx_stack_topsize(stack);
1.127 + if (len > n) {
1.128 + len = n;
1.129 + }
1.130 +
1.131 + memcpy(dest, stack->top, len);
1.132 +
1.133 + ucx_stack_free(stack, stack->top);
1.134 +}
1.135 +
1.136 +size_t ucx_stack_avail(UcxStack *stack) {
1.137 + size_t avail = ((stack->top ? (stack->size
1.138 + - (stack->top - stack->space)
1.139 + - ucx_stack_align(ucx_stack_topsize(stack)))
1.140 + : stack->size));
1.141 +
1.142 + if (avail > sizeof(struct ucx_stack_metadata)) {
1.143 + return avail - sizeof(struct ucx_stack_metadata);
1.144 + } else {
1.145 + return 0;
1.146 + }
1.147 +}
