ucx/stack.h@1e51558b9d09
ucx/stack.h
Sun, 17 May 2015 17:31:32 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Sun, 17 May 2015 17:31:32 +0200
- changeset 192
- 1e51558b9d09
- parent 188
- 63f87e2884c1
- child 217
- e056e4e0b08e
- permissions
- -rw-r--r--
updated copyright notice + added files for upcoming AVL tree implementation
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2015 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 */
29 /**
30 * @file stack.h
31 *
32 * Default stack memory allocation implementation.
33 *
34 * @author Mike Becker
35 * @author Olaf Wintermann
36 */
38 #ifndef UCX_STACK_H
39 #define UCX_STACK_H
41 #include "ucx.h"
42 #include <stdint.h>
43 #include "allocator.h"
45 #ifdef __cplusplus
46 extern "C" {
47 #endif
50 /**
51 * UCX stack structure.
52 */
53 typedef struct {
54 /** UcxAllocator based on this stack */
55 UcxAllocator allocator;
57 /** Stack size. */
58 size_t size;
60 /** Pointer to the bottom of the stack */
61 char *space;
63 /** Pointer to the top of the stack */
64 char *top;
65 } UcxStack;
67 /**
68 * Metadata for each UCX stack element.
69 */
70 struct ucx_stack_metadata {
71 /**
72 * Location of the previous element (<code>NULL</code> if this is the first)
73 */
74 char *prev;
76 /** Size of this element */
77 size_t size;
78 };
80 /**
81 * Initializes UcxStack structure with memory.
82 *
83 * @param stack a pointer to an uninitialized stack structure
84 * @param space the memory area that shall be managed
85 * @param size size of the memory area
86 * @return a new UcxStack structure
87 */
88 void ucx_stack_init(UcxStack *stack, char* space, size_t size);
90 /**
91 * Allocates stack memory.
92 *
93 * @param stack a pointer to the stack
94 * @param n amount of memory to allocate
95 * @return a pointer to the allocated memory
96 * @see ucx_allocator_malloc()
97 */
98 void *ucx_stack_malloc(UcxStack *stack, size_t n);
100 /**
101 * Alias for #ucx_stack_malloc().
102 * @param stack a pointer to the stack
103 * @param n amount of memory to allocate
104 * @return a pointer to the allocated memory
105 * @see ucx_stack_malloc
106 */
107 #define ucx_stack_push(stack, n) ucx_stack_malloc(stack, n)
109 /**
110 * Allocates an array of stack memory
111 *
112 * The content of the allocated memory is set to zero.
113 *
114 * @param stack a pointer to the stack
115 * @param nelem amount of elements to allocate
116 * @param elsize amount of memory per element
117 * @return a pointer to the allocated memory
118 * @see ucx_allocator_calloc()
119 */
120 void *ucx_stack_calloc(UcxStack *stack, size_t nelem, size_t elsize);
122 /**
123 * Alias for #ucx_stack_calloc().
124 *
125 * @param stack a pointer to the stack
126 * @param n amount of elements to allocate
127 * @param elsize amount of memory per element
128 * @return a pointer to the allocated memory
129 * @see ucx_stack_calloc
130 */
131 #define ucx_stack_pusharr(stack,n,elsize) ucx_stack_calloc(stack,n,elssize)
133 /**
134 * Reallocates memory on the stack.
135 *
136 * Shrinking memory is always safe. Extending memory can be very expensive.
137 *
138 * @param stack the stack
139 * @param ptr a pointer to the memory that shall be reallocated
140 * @param n the new size of the memory
141 * @return a pointer to the new location of the memory
142 * @see ucx_allocator_realloc()
143 */
144 void *ucx_stack_realloc(UcxStack *stack, void *ptr, size_t n);
146 /**
147 * Frees memory on the stack.
148 *
149 * Freeing stack memory behaves in a special way.
150 *
151 * If the element, that should be freed, is the top most element of the stack,
152 * it is removed from the stack. Otherwise it is marked as freed. Marked
153 * elements are removed, when they become the top most elements of the stack.
154 *
155 * @param stack a pointer to the stack
156 * @param ptr a pointer to the memory that shall be freed
157 */
158 void ucx_stack_free(UcxStack *stack, void *ptr);
161 /**
162 * Returns the size of the top most element.
163 * @param stack a pointer to the stack
164 * @return the size of the top most element
165 */
166 #define ucx_stack_topsize(stack) ((stack)->top ? ((struct ucx_stack_metadata*)\
167 (stack)->top - 1)->size : 0)
169 /**
170 * Removes the top most element from the stack and copies the content to <code>
171 * dest</code>, if specified.
172 *
173 * Use #ucx_stack_topsize()# to get the amount of memory that must be available
174 * at the location of <code>dest</code>.
175 *
176 * @param stack a pointer to the stack
177 * @param dest the location where the contents shall be written to, or <code>
178 * NULL</code>, if the element shall only be removed.
179 * @see ucx_stack_free
180 * @see ucx_stack_popn
181 */
182 #define ucx_stack_pop(stack, dest) ucx_stack_popn(stack, dest, SIZE_MAX)
184 /**
185 * Removes the top most element from the stack and copies the content to <code>
186 * dest</code>.
187 *
188 * In contrast to #ucx_stack_pop() the <code>dest</code> pointer <code>MUST
189 * NOT</code> be <code>NULL</code>.
190 *
191 * @param stack a pointer to the stack
192 * @param dest the location where the contents shall be written to
193 * @param n copies at most n elements to <code>dest</code>
194 * @see ucx_stack_pop
195 */
196 void ucx_stack_popn(UcxStack *stack, void *dest, size_t n);
198 /**
199 * Returns the remaining available memory on the specified stack.
200 *
201 * @param stack a pointer to the stack
202 * @return the remaining available memory
203 */
204 size_t ucx_stack_avail(UcxStack *stack);
206 /**
207 * Checks, if the stack is empty.
208 *
209 * @param stack a pointer to the stack
210 * @return nonzero, if the stack is empty, zero otherwise
211 */
212 #define ucx_stack_empty(stack) (!(stack)->top)
214 /**
215 * Computes a recommended size for the stack memory area. Note, that
216 * reallocations have not been taken into account, so you might need to reserve
217 * twice as much memory to allow many reallocations.
218 *
219 * @param size the approximate payload
220 * @param elems the approximate count of element allocations
221 * @return a recommended size for the stack space based on the information
222 * provided
223 */
224 #define ucx_stack_dim(size, elems) (size+sizeof(struct ucx_stack_metadata) * \
225 (elems + 1))
228 #ifdef __cplusplus
229 }
230 #endif
232 #endif /* UCX_STACK_H */
