added regexp helper struct
[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_do_lookup(dict_t*h, const void*key, void***match)
804 {
805     if(!h->num) {
806         *match = 0;
807         return;
808     }
809     
810     unsigned int ohash = h->key_type->hash(key);
811     unsigned int hash = ohash % h->hashsize;
812
813     /* check first entry for match */
814     dictentry_t*e = h->slots[hash];
815     if(e && h->key_type->equals(e->key, key)) {
816         *match = &e->data;
817         return;
818     } else if(e) {
819         e = e->next;
820     }
821
822     /* if dict is 2/3 filled, double the size. Do
823        this the first time we have to actually iterate
824        through a slot to find our data */
825     if(e && h->num*3 >= h->hashsize*2) {
826         int newsize = h->hashsize;
827         while(h->num*3 >= newsize*2) {
828             newsize = newsize<15?15:(newsize+1)*2-1;
829         }
830         dict_expand(h, newsize);
831         hash = ohash % h->hashsize;
832         e = h->slots[hash];
833     }
834
835     /* check subsequent entries for a match */
836     while(e) {
837         if(h->key_type->equals(e->key, key)) {
838             *match = &e->data;
839             return;
840         }
841         e = e->next;
842     }
843     *match = 0;
844 }
845 void* dict_lookup(dict_t*h, const void*key)
846 {
847     void**data = 0;
848     dict_do_lookup(h, key, &data);
849     if(data)
850         return *data;
851     return 0;
852 }
853 char dict_contains(dict_t*h, const void*key)
854 {
855     void**data = 0;
856     dict_do_lookup(h, key, &data);
857     return !!data;
858 }
859
860 char dict_del(dict_t*h, const void*key)
861 {
862     if(!h->num)
863         return 0;
864     unsigned int hash = h->key_type->hash(key) % h->hashsize;
865     dictentry_t*head = h->slots[hash];
866     dictentry_t*e = head, *prev=0;
867     while(e) {
868         if(h->key_type->equals(e->key, key)) {
869             dictentry_t*next = e->next;
870             rfx_free((void*)e->key);
871             memset(e, 0, sizeof(dictentry_t));
872             rfx_free(e);
873             if(e == head) {
874                 h->slots[hash] = 0;
875             } else {
876                 assert(prev);
877                 prev->next = next;
878             }
879             h->num--;
880             return 1;
881         }
882         prev = e;
883         e = e->next;
884     }
885     return 0;
886 }
887
888 dictentry_t* dict_get_slot(dict_t*h, const void*key)
889 {
890     if(!h->num)
891         return 0;
892     unsigned int ohash = h->key_type->hash(key);
893     unsigned int hash = ohash % h->hashsize;
894     return h->slots[hash];
895 }
896
897 void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const void*key, void*val), void*data)
898 {
899     int t;
900     for(t=0;t<h->hashsize;t++) {
901         dictentry_t*e = h->slots[t];
902         while(e) {
903             dictentry_t*next = e->next;
904             if(runFunction) {
905                 runFunction(data, e->key, e->data);
906             }
907             e = e->next;
908         }
909     }
910 }
911 void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
912 {
913     int t;
914     for(t=0;t<h->hashsize;t++) {
915         dictentry_t*e = h->slots[t];
916         while(e) {
917             dictentry_t*next = e->next;
918             if(runFunction) {
919                 runFunction(e->data);
920             }
921             e = e->next;
922         }
923     }
924 }
925
926 void dict_free_all(dict_t*h, void (*freeFunction)(void*))
927 {
928     int t;
929     for(t=0;t<h->hashsize;t++) {
930         dictentry_t*e = h->slots[t];
931         while(e) {
932             dictentry_t*next = e->next;
933             h->key_type->free(e->key);
934             if(freeFunction) {
935                 freeFunction(e->data);
936             }
937             memset(e, 0, sizeof(dictentry_t));
938             rfx_free(e);
939             e = next;
940         }
941         h->slots[t]=0;
942     }
943     rfx_free(h->slots);
944     memset(h, 0, sizeof(dict_t));
945 }
946
947 void dict_clear(dict_t*h) 
948 {
949     dict_free_all(h, 0);
950 }
951
952 void dict_destroy(dict_t*dict)
953 {
954     dict_clear(dict);
955     rfx_free(dict);
956 }
957
958 // ------------------------------- map_t --------------------------------------
959
960 typedef struct _map_internal_t
961 {
962     dict_t d;
963 } map_internal_t;
964
965 void map_init(map_t*map)
966 {
967     map_internal_t*m;
968     map->internal = (map_internal_t*)rfx_calloc(sizeof(map_internal_t));
969     m = (map_internal_t*)map->internal;
970     dict_init(&m->d, INITIAL_SIZE);
971 }
972 void map_put(map_t*map, string_t t1, string_t t2)
973 {
974     map_internal_t*m = (map_internal_t*)map->internal;
975     string_t s;
976     char* s1 = string_cstr(&t1);
977     dict_put2(&m->d, s1, (void*)string_cstr(&t2));
978     rfx_free(s1);
979 }
980 const char* map_lookup(map_t*map, const char*name)
981 {
982     map_internal_t*m = (map_internal_t*)map->internal;
983     const char*value = dict_lookup(&m->d, name);
984     return value;
985 }
986 static void freestring(void*data)
987 {
988     rfx_free(data);
989 }
990 static void dumpmapentry(void*data, const void*key, void*value)
991 {
992     FILE*fi = (FILE*)data;
993     fprintf(fi, "%s=%s\n", key, (char*)value);
994 }
995 void map_dump(map_t*map, FILE*fi, const char*prefix)
996 {
997     int t;
998     map_internal_t*m = (map_internal_t*)map->internal;
999     dict_foreach_keyvalue(&m->d, dumpmapentry, fi);
1000 }
1001 void map_clear(map_t*map)
1002 {
1003     map_internal_t*m = (map_internal_t*)map->internal;
1004     dict_free_all(&m->d, freestring);
1005     rfx_free(m);
1006 }
1007 void map_destroy(map_t*map)
1008 {
1009     map_clear(map);
1010     rfx_free(map);
1011 }
1012
1013 // ------------------------------- array_t --------------------------------------
1014
1015 array_t* array_new() {
1016     array_t*d = malloc(sizeof(array_t));
1017     memset(d, 0, sizeof(array_t));
1018     d->entry2pos = dict_new();
1019     return d;
1020 }
1021 array_t* array_new2(type_t*type) {
1022     array_t*d = malloc(sizeof(array_t));
1023     memset(d, 0, sizeof(array_t));
1024     d->entry2pos = dict_new2(type);
1025     return d;
1026 }
1027 void*array_getkey(array_t*array, int nr) {
1028     if(nr > array->num || nr<0) {
1029         printf("error: reference to element %d in array[%d]\n", nr, array->num);
1030         *(int*)0 = 0xdead;
1031         return 0;
1032     }
1033     return array->d[nr].name;
1034 }
1035 void*array_getvalue(array_t*array, int nr) {
1036     if(nr > array->num || nr<0) {
1037         printf("error: reference to element %d in array[%d]\n", nr, array->num);
1038         *(int*)0 = 0xdead;
1039         return 0;
1040     }
1041     return array->d[nr].data;
1042 }
1043 int array_append(array_t*array, const void*name, void*data) {
1044     while(array->size <= array->num) {
1045         array->size += 64;
1046         if(!array->d) {
1047             array->d = malloc(sizeof(array_entry_t)*array->size);
1048         } else {
1049             array->d = realloc(array->d, sizeof(array_entry_t)*array->size);
1050         }
1051     }
1052
1053     dictentry_t*e = dict_put(array->entry2pos, name, (void*)(ptroff_t)(array->num+1));
1054
1055     if(name) {
1056         array->d[array->num].name = e->key;
1057     } else {
1058         array->d[array->num].name = 0;
1059     }
1060     array->d[array->num].data = (void*)data;
1061     return array->num++;
1062 }
1063 int array_find(array_t*array, const void*name)
1064 {
1065     int pos = (int)(ptroff_t)dict_lookup(array->entry2pos, name);
1066     return pos-1;
1067 }
1068 int array_find2(array_t*array, const void*name, void*data)
1069 {
1070     dict_t*h= array->entry2pos;
1071     dictentry_t*e = dict_get_slot(array->entry2pos, name);
1072
1073     while(e) {
1074         int index = ((int)(ptroff_t)e->data) - 1;
1075         if(h->key_type->equals(e->key, name) && array->d[index].data == data) {
1076             return index;
1077         }
1078         e = e->next;
1079     }
1080     return -1;
1081 }
1082 int array_update(array_t*array, const void*name, void*data) {
1083     int pos = array_find(array, name);
1084     if(pos>=0) {
1085         array->d[pos].data = data;
1086         return pos;
1087     }
1088     return array_append(array, name, data);
1089 }
1090 int array_append_if_new(array_t*array, const void*name, void*data) {
1091     int pos = array_find(array, name);
1092     if(pos>=0)
1093         return pos;
1094     return array_append(array, name, data);
1095 }
1096 void array_free(array_t*array) {
1097     dict_destroy(array->entry2pos);
1098     if(array->d) {
1099         free(array->d);array->d = 0;
1100     }
1101     free(array);
1102 }
1103
1104 // ------------------------------- list_t --------------------------------------
1105
1106 struct _commonlist;
1107 typedef struct _listinfo {
1108     int size;
1109     struct _commonlist*last;
1110 } listinfo_t;
1111
1112 typedef struct _commonlist {
1113     void*entry;
1114     struct _commonlist*next;
1115     listinfo_t info[0];
1116 } commonlist_t;
1117
1118 int list_length_(void*_list)
1119 {
1120     commonlist_t*l = (commonlist_t*)_list;
1121     if(!l)
1122         return 0;
1123     return l->info[0].size;
1124 }
1125 void list_append_(void*_list, void*entry)
1126 {
1127     commonlist_t**list = (commonlist_t**)_list;
1128     commonlist_t* n = 0;
1129     if(!*list) {
1130         n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1131         *list = n;
1132         (*list)->info[0].size = 0;
1133     } else {
1134         n = malloc(sizeof(commonlist_t));
1135         (*list)->info[0].last->next = n;
1136     }
1137     n->next = 0;
1138     n->entry = entry;
1139     (*list)->info[0].last = n;
1140     (*list)->info[0].size++;
1141 }
1142 /* notice: prepending uses slighly more space than appending */
1143 void list_prepend_(void*_list, void*entry)
1144 {
1145     commonlist_t**list = (commonlist_t**)_list;
1146     commonlist_t* n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1147     int size = 0;
1148     commonlist_t* last = 0;
1149     if(*list) {
1150         last = (*list)->info[0].last;
1151         size = (*list)->info[0].size;
1152     }
1153     n->next = *list;
1154     n->entry = entry;
1155     *list = n;
1156     (*list)->info[0].last = last;
1157     (*list)->info[0].size = size+1;
1158 }
1159 void list_free_(void*_list) 
1160 {
1161     commonlist_t**list = (commonlist_t**)_list;
1162     commonlist_t*l = *list;
1163     while(l) {
1164         commonlist_t*next = l->next;
1165         free(l);
1166         l = next;
1167     }
1168     *list = 0;
1169 }
1170 void*list_clone_(void*_list) 
1171 {
1172     commonlist_t*l = *(commonlist_t**)_list;
1173
1174     void*dest = 0;
1175     while(l) {
1176         commonlist_t*next = l->next;
1177         list_append_(&dest, l->entry);
1178         l = next;
1179     }
1180     return dest;
1181
1182 }