File Coverage

srl_stack.h
Criterion Covered Total %
statement 22 34 64.7
branch 8 20 40.0
condition n/a
subroutine n/a
pod n/a
total 30 54 55.5


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