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