55a4c06f8d50db3493a104658d5513d522afc444
[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         int v1 = (m->pos+63)&~63;
72         int v2 = m->len + m->len / 2;
73         m->len = v1>v2?v1:v2;
74         m->buffer = m->buffer?(char*)rfx_realloc(m->buffer,m->len):(char*)rfx_alloc(m->len);
75     }
76     assert(n+length <= m->len);
77     memcpy(&m->buffer[n], data, length);
78     if(null)
79         m->buffer[n + length] = 0;
80     return n;
81 }
82 int mem_put(mem_t*m,void*data, int length)
83 {
84     return mem_put_(m, data, length, 0);
85 }
86 int mem_putstring(mem_t*m,string_t str)
87 {
88     return mem_put_(m, str.str, str.len, 1);
89 }
90 int mem_get(mem_t*m, void*data, int length)
91 {
92     if(m->read_pos + length > m->pos) {
93         length = m->pos - m->read_pos;
94     }
95     memcpy(data, m->buffer+m->read_pos, length);
96     m->read_pos += length;
97     return length;
98 }
99
100 // ------------------------------- ringbuffer_t -------------------------------
101
102 typedef struct _ringbuffer_internal_t
103 {
104     unsigned char*buffer;
105     int readpos;
106     int writepos;
107     int buffersize;
108 } ringbuffer_internal_t;
109
110 void ringbuffer_init(ringbuffer_t*r)
111 {
112     ringbuffer_internal_t*i = (ringbuffer_internal_t*)rfx_calloc(sizeof(ringbuffer_internal_t)); 
113     memset(r, 0, sizeof(ringbuffer_t));
114     r->internal = i;
115     i->buffer = (unsigned char*)rfx_alloc(1024);
116     i->buffersize = 1024;
117 }
118 int ringbuffer_read(ringbuffer_t*r, void*buf, int len)
119 {
120     unsigned char* data = (unsigned char*)buf;
121     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
122     if(r->available < len)
123         len = r->available;
124     if(!len)
125         return 0;
126     if(i->readpos + len > i->buffersize) {
127         int read1 = i->buffersize-i->readpos;
128         memcpy(data, &i->buffer[i->readpos], read1);
129         memcpy(&data[read1], &i->buffer[0], len - read1);
130         i->readpos = len - read1;
131     } else {
132         memcpy(data, &i->buffer[i->readpos], len);
133         i->readpos += len;
134         i->readpos %= i->buffersize;
135     }
136     r->available -= len;
137     return len;
138 }
139 void ringbuffer_put(ringbuffer_t*r, void*buf, int len)
140 {
141     unsigned char* data = (unsigned char*)buf;
142     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
143     
144     if(i->buffersize - r->available < len)
145     {
146         unsigned char* buf2;
147         int newbuffersize = i->buffersize;
148         int oldavailable = r->available;
149         newbuffersize*=3;newbuffersize/=2; /*grow at least by 50% each time */
150
151         if(newbuffersize < r->available + len)
152             newbuffersize = r->available + len + 1024;
153
154         buf2 = (unsigned char*)rfx_alloc(newbuffersize);
155         ringbuffer_read(r, buf2, r->available);
156         rfx_free(i->buffer);
157         i->buffer = buf2;
158         i->buffersize = newbuffersize;
159         i->readpos = 0;
160         i->writepos = oldavailable;
161         r->available = oldavailable;
162     }
163     if(i->writepos + len > i->buffersize) {
164         int read1 = i->buffersize-i->writepos;
165         memcpy(&i->buffer[i->writepos], data, read1);
166         memcpy(&i->buffer[0], &data[read1], len - read1);
167         i->writepos = len - read1;
168     } else {
169         memcpy(&i->buffer[i->writepos], data, len);
170         i->writepos += len;
171         i->writepos %= i->buffersize;
172     }
173     r->available += len;
174 }
175 void ringbuffer_clear(ringbuffer_t*r)
176 {
177     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
178     rfx_free(i->buffer);i->buffer = 0;
179     rfx_free(i);
180 }
181
182 // ------------------------------- heap_t -------------------------------
183
184 void heap_init(heap_t*h,int n,int elem_size, int(*compare)(const void *, const void *))
185 {
186     memset(h, 0, sizeof(heap_t));
187     h->max_size = n;
188     h->size = 0;
189     h->elem_size = elem_size;
190     h->compare = compare;
191     h->elements = (void**)rfx_calloc(n*sizeof(void*));
192     h->data = (char*)rfx_calloc(h->max_size*h->elem_size);
193 }
194 void heap_clear(heap_t*h)
195 {
196     rfx_free(h->elements);
197     rfx_free(h->data);
198 }
199
200 #define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))>0)
201
202 static void up(heap_t*h, int node)
203 {
204     void*node_p = h->elements[node];
205     int parent = node;
206     do {
207         node = parent;
208         if(!node) break;
209         parent = (node-1)/2;
210         h->elements[node] = h->elements[parent];
211     } while(HEAP_NODE_SMALLER(h,h->elements[parent], node_p));
212
213     h->elements[node] = node_p;
214 }
215 static void down(heap_t*h, int node)
216 {
217     void*node_p = h->elements[node];
218     int child = node;
219     do {
220         node = child;
221
222         /* determine new child's position */
223         child = node<<1|1;
224         if(child >= h->size) 
225             break;
226         if(child+1 < h->size && HEAP_NODE_SMALLER(h,h->elements[child],h->elements[child+1])) // search for bigger child
227             child++;
228
229         h->elements[node] = h->elements[child];
230     } while(HEAP_NODE_SMALLER(h,node_p, h->elements[child]));
231     
232     h->elements[node] = node_p;
233 }
234 void heap_put(heap_t*h, void*e) 
235 {
236     int pos = h->size++;
237     memcpy(&h->data[pos*h->elem_size],e,h->elem_size);
238     h->elements[pos] = &h->data[pos];
239     up(h, pos);
240 }
241 int heap_size(heap_t*h)
242 {
243     return h->size;
244 }
245 void* heap_max(heap_t*h)
246 {
247     return h->elements[0];
248 }
249 void* heap_chopmax(heap_t*h)
250 {
251     void*p = h->elements[0];
252     h->elements[0] = h->elements[--h->size];
253     down(h,0);
254     return p;
255 }
256 void heap_dump(heap_t*h, FILE*fi)
257 {
258     int t;
259     for(t=0;t<h->size;t++) {
260         int s;
261         for(s=0;s<=t;s=(s+1)*2-1) {
262             if(s==t) fprintf(fi,"\n");
263         }
264         //fprintf(fi,"%d ", h->elements[t]->x); //?
265     }
266 }
267 void** heap_flatten(heap_t*h)
268 {
269     void**nodes = (void**)rfx_alloc(h->size*sizeof(void*));
270     void**p = nodes;
271    
272     while(h->size) {
273         /*printf("Heap Size: %d\n", h->size);
274         heap_print(stdout, h);
275         printf("\n");*/
276         *p++ = heap_chopmax(h);
277     }
278     return nodes;
279 }
280
281 // ------------------------------- trie --------------------------------------
282
283 void trie_put(trie_t**t, unsigned const char*id)
284 {
285     if(!*t) {
286         (*t) = rfx_calloc(sizeof(trie_t));
287         (*t)->rest = (unsigned char*)strdup(id);
288         return;
289     } 
290     if((*t)->rest && (*t)->rest[0]) {
291         // shift whatever's currently in here one node down
292         trie_put(&(*t)->row[(*t)->rest[0]], (*t)->rest+1);
293         (*t)->rest = 0;
294     }
295     if(id[0]) {
296         trie_put(&(*t)->row[id[0]], id+1);
297     } else {
298         (*t)->rest = "";
299     }
300 }
301
302 int trie_lookup(trie_t*t, unsigned const char*id)
303 {
304     while(t) {
305         if(t->rest && !strcmp(t->rest, id))
306             return 1;
307         t = t->row[id[0]];
308         if(!*id) 
309             return 0;
310         id++;
311     }
312     return 0;
313 }
314
315 // ------------------------------- crc32 --------------------------------------
316 static unsigned int*crc32 = 0;
317 static void crc32_init(void)
318 {
319     int t;
320     if(crc32) 
321         return;
322     crc32= (unsigned int*)rfx_alloc(sizeof(unsigned int)*256);
323     for(t=0; t<256; t++) {
324         unsigned int c = t;
325         int s;
326         for (s = 0; s < 8; s++) {
327           c = (0xedb88320L*(c&1)) ^ (c >> 1);
328         }
329         crc32[t] = c;
330     }
331 }
332 // ------------------------------- string_t -----------------------------------
333
334 void string_set2(string_t*str, const char*text, int len)
335 {
336     str->len = len;
337     str->str = text;
338 }
339 void string_set(string_t*str, const char*text)
340 {
341     if(text) {
342         str->len = strlen(text);
343     } else {
344         str->len = 0;
345     }
346     str->str = text;
347 }
348 string_t string_new(const char*text, int len)
349 {
350     string_t s;
351     s.len = len;
352     s.str = text;
353     return s;
354 }
355 string_t string_new2(const char*text)
356 {
357     string_t s;
358     if(text) {
359         s.len = strlen(text);
360     } else {
361         s.len = 0;
362     }
363     s.str = text;
364     return s;
365 }
366 string_t* string_new3(const char*text, int len)
367 {
368     if(!text) {
369         string_t*s = malloc(sizeof(string_t));
370         s->len = 0;
371         s->str = 0;
372         return s;
373     } else {
374         string_t*s = malloc(sizeof(string_t)+len+1);
375         s->len = len;
376         s->str = (const char*)(s+1);
377         memcpy((char*)s->str, text, len);
378         ((char*)s->str)[len]=0;
379         return s;
380     }
381 }
382 string_t* string_new4(const char*text)
383 {
384     int l = strlen(text);
385     return string_new3(text, l);
386 }
387
388 void string_free(string_t*s)
389 {
390     if(!s) 
391         return;
392     s->len = 0;
393     if((string_t*)(s->str) == s+1) {
394         s->str = 0;
395         rfx_free(s);
396     } else {
397         rfx_free((char*)(s->str));
398         s->str = 0;
399         rfx_free(s);
400     }
401 }
402 char* string_cstr(string_t*str)
403 {
404     return strdup_n(str->str, str->len);
405 }
406 char* string_escape(string_t*str)
407 {
408     int t;
409     int len = 0;
410     for(t=0;t<str->len;t++) {
411         if(str->str[t]<0x20)
412             len+=3;
413         else
414             len++;
415     }
416     char*s = malloc(len+1);
417     char*p=s;
418     for(t=0;t<str->len;t++) {
419         if(str->str[t]<0x20) {
420             *p++ ='\\';
421             unsigned char c = str->str[t];
422             *p++ = "0123456789abcdef"[c>>4];
423             *p++ = "0123456789abcdef"[c&0x0f];
424         } else {
425             *p++ = str->str[t];
426         }
427     }
428     *p++ = 0;
429     assert(p == &s[len+1]);
430     return s;
431 }
432
433 unsigned int crc32_add_byte(unsigned int checksum, unsigned char b) 
434 {
435     if(!crc32)
436         crc32_init();
437     return checksum>>8 ^ crc32[(b^checksum)&0xff];
438 }
439 unsigned int crc32_add_string(unsigned int checksum, const char*s)
440 {
441     if(!crc32)
442         crc32_init();
443     if(!s)
444         return checksum;
445     while(*s) {
446         checksum = checksum>>8 ^ crc32[(*s^checksum)&0xff];
447         s++;
448     }
449     return checksum;
450 }
451
452 unsigned int string_hash(const string_t*str)
453 {
454     int t;
455     unsigned int checksum = 0;
456     if(!crc32)
457         crc32_init();
458     for(t=0;t<str->len;t++) {
459         checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff];
460     }
461     return checksum;
462 }
463 unsigned int string_hash2(const char*str)
464 {
465     unsigned int checksum = 0;
466     const char*p = str;
467     if(!crc32)
468         crc32_init();
469     while(*p) {
470         checksum = checksum>>8 ^ crc32[(*p^checksum)&0xff];
471         p++;
472     }
473     return checksum;
474 }
475 unsigned int string_hash3(const char*str, int len)
476 {
477     string_t s;
478     s.str = str;
479     s.len = len;
480     return string_hash(&s);
481 }
482 void string_dup2(string_t*str, const char*text, int len)
483 {
484     str->len = len;
485     str->str = strdup_n(text, len);
486 }
487 void string_dup(string_t*str, const char*text)
488 {
489     str->len = strlen(text);
490     str->str = strdup(text);
491 }
492 int string_equals(string_t*str, const char*text)
493 {
494     int l = strlen(text);
495     if(str->len == l && !memcmp(str->str, text, l))
496         return 1;
497     return 0;
498 }
499 int string_equals2(string_t*str, string_t*str2)
500 {
501     if(str->len == str2->len && !memcmp(str->str, str2->str, str->len))
502         return 1;
503     return 0;
504 }
505
506 // ------------------------------- stringarray_t ------------------------------
507
508 typedef struct _stringlist {
509     int index;
510     struct _stringlist*next;
511 } stringlist_t;
512
513 typedef struct _stringarray_internal_t
514 {
515     mem_t pos;
516     stringlist_t**hash;
517     int num;
518     int hashsize;
519 } stringarray_internal_t;
520
521 void stringarray_init(stringarray_t*sa, int hashsize)
522 {
523     stringarray_internal_t*s;
524     int t;
525     sa->internal = (stringarray_internal_t*)rfx_calloc(sizeof(stringarray_internal_t)); 
526     s = (stringarray_internal_t*)sa->internal;
527     mem_init(&s->pos);
528     s->hash = rfx_calloc(sizeof(stringlist_t*)*hashsize);
529     s->hashsize = hashsize;
530 }
531 void stringarray_put(stringarray_t*sa, string_t str)
532 {
533     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
534     int pos;
535     int hash = string_hash(&str) % s->hashsize;
536
537     char*ss = string_cstr(&str);
538     mem_put(&s->pos, &ss, sizeof(char*));
539
540     stringlist_t*l = rfx_alloc(sizeof(stringlist_t));
541     l->index = s->num;
542     l->next = s->hash[hash];
543     s->hash[hash] = l;
544
545     s->num++;
546 }
547 char* stringarray_at(stringarray_t*sa, int pos)
548 {
549     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
550     char*p;
551     if(pos<0 || pos>=s->num)
552         return 0;
553     p = *(char**)&s->pos.buffer[pos*sizeof(char*)];
554     if(p<0)
555         return 0;
556     return p;
557 }
558 string_t stringarray_at2(stringarray_t*sa, int pos)
559 {
560     string_t s;
561     s.str = stringarray_at(sa, pos);
562     s.len = s.str?strlen(s.str):0;
563     return s;
564 }
565 static stringlist_t* stringlist_del(stringarray_t*sa, stringlist_t*l, int index)
566 {
567     stringlist_t*ll = l;
568     stringlist_t*old = l;
569     while(l) {
570         if(index==l->index) {
571             old->next = l->next;
572             memset(l, 0, sizeof(stringlist_t));
573             rfx_free(l);
574             if(old==l)
575                 return 0;
576             else
577                 return ll;
578         }
579         old = l;
580         l = l->next;
581     }
582     fprintf(stderr, "Internal error: did not find string %d in hash\n", index);
583     return ll;
584 }
585
586 void stringarray_del(stringarray_t*sa, int pos)
587 {
588     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
589     string_t str = stringarray_at2(sa, pos);
590     int hash = string_hash(&str) % s->hashsize;
591     s->hash[hash] = stringlist_del(sa, s->hash[hash], pos);
592     *(char**)&s->pos.buffer[pos*sizeof(char*)] = 0;
593 }
594 int stringarray_find(stringarray_t*sa, string_t* str)
595 {
596     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
597     int hash = string_hash(str) % s->hashsize;
598     int t;
599     stringlist_t*l = s->hash[hash];
600     //TODO: statistics
601     while(l) {
602         string_t s = stringarray_at2(sa, l->index);
603         if(string_equals2(str, &s)) {
604             return l->index;
605         }
606         l = l->next;
607     }
608     return -1;
609 }
610 void stringarray_clear(stringarray_t*sa)
611 {
612     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
613     mem_clear(&s->pos);
614     int t;
615     for(t=0;t<s->hashsize;t++) {
616         stringlist_t*l = s->hash[t];
617         while(l) {
618             stringlist_t*next = l->next;
619             memset(l, 0, sizeof(stringlist_t));
620             rfx_free(l);
621             l = next;
622         }
623     }
624     rfx_free(s->hash);s->hash=0;
625     rfx_free(s);
626 }
627 void stringarray_destroy(stringarray_t*sa)
628 {
629     stringarray_clear(sa);
630     rfx_free(sa);
631 }
632
633 // ------------------------------- type_t -------------------------------
634
635 char ptr_equals(const void*o1, const void*o2) 
636 {
637     return o1==o2;
638 }
639 unsigned int ptr_hash(const void*o) 
640 {
641     return string_hash3((const char*)&o, sizeof(o));
642 }
643 void* ptr_dup(const void*o) 
644 {
645     return (void*)o;
646 }
647 void ptr_free(void*o) 
648 {
649     return;
650 }
651
652 char charptr_equals(const void*o1, const void*o2) 
653 {
654     if(!o1 || !o2)
655         return o1==o2;
656     return !strcmp(o1,o2);
657 }
658 unsigned int charptr_hash(const void*o) 
659 {
660     if(!o)
661         return 0;
662     return string_hash2(o);
663 }
664 void* charptr_dup(const void*o) 
665 {
666     if(!o)
667         return 0;
668     return strdup(o);
669 }
670 void charptr_free(void*o) 
671 {
672     if(o) {
673         rfx_free(o);
674     }
675 }
676
677 char stringstruct_equals(const void*o1, const void*o2) 
678 {
679     if(!o1 || !o2) 
680         return o1==o2;
681     string_t*s1 = (string_t*)o1;
682     string_t*s2 = (string_t*)o2;
683     int l = s1->len<s2->len?s1->len:s2->len;
684     int r = memcmp(s1->str, s2->str, l);
685     if(r)
686         return 0;
687     else
688         return s1->len==s2->len;
689 }
690 unsigned int stringstruct_hash(const void*o) 
691 {
692     if(!o) return 0;
693     return string_hash(o);
694 }
695 string_t*string_dup3(string_t*o)
696 {
697     if(!o) return 0;
698     if(!o->str) {
699         string_t*s = malloc(sizeof(string_t));
700         s->str=0;
701         s->len=0;
702         return s;
703     }
704     string_t*s = rfx_alloc(sizeof(string_t)+o->len+1);
705     s->len = o->len;
706     s->str = (const char*)(s+1);
707     memcpy((char*)s->str, o->str, s->len);
708     ((char*)s->str)[s->len]=0;
709     return s;
710 }
711 void stringstruct_free(void*o) 
712 {
713     if(o)
714         string_free(o);
715 }
716
717 type_t ptr_type = {
718     equals: ptr_equals,
719     hash: ptr_hash,
720     dup: ptr_dup,
721     free: ptr_free,
722 };
723
724 type_t charptr_type = {
725     equals: charptr_equals,
726     hash: charptr_hash,
727     dup: charptr_dup,
728     free: charptr_free,
729 };
730
731 type_t stringstruct_type = {
732     equals: stringstruct_equals,
733     hash: stringstruct_hash,
734     dup: (dup_func)string_dup3,
735     free: stringstruct_free,
736 };
737
738 // ------------------------------- dictionary_t -------------------------------
739
740 #define INITIAL_SIZE 1
741
742 static int max(int x, int y) {
743     return x>y?x:y;
744 }
745
746 dict_t*dict_new()
747 {
748     dict_t*d = rfx_alloc(sizeof(dict_t));
749     dict_init(d, INITIAL_SIZE);
750     return d;
751 }
752 dict_t*dict_new2(type_t*t)
753 {
754     dict_t*d = rfx_alloc(sizeof(dict_t));
755     dict_init(d, INITIAL_SIZE);
756     d->key_type = t;
757     return d;
758 }
759 void dict_init(dict_t*h, int size) 
760 {
761     memset(h, 0, sizeof(dict_t));
762     h->hashsize = size;
763     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
764     h->num = 0;
765     h->key_type = &charptr_type;
766 }
767
768 dict_t*dict_clone(dict_t*o)
769 {
770     dict_t*h = rfx_alloc(sizeof(dict_t));
771     memcpy(h, o, sizeof(dict_t));
772     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
773     int t;
774     for(t=0;t<o->hashsize;t++) {
775         dictentry_t*e = o->slots[t];
776         while(e) {
777             dictentry_t*n = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
778             memcpy(n, e, sizeof(dictentry_t));
779             n->key = h->key_type->dup(e->key);
780             n->data = e->data;
781             n->next = h->slots[t];
782             h->slots[t] = n;
783             e = e->next;
784         }
785     }
786     return h;
787 }
788
789 static void dict_expand(dict_t*h, int newlen)
790 {
791     assert(h->hashsize < newlen);
792     dictentry_t**newslots = (dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*newlen);
793     int t; 
794     for(t=0;t<h->hashsize;t++) {
795         dictentry_t*e = h->slots[t];
796         while(e) {
797             dictentry_t*next = e->next;
798             unsigned int newhash = e->hash%newlen;
799             e->next = newslots[newhash];
800             newslots[newhash] = e;
801             e = next;
802         }
803     }
804     if(h->slots)
805         rfx_free(h->slots);
806     h->slots = newslots;
807     h->hashsize = newlen;
808 }
809
810 dictentry_t* dict_put(dict_t*h, const void*key, void* data)
811 {
812     unsigned int hash = h->key_type->hash(key);
813     dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
814     unsigned int hash2 = hash % h->hashsize;
815     
816     e->key = h->key_type->dup(key);
817     e->hash = hash; //for resizing
818     e->next = h->slots[hash2];
819     e->data = data;
820     h->slots[hash2] = e;
821     h->num++;
822     return e;
823 }
824 void dict_put2(dict_t*h, const char*s, void*data) 
825 {
826     assert(h->key_type == &charptr_type);
827     dict_put(h, s, data);
828 }
829 void dict_dump(dict_t*h, FILE*fi, const char*prefix)
830 {
831     int t;
832     for(t=0;t<h->hashsize;t++) {
833         dictentry_t*e = h->slots[t];
834         while(e) {
835             if(h->key_type!=&charptr_type) {
836                 fprintf(fi, "%s%08x=%08x\n", prefix, e->key, e->data);
837             } else {
838                 fprintf(fi, "%s%s=%08x\n", prefix, e->key, e->data);
839             }
840             e = e->next;
841         }
842     }
843 }
844
845 int dict_count(dict_t*h)
846 {
847     return h->num;
848 }
849
850 static inline dictentry_t* dict_do_lookup(dict_t*h, const void*key)
851 {
852     if(!h->num) {
853         return 0;
854     }
855     
856     unsigned int ohash = h->key_type->hash(key);
857     unsigned int hash = ohash % h->hashsize;
858
859     /* check first entry for match */
860     dictentry_t*e = h->slots[hash];
861     if(e && h->key_type->equals(e->key, key)) {
862         return e;
863     } else if(e) {
864         e = e->next;
865     }
866
867     /* if dict is 2/3 filled, double the size. Do
868        this the first time we have to actually iterate
869        through a slot to find our data */
870     if(e && h->num*3 >= h->hashsize*2) {
871         int newsize = h->hashsize;
872         while(h->num*3 >= newsize*2) {
873             newsize = newsize<15?15:(newsize+1)*2-1;
874         }
875         dict_expand(h, newsize);
876         hash = ohash % h->hashsize;
877         e = h->slots[hash];
878         if(e && h->key_type->equals(e->key, key)) {
879             // omit move to front
880             return e;
881         } else if(e) {
882             e = e->next;
883         }
884     }
885
886     /* check subsequent entries for a match */
887     dictentry_t*last = h->slots[hash];
888     while(e) {
889         if(h->key_type->equals(e->key, key)) {
890             /* move to front- makes a difference of about 10% in most applications */
891             last->next = e->next;
892             e->next = h->slots[hash];
893             h->slots[hash] = e;
894             return e;
895         }
896         last=e;
897         e = e->next;
898     }
899     return 0;
900 }
901 void* dict_lookup(dict_t*h, const void*key)
902 {
903     dictentry_t*e = dict_do_lookup(h, key);
904     if(e)
905         return e->data;
906     return 0;
907 }
908 char dict_contains(dict_t*h, const void*key)
909 {
910     dictentry_t*e = dict_do_lookup(h, key);
911     return !!e;
912 }
913
914 char dict_del(dict_t*h, const void*key)
915 {
916     if(!h->num)
917         return 0;
918     unsigned int hash = h->key_type->hash(key) % h->hashsize;
919     dictentry_t*head = h->slots[hash];
920     dictentry_t*e = head, *prev=0;
921     while(e) {
922         if(h->key_type->equals(e->key, key)) {
923             dictentry_t*next = e->next;
924             rfx_free((void*)e->key);
925             memset(e, 0, sizeof(dictentry_t));
926             rfx_free(e);
927             if(e == head) {
928                 h->slots[hash] = 0;
929             } else {
930                 assert(prev);
931                 prev->next = next;
932             }
933             h->num--;
934             return 1;
935         }
936         prev = e;
937         e = e->next;
938     }
939     return 0;
940 }
941
942 dictentry_t* dict_get_slot(dict_t*h, const void*key)
943 {
944     if(!h->num)
945         return 0;
946     unsigned int ohash = h->key_type->hash(key);
947     unsigned int hash = ohash % h->hashsize;
948     return h->slots[hash];
949 }
950
951 void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const void*key, void*val), void*data)
952 {
953     int t;
954     for(t=0;t<h->hashsize;t++) {
955         dictentry_t*e = h->slots[t];
956         while(e) {
957             dictentry_t*next = e->next;
958             if(runFunction) {
959                 runFunction(data, e->key, e->data);
960             }
961             e = e->next;
962         }
963     }
964 }
965 void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
966 {
967     int t;
968     for(t=0;t<h->hashsize;t++) {
969         dictentry_t*e = h->slots[t];
970         while(e) {
971             dictentry_t*next = e->next;
972             if(runFunction) {
973                 runFunction(e->data);
974             }
975             e = e->next;
976         }
977     }
978 }
979
980 void dict_free_all(dict_t*h, char free_keys, void (*free_data_function)(void*))
981 {
982     int t;
983     for(t=0;t<h->hashsize;t++) {
984         dictentry_t*e = h->slots[t];
985         while(e) {
986             dictentry_t*next = e->next;
987             if(free_keys) {
988                 h->key_type->free(e->key);
989             }
990             if(free_data_function) {
991                 free_data_function(e->data);
992             }
993             memset(e, 0, sizeof(dictentry_t));
994             rfx_free(e);
995             e = next;
996         }
997         h->slots[t]=0;
998     }
999     rfx_free(h->slots);
1000     memset(h, 0, sizeof(dict_t));
1001 }
1002
1003 void dict_clear_shallow(dict_t*h) 
1004 {
1005     dict_free_all(h, 0, 0);
1006 }
1007
1008 void dict_clear(dict_t*h) 
1009 {
1010     dict_free_all(h, 1, 0);
1011 }
1012
1013 void dict_destroy_shallow(dict_t*dict)
1014 {
1015     dict_clear_shallow(dict);
1016     rfx_free(dict);
1017 }
1018
1019 void dict_destroy(dict_t*dict)
1020 {
1021     dict_clear(dict);
1022     rfx_free(dict);
1023 }
1024
1025 // ------------------------------- map_t --------------------------------------
1026
1027 typedef struct _map_internal_t
1028 {
1029     dict_t d;
1030 } map_internal_t;
1031
1032 void map_init(map_t*map)
1033 {
1034     map_internal_t*m;
1035     map->internal = (map_internal_t*)rfx_calloc(sizeof(map_internal_t));
1036     m = (map_internal_t*)map->internal;
1037     dict_init(&m->d, INITIAL_SIZE);
1038 }
1039 void map_put(map_t*map, string_t t1, string_t t2)
1040 {
1041     map_internal_t*m = (map_internal_t*)map->internal;
1042     string_t s;
1043     char* s1 = string_cstr(&t1);
1044     dict_put2(&m->d, s1, (void*)string_cstr(&t2));
1045     rfx_free(s1);
1046 }
1047 const char* map_lookup(map_t*map, const char*name)
1048 {
1049     map_internal_t*m = (map_internal_t*)map->internal;
1050     const char*value = dict_lookup(&m->d, name);
1051     return value;
1052 }
1053 static void freestring(void*data)
1054 {
1055     rfx_free(data);
1056 }
1057 static void dumpmapentry(void*data, const void*key, void*value)
1058 {
1059     FILE*fi = (FILE*)data;
1060     fprintf(fi, "%s=%s\n", key, (char*)value);
1061 }
1062 void map_dump(map_t*map, FILE*fi, const char*prefix)
1063 {
1064     int t;
1065     map_internal_t*m = (map_internal_t*)map->internal;
1066     dict_foreach_keyvalue(&m->d, dumpmapentry, fi);
1067 }
1068 void map_clear(map_t*map)
1069 {
1070     map_internal_t*m = (map_internal_t*)map->internal;
1071     dict_free_all(&m->d, 1, freestring);
1072     rfx_free(m);
1073 }
1074 void map_destroy(map_t*map)
1075 {
1076     map_clear(map);
1077     rfx_free(map);
1078 }
1079
1080 // ------------------------------- array_t --------------------------------------
1081
1082 array_t* array_new() {
1083     array_t*d = malloc(sizeof(array_t));
1084     memset(d, 0, sizeof(array_t));
1085     d->entry2pos = dict_new();
1086     return d;
1087 }
1088 array_t* array_new2(type_t*type) {
1089     array_t*d = malloc(sizeof(array_t));
1090     memset(d, 0, sizeof(array_t));
1091     d->entry2pos = dict_new2(type);
1092     return d;
1093 }
1094 void*array_getkey(array_t*array, int nr) {
1095     if(nr > array->num || nr<0) {
1096         printf("error: reference to element %d in array[%d]\n", nr, array->num);
1097         return 0;
1098     }
1099     return array->d[nr].name;
1100 }
1101 void*array_getvalue(array_t*array, int nr) {
1102     if(nr > array->num || nr<0) {
1103         printf("error: reference to element %d in array[%d]\n", nr, array->num);
1104         return 0;
1105     }
1106     return array->d[nr].data;
1107 }
1108 int array_append(array_t*array, const void*name, void*data) {
1109     while(array->size <= array->num) {
1110         array->size += 64;
1111         if(!array->d) {
1112             array->d = malloc(sizeof(array_entry_t)*array->size);
1113         } else {
1114             array->d = realloc(array->d, sizeof(array_entry_t)*array->size);
1115         }
1116     }
1117
1118     dictentry_t*e = dict_put(array->entry2pos, name, (void*)(ptroff_t)(array->num+1));
1119
1120     if(name) {
1121         array->d[array->num].name = e->key;
1122     } else {
1123         array->d[array->num].name = 0;
1124     }
1125     array->d[array->num].data = (void*)data;
1126     return array->num++;
1127 }
1128 int array_find(array_t*array, const void*name)
1129 {
1130     int pos = (int)(ptroff_t)dict_lookup(array->entry2pos, name);
1131     return pos-1;
1132 }
1133 int array_find2(array_t*array, const void*name, void*data)
1134 {
1135     dict_t*h= array->entry2pos;
1136     dictentry_t*e = dict_get_slot(array->entry2pos, name);
1137
1138     while(e) {
1139         int index = ((int)(ptroff_t)e->data) - 1;
1140         if(h->key_type->equals(e->key, name) && array->d[index].data == data) {
1141             return index;
1142         }
1143         e = e->next;
1144     }
1145     return -1;
1146 }
1147 int array_update(array_t*array, const void*name, void*data) {
1148     int pos = array_find(array, name);
1149     if(pos>=0) {
1150         array->d[pos].data = data;
1151         return pos;
1152     }
1153     return array_append(array, name, data);
1154 }
1155 int array_append_if_new(array_t*array, const void*name, void*data) {
1156     int pos = array_find(array, name);
1157     if(pos>=0)
1158         return pos;
1159     return array_append(array, name, data);
1160 }
1161 void array_free(array_t*array) {
1162     dict_destroy(array->entry2pos);
1163     if(array->d) {
1164         free(array->d);array->d = 0;
1165     }
1166     free(array);
1167 }
1168
1169 // ------------------------------- list_t --------------------------------------
1170
1171 struct _commonlist;
1172 typedef struct _listinfo {
1173     int size;
1174     struct _commonlist*last;
1175 } listinfo_t;
1176
1177 typedef struct _commonlist {
1178     void*entry;
1179     struct _commonlist*next;
1180     listinfo_t info[0];
1181 } commonlist_t;
1182
1183 int list_length_(void*_list)
1184 {
1185     commonlist_t*l = (commonlist_t*)_list;
1186     if(!l)
1187         return 0;
1188     return l->info[0].size;
1189 }
1190 void list_concat_(void*_l1, void*_l2)
1191 {
1192     commonlist_t**l1 = (commonlist_t**)_l1;
1193     commonlist_t**l2 = (commonlist_t**)_l2;
1194
1195     if(!*l1) {
1196         *l1 = *l2;
1197     } else if(*l2) {
1198         (*l1)->info[0].last->next = *l2;
1199         (*l1)->info[0].last = (*l2)->info[0].last;
1200         (*l1)->info[0].size += (*l2)->info[0].size;
1201     }
1202     *l2 = 0;
1203 }
1204 void list_append_(void*_list, void*entry)
1205 {
1206     commonlist_t**list = (commonlist_t**)_list;
1207     commonlist_t* n = 0;
1208     if(!*list) {
1209         n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1210         *list = n;
1211         (*list)->info[0].size = 0;
1212     } else {
1213         n = malloc(sizeof(commonlist_t));
1214         (*list)->info[0].last->next = n;
1215     }
1216     n->next = 0;
1217     n->entry = entry;
1218     (*list)->info[0].last = n;
1219     (*list)->info[0].size++;
1220 }
1221 /* notice: prepending uses slighly more space than appending */
1222 void list_prepend_(void*_list, void*entry)
1223 {
1224     commonlist_t**list = (commonlist_t**)_list;
1225     commonlist_t* n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1226     int size = 0;
1227     commonlist_t* last = 0;
1228     if(*list) {
1229         last = (*list)->info[0].last;
1230         size = (*list)->info[0].size;
1231     }
1232     n->next = *list;
1233     n->entry = entry;
1234     *list = n;
1235     (*list)->info[0].last = last;
1236     (*list)->info[0].size = size+1;
1237 }
1238 void list_free_(void*_list) 
1239 {
1240     commonlist_t**list = (commonlist_t**)_list;
1241     commonlist_t*l = *list;
1242     while(l) {
1243         commonlist_t*next = l->next;
1244         free(l);
1245         l = next;
1246     }
1247     *list = 0;
1248 }
1249 void list_deep_free_(void*_list)
1250 {
1251     commonlist_t**list = (commonlist_t**)_list;
1252     commonlist_t*l = *list;
1253     while(l) {
1254         commonlist_t*next = l->next;
1255         if(l->entry) {
1256             free(l->entry);l->entry=0;
1257         }
1258         free(l);
1259         l = next;
1260     }
1261     *list = 0;
1262 }
1263 void*list_clone_(void*_list) 
1264 {
1265     commonlist_t*l = *(commonlist_t**)_list;
1266
1267     void*dest = 0;
1268     while(l) {
1269         commonlist_t*next = l->next;
1270         list_append_(&dest, l->entry);
1271         l = next;
1272     }
1273     return dest;
1274
1275 }