line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
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 |
9
|
|
|
|
|
|
|
#include |
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 |
48
|
95
|
|
|
|
|
|
srl_stack_init(pTHX_ srl_stack_t * stack, size_t size) |
49
|
|
|
|
|
|
|
{ |
50
|
|
|
|
|
|
|
assert(size > 0); |
51
|
|
|
|
|
|
|
assert(stack != NULL); |
52
|
|
|
|
|
|
|
|
53
|
95
|
|
|
|
|
|
stack->begin = NULL; |
54
|
95
|
50
|
|
|
|
|
Newx(stack->begin, size, srl_stack_type_t); |
55
|
95
|
50
|
|
|
|
|
if (expect_false(stack->begin == NULL)) |
56
|
0
|
|
|
|
|
|
return 1; |
57
|
|
|
|
|
|
|
|
58
|
95
|
|
|
|
|
|
stack->end = stack->begin + size - 1; |
59
|
95
|
|
|
|
|
|
stack->ptr = NULL; |
60
|
95
|
|
|
|
|
|
stack->depth = -1; |
61
|
|
|
|
|
|
|
|
62
|
|
|
|
|
|
|
assert(SRL_STACK_SIZE(stack) == (int) size); |
63
|
95
|
|
|
|
|
|
return 0; |
64
|
|
|
|
|
|
|
} |
65
|
|
|
|
|
|
|
|
66
|
|
|
|
|
|
|
SRL_STATIC_INLINE void |
67
|
0
|
|
|
|
|
|
srl_stack_grow(pTHX_ srl_stack_t *stack) |
68
|
|
|
|
|
|
|
{ |
69
|
0
|
|
|
|
|
|
ptrdiff_t pos = SRL_STACK_DEPTH(stack); |
70
|
0
|
|
|
|
|
|
size_t new_size = SRL_STACK_SIZE(stack) * 2; |
71
|
|
|
|
|
|
|
assert(new_size <= 1024 * 1024); |
72
|
|
|
|
|
|
|
|
73
|
0
|
0
|
|
|
|
|
Renew(stack->begin, new_size, srl_stack_type_t); |
74
|
0
|
0
|
|
|
|
|
if (stack->begin == NULL) |
75
|
0
|
|
|
|
|
|
croak("Out of memory"); |
76
|
|
|
|
|
|
|
|
77
|
0
|
|
|
|
|
|
stack->end = stack->begin + new_size - 1; |
78
|
0
|
|
|
|
|
|
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
|
0
|
|
|
|
|
|
} |
84
|
|
|
|
|
|
|
|
85
|
|
|
|
|
|
|
/* Free stack arrfer (not not the stack struct */ |
86
|
|
|
|
|
|
|
SRL_STATIC_INLINE void |
87
|
133
|
|
|
|
|
|
srl_stack_deinit(pTHX_ srl_stack_t *stack) |
88
|
|
|
|
|
|
|
{ |
89
|
133
|
50
|
|
|
|
|
if (stack == NULL || stack->begin == NULL) return; |
|
|
50
|
|
|
|
|
|
90
|
133
|
|
|
|
|
|
Safefree(stack->begin); |
91
|
|
|
|
|
|
|
} |
92
|
|
|
|
|
|
|
|
93
|
|
|
|
|
|
|
SRL_STATIC_INLINE int |
94
|
38
|
|
|
|
|
|
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
|
38
|
|
|
|
|
|
to->begin = NULL; |
101
|
38
|
|
|
|
|
|
size = SRL_STACK_SIZE(from); |
102
|
|
|
|
|
|
|
|
103
|
38
|
50
|
|
|
|
|
Newx(to->begin, size, srl_stack_type_t); |
104
|
38
|
50
|
|
|
|
|
if (expect_false(to->begin == NULL)) |
105
|
0
|
|
|
|
|
|
return 1; |
106
|
|
|
|
|
|
|
|
107
|
38
|
50
|
|
|
|
|
if (from->ptr == NULL) { |
108
|
0
|
|
|
|
|
|
to->ptr = NULL; |
109
|
|
|
|
|
|
|
} else { |
110
|
38
|
50
|
|
|
|
|
Copy(from->begin, to->begin, SRL_STACK_SPACE(from), srl_stack_type_t); |
111
|
38
|
|
|
|
|
|
to->ptr = to->begin + from->depth; |
112
|
|
|
|
|
|
|
} |
113
|
|
|
|
|
|
|
|
114
|
38
|
|
|
|
|
|
to->end = to->begin + size - 1; |
115
|
38
|
|
|
|
|
|
to->depth = from->depth; |
116
|
|
|
|
|
|
|
|
117
|
|
|
|
|
|
|
DEBUG_ASSERT_STACK_SANE(to); |
118
|
|
|
|
|
|
|
assert(SRL_STACK_SIZE(to) == (int) size); |
119
|
38
|
|
|
|
|
|
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 |
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 |
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 |