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