made method construction functions return abc_method instead of abc_method_body
[swftools.git] / lib / q.c
1 /* q.c
2
3    Part of the swftools package.
4    
5    Copyright (c) 2001,2002,2003,2004 Matthias Kramm <kramm@quiss.org>
6  
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.
11
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.
16
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 */
20
21
22 #include <stdlib.h>
23 #include <stdio.h>
24 #include <string.h>
25 #include <assert.h>
26 #include <memory.h>
27 #include "mem.h"
28 #include "types.h"
29 #include "q.h"
30
31 // ------------------------------- malloc, alloc routines ---------------------
32
33 #ifndef STRNDUP
34 char* strdup_n(const char*str, int size)
35 {
36     char*m = (char*)rfx_alloc(size+1);
37     memcpy(m, str, size);
38     m[size] = 0;
39     return m;
40 }
41 #endif
42 char*qstrdup(const char*string)
43 {
44     return strdup(string);
45 }
46 char*qstrndup(const char*string, int len)
47 {
48     return strdup_n(string, len);
49 }
50
51 // ------------------------------- mem_t --------------------------------------
52
53 void mem_init(mem_t*mem)
54 {
55     memset(mem, 0, sizeof(mem_t));
56 }
57 void mem_clear(mem_t*mem)
58 {
59     rfx_free(mem->buffer);mem->buffer = 0;
60 }
61 void mem_destroy(mem_t*mem)
62 {
63     mem_clear(mem);
64     rfx_free(mem);
65 }
66 static int mem_put_(mem_t*m,const void*data, int length, int null)
67 {
68     int n = m->pos;
69     m->pos += length + (null?1:0);
70     if(m->pos > m->len) { 
71         m->len = (m->pos+63)&~63;
72         m->buffer = m->buffer?(char*)rfx_realloc(m->buffer,m->len):(char*)rfx_alloc(m->len);
73     }
74     assert(n+length <= m->len);
75     memcpy(&m->buffer[n], data, length);
76     if(null)
77         m->buffer[n + length] = 0;
78     return n;
79 }
80 int mem_put(mem_t*m,void*data, int length)
81 {
82     return mem_put_(m, data, length, 0);
83 }
84 int mem_putstring(mem_t*m,string_t str)
85 {
86     return mem_put_(m, str.str, str.len, 1);
87 }
88
89 // ------------------------------- ringbuffer_t -------------------------------
90
91 typedef struct _ringbuffer_internal_t
92 {
93     unsigned char*buffer;
94     int readpos;
95     int writepos;
96     int buffersize;
97 } ringbuffer_internal_t;
98
99 void ringbuffer_init(ringbuffer_t*r)
100 {
101     ringbuffer_internal_t*i = (ringbuffer_internal_t*)rfx_calloc(sizeof(ringbuffer_internal_t)); 
102     memset(r, 0, sizeof(ringbuffer_t));
103     r->internal = i;
104     i->buffer = (unsigned char*)rfx_alloc(1024);
105     i->buffersize = 1024;
106 }
107 int ringbuffer_read(ringbuffer_t*r, void*buf, int len)
108 {
109     unsigned char* data = (unsigned char*)buf;
110     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
111     if(r->available < len)
112         len = r->available;
113     if(!len)
114         return 0;
115     if(i->readpos + len > i->buffersize) {
116         int read1 = i->buffersize-i->readpos;
117         memcpy(data, &i->buffer[i->readpos], read1);
118         memcpy(&data[read1], &i->buffer[0], len - read1);
119         i->readpos = len - read1;
120     } else {
121         memcpy(data, &i->buffer[i->readpos], len);
122         i->readpos += len;
123         i->readpos %= i->buffersize;
124     }
125     r->available -= len;
126     return len;
127 }
128 void ringbuffer_put(ringbuffer_t*r, void*buf, int len)
129 {
130     unsigned char* data = (unsigned char*)buf;
131     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
132     
133     if(i->buffersize - r->available < len)
134     {
135         unsigned char* buf2;
136         int newbuffersize = i->buffersize;
137         int oldavailable = r->available;
138         newbuffersize*=3;newbuffersize/=2; /*grow at least by 50% each time */
139
140         if(newbuffersize < r->available + len)
141             newbuffersize = r->available + len + 1024;
142
143         buf2 = (unsigned char*)rfx_alloc(newbuffersize);
144         ringbuffer_read(r, buf2, r->available);
145         rfx_free(i->buffer);
146         i->buffer = buf2;
147         i->buffersize = newbuffersize;
148         i->readpos = 0;
149         i->writepos = oldavailable;
150         r->available = oldavailable;
151     }
152     if(i->writepos + len > i->buffersize) {
153         int read1 = i->buffersize-i->writepos;
154         memcpy(&i->buffer[i->writepos], data, read1);
155         memcpy(&i->buffer[0], &data[read1], len - read1);
156         i->writepos = len - read1;
157     } else {
158         memcpy(&i->buffer[i->writepos], data, len);
159         i->writepos += len;
160         i->writepos %= i->buffersize;
161     }
162     r->available += len;
163 }
164 void ringbuffer_clear(ringbuffer_t*r)
165 {
166     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
167     rfx_free(i->buffer);i->buffer = 0;
168     rfx_free(i);
169 }
170
171 // ------------------------------- heap_t -------------------------------
172
173 void heap_init(heap_t*h,int n,int elem_size, int(*compare)(const void *, const void *))
174 {
175     memset(h, 0, sizeof(heap_t));
176     h->max_size = n;
177     h->size = 0;
178     h->elem_size = elem_size;
179     h->compare = compare;
180     h->elements = (void**)rfx_calloc(n*sizeof(void*));
181     h->data = (char*)rfx_calloc(h->max_size*h->elem_size);
182 }
183 void heap_clear(heap_t*h)
184 {
185     rfx_free(h->elements);
186     rfx_free(h->data);
187 }
188
189 #define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))>0)
190
191 static void up(heap_t*h, int node)
192 {
193     void*node_p = h->elements[node];
194     int parent = node;
195     do {
196         node = parent;
197         if(!node) break;
198         parent = (node-1)/2;
199         h->elements[node] = h->elements[parent];
200     } while(HEAP_NODE_SMALLER(h,h->elements[parent], node_p));
201
202     h->elements[node] = node_p;
203 }
204 static void down(heap_t*h, int node)
205 {
206     void*node_p = h->elements[node];
207     int child = node;
208     do {
209         node = child;
210
211         /* determine new child's position */
212         child = node<<1|1;
213         if(child >= h->size) 
214             break;
215         if(child+1 < h->size && HEAP_NODE_SMALLER(h,h->elements[child],h->elements[child+1])) // search for bigger child
216             child++;
217
218         h->elements[node] = h->elements[child];
219     } while(HEAP_NODE_SMALLER(h,node_p, h->elements[child]));
220     
221     h->elements[node] = node_p;
222 }
223 void heap_put(heap_t*h, void*e) 
224 {
225     int pos = h->size++;
226     memcpy(&h->data[pos*h->elem_size],e,h->elem_size);
227     h->elements[pos] = &h->data[pos];
228     up(h, pos);
229 }
230 int heap_size(heap_t*h)
231 {
232     return h->size;
233 }
234 void* heap_max(heap_t*h)
235 {
236     return h->elements[0];
237 }
238 void* heap_chopmax(heap_t*h)
239 {
240     void*p = h->elements[0];
241     h->elements[0] = h->elements[--h->size];
242     down(h,0);
243     return p;
244 }
245 void heap_dump(heap_t*h, FILE*fi)
246 {
247     int t;
248     for(t=0;t<h->size;t++) {
249         int s;
250         for(s=0;s<=t;s=(s+1)*2-1) {
251             if(s==t) fprintf(fi,"\n");
252         }
253         //fprintf(fi,"%d ", h->elements[t]->x); //?
254     }
255 }
256 void** heap_flatten(heap_t*h)
257 {
258     void**nodes = (void**)rfx_alloc(h->size*sizeof(void*));
259     void**p = nodes;
260    
261     while(h->size) {
262         /*printf("Heap Size: %d\n", h->size);
263         heap_print(stdout, h);
264         printf("\n");*/
265         *p++ = heap_chopmax(h);
266     }
267     return nodes;
268 }
269
270 // ------------------------------- crc32 --------------------------------------
271 static unsigned int*crc32 = 0;
272 static void crc32_init(void)
273 {
274     int t;
275     if(crc32) 
276         return;
277     crc32= (unsigned int*)rfx_alloc(sizeof(unsigned int)*256);
278     for(t=0; t<256; t++) {
279         unsigned int c = t;
280         int s;
281         for (s = 0; s < 8; s++) {
282           c = (0xedb88320L*(c&1)) ^ (c >> 1);
283         }
284         crc32[t] = c;
285     }
286 }
287 // ------------------------------- string_t -----------------------------------
288
289 void string_set2(string_t*str, const char*text, int len)
290 {
291     str->len = len;
292     str->str = text;
293 }
294 void string_set(string_t*str, const char*text)
295 {
296     if(text) {
297         str->len = strlen(text);
298     } else {
299         str->len = 0;
300     }
301     str->str = text;
302 }
303 string_t string_new(const char*text, int len)
304 {
305     string_t s;
306     s.len = len;
307     s.str = text;
308     return s;
309 }
310 string_t string_new2(const char*text)
311 {
312     string_t s;
313     if(text) {
314         s.len = strlen(text);
315     } else {
316         s.len = 0;
317     }
318     s.str = text;
319     return s;
320 }
321 char* string_cstr(string_t*str)
322 {
323     return strdup_n(str->str, str->len);
324 }
325
326 unsigned int crc32_add_byte(unsigned int checksum, unsigned char b) 
327 {
328     if(!crc32)
329         crc32_init();
330     return checksum>>8 ^ crc32[(b^checksum)&0xff];
331 }
332 unsigned int crc32_add_string(unsigned int checksum, const char*s)
333 {
334     if(!s)
335         return checksum;
336     while(*s) {
337         checksum = crc32_add_byte(checksum, *s);
338         s++;
339     }
340     return checksum;
341 }
342
343 unsigned int string_hash(const string_t*str)
344 {
345     int t;
346     unsigned int checksum = 0;
347     if(!crc32)
348         crc32_init();
349     for(t=0;t<str->len;t++) {
350         checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff];
351     }
352     return checksum;
353 }
354 unsigned int string_hash2(const char*str)
355 {
356     unsigned int checksum = 0;
357     const char*p = str;
358     if(!crc32)
359         crc32_init();
360     while(*p) {
361         checksum = checksum>>8 ^ crc32[(*p^checksum)&0xff];
362         p++;
363     }
364     return checksum;
365 }
366 unsigned int string_hash3(const char*str, int len)
367 {
368     string_t s;
369     s.str = str;
370     s.len = len;
371     return string_hash(&s);
372 }
373 void string_dup2(string_t*str, const char*text, int len)
374 {
375     str->len = len;
376     str->str = strdup_n(text, len);
377 }
378 void string_dup(string_t*str, const char*text)
379 {
380     str->len = strlen(text);
381     str->str = strdup(text);
382 }
383 int string_equals(string_t*str, const char*text)
384 {
385     int l = strlen(text);
386     if(str->len == l && !memcmp(str->str, text, l))
387         return 1;
388     return 0;
389 }
390 int string_equals2(string_t*str, string_t*str2)
391 {
392     if(str->len == str2->len && !memcmp(str->str, str2->str, str->len))
393         return 1;
394     return 0;
395 }
396
397 // ------------------------------- stringarray_t ------------------------------
398
399 typedef struct _stringlist {
400     int index;
401     struct _stringlist*next;
402 } stringlist_t;
403
404 typedef struct _stringarray_internal_t
405 {
406     mem_t pos;
407     stringlist_t**hash;
408     int num;
409     int hashsize;
410 } stringarray_internal_t;
411
412 void stringarray_init(stringarray_t*sa, int hashsize)
413 {
414     stringarray_internal_t*s;
415     int t;
416     sa->internal = (stringarray_internal_t*)rfx_calloc(sizeof(stringarray_internal_t)); 
417     s = (stringarray_internal_t*)sa->internal;
418     mem_init(&s->pos);
419     s->hash = rfx_calloc(sizeof(stringlist_t*)*hashsize);
420     s->hashsize = hashsize;
421 }
422 void stringarray_put(stringarray_t*sa, string_t str)
423 {
424     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
425     int pos;
426     int hash = string_hash(&str) % s->hashsize;
427
428     char*ss = string_cstr(&str);
429     mem_put(&s->pos, &ss, sizeof(char*));
430
431     stringlist_t*l = rfx_alloc(sizeof(stringlist_t));
432     l->index = s->num;
433     l->next = s->hash[hash];
434     s->hash[hash] = l;
435
436     s->num++;
437 }
438 char* stringarray_at(stringarray_t*sa, int pos)
439 {
440     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
441     char*p;
442     if(pos<0 || pos>=s->num)
443         return 0;
444     p = *(char**)&s->pos.buffer[pos*sizeof(char*)];
445     if(p<0)
446         return 0;
447     return p;
448 }
449 string_t stringarray_at2(stringarray_t*sa, int pos)
450 {
451     string_t s;
452     s.str = stringarray_at(sa, pos);
453     s.len = s.str?strlen(s.str):0;
454     return s;
455 }
456 static stringlist_t* stringlist_del(stringarray_t*sa, stringlist_t*l, int index)
457 {
458     stringlist_t*ll = l;
459     stringlist_t*old = l;
460     while(l) {
461         if(index==l->index) {
462             old->next = l->next;
463             memset(l, 0, sizeof(stringlist_t));
464             rfx_free(l);
465             if(old==l)
466                 return 0;
467             else
468                 return ll;
469         }
470         old = l;
471         l = l->next;
472     }
473     fprintf(stderr, "Internal error: did not find string %d in hash\n", index);
474     return ll;
475 }
476
477 void stringarray_del(stringarray_t*sa, int pos)
478 {
479     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
480     string_t str = stringarray_at2(sa, pos);
481     int hash = string_hash(&str) % s->hashsize;
482     s->hash[hash] = stringlist_del(sa, s->hash[hash], pos);
483     *(char**)&s->pos.buffer[pos*sizeof(char*)] = 0;
484 }
485 int stringarray_find(stringarray_t*sa, string_t* str)
486 {
487     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
488     int hash = string_hash(str) % s->hashsize;
489     int t;
490     stringlist_t*l = s->hash[hash];
491     //TODO: statistics
492     while(l) {
493         string_t s = stringarray_at2(sa, l->index);
494         if(string_equals2(str, &s)) {
495             return l->index;
496         }
497         l = l->next;
498     }
499     return -1;
500 }
501 void stringarray_clear(stringarray_t*sa)
502 {
503     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
504     mem_clear(&s->pos);
505     int t;
506     for(t=0;t<s->hashsize;t++) {
507         stringlist_t*l = s->hash[t];
508         while(l) {
509             stringlist_t*next = l->next;
510             memset(l, 0, sizeof(stringlist_t));
511             rfx_free(l);
512             l = next;
513         }
514     }
515     rfx_free(s->hash);s->hash=0;
516     rfx_free(s);
517 }
518 void stringarray_destroy(stringarray_t*sa)
519 {
520     stringarray_clear(sa);
521     rfx_free(sa);
522 }
523
524 // ------------------------------- type_t -------------------------------
525
526 char charptr_equals(const void*o1, const void*o2) 
527 {
528     if(!o1 || !o2)
529         return o1==o2;
530     return !strcmp(o1,o2);
531 }
532 unsigned int charptr_hash(const void*o) 
533 {
534     if(!o)
535         return 0;
536     return string_hash2(o);
537 }
538 void* charptr_dup(const void*o) 
539 {
540     if(!o)
541         return 0;
542     return strdup(o);
543 }
544 void charptr_free(void*o) 
545 {
546     if(o) {
547         rfx_free(o);
548     }
549 }
550 char stringstruct_equals(const void*o1, const void*o2) 
551 {
552     string_t*s1 = (string_t*)o1;
553     string_t*s2 = (string_t*)o2;
554     int l = s1->len<s2->len?s1->len:s2->len;
555     int r = memcmp(s1->str, s2->str, l);
556     if(r)
557         return 0;
558     else
559         return s1->len==s2->len;
560 }
561 unsigned int stringstruct_hash(const void*o) 
562 {
563     return string_hash(o);
564 }
565 void*stringstruct_dup(const void*o) 
566 {
567     string_t*s = malloc(sizeof(string_t));
568     string_set2(s, ((string_t*)o)->str, ((string_t*)o)->len);
569     return s;
570 }
571 void stringstruct_free(void*o) 
572 {
573     rfx_free((void*)(((string_t*)o)->str));
574     rfx_free((void*)o);
575 }
576
577
578 type_t charptr_type = {
579     equals: charptr_equals,
580     hash: charptr_hash,
581     dup: charptr_dup,
582     free: charptr_free,
583 };
584
585 type_t stringstruct_type = {
586     equals: stringstruct_equals,
587     hash: stringstruct_hash,
588     dup: stringstruct_dup,
589     free: stringstruct_free,
590 };
591
592 // ------------------------------- dictionary_t -------------------------------
593
594 #define INITIAL_SIZE 1
595
596 static int max(int x, int y) {
597     return x>y?x:y;
598 }
599
600 dict_t*dict_new()
601 {
602     dict_t*d = rfx_alloc(sizeof(dict_t));
603     dict_init(d, INITIAL_SIZE);
604     return d;
605 }
606 dict_t*dict_new2(type_t*t)
607 {
608     dict_t*d = rfx_alloc(sizeof(dict_t));
609     dict_init(d, INITIAL_SIZE);
610     d->key_type = t;
611     return d;
612 }
613 void dict_init(dict_t*h, int size) 
614 {
615     memset(h, 0, sizeof(dict_t));
616     h->hashsize = size;
617     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
618     h->num = 0;
619     h->key_type = &charptr_type;
620 }
621
622 dict_t*dict_clone(dict_t*o)
623 {
624     dict_t*h = rfx_alloc(sizeof(dict_t));
625     memcpy(h, o, sizeof(dict_t));
626     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
627     int t;
628     for(t=0;t<o->hashsize;t++) {
629         dictentry_t*e = o->slots[t];
630         while(e) {
631             dictentry_t*n = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
632             memcpy(n, e, sizeof(dictentry_t));
633             n->key = h->key_type->dup(e->key);
634             n->data = e->data;
635             n->next = h->slots[t];
636             h->slots[t] = n;
637             e = e->next;
638         }
639     }
640     return h;
641 }
642
643 static void dict_expand(dict_t*h, int newlen)
644 {
645     assert(h->hashsize < newlen);
646     dictentry_t**newslots = (dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*newlen);
647     int t; 
648     for(t=0;t<h->hashsize;t++) {
649         dictentry_t*e = h->slots[t];
650         while(e) {
651             dictentry_t*next = e->next;
652             unsigned int newhash = e->hash%newlen;
653             e->next = newslots[newhash];
654             newslots[newhash] = e;
655             e = next;
656         }
657     }
658     if(h->slots)
659         rfx_free(h->slots);
660     h->slots = newslots;
661     h->hashsize = newlen;
662 }
663
664 dictentry_t* dict_put(dict_t*h, const void*key, void* data)
665 {
666     unsigned int hash = h->key_type->hash(key);
667     dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
668     unsigned int hash2 = hash % h->hashsize;
669     
670     e->key = h->key_type->dup(key);
671     e->hash = hash; //for resizing
672     e->next = h->slots[hash2];
673     e->data = data;
674     h->slots[hash2] = e;
675     h->num++;
676     return e;
677 }
678 void dict_put2(dict_t*h, const char*s, void*data) 
679 {
680     assert(h->key_type == &charptr_type);
681     dict_put(h, s, data);
682 }
683 void dict_dump(dict_t*h, FILE*fi, const char*prefix)
684 {
685     int t;
686     for(t=0;t<h->hashsize;t++) {
687         dictentry_t*e = h->slots[t];
688         while(e) {
689             if(h->key_type!=&charptr_type) {
690                 fprintf(fi, "%s%08x=%08x\n", prefix, e->key, e->data);
691             } else {
692                 fprintf(fi, "%s%s=%08x\n", prefix, e->key, e->data);
693             }
694             e = e->next;
695         }
696     }
697 }
698
699 int dict_count(dict_t*h)
700 {
701     return h->num;
702 }
703
704 void* dict_lookup(dict_t*h, const void*key)
705 {
706     if(!h->num)
707         return 0;
708     
709     unsigned int ohash = h->key_type->hash(key);
710     unsigned int hash = ohash % h->hashsize;
711
712     /* check first entry for match */
713     dictentry_t*e = h->slots[hash];
714     if(e && h->key_type->equals(e->key, key)) {
715         return e->data;
716     } else if(e) {
717         e = e->next;
718     }
719
720     /* if dict is 2/3 filled, double the size. Do
721        this the first time we have to actually iterate
722        through a slot to find our data */
723     if(e && h->num*3 >= h->hashsize*2) {
724         int newsize = h->hashsize;
725         while(h->num*3 >= newsize*2) {
726             newsize = newsize<15?15:(newsize+1)*2-1;
727         }
728         dict_expand(h, newsize);
729         hash = ohash % h->hashsize;
730         e = h->slots[hash];
731     }
732
733     /* check subsequent entries for a match */
734     while(e) {
735         if(h->key_type->equals(e->key, key)) {
736             return e->data;
737         }
738         e = e->next;
739     }
740     return 0;
741 }
742 char dict_del(dict_t*h, const void*key)
743 {
744     if(!h->num)
745         return 0;
746     unsigned int hash = h->key_type->hash(key) % h->hashsize;
747     dictentry_t*head = h->slots[hash];
748     dictentry_t*e = head, *prev=0;
749     while(e) {
750         if(h->key_type->equals(e->key, key)) {
751             dictentry_t*next = e->next;
752             rfx_free((void*)e->key);
753             memset(e, 0, sizeof(dictentry_t));
754             rfx_free(e);
755             if(e == head) {
756                 h->slots[hash] = 0;
757             } else {
758                 assert(prev);
759                 prev->next = next;
760             }
761             h->num--;
762             return 1;
763         }
764         prev = e;
765         e = e->next;
766     }
767     return 0;
768 }
769
770 dictentry_t* dict_get_slot(dict_t*h, const void*key)
771 {
772     if(!h->num)
773         return 0;
774     unsigned int ohash = h->key_type->hash(key);
775     unsigned int hash = ohash % h->hashsize;
776     return h->slots[hash];
777 }
778
779 void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const void*key, void*val), void*data)
780 {
781     int t;
782     for(t=0;t<h->hashsize;t++) {
783         dictentry_t*e = h->slots[t];
784         while(e) {
785             dictentry_t*next = e->next;
786             if(runFunction) {
787                 runFunction(data, e->key, e->data);
788             }
789             e = e->next;
790         }
791     }
792 }
793 void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
794 {
795     int t;
796     for(t=0;t<h->hashsize;t++) {
797         dictentry_t*e = h->slots[t];
798         while(e) {
799             dictentry_t*next = e->next;
800             if(runFunction) {
801                 runFunction(e->data);
802             }
803             e = e->next;
804         }
805     }
806 }
807
808 void dict_free_all(dict_t*h, void (*freeFunction)(void*))
809 {
810     int t;
811     for(t=0;t<h->hashsize;t++) {
812         dictentry_t*e = h->slots[t];
813         while(e) {
814             dictentry_t*next = e->next;
815             h->key_type->free(e->key);
816             if(freeFunction) {
817                 freeFunction(e->data);
818             }
819             memset(e, 0, sizeof(dictentry_t));
820             rfx_free(e);
821             e = next;
822         }
823         h->slots[t]=0;
824     }
825     rfx_free(h->slots);
826     memset(h, 0, sizeof(dict_t));
827 }
828
829 void dict_clear(dict_t*h) 
830 {
831     dict_free_all(h, 0);
832 }
833
834 void dict_destroy(dict_t*dict)
835 {
836     dict_clear(dict);
837     rfx_free(dict);
838 }
839
840 // ------------------------------- map_t --------------------------------------
841
842 typedef struct _map_internal_t
843 {
844     dict_t d;
845 } map_internal_t;
846
847 void map_init(map_t*map)
848 {
849     map_internal_t*m;
850     map->internal = (map_internal_t*)rfx_calloc(sizeof(map_internal_t));
851     m = (map_internal_t*)map->internal;
852     dict_init(&m->d, INITIAL_SIZE);
853 }
854 void map_put(map_t*map, string_t t1, string_t t2)
855 {
856     map_internal_t*m = (map_internal_t*)map->internal;
857     string_t s;
858     char* s1 = string_cstr(&t1);
859     dict_put2(&m->d, s1, (void*)string_cstr(&t2));
860     rfx_free(s1);
861 }
862 const char* map_lookup(map_t*map, const char*name)
863 {
864     map_internal_t*m = (map_internal_t*)map->internal;
865     const char*value = dict_lookup(&m->d, name);
866     return value;
867 }
868 static void freestring(void*data)
869 {
870     rfx_free(data);
871 }
872 static void dumpmapentry(void*data, const void*key, void*value)
873 {
874     FILE*fi = (FILE*)data;
875     fprintf(fi, "%s=%s\n", key, (char*)value);
876 }
877 void map_dump(map_t*map, FILE*fi, const char*prefix)
878 {
879     int t;
880     map_internal_t*m = (map_internal_t*)map->internal;
881     dict_foreach_keyvalue(&m->d, dumpmapentry, fi);
882 }
883 void map_clear(map_t*map)
884 {
885     map_internal_t*m = (map_internal_t*)map->internal;
886     dict_free_all(&m->d, freestring);
887     rfx_free(m);
888 }
889 void map_destroy(map_t*map)
890 {
891     map_clear(map);
892     rfx_free(map);
893 }
894
895 // ------------------------------- array_t --------------------------------------
896
897 array_t* array_new() {
898     array_t*d = malloc(sizeof(array_t));
899     memset(d, 0, sizeof(array_t));
900     d->entry2pos = dict_new();
901     return d;
902 }
903 array_t* array_new2(type_t*type) {
904     array_t*d = malloc(sizeof(array_t));
905     memset(d, 0, sizeof(array_t));
906     d->entry2pos = dict_new2(type);
907     return d;
908 }
909 void*array_getkey(array_t*array, int nr) {
910     if(nr > array->num || nr<0) {
911         printf("error: reference to element %d in array[%d]\n", nr, array->num);
912         *(int*)0 = 0xdead;
913         return 0;
914     }
915     return array->d[nr].name;
916 }
917 void*array_getvalue(array_t*array, int nr) {
918     if(nr > array->num || nr<0) {
919         printf("error: reference to element %d in array[%d]\n", nr, array->num);
920         *(int*)0 = 0xdead;
921         return 0;
922     }
923     return array->d[nr].data;
924 }
925 int array_append(array_t*array, const void*name, void*data) {
926     while(array->size <= array->num) {
927         array->size += 64;
928         if(!array->d) {
929             array->d = malloc(sizeof(array_entry_t)*array->size);
930         } else {
931             array->d = realloc(array->d, sizeof(array_entry_t)*array->size);
932         }
933     }
934
935     dictentry_t*e = dict_put(array->entry2pos, name, (void*)(ptroff_t)(array->num+1));
936
937     if(name) {
938         array->d[array->num].name = e->key;
939     } else {
940         array->d[array->num].name = 0;
941     }
942     array->d[array->num].data = (void*)data;
943     return array->num++;
944 }
945 int array_find(array_t*array, const void*name)
946 {
947     int pos = (int)(ptroff_t)dict_lookup(array->entry2pos, name);
948     return pos-1;
949 }
950 int array_find2(array_t*array, const void*name, void*data)
951 {
952     dict_t*h= array->entry2pos;
953     dictentry_t*e = dict_get_slot(array->entry2pos, name);
954
955     while(e) {
956         int index = ((int)(ptroff_t)e->data) - 1;
957         if(h->key_type->equals(e->key, name) && array->d[index].data == data) {
958             return index;
959         }
960         e = e->next;
961     }
962     return -1;
963 }
964 int array_update(array_t*array, const void*name, void*data) {
965     int pos = array_find(array, name);
966     if(pos>=0) {
967         array->d[pos].data = data;
968         return pos;
969     }
970     return array_append(array, name, data);
971 }
972 int array_append_if_new(array_t*array, const void*name, void*data) {
973     int pos = array_find(array, name);
974     if(pos>=0)
975         return pos;
976     return array_append(array, name, data);
977 }
978 void array_free(array_t*array) {
979     dict_destroy(array->entry2pos);
980     if(array->d) {
981         free(array->d);array->d = 0;
982     }
983     free(array);
984 }
985
986 // ------------------------------- list_t --------------------------------------
987
988 struct _commonlist;
989 typedef struct _listinfo {
990     int size;
991     struct _commonlist*last;
992 } listinfo_t;
993
994 typedef struct _commonlist {
995     void*entry;
996     struct _commonlist*next;
997     listinfo_t info[0];
998 } commonlist_t;
999
1000 int list_length_(void*_list)
1001 {
1002     commonlist_t*l = (commonlist_t*)_list;
1003     if(!l)
1004         return 0;
1005     return l->info[0].size;
1006 }
1007 void list_append_(void*_list, void*entry)
1008 {
1009     commonlist_t**list = (commonlist_t**)_list;
1010     commonlist_t* n = 0;
1011     if(!*list) {
1012         n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1013         *list = n;
1014         (*list)->info[0].size = 0;
1015     } else {
1016         n = malloc(sizeof(commonlist_t));
1017         (*list)->info[0].last->next = n;
1018     }
1019     n->next = 0;
1020     n->entry = entry;
1021     (*list)->info[0].last = n;
1022     (*list)->info[0].size++;
1023 }
1024 /* notice: prepending uses slighly more space than appending */
1025 void list_prepend_(void*_list, void*entry)
1026 {
1027     commonlist_t**list = (commonlist_t**)_list;
1028     commonlist_t* n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1029     int size = 0;
1030     commonlist_t* last = 0;
1031     if(*list) {
1032         last = (*list)->info[0].last;
1033         size = (*list)->info[0].size;
1034     }
1035     n->next = *list;
1036     n->entry = entry;
1037     *list = n;
1038     (*list)->info[0].last = last;
1039     (*list)->info[0].size = size+1;
1040 }
1041 void list_free_(void*_list) 
1042 {
1043     commonlist_t**list = (commonlist_t**)_list;
1044     commonlist_t*l = *list;
1045     while(l) {
1046         commonlist_t*next = l->next;
1047         free(l);
1048         l = next;
1049     }
1050     *list = 0;
1051 }
1052 void*list_clone_(void*_list) 
1053 {
1054     commonlist_t*l = *(commonlist_t**)_list;
1055
1056     void*dest = 0;
1057     while(l) {
1058         commonlist_t*next = l->next;
1059         list_append_(&dest, l->entry);
1060         l = next;
1061     }
1062     return dest;
1063
1064 }