added ptr_type
[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 ptr_equals(const void*o1, const void*o2) 
527 {
528     return o1==o2;
529 }
530 unsigned int ptr_hash(const void*o) 
531 {
532     return string_hash3(o, sizeof(o));
533 }
534 void* ptr_dup(const void*o) 
535 {
536     return (void*)o;
537 }
538 void ptr_free(void*o) 
539 {
540     return;
541 }
542
543 char charptr_equals(const void*o1, const void*o2) 
544 {
545     if(!o1 || !o2)
546         return o1==o2;
547     return !strcmp(o1,o2);
548 }
549 unsigned int charptr_hash(const void*o) 
550 {
551     if(!o)
552         return 0;
553     return string_hash2(o);
554 }
555 void* charptr_dup(const void*o) 
556 {
557     if(!o)
558         return 0;
559     return strdup(o);
560 }
561 void charptr_free(void*o) 
562 {
563     if(o) {
564         rfx_free(o);
565     }
566 }
567
568 char stringstruct_equals(const void*o1, const void*o2) 
569 {
570     string_t*s1 = (string_t*)o1;
571     string_t*s2 = (string_t*)o2;
572     int l = s1->len<s2->len?s1->len:s2->len;
573     int r = memcmp(s1->str, s2->str, l);
574     if(r)
575         return 0;
576     else
577         return s1->len==s2->len;
578 }
579 unsigned int stringstruct_hash(const void*o) 
580 {
581     return string_hash(o);
582 }
583 void*stringstruct_dup(const void*o) 
584 {
585     string_t*s = malloc(sizeof(string_t));
586     string_set2(s, ((string_t*)o)->str, ((string_t*)o)->len);
587     return s;
588 }
589 void stringstruct_free(void*o) 
590 {
591     rfx_free((void*)(((string_t*)o)->str));
592     rfx_free((void*)o);
593 }
594
595 type_t ptr_type = {
596     equals: ptr_equals,
597     hash: ptr_hash,
598     dup: ptr_dup,
599     free: ptr_free,
600 };
601
602 type_t charptr_type = {
603     equals: charptr_equals,
604     hash: charptr_hash,
605     dup: charptr_dup,
606     free: charptr_free,
607 };
608
609 type_t stringstruct_type = {
610     equals: stringstruct_equals,
611     hash: stringstruct_hash,
612     dup: stringstruct_dup,
613     free: stringstruct_free,
614 };
615
616 // ------------------------------- dictionary_t -------------------------------
617
618 #define INITIAL_SIZE 1
619
620 static int max(int x, int y) {
621     return x>y?x:y;
622 }
623
624 dict_t*dict_new()
625 {
626     dict_t*d = rfx_alloc(sizeof(dict_t));
627     dict_init(d, INITIAL_SIZE);
628     return d;
629 }
630 dict_t*dict_new2(type_t*t)
631 {
632     dict_t*d = rfx_alloc(sizeof(dict_t));
633     dict_init(d, INITIAL_SIZE);
634     d->key_type = t;
635     return d;
636 }
637 void dict_init(dict_t*h, int size) 
638 {
639     memset(h, 0, sizeof(dict_t));
640     h->hashsize = size;
641     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
642     h->num = 0;
643     h->key_type = &charptr_type;
644 }
645
646 dict_t*dict_clone(dict_t*o)
647 {
648     dict_t*h = rfx_alloc(sizeof(dict_t));
649     memcpy(h, o, sizeof(dict_t));
650     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
651     int t;
652     for(t=0;t<o->hashsize;t++) {
653         dictentry_t*e = o->slots[t];
654         while(e) {
655             dictentry_t*n = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
656             memcpy(n, e, sizeof(dictentry_t));
657             n->key = h->key_type->dup(e->key);
658             n->data = e->data;
659             n->next = h->slots[t];
660             h->slots[t] = n;
661             e = e->next;
662         }
663     }
664     return h;
665 }
666
667 static void dict_expand(dict_t*h, int newlen)
668 {
669     assert(h->hashsize < newlen);
670     dictentry_t**newslots = (dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*newlen);
671     int t; 
672     for(t=0;t<h->hashsize;t++) {
673         dictentry_t*e = h->slots[t];
674         while(e) {
675             dictentry_t*next = e->next;
676             unsigned int newhash = e->hash%newlen;
677             e->next = newslots[newhash];
678             newslots[newhash] = e;
679             e = next;
680         }
681     }
682     if(h->slots)
683         rfx_free(h->slots);
684     h->slots = newslots;
685     h->hashsize = newlen;
686 }
687
688 dictentry_t* dict_put(dict_t*h, const void*key, void* data)
689 {
690     unsigned int hash = h->key_type->hash(key);
691     dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
692     unsigned int hash2 = hash % h->hashsize;
693     
694     e->key = h->key_type->dup(key);
695     e->hash = hash; //for resizing
696     e->next = h->slots[hash2];
697     e->data = data;
698     h->slots[hash2] = e;
699     h->num++;
700     return e;
701 }
702 void dict_put2(dict_t*h, const char*s, void*data) 
703 {
704     assert(h->key_type == &charptr_type);
705     dict_put(h, s, data);
706 }
707 void dict_dump(dict_t*h, FILE*fi, const char*prefix)
708 {
709     int t;
710     for(t=0;t<h->hashsize;t++) {
711         dictentry_t*e = h->slots[t];
712         while(e) {
713             if(h->key_type!=&charptr_type) {
714                 fprintf(fi, "%s%08x=%08x\n", prefix, e->key, e->data);
715             } else {
716                 fprintf(fi, "%s%s=%08x\n", prefix, e->key, e->data);
717             }
718             e = e->next;
719         }
720     }
721 }
722
723 int dict_count(dict_t*h)
724 {
725     return h->num;
726 }
727
728 void* dict_lookup(dict_t*h, const void*key)
729 {
730     if(!h->num)
731         return 0;
732     
733     unsigned int ohash = h->key_type->hash(key);
734     unsigned int hash = ohash % h->hashsize;
735
736     /* check first entry for match */
737     dictentry_t*e = h->slots[hash];
738     if(e && h->key_type->equals(e->key, key)) {
739         return e->data;
740     } else if(e) {
741         e = e->next;
742     }
743
744     /* if dict is 2/3 filled, double the size. Do
745        this the first time we have to actually iterate
746        through a slot to find our data */
747     if(e && h->num*3 >= h->hashsize*2) {
748         int newsize = h->hashsize;
749         while(h->num*3 >= newsize*2) {
750             newsize = newsize<15?15:(newsize+1)*2-1;
751         }
752         dict_expand(h, newsize);
753         hash = ohash % h->hashsize;
754         e = h->slots[hash];
755     }
756
757     /* check subsequent entries for a match */
758     while(e) {
759         if(h->key_type->equals(e->key, key)) {
760             return e->data;
761         }
762         e = e->next;
763     }
764     return 0;
765 }
766 char dict_del(dict_t*h, const void*key)
767 {
768     if(!h->num)
769         return 0;
770     unsigned int hash = h->key_type->hash(key) % h->hashsize;
771     dictentry_t*head = h->slots[hash];
772     dictentry_t*e = head, *prev=0;
773     while(e) {
774         if(h->key_type->equals(e->key, key)) {
775             dictentry_t*next = e->next;
776             rfx_free((void*)e->key);
777             memset(e, 0, sizeof(dictentry_t));
778             rfx_free(e);
779             if(e == head) {
780                 h->slots[hash] = 0;
781             } else {
782                 assert(prev);
783                 prev->next = next;
784             }
785             h->num--;
786             return 1;
787         }
788         prev = e;
789         e = e->next;
790     }
791     return 0;
792 }
793
794 dictentry_t* dict_get_slot(dict_t*h, const void*key)
795 {
796     if(!h->num)
797         return 0;
798     unsigned int ohash = h->key_type->hash(key);
799     unsigned int hash = ohash % h->hashsize;
800     return h->slots[hash];
801 }
802
803 void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const void*key, void*val), void*data)
804 {
805     int t;
806     for(t=0;t<h->hashsize;t++) {
807         dictentry_t*e = h->slots[t];
808         while(e) {
809             dictentry_t*next = e->next;
810             if(runFunction) {
811                 runFunction(data, e->key, e->data);
812             }
813             e = e->next;
814         }
815     }
816 }
817 void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
818 {
819     int t;
820     for(t=0;t<h->hashsize;t++) {
821         dictentry_t*e = h->slots[t];
822         while(e) {
823             dictentry_t*next = e->next;
824             if(runFunction) {
825                 runFunction(e->data);
826             }
827             e = e->next;
828         }
829     }
830 }
831
832 void dict_free_all(dict_t*h, void (*freeFunction)(void*))
833 {
834     int t;
835     for(t=0;t<h->hashsize;t++) {
836         dictentry_t*e = h->slots[t];
837         while(e) {
838             dictentry_t*next = e->next;
839             h->key_type->free(e->key);
840             if(freeFunction) {
841                 freeFunction(e->data);
842             }
843             memset(e, 0, sizeof(dictentry_t));
844             rfx_free(e);
845             e = next;
846         }
847         h->slots[t]=0;
848     }
849     rfx_free(h->slots);
850     memset(h, 0, sizeof(dict_t));
851 }
852
853 void dict_clear(dict_t*h) 
854 {
855     dict_free_all(h, 0);
856 }
857
858 void dict_destroy(dict_t*dict)
859 {
860     dict_clear(dict);
861     rfx_free(dict);
862 }
863
864 // ------------------------------- map_t --------------------------------------
865
866 typedef struct _map_internal_t
867 {
868     dict_t d;
869 } map_internal_t;
870
871 void map_init(map_t*map)
872 {
873     map_internal_t*m;
874     map->internal = (map_internal_t*)rfx_calloc(sizeof(map_internal_t));
875     m = (map_internal_t*)map->internal;
876     dict_init(&m->d, INITIAL_SIZE);
877 }
878 void map_put(map_t*map, string_t t1, string_t t2)
879 {
880     map_internal_t*m = (map_internal_t*)map->internal;
881     string_t s;
882     char* s1 = string_cstr(&t1);
883     dict_put2(&m->d, s1, (void*)string_cstr(&t2));
884     rfx_free(s1);
885 }
886 const char* map_lookup(map_t*map, const char*name)
887 {
888     map_internal_t*m = (map_internal_t*)map->internal;
889     const char*value = dict_lookup(&m->d, name);
890     return value;
891 }
892 static void freestring(void*data)
893 {
894     rfx_free(data);
895 }
896 static void dumpmapentry(void*data, const void*key, void*value)
897 {
898     FILE*fi = (FILE*)data;
899     fprintf(fi, "%s=%s\n", key, (char*)value);
900 }
901 void map_dump(map_t*map, FILE*fi, const char*prefix)
902 {
903     int t;
904     map_internal_t*m = (map_internal_t*)map->internal;
905     dict_foreach_keyvalue(&m->d, dumpmapentry, fi);
906 }
907 void map_clear(map_t*map)
908 {
909     map_internal_t*m = (map_internal_t*)map->internal;
910     dict_free_all(&m->d, freestring);
911     rfx_free(m);
912 }
913 void map_destroy(map_t*map)
914 {
915     map_clear(map);
916     rfx_free(map);
917 }
918
919 // ------------------------------- array_t --------------------------------------
920
921 array_t* array_new() {
922     array_t*d = malloc(sizeof(array_t));
923     memset(d, 0, sizeof(array_t));
924     d->entry2pos = dict_new();
925     return d;
926 }
927 array_t* array_new2(type_t*type) {
928     array_t*d = malloc(sizeof(array_t));
929     memset(d, 0, sizeof(array_t));
930     d->entry2pos = dict_new2(type);
931     return d;
932 }
933 void*array_getkey(array_t*array, int nr) {
934     if(nr > array->num || nr<0) {
935         printf("error: reference to element %d in array[%d]\n", nr, array->num);
936         *(int*)0 = 0xdead;
937         return 0;
938     }
939     return array->d[nr].name;
940 }
941 void*array_getvalue(array_t*array, int nr) {
942     if(nr > array->num || nr<0) {
943         printf("error: reference to element %d in array[%d]\n", nr, array->num);
944         *(int*)0 = 0xdead;
945         return 0;
946     }
947     return array->d[nr].data;
948 }
949 int array_append(array_t*array, const void*name, void*data) {
950     while(array->size <= array->num) {
951         array->size += 64;
952         if(!array->d) {
953             array->d = malloc(sizeof(array_entry_t)*array->size);
954         } else {
955             array->d = realloc(array->d, sizeof(array_entry_t)*array->size);
956         }
957     }
958
959     dictentry_t*e = dict_put(array->entry2pos, name, (void*)(ptroff_t)(array->num+1));
960
961     if(name) {
962         array->d[array->num].name = e->key;
963     } else {
964         array->d[array->num].name = 0;
965     }
966     array->d[array->num].data = (void*)data;
967     return array->num++;
968 }
969 int array_find(array_t*array, const void*name)
970 {
971     int pos = (int)(ptroff_t)dict_lookup(array->entry2pos, name);
972     return pos-1;
973 }
974 int array_find2(array_t*array, const void*name, void*data)
975 {
976     dict_t*h= array->entry2pos;
977     dictentry_t*e = dict_get_slot(array->entry2pos, name);
978
979     while(e) {
980         int index = ((int)(ptroff_t)e->data) - 1;
981         if(h->key_type->equals(e->key, name) && array->d[index].data == data) {
982             return index;
983         }
984         e = e->next;
985     }
986     return -1;
987 }
988 int array_update(array_t*array, const void*name, void*data) {
989     int pos = array_find(array, name);
990     if(pos>=0) {
991         array->d[pos].data = data;
992         return pos;
993     }
994     return array_append(array, name, data);
995 }
996 int array_append_if_new(array_t*array, const void*name, void*data) {
997     int pos = array_find(array, name);
998     if(pos>=0)
999         return pos;
1000     return array_append(array, name, data);
1001 }
1002 void array_free(array_t*array) {
1003     dict_destroy(array->entry2pos);
1004     if(array->d) {
1005         free(array->d);array->d = 0;
1006     }
1007     free(array);
1008 }
1009
1010 // ------------------------------- list_t --------------------------------------
1011
1012 struct _commonlist;
1013 typedef struct _listinfo {
1014     int size;
1015     struct _commonlist*last;
1016 } listinfo_t;
1017
1018 typedef struct _commonlist {
1019     void*entry;
1020     struct _commonlist*next;
1021     listinfo_t info[0];
1022 } commonlist_t;
1023
1024 int list_length_(void*_list)
1025 {
1026     commonlist_t*l = (commonlist_t*)_list;
1027     if(!l)
1028         return 0;
1029     return l->info[0].size;
1030 }
1031 void list_append_(void*_list, void*entry)
1032 {
1033     commonlist_t**list = (commonlist_t**)_list;
1034     commonlist_t* n = 0;
1035     if(!*list) {
1036         n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1037         *list = n;
1038         (*list)->info[0].size = 0;
1039     } else {
1040         n = malloc(sizeof(commonlist_t));
1041         (*list)->info[0].last->next = n;
1042     }
1043     n->next = 0;
1044     n->entry = entry;
1045     (*list)->info[0].last = n;
1046     (*list)->info[0].size++;
1047 }
1048 /* notice: prepending uses slighly more space than appending */
1049 void list_prepend_(void*_list, void*entry)
1050 {
1051     commonlist_t**list = (commonlist_t**)_list;
1052     commonlist_t* n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1053     int size = 0;
1054     commonlist_t* last = 0;
1055     if(*list) {
1056         last = (*list)->info[0].last;
1057         size = (*list)->info[0].size;
1058     }
1059     n->next = *list;
1060     n->entry = entry;
1061     *list = n;
1062     (*list)->info[0].last = last;
1063     (*list)->info[0].size = size+1;
1064 }
1065 void list_free_(void*_list) 
1066 {
1067     commonlist_t**list = (commonlist_t**)_list;
1068     commonlist_t*l = *list;
1069     while(l) {
1070         commonlist_t*next = l->next;
1071         free(l);
1072         l = next;
1073     }
1074     *list = 0;
1075 }
1076 void*list_clone_(void*_list) 
1077 {
1078     commonlist_t*l = *(commonlist_t**)_list;
1079
1080     void*dest = 0;
1081     while(l) {
1082         commonlist_t*next = l->next;
1083         list_append_(&dest, l->entry);
1084         l = next;
1085     }
1086     return dest;
1087
1088 }