3 Part of the swftools package.
5 Copyright (c) 2001,2002,2003,2004 Matthias Kramm <kramm@quiss.org>
7 This program is rfx_free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the rfx_free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the rfx_free Software
19 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
32 // ------------------------------- malloc, alloc routines ---------------------
35 char* strdup_n(const char*str, int size)
37 char*m = (char*)rfx_alloc(size+1);
43 char*qstrdup(const char*string)
45 return strdup(string);
47 char*qstrndup(const char*string, int len)
49 return strdup_n(string, len);
51 char* allocprintf(const char*format, ...)
54 va_start(arglist1, format);
56 int l = vsnprintf(&dummy, 1, format, arglist1);
60 va_start(arglist2, format);
61 char*buf = malloc(l+1);
62 vsnprintf(buf, l+1, format, arglist2);
67 // ------------------------------- mem_t --------------------------------------
69 void mem_init(mem_t*mem)
71 memset(mem, 0, sizeof(mem_t));
73 void mem_clear(mem_t*mem)
75 rfx_free(mem->buffer);mem->buffer = 0;
77 void mem_destroy(mem_t*mem)
82 static int mem_put_(mem_t*m,const void*data, int length, int null)
85 m->pos += length + (null?1:0);
87 int v1 = (m->pos+63)&~63;
88 int v2 = m->len + m->len / 2;
90 m->buffer = m->buffer?(char*)rfx_realloc(m->buffer,m->len):(char*)rfx_alloc(m->len);
92 assert(n+length <= m->len);
93 memcpy(&m->buffer[n], data, length);
95 m->buffer[n + length] = 0;
98 int mem_put(mem_t*m,void*data, int length)
100 return mem_put_(m, data, length, 0);
102 int mem_putstring(mem_t*m,string_t str)
104 return mem_put_(m, str.str, str.len, 1);
106 int mem_get(mem_t*m, void*data, int length)
108 if(m->read_pos + length > m->pos) {
109 length = m->pos - m->read_pos;
111 memcpy(data, m->buffer+m->read_pos, length);
112 m->read_pos += length;
116 // ------------------------------- ringbuffer_t -------------------------------
118 typedef struct _ringbuffer_internal_t
120 unsigned char*buffer;
124 } ringbuffer_internal_t;
126 void ringbuffer_init(ringbuffer_t*r)
128 ringbuffer_internal_t*i = (ringbuffer_internal_t*)rfx_calloc(sizeof(ringbuffer_internal_t));
129 memset(r, 0, sizeof(ringbuffer_t));
131 i->buffer = (unsigned char*)rfx_alloc(1024);
132 i->buffersize = 1024;
134 int ringbuffer_read(ringbuffer_t*r, void*buf, int len)
136 unsigned char* data = (unsigned char*)buf;
137 ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
138 if(r->available < len)
142 if(i->readpos + len > i->buffersize) {
143 int read1 = i->buffersize-i->readpos;
144 memcpy(data, &i->buffer[i->readpos], read1);
145 memcpy(&data[read1], &i->buffer[0], len - read1);
146 i->readpos = len - read1;
148 memcpy(data, &i->buffer[i->readpos], len);
150 i->readpos %= i->buffersize;
155 void ringbuffer_put(ringbuffer_t*r, void*buf, int len)
157 unsigned char* data = (unsigned char*)buf;
158 ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
160 if(i->buffersize - r->available < len)
163 int newbuffersize = i->buffersize;
164 int oldavailable = r->available;
165 newbuffersize*=3;newbuffersize/=2; /*grow at least by 50% each time */
167 if(newbuffersize < r->available + len)
168 newbuffersize = r->available + len + 1024;
170 buf2 = (unsigned char*)rfx_alloc(newbuffersize);
171 ringbuffer_read(r, buf2, r->available);
174 i->buffersize = newbuffersize;
176 i->writepos = oldavailable;
177 r->available = oldavailable;
179 if(i->writepos + len > i->buffersize) {
180 int read1 = i->buffersize-i->writepos;
181 memcpy(&i->buffer[i->writepos], data, read1);
182 memcpy(&i->buffer[0], &data[read1], len - read1);
183 i->writepos = len - read1;
185 memcpy(&i->buffer[i->writepos], data, len);
187 i->writepos %= i->buffersize;
191 void ringbuffer_clear(ringbuffer_t*r)
193 ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
194 rfx_free(i->buffer);i->buffer = 0;
198 // ------------------------------- heap_t -------------------------------
200 void heap_init(heap_t*h,int elem_size, int(*compare)(const void *, const void *))
202 memset(h, 0, sizeof(heap_t));
204 h->elem_size = elem_size;
205 h->compare = compare;
209 heap_t* heap_new(int elem_size, int(*compare)(const void *, const void *))
211 heap_t*h = malloc(sizeof(heap_t));
212 heap_init(h, elem_size, compare);
215 heap_t* heap_clone(heap_t*o)
217 heap_t*h = malloc(sizeof(heap_t));
218 memcpy(h, o, sizeof(heap_t));
219 h->elements = rfx_alloc(sizeof(void*)*h->size);
221 for(t=0;t<h->size;t++) {
222 h->elements[t] = rfx_alloc(h->elem_size);
223 memcpy(h->elements[t], o->elements[t], h->elem_size);
227 void heap_clear(heap_t*h)
230 for(t=0;t<h->size;t++) {
231 rfx_free(h->elements[t]);
234 rfx_free(h->elements);
236 void heap_destroy(heap_t*h)
242 #define HEAP_NODE_LARGER(h,node1,node2) ((h)->compare((node1),(node2))>0)
243 #define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))<0)
245 static void up(heap_t*h, int node)
247 void*node_p = h->elements[node];
254 h->elements[node] = h->elements[parent];
255 } while(HEAP_NODE_SMALLER(h, h->elements[parent], node_p));
256 h->elements[node] = node_p;
258 static void down(heap_t*h, int node)
260 void*node_p = h->elements[node];
265 /* determine new child's position */
269 if(child+1 < h->size && HEAP_NODE_SMALLER(h,h->elements[child],h->elements[child+1])) // search for bigger child
272 h->elements[node] = h->elements[child];
273 } while(HEAP_NODE_SMALLER(h,node_p, h->elements[child]));
275 h->elements[node] = node_p;
277 void heap_put(heap_t*h, void*e)
280 void*data = rfx_alloc(h->elem_size);
281 memcpy(data,e,h->elem_size);
283 if(pos>=h->max_size) {
284 h->max_size = h->max_size<15?15:(h->max_size+1)*2-1;
285 h->elements = (void**)rfx_realloc(h->elements, h->max_size*sizeof(void*));
286 assert(pos<h->max_size);
289 h->elements[pos] = data;
292 int heap_size(heap_t*h)
296 void* heap_peek(heap_t*h)
300 return h->elements[0];
302 void* heap_chopmax(heap_t*h)
306 void*p = h->elements[0];
307 h->elements[0] = h->elements[--h->size];
311 void heap_dump(heap_t*h, FILE*fi)
314 for(t=0;t<h->size;t++) {
316 for(s=0;s<=t;s=(s+1)*2-1) {
317 if(s==t) fprintf(fi,"\n");
319 //fprintf(fi,"%d ", h->elements[t]->x); //?
322 void** heap_flatten(heap_t*h)
324 void**nodes = (void**)rfx_alloc((h->size+1)*sizeof(void*));
328 /*printf("Heap Size: %d\n", h->size);
329 heap_print(stdout, h);
331 *p++ = heap_chopmax(h);
337 // ------------------------------- trie --------------------------------------
341 return (trie_t*)rfx_calloc(sizeof(trie_t));
343 static char _trie_put(trielayer_t**t, unsigned const char*id, void*data)
346 (*t) = rfx_calloc(sizeof(trielayer_t));
347 (*t)->rest = (unsigned char*)strdup(id);
351 if((*t)->rest && (*t)->rest[0]) {
352 // make room: shift whatever's currently in here one node down
353 _trie_put(&(*t)->row[(*t)->rest[0]], (*t)->rest+1, (*t)->data);
357 return _trie_put(&(*t)->row[id[0]], id+1, data);
362 (*t)->rest = strdup("");
367 static char _trie_remove(trielayer_t*t, unsigned const char*id)
370 if(t->rest && !strcmp(t->rest, id)) {
382 static void trie_rollback_removes(trie_t*t, unsigned const char*id, void*data);
383 static void trie_rollback_adds(trie_t*t, unsigned const char*id, void*data);
385 void trie_put(trie_t*t, unsigned const char*id, void*data)
388 _trie_put(&t->start, id, data);
390 char contains = trie_contains(t, id);
391 void*olddata = contains?trie_lookup(t, id):0;
392 _trie_put(&t->start, id, data);
394 trie_rollback_adds(t, id, olddata);
396 trie_rollback_removes(t, id, data);
399 char trie_remove(trie_t*t, unsigned const char*id)
402 return _trie_remove(t->start, id);
404 void*olddata = trie_lookup(t, id);
405 char exists = _trie_remove(t->start, id);
407 trie_rollback_adds(t, id, olddata);
412 int trie_contains(trie_t*trie, unsigned const char*id)
414 trielayer_t*t = trie->start;
416 if(t->rest && !strcmp(t->rest, id))
424 void* trie_lookup(trie_t*trie, unsigned const char*id)
426 trielayer_t*t = trie->start;
428 if(t->rest && !strcmp(t->rest, id))
437 typedef struct _triememory {
438 const unsigned char*key;
441 struct _triememory*next;
444 typedef struct _trierollback {
446 struct _trierollback*prev;
449 static void trie_rollback_adds(trie_t*t, unsigned const char*id, void*data)
451 trierollback_t*rollback = (trierollback_t*)t->rollback;
452 triememory_t*m = (triememory_t*)rfx_calloc(sizeof(triememory_t));
456 m->next = rollback->ops;
459 static void trie_rollback_removes(trie_t*t, unsigned const char*id, void*data)
461 trierollback_t*rollback = (trierollback_t*)t->rollback;
462 triememory_t*m = (triememory_t*)rfx_calloc(sizeof(triememory_t));
466 m->next = rollback->ops;
470 void _trie_dump(trielayer_t*t, char*buffer, int pos)
476 _trie_dump(t->row[i], buffer, pos+1);
481 printf("%s%s %08x\n", buffer, t->rest, t->data);
485 void trie_dump(trie_t*t)
488 _trie_dump(t->start, buffer, 0);
492 void trie_remember(trie_t*t)
494 trierollback_t*old = (trierollback_t*)t->rollback;
495 t->rollback = (trierollback_t*)rfx_calloc(sizeof(trierollback_t));
496 ((trierollback_t*)t->rollback)->prev = old;
499 void trie_rollback(trie_t*t)
501 trierollback_t*rollback = (trierollback_t*)t->rollback;
503 fprintf(stderr, "Internal error: can't roll back this trie any further\n");
506 t->rollback = ((trierollback_t*)t->rollback)->prev;
508 triememory_t*op = rollback->ops;
510 triememory_t*next = op->next;
512 if(!_trie_remove(t->start, op->key)) {
513 fprintf(stderr, "Internal error: can't delete key %s in trie during rollback\n", op->key);
516 if(_trie_put(&t->start, op->key, op->data)) {
517 fprintf(stderr, "Internal error: overwrote key %s in trie during rollback\n", op->key);
526 // ------------------------------- crc32 --------------------------------------
527 static unsigned int crc32[256];
528 static char crc32_initialized=0;
529 static void crc32_init(void)
532 if(crc32_initialized)
534 crc32_initialized = 1;
535 for(t=0; t<256; t++) {
538 for (s = 0; s < 8; s++) {
539 c = (0xedb88320L*(c&1)) ^ (c >> 1);
544 // ------------------------------- string_t -----------------------------------
546 void string_set2(string_t*str, const char*text, int len)
551 void string_set(string_t*str, const char*text)
554 str->len = strlen(text);
560 string_t string_new(const char*text, int len)
567 string_t string_new2(const char*text)
571 s.len = strlen(text);
578 string_t* string_new3(const char*text, int len)
581 string_t*s = malloc(sizeof(string_t));
586 string_t*s = malloc(sizeof(string_t)+len+1);
588 s->str = (const char*)(s+1);
589 memcpy((char*)s->str, text, len);
590 ((char*)s->str)[len]=0;
594 string_t* string_new4(const char*text)
596 int l = strlen(text);
597 return string_new3(text, l);
600 void string_free(string_t*s)
605 if((string_t*)(s->str) == s+1) {
609 rfx_free((char*)(s->str));
614 char* string_cstr(string_t*str)
616 return strdup_n(str->str, str->len);
618 char* string_escape(string_t*str)
622 for(t=0;t<str->len;t++) {
628 char*s = malloc(len+1);
630 for(t=0;t<str->len;t++) {
631 if(str->str[t]<0x20) {
633 unsigned char c = str->str[t];
634 *p++ = "0123456789abcdef"[c>>4];
635 *p++ = "0123456789abcdef"[c&0x0f];
641 assert(p == &s[len+1]);
645 unsigned int crc32_add_byte(unsigned int checksum, unsigned char b)
649 return checksum>>8 ^ crc32[(b^checksum)&0xff];
651 unsigned int crc32_add_string(unsigned int checksum, const char*s)
658 checksum = checksum>>8 ^ crc32[(*s^checksum)&0xff];
664 unsigned int string_hash(const string_t*str)
667 unsigned int checksum = 0;
670 for(t=0;t<str->len;t++) {
671 checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff];
675 unsigned int string_hash2(const char*str)
677 unsigned int checksum = 0;
682 checksum = checksum>>8 ^ crc32[(*p^checksum)&0xff];
687 unsigned int string_hash3(const char*str, int len)
692 return string_hash(&s);
694 void string_dup2(string_t*str, const char*text, int len)
697 str->str = strdup_n(text, len);
699 void string_dup(string_t*str, const char*text)
701 str->len = strlen(text);
702 str->str = strdup(text);
704 int string_equals(string_t*str, const char*text)
706 int l = strlen(text);
707 if(str->len == l && !memcmp(str->str, text, l))
711 int string_equals2(string_t*str, string_t*str2)
713 if(str->len == str2->len && !memcmp(str->str, str2->str, str->len))
718 // ------------------------------- stringarray_t ------------------------------
720 typedef struct _stringlist {
722 struct _stringlist*next;
725 typedef struct _stringarray_internal_t
731 } stringarray_internal_t;
733 void stringarray_init(stringarray_t*sa, int hashsize)
735 stringarray_internal_t*s;
737 sa->internal = (stringarray_internal_t*)rfx_calloc(sizeof(stringarray_internal_t));
738 s = (stringarray_internal_t*)sa->internal;
740 s->hash = rfx_calloc(sizeof(stringlist_t*)*hashsize);
741 s->hashsize = hashsize;
743 void stringarray_put(stringarray_t*sa, string_t str)
745 stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
747 int hash = string_hash(&str) % s->hashsize;
749 char*ss = string_cstr(&str);
750 mem_put(&s->pos, &ss, sizeof(char*));
752 stringlist_t*l = rfx_alloc(sizeof(stringlist_t));
754 l->next = s->hash[hash];
759 char* stringarray_at(stringarray_t*sa, int pos)
761 stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
763 if(pos<0 || pos>=s->num)
765 p = *(char**)&s->pos.buffer[pos*sizeof(char*)];
770 string_t stringarray_at2(stringarray_t*sa, int pos)
773 s.str = stringarray_at(sa, pos);
774 s.len = s.str?strlen(s.str):0;
777 static stringlist_t* stringlist_del(stringarray_t*sa, stringlist_t*l, int index)
780 stringlist_t*old = l;
782 if(index==l->index) {
784 memset(l, 0, sizeof(stringlist_t));
794 fprintf(stderr, "Internal error: did not find string %d in hash\n", index);
798 void stringarray_del(stringarray_t*sa, int pos)
800 stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
801 string_t str = stringarray_at2(sa, pos);
802 int hash = string_hash(&str) % s->hashsize;
803 s->hash[hash] = stringlist_del(sa, s->hash[hash], pos);
804 *(char**)&s->pos.buffer[pos*sizeof(char*)] = 0;
806 int stringarray_find(stringarray_t*sa, string_t* str)
808 stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
809 int hash = string_hash(str) % s->hashsize;
811 stringlist_t*l = s->hash[hash];
814 string_t s = stringarray_at2(sa, l->index);
815 if(string_equals2(str, &s)) {
822 void stringarray_clear(stringarray_t*sa)
824 stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
827 for(t=0;t<s->hashsize;t++) {
828 stringlist_t*l = s->hash[t];
830 stringlist_t*next = l->next;
831 memset(l, 0, sizeof(stringlist_t));
836 rfx_free(s->hash);s->hash=0;
839 void stringarray_destroy(stringarray_t*sa)
841 stringarray_clear(sa);
845 // ------------------------------- type_t -------------------------------
847 char ptr_equals(const void*o1, const void*o2)
851 unsigned int ptr_hash(const void*o)
853 return string_hash3((const char*)&o, sizeof(o));
855 void* ptr_dup(const void*o)
859 void ptr_free(void*o)
864 char charptr_equals(const void*o1, const void*o2)
868 return !strcmp(o1,o2);
870 unsigned int charptr_hash(const void*o)
874 return string_hash2(o);
876 void* charptr_dup(const void*o)
882 void charptr_free(void*o)
889 char stringstruct_equals(const void*o1, const void*o2)
893 string_t*s1 = (string_t*)o1;
894 string_t*s2 = (string_t*)o2;
895 int l = s1->len<s2->len?s1->len:s2->len;
896 int r = memcmp(s1->str, s2->str, l);
900 return s1->len==s2->len;
902 unsigned int stringstruct_hash(const void*o)
905 return string_hash(o);
907 string_t*string_dup3(string_t*o)
911 string_t*s = malloc(sizeof(string_t));
916 string_t*s = rfx_alloc(sizeof(string_t)+o->len+1);
918 s->str = (const char*)(s+1);
919 memcpy((char*)s->str, o->str, s->len);
920 ((char*)s->str)[s->len]=0;
923 void stringstruct_free(void*o)
936 type_t charptr_type = {
937 equals: charptr_equals,
943 type_t stringstruct_type = {
944 equals: stringstruct_equals,
945 hash: stringstruct_hash,
946 dup: (dup_func)string_dup3,
947 free: stringstruct_free,
950 // ------------------------------- dictionary_t -------------------------------
952 #define INITIAL_SIZE 1
954 static int max(int x, int y) {
960 dict_t*d = rfx_alloc(sizeof(dict_t));
961 dict_init(d, INITIAL_SIZE);
964 dict_t*dict_new2(type_t*t)
966 dict_t*d = rfx_alloc(sizeof(dict_t));
967 dict_init(d, INITIAL_SIZE);
971 void dict_init(dict_t*h, int size)
973 memset(h, 0, sizeof(dict_t));
975 h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
977 h->key_type = &charptr_type;
979 void dict_init2(dict_t*h, type_t*t, int size)
981 memset(h, 0, sizeof(dict_t));
983 h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
988 dict_t*dict_clone(dict_t*o)
990 dict_t*h = rfx_alloc(sizeof(dict_t));
991 memcpy(h, o, sizeof(dict_t));
992 h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
994 for(t=0;t<o->hashsize;t++) {
995 dictentry_t*e = o->slots[t];
997 dictentry_t*n = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
998 memcpy(n, e, sizeof(dictentry_t));
999 n->key = h->key_type->dup(e->key);
1001 n->next = h->slots[t];
1009 static void dict_expand(dict_t*h, int newlen)
1011 assert(h->hashsize < newlen);
1012 dictentry_t**newslots = (dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*newlen);
1014 for(t=0;t<h->hashsize;t++) {
1015 dictentry_t*e = h->slots[t];
1017 dictentry_t*next = e->next;
1018 unsigned int newhash = e->hash%newlen;
1019 e->next = newslots[newhash];
1020 newslots[newhash] = e;
1026 h->slots = newslots;
1027 h->hashsize = newlen;
1030 dictentry_t* dict_put(dict_t*h, const void*key, void* data)
1032 unsigned int hash = h->key_type->hash(key);
1033 dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
1038 unsigned int hash2 = hash % h->hashsize;
1040 e->key = h->key_type->dup(key);
1041 e->hash = hash; //for resizing
1042 e->next = h->slots[hash2];
1044 h->slots[hash2] = e;
1048 void dict_put2(dict_t*h, const char*s, void*data)
1050 assert(h->key_type == &charptr_type);
1051 dict_put(h, s, data);
1053 void dict_dump(dict_t*h, FILE*fi, const char*prefix)
1056 for(t=0;t<h->hashsize;t++) {
1057 dictentry_t*e = h->slots[t];
1059 if(h->key_type!=&charptr_type) {
1060 fprintf(fi, "%s%08x=%08x\n", prefix, e->key, e->data);
1062 fprintf(fi, "%s%s=%08x\n", prefix, e->key, e->data);
1069 int dict_count(dict_t*h)
1074 static inline dictentry_t* dict_do_lookup(dict_t*h, const void*key)
1080 unsigned int ohash = h->key_type->hash(key);
1081 unsigned int hash = ohash % h->hashsize;
1083 /* check first entry for match */
1084 dictentry_t*e = h->slots[hash];
1085 if(e && h->key_type->equals(e->key, key)) {
1091 /* if dict is 2/3 filled, double the size. Do
1092 this the first time we have to actually iterate
1093 through a slot to find our data */
1094 if(e && h->num*3 >= h->hashsize*2) {
1095 int newsize = h->hashsize;
1096 while(h->num*3 >= newsize*2) {
1097 newsize = newsize<15?15:(newsize+1)*2-1;
1099 dict_expand(h, newsize);
1100 hash = ohash % h->hashsize;
1102 if(e && h->key_type->equals(e->key, key)) {
1103 // omit move to front
1110 /* check subsequent entries for a match */
1111 dictentry_t*last = h->slots[hash];
1113 if(h->key_type->equals(e->key, key)) {
1114 /* move to front- makes a difference of about 10% in most applications */
1115 last->next = e->next;
1116 e->next = h->slots[hash];
1125 void* dict_lookup(dict_t*h, const void*key)
1127 dictentry_t*e = dict_do_lookup(h, key);
1132 char dict_contains(dict_t*h, const void*key)
1134 dictentry_t*e = dict_do_lookup(h, key);
1138 char dict_del(dict_t*h, const void*key)
1142 unsigned int hash = h->key_type->hash(key) % h->hashsize;
1143 dictentry_t*head = h->slots[hash];
1144 dictentry_t*e = head, *prev=0;
1146 if(h->key_type->equals(e->key, key)) {
1147 dictentry_t*next = e->next;
1148 h->key_type->free(e->key);
1149 memset(e, 0, sizeof(dictentry_t));
1152 h->slots[hash] = next;
1166 dictentry_t* dict_get_slot(dict_t*h, const void*key)
1170 unsigned int ohash = h->key_type->hash(key);
1171 unsigned int hash = ohash % h->hashsize;
1172 return h->slots[hash];
1175 void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const void*key, void*val), void*data)
1178 for(t=0;t<h->hashsize;t++) {
1179 dictentry_t*e = h->slots[t];
1181 dictentry_t*next = e->next;
1183 runFunction(data, e->key, e->data);
1189 void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
1192 for(t=0;t<h->hashsize;t++) {
1193 dictentry_t*e = h->slots[t];
1195 dictentry_t*next = e->next;
1197 runFunction(e->data);
1204 void dict_free_all(dict_t*h, char free_keys, void (*free_data_function)(void*))
1207 for(t=0;t<h->hashsize;t++) {
1208 dictentry_t*e = h->slots[t];
1210 dictentry_t*next = e->next;
1212 h->key_type->free(e->key);
1214 if(free_data_function) {
1215 free_data_function(e->data);
1217 memset(e, 0, sizeof(dictentry_t));
1224 memset(h, 0, sizeof(dict_t));
1227 void dict_clear_shallow(dict_t*h)
1229 dict_free_all(h, 0, 0);
1232 void dict_clear(dict_t*h)
1234 dict_free_all(h, 1, 0);
1237 void dict_destroy_shallow(dict_t*dict)
1239 dict_clear_shallow(dict);
1243 void dict_destroy(dict_t*dict)
1251 // ------------------------------- map_t --------------------------------------
1253 typedef struct _map_internal_t
1258 void map_init(map_t*map)
1261 map->internal = (map_internal_t*)rfx_calloc(sizeof(map_internal_t));
1262 m = (map_internal_t*)map->internal;
1263 dict_init(&m->d, INITIAL_SIZE);
1265 void map_put(map_t*map, string_t t1, string_t t2)
1267 map_internal_t*m = (map_internal_t*)map->internal;
1269 char* s1 = string_cstr(&t1);
1270 dict_put2(&m->d, s1, (void*)string_cstr(&t2));
1273 const char* map_lookup(map_t*map, const char*name)
1275 map_internal_t*m = (map_internal_t*)map->internal;
1276 const char*value = dict_lookup(&m->d, name);
1279 static void freestring(void*data)
1283 static void dumpmapentry(void*data, const void*key, void*value)
1285 FILE*fi = (FILE*)data;
1286 fprintf(fi, "%s=%s\n", key, (char*)value);
1288 void map_dump(map_t*map, FILE*fi, const char*prefix)
1291 map_internal_t*m = (map_internal_t*)map->internal;
1292 dict_foreach_keyvalue(&m->d, dumpmapentry, fi);
1294 void map_clear(map_t*map)
1296 map_internal_t*m = (map_internal_t*)map->internal;
1297 dict_free_all(&m->d, 1, freestring);
1300 void map_destroy(map_t*map)
1306 // ------------------------------- array_t --------------------------------------
1308 array_t* array_new() {
1309 array_t*d = malloc(sizeof(array_t));
1310 memset(d, 0, sizeof(array_t));
1311 d->entry2pos = dict_new();
1314 array_t* array_new2(type_t*type) {
1315 array_t*d = malloc(sizeof(array_t));
1316 memset(d, 0, sizeof(array_t));
1317 d->entry2pos = dict_new2(type);
1320 void*array_getkey(array_t*array, int nr) {
1321 if(nr > array->num || nr<0) {
1322 printf("error: reference to element %d in array[%d]\n", nr, array->num);
1325 return array->d[nr].name;
1327 void*array_getvalue(array_t*array, int nr) {
1328 if(nr > array->num || nr<0) {
1329 printf("error: reference to element %d in array[%d]\n", nr, array->num);
1332 return array->d[nr].data;
1334 int array_append(array_t*array, const void*name, void*data) {
1335 while(array->size <= array->num) {
1338 array->d = malloc(sizeof(array_entry_t)*array->size);
1340 array->d = realloc(array->d, sizeof(array_entry_t)*array->size);
1344 dictentry_t*e = dict_put(array->entry2pos, name, (void*)(ptroff_t)(array->num+1));
1347 array->d[array->num].name = e->key;
1349 array->d[array->num].name = 0;
1351 array->d[array->num].data = (void*)data;
1352 return array->num++;
1354 int array_find(array_t*array, const void*name)
1356 int pos = (int)(ptroff_t)dict_lookup(array->entry2pos, name);
1359 int array_find2(array_t*array, const void*name, void*data)
1361 dict_t*h= array->entry2pos;
1362 dictentry_t*e = dict_get_slot(array->entry2pos, name);
1365 int index = ((int)(ptroff_t)e->data) - 1;
1366 if(h->key_type->equals(e->key, name) && array->d[index].data == data) {
1373 int array_update(array_t*array, const void*name, void*data) {
1374 int pos = array_find(array, name);
1376 array->d[pos].data = data;
1379 return array_append(array, name, data);
1381 int array_append_if_new(array_t*array, const void*name, void*data) {
1382 int pos = array_find(array, name);
1385 return array_append(array, name, data);
1387 void array_free(array_t*array) {
1388 dict_destroy(array->entry2pos);
1390 free(array->d);array->d = 0;
1395 // ------------------------------- list_t --------------------------------------
1398 typedef struct _listinfo {
1400 struct _commonlist*last;
1403 typedef struct _commonlist {
1405 struct _commonlist*next;
1409 int list_length_(void*_list)
1411 commonlist_t*l = (commonlist_t*)_list;
1414 return l->info[0].size;
1416 void list_concat_(void*_l1, void*_l2)
1418 commonlist_t**l1 = (commonlist_t**)_l1;
1419 commonlist_t**l2 = (commonlist_t**)_l2;
1424 (*l1)->info[0].last->next = *l2;
1425 (*l1)->info[0].last = (*l2)->info[0].last;
1426 (*l1)->info[0].size += (*l2)->info[0].size;
1430 void list_append_(void*_list, void*entry)
1432 commonlist_t**list = (commonlist_t**)_list;
1433 commonlist_t* n = 0;
1435 n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1437 (*list)->info[0].size = 0;
1439 n = malloc(sizeof(commonlist_t));
1440 (*list)->info[0].last->next = n;
1444 (*list)->info[0].last = n;
1445 (*list)->info[0].size++;
1447 /* notice: prepending uses slighly more space than appending */
1448 void list_prepend_(void*_list, void*entry)
1450 commonlist_t**list = (commonlist_t**)_list;
1451 commonlist_t* n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1453 commonlist_t* last = 0;
1455 last = (*list)->info[0].last;
1456 size = (*list)->info[0].size;
1461 (*list)->info[0].last = last;
1462 (*list)->info[0].size = size+1;
1464 void list_free_(void*_list)
1466 commonlist_t**list = (commonlist_t**)_list;
1467 commonlist_t*l = *list;
1469 commonlist_t*next = l->next;
1475 void list_deep_free_(void*_list)
1477 commonlist_t**list = (commonlist_t**)_list;
1478 commonlist_t*l = *list;
1480 commonlist_t*next = l->next;
1482 free(l->entry);l->entry=0;
1489 void*list_clone_(void*_list)
1491 commonlist_t*l = *(commonlist_t**)_list;
1495 commonlist_t*next = l->next;
1496 list_append_(&dest, l->entry);