Debian Codegraph @

src/headers/template_stack.h

raw
1 /* 'checkit_tiff' is a conformance checker for baseline TIFFs
2 *
3 * author: Andreas Romeyke, 2015-2022
4 * licensed under conditions of libtiff
5 * (see http://libtiff.maptools.org/misc.html)
6 *
7 * stack implementation
8 */
9
10 /* the stack size depends on count of rules and count of numbers, in general
11 * 65536 should be enough, otherwise you need to increase it */
12
13 /* TODO: We could improve the push-back actions, if we allocate stack, but hold the pointer to first element
14 * in the middle of the allocated memory. This allows us to operate wih pointers instead using memmove.
15 */
16
17 #include <assert.h>
18 #include <stddef.h>
19 #include <stdio.h>
20 #include <stdlib.h>
21 #include "parser_types.h"
22 #include "check.h"
23
24 #ifdef TEMPLATE_STACK_MAXSTACKDEPTH
25 #error "TEMPLATE_STACK_MAXSTACKDEPT was already defined, but should be exclusive for " __FILE__
26 #endif
27 #ifdef TEMPLATE_STACK_INTERNALSTACKDEPTH
28 #error "TEMPLATE_STACK_INTERNALSTACKDEPTH was already defined, but should be exclusive for " __FILE__
29 #endif
30 #define TEMPLATE_STACK_MAXSTACKDEPTH 65536
31 #define TEMPLATE_STACK_INTERNALSTACKDEPTH 32
32 //#define TEMPLATE_STACK_INTERNALSTACKDEPTH 4
33 //#define STACKDEBUG 1
34 //#define STACKSTAT 1
35
36
37 /*
38 #define T int
39 #define PRINT_TYPE(a,b) printf("%i,%i\n", a,b);
40 */
41
42 #ifndef T
43 #error "no stacktype <T> defined!"
44 #endif
45 #ifndef PRINT_TYPE
46 #error "set PRINT_TYPE to to a function which handles the signature 'f(int, <T>)"
47 #endif
48
49
50 #define CAT(a, b) a##b
51 #define PASTE(a, b) CAT(a, b)
52 #define JOIN(prefix, name) PASTE(prefix, PASTE(_, name))
53 #define STACK_S JOIN(T, stack_s)
54 #define STACK_T JOIN(T, stack_t)
55 #define STRINGIFY(a) #a
56 //#define T_AS_STRING STRINGIFY(T)
57 #define AS_STRING(a) "a"
58 #define QuoteIdent(ident) #ident
59 #define QuoteMacro(macro) QuoteIdent(macro)
60 #define T_AS_STRING QuoteMacro(T)
61
62 struct STACK_S {
63 const char * _first_caller;
64 int _first_line; /* line no */
65 size_t first_index; /* bottom value index */
66 size_t last_index; /* top value index */
67 size_t capacity; /* size of stack */
68 #ifdef STACKSTAT
69 stat_t stat;
70 #endif
71 T * value_p; /* values */
72 };
73
74
75 typedef struct STACK_S STACK_T;
76
77
78 /* init */
79 static void JOIN(T,init)(STACK_T *this, const char * caller, int line) {
80 assert(this != NULL);
81 if (this->value_p != NULL) {
82 fprintf(stderr, "stack of type %s was already initialized!\n", T_AS_STRING);
83 fprintf(stderr, "this caller (caller %s, %i)\n", caller, line);
84 fprintf(stderr, "first caller (caller %s, %i)\n",this->_first_caller, this->_first_line);
85 exit(EXIT_FAILURE);
86 }
87 this->_first_caller = strdup(caller);
88 this->_first_line = line;
89 this->capacity=TEMPLATE_STACK_INTERNALSTACKDEPTH;
90 this->first_index=this->capacity/3;
91 assert(this->first_index > 0);
92 this->last_index=this->first_index-1;
93 //assert(this->last_index >= 0);
94 #ifdef STACKSTAT
95 this->stat.stat_push_count=0;
96 this->stat.stat_pushback_count=0;
97 this->stat.stat_realloc_count=0;
98 #endif
99 this->value_p = calloc(TEMPLATE_STACK_INTERNALSTACKDEPTH,sizeof(T));
100 if (NULL == this->value_p) {
101 perror( "could not reallocate memory for stack, abort");
102 exit(EXIT_FAILURE);
103 }
104 #ifdef STACKDEBUG
105 printf("init stack of type %s\n", STRINGIFY(T) );
106 #endif
107 }
108
109 #define NEW new
110 static STACK_T * JOIN(T,NEW)(void) {
111 STACK_T *this = malloc( sizeof (STACK_T));
112 if (NULL == this) {
113 fprintf(stderr,"could not create a stack of type %s", T_AS_STRING);
114 exit(EXIT_FAILURE);
115 }
116 this->_first_caller="";
117 this->value_p=NULL;
118 JOIN(T,init)(this, __FILE__, __LINE__);
119 return this;
120 }
121 #undef NEW
122
123 static void JOIN(T, init_capacity) (STACK_T *this) {
124 if (this->value_p == NULL) {
125 //printf("calloc call\n");
126 this->value_p = calloc(this->capacity,sizeof(T));
127 if (NULL == this->value_p) {
128 perror( "could not allocate memory for increased stack, abort");
129 exit(EXIT_FAILURE);
130 }
131 }
132 }
133
134 /* increase capacity */
135 static void JOIN(T, increase_capacity) (STACK_T *this) {
136 #ifdef STACKSTAT
137 this->stat.stat_realloc_count++;
138 #endif
139 if (this->capacity == 0) {
140 //printf("simple first:%lu last:%lu\n", this->first_index, this->last_index);
141 this->capacity = TEMPLATE_STACK_INTERNALSTACKDEPTH;
142 this->first_index=this->capacity/3;
143 assert(this->first_index > 0);
144 this->last_index=this->first_index-1;
145 //assert(this->last_index >= 0);
146 }
147 if (this->capacity > TEMPLATE_STACK_MAXSTACKDEPTH) {
148 fprintf(stderr, "max stack capacity (current:%lu max:%u, size=%lu) reached, abort\n", this->capacity, TEMPLATE_STACK_MAXSTACKDEPTH, this->last_index - this->first_index);
149 exit(EXIT_FAILURE);
150 }
151 if (this->value_p == NULL) {
152 //printf("empty first:%lu last:%lu\n", this->first_index, this->last_index);
153 this->first_index=this->capacity/3;
154 assert(this->first_index > 0);
155 this->last_index=this->first_index-1;
156 //assert(this->last_index >= 0);
157 JOIN(T, init_capacity)(this);
158 } else {
159 T *new_value_p = NULL;
160 T *old_value_p = this->value_p;
161 size_t new_capacity = (3 * (this->capacity) / 2 );
162 //size_t new_capacity = 2 * this->capacity;
163 //printf("old capacity=%lu, new capacity=%lu, holding %lu values\n", this->capacity, new_capacity, this->last_index - this->first_index);
164 assert(old_value_p != NULL);
165 assert(new_capacity > this->capacity);
166 assert(new_capacity > 0);
167 assert(new_capacity > this->last_index);
168 #ifdef STACKDEBUG
169 printf("increased stack capacity for stacktype %s to %lu * %lu = %luBytes\n", T_AS_STRING, new_capacity,
170 sizeof(T), new_capacity * sizeof(T));
171 printf("this capacity was: %lu\n", this->capacity);
172 printf("this value_p points to: %p\n", (void *) this->value_p);
173 printf("realloc call\n");
174 #endif
175 #ifdef COMPAT_NEED_REALLOCARRAY
176 new_value_p = (T*) realloc( old_value_p, new_capacity * sizeof( T ));
177 #else
178 new_value_p = reallocarray(old_value_p, new_capacity, sizeof(T));
179 #endif
180 if (NULL == new_value_p) {
181 if (NULL != old_value_p) {
182 free(old_value_p);
183 }
184 perror("could not reallocate memory for increased stack, abort");
185 exit(EXIT_FAILURE);
186 }
187 this->capacity = new_capacity;
188 this->value_p = new_value_p;
189 }
190 }
191
192 /* is_empty */
193 static bool JOIN(T,is_empty)(STACK_T *this) {
194 return (this->last_index == this->first_index-1);
195 }
196
197 /* size() */
198 static size_t JOIN(T,size)(STACK_T *this) {
199 //printf("SIZE OF STACK is %li\n", (1+this->last_index - this->first_index));
200 return (1+ this->last_index - this->first_index);
201 }
202
203 /* reset_capacity() */
204 static void JOIN(T, reset_capacity) (STACK_T *this) {
205 if (
206 (JOIN(T, size)(this) < TEMPLATE_STACK_INTERNALSTACKDEPTH)
207 && (this->capacity > TEMPLATE_STACK_INTERNALSTACKDEPTH)
208 ){
209 size_t new_capacity = TEMPLATE_STACK_INTERNALSTACKDEPTH;
210 #ifdef STACKDEBUG
211 printf("decreased stack capacity for stacktype %s to %lu\n", STRINGIFY(T), new_capacity );
212 #endif
213 T *new_value_p = NULL;
214 #ifdef COMPAT_NEED_REALLOCARRAY
215 new_value_p = (T*) realloc( this->value_p, new_capacity * sizeof( T ));
216 #else
217 new_value_p = reallocarray(this->value_p, new_capacity, sizeof(T));
218 #endif
219 if (NULL == new_value_p) {
220 perror("could not reallocate memory for increased stack, abort");
221 exit(EXIT_FAILURE);
222 }
223 #ifdef STACKSTAT
224 this->stat.stat_realloc_count++;
225 #endif
226 this->capacity = new_capacity;
227 this->value_p = new_value_p;
228 }
229 }
230
231 /* delete() */
232 static void JOIN(T, delete) (STACK_T *this) {
233 if (JOIN(T, is_empty)(this)) {
234 free(this->value_p);
235 this->value_p = NULL;
236 this->capacity = 0;
237 #ifdef STACKSTAT
238 printf("------------------------\n");
239 printf("DEBUG STACK: %s\n", T_AS_STRING);
240 printf("%s push: %lu\n", T_AS_STRING, this->stat.stat_push_count);
241 printf("%s pushback: %lu\n", T_AS_STRING, this->stat.stat_pushback_count);
242 printf("%s realloc: %lu\n", T_AS_STRING, this->stat.stat_realloc_count);
243 printf("------------------------\n");
244 #endif
245 }
246 }
247
248 static void JOIN(T, print_typed_value) (int i, const T v) {
249 PRINT_TYPE(i,v);
250 }
251
252 /* print_top */
253 static void JOIN(T, print_top)(STACK_T *this) {
254 printf("################################################\n");
255 printf("\nstack (firstidx=%lu, lastidx=%lu, capacity=%lu, type=%s):\n", this->first_index, this->last_index,
256 this->capacity, T_AS_STRING);
257 printf("------------------------------------\n");
258 if (JOIN(T, is_empty)(this)) {
259 printf("empty stack (type=%s)\n", T_AS_STRING);
260 } else {
261 assert(this->last_index >= this->first_index);
262 for (size_t i = this->capacity - 1; i < (this->capacity); --i) {
263 if (i == this->first_index) { printf("first --->"); }
264 else if (i == this->last_index) { printf(" last --->"); }
265 else { printf(" "); }
266 JOIN(T, print_typed_value)(i, this->value_p[i]);
267 }
268 }
269
270 printf("------------------------------------\n");
271 printf("################################################\n\n");
272 }
273
274 /* push */
275 static void JOIN(T,push)(STACK_T *this, T v) {
276 if (
277 (this->capacity == 0) ||
278 ((size_t) this->last_index >= this->capacity - 1)
279 ) {
280 JOIN(T, increase_capacity)(this);
281 }
282 #ifdef STACKDEBUG
283 JOIN(T, print_top)(this);
284 printf("(push) this->last_index = %lu (after)\n", this->last_index + 1);
285 #endif
286 #ifdef STACKSTAT
287 this->stat.stat_push_count++;
288 #endif
289 assert(this->capacity > 0);
290 //printf("SSIZUE: %li last:%lu CAP:%lu\n", ( (ssize_t) this->last_index - this->first_index), this->last_index, this->capacity );
291 assert(( (ssize_t) this->last_index - (ssize_t) this->first_index) >= -1 );
292 assert(this->capacity > this->last_index);
293 this->value_p[++this->last_index] = v;
294 assert(this->first_index <= this->last_index);
295 }
296
297
298 /* pop */
299 static T JOIN(T,pop)(STACK_T *this) {
300 if (this->last_index < this->first_index) {
301 perror ("Stack underflow!");
302 exit(EXIT_FAILURE);
303 }
304 #ifdef STACKDEBUG
305 JOIN(T,print_top)(this);
306 printf ("(pop) this->last_index = %li (before)\n", this->last_index);
307 #endif
308 T v = this->value_p[this->last_index--];
309 #ifdef STACKDEBUG
310 JOIN(T,print_top)(this);
311 printf ("(pop) this->last_index = %li (before)\n", this->last_index);
312 printf("END AFTER pop\n");
313 #endif
314 if (JOIN(T, is_empty)(this)) {
315 JOIN(T, delete)(this);
316 } else if (this->last_index < TEMPLATE_STACK_INTERNALSTACKDEPTH / 2) {
317 JOIN(T, reset_capacity)(this);
318 assert(this->last_index >= this->first_index);
319 }
320 return v;
321 }
322
323 /* push_back */
324 static void JOIN(T,push_back)(STACK_T *this, const T v_init) {
325 //printf("pushback call first_index=%lu lastindex=%lu capacity=%lu\n", this->first_index, this->last_index, this->capacity);
326 //printf("VALUE: %lu\n", v_init);
327 if ((this->first_index > 0) ) {
328 this->first_index--;
329 this->value_p[this->first_index] = v_init;
330 } else {
331 size_t count_of_elements = this->last_index - this->first_index;
332 size_t new_first = count_of_elements / 3 + 1;
333 size_t new_last = new_first + count_of_elements;
334 if (new_last+1 >= this->capacity) {
335 /* there is no space in bikini bottom */
336 /* increase capacity */
337 //printf("INCREASE\n");
338 JOIN(T, increase_capacity)(this);
339 }
340 assert((long signed int) this->capacity > (long signed int) this->last_index);
341 assert((long signed int) this->capacity > (long signed int) new_last);
342 /* copy from first index to last index */
343
344 memmove(
345 this->value_p + new_first,
346 this->value_p + this->first_index,
347 ((1+count_of_elements) * sizeof(T))
348 );
349 /*
350 memset(this->value_p, 0xfe, (new_first-1)*sizeof(T));
351 memset(this->value_p + new_last + 1, 0xff , (this->capacity - new_last -1)*sizeof(T));
352 */
353 /*
354 memset(this->value_p, 0, (new_first-1)*sizeof(T));
355 memset(this->value_p + new_last + 1, 0 , (this->capacity - new_last -1)*sizeof(T));
356 */
357 this->first_index = new_first-1;
358 this->last_index = new_last;
359 //printf("pushback called first_index=%lu lastindex=%lu capacity=%lu\n", this->first_index, this->last_index, this->capacity);
360 /* copy v_init on top */
361 this->value_p[this->first_index] = v_init;
362 }
363 assert(this->first_index <= this->last_index);
364 #ifdef STACKSTAT
365 this->stat.stat_pushback_count++;
366 #endif
367
368 }
369
370 #undef TEMPLATE_STACK_MAXSTACKDEPTH
371 #undef TEMPLATE_STACK_INTERNALSTACKDEPTH
372 #undef T
373 #undef PRINT_TYPE