1 #ifndef SRL_STACK_H_
2 #define SRL_STACK_H_
3
4 #ifndef srl_stack_type_t
5 #error define srl_stack_type_t before including srl_stack.h
6 #endif
7
8 #include <stdlib.h>
9 #include <assert.h>
10 #include "srl_inline.h"
11 #include "srl_common.h"
12
13 #define DEBUG_ASSERT_STACK_PTR(stack, ptr) \
14 assert((ptr) >= (stack)->begin && (ptr) <= (stack)->end)
15
16 #define DEBUG_ASSERT_STACK_SANE(stack) STMT_START { \
17 assert((stack) != NULL); \
18 assert((stack)->begin != NULL); \
19 assert((stack)->end != NULL); \
20 assert((stack)->begin <= (stack)->end); \
21 assert((stack)->ptr == NULL || \
22 ((stack)->ptr >= (stack)->begin && (stack)->ptr <= (stack)->end)); \
23 assert(((stack)->ptr == NULL && (stack)->depth == -1) || \
24 ((stack)->ptr - (stack)->begin) == (stack)->depth); \
25 } STMT_END
26
27 #ifdef TRACE_STACK
28 # define SRL_STACK_TRACE(msg, args...) \
29 fprintf(stderr, "%s:%d:%s(): "msg"\n", __FILE__, __LINE__, __func__, args)
30 #else
31 # define SRL_STACK_TRACE(msg, args...)
32 #endif
33
34 #define SRL_STACK_SIZE(stack) (((stack)->end - (stack)->begin) + 1)
35 #define SRL_STACK_SPACE(stack) (((stack)->ptr - (stack)->begin) + 1)
36 #define SRL_STACK_DEPTH(stack) ((stack)->depth)
37
38 typedef struct srl_stack srl_stack_t;
39 typedef struct srl_stack * srl_stack_ptr;
40
41 struct srl_stack {
42 IV depth; /* benchmarking showed that calculating depth takes up to 5%, so we store it */
43 srl_stack_type_t *ptr, *begin, *end;
44 };
45
46 /* Allocate new arrfer (but not the stack struct */
47 SRL_STATIC_INLINE int
srl_stack_init(pTHX_ srl_stack_t * stack,size_t size)48 srl_stack_init(pTHX_ srl_stack_t * stack, size_t size)
49 {
50 assert(size > 0);
51 assert(stack != NULL);
52
53 stack->begin = NULL;
54 Newx(stack->begin, size, srl_stack_type_t);
55 if (expect_false(stack->begin == NULL))
56 return 1;
57
58 stack->end = stack->begin + size - 1;
59 stack->ptr = NULL;
60 stack->depth = -1;
61
62 assert(SRL_STACK_SIZE(stack) == (int) size);
63 return 0;
64 }
65
66 SRL_STATIC_INLINE void
srl_stack_grow(pTHX_ srl_stack_t * stack)67 srl_stack_grow(pTHX_ srl_stack_t *stack)
68 {
69 ptrdiff_t pos = SRL_STACK_DEPTH(stack);
70 size_t new_size = SRL_STACK_SIZE(stack) * 2;
71 assert(new_size <= 1024 * 1024);
72
73 Renew(stack->begin, new_size, srl_stack_type_t);
74 if (stack->begin == NULL)
75 croak("Out of memory");
76
77 stack->end = stack->begin + new_size - 1;
78 stack->ptr = stack->begin + pos;
79
80 DEBUG_ASSERT_STACK_SANE(stack);
81 assert(SRL_STACK_SIZE(stack) == (int) new_size);
82 SRL_STACK_TRACE("grew stack to size %zu", new_size);
83 }
84
85 /* Free stack arrfer (not not the stack struct */
86 SRL_STATIC_INLINE void
srl_stack_deinit(pTHX_ srl_stack_t * stack)87 srl_stack_deinit(pTHX_ srl_stack_t *stack)
88 {
89 if (stack == NULL || stack->begin == NULL) return;
90 Safefree(stack->begin);
91 }
92
93 SRL_STATIC_INLINE int
srl_stack_copy(pTHX_ srl_stack_t * from,srl_stack_t * to)94 srl_stack_copy(pTHX_ srl_stack_t *from, srl_stack_t *to)
95 {
96 size_t size;
97 assert(from != NULL);
98 assert(to != NULL);
99
100 to->begin = NULL;
101 size = SRL_STACK_SIZE(from);
102
103 Newx(to->begin, size, srl_stack_type_t);
104 if (expect_false(to->begin == NULL))
105 return 1;
106
107 if (from->ptr == NULL) {
108 to->ptr = NULL;
109 } else {
110 Copy(from->begin, to->begin, SRL_STACK_SPACE(from), srl_stack_type_t);
111 to->ptr = to->begin + from->depth;
112 }
113
114 to->end = to->begin + size - 1;
115 to->depth = from->depth;
116
117 DEBUG_ASSERT_STACK_SANE(to);
118 assert(SRL_STACK_SIZE(to) == (int) size);
119 return 0;
120 }
121
122 #define srl_stack_clear(stack) STMT_START { \
123 DEBUG_ASSERT_STACK_SANE(stack); \
124 (stack)->ptr = NULL; \
125 (stack)->depth = -1; \
126 } STMT_END
127
128 #define srl_stack_ptr(stack) ((stack)->ptr)
129 #define srl_stack_empty(stack) ((stack)->ptr == NULL)
130 #define srl_stack_full(stack) ((stack)->ptr >= (stack)->end)
131
132 #define srl_stack_push_ptr(stack, val_ptr) STMT_START { \
133 DEBUG_ASSERT_STACK_SANE(stack); \
134 \
135 if (expect_false(srl_stack_empty(stack))) { \
136 (stack)->ptr = (stack)->begin; \
137 (val_ptr) = (stack)->begin; \
138 } else { \
139 if (expect_false(srl_stack_full(stack))) \
140 srl_stack_grow(aTHX_ (stack)); \
141 \
142 (val_ptr) = ++(stack)->ptr; \
143 } \
144 \
145 (stack)->depth++; \
146 \
147 DEBUG_ASSERT_STACK_SANE(stack); \
148 SRL_STACK_TRACE("pushed value on stack, current depth %d", \
149 (int) SRL_STACK_DEPTH(stack)); \
150 } STMT_END
151
152 #define srl_stack_push_val(stack, val) STMT_START { \
153 DEBUG_ASSERT_STACK_SANE(stack); \
154 \
155 if (expect_false(srl_stack_empty(stack))) { \
156 (stack)->ptr = (stack)->begin; \
157 } else { \
158 if (expect_false(srl_stack_full(stack))) \
159 srl_stack_grow(aTHX_ (stack)); \
160 \
161 (stack)->ptr++; \
162 } \
163 \
164 *(stack)->ptr = (val); \
165 (stack)->depth++; \
166 \
167 DEBUG_ASSERT_STACK_SANE(stack); \
168 SRL_STACK_TRACE("pushed value on stack, current depth %d", \
169 (int) SRL_STACK_DEPTH(stack)); \
170 } STMT_END
171
172
173 #define srl_stack_pop_nocheck(stack) STMT_START { \
174 DEBUG_ASSERT_STACK_SANE(stack); \
175 \
176 if (expect_false((stack)->ptr == (stack)->begin)) { \
177 (stack)->ptr = NULL; \
178 } else { \
179 (stack)->ptr--; \
180 } \
181 \
182 (stack)->depth--; \
183 \
184 DEBUG_ASSERT_STACK_SANE(stack); \
185 SRL_STACK_TRACE("poped stack, current depth %d", \
186 (int) SRL_STACK_DEPTH(stack)); \
187 } STMT_END
188
189 #define srl_stack_pop(stack) STMT_START { \
190 if (expect_false(srl_stack_empty(stack))) \
191 croak("Pop empty stack"); \
192 \
193 srl_stack_pop_nocheck(stack); \
194 } STMT_END
195
196 SRL_STATIC_INLINE srl_stack_type_t
srl_stack_peek_nocheck(pTHX_ srl_stack_t * stack)197 srl_stack_peek_nocheck(pTHX_ srl_stack_t *stack)
198 {
199 DEBUG_ASSERT_STACK_SANE(stack);
200 return *stack->ptr;
201 }
202
203 SRL_STATIC_INLINE srl_stack_type_t
srl_stack_peek(pTHX_ srl_stack_t * stack)204 srl_stack_peek(pTHX_ srl_stack_t *stack)
205 {
206 DEBUG_ASSERT_STACK_SANE(stack);
207 if (expect_false(srl_stack_empty(stack)))
208 croak("srl_stack_peek on empty stack");
209
210 return srl_stack_peek_nocheck(aTHX_ stack);
211 }
212
213 #endif
214