X-Git-Url: http://git.asbjorn.biz/?a=blobdiff_plain;f=lib%2Fq.c;h=2f4637394479d6a2d30b9f05dffdc7cdaf032d14;hb=14267197e47b28a7f504c39f916f21d702fdabf5;hp=db9db349272f3c18e66e2749fa03a494c366409b;hpb=aee9de2c6eb23628e54b6896f5b441d9b39317c1;p=swftools.git diff --git a/lib/q.c b/lib/q.c index db9db34..2f46373 100644 --- a/lib/q.c +++ b/lib/q.c @@ -2,7 +2,7 @@ Part of the swftools package. - Copyright (c) 2001 Matthias Kramm + Copyright (c) 2001,2002,2003,2004 Matthias Kramm This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -36,30 +36,6 @@ char* strdup_n(const char*str, int size) return m; } #endif -void* qmalloc_internal(int len) -{ - void*val = malloc(len); - if(!val) { - printf("memory error! Couldn't reserve %d bytes\n", len); - fprintf(stderr, "memory error! Couldn't reserve %d bytes\n", len); - exit(1); - } - return val; -} -void* qrealloc_internal(void*old, int len) -{ - void*val = realloc(old, len); - if(!val) { - printf("memory error! Couldn't reserve %d bytes\n", len); - fprintf(stderr, "memory error! Couldn't reserve %d bytes\n", len); - exit(1); - } - return val; -} -void qfree_internal(void*old) -{ - free(old); -} char*qstrdup(const char*string) { return strdup(string); @@ -77,7 +53,7 @@ void mem_init(mem_t*mem) } void mem_clear(mem_t*mem) { - free(mem->buffer); + free(mem->buffer);mem->buffer = 0; } void mem_destroy(mem_t*mem) { @@ -191,10 +167,27 @@ void ringbuffer_put(ringbuffer_t*r, void*buf, int len) void ringbuffer_clear(ringbuffer_t*r) { ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal; - free(i->buffer); + free(i->buffer);i->buffer = 0; free(i); } +// ------------------------------- crc32 -------------------------------------- +static unsigned int*crc32 = 0; +static void crc32_init(void) +{ + int t; + if(crc32) + return; + crc32= (unsigned int*)malloc(sizeof(unsigned int)*256); + for(t=0; t<256; t++) { + unsigned int c = t; + int s; + for (s = 0; s < 8; s++) { + c = (0xedb88320L*(c&1)) ^ (c >> 1); + } + crc32[t] = c; + } +} // ------------------------------- string_t ----------------------------------- void string_set2(string_t*str, char*text, int len) @@ -207,6 +200,16 @@ void string_set(string_t*str, char*text) str->len = strlen(text); str->str = text; } +unsigned int string_hash(string_t*str) +{ + int t; + unsigned int checksum = 0; + crc32_init(); + for(t=0;tlen;t++) { + checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff]; + } + return checksum; +} void string_dup2(string_t*str, const char*text, int len) { str->len = len; @@ -220,13 +223,13 @@ void string_dup(string_t*str, const char*text) int string_equals(string_t*str, const char*text) { int l = strlen(text); - if(str->len == l && !strncmp(str->str, text, l)) + if(str->len == l && !memcmp(str->str, text, l)) return 1; return 0; } int string_equals2(string_t*str, string_t*str2) { - if(str->len == str2->len && !strncmp(str->str, str2->str, str->len)) + if(str->len == str2->len && !memcmp(str->str, str2->str, str->len)) return 1; return 0; } @@ -237,27 +240,48 @@ char* string_cstr(string_t*str) // ------------------------------- stringarray_t ------------------------------ +#define DEFAULT_HASH_SIZE 257 + +typedef struct _stringlist { + int index; + struct _stringlist*next; +} stringlist_t; + typedef struct _stringarray_internal_t { mem_t data; mem_t pos; + stringlist_t**hash; int num; + int hashsize; } stringarray_internal_t; -void stringarray_init(stringarray_t*sa) + +void stringarray_init(stringarray_t*sa, int hashsize) { stringarray_internal_t*s; + int t; sa->internal = (stringarray_internal_t*)malloc(sizeof(stringarray_internal_t)); memset(sa->internal, 0, sizeof(stringarray_internal_t)); s = (stringarray_internal_t*)sa->internal; mem_init(&s->data); mem_init(&s->pos); + s->hash = malloc(sizeof(stringlist_t*)*hashsize); + memset(s->hash, 0, sizeof(stringlist_t*)*hashsize); + s->hashsize = hashsize; } void stringarray_put(stringarray_t*sa, string_t str) { stringarray_internal_t*s = (stringarray_internal_t*)sa->internal; int pos; + int hash = string_hash(&str) % s->hashsize; pos = mem_putstring(&s->data, str); mem_put(&s->pos, &pos, sizeof(int)); + + stringlist_t*l = malloc(sizeof(stringlist_t)); + l->index = s->num; + l->next = s->hash[hash]; + s->hash[hash] = l; + s->num++; } char* stringarray_at(stringarray_t*sa, int pos) @@ -278,20 +302,47 @@ string_t stringarray_at2(stringarray_t*sa, int pos) s.len = s.str?strlen(s.str):0; return s; } +static stringlist_t* stringlist_del(stringarray_t*sa, stringlist_t*l, int index) +{ + stringlist_t*ll = l; + stringlist_t*old = l; + while(l) { + if(index==l->index) { + old->next = l->next; + memset(l, 0, sizeof(stringlist_t)); + free(l); + if(old==l) + return 0; + else + return ll; + } + old = l; + l = l->next; + } + fprintf(stderr, "Internal error: did not find string %d in hash\n", index); + return ll; +} + void stringarray_del(stringarray_t*sa, int pos) { stringarray_internal_t*s = (stringarray_internal_t*)sa->internal; + string_t str = stringarray_at2(sa, pos); + int hash = string_hash(&str) % s->hashsize; + s->hash[hash] = stringlist_del(sa, s->hash[hash], pos); *(int*)&s->pos.buffer[pos*sizeof(int)] = -1; } int stringarray_find(stringarray_t*sa, string_t* str) { stringarray_internal_t*s = (stringarray_internal_t*)sa->internal; + int hash = string_hash(str) % s->hashsize; int t; - for(t=0;tnum;t++) { - string_t s = stringarray_at2(sa, t); - if(s.str && string_equals2(&s, str)) { - return t; - } + stringlist_t*l = s->hash[hash]; + while(l) { + string_t s = stringarray_at2(sa, l->index); + if(string_equals2(str, &s)) { + return l->index; + } + l = l->next; } return -1; } @@ -300,6 +351,16 @@ void stringarray_clear(stringarray_t*sa) stringarray_internal_t*s = (stringarray_internal_t*)sa->internal; mem_clear(&s->data); mem_clear(&s->pos); + int t; + for(t=0;thashsize;t++) { + stringlist_t*l = s->hash[t]; + while(l) { + stringlist_t*next = l->next; + memset(l, 0, sizeof(stringlist_t)); + free(l); + l = next; + } + } free(s); } void stringarray_destroy(stringarray_t*sa) @@ -324,8 +385,8 @@ void map_init(map_t*map) map->internal = (map_internal_t*)malloc(sizeof(map_internal_t)); memset(map->internal, 0, sizeof(map_internal_t)); m = (map_internal_t*)map->internal; - stringarray_init(&m->keys); - stringarray_init(&m->values); + stringarray_init(&m->keys, DEFAULT_HASH_SIZE); + stringarray_init(&m->values, DEFAULT_HASH_SIZE); } void map_put(map_t*map, string_t t1, string_t t2) { @@ -385,7 +446,7 @@ void dictionary_init(dictionary_t*dict) dict->internal = (dictionary_internal_t*)malloc(sizeof(dictionary_internal_t)); memset(dict->internal, 0, sizeof(dictionary_internal_t)); d = (dictionary_internal_t*)dict->internal; - stringarray_init(&d->keys); + stringarray_init(&d->keys, DEFAULT_HASH_SIZE); mem_init(&d->values); } void dictionary_put(dictionary_t*dict, string_t t1, void* t2) @@ -408,6 +469,16 @@ void dictionary_put2(dictionary_t*dict, const char*t1, void* t2) string_set(&s, (char*)t1); dictionary_put(dict, s, t2); } +stringarray_t* dictionary_index(dictionary_t*dict) +{ + dictionary_internal_t*d = (dictionary_internal_t*)dict->internal; + return &d->keys; +} +int dictionary_count(dictionary_t* dict) // this count includes entries that have been deleted +{ + dictionary_internal_t*d = (dictionary_internal_t*)dict->internal; + return d->num; +} void* dictionary_lookup(dictionary_t*dict, const char*name) { int s; @@ -453,3 +524,117 @@ void dictionary_destroy(dictionary_t*dict) dictionary_clear(dict); free(dict); } + +void dictionary_free_all(dictionary_t* dict, void (*freeFunction)(void*)) +{ + dictionary_internal_t*d = (dictionary_internal_t*)dict->internal; + int num = 0; + char* name = stringarray_at(&d->keys, num) ; + while (name) + { + freeFunction(dictionary_lookup(dict, name)); + num++; + name = stringarray_at(&d->keys, num); + } + dictionary_clear(dict); +} + +// ------------------------------- heap_t ------------------------------- + +void heap_init(heap_t*h,int n,int elem_size, int(*compare)(const void *, const void *)) +{ + memset(h, 0, sizeof(heap_t)); + h->max_size = n; + h->size = 0; + h->elem_size = elem_size; + h->compare = compare; + h->elements = (void**)malloc(n*sizeof(void*));memset(h->elements, 0, n*sizeof(void*)); + h->data = (char*)malloc(h->max_size*h->elem_size);memset(h->data, 0, h->max_size*h->elem_size); +} +void heap_clear(heap_t*h) +{ + free(h->elements); + free(h->data); +} + +#define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))>0) + +static void up(heap_t*h, int node) +{ + void*node_p = h->elements[node]; + int parent = node; + do { + node = parent; + if(!node) break; + parent = (node-1)/2; + h->elements[node] = h->elements[parent]; + } while(HEAP_NODE_SMALLER(h,h->elements[parent], node_p)); + + h->elements[node] = node_p; +} +static void down(heap_t*h, int node) +{ + void*node_p = h->elements[node]; + int child = node; + do { + node = child; + + /* determine new child's position */ + child = node<<1|1; + if(child >= h->size) + break; + if(child+1 < h->size && HEAP_NODE_SMALLER(h,h->elements[child],h->elements[child+1])) // search for bigger child + child++; + + h->elements[node] = h->elements[child]; + } while(HEAP_NODE_SMALLER(h,node_p, h->elements[child])); + + h->elements[node] = node_p; +} +void heap_put(heap_t*h, void*e) +{ + int pos = h->size++; + memcpy(&h->data[pos*h->elem_size],e,h->elem_size); + h->elements[pos] = &h->data[pos]; + up(h, pos); +} +int heap_size(heap_t*h) +{ + return h->size; +} +void* heap_max(heap_t*h) +{ + return h->elements[0]; +} +void* heap_chopmax(heap_t*h) +{ + void*p = h->elements[0]; + h->elements[0] = h->elements[--h->size]; + down(h,0); + return p; +} +void heap_dump(heap_t*h, FILE*fi) +{ + int t; + for(t=0;tsize;t++) { + int s; + for(s=0;s<=t;s=(s+1)*2-1) { + if(s==t) fprintf(fi,"\n"); + } + //fprintf(fi,"%d ", h->elements[t]->x); //? + } +} +void** heap_flatten(heap_t*h) +{ + void**nodes = (void**)malloc(h->size*sizeof(void*)); + void**p = nodes; + + while(h->size) { + /*printf("Heap Size: %d\n", h->size); + heap_print(stdout, h); + printf("\n");*/ + *p++ = heap_chopmax(h); + } + return nodes; +} +