e07c39729b40a2f521bf71d29b56fb1b5e542035
[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 "q.h"
29
30 // ------------------------------- malloc, alloc routines ---------------------
31
32 #ifndef STRNDUP
33 char* strdup_n(const char*str, int size)
34 {
35     char*m = (char*)rfx_alloc(size+1);
36     memcpy(m, str, size);
37     m[size] = 0;
38     return m;
39 }
40 #endif
41 char*qstrdup(const char*string)
42 {
43     return strdup(string);
44 }
45 char*qstrndup(const char*string, int len)
46 {
47     return strdup_n(string, len);
48 }
49
50 // ------------------------------- mem_t --------------------------------------
51
52 void mem_init(mem_t*mem)
53 {
54     memset(mem, 0, sizeof(mem_t));
55 }
56 void mem_clear(mem_t*mem)
57 {
58     rfx_free(mem->buffer);mem->buffer = 0;
59 }
60 void mem_destroy(mem_t*mem)
61 {
62     mem_clear(mem);
63     rfx_free(mem);
64 }
65 static int mem_put_(mem_t*m,const void*data, int length, int null)
66 {
67     int n = m->pos;
68     m->pos += length + (null?1:0);
69     if(m->pos > m->len) { 
70         m->len = (m->pos+63)&~63;
71         m->buffer = m->buffer?(char*)rfx_realloc(m->buffer,m->len):(char*)rfx_alloc(m->len);
72     }
73     assert(n+length <= m->len);
74     memcpy(&m->buffer[n], data, length);
75     if(null)
76         m->buffer[n + length] = 0;
77     return n;
78 }
79 int mem_put(mem_t*m,void*data, int length)
80 {
81     return mem_put_(m, data, length, 0);
82 }
83 int mem_putstring(mem_t*m,string_t str)
84 {
85     return mem_put_(m, str.str, str.len, 1);
86 }
87
88 // ------------------------------- ringbuffer_t -------------------------------
89
90 typedef struct _ringbuffer_internal_t
91 {
92     unsigned char*buffer;
93     int readpos;
94     int writepos;
95     int buffersize;
96 } ringbuffer_internal_t;
97
98 void ringbuffer_init(ringbuffer_t*r)
99 {
100     ringbuffer_internal_t*i = (ringbuffer_internal_t*)rfx_calloc(sizeof(ringbuffer_internal_t)); 
101     memset(r, 0, sizeof(ringbuffer_t));
102     r->internal = i;
103     i->buffer = (unsigned char*)rfx_alloc(1024);
104     i->buffersize = 1024;
105 }
106 int ringbuffer_read(ringbuffer_t*r, void*buf, int len)
107 {
108     unsigned char* data = (unsigned char*)buf;
109     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
110     if(r->available < len)
111         len = r->available;
112     if(!len)
113         return 0;
114     if(i->readpos + len > i->buffersize) {
115         int read1 = i->buffersize-i->readpos;
116         memcpy(data, &i->buffer[i->readpos], read1);
117         memcpy(&data[read1], &i->buffer[0], len - read1);
118         i->readpos = len - read1;
119     } else {
120         memcpy(data, &i->buffer[i->readpos], len);
121         i->readpos += len;
122         i->readpos %= i->buffersize;
123     }
124     r->available -= len;
125     return len;
126 }
127 void ringbuffer_put(ringbuffer_t*r, void*buf, int len)
128 {
129     unsigned char* data = (unsigned char*)buf;
130     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
131     
132     if(i->buffersize - r->available < len)
133     {
134         unsigned char* buf2;
135         int newbuffersize = i->buffersize;
136         int oldavailable = r->available;
137         newbuffersize*=3;newbuffersize/=2; /*grow at least by 50% each time */
138
139         if(newbuffersize < r->available + len)
140             newbuffersize = r->available + len + 1024;
141
142         buf2 = (unsigned char*)rfx_alloc(newbuffersize);
143         ringbuffer_read(r, buf2, r->available);
144         rfx_free(i->buffer);
145         i->buffer = buf2;
146         i->buffersize = newbuffersize;
147         i->readpos = 0;
148         i->writepos = oldavailable;
149         r->available = oldavailable;
150     }
151     if(i->writepos + len > i->buffersize) {
152         int read1 = i->buffersize-i->writepos;
153         memcpy(&i->buffer[i->writepos], data, read1);
154         memcpy(&i->buffer[0], &data[read1], len - read1);
155         i->writepos = len - read1;
156     } else {
157         memcpy(&i->buffer[i->writepos], data, len);
158         i->writepos += len;
159         i->writepos %= i->buffersize;
160     }
161     r->available += len;
162 }
163 void ringbuffer_clear(ringbuffer_t*r)
164 {
165     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
166     rfx_free(i->buffer);i->buffer = 0;
167     rfx_free(i);
168 }
169
170 // ------------------------------- heap_t -------------------------------
171
172 void heap_init(heap_t*h,int n,int elem_size, int(*compare)(const void *, const void *))
173 {
174     memset(h, 0, sizeof(heap_t));
175     h->max_size = n;
176     h->size = 0;
177     h->elem_size = elem_size;
178     h->compare = compare;
179     h->elements = (void**)rfx_calloc(n*sizeof(void*));
180     h->data = (char*)rfx_calloc(h->max_size*h->elem_size);
181 }
182 void heap_clear(heap_t*h)
183 {
184     rfx_free(h->elements);
185     rfx_free(h->data);
186 }
187
188 #define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))>0)
189
190 static void up(heap_t*h, int node)
191 {
192     void*node_p = h->elements[node];
193     int parent = node;
194     do {
195         node = parent;
196         if(!node) break;
197         parent = (node-1)/2;
198         h->elements[node] = h->elements[parent];
199     } while(HEAP_NODE_SMALLER(h,h->elements[parent], node_p));
200
201     h->elements[node] = node_p;
202 }
203 static void down(heap_t*h, int node)
204 {
205     void*node_p = h->elements[node];
206     int child = node;
207     do {
208         node = child;
209
210         /* determine new child's position */
211         child = node<<1|1;
212         if(child >= h->size) 
213             break;
214         if(child+1 < h->size && HEAP_NODE_SMALLER(h,h->elements[child],h->elements[child+1])) // search for bigger child
215             child++;
216
217         h->elements[node] = h->elements[child];
218     } while(HEAP_NODE_SMALLER(h,node_p, h->elements[child]));
219     
220     h->elements[node] = node_p;
221 }
222 void heap_put(heap_t*h, void*e) 
223 {
224     int pos = h->size++;
225     memcpy(&h->data[pos*h->elem_size],e,h->elem_size);
226     h->elements[pos] = &h->data[pos];
227     up(h, pos);
228 }
229 int heap_size(heap_t*h)
230 {
231     return h->size;
232 }
233 void* heap_max(heap_t*h)
234 {
235     return h->elements[0];
236 }
237 void* heap_chopmax(heap_t*h)
238 {
239     void*p = h->elements[0];
240     h->elements[0] = h->elements[--h->size];
241     down(h,0);
242     return p;
243 }
244 void heap_dump(heap_t*h, FILE*fi)
245 {
246     int t;
247     for(t=0;t<h->size;t++) {
248         int s;
249         for(s=0;s<=t;s=(s+1)*2-1) {
250             if(s==t) fprintf(fi,"\n");
251         }
252         //fprintf(fi,"%d ", h->elements[t]->x); //?
253     }
254 }
255 void** heap_flatten(heap_t*h)
256 {
257     void**nodes = (void**)rfx_alloc(h->size*sizeof(void*));
258     void**p = nodes;
259    
260     while(h->size) {
261         /*printf("Heap Size: %d\n", h->size);
262         heap_print(stdout, h);
263         printf("\n");*/
264         *p++ = heap_chopmax(h);
265     }
266     return nodes;
267 }
268
269 // ------------------------------- crc32 --------------------------------------
270 static unsigned int*crc32 = 0;
271 static void crc32_init(void)
272 {
273     int t;
274     if(crc32) 
275         return;
276     crc32= (unsigned int*)rfx_alloc(sizeof(unsigned int)*256);
277     for(t=0; t<256; t++) {
278         unsigned int c = t;
279         int s;
280         for (s = 0; s < 8; s++) {
281           c = (0xedb88320L*(c&1)) ^ (c >> 1);
282         }
283         crc32[t] = c;
284     }
285 }
286 // ------------------------------- string_t -----------------------------------
287
288 void string_set2(string_t*str, const char*text, int len)
289 {
290     str->len = len;
291     str->str = text;
292 }
293 void string_set(string_t*str, const char*text)
294 {
295     str->len = strlen(text);
296     str->str = text;
297 }
298 string_t string_new(const char*text, int len)
299 {
300     string_t s;
301     s.len = len;
302     s.str = text;
303     return s;
304 }
305 string_t string_new2(const char*text)
306 {
307     string_t s;
308     s.len = strlen(text);
309     s.str = text;
310     return s;
311 }
312 char* string_cstr(string_t*str)
313 {
314     return strdup_n(str->str, str->len);
315 }
316 unsigned int string_hash(string_t*str)
317 {
318     int t;
319     unsigned int checksum = 0;
320     if(!crc32)
321         crc32_init();
322     for(t=0;t<str->len;t++) {
323         checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff];
324     }
325     return checksum;
326 }
327 unsigned int string_hash2(const char*str)
328 {
329     unsigned int checksum = 0;
330     const char*p = str;
331     if(!crc32)
332         crc32_init();
333     while(*p) {
334         checksum = checksum>>8 ^ crc32[(*p^checksum)&0xff];
335         p++;
336     }
337     return checksum;
338 }
339 unsigned int string_hash3(const char*str, int len)
340 {
341     string_t s;
342     s.str = str;
343     s.len = len;
344     return string_hash(&s);
345 }
346 void string_dup2(string_t*str, const char*text, int len)
347 {
348     str->len = len;
349     str->str = strdup_n(text, len);
350 }
351 void string_dup(string_t*str, const char*text)
352 {
353     str->len = strlen(text);
354     str->str = strdup(text);
355 }
356 int string_equals(string_t*str, const char*text)
357 {
358     int l = strlen(text);
359     if(str->len == l && !memcmp(str->str, text, l))
360         return 1;
361     return 0;
362 }
363 int string_equals2(string_t*str, string_t*str2)
364 {
365     if(str->len == str2->len && !memcmp(str->str, str2->str, str->len))
366         return 1;
367     return 0;
368 }
369
370 // ------------------------------- stringarray_t ------------------------------
371
372 typedef struct _stringlist {
373     int index;
374     struct _stringlist*next;
375 } stringlist_t;
376
377 typedef struct _stringarray_internal_t
378 {
379     mem_t pos;
380     stringlist_t**hash;
381     int num;
382     int hashsize;
383 } stringarray_internal_t;
384
385 void stringarray_init(stringarray_t*sa, int hashsize)
386 {
387     stringarray_internal_t*s;
388     int t;
389     sa->internal = (stringarray_internal_t*)rfx_calloc(sizeof(stringarray_internal_t)); 
390     s = (stringarray_internal_t*)sa->internal;
391     mem_init(&s->pos);
392     s->hash = rfx_calloc(sizeof(stringlist_t*)*hashsize);
393     s->hashsize = hashsize;
394 }
395 void stringarray_put(stringarray_t*sa, string_t str)
396 {
397     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
398     int pos;
399     int hash = string_hash(&str) % s->hashsize;
400
401     char*ss = string_cstr(&str);
402     mem_put(&s->pos, &ss, sizeof(char*));
403
404     stringlist_t*l = rfx_alloc(sizeof(stringlist_t));
405     l->index = s->num;
406     l->next = s->hash[hash];
407     s->hash[hash] = l;
408
409     s->num++;
410 }
411 char* stringarray_at(stringarray_t*sa, int pos)
412 {
413     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
414     char*p;
415     if(pos<0 || pos>=s->num)
416         return 0;
417     p = *(char**)&s->pos.buffer[pos*sizeof(char*)];
418     if(p<0)
419         return 0;
420     return p;
421 }
422 string_t stringarray_at2(stringarray_t*sa, int pos)
423 {
424     string_t s;
425     s.str = stringarray_at(sa, pos);
426     s.len = s.str?strlen(s.str):0;
427     return s;
428 }
429 static stringlist_t* stringlist_del(stringarray_t*sa, stringlist_t*l, int index)
430 {
431     stringlist_t*ll = l;
432     stringlist_t*old = l;
433     while(l) {
434         if(index==l->index) {
435             old->next = l->next;
436             memset(l, 0, sizeof(stringlist_t));
437             rfx_free(l);
438             if(old==l)
439                 return 0;
440             else
441                 return ll;
442         }
443         old = l;
444         l = l->next;
445     }
446     fprintf(stderr, "Internal error: did not find string %d in hash\n", index);
447     return ll;
448 }
449
450 void stringarray_del(stringarray_t*sa, int pos)
451 {
452     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
453     string_t str = stringarray_at2(sa, pos);
454     int hash = string_hash(&str) % s->hashsize;
455     s->hash[hash] = stringlist_del(sa, s->hash[hash], pos);
456     *(char**)&s->pos.buffer[pos*sizeof(char*)] = 0;
457 }
458 int stringarray_find(stringarray_t*sa, string_t* str)
459 {
460     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
461     int hash = string_hash(str) % s->hashsize;
462     int t;
463     stringlist_t*l = s->hash[hash];
464     //TODO: statistics
465     while(l) {
466         string_t s = stringarray_at2(sa, l->index);
467         if(string_equals2(str, &s)) {
468             return l->index;
469         }
470         l = l->next;
471     }
472     return -1;
473 }
474 void stringarray_clear(stringarray_t*sa)
475 {
476     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
477     mem_clear(&s->pos);
478     int t;
479     for(t=0;t<s->hashsize;t++) {
480         stringlist_t*l = s->hash[t];
481         while(l) {
482             stringlist_t*next = l->next;
483             memset(l, 0, sizeof(stringlist_t));
484             rfx_free(l);
485             l = next;
486         }
487     }
488     rfx_free(s->hash);s->hash=0;
489     rfx_free(s);
490 }
491 void stringarray_destroy(stringarray_t*sa)
492 {
493     stringarray_clear(sa);
494     rfx_free(sa);
495 }
496
497
498 // ------------------------------- dictionary_t -------------------------------
499
500 #define INITIAL_SIZE 1
501
502 static int max(int x, int y) {
503     return x>y?x:y;
504 }
505
506 dict_t*dict_new()
507 {
508     dict_t*d = rfx_alloc(sizeof(dict_t));
509     dict_init(d);
510     return d;
511 }
512 void dict_init(dict_t*h) 
513 {
514     memset(h, 0, sizeof(dict_t));
515     h->hashsize = INITIAL_SIZE;
516     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
517     h->num = 0;
518 }
519 static void dict_expand(dict_t*h, int newlen)
520 {
521     assert(h->hashsize < newlen);
522     dictentry_t**newslots = (dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*newlen);
523     int t; 
524     for(t=0;t<h->hashsize;t++) {
525         dictentry_t*e = h->slots[t];
526         while(e) {
527             dictentry_t*next = e->next;
528             unsigned int newhash = e->hash%newlen;
529             e->next = newslots[newhash];
530             newslots[newhash] = e;
531             e = next;
532         }
533     }
534     if(h->slots)
535         rfx_free(h->slots);
536     h->slots = newslots;
537     h->hashsize = newlen;
538 }
539 void dict_put(dict_t*h, string_t s, void* data)
540 {
541     /* TODO: should we look for duplicates here? */
542     unsigned int hash = string_hash(&s);
543     dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
544
545     unsigned int hash2 = string_hash(&s) % h->hashsize;
546     char*sdata = rfx_alloc(s.len);
547     memcpy(sdata, s.str, s.len);
548     e->s = sdata;
549     e->len = s.len;
550     e->hash = hash; //for resizing
551     e->next = h->slots[hash2];
552     e->data = data;
553     h->slots[hash2] = e;
554     h->num++;
555 }
556 void dict_put2(dict_t*h, const char*s, void*data) 
557 {
558     string_t s2;
559     string_set(&s2, s);
560     dict_put(h, s2, data);
561 }
562 void dict_put3(dict_t*h, const char* s, int len, void*data)
563 {
564     string_t s3;
565     string_set2(&s3, s, len);
566     dict_put(h, s3, data);
567 }
568 void dict_dump(dict_t*h, FILE*fi, const char*prefix)
569 {
570     int t;
571     for(t=0;t<h->hashsize;t++) {
572         dictentry_t*e = h->slots[t];
573         while(e) {
574             char*s = strdup_n(e->s, e->len);
575             fprintf(fi, "%s%s=%08x\n", prefix, e->s, e->data);
576             rfx_free(s);
577             e = e->next;
578         }
579     }
580 }
581 int dict_count(dict_t*h)
582 {
583     return h->num;
584 }
585 void* dict_lookup2(dict_t*h, const char*s, int len)
586 {
587     if(!h->num)
588         return 0;
589     
590     unsigned int ohash = string_hash2(s);
591     unsigned int hash = ohash % h->hashsize;
592
593     /* check first entry for match */
594     dictentry_t*e = h->slots[hash];
595     if(e && e->len == len && !memcmp(e->s, s, len)) {
596         return e->data;
597     } else if(e) {
598         e = e->next;
599     }
600
601     /* if dict is 2/3 filled, double the size. Do
602        this the first time we have to actually iterate
603        through a slot to find our data */
604     if(e && h->num*3 >= h->hashsize*2) {
605         int newsize = h->hashsize;
606         while(h->num*3 >= newsize*2) {
607             newsize = newsize<15?15:(newsize+1)*2-1;
608         }
609         dict_expand(h, newsize);
610         hash = ohash % h->hashsize;
611         e = h->slots[hash];
612     }
613
614     /* check subsequent entries for a match */
615     while(e) {
616         if(e->len == len && !memcmp(e->s, s, len)) {
617             return e->data;
618         }
619         e = e->next;
620     }
621     return 0;
622 }
623 void* dict_lookup(dict_t*h, const char*s)
624 {
625     int l = strlen(s);
626     return dict_lookup2(h, s, l);
627 }
628 char dict_del(dict_t*h, const char*s)
629 {
630     if(!h->num)
631         return 0;
632     unsigned int hash = string_hash2(s) % h->hashsize;
633     int l = strlen(s);
634     dictentry_t*head = h->slots[hash];
635     dictentry_t*e = head, *prev=0;
636     while(e) {
637         if(e->len ==l && !memcmp(e->s, s, l)) {
638             dictentry_t*next = e->next;
639             rfx_free((void*)e->s);
640             memset(e, 0, sizeof(dictentry_t));
641             rfx_free(e);
642             if(e == head) {
643                 h->slots[hash] = 0;
644             } else {
645                 assert(prev);
646                 prev->next = next;
647             }
648             h->num--;
649             return 1;
650         }
651         prev = e;
652         e = e->next;
653     }
654     return 0;
655 }
656 void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const char*key, void*val), void*data)
657 {
658     int t;
659     for(t=0;t<h->hashsize;t++) {
660         dictentry_t*e = h->slots[t];
661         while(e) {
662             dictentry_t*next = e->next;
663             if(runFunction) {
664                 char*s = strdup_n(e->s, e->len); //append \0
665                 runFunction(data, s, e->data);
666                 rfx_free(s);
667             }
668             e = e->next;
669         }
670     }
671 }
672 void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
673 {
674     int t;
675     for(t=0;t<h->hashsize;t++) {
676         dictentry_t*e = h->slots[t];
677         while(e) {
678             dictentry_t*next = e->next;
679             if(runFunction) {
680                 runFunction(e->data);
681             }
682             e = e->next;
683         }
684     }
685 }
686 void dict_free_all(dict_t*h, void (*freeFunction)(void*))
687 {
688     int t;
689     for(t=0;t<h->hashsize;t++) {
690         dictentry_t*e = h->slots[t];
691         while(e) {
692             dictentry_t*next = e->next;
693             rfx_free((void*)e->s);
694             if(freeFunction) {
695                 freeFunction(e->data);
696             }
697             memset(e, 0, sizeof(dictentry_t));
698             rfx_free(e);
699             e = next;
700         }
701     }
702     rfx_free(h->slots);
703     memset(h, 0, sizeof(dict_t));
704 }
705 void dict_clear(dict_t*h) 
706 {
707     dict_free_all(h, 0);
708 }
709 void dict_destroy(dict_t*dict)
710 {
711     dict_clear(dict);
712     rfx_free(dict);
713 }
714
715 // ------------------------------- map_t --------------------------------------
716
717 typedef struct _map_internal_t
718 {
719     dict_t d;
720 } map_internal_t;
721
722 void map_init(map_t*map)
723 {
724     map_internal_t*m;
725     map->internal = (map_internal_t*)rfx_calloc(sizeof(map_internal_t));
726     m = (map_internal_t*)map->internal;
727     dict_init(&m->d);
728 }
729 void map_put(map_t*map, string_t t1, string_t t2)
730 {
731     map_internal_t*m = (map_internal_t*)map->internal;
732     string_t s;
733     char* s1 = string_cstr(&t1);
734     dict_put2(&m->d, s1, (void*)string_cstr(&t2));
735     rfx_free(s1);
736 }
737 const char* map_lookup(map_t*map, const char*name)
738 {
739     map_internal_t*m = (map_internal_t*)map->internal;
740     const char*value = dict_lookup(&m->d, name);
741     return value;
742 }
743 static void freestring(void*data)
744 {
745     rfx_free(data);
746 }
747 static void dumpmapentry(void*data, const char*key, void*value)
748 {
749     FILE*fi = (FILE*)data;
750     fprintf(fi, "%s=%s\n", key, (char*)value);
751 }
752 void map_dump(map_t*map, FILE*fi, const char*prefix)
753 {
754     int t;
755     map_internal_t*m = (map_internal_t*)map->internal;
756     dict_foreach_keyvalue(&m->d, dumpmapentry, fi);
757 }
758 void map_clear(map_t*map)
759 {
760     map_internal_t*m = (map_internal_t*)map->internal;
761     dict_free_all(&m->d, freestring);
762     rfx_free(m);
763 }
764 void map_destroy(map_t*map)
765 {
766     map_clear(map);
767     rfx_free(map);
768 }
769