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