/* 'checkit_tiff' is a conformance checker for baseline TIFFs * * author: Andreas Romeyke, 2015-2022 * licensed under conditions of libtiff * (see http://libtiff.maptools.org/misc.html) * * stack implementation */ /* the stack size depends on count of rules and count of numbers, in general * 65536 should be enough, otherwise you need to increase it */ /* TODO: We could improve the push-back actions, if we allocate stack, but hold the pointer to first element * in the middle of the allocated memory. This allows us to operate wih pointers instead using memmove. */ #include #include #include #include #include "parser_types.h" #include "check.h" #ifdef TEMPLATE_STACK_MAXSTACKDEPTH #error "TEMPLATE_STACK_MAXSTACKDEPT was already defined, but should be exclusive for " __FILE__ #endif #ifdef TEMPLATE_STACK_INTERNALSTACKDEPTH #error "TEMPLATE_STACK_INTERNALSTACKDEPTH was already defined, but should be exclusive for " __FILE__ #endif #define TEMPLATE_STACK_MAXSTACKDEPTH 65536 #define TEMPLATE_STACK_INTERNALSTACKDEPTH 32 //#define TEMPLATE_STACK_INTERNALSTACKDEPTH 4 //#define STACKDEBUG 1 //#define STACKSTAT 1 /* #define T int #define PRINT_TYPE(a,b) printf("%i,%i\n", a,b); */ #ifndef T #error "no stacktype defined!" #endif #ifndef PRINT_TYPE #error "set PRINT_TYPE to to a function which handles the signature 'f(int, )" #endif #define CAT(a, b) a##b #define PASTE(a, b) CAT(a, b) #define JOIN(prefix, name) PASTE(prefix, PASTE(_, name)) #define STACK_S JOIN(T, stack_s) #define STACK_T JOIN(T, stack_t) #define STRINGIFY(a) #a //#define T_AS_STRING STRINGIFY(T) #define AS_STRING(a) "a" #define QuoteIdent(ident) #ident #define QuoteMacro(macro) QuoteIdent(macro) #define T_AS_STRING QuoteMacro(T) struct STACK_S { const char * _first_caller; int _first_line; /* line no */ size_t first_index; /* bottom value index */ size_t last_index; /* top value index */ size_t capacity; /* size of stack */ #ifdef STACKSTAT stat_t stat; #endif T * value_p; /* values */ }; typedef struct STACK_S STACK_T; /* init */ static void JOIN(T,init)(STACK_T *this, const char * caller, int line) { assert(this != NULL); if (this->value_p != NULL) { fprintf(stderr, "stack of type %s was already initialized!\n", T_AS_STRING); fprintf(stderr, "this caller (caller %s, %i)\n", caller, line); fprintf(stderr, "first caller (caller %s, %i)\n",this->_first_caller, this->_first_line); exit(EXIT_FAILURE); } this->_first_caller = strdup(caller); this->_first_line = line; this->capacity=TEMPLATE_STACK_INTERNALSTACKDEPTH; this->first_index=this->capacity/3; assert(this->first_index > 0); this->last_index=this->first_index-1; //assert(this->last_index >= 0); #ifdef STACKSTAT this->stat.stat_push_count=0; this->stat.stat_pushback_count=0; this->stat.stat_realloc_count=0; #endif this->value_p = calloc(TEMPLATE_STACK_INTERNALSTACKDEPTH,sizeof(T)); if (NULL == this->value_p) { perror( "could not reallocate memory for stack, abort"); exit(EXIT_FAILURE); } #ifdef STACKDEBUG printf("init stack of type %s\n", STRINGIFY(T) ); #endif } #define NEW new static STACK_T * JOIN(T,NEW)(void) { STACK_T *this = malloc( sizeof (STACK_T)); if (NULL == this) { fprintf(stderr,"could not create a stack of type %s", T_AS_STRING); exit(EXIT_FAILURE); } this->_first_caller=""; this->value_p=NULL; JOIN(T,init)(this, __FILE__, __LINE__); return this; } #undef NEW static void JOIN(T, init_capacity) (STACK_T *this) { if (this->value_p == NULL) { //printf("calloc call\n"); this->value_p = calloc(this->capacity,sizeof(T)); if (NULL == this->value_p) { perror( "could not allocate memory for increased stack, abort"); exit(EXIT_FAILURE); } } } /* increase capacity */ static void JOIN(T, increase_capacity) (STACK_T *this) { #ifdef STACKSTAT this->stat.stat_realloc_count++; #endif if (this->capacity == 0) { //printf("simple first:%lu last:%lu\n", this->first_index, this->last_index); this->capacity = TEMPLATE_STACK_INTERNALSTACKDEPTH; this->first_index=this->capacity/3; assert(this->first_index > 0); this->last_index=this->first_index-1; //assert(this->last_index >= 0); } if (this->capacity > TEMPLATE_STACK_MAXSTACKDEPTH) { 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); exit(EXIT_FAILURE); } if (this->value_p == NULL) { //printf("empty first:%lu last:%lu\n", this->first_index, this->last_index); this->first_index=this->capacity/3; assert(this->first_index > 0); this->last_index=this->first_index-1; //assert(this->last_index >= 0); JOIN(T, init_capacity)(this); } else { T *new_value_p = NULL; T *old_value_p = this->value_p; size_t new_capacity = (3 * (this->capacity) / 2 ); //size_t new_capacity = 2 * this->capacity; //printf("old capacity=%lu, new capacity=%lu, holding %lu values\n", this->capacity, new_capacity, this->last_index - this->first_index); assert(old_value_p != NULL); assert(new_capacity > this->capacity); assert(new_capacity > 0); assert(new_capacity > this->last_index); #ifdef STACKDEBUG printf("increased stack capacity for stacktype %s to %lu * %lu = %luBytes\n", T_AS_STRING, new_capacity, sizeof(T), new_capacity * sizeof(T)); printf("this capacity was: %lu\n", this->capacity); printf("this value_p points to: %p\n", (void *) this->value_p); printf("realloc call\n"); #endif #ifdef COMPAT_NEED_REALLOCARRAY new_value_p = (T*) realloc( old_value_p, new_capacity * sizeof( T )); #else new_value_p = reallocarray(old_value_p, new_capacity, sizeof(T)); #endif if (NULL == new_value_p) { if (NULL != old_value_p) { free(old_value_p); } perror("could not reallocate memory for increased stack, abort"); exit(EXIT_FAILURE); } this->capacity = new_capacity; this->value_p = new_value_p; } } /* is_empty */ static bool JOIN(T,is_empty)(STACK_T *this) { return (this->last_index == this->first_index-1); } /* size() */ static size_t JOIN(T,size)(STACK_T *this) { //printf("SIZE OF STACK is %li\n", (1+this->last_index - this->first_index)); return (1+ this->last_index - this->first_index); } /* reset_capacity() */ static void JOIN(T, reset_capacity) (STACK_T *this) { if ( (JOIN(T, size)(this) < TEMPLATE_STACK_INTERNALSTACKDEPTH) && (this->capacity > TEMPLATE_STACK_INTERNALSTACKDEPTH) ){ size_t new_capacity = TEMPLATE_STACK_INTERNALSTACKDEPTH; #ifdef STACKDEBUG printf("decreased stack capacity for stacktype %s to %lu\n", STRINGIFY(T), new_capacity ); #endif T *new_value_p = NULL; #ifdef COMPAT_NEED_REALLOCARRAY new_value_p = (T*) realloc( this->value_p, new_capacity * sizeof( T )); #else new_value_p = reallocarray(this->value_p, new_capacity, sizeof(T)); #endif if (NULL == new_value_p) { perror("could not reallocate memory for increased stack, abort"); exit(EXIT_FAILURE); } #ifdef STACKSTAT this->stat.stat_realloc_count++; #endif this->capacity = new_capacity; this->value_p = new_value_p; } } /* delete() */ static void JOIN(T, delete) (STACK_T *this) { if (JOIN(T, is_empty)(this)) { free(this->value_p); this->value_p = NULL; this->capacity = 0; #ifdef STACKSTAT printf("------------------------\n"); printf("DEBUG STACK: %s\n", T_AS_STRING); printf("%s push: %lu\n", T_AS_STRING, this->stat.stat_push_count); printf("%s pushback: %lu\n", T_AS_STRING, this->stat.stat_pushback_count); printf("%s realloc: %lu\n", T_AS_STRING, this->stat.stat_realloc_count); printf("------------------------\n"); #endif } } static void JOIN(T, print_typed_value) (int i, const T v) { PRINT_TYPE(i,v); } /* print_top */ static void JOIN(T, print_top)(STACK_T *this) { printf("################################################\n"); printf("\nstack (firstidx=%lu, lastidx=%lu, capacity=%lu, type=%s):\n", this->first_index, this->last_index, this->capacity, T_AS_STRING); printf("------------------------------------\n"); if (JOIN(T, is_empty)(this)) { printf("empty stack (type=%s)\n", T_AS_STRING); } else { assert(this->last_index >= this->first_index); for (size_t i = this->capacity - 1; i < (this->capacity); --i) { if (i == this->first_index) { printf("first --->"); } else if (i == this->last_index) { printf(" last --->"); } else { printf(" "); } JOIN(T, print_typed_value)(i, this->value_p[i]); } } printf("------------------------------------\n"); printf("################################################\n\n"); } /* push */ static void JOIN(T,push)(STACK_T *this, T v) { if ( (this->capacity == 0) || ((size_t) this->last_index >= this->capacity - 1) ) { JOIN(T, increase_capacity)(this); } #ifdef STACKDEBUG JOIN(T, print_top)(this); printf("(push) this->last_index = %lu (after)\n", this->last_index + 1); #endif #ifdef STACKSTAT this->stat.stat_push_count++; #endif assert(this->capacity > 0); //printf("SSIZUE: %li last:%lu CAP:%lu\n", ( (ssize_t) this->last_index - this->first_index), this->last_index, this->capacity ); assert(( (ssize_t) this->last_index - (ssize_t) this->first_index) >= -1 ); assert(this->capacity > this->last_index); this->value_p[++this->last_index] = v; assert(this->first_index <= this->last_index); } /* pop */ static T JOIN(T,pop)(STACK_T *this) { if (this->last_index < this->first_index) { perror ("Stack underflow!"); exit(EXIT_FAILURE); } #ifdef STACKDEBUG JOIN(T,print_top)(this); printf ("(pop) this->last_index = %li (before)\n", this->last_index); #endif T v = this->value_p[this->last_index--]; #ifdef STACKDEBUG JOIN(T,print_top)(this); printf ("(pop) this->last_index = %li (before)\n", this->last_index); printf("END AFTER pop\n"); #endif if (JOIN(T, is_empty)(this)) { JOIN(T, delete)(this); } else if (this->last_index < TEMPLATE_STACK_INTERNALSTACKDEPTH / 2) { JOIN(T, reset_capacity)(this); assert(this->last_index >= this->first_index); } return v; } /* push_back */ static void JOIN(T,push_back)(STACK_T *this, const T v_init) { //printf("pushback call first_index=%lu lastindex=%lu capacity=%lu\n", this->first_index, this->last_index, this->capacity); //printf("VALUE: %lu\n", v_init); if ((this->first_index > 0) ) { this->first_index--; this->value_p[this->first_index] = v_init; } else { size_t count_of_elements = this->last_index - this->first_index; size_t new_first = count_of_elements / 3 + 1; size_t new_last = new_first + count_of_elements; if (new_last+1 >= this->capacity) { /* there is no space in bikini bottom */ /* increase capacity */ //printf("INCREASE\n"); JOIN(T, increase_capacity)(this); } assert((long signed int) this->capacity > (long signed int) this->last_index); assert((long signed int) this->capacity > (long signed int) new_last); /* copy from first index to last index */ memmove( this->value_p + new_first, this->value_p + this->first_index, ((1+count_of_elements) * sizeof(T)) ); /* memset(this->value_p, 0xfe, (new_first-1)*sizeof(T)); memset(this->value_p + new_last + 1, 0xff , (this->capacity - new_last -1)*sizeof(T)); */ /* memset(this->value_p, 0, (new_first-1)*sizeof(T)); memset(this->value_p + new_last + 1, 0 , (this->capacity - new_last -1)*sizeof(T)); */ this->first_index = new_first-1; this->last_index = new_last; //printf("pushback called first_index=%lu lastindex=%lu capacity=%lu\n", this->first_index, this->last_index, this->capacity); /* copy v_init on top */ this->value_p[this->first_index] = v_init; } assert(this->first_index <= this->last_index); #ifdef STACKSTAT this->stat.stat_pushback_count++; #endif } #undef TEMPLATE_STACK_MAXSTACKDEPTH #undef TEMPLATE_STACK_INTERNALSTACKDEPTH #undef T #undef PRINT_TYPE