| 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 |