1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/ucx/stack.h Tue Oct 17 16:15:41 2017 +0200
1.3 @@ -0,0 +1,232 @@
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 +/**
1.33 + * @file stack.h
1.34 + *
1.35 + * Default stack memory allocation implementation.
1.36 + *
1.37 + * @author Mike Becker
1.38 + * @author Olaf Wintermann
1.39 + */
1.40 +
1.41 +#ifndef UCX_STACK_H
1.42 +#define UCX_STACK_H
1.43 +
1.44 +#include <ucx/ucx.h>
1.45 +#include <ucx/allocator.h>
1.46 +
1.47 +#ifdef __cplusplus
1.48 +extern "C" {
1.49 +#endif
1.50 +
1.51 +
1.52 +/**
1.53 + * UCX stack structure.
1.54 + */
1.55 +typedef struct {
1.56 + /** UcxAllocator based on this stack */
1.57 + UcxAllocator allocator;
1.58 +
1.59 + /** Stack size. */
1.60 + size_t size;
1.61 +
1.62 + /** Pointer to the bottom of the stack */
1.63 + char *space;
1.64 +
1.65 + /** Pointer to the top of the stack */
1.66 + char *top;
1.67 +} UcxStack;
1.68 +
1.69 +/**
1.70 + * Metadata for each UCX stack element.
1.71 + */
1.72 +struct ucx_stack_metadata {
1.73 + /**
1.74 + * Location of the previous element (<code>NULL</code> if this is the first)
1.75 + */
1.76 + char *prev;
1.77 +
1.78 + /** Size of this element */
1.79 + size_t size;
1.80 +};
1.81 +
1.82 +/**
1.83 + * Initializes UcxStack structure with memory.
1.84 + *
1.85 + * @param stack a pointer to an uninitialized stack structure
1.86 + * @param space the memory area that shall be managed
1.87 + * @param size size of the memory area
1.88 + * @return a new UcxStack structure
1.89 + */
1.90 +void ucx_stack_init(UcxStack *stack, char* space, size_t size);
1.91 +
1.92 +/**
1.93 + * Allocates stack memory.
1.94 + *
1.95 + * @param stack a pointer to the stack
1.96 + * @param n amount of memory to allocate
1.97 + * @return a pointer to the allocated memory
1.98 + * @see ucx_allocator_malloc()
1.99 + */
1.100 +void *ucx_stack_malloc(UcxStack *stack, size_t n);
1.101 +
1.102 +/**
1.103 + * Alias for #ucx_stack_malloc().
1.104 + * @param stack a pointer to the stack
1.105 + * @param n amount of memory to allocate
1.106 + * @return a pointer to the allocated memory
1.107 + * @see ucx_stack_malloc
1.108 + */
1.109 +#define ucx_stack_push(stack, n) ucx_stack_malloc(stack, n)
1.110 +
1.111 +/**
1.112 + * Allocates an array of stack memory
1.113 + *
1.114 + * The content of the allocated memory is set to zero.
1.115 + *
1.116 + * @param stack a pointer to the stack
1.117 + * @param nelem amount of elements to allocate
1.118 + * @param elsize amount of memory per element
1.119 + * @return a pointer to the allocated memory
1.120 + * @see ucx_allocator_calloc()
1.121 + */
1.122 +void *ucx_stack_calloc(UcxStack *stack, size_t nelem, size_t elsize);
1.123 +
1.124 +/**
1.125 + * Alias for #ucx_stack_calloc().
1.126 + *
1.127 + * @param stack a pointer to the stack
1.128 + * @param n amount of elements to allocate
1.129 + * @param elsize amount of memory per element
1.130 + * @return a pointer to the allocated memory
1.131 + * @see ucx_stack_calloc
1.132 + */
1.133 +#define ucx_stack_pusharr(stack,n,elsize) ucx_stack_calloc(stack,n,elssize)
1.134 +
1.135 +/**
1.136 + * Reallocates memory on the stack.
1.137 + *
1.138 + * Shrinking memory is always safe. Extending memory can be very expensive.
1.139 + *
1.140 + * @param stack the stack
1.141 + * @param ptr a pointer to the memory that shall be reallocated
1.142 + * @param n the new size of the memory
1.143 + * @return a pointer to the new location of the memory
1.144 + * @see ucx_allocator_realloc()
1.145 + */
1.146 +void *ucx_stack_realloc(UcxStack *stack, void *ptr, size_t n);
1.147 +
1.148 +/**
1.149 + * Frees memory on the stack.
1.150 + *
1.151 + * Freeing stack memory behaves in a special way.
1.152 + *
1.153 + * If the element, that should be freed, is the top most element of the stack,
1.154 + * it is removed from the stack. Otherwise it is marked as freed. Marked
1.155 + * elements are removed, when they become the top most elements of the stack.
1.156 + *
1.157 + * @param stack a pointer to the stack
1.158 + * @param ptr a pointer to the memory that shall be freed
1.159 + */
1.160 +void ucx_stack_free(UcxStack *stack, void *ptr);
1.161 +
1.162 +
1.163 +/**
1.164 + * Returns the size of the top most element.
1.165 + * @param stack a pointer to the stack
1.166 + * @return the size of the top most element
1.167 + */
1.168 +#define ucx_stack_topsize(stack) ((stack)->top ? ((struct ucx_stack_metadata*)\
1.169 + (stack)->top - 1)->size : 0)
1.170 +
1.171 +/**
1.172 + * Removes the top most element from the stack and copies the content to <code>
1.173 + * dest</code>, if specified.
1.174 + *
1.175 + * Use #ucx_stack_topsize()# to get the amount of memory that must be available
1.176 + * at the location of <code>dest</code>.
1.177 + *
1.178 + * @param stack a pointer to the stack
1.179 + * @param dest the location where the contents shall be written to, or <code>
1.180 + * NULL</code>, if the element shall only be removed.
1.181 + * @see ucx_stack_free
1.182 + * @see ucx_stack_popn
1.183 + */
1.184 +#define ucx_stack_pop(stack, dest) ucx_stack_popn(stack, dest, (size_t)-1)
1.185 +
1.186 +/**
1.187 + * Removes the top most element from the stack and copies the content to <code>
1.188 + * dest</code>.
1.189 + *
1.190 + * In contrast to #ucx_stack_pop() the <code>dest</code> pointer <code>MUST
1.191 + * NOT</code> be <code>NULL</code>.
1.192 + *
1.193 + * @param stack a pointer to the stack
1.194 + * @param dest the location where the contents shall be written to
1.195 + * @param n copies at most n elements to <code>dest</code>
1.196 + * @see ucx_stack_pop
1.197 + */
1.198 +void ucx_stack_popn(UcxStack *stack, void *dest, size_t n);
1.199 +
1.200 +/**
1.201 + * Returns the remaining available memory on the specified stack.
1.202 + *
1.203 + * @param stack a pointer to the stack
1.204 + * @return the remaining available memory
1.205 + */
1.206 +size_t ucx_stack_avail(UcxStack *stack);
1.207 +
1.208 +/**
1.209 + * Checks, if the stack is empty.
1.210 + *
1.211 + * @param stack a pointer to the stack
1.212 + * @return nonzero, if the stack is empty, zero otherwise
1.213 + */
1.214 +#define ucx_stack_empty(stack) (!(stack)->top)
1.215 +
1.216 +/**
1.217 + * Computes a recommended size for the stack memory area. Note, that
1.218 + * reallocations have not been taken into account, so you might need to reserve
1.219 + * twice as much memory to allow many reallocations.
1.220 + *
1.221 + * @param size the approximate payload
1.222 + * @param elems the approximate count of element allocations
1.223 + * @return a recommended size for the stack space based on the information
1.224 + * provided
1.225 + */
1.226 +#define ucx_stack_dim(size, elems) (size+sizeof(struct ucx_stack_metadata) * \
1.227 + (elems + 1))
1.228 +
1.229 +
1.230 +#ifdef __cplusplus
1.231 +}
1.232 +#endif
1.233 +
1.234 +#endif /* UCX_STACK_H */
1.235 +
