fixed bug in for/do/while/switch
[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 string_t* string_new3(const char*text, int len)
322 {
323     if(!text) {
324         string_t*s = malloc(sizeof(string_t));
325         s->len = 0;
326         s->str = 0;
327         return s;
328     } else {
329         string_t*s = malloc(sizeof(string_t)+len+1);
330         s->len = len;
331         s->str = (const char*)(s+1);
332         memcpy((char*)s->str, text, len);
333         ((char*)s->str)[len]=0;
334         return s;
335     }
336 }
337 string_t* string_new4(const char*text)
338 {
339     int l = strlen(text);
340     return string_new3(text, l);
341 }
342
343 void string_free(string_t*s)
344 {
345     if(!s) 
346         return;
347     s->len = 0;
348     if((string_t*)(s->str) == s+1) {
349         s->str = 0;
350         rfx_free(s);
351     } else {
352         rfx_free((char*)(s->str));
353         s->str = 0;
354         rfx_free(s);
355     }
356 }
357 char* string_cstr(string_t*str)
358 {
359     return strdup_n(str->str, str->len);
360 }
361 char* string_escape(string_t*str)
362 {
363     int t;
364     int len = 0;
365     for(t=0;t<str->len;t++) {
366         if(str->str[t]<0x20)
367             len+=3;
368         else
369             len++;
370     }
371     char*s = malloc(len+1);
372     char*p=s;
373     for(t=0;t<str->len;t++) {
374         if(str->str[t]<0x20) {
375             *p++ ='\\';
376             unsigned char c = str->str[t];
377             *p++ = "0123456789abcdef"[c>>4];
378             *p++ = "0123456789abcdef"[c&0x0f];
379         } else {
380             *p++ = str->str[t];
381         }
382     }
383     *p++ = 0;
384     assert(p == &s[len+1]);
385     return s;
386 }
387
388 unsigned int crc32_add_byte(unsigned int checksum, unsigned char b) 
389 {
390     if(!crc32)
391         crc32_init();
392     return checksum>>8 ^ crc32[(b^checksum)&0xff];
393 }
394 unsigned int crc32_add_string(unsigned int checksum, const char*s)
395 {
396     if(!s)
397         return checksum;
398     while(*s) {
399         checksum = crc32_add_byte(checksum, *s);
400         s++;
401     }
402     return checksum;
403 }
404
405 unsigned int string_hash(const string_t*str)
406 {
407     int t;
408     unsigned int checksum = 0;
409     if(!crc32)
410         crc32_init();
411     for(t=0;t<str->len;t++) {
412         checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff];
413     }
414     return checksum;
415 }
416 unsigned int string_hash2(const char*str)
417 {
418     unsigned int checksum = 0;
419     const char*p = str;
420     if(!crc32)
421         crc32_init();
422     while(*p) {
423         checksum = checksum>>8 ^ crc32[(*p^checksum)&0xff];
424         p++;
425     }
426     return checksum;
427 }
428 unsigned int string_hash3(const char*str, int len)
429 {
430     string_t s;
431     s.str = str;
432     s.len = len;
433     return string_hash(&s);
434 }
435 void string_dup2(string_t*str, const char*text, int len)
436 {
437     str->len = len;
438     str->str = strdup_n(text, len);
439 }
440 void string_dup(string_t*str, const char*text)
441 {
442     str->len = strlen(text);
443     str->str = strdup(text);
444 }
445 int string_equals(string_t*str, const char*text)
446 {
447     int l = strlen(text);
448     if(str->len == l && !memcmp(str->str, text, l))
449         return 1;
450     return 0;
451 }
452 int string_equals2(string_t*str, string_t*str2)
453 {
454     if(str->len == str2->len && !memcmp(str->str, str2->str, str->len))
455         return 1;
456     return 0;
457 }
458
459 // ------------------------------- stringarray_t ------------------------------
460
461 typedef struct _stringlist {
462     int index;
463     struct _stringlist*next;
464 } stringlist_t;
465
466 typedef struct _stringarray_internal_t
467 {
468     mem_t pos;
469     stringlist_t**hash;
470     int num;
471     int hashsize;
472 } stringarray_internal_t;
473
474 void stringarray_init(stringarray_t*sa, int hashsize)
475 {
476     stringarray_internal_t*s;
477     int t;
478     sa->internal = (stringarray_internal_t*)rfx_calloc(sizeof(stringarray_internal_t)); 
479     s = (stringarray_internal_t*)sa->internal;
480     mem_init(&s->pos);
481     s->hash = rfx_calloc(sizeof(stringlist_t*)*hashsize);
482     s->hashsize = hashsize;
483 }
484 void stringarray_put(stringarray_t*sa, string_t str)
485 {
486     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
487     int pos;
488     int hash = string_hash(&str) % s->hashsize;
489
490     char*ss = string_cstr(&str);
491     mem_put(&s->pos, &ss, sizeof(char*));
492
493     stringlist_t*l = rfx_alloc(sizeof(stringlist_t));
494     l->index = s->num;
495     l->next = s->hash[hash];
496     s->hash[hash] = l;
497
498     s->num++;
499 }
500 char* stringarray_at(stringarray_t*sa, int pos)
501 {
502     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
503     char*p;
504     if(pos<0 || pos>=s->num)
505         return 0;
506     p = *(char**)&s->pos.buffer[pos*sizeof(char*)];
507     if(p<0)
508         return 0;
509     return p;
510 }
511 string_t stringarray_at2(stringarray_t*sa, int pos)
512 {
513     string_t s;
514     s.str = stringarray_at(sa, pos);
515     s.len = s.str?strlen(s.str):0;
516     return s;
517 }
518 static stringlist_t* stringlist_del(stringarray_t*sa, stringlist_t*l, int index)
519 {
520     stringlist_t*ll = l;
521     stringlist_t*old = l;
522     while(l) {
523         if(index==l->index) {
524             old->next = l->next;
525             memset(l, 0, sizeof(stringlist_t));
526             rfx_free(l);
527             if(old==l)
528                 return 0;
529             else
530                 return ll;
531         }
532         old = l;
533         l = l->next;
534     }
535     fprintf(stderr, "Internal error: did not find string %d in hash\n", index);
536     return ll;
537 }
538
539 void stringarray_del(stringarray_t*sa, int pos)
540 {
541     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
542     string_t str = stringarray_at2(sa, pos);
543     int hash = string_hash(&str) % s->hashsize;
544     s->hash[hash] = stringlist_del(sa, s->hash[hash], pos);
545     *(char**)&s->pos.buffer[pos*sizeof(char*)] = 0;
546 }
547 int stringarray_find(stringarray_t*sa, string_t* str)
548 {
549     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
550     int hash = string_hash(str) % s->hashsize;
551     int t;
552     stringlist_t*l = s->hash[hash];
553     //TODO: statistics
554     while(l) {
555         string_t s = stringarray_at2(sa, l->index);
556         if(string_equals2(str, &s)) {
557             return l->index;
558         }
559         l = l->next;
560     }
561     return -1;
562 }
563 void stringarray_clear(stringarray_t*sa)
564 {
565     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
566     mem_clear(&s->pos);
567     int t;
568     for(t=0;t<s->hashsize;t++) {
569         stringlist_t*l = s->hash[t];
570         while(l) {
571             stringlist_t*next = l->next;
572             memset(l, 0, sizeof(stringlist_t));
573             rfx_free(l);
574             l = next;
575         }
576     }
577     rfx_free(s->hash);s->hash=0;
578     rfx_free(s);
579 }
580 void stringarray_destroy(stringarray_t*sa)
581 {
582     stringarray_clear(sa);
583     rfx_free(sa);
584 }
585
586 // ------------------------------- type_t -------------------------------
587
588 char ptr_equals(const void*o1, const void*o2) 
589 {
590     return o1==o2;
591 }
592 unsigned int ptr_hash(const void*o) 
593 {
594     return string_hash3(o, sizeof(o));
595 }
596 void* ptr_dup(const void*o) 
597 {
598     return (void*)o;
599 }
600 void ptr_free(void*o) 
601 {
602     return;
603 }
604
605 char charptr_equals(const void*o1, const void*o2) 
606 {
607     if(!o1 || !o2)
608         return o1==o2;
609     return !strcmp(o1,o2);
610 }
611 unsigned int charptr_hash(const void*o) 
612 {
613     if(!o)
614         return 0;
615     return string_hash2(o);
616 }
617 void* charptr_dup(const void*o) 
618 {
619     if(!o)
620         return 0;
621     return strdup(o);
622 }
623 void charptr_free(void*o) 
624 {
625     if(o) {
626         rfx_free(o);
627     }
628 }
629
630 char stringstruct_equals(const void*o1, const void*o2) 
631 {
632     if(!o1 || !o2) 
633         return o1==o2;
634     string_t*s1 = (string_t*)o1;
635     string_t*s2 = (string_t*)o2;
636     int l = s1->len<s2->len?s1->len:s2->len;
637     int r = memcmp(s1->str, s2->str, l);
638     if(r)
639         return 0;
640     else
641         return s1->len==s2->len;
642 }
643 unsigned int stringstruct_hash(const void*o) 
644 {
645     if(!o) return 0;
646     return string_hash(o);
647 }
648 string_t*string_dup3(string_t*o)
649 {
650     if(!o) return 0;
651     if(!o->str) {
652         string_t*s = malloc(sizeof(string_t));
653         s->str=0;
654         s->len=0;
655         return s;
656     }
657     string_t*s = rfx_alloc(sizeof(string_t)+o->len+1);
658     s->len = o->len;
659     s->str = (const char*)(s+1);
660     memcpy((char*)s->str, o->str, s->len);
661     ((char*)s->str)[s->len]=0;
662     return s;
663 }
664 void stringstruct_free(void*o) 
665 {
666     if(o)
667         string_free(o);
668 }
669
670 type_t ptr_type = {
671     equals: ptr_equals,
672     hash: ptr_hash,
673     dup: ptr_dup,
674     free: ptr_free,
675 };
676
677 type_t charptr_type = {
678     equals: charptr_equals,
679     hash: charptr_hash,
680     dup: charptr_dup,
681     free: charptr_free,
682 };
683
684 type_t stringstruct_type = {
685     equals: stringstruct_equals,
686     hash: stringstruct_hash,
687     dup: (dup_func)string_dup3,
688     free: stringstruct_free,
689 };
690
691 // ------------------------------- dictionary_t -------------------------------
692
693 #define INITIAL_SIZE 1
694
695 static int max(int x, int y) {
696     return x>y?x:y;
697 }
698
699 dict_t*dict_new()
700 {
701     dict_t*d = rfx_alloc(sizeof(dict_t));
702     dict_init(d, INITIAL_SIZE);
703     return d;
704 }
705 dict_t*dict_new2(type_t*t)
706 {
707     dict_t*d = rfx_alloc(sizeof(dict_t));
708     dict_init(d, INITIAL_SIZE);
709     d->key_type = t;
710     return d;
711 }
712 void dict_init(dict_t*h, int size) 
713 {
714     memset(h, 0, sizeof(dict_t));
715     h->hashsize = size;
716     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
717     h->num = 0;
718     h->key_type = &charptr_type;
719 }
720
721 dict_t*dict_clone(dict_t*o)
722 {
723     dict_t*h = rfx_alloc(sizeof(dict_t));
724     memcpy(h, o, sizeof(dict_t));
725     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
726     int t;
727     for(t=0;t<o->hashsize;t++) {
728         dictentry_t*e = o->slots[t];
729         while(e) {
730             dictentry_t*n = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
731             memcpy(n, e, sizeof(dictentry_t));
732             n->key = h->key_type->dup(e->key);
733             n->data = e->data;
734             n->next = h->slots[t];
735             h->slots[t] = n;
736             e = e->next;
737         }
738     }
739     return h;
740 }
741
742 static void dict_expand(dict_t*h, int newlen)
743 {
744     assert(h->hashsize < newlen);
745     dictentry_t**newslots = (dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*newlen);
746     int t; 
747     for(t=0;t<h->hashsize;t++) {
748         dictentry_t*e = h->slots[t];
749         while(e) {
750             dictentry_t*next = e->next;
751             unsigned int newhash = e->hash%newlen;
752             e->next = newslots[newhash];
753             newslots[newhash] = e;
754             e = next;
755         }
756     }
757     if(h->slots)
758         rfx_free(h->slots);
759     h->slots = newslots;
760     h->hashsize = newlen;
761 }
762
763 dictentry_t* dict_put(dict_t*h, const void*key, void* data)
764 {
765     unsigned int hash = h->key_type->hash(key);
766     dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
767     unsigned int hash2 = hash % h->hashsize;
768     
769     e->key = h->key_type->dup(key);
770     e->hash = hash; //for resizing
771     e->next = h->slots[hash2];
772     e->data = data;
773     h->slots[hash2] = e;
774     h->num++;
775     return e;
776 }
777 void dict_put2(dict_t*h, const char*s, void*data) 
778 {
779     assert(h->key_type == &charptr_type);
780     dict_put(h, s, data);
781 }
782 void dict_dump(dict_t*h, FILE*fi, const char*prefix)
783 {
784     int t;
785     for(t=0;t<h->hashsize;t++) {
786         dictentry_t*e = h->slots[t];
787         while(e) {
788             if(h->key_type!=&charptr_type) {
789                 fprintf(fi, "%s%08x=%08x\n", prefix, e->key, e->data);
790             } else {
791                 fprintf(fi, "%s%s=%08x\n", prefix, e->key, e->data);
792             }
793             e = e->next;
794         }
795     }
796 }
797
798 int dict_count(dict_t*h)
799 {
800     return h->num;
801 }
802
803 void* dict_lookup(dict_t*h, const void*key)
804 {
805     if(!h->num)
806         return 0;
807     
808     unsigned int ohash = h->key_type->hash(key);
809     unsigned int hash = ohash % h->hashsize;
810
811     /* check first entry for match */
812     dictentry_t*e = h->slots[hash];
813     if(e && h->key_type->equals(e->key, key)) {
814         return e->data;
815     } else if(e) {
816         e = e->next;
817     }
818
819     /* if dict is 2/3 filled, double the size. Do
820        this the first time we have to actually iterate
821        through a slot to find our data */
822     if(e && h->num*3 >= h->hashsize*2) {
823         int newsize = h->hashsize;
824         while(h->num*3 >= newsize*2) {
825             newsize = newsize<15?15:(newsize+1)*2-1;
826         }
827         dict_expand(h, newsize);
828         hash = ohash % h->hashsize;
829         e = h->slots[hash];
830     }
831
832     /* check subsequent entries for a match */
833     while(e) {
834         if(h->key_type->equals(e->key, key)) {
835             return e->data;
836         }
837         e = e->next;
838     }
839     return 0;
840 }
841 char dict_del(dict_t*h, const void*key)
842 {
843     if(!h->num)
844         return 0;
845     unsigned int hash = h->key_type->hash(key) % h->hashsize;
846     dictentry_t*head = h->slots[hash];
847     dictentry_t*e = head, *prev=0;
848     while(e) {
849         if(h->key_type->equals(e->key, key)) {
850             dictentry_t*next = e->next;
851             rfx_free((void*)e->key);
852             memset(e, 0, sizeof(dictentry_t));
853             rfx_free(e);
854             if(e == head) {
855                 h->slots[hash] = 0;
856             } else {
857                 assert(prev);
858                 prev->next = next;
859             }
860             h->num--;
861             return 1;
862         }
863         prev = e;
864         e = e->next;
865     }
866     return 0;
867 }
868
869 dictentry_t* dict_get_slot(dict_t*h, const void*key)
870 {
871     if(!h->num)
872         return 0;
873     unsigned int ohash = h->key_type->hash(key);
874     unsigned int hash = ohash % h->hashsize;
875     return h->slots[hash];
876 }
877
878 void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const void*key, void*val), void*data)
879 {
880     int t;
881     for(t=0;t<h->hashsize;t++) {
882         dictentry_t*e = h->slots[t];
883         while(e) {
884             dictentry_t*next = e->next;
885             if(runFunction) {
886                 runFunction(data, e->key, e->data);
887             }
888             e = e->next;
889         }
890     }
891 }
892 void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
893 {
894     int t;
895     for(t=0;t<h->hashsize;t++) {
896         dictentry_t*e = h->slots[t];
897         while(e) {
898             dictentry_t*next = e->next;
899             if(runFunction) {
900                 runFunction(e->data);
901             }
902             e = e->next;
903         }
904     }
905 }
906
907 void dict_free_all(dict_t*h, void (*freeFunction)(void*))
908 {
909     int t;
910     for(t=0;t<h->hashsize;t++) {
911         dictentry_t*e = h->slots[t];
912         while(e) {
913             dictentry_t*next = e->next;
914             h->key_type->free(e->key);
915             if(freeFunction) {
916                 freeFunction(e->data);
917             }
918             memset(e, 0, sizeof(dictentry_t));
919             rfx_free(e);
920             e = next;
921         }
922         h->slots[t]=0;
923     }
924     rfx_free(h->slots);
925     memset(h, 0, sizeof(dict_t));
926 }
927
928 void dict_clear(dict_t*h) 
929 {
930     dict_free_all(h, 0);
931 }
932
933 void dict_destroy(dict_t*dict)
934 {
935     dict_clear(dict);
936     rfx_free(dict);
937 }
938
939 // ------------------------------- map_t --------------------------------------
940
941 typedef struct _map_internal_t
942 {
943     dict_t d;
944 } map_internal_t;
945
946 void map_init(map_t*map)
947 {
948     map_internal_t*m;
949     map->internal = (map_internal_t*)rfx_calloc(sizeof(map_internal_t));
950     m = (map_internal_t*)map->internal;
951     dict_init(&m->d, INITIAL_SIZE);
952 }
953 void map_put(map_t*map, string_t t1, string_t t2)
954 {
955     map_internal_t*m = (map_internal_t*)map->internal;
956     string_t s;
957     char* s1 = string_cstr(&t1);
958     dict_put2(&m->d, s1, (void*)string_cstr(&t2));
959     rfx_free(s1);
960 }
961 const char* map_lookup(map_t*map, const char*name)
962 {
963     map_internal_t*m = (map_internal_t*)map->internal;
964     const char*value = dict_lookup(&m->d, name);
965     return value;
966 }
967 static void freestring(void*data)
968 {
969     rfx_free(data);
970 }
971 static void dumpmapentry(void*data, const void*key, void*value)
972 {
973     FILE*fi = (FILE*)data;
974     fprintf(fi, "%s=%s\n", key, (char*)value);
975 }
976 void map_dump(map_t*map, FILE*fi, const char*prefix)
977 {
978     int t;
979     map_internal_t*m = (map_internal_t*)map->internal;
980     dict_foreach_keyvalue(&m->d, dumpmapentry, fi);
981 }
982 void map_clear(map_t*map)
983 {
984     map_internal_t*m = (map_internal_t*)map->internal;
985     dict_free_all(&m->d, freestring);
986     rfx_free(m);
987 }
988 void map_destroy(map_t*map)
989 {
990     map_clear(map);
991     rfx_free(map);
992 }
993
994 // ------------------------------- array_t --------------------------------------
995
996 array_t* array_new() {
997     array_t*d = malloc(sizeof(array_t));
998     memset(d, 0, sizeof(array_t));
999     d->entry2pos = dict_new();
1000     return d;
1001 }
1002 array_t* array_new2(type_t*type) {
1003     array_t*d = malloc(sizeof(array_t));
1004     memset(d, 0, sizeof(array_t));
1005     d->entry2pos = dict_new2(type);
1006     return d;
1007 }
1008 void*array_getkey(array_t*array, int nr) {
1009     if(nr > array->num || nr<0) {
1010         printf("error: reference to element %d in array[%d]\n", nr, array->num);
1011         *(int*)0 = 0xdead;
1012         return 0;
1013     }
1014     return array->d[nr].name;
1015 }
1016 void*array_getvalue(array_t*array, int nr) {
1017     if(nr > array->num || nr<0) {
1018         printf("error: reference to element %d in array[%d]\n", nr, array->num);
1019         *(int*)0 = 0xdead;
1020         return 0;
1021     }
1022     return array->d[nr].data;
1023 }
1024 int array_append(array_t*array, const void*name, void*data) {
1025     while(array->size <= array->num) {
1026         array->size += 64;
1027         if(!array->d) {
1028             array->d = malloc(sizeof(array_entry_t)*array->size);
1029         } else {
1030             array->d = realloc(array->d, sizeof(array_entry_t)*array->size);
1031         }
1032     }
1033
1034     dictentry_t*e = dict_put(array->entry2pos, name, (void*)(ptroff_t)(array->num+1));
1035
1036     if(name) {
1037         array->d[array->num].name = e->key;
1038     } else {
1039         array->d[array->num].name = 0;
1040     }
1041     array->d[array->num].data = (void*)data;
1042     return array->num++;
1043 }
1044 int array_find(array_t*array, const void*name)
1045 {
1046     int pos = (int)(ptroff_t)dict_lookup(array->entry2pos, name);
1047     return pos-1;
1048 }
1049 int array_find2(array_t*array, const void*name, void*data)
1050 {
1051     dict_t*h= array->entry2pos;
1052     dictentry_t*e = dict_get_slot(array->entry2pos, name);
1053
1054     while(e) {
1055         int index = ((int)(ptroff_t)e->data) - 1;
1056         if(h->key_type->equals(e->key, name) && array->d[index].data == data) {
1057             return index;
1058         }
1059         e = e->next;
1060     }
1061     return -1;
1062 }
1063 int array_update(array_t*array, const void*name, void*data) {
1064     int pos = array_find(array, name);
1065     if(pos>=0) {
1066         array->d[pos].data = data;
1067         return pos;
1068     }
1069     return array_append(array, name, data);
1070 }
1071 int array_append_if_new(array_t*array, const void*name, void*data) {
1072     int pos = array_find(array, name);
1073     if(pos>=0)
1074         return pos;
1075     return array_append(array, name, data);
1076 }
1077 void array_free(array_t*array) {
1078     dict_destroy(array->entry2pos);
1079     if(array->d) {
1080         free(array->d);array->d = 0;
1081     }
1082     free(array);
1083 }
1084
1085 // ------------------------------- list_t --------------------------------------
1086
1087 struct _commonlist;
1088 typedef struct _listinfo {
1089     int size;
1090     struct _commonlist*last;
1091 } listinfo_t;
1092
1093 typedef struct _commonlist {
1094     void*entry;
1095     struct _commonlist*next;
1096     listinfo_t info[0];
1097 } commonlist_t;
1098
1099 int list_length_(void*_list)
1100 {
1101     commonlist_t*l = (commonlist_t*)_list;
1102     if(!l)
1103         return 0;
1104     return l->info[0].size;
1105 }
1106 void list_append_(void*_list, void*entry)
1107 {
1108     commonlist_t**list = (commonlist_t**)_list;
1109     commonlist_t* n = 0;
1110     if(!*list) {
1111         n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1112         *list = n;
1113         (*list)->info[0].size = 0;
1114     } else {
1115         n = malloc(sizeof(commonlist_t));
1116         (*list)->info[0].last->next = n;
1117     }
1118     n->next = 0;
1119     n->entry = entry;
1120     (*list)->info[0].last = n;
1121     (*list)->info[0].size++;
1122 }
1123 /* notice: prepending uses slighly more space than appending */
1124 void list_prepend_(void*_list, void*entry)
1125 {
1126     commonlist_t**list = (commonlist_t**)_list;
1127     commonlist_t* n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1128     int size = 0;
1129     commonlist_t* last = 0;
1130     if(*list) {
1131         last = (*list)->info[0].last;
1132         size = (*list)->info[0].size;
1133     }
1134     n->next = *list;
1135     n->entry = entry;
1136     *list = n;
1137     (*list)->info[0].last = last;
1138     (*list)->info[0].size = size+1;
1139 }
1140 void list_free_(void*_list) 
1141 {
1142     commonlist_t**list = (commonlist_t**)_list;
1143     commonlist_t*l = *list;
1144     while(l) {
1145         commonlist_t*next = l->next;
1146         free(l);
1147         l = next;
1148     }
1149     *list = 0;
1150 }
1151 void*list_clone_(void*_list) 
1152 {
1153     commonlist_t*l = *(commonlist_t**)_list;
1154
1155     void*dest = 0;
1156     while(l) {
1157         commonlist_t*next = l->next;
1158         list_append_(&dest, l->entry);
1159         l = next;
1160     }
1161     return dest;
1162
1163 }