ucx/ucx/stack.h

   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 /**
  30  * @file stack.h
  31  *
  32  * Default stack memory allocation implementation.
  33  *
  34  * @author Mike Becker
  35  * @author Olaf Wintermann
  36  */
  37
  38 #ifndef UCX_STACK_H
  39 #define UCX_STACK_H
  40
  41 #include "ucx.h"
  42 #include "allocator.h"
  43
  44 #ifdef  __cplusplus
  45 extern "C" {
  46 #endif
  47
  48
  49 /**
  50  * UCX stack structure.
  51  */
  52 typedef struct {
  53     /** UcxAllocator based on this stack */
  54     UcxAllocator allocator;
  55
  56     /** Stack size. */
  57     size_t size;
  58
  59     /** Pointer to the bottom of the stack */
  60     char *space;
  61
  62     /** Pointer to the top of the stack */
  63     char *top;
  64 } UcxStack;
  65
  66 /**
  67  * Metadata for each UCX stack element.
  68  */
  69 struct ucx_stack_metadata {
  70     /**
  71      * Location of the previous element (<code>NULL</code> if this is the first)
  72      */
  73     char *prev;
  74
  75     /** Size of this element */
  76     size_t size;
  77 };
  78
  79 /**
  80  * Initializes UcxStack structure with memory.
  81  *
  82  * @param stack a pointer to an uninitialized stack structure
  83  * @param space the memory area that shall be managed
  84  * @param size size of the memory area
  85  * @return a new UcxStack structure
  86  */
  87 void ucx_stack_init(UcxStack *stack, char* space, size_t size);
  88
  89 /**
  90  * Allocates stack memory.
  91  *
  92  * @param stack a pointer to the stack
  93  * @param n amount of memory to allocate
  94  * @return a pointer to the allocated memory or <code>NULL</code> on stack
  95  * overflow
  96  * @see ucx_allocator_malloc()
  97  */
  98 void *ucx_stack_malloc(UcxStack *stack, size_t n);
  99
 100 /**
 101  * Allocates memory with #ucx_stack_malloc() and copies the specified data if
 102  * the allocation was successful.
 103  *
 104  * @param stack a pointer to the stack
 105  * @param n amount of memory to allocate
 106  * @param data a pointer to the data to copy
 107  * @return a pointer to the allocated memory
 108  * @see ucx_stack_malloc
 109  */
 110 void *ucx_stack_push(UcxStack *stack, size_t n, const void *data);
 111
 112 /**
 113  * Allocates an array of stack memory
 114  *
 115  * The content of the allocated memory is set to zero.
 116  *
 117  * @param stack a pointer to the stack
 118  * @param nelem amount of elements to allocate
 119  * @param elsize amount of memory per element
 120  * @return a pointer to the allocated memory
 121  * @see ucx_allocator_calloc()
 122  */
 123 void *ucx_stack_calloc(UcxStack *stack, size_t nelem, size_t elsize);
 124
 125 /**
 126  * Allocates memory with #ucx_stack_calloc() and copies the specified data if
 127  * the allocation was successful.
 128  *
 129  * @param stack a pointer to the stack
 130  * @param nelem amount of elements to allocate
 131  * @param elsize amount of memory per element
 132  * @param data a pointer to the data
 133  * @return a pointer to the allocated memory
 134  * @see ucx_stack_calloc
 135  */
 136 void *ucx_stack_pusharr(UcxStack *stack,
 137         size_t nelem, size_t elsize, const void *data);
 138
 139 /**
 140  * Reallocates memory on the stack.
 141  *
 142  * Shrinking memory is always safe. Extending memory can be very expensive.
 143  *
 144  * @param stack the stack
 145  * @param ptr a pointer to the memory that shall be reallocated
 146  * @param n the new size of the memory
 147  * @return a pointer to the new location of the memory
 148  * @see ucx_allocator_realloc()
 149  */
 150 void *ucx_stack_realloc(UcxStack *stack, void *ptr, size_t n);
 151
 152 /**
 153  * Frees memory on the stack.
 154  *
 155  * Freeing stack memory behaves in a special way.
 156  *
 157  * If the element, that should be freed, is the top most element of the stack,
 158  * it is removed from the stack. Otherwise it is marked as freed. Marked
 159  * elements are removed, when they become the top most elements of the stack.
 160  *
 161  * @param stack a pointer to the stack
 162  * @param ptr a pointer to the memory that shall be freed
 163  */
 164 void ucx_stack_free(UcxStack *stack, void *ptr);
 165
 166
 167 /**
 168  * Returns the size of the top most element.
 169  * @param stack a pointer to the stack
 170  * @return the size of the top most element
 171  */
 172 #define ucx_stack_topsize(stack) ((stack)->top ? ((struct ucx_stack_metadata*)\
 173                                   (stack)->top - 1)->size : 0)
 174
 175 /**
 176  * Removes the top most element from the stack and copies the content to <code>
 177  * dest</code>, if specified.
 178  *
 179  * Use #ucx_stack_topsize()# to get the amount of memory that must be available
 180  * at the location of <code>dest</code>.
 181  *
 182  * @param stack a pointer to the stack
 183  * @param dest the location where the contents shall be written to, or <code>
 184  * NULL</code>, if the element shall only be removed.
 185  * @see ucx_stack_free
 186  * @see ucx_stack_popn
 187  */
 188 #define ucx_stack_pop(stack, dest) ucx_stack_popn(stack, dest, (size_t)-1)
 189
 190 /**
 191  * Removes the top most element from the stack and copies the content to <code>
 192  * dest</code>.
 193  *
 194  * This function copies at most <code>n</code> bytes to the destination, but
 195  * the element is always freed as a whole.
 196  * If the element was larger than <code>n</code>, the remaining data is lost.
 197  *
 198  * @param stack a pointer to the stack
 199  * @param dest the location where the contents shall be written to
 200  * @param n copies at most n bytes to <code>dest</code>
 201  * @see ucx_stack_pop
 202  */
 203 void ucx_stack_popn(UcxStack *stack, void *dest, size_t n);
 204
 205 /**
 206  * Returns the remaining available memory on the specified stack.
 207  *
 208  * @param stack a pointer to the stack
 209  * @return the remaining available memory
 210  */
 211 size_t ucx_stack_avail(UcxStack *stack);
 212
 213 /**
 214  * Checks, if the stack is empty.
 215  *
 216  * @param stack a pointer to the stack
 217  * @return nonzero, if the stack is empty, zero otherwise
 218  */
 219 #define ucx_stack_empty(stack) (!(stack)->top)
 220
 221 /**
 222  * Computes a recommended size for the stack memory area. Note, that
 223  * reallocations have not been taken into account, so you might need to reserve
 224  * twice as much memory to allow many reallocations.
 225  *
 226  * @param size the approximate payload
 227  * @param elems the approximate count of element allocations
 228  * @return a recommended size for the stack space based on the information
 229  * provided
 230  */
 231 #define ucx_stack_dim(size, elems) (size+sizeof(struct ucx_stack_metadata) * \
 232                                     (elems + 1))
 233
 234
 235 #ifdef  __cplusplus
 236 }
 237 #endif
 238
 239 #endif  /* UCX_STACK_H */
 240