X-Git-Url: http://git.asbjorn.it/?a=blobdiff_plain;f=lib%2Fq.c;h=2f4637394479d6a2d30b9f05dffdc7cdaf032d14;hb=14267197e47b28a7f504c39f916f21d702fdabf5;hp=400c92d933e42ae0da08a5044ece1252ea8aa0a7;hpb=9788caae660683c6c8f98f53b3fc1a4274b73e47;p=swftools.git diff --git a/lib/q.c b/lib/q.c index 400c92d..2f46373 100644 --- a/lib/q.c +++ b/lib/q.c @@ -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); @@ -195,6 +171,23 @@ void ringbuffer_clear(ringbuffer_t*r) 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; @@ -454,6 +525,20 @@ void dictionary_destroy(dictionary_t*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 *))