ucx/stack.c

   1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
   3  *
   4  * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions are met:
   8  *
   9  *   1. Redistributions of source code must retain the above copyright
  10  *      notice, this list of conditions and the following disclaimer.
  11  *
  12  *   2. Redistributions in binary form must reproduce the above copyright
  13  *      notice, this list of conditions and the following disclaimer in the
  14  *      documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  26  * POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #include "ucx/stack.h"
  30
  31 #include <string.h>
  32
  33 static size_t ucx_stack_align(size_t n) {
  34     int align = n % sizeof(void*);
  35     if (align) {
  36         n += sizeof(void*) - align;
  37     }
  38     return n;
  39 }
  40
  41 void ucx_stack_init(UcxStack *stack, char* space, size_t size) {
  42     stack->size = size - size % sizeof(void*);
  43     stack->space = space;
  44     stack->top = NULL;
  45
  46     stack->allocator.pool = stack;
  47     stack->allocator.malloc = (ucx_allocator_malloc) ucx_stack_malloc;
  48     stack->allocator.calloc = (ucx_allocator_calloc) ucx_stack_calloc;
  49     stack->allocator.realloc = (ucx_allocator_realloc) ucx_stack_realloc;
  50     stack->allocator.free = (ucx_allocator_free) ucx_stack_free;
  51 }
  52
  53 void *ucx_stack_malloc(UcxStack *stack, size_t n) {
  54
  55     if (ucx_stack_avail(stack) < ucx_stack_align(n)) {
  56         return NULL;
  57     } else {
  58         char *prev = stack->top;
  59         if (stack->top) {
  60             stack->top += ucx_stack_align(ucx_stack_topsize(stack));
  61         } else {
  62             stack->top = stack->space;
  63         }
  64
  65         ((struct ucx_stack_metadata*)stack->top)->prev = prev;
  66         ((struct ucx_stack_metadata*)stack->top)->size = n;
  67         stack->top += sizeof(struct ucx_stack_metadata);
  68
  69         return stack->top;
  70     }
  71 }
  72
  73 void *ucx_stack_calloc(UcxStack *stack, size_t nelem, size_t elsize) {
  74     void *mem = ucx_stack_malloc(stack, nelem*elsize);
  75     memset(mem, 0, nelem*elsize);
  76     return mem;
  77 }
  78
  79 void *ucx_stack_realloc(UcxStack *stack, void *ptr, size_t n) {
  80     if (ptr == stack->top) {
  81         if (stack->size - (stack->top - stack->space) < ucx_stack_align(n)) {
  82             return NULL;
  83         } else {
  84             ((struct ucx_stack_metadata*)stack->top - 1)->size = n;
  85             return ptr;
  86         }
  87     } else {
  88         if (ucx_stack_align(((struct ucx_stack_metadata*)ptr - 1)->size) <
  89                 ucx_stack_align(n)) {
  90             void *nptr = ucx_stack_malloc(stack, n);
  91             if (nptr) {
  92                 memcpy(nptr, ptr, n);
  93                 ucx_stack_free(stack, ptr);
  94
  95                 return nptr;
  96             } else {
  97                 return NULL;
  98             }
  99         } else {
 100             ((struct ucx_stack_metadata*)ptr - 1)->size = n;
 101             return ptr;
 102         }
 103     }
 104 }
 105
 106 void ucx_stack_free(UcxStack *stack, void *ptr) {
 107     if (ptr == stack->top) {
 108         stack->top = ((struct ucx_stack_metadata*) stack->top - 1)->prev;
 109     } else {
 110         struct ucx_stack_metadata *next = (struct ucx_stack_metadata*)(
 111             (char*)ptr +
 112             ucx_stack_align(((struct ucx_stack_metadata*) ptr - 1)->size)
 113         );
 114         next->prev = ((struct ucx_stack_metadata*) ptr - 1)->prev;
 115     }
 116 }
 117
 118 void ucx_stack_popn(UcxStack *stack, void *dest, size_t n) {
 119     if (ucx_stack_empty(stack)) {
 120         return;
 121     }
 122
 123     if (dest) {
 124         size_t len = ucx_stack_topsize(stack);
 125         if (len > n) {
 126             len = n;
 127         }
 128
 129         memcpy(dest, stack->top, len);
 130     }
 131
 132     ucx_stack_free(stack, stack->top);
 133 }
 134
 135 size_t ucx_stack_avail(UcxStack *stack) {
 136     size_t avail = ((stack->top ? (stack->size
 137                     - (stack->top - stack->space)
 138                     - ucx_stack_align(ucx_stack_topsize(stack)))
 139                     : stack->size));
 140
 141     if (avail > sizeof(struct ucx_stack_metadata)) {
 142         return avail - sizeof(struct ucx_stack_metadata);
 143     } else {
 144         return 0;
 145     }
 146 }
 147
 148 void *ucx_stack_push(UcxStack *stack, size_t n, const void *data) {
 149     void *space = ucx_stack_malloc(stack, n);
 150     if (space) {
 151         memcpy(space, data, n);
 152     }
 153     return space;
 154 }
 155
 156 void *ucx_stack_pusharr(UcxStack *stack,
 157         size_t nelem, size_t elsize, const void *data) {
 158
 159     // skip the memset by using malloc
 160     void *space = ucx_stack_malloc(stack, nelem*elsize);
 161     if (space) {
 162         memcpy(space, data, nelem*elsize);
 163     }
 164     return space;
 165 }