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