3 Part of the swftools package.
5 Copyright (c) 2001,2002,2003,2004 Matthias Kramm <kramm@quiss.org>
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.
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 rfx_free Software
19 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
31 // ------------------------------- malloc, alloc routines ---------------------
34 char* strdup_n(const char*str, int size)
36 char*m = (char*)rfx_alloc(size+1);
42 char*qstrdup(const char*string)
44 return strdup(string);
46 char*qstrndup(const char*string, int len)
48 return strdup_n(string, len);
51 // ------------------------------- mem_t --------------------------------------
53 void mem_init(mem_t*mem)
55 memset(mem, 0, sizeof(mem_t));
57 void mem_clear(mem_t*mem)
59 rfx_free(mem->buffer);mem->buffer = 0;
61 void mem_destroy(mem_t*mem)
66 static int mem_put_(mem_t*m,const void*data, int length, int null)
69 m->pos += length + (null?1:0);
71 m->len = (m->pos+63)&~63;
72 m->buffer = m->buffer?(char*)rfx_realloc(m->buffer,m->len):(char*)rfx_alloc(m->len);
74 assert(n+length <= m->len);
75 memcpy(&m->buffer[n], data, length);
77 m->buffer[n + length] = 0;
80 int mem_put(mem_t*m,void*data, int length)
82 return mem_put_(m, data, length, 0);
84 int mem_putstring(mem_t*m,string_t str)
86 return mem_put_(m, str.str, str.len, 1);
89 // ------------------------------- ringbuffer_t -------------------------------
91 typedef struct _ringbuffer_internal_t
97 } ringbuffer_internal_t;
99 void ringbuffer_init(ringbuffer_t*r)
101 ringbuffer_internal_t*i = (ringbuffer_internal_t*)rfx_calloc(sizeof(ringbuffer_internal_t));
102 memset(r, 0, sizeof(ringbuffer_t));
104 i->buffer = (unsigned char*)rfx_alloc(1024);
105 i->buffersize = 1024;
107 int ringbuffer_read(ringbuffer_t*r, void*buf, int len)
109 unsigned char* data = (unsigned char*)buf;
110 ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
111 if(r->available < len)
115 if(i->readpos + len > i->buffersize) {
116 int read1 = i->buffersize-i->readpos;
117 memcpy(data, &i->buffer[i->readpos], read1);
118 memcpy(&data[read1], &i->buffer[0], len - read1);
119 i->readpos = len - read1;
121 memcpy(data, &i->buffer[i->readpos], len);
123 i->readpos %= i->buffersize;
128 void ringbuffer_put(ringbuffer_t*r, void*buf, int len)
130 unsigned char* data = (unsigned char*)buf;
131 ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
133 if(i->buffersize - r->available < len)
136 int newbuffersize = i->buffersize;
137 int oldavailable = r->available;
138 newbuffersize*=3;newbuffersize/=2; /*grow at least by 50% each time */
140 if(newbuffersize < r->available + len)
141 newbuffersize = r->available + len + 1024;
143 buf2 = (unsigned char*)rfx_alloc(newbuffersize);
144 ringbuffer_read(r, buf2, r->available);
147 i->buffersize = newbuffersize;
149 i->writepos = oldavailable;
150 r->available = oldavailable;
152 if(i->writepos + len > i->buffersize) {
153 int read1 = i->buffersize-i->writepos;
154 memcpy(&i->buffer[i->writepos], data, read1);
155 memcpy(&i->buffer[0], &data[read1], len - read1);
156 i->writepos = len - read1;
158 memcpy(&i->buffer[i->writepos], data, len);
160 i->writepos %= i->buffersize;
164 void ringbuffer_clear(ringbuffer_t*r)
166 ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
167 rfx_free(i->buffer);i->buffer = 0;
171 // ------------------------------- heap_t -------------------------------
173 void heap_init(heap_t*h,int n,int elem_size, int(*compare)(const void *, const void *))
175 memset(h, 0, sizeof(heap_t));
178 h->elem_size = elem_size;
179 h->compare = compare;
180 h->elements = (void**)rfx_calloc(n*sizeof(void*));
181 h->data = (char*)rfx_calloc(h->max_size*h->elem_size);
183 void heap_clear(heap_t*h)
185 rfx_free(h->elements);
189 #define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))>0)
191 static void up(heap_t*h, int node)
193 void*node_p = h->elements[node];
199 h->elements[node] = h->elements[parent];
200 } while(HEAP_NODE_SMALLER(h,h->elements[parent], node_p));
202 h->elements[node] = node_p;
204 static void down(heap_t*h, int node)
206 void*node_p = h->elements[node];
211 /* determine new child's position */
215 if(child+1 < h->size && HEAP_NODE_SMALLER(h,h->elements[child],h->elements[child+1])) // search for bigger child
218 h->elements[node] = h->elements[child];
219 } while(HEAP_NODE_SMALLER(h,node_p, h->elements[child]));
221 h->elements[node] = node_p;
223 void heap_put(heap_t*h, void*e)
226 memcpy(&h->data[pos*h->elem_size],e,h->elem_size);
227 h->elements[pos] = &h->data[pos];
230 int heap_size(heap_t*h)
234 void* heap_max(heap_t*h)
236 return h->elements[0];
238 void* heap_chopmax(heap_t*h)
240 void*p = h->elements[0];
241 h->elements[0] = h->elements[--h->size];
245 void heap_dump(heap_t*h, FILE*fi)
248 for(t=0;t<h->size;t++) {
250 for(s=0;s<=t;s=(s+1)*2-1) {
251 if(s==t) fprintf(fi,"\n");
253 //fprintf(fi,"%d ", h->elements[t]->x); //?
256 void** heap_flatten(heap_t*h)
258 void**nodes = (void**)rfx_alloc(h->size*sizeof(void*));
262 /*printf("Heap Size: %d\n", h->size);
263 heap_print(stdout, h);
265 *p++ = heap_chopmax(h);
270 // ------------------------------- crc32 --------------------------------------
271 static unsigned int*crc32 = 0;
272 static void crc32_init(void)
277 crc32= (unsigned int*)rfx_alloc(sizeof(unsigned int)*256);
278 for(t=0; t<256; t++) {
281 for (s = 0; s < 8; s++) {
282 c = (0xedb88320L*(c&1)) ^ (c >> 1);
287 // ------------------------------- string_t -----------------------------------
289 void string_set2(string_t*str, const char*text, int len)
294 void string_set(string_t*str, const char*text)
297 str->len = strlen(text);
303 string_t string_new(const char*text, int len)
310 string_t string_new2(const char*text)
314 s.len = strlen(text);
321 char* string_cstr(string_t*str)
323 return strdup_n(str->str, str->len);
326 unsigned int crc32_add_byte(unsigned int checksum, unsigned char b)
330 return checksum>>8 ^ crc32[(b^checksum)&0xff];
332 unsigned int crc32_add_string(unsigned int checksum, const char*s)
335 checksum = crc32_add_byte(checksum, *s);
341 unsigned int string_hash(const string_t*str)
344 unsigned int checksum = 0;
347 for(t=0;t<str->len;t++) {
348 checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff];
352 unsigned int string_hash2(const char*str)
354 unsigned int checksum = 0;
359 checksum = checksum>>8 ^ crc32[(*p^checksum)&0xff];
364 unsigned int string_hash3(const char*str, int len)
369 return string_hash(&s);
371 void string_dup2(string_t*str, const char*text, int len)
374 str->str = strdup_n(text, len);
376 void string_dup(string_t*str, const char*text)
378 str->len = strlen(text);
379 str->str = strdup(text);
381 int string_equals(string_t*str, const char*text)
383 int l = strlen(text);
384 if(str->len == l && !memcmp(str->str, text, l))
388 int string_equals2(string_t*str, string_t*str2)
390 if(str->len == str2->len && !memcmp(str->str, str2->str, str->len))
395 // ------------------------------- stringarray_t ------------------------------
397 typedef struct _stringlist {
399 struct _stringlist*next;
402 typedef struct _stringarray_internal_t
408 } stringarray_internal_t;
410 void stringarray_init(stringarray_t*sa, int hashsize)
412 stringarray_internal_t*s;
414 sa->internal = (stringarray_internal_t*)rfx_calloc(sizeof(stringarray_internal_t));
415 s = (stringarray_internal_t*)sa->internal;
417 s->hash = rfx_calloc(sizeof(stringlist_t*)*hashsize);
418 s->hashsize = hashsize;
420 void stringarray_put(stringarray_t*sa, string_t str)
422 stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
424 int hash = string_hash(&str) % s->hashsize;
426 char*ss = string_cstr(&str);
427 mem_put(&s->pos, &ss, sizeof(char*));
429 stringlist_t*l = rfx_alloc(sizeof(stringlist_t));
431 l->next = s->hash[hash];
436 char* stringarray_at(stringarray_t*sa, int pos)
438 stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
440 if(pos<0 || pos>=s->num)
442 p = *(char**)&s->pos.buffer[pos*sizeof(char*)];
447 string_t stringarray_at2(stringarray_t*sa, int pos)
450 s.str = stringarray_at(sa, pos);
451 s.len = s.str?strlen(s.str):0;
454 static stringlist_t* stringlist_del(stringarray_t*sa, stringlist_t*l, int index)
457 stringlist_t*old = l;
459 if(index==l->index) {
461 memset(l, 0, sizeof(stringlist_t));
471 fprintf(stderr, "Internal error: did not find string %d in hash\n", index);
475 void stringarray_del(stringarray_t*sa, int pos)
477 stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
478 string_t str = stringarray_at2(sa, pos);
479 int hash = string_hash(&str) % s->hashsize;
480 s->hash[hash] = stringlist_del(sa, s->hash[hash], pos);
481 *(char**)&s->pos.buffer[pos*sizeof(char*)] = 0;
483 int stringarray_find(stringarray_t*sa, string_t* str)
485 stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
486 int hash = string_hash(str) % s->hashsize;
488 stringlist_t*l = s->hash[hash];
491 string_t s = stringarray_at2(sa, l->index);
492 if(string_equals2(str, &s)) {
499 void stringarray_clear(stringarray_t*sa)
501 stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
504 for(t=0;t<s->hashsize;t++) {
505 stringlist_t*l = s->hash[t];
507 stringlist_t*next = l->next;
508 memset(l, 0, sizeof(stringlist_t));
513 rfx_free(s->hash);s->hash=0;
516 void stringarray_destroy(stringarray_t*sa)
518 stringarray_clear(sa);
522 // ------------------------------- type_t -------------------------------
524 char charptr_equals(const void*o1, const void*o2)
526 return !strcmp(o1,o2);
528 unsigned int charptr_hash(const void*o)
530 return string_hash2(o);
532 void* charptr_dup(const void*o)
536 void charptr_free(void*o)
540 char stringstruct_equals(const void*o1, const void*o2)
542 string_t*s1 = (string_t*)o1;
543 string_t*s2 = (string_t*)o2;
544 int l = s1->len<s2->len?s1->len:s2->len;
545 int r = memcmp(s1->str, s2->str, l);
549 return s1->len==s2->len;
551 unsigned int stringstruct_hash(const void*o)
553 return string_hash(o);
555 void*stringstruct_dup(const void*o)
557 string_t*s = malloc(sizeof(string_t));
558 string_set2(s, ((string_t*)o)->str, ((string_t*)o)->len);
561 void stringstruct_free(void*o)
563 rfx_free((void*)(((string_t*)o)->str));
568 type_t charptr_type = {
569 equals: charptr_equals,
575 type_t stringstruct_type = {
576 equals: stringstruct_equals,
577 hash: stringstruct_hash,
578 dup: stringstruct_dup,
579 free: stringstruct_free,
582 // ------------------------------- dictionary_t -------------------------------
584 #define INITIAL_SIZE 1
586 static int max(int x, int y) {
592 dict_t*d = rfx_alloc(sizeof(dict_t));
596 dict_t*dict_new2(type_t*t)
598 dict_t*d = rfx_alloc(sizeof(dict_t));
603 void dict_init(dict_t*h)
605 memset(h, 0, sizeof(dict_t));
606 h->hashsize = INITIAL_SIZE;
607 h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
609 h->key_type = &charptr_type;
612 static void dict_expand(dict_t*h, int newlen)
614 assert(h->hashsize < newlen);
615 dictentry_t**newslots = (dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*newlen);
617 for(t=0;t<h->hashsize;t++) {
618 dictentry_t*e = h->slots[t];
620 dictentry_t*next = e->next;
621 unsigned int newhash = e->hash%newlen;
622 e->next = newslots[newhash];
623 newslots[newhash] = e;
630 h->hashsize = newlen;
633 dictentry_t* dict_put(dict_t*h, const void*key, void* data)
635 unsigned int hash = h->key_type->hash(key);
636 dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
637 unsigned int hash2 = hash % h->hashsize;
639 e->key = h->key_type->dup(key);
640 e->hash = hash; //for resizing
641 e->next = h->slots[hash2];
647 void dict_put2(dict_t*h, const char*s, void*data)
649 assert(h->key_type == &charptr_type);
650 dict_put(h, s, data);
652 void dict_dump(dict_t*h, FILE*fi, const char*prefix)
655 for(t=0;t<h->hashsize;t++) {
656 dictentry_t*e = h->slots[t];
658 if(h->key_type==&charptr_type) {
659 fprintf(fi, "%s%08x=%08x\n", prefix, e->key, e->data);
661 fprintf(fi, "%s%s=%08x\n", prefix, e->key, e->data);
668 int dict_count(dict_t*h)
673 void* dict_lookup(dict_t*h, const void*key)
678 unsigned int ohash = h->key_type->hash(key);
679 unsigned int hash = ohash % h->hashsize;
681 /* check first entry for match */
682 dictentry_t*e = h->slots[hash];
683 if(e && h->key_type->equals(e->key, key)) {
689 /* if dict is 2/3 filled, double the size. Do
690 this the first time we have to actually iterate
691 through a slot to find our data */
692 if(e && h->num*3 >= h->hashsize*2) {
693 int newsize = h->hashsize;
694 while(h->num*3 >= newsize*2) {
695 newsize = newsize<15?15:(newsize+1)*2-1;
697 dict_expand(h, newsize);
698 hash = ohash % h->hashsize;
702 /* check subsequent entries for a match */
704 if(h->key_type->equals(e->key, key)) {
711 char dict_del(dict_t*h, const void*key)
715 unsigned int hash = h->key_type->hash(key) % h->hashsize;
716 dictentry_t*head = h->slots[hash];
717 dictentry_t*e = head, *prev=0;
719 if(h->key_type->equals(e->key, key)) {
720 dictentry_t*next = e->next;
721 rfx_free((void*)e->key);
722 memset(e, 0, sizeof(dictentry_t));
739 static dictentry_t* dict_get_slot(dict_t*h, const void*key)
743 unsigned int ohash = h->key_type->hash(key);
744 unsigned int hash = ohash % h->hashsize;
745 return h->slots[hash];
748 void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const void*key, void*val), void*data)
751 for(t=0;t<h->hashsize;t++) {
752 dictentry_t*e = h->slots[t];
754 dictentry_t*next = e->next;
756 runFunction(data, e->key, e->data);
762 void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
765 for(t=0;t<h->hashsize;t++) {
766 dictentry_t*e = h->slots[t];
768 dictentry_t*next = e->next;
770 runFunction(e->data);
777 void dict_free_all(dict_t*h, void (*freeFunction)(void*))
780 for(t=0;t<h->hashsize;t++) {
781 dictentry_t*e = h->slots[t];
783 dictentry_t*next = e->next;
784 h->key_type->free(e->key);
786 freeFunction(e->data);
788 memset(e, 0, sizeof(dictentry_t));
794 memset(h, 0, sizeof(dict_t));
797 void dict_clear(dict_t*h)
802 void dict_destroy(dict_t*dict)
808 // ------------------------------- map_t --------------------------------------
810 typedef struct _map_internal_t
815 void map_init(map_t*map)
818 map->internal = (map_internal_t*)rfx_calloc(sizeof(map_internal_t));
819 m = (map_internal_t*)map->internal;
822 void map_put(map_t*map, string_t t1, string_t t2)
824 map_internal_t*m = (map_internal_t*)map->internal;
826 char* s1 = string_cstr(&t1);
827 dict_put2(&m->d, s1, (void*)string_cstr(&t2));
830 const char* map_lookup(map_t*map, const char*name)
832 map_internal_t*m = (map_internal_t*)map->internal;
833 const char*value = dict_lookup(&m->d, name);
836 static void freestring(void*data)
840 static void dumpmapentry(void*data, const void*key, void*value)
842 FILE*fi = (FILE*)data;
843 fprintf(fi, "%s=%s\n", key, (char*)value);
845 void map_dump(map_t*map, FILE*fi, const char*prefix)
848 map_internal_t*m = (map_internal_t*)map->internal;
849 dict_foreach_keyvalue(&m->d, dumpmapentry, fi);
851 void map_clear(map_t*map)
853 map_internal_t*m = (map_internal_t*)map->internal;
854 dict_free_all(&m->d, freestring);
857 void map_destroy(map_t*map)
863 // ------------------------------- array_t --------------------------------------
865 array_t* array_new() {
866 array_t*d = malloc(sizeof(array_t));
867 memset(d, 0, sizeof(array_t));
868 d->entry2pos = dict_new();
871 array_t* array_new2(type_t*type) {
872 array_t*d = malloc(sizeof(array_t));
873 memset(d, 0, sizeof(array_t));
874 d->entry2pos = dict_new2(type);
877 void*array_getkey(array_t*array, int nr) {
878 if(nr > array->num || nr<0) {
879 printf("error: reference to element %d in array[%d]\n", nr, array->num);
883 return array->d[nr].name;
885 void*array_getvalue(array_t*array, int nr) {
886 if(nr > array->num || nr<0) {
887 printf("error: reference to element %d in array[%d]\n", nr, array->num);
891 return array->d[nr].data;
893 int array_append(array_t*array, const void*name, void*data) {
894 while(array->size <= array->num) {
897 array->d = malloc(sizeof(array_entry_t)*array->size);
899 array->d = realloc(array->d, sizeof(array_entry_t)*array->size);
903 dictentry_t*e = dict_put(array->entry2pos, name, (void*)(ptroff_t)(array->num+1));
906 array->d[array->num].name = e->key;
908 array->d[array->num].name = 0;
910 array->d[array->num].data = (void*)data;
913 int array_find(array_t*array, const void*name)
915 int pos = (int)(ptroff_t)dict_lookup(array->entry2pos, name);
918 int array_find2(array_t*array, const void*name, void*data)
920 dict_t*h= array->entry2pos;
921 dictentry_t*e = dict_get_slot(array->entry2pos, name);
924 int index = ((int)(ptroff_t)e->data) - 1;
925 if(h->key_type->equals(e->key, name) && array->d[index].data == data) {
932 int array_update(array_t*array, const void*name, void*data) {
933 int pos = array_find(array, name);
935 array->d[pos].data = data;
938 return array_append(array, name, data);
940 int array_append_if_new(array_t*array, const void*name, void*data) {
941 int pos = array_find(array, name);
944 return array_append(array, name, data);
946 void array_free(array_t*array) {
947 dict_destroy(array->entry2pos);
949 free(array->d);array->d = 0;
954 // ------------------------------- list_t --------------------------------------
957 typedef struct _listinfo {
959 struct _commonlist*last;
962 typedef struct _commonlist {
964 struct _commonlist*next;
968 int list_length(void*_list)
970 commonlist_t*l = (commonlist_t*)_list;
973 return l->info[0].size;
975 void list_append_(void*_list, void*entry)
977 commonlist_t**list = (commonlist_t**)_list;
980 n = malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
982 (*list)->info[0].size = 0;
984 n = malloc(sizeof(commonlist_t));
985 (*list)->info[0].last->next = n;
989 (*list)->info[0].last = n;
990 (*list)->info[0].size++;
992 void list_free_(void*_list)
994 commonlist_t**list = (commonlist_t**)_list;
995 commonlist_t*l = *list;
997 commonlist_t*next = l->next;
1003 void*list_clone_(void*_list)
1005 commonlist_t*l = *(commonlist_t**)_list;
1009 commonlist_t*next = l->next;
1010 list_append_(&dest, l->entry);