|
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 */ |
|
28 |
|
29 #include "stack.h" |
|
30 #include <string.h> |
|
31 |
|
32 static size_t ucx_stack_align(size_t n) { |
|
33 int align = n % sizeof(void*); |
|
34 if (align) { |
|
35 n += sizeof(void*) - align; |
|
36 } |
|
37 return n; |
|
38 } |
|
39 |
|
40 void ucx_stack_init(UcxStack *stack, char* space, size_t size) { |
|
41 stack->size = size - size % sizeof(void*); |
|
42 stack->space = space; |
|
43 stack->top = NULL; |
|
44 |
|
45 stack->allocator.pool = stack; |
|
46 stack->allocator.malloc = (ucx_allocator_malloc) ucx_stack_malloc; |
|
47 stack->allocator.calloc = (ucx_allocator_calloc) ucx_stack_calloc; |
|
48 stack->allocator.realloc = (ucx_allocator_realloc) ucx_stack_realloc; |
|
49 stack->allocator.free = (ucx_allocator_free) ucx_stack_free; |
|
50 } |
|
51 |
|
52 void *ucx_stack_malloc(UcxStack *stack, size_t n) { |
|
53 |
|
54 if (ucx_stack_avail(stack) < ucx_stack_align(n)) { |
|
55 return NULL; |
|
56 } else { |
|
57 char *prev = stack->top; |
|
58 if (stack->top) { |
|
59 stack->top += ucx_stack_align(ucx_stack_topsize(stack)); |
|
60 } else { |
|
61 stack->top = stack->space; |
|
62 } |
|
63 |
|
64 ((struct ucx_stack_metadata*)stack->top)->prev = prev; |
|
65 ((struct ucx_stack_metadata*)stack->top)->size = n; |
|
66 stack->top += sizeof(struct ucx_stack_metadata); |
|
67 |
|
68 return stack->top; |
|
69 } |
|
70 } |
|
71 |
|
72 void *ucx_stack_calloc(UcxStack *stack, size_t nelem, size_t elsize) { |
|
73 void *mem = ucx_stack_malloc(stack, nelem*elsize); |
|
74 memset(mem, 0, nelem*elsize); |
|
75 return mem; |
|
76 } |
|
77 |
|
78 void *ucx_stack_realloc(UcxStack *stack, void *ptr, size_t n) { |
|
79 if (ptr == stack->top) { |
|
80 if (stack->size - (stack->top - stack->space) < ucx_stack_align(n)) { |
|
81 return NULL; |
|
82 } else { |
|
83 ((struct ucx_stack_metadata*)stack->top - 1)->size = n; |
|
84 return ptr; |
|
85 } |
|
86 } else { |
|
87 if (ucx_stack_align(((struct ucx_stack_metadata*)ptr - 1)->size) < |
|
88 ucx_stack_align(n)) { |
|
89 void *nptr = ucx_stack_malloc(stack, n); |
|
90 if (nptr) { |
|
91 memcpy(nptr, ptr, n); |
|
92 ucx_stack_free(stack, ptr); |
|
93 |
|
94 return nptr; |
|
95 } else { |
|
96 return NULL; |
|
97 } |
|
98 } else { |
|
99 ((struct ucx_stack_metadata*)ptr - 1)->size = n; |
|
100 return ptr; |
|
101 } |
|
102 } |
|
103 } |
|
104 |
|
105 void ucx_stack_free(UcxStack *stack, void *ptr) { |
|
106 if (ptr == stack->top) { |
|
107 stack->top = ((struct ucx_stack_metadata*) stack->top - 1)->prev; |
|
108 } else { |
|
109 struct ucx_stack_metadata *next = (struct ucx_stack_metadata*)( |
|
110 (char*)ptr + |
|
111 ucx_stack_align(((struct ucx_stack_metadata*) ptr - 1)->size) |
|
112 ); |
|
113 next->prev = ((struct ucx_stack_metadata*) ptr - 1)->prev; |
|
114 } |
|
115 } |
|
116 |
|
117 void ucx_stack_popn(UcxStack *stack, void *dest, size_t n) { |
|
118 if (ucx_stack_empty(stack)) { |
|
119 return; |
|
120 } |
|
121 |
|
122 size_t len = ucx_stack_topsize(stack); |
|
123 if (len > n) { |
|
124 len = n; |
|
125 } |
|
126 |
|
127 memcpy(dest, stack->top, len); |
|
128 |
|
129 ucx_stack_free(stack, stack->top); |
|
130 } |
|
131 |
|
132 size_t ucx_stack_avail(UcxStack *stack) { |
|
133 size_t avail = ((stack->top ? (stack->size |
|
134 - (stack->top - stack->space) |
|
135 - ucx_stack_align(ucx_stack_topsize(stack))) |
|
136 : stack->size)); |
|
137 |
|
138 if (avail > sizeof(struct ucx_stack_metadata)) { |
|
139 return avail - sizeof(struct ucx_stack_metadata); |
|
140 } else { |
|
141 return 0; |
|
142 } |
|
143 } |