added items.
[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,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     { 
69         //m->len += 1024>length?1024:(null?length*2:length);
70
71         m->len *= 2;
72         while(m->len < m->pos)
73             m->len += 64;
74
75         m->buffer = m->buffer?(char*)realloc(m->buffer,m->len):(char*)malloc(m->len);
76     }
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
91 // ------------------------------- ringbuffer_t -------------------------------
92
93 typedef struct _ringbuffer_internal_t
94 {
95     unsigned char*buffer;
96     int readpos;
97     int writepos;
98     int buffersize;
99 } ringbuffer_internal_t;
100
101 void ringbuffer_init(ringbuffer_t*r)
102 {
103     ringbuffer_internal_t*i = (ringbuffer_internal_t*)malloc(sizeof(ringbuffer_internal_t)); 
104     memset(r, 0, sizeof(ringbuffer_t));
105     memset(i, 0, sizeof(ringbuffer_internal_t));
106     r->internal = i;
107     i->buffer = (unsigned char*)malloc(1024);
108     i->buffersize = 1024;
109 }
110 int ringbuffer_read(ringbuffer_t*r, void*buf, int len)
111 {
112     unsigned char* data = (unsigned char*)buf;
113     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
114     if(r->available < len)
115         len = r->available;
116     if(!len)
117         return 0;
118     if(i->readpos + len > i->buffersize) {
119         int read1 = i->buffersize-i->readpos;
120         memcpy(data, &i->buffer[i->readpos], read1);
121         memcpy(&data[read1], &i->buffer[0], len - read1);
122         i->readpos = len - read1;
123     } else {
124         memcpy(data, &i->buffer[i->readpos], len);
125         i->readpos += len;
126         i->readpos %= i->buffersize;
127     }
128     r->available -= len;
129     return len;
130 }
131 void ringbuffer_put(ringbuffer_t*r, void*buf, int len)
132 {
133     unsigned char* data = (unsigned char*)buf;
134     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
135     
136     if(i->buffersize - r->available < len)
137     {
138         unsigned char* buf2;
139         int newbuffersize = i->buffersize;
140         int oldavailable = r->available;
141         newbuffersize*=3;newbuffersize/=2; /*grow at least by 50% each time */
142
143         if(newbuffersize < r->available + len)
144             newbuffersize = r->available + len + 1024;
145
146         buf2 = (unsigned char*)malloc(newbuffersize);
147         ringbuffer_read(r, buf2, r->available);
148         free(i->buffer);
149         i->buffer = buf2;
150         i->buffersize = newbuffersize;
151         i->readpos = 0;
152         i->writepos = oldavailable;
153         r->available = oldavailable;
154     }
155     if(i->writepos + len > i->buffersize) {
156         int read1 = i->buffersize-i->writepos;
157         memcpy(&i->buffer[i->writepos], data, read1);
158         memcpy(&i->buffer[0], &data[read1], len - read1);
159         i->writepos = len - read1;
160     } else {
161         memcpy(&i->buffer[i->writepos], data, len);
162         i->writepos += len;
163         i->writepos %= i->buffersize;
164     }
165     r->available += len;
166 }
167 void ringbuffer_clear(ringbuffer_t*r)
168 {
169     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
170     free(i->buffer);i->buffer = 0;
171     free(i);
172 }
173
174 // ------------------------------- string_t -----------------------------------
175
176 void string_set2(string_t*str, char*text, int len)
177 {
178     str->len = len;
179     str->str = text;
180 }
181 void string_set(string_t*str, char*text)
182 {
183     str->len = strlen(text);
184     str->str = text;
185 }
186 void string_dup2(string_t*str, const char*text, int len)
187 {
188     str->len = len;
189     str->str = strdup_n(text, len);
190 }
191 void string_dup(string_t*str, const char*text)
192 {
193     str->len = strlen(text);
194     str->str = strdup(text);
195 }
196 int string_equals(string_t*str, const char*text)
197 {
198     int l = strlen(text);
199     if(str->len == l && !strncmp(str->str, text, l))
200         return 1;
201     return 0;
202 }
203 int string_equals2(string_t*str, string_t*str2)
204 {
205     if(str->len == str2->len && !strncmp(str->str, str2->str, str->len))
206         return 1;
207     return 0;
208 }
209 char* string_cstr(string_t*str)
210 {
211     return strdup_n(str->str, str->len);
212 }
213
214 // ------------------------------- stringarray_t ------------------------------
215
216 typedef struct _stringarray_internal_t
217 {
218     mem_t data;
219     mem_t pos;
220     int num;
221 } stringarray_internal_t;
222 void stringarray_init(stringarray_t*sa)
223 {
224     stringarray_internal_t*s;
225     sa->internal = (stringarray_internal_t*)malloc(sizeof(stringarray_internal_t)); 
226     memset(sa->internal, 0, sizeof(stringarray_internal_t));
227     s = (stringarray_internal_t*)sa->internal;
228     mem_init(&s->data);
229     mem_init(&s->pos);
230 }
231 void stringarray_put(stringarray_t*sa, string_t str)
232 {
233     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
234     int pos;
235     pos = mem_putstring(&s->data, str);
236     mem_put(&s->pos, &pos, sizeof(int));
237     s->num++;
238 }
239 char* stringarray_at(stringarray_t*sa, int pos)
240 {
241     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
242     int p;
243     if(pos<0 || pos>=s->num)
244         return 0;
245     p = *(int*)&s->pos.buffer[pos*sizeof(int)];
246     if(p<0)
247         return 0;
248     return &s->data.buffer[p];
249 }
250 string_t stringarray_at2(stringarray_t*sa, int pos)
251 {
252     string_t s;
253     s.str = stringarray_at(sa, pos);
254     s.len = s.str?strlen(s.str):0;
255     return s;
256 }
257 void stringarray_del(stringarray_t*sa, int pos)
258 {
259     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
260     *(int*)&s->pos.buffer[pos*sizeof(int)] = -1;
261 }
262 int stringarray_find(stringarray_t*sa, string_t* str)
263 {
264     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
265     int t;
266     for(t=0;t<s->num;t++) {
267         string_t s = stringarray_at2(sa, t);
268         if(s.str && string_equals2(&s, str)) {
269             return t;
270         }
271     }
272     return -1;
273 }
274 void stringarray_clear(stringarray_t*sa)
275 {
276     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
277     mem_clear(&s->data);
278     mem_clear(&s->pos);
279     free(s);
280 }
281 void stringarray_destroy(stringarray_t*sa)
282 {
283     stringarray_clear(sa);
284     free(sa);
285 }
286
287
288 // ------------------------------- map_t --------------------------------------
289
290 typedef struct _map_internal_t
291 {
292     stringarray_t keys;
293     stringarray_t values;
294     int num;
295 } map_internal_t;
296
297 void map_init(map_t*map)
298 {
299     map_internal_t*m;
300     map->internal = (map_internal_t*)malloc(sizeof(map_internal_t));
301     memset(map->internal, 0, sizeof(map_internal_t));
302     m = (map_internal_t*)map->internal;
303     stringarray_init(&m->keys);
304     stringarray_init(&m->values);
305 }
306 void map_put(map_t*map, string_t t1, string_t t2)
307 {
308     map_internal_t*m = (map_internal_t*)map->internal;
309     stringarray_put(&m->keys, t1);
310     stringarray_put(&m->values, t2);
311     m->num++;
312 }
313 char* map_lookup(map_t*map, const char*name)
314 {
315     int s;
316     map_internal_t*m = (map_internal_t*)map->internal;
317     string_t str;
318     string_set(&str, (char*)name);
319     s = stringarray_find(&m->keys, &str);
320     if(s>=0) {
321         string_t s2 = stringarray_at2(&m->values, s);
322         return s2.str;
323     }
324     return 0;
325 }
326 void map_dump(map_t*map, FILE*fi, const char*prefix)
327 {
328     int t;
329     map_internal_t*m = (map_internal_t*)map->internal;
330     for(t=0;t<m->num;t++) {
331         string_t s1 = stringarray_at2(&m->keys, t);
332         string_t s2 = stringarray_at2(&m->values, t);
333         fprintf(fi, "%s%s=%s\n", prefix, s1.str, s2.str);
334     }
335 }
336 void map_clear(map_t*map)
337 {
338     map_internal_t*m = (map_internal_t*)map->internal;
339     stringarray_clear(&m->keys);
340     stringarray_clear(&m->values);
341     free(m);
342 }
343 void map_destroy(map_t*map)
344 {
345     map_clear(map);
346     free(map);
347 }
348
349 // ------------------------------- dictionary_t -------------------------------
350
351 typedef struct _dictionary_internal_t
352 {
353     stringarray_t keys;
354     mem_t values;
355     int num;
356 } dictionary_internal_t;
357
358 void dictionary_init(dictionary_t*dict)
359 {
360     dictionary_internal_t*d;
361     dict->internal = (dictionary_internal_t*)malloc(sizeof(dictionary_internal_t));
362     memset(dict->internal, 0, sizeof(dictionary_internal_t));
363     d = (dictionary_internal_t*)dict->internal;
364     stringarray_init(&d->keys);
365     mem_init(&d->values);
366 }
367 void dictionary_put(dictionary_t*dict, string_t t1, void* t2)
368 {
369     dictionary_internal_t*d = (dictionary_internal_t*)dict->internal;
370     int s=0;
371     s = stringarray_find(&d->keys, &t1);
372     if(s>=0) {
373         /* replace */
374         *(void**)(&d->values.buffer[s*sizeof(void*)]) = t2;
375     } else {
376         stringarray_put(&d->keys, t1);
377         mem_put(&d->values, &t2, sizeof(void*));
378         d->num++;
379     }
380 }
381 void dictionary_put2(dictionary_t*dict, const char*t1, void* t2)
382 {
383     string_t s;
384     string_set(&s, (char*)t1);
385     dictionary_put(dict, s, t2);
386 }
387 void* dictionary_lookup(dictionary_t*dict, const char*name)
388 {
389     int s;
390     dictionary_internal_t*d = (dictionary_internal_t*)dict->internal;
391     string_t str;
392     string_set(&str, (char*)name);
393     s = stringarray_find(&d->keys, &str);
394     if(s>=0) {
395         return *(void**)&d->values.buffer[sizeof(void*)*s];
396     }
397     return 0;
398 }
399 void dictionary_dump(dictionary_t*dict, FILE*fi, const char*prefix)
400 {
401     dictionary_internal_t*d = (dictionary_internal_t*)dict->internal;
402     int t;
403     for(t=0;t<d->num;t++) {
404         string_t s1 = stringarray_at2(&d->keys, t);
405         fprintf(fi, "%s%s=%08x\n", prefix, s1.str, *(void**)&d->values.buffer[sizeof(void*)*t]);
406     }
407 }
408 void dictionary_del(dictionary_t*dict, const char* name)
409 {
410     dictionary_internal_t*d = (dictionary_internal_t*)dict->internal;
411     int s;
412     string_t str;
413     string_set(&str, (char*)name);
414     s = stringarray_find(&d->keys, &str);
415     if(s>=0) {
416         *(void**)(&d->values.buffer[s*sizeof(void*)]) = 0;
417         stringarray_del(&d->keys, s);
418     }
419 }
420 void dictionary_clear(dictionary_t*dict)
421 {
422     dictionary_internal_t*d = (dictionary_internal_t*)dict->internal;
423     stringarray_clear(&d->keys);
424     mem_clear(&d->values);
425     free(d);
426 }
427 void dictionary_destroy(dictionary_t*dict)
428 {
429     dictionary_clear(dict);
430     free(dict);
431 }
432
433 // ------------------------------- heap_t -------------------------------
434
435 void heap_init(heap_t*h,int n,int elem_size, int(*compare)(const void *, const void *))
436 {
437     memset(h, 0, sizeof(heap_t));
438     h->max_size = n;
439     h->size = 0;
440     h->elem_size = elem_size;
441     h->compare = compare;
442     h->elements = (void**)malloc(n*sizeof(void*));memset(h->elements, 0, n*sizeof(void*));
443     h->data = (char*)malloc(h->max_size*h->elem_size);memset(h->data, 0, h->max_size*h->elem_size);
444 }
445 void heap_clear(heap_t*h)
446 {
447     free(h->elements);
448     free(h->data);
449 }
450
451 #define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))>0)
452
453 static void up(heap_t*h, int node)
454 {
455     void*node_p = h->elements[node];
456     int parent = node;
457     do {
458         node = parent;
459         if(!node) break;
460         parent = (node-1)/2;
461         h->elements[node] = h->elements[parent];
462     } while(HEAP_NODE_SMALLER(h,h->elements[parent], node_p));
463
464     h->elements[node] = node_p;
465 }
466 static void down(heap_t*h, int node)
467 {
468     void*node_p = h->elements[node];
469     int child = node;
470     do {
471         node = child;
472
473         /* determine new child's position */
474         child = node<<1|1;
475         if(child >= h->size) 
476             break;
477         if(child+1 < h->size && HEAP_NODE_SMALLER(h,h->elements[child],h->elements[child+1])) // search for bigger child
478             child++;
479
480         h->elements[node] = h->elements[child];
481     } while(HEAP_NODE_SMALLER(h,node_p, h->elements[child]));
482     
483     h->elements[node] = node_p;
484 }
485 void heap_put(heap_t*h, void*e) 
486 {
487     int pos = h->size++;
488     memcpy(&h->data[pos*h->elem_size],e,h->elem_size);
489     h->elements[pos] = &h->data[pos];
490     up(h, pos);
491 }
492 int heap_size(heap_t*h)
493 {
494     return h->size;
495 }
496 void* heap_max(heap_t*h)
497 {
498     return h->elements[0];
499 }
500 void* heap_chopmax(heap_t*h)
501 {
502     void*p = h->elements[0];
503     h->elements[0] = h->elements[--h->size];
504     down(h,0);
505     return p;
506 }
507 void heap_dump(heap_t*h, FILE*fi)
508 {
509     int t;
510     for(t=0;t<h->size;t++) {
511         int s;
512         for(s=0;s<=t;s=(s+1)*2-1) {
513             if(s==t) fprintf(fi,"\n");
514         }
515         //fprintf(fi,"%d ", h->elements[t]->x); //?
516     }
517 }
518 void** heap_flatten(heap_t*h)
519 {
520     void**nodes = (void**)malloc(h->size*sizeof(void*));
521     void**p = nodes;
522    
523     while(h->size) {
524         /*printf("Heap Size: %d\n", h->size);
525         heap_print(stdout, h);
526         printf("\n");*/
527         *p++ = heap_chopmax(h);
528     }
529     return nodes;
530 }
531