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