3 Part of the swftools package.
5 Copyright (c) 2001,2002,2003,2004 Matthias Kramm <kramm@quiss.org>
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.
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.
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 */
28 // ------------------------------- malloc, alloc routines ---------------------
31 char* strdup_n(const char*str, int size)
33 char*m = (char*)malloc(size+1);
39 char*qstrdup(const char*string)
41 return strdup(string);
43 char*qstrndup(const char*string, int len)
45 return strdup_n(string, len);
48 // ------------------------------- mem_t --------------------------------------
50 void mem_init(mem_t*mem)
52 memset(mem, 0, sizeof(mem_t));
54 void mem_clear(mem_t*mem)
56 free(mem->buffer);mem->buffer = 0;
58 void mem_destroy(mem_t*mem)
63 static int mem_put_(mem_t*m,void*data, int length, int null)
66 m->pos += length + (null?1:0);
69 //m->len += 1024>length?1024:(null?length*2:length);
72 while(m->len < m->pos)
75 m->buffer = m->buffer?(char*)realloc(m->buffer,m->len):(char*)malloc(m->len);
77 memcpy(&m->buffer[n], data, length);
79 m->buffer[n + length] = 0;
82 int mem_put(mem_t*m,void*data, int length)
84 return mem_put_(m, data, length, 0);
86 int mem_putstring(mem_t*m,string_t str)
88 return mem_put_(m, str.str, str.len, 1);
91 // ------------------------------- ringbuffer_t -------------------------------
93 typedef struct _ringbuffer_internal_t
99 } ringbuffer_internal_t;
101 void ringbuffer_init(ringbuffer_t*r)
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));
107 i->buffer = (unsigned char*)malloc(1024);
108 i->buffersize = 1024;
110 int ringbuffer_read(ringbuffer_t*r, void*buf, int len)
112 unsigned char* data = (unsigned char*)buf;
113 ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
114 if(r->available < len)
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;
124 memcpy(data, &i->buffer[i->readpos], len);
126 i->readpos %= i->buffersize;
131 void ringbuffer_put(ringbuffer_t*r, void*buf, int len)
133 unsigned char* data = (unsigned char*)buf;
134 ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
136 if(i->buffersize - r->available < len)
139 int newbuffersize = i->buffersize;
140 int oldavailable = r->available;
141 newbuffersize*=3;newbuffersize/=2; /*grow at least by 50% each time */
143 if(newbuffersize < r->available + len)
144 newbuffersize = r->available + len + 1024;
146 buf2 = (unsigned char*)malloc(newbuffersize);
147 ringbuffer_read(r, buf2, r->available);
150 i->buffersize = newbuffersize;
152 i->writepos = oldavailable;
153 r->available = oldavailable;
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;
161 memcpy(&i->buffer[i->writepos], data, len);
163 i->writepos %= i->buffersize;
167 void ringbuffer_clear(ringbuffer_t*r)
169 ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
170 free(i->buffer);i->buffer = 0;
174 // ------------------------------- crc32 --------------------------------------
175 static unsigned int*crc32 = 0;
176 static void crc32_init(void)
181 crc32= (unsigned int*)malloc(sizeof(unsigned int)*256);
182 for(t=0; t<256; t++) {
185 for (s = 0; s < 8; s++) {
186 c = (0xedb88320L*(c&1)) ^ (c >> 1);
191 // ------------------------------- string_t -----------------------------------
193 void string_set2(string_t*str, char*text, int len)
198 void string_set(string_t*str, char*text)
200 str->len = strlen(text);
203 unsigned int string_hash(string_t*str)
206 unsigned int checksum = 0;
208 for(t=0;t<str->len;t++) {
209 checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff];
213 void string_dup2(string_t*str, const char*text, int len)
216 str->str = strdup_n(text, len);
218 void string_dup(string_t*str, const char*text)
220 str->len = strlen(text);
221 str->str = strdup(text);
223 int string_equals(string_t*str, const char*text)
225 int l = strlen(text);
226 if(str->len == l && !memcmp(str->str, text, l))
230 int string_equals2(string_t*str, string_t*str2)
232 if(str->len == str2->len && !memcmp(str->str, str2->str, str->len))
236 char* string_cstr(string_t*str)
238 return strdup_n(str->str, str->len);
241 // ------------------------------- stringarray_t ------------------------------
243 #define DEFAULT_HASH_SIZE 257
245 typedef struct _stringlist {
247 struct _stringlist*next;
250 typedef struct _stringarray_internal_t
257 } stringarray_internal_t;
259 void stringarray_init(stringarray_t*sa, int hashsize)
261 stringarray_internal_t*s;
263 sa->internal = (stringarray_internal_t*)malloc(sizeof(stringarray_internal_t));
264 memset(sa->internal, 0, sizeof(stringarray_internal_t));
265 s = (stringarray_internal_t*)sa->internal;
268 s->hash = malloc(sizeof(stringlist_t*)*hashsize);
269 memset(s->hash, 0, sizeof(stringlist_t*)*hashsize);
270 s->hashsize = hashsize;
272 void stringarray_put(stringarray_t*sa, string_t str)
274 stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
276 int hash = string_hash(&str) % s->hashsize;
277 pos = mem_putstring(&s->data, str);
278 mem_put(&s->pos, &pos, sizeof(int));
280 stringlist_t*l = malloc(sizeof(stringlist_t));
282 l->next = s->hash[hash];
287 char* stringarray_at(stringarray_t*sa, int pos)
289 stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
291 if(pos<0 || pos>=s->num)
293 p = *(int*)&s->pos.buffer[pos*sizeof(int)];
296 return &s->data.buffer[p];
298 string_t stringarray_at2(stringarray_t*sa, int pos)
301 s.str = stringarray_at(sa, pos);
302 s.len = s.str?strlen(s.str):0;
305 static stringlist_t* stringlist_del(stringarray_t*sa, stringlist_t*l, int index)
308 stringlist_t*old = l;
310 if(index==l->index) {
312 memset(l, 0, sizeof(stringlist_t));
322 fprintf(stderr, "Internal error: did not find string %d in hash\n", index);
326 void stringarray_del(stringarray_t*sa, int pos)
328 stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
329 string_t str = stringarray_at2(sa, pos);
330 int hash = string_hash(&str) % s->hashsize;
331 s->hash[hash] = stringlist_del(sa, s->hash[hash], pos);
332 *(int*)&s->pos.buffer[pos*sizeof(int)] = -1;
334 int stringarray_find(stringarray_t*sa, string_t* str)
336 stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
337 int hash = string_hash(str) % s->hashsize;
339 stringlist_t*l = s->hash[hash];
341 string_t s = stringarray_at2(sa, l->index);
342 if(string_equals2(str, &s)) {
349 void stringarray_clear(stringarray_t*sa)
351 stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
355 for(t=0;t<s->hashsize;t++) {
356 stringlist_t*l = s->hash[t];
358 stringlist_t*next = l->next;
359 memset(l, 0, sizeof(stringlist_t));
366 void stringarray_destroy(stringarray_t*sa)
368 stringarray_clear(sa);
373 // ------------------------------- map_t --------------------------------------
375 typedef struct _map_internal_t
378 stringarray_t values;
382 void map_init(map_t*map)
385 map->internal = (map_internal_t*)malloc(sizeof(map_internal_t));
386 memset(map->internal, 0, sizeof(map_internal_t));
387 m = (map_internal_t*)map->internal;
388 stringarray_init(&m->keys, DEFAULT_HASH_SIZE);
389 stringarray_init(&m->values, DEFAULT_HASH_SIZE);
391 void map_put(map_t*map, string_t t1, string_t t2)
393 map_internal_t*m = (map_internal_t*)map->internal;
394 stringarray_put(&m->keys, t1);
395 stringarray_put(&m->values, t2);
398 char* map_lookup(map_t*map, const char*name)
401 map_internal_t*m = (map_internal_t*)map->internal;
403 string_set(&str, (char*)name);
404 s = stringarray_find(&m->keys, &str);
406 string_t s2 = stringarray_at2(&m->values, s);
411 void map_dump(map_t*map, FILE*fi, const char*prefix)
414 map_internal_t*m = (map_internal_t*)map->internal;
415 for(t=0;t<m->num;t++) {
416 string_t s1 = stringarray_at2(&m->keys, t);
417 string_t s2 = stringarray_at2(&m->values, t);
418 fprintf(fi, "%s%s=%s\n", prefix, s1.str, s2.str);
421 void map_clear(map_t*map)
423 map_internal_t*m = (map_internal_t*)map->internal;
424 stringarray_clear(&m->keys);
425 stringarray_clear(&m->values);
428 void map_destroy(map_t*map)
434 // ------------------------------- dictionary_t -------------------------------
436 typedef struct _dictionary_internal_t
441 } dictionary_internal_t;
443 void dictionary_init(dictionary_t*dict)
445 dictionary_internal_t*d;
446 dict->internal = (dictionary_internal_t*)malloc(sizeof(dictionary_internal_t));
447 memset(dict->internal, 0, sizeof(dictionary_internal_t));
448 d = (dictionary_internal_t*)dict->internal;
449 stringarray_init(&d->keys, DEFAULT_HASH_SIZE);
450 mem_init(&d->values);
452 void dictionary_put(dictionary_t*dict, string_t t1, void* t2)
454 dictionary_internal_t*d = (dictionary_internal_t*)dict->internal;
456 s = stringarray_find(&d->keys, &t1);
459 *(void**)(&d->values.buffer[s*sizeof(void*)]) = t2;
461 stringarray_put(&d->keys, t1);
462 mem_put(&d->values, &t2, sizeof(void*));
466 void dictionary_put2(dictionary_t*dict, const char*t1, void* t2)
469 string_set(&s, (char*)t1);
470 dictionary_put(dict, s, t2);
472 stringarray_t* dictionary_index(dictionary_t*dict)
474 dictionary_internal_t*d = (dictionary_internal_t*)dict->internal;
477 int dictionary_count(dictionary_t* dict) // this count includes entries that have been deleted
479 dictionary_internal_t*d = (dictionary_internal_t*)dict->internal;
482 void* dictionary_lookup(dictionary_t*dict, const char*name)
485 dictionary_internal_t*d = (dictionary_internal_t*)dict->internal;
487 string_set(&str, (char*)name);
488 s = stringarray_find(&d->keys, &str);
490 return *(void**)&d->values.buffer[sizeof(void*)*s];
494 void dictionary_dump(dictionary_t*dict, FILE*fi, const char*prefix)
496 dictionary_internal_t*d = (dictionary_internal_t*)dict->internal;
498 for(t=0;t<d->num;t++) {
499 string_t s1 = stringarray_at2(&d->keys, t);
500 fprintf(fi, "%s%s=%08x\n", prefix, s1.str, *(void**)&d->values.buffer[sizeof(void*)*t]);
503 void dictionary_del(dictionary_t*dict, const char* name)
505 dictionary_internal_t*d = (dictionary_internal_t*)dict->internal;
508 string_set(&str, (char*)name);
509 s = stringarray_find(&d->keys, &str);
511 *(void**)(&d->values.buffer[s*sizeof(void*)]) = 0;
512 stringarray_del(&d->keys, s);
515 void dictionary_clear(dictionary_t*dict)
517 dictionary_internal_t*d = (dictionary_internal_t*)dict->internal;
518 stringarray_clear(&d->keys);
519 mem_clear(&d->values);
522 void dictionary_destroy(dictionary_t*dict)
524 dictionary_clear(dict);
528 void dictionary_free_all(dictionary_t* dict, void (*freeFunction)(void*))
530 dictionary_internal_t*d = (dictionary_internal_t*)dict->internal;
532 char* name = stringarray_at(&d->keys, num) ;
535 freeFunction(dictionary_lookup(dict, name));
537 name = stringarray_at(&d->keys, num);
539 dictionary_clear(dict);
542 // ------------------------------- heap_t -------------------------------
544 void heap_init(heap_t*h,int n,int elem_size, int(*compare)(const void *, const void *))
546 memset(h, 0, sizeof(heap_t));
549 h->elem_size = elem_size;
550 h->compare = compare;
551 h->elements = (void**)malloc(n*sizeof(void*));memset(h->elements, 0, n*sizeof(void*));
552 h->data = (char*)malloc(h->max_size*h->elem_size);memset(h->data, 0, h->max_size*h->elem_size);
554 void heap_clear(heap_t*h)
560 #define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))>0)
562 static void up(heap_t*h, int node)
564 void*node_p = h->elements[node];
570 h->elements[node] = h->elements[parent];
571 } while(HEAP_NODE_SMALLER(h,h->elements[parent], node_p));
573 h->elements[node] = node_p;
575 static void down(heap_t*h, int node)
577 void*node_p = h->elements[node];
582 /* determine new child's position */
586 if(child+1 < h->size && HEAP_NODE_SMALLER(h,h->elements[child],h->elements[child+1])) // search for bigger child
589 h->elements[node] = h->elements[child];
590 } while(HEAP_NODE_SMALLER(h,node_p, h->elements[child]));
592 h->elements[node] = node_p;
594 void heap_put(heap_t*h, void*e)
597 memcpy(&h->data[pos*h->elem_size],e,h->elem_size);
598 h->elements[pos] = &h->data[pos];
601 int heap_size(heap_t*h)
605 void* heap_max(heap_t*h)
607 return h->elements[0];
609 void* heap_chopmax(heap_t*h)
611 void*p = h->elements[0];
612 h->elements[0] = h->elements[--h->size];
616 void heap_dump(heap_t*h, FILE*fi)
619 for(t=0;t<h->size;t++) {
621 for(s=0;s<=t;s=(s+1)*2-1) {
622 if(s==t) fprintf(fi,"\n");
624 //fprintf(fi,"%d ", h->elements[t]->x); //?
627 void** heap_flatten(heap_t*h)
629 void**nodes = (void**)malloc(h->size*sizeof(void*));
633 /*printf("Heap Size: %d\n", h->size);
634 heap_print(stdout, h);
636 *p++ = heap_chopmax(h);