#include <stdlib.h>
#include <stdio.h>
+#include <stdarg.h>
#include <string.h>
#include <assert.h>
#include <memory.h>
{
return strdup_n(string, len);
}
+char* allocprintf(const char*format, ...)
+{
+ va_list arglist1;
+ va_start(arglist1, format);
+ char dummy;
+ int l = vsnprintf(&dummy, 1, format, arglist1);
+ va_end(arglist1);
+
+ va_list arglist2;
+ va_start(arglist2, format);
+ char*buf = malloc(l+1);
+ vsnprintf(buf, l+1, format, arglist2);
+ va_end(arglist2);
+ return buf;
+}
// ------------------------------- mem_t --------------------------------------
int n = m->pos;
m->pos += length + (null?1:0);
if(m->pos > m->len) {
- m->len = (m->pos+63)&~63;
+ int v1 = (m->pos+63)&~63;
+ int v2 = m->len + m->len / 2;
+ m->len = v1>v2?v1:v2;
m->buffer = m->buffer?(char*)rfx_realloc(m->buffer,m->len):(char*)rfx_alloc(m->len);
}
assert(n+length <= m->len);
{
return mem_put_(m, str.str, str.len, 1);
}
+int mem_get(mem_t*m, void*data, int length)
+{
+ if(m->read_pos + length > m->pos) {
+ length = m->pos - m->read_pos;
+ }
+ memcpy(data, m->buffer+m->read_pos, length);
+ m->read_pos += length;
+ return length;
+}
// ------------------------------- ringbuffer_t -------------------------------
// ------------------------------- heap_t -------------------------------
-void heap_init(heap_t*h,int n,int elem_size, int(*compare)(const void *, const void *))
+void heap_init(heap_t*h,int elem_size, int(*compare)(const void *, const void *))
{
memset(h, 0, sizeof(heap_t));
- h->max_size = n;
h->size = 0;
h->elem_size = elem_size;
h->compare = compare;
- h->elements = (void**)rfx_calloc(n*sizeof(void*));
- h->data = (char*)rfx_calloc(h->max_size*h->elem_size);
+ h->elements = 0;
+ h->max_size = 0;
+}
+heap_t* heap_new(int elem_size, int(*compare)(const void *, const void *))
+{
+ heap_t*h = malloc(sizeof(heap_t));
+ heap_init(h, elem_size, compare);
+ return h;
+}
+heap_t* heap_clone(heap_t*o)
+{
+ heap_t*h = malloc(sizeof(heap_t));
+ memcpy(h, o, sizeof(heap_t));
+ h->elements = rfx_alloc(sizeof(void*)*h->size);
+ int t;
+ for(t=0;t<h->size;t++) {
+ h->elements[t] = rfx_alloc(h->elem_size);
+ memcpy(h->elements[t], o->elements[t], h->elem_size);
+ }
+ return h;
}
void heap_clear(heap_t*h)
{
+ int t;
+ for(t=0;t<h->size;t++) {
+ rfx_free(h->elements[t]);
+ h->elements[t]=0;
+ }
rfx_free(h->elements);
- rfx_free(h->data);
+}
+void heap_destroy(heap_t*h)
+{
+ heap_clear(h);
+ free(h);
}
-#define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))>0)
+#define HEAP_NODE_LARGER(h,node1,node2) ((h)->compare((node1),(node2))>0)
+#define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))<0)
static void up(heap_t*h, int node)
{
void*node_p = h->elements[node];
int parent = node;
+ int tmp = node;
do {
node = parent;
if(!node) break;
parent = (node-1)/2;
h->elements[node] = h->elements[parent];
- } while(HEAP_NODE_SMALLER(h,h->elements[parent], node_p));
-
+ } while(HEAP_NODE_SMALLER(h, h->elements[parent], node_p));
h->elements[node] = node_p;
}
static void down(heap_t*h, int node)
void heap_put(heap_t*h, void*e)
{
int pos = h->size++;
- memcpy(&h->data[pos*h->elem_size],e,h->elem_size);
- h->elements[pos] = &h->data[pos];
+ void*data = rfx_alloc(h->elem_size);
+ memcpy(data,e,h->elem_size);
+
+ if(pos>=h->max_size) {
+ h->max_size = h->max_size<15?15:(h->max_size+1)*2-1;
+ h->elements = (void**)rfx_realloc(h->elements, h->max_size*sizeof(void*));
+ assert(pos<h->max_size);
+ }
+
+ h->elements[pos] = data;
up(h, pos);
}
int heap_size(heap_t*h)
{
return h->size;
}
-void* heap_max(heap_t*h)
+void* heap_peek(heap_t*h)
{
+ if(!h || !h->size)
+ return 0;
return h->elements[0];
}
void* heap_chopmax(heap_t*h)
{
+ if(!h->size)
+ return 0;
void*p = h->elements[0];
h->elements[0] = h->elements[--h->size];
down(h,0);
}
void** heap_flatten(heap_t*h)
{
- void**nodes = (void**)rfx_alloc(h->size*sizeof(void*));
+ void**nodes = (void**)rfx_alloc((h->size+1)*sizeof(void*));
void**p = nodes;
while(h->size) {
printf("\n");*/
*p++ = heap_chopmax(h);
}
+ *p++ = 0;
return nodes;
}
+// ------------------------------- trie --------------------------------------
+
+trie_t*trie_new()
+{
+ return (trie_t*)rfx_calloc(sizeof(trie_t));
+}
+static char _trie_put(trielayer_t**t, unsigned const char*id, void*data)
+{
+ if(!*t) {
+ (*t) = rfx_calloc(sizeof(trielayer_t));
+ (*t)->rest = (unsigned char*)strdup(id);
+ (*t)->data = data;
+ return 0;
+ }
+ if((*t)->rest && (*t)->rest[0]) {
+ // make room: shift whatever's currently in here one node down
+ _trie_put(&(*t)->row[(*t)->rest[0]], (*t)->rest+1, (*t)->data);
+ (*t)->rest = 0;
+ }
+ if(id[0]) {
+ return _trie_put(&(*t)->row[id[0]], id+1, data);
+ } else {
+ char overwrite = 0;
+ if((*t)->rest)
+ overwrite = 1;
+ (*t)->rest = strdup("");
+ (*t)->data = data;
+ return overwrite;
+ }
+}
+static char _trie_remove(trielayer_t*t, unsigned const char*id)
+{
+ while(t) {
+ if(t->rest && !strcmp(t->rest, id)) {
+ free(t->rest);
+ t->rest = 0;
+ return 1;
+ }
+ if(!*id)
+ return 0;
+ t = t->row[*id++];
+ }
+ return 0;
+}
+
+static void trie_rollback_removes(trie_t*t, unsigned const char*id, void*data);
+static void trie_rollback_adds(trie_t*t, unsigned const char*id, void*data);
+
+void trie_put(trie_t*t, unsigned const char*id, void*data)
+{
+ if(!t->rollback) {
+ _trie_put(&t->start, id, data);
+ } else {
+ char contains = trie_contains(t, id);
+ void*olddata = contains?trie_lookup(t, id):0;
+ _trie_put(&t->start, id, data);
+ if(contains) {
+ trie_rollback_adds(t, id, olddata);
+ }
+ trie_rollback_removes(t, id, data);
+ }
+}
+char trie_remove(trie_t*t, unsigned const char*id)
+{
+ if(!t->rollback) {
+ return _trie_remove(t->start, id);
+ } else {
+ void*olddata = trie_lookup(t, id);
+ char exists = _trie_remove(t->start, id);
+ if(exists) {
+ trie_rollback_adds(t, id, olddata);
+ }
+ return exists;
+ }
+}
+int trie_contains(trie_t*trie, unsigned const char*id)
+{
+ trielayer_t*t = trie->start;
+ while(t) {
+ if(t->rest && !strcmp(t->rest, id))
+ return 1;
+ if(!*id)
+ return 0;
+ t = t->row[*id++];
+ }
+ return 0;
+}
+void* trie_lookup(trie_t*trie, unsigned const char*id)
+{
+ trielayer_t*t = trie->start;
+ while(t) {
+ if(t->rest && !strcmp(t->rest, id))
+ return t->data;
+ if(!*id)
+ return 0;
+ t = t->row[*id++];
+ }
+ return 0;
+}
+
+typedef struct _triememory {
+ const unsigned char*key;
+ void*data;
+ char del; // 0/1
+ struct _triememory*next;
+} triememory_t;
+
+typedef struct _trierollback {
+ triememory_t*ops;
+ struct _trierollback*prev;
+} trierollback_t;
+
+static void trie_rollback_adds(trie_t*t, unsigned const char*id, void*data)
+{
+ trierollback_t*rollback = (trierollback_t*)t->rollback;
+ triememory_t*m = (triememory_t*)rfx_calloc(sizeof(triememory_t));
+ m->key = id;
+ m->data = data;
+ m->del = 0;
+ m->next = rollback->ops;
+ rollback->ops = m;
+}
+static void trie_rollback_removes(trie_t*t, unsigned const char*id, void*data)
+{
+ trierollback_t*rollback = (trierollback_t*)t->rollback;
+ triememory_t*m = (triememory_t*)rfx_calloc(sizeof(triememory_t));
+ m->key = id;
+ m->data = data;
+ m->del = 1;
+ m->next = rollback->ops;
+ rollback->ops = m;
+}
+
+void _trie_dump(trielayer_t*t, char*buffer, int pos)
+{
+ int i;
+ for(i=0;i<256;i++) {
+ if(t->row[i]) {
+ buffer[pos]=i;
+ _trie_dump(t->row[i], buffer, pos+1);
+ }
+ }
+ if(t->rest) {
+ buffer[pos]=0;
+ printf("%s%s %08x\n", buffer, t->rest, t->data);
+ }
+}
+
+void trie_dump(trie_t*t)
+{
+ char buffer[256];
+ _trie_dump(t->start, buffer, 0);
+}
+
+
+void trie_remember(trie_t*t)
+{
+ trierollback_t*old = (trierollback_t*)t->rollback;
+ t->rollback = (trierollback_t*)rfx_calloc(sizeof(trierollback_t));
+ ((trierollback_t*)t->rollback)->prev = old;
+}
+
+void trie_rollback(trie_t*t)
+{
+ trierollback_t*rollback = (trierollback_t*)t->rollback;
+ if(!rollback) {
+ fprintf(stderr, "Internal error: can't roll back this trie any further\n");
+ return;
+ }
+ t->rollback = ((trierollback_t*)t->rollback)->prev;
+
+ triememory_t*op = rollback->ops;
+ while(op) {
+ triememory_t*next = op->next;
+ if(op->del) {
+ if(!_trie_remove(t->start, op->key)) {
+ fprintf(stderr, "Internal error: can't delete key %s in trie during rollback\n", op->key);
+ }
+ } else {
+ if(_trie_put(&t->start, op->key, op->data)) {
+ fprintf(stderr, "Internal error: overwrote key %s in trie during rollback\n", op->key);
+ }
+ }
+ free(op);
+ op = next;
+ }
+}
+
+
// ------------------------------- crc32 --------------------------------------
-static unsigned int*crc32 = 0;
+static unsigned int crc32[256];
+static char crc32_initialized=0;
static void crc32_init(void)
{
int t;
- if(crc32)
+ if(crc32_initialized)
return;
- crc32= (unsigned int*)rfx_alloc(sizeof(unsigned int)*256);
+ crc32_initialized = 1;
for(t=0; t<256; t++) {
unsigned int c = t;
int s;
s.str = text;
return s;
}
+string_t* string_new3(const char*text, int len)
+{
+ if(!text) {
+ string_t*s = malloc(sizeof(string_t));
+ s->len = 0;
+ s->str = 0;
+ return s;
+ } else {
+ string_t*s = malloc(sizeof(string_t)+len+1);
+ s->len = len;
+ s->str = (const char*)(s+1);
+ memcpy((char*)s->str, text, len);
+ ((char*)s->str)[len]=0;
+ return s;
+ }
+}
+string_t* string_new4(const char*text)
+{
+ int l = strlen(text);
+ return string_new3(text, l);
+}
+
+void string_free(string_t*s)
+{
+ if(!s)
+ return;
+ s->len = 0;
+ if((string_t*)(s->str) == s+1) {
+ s->str = 0;
+ rfx_free(s);
+ } else {
+ rfx_free((char*)(s->str));
+ s->str = 0;
+ rfx_free(s);
+ }
+}
char* string_cstr(string_t*str)
{
return strdup_n(str->str, str->len);
}
+char* string_escape(string_t*str)
+{
+ int t;
+ int len = 0;
+ for(t=0;t<str->len;t++) {
+ if(str->str[t]<0x20)
+ len+=3;
+ else
+ len++;
+ }
+ char*s = malloc(len+1);
+ char*p=s;
+ for(t=0;t<str->len;t++) {
+ if(str->str[t]<0x20) {
+ *p++ ='\\';
+ unsigned char c = str->str[t];
+ *p++ = "0123456789abcdef"[c>>4];
+ *p++ = "0123456789abcdef"[c&0x0f];
+ } else {
+ *p++ = str->str[t];
+ }
+ }
+ *p++ = 0;
+ assert(p == &s[len+1]);
+ return s;
+}
unsigned int crc32_add_byte(unsigned int checksum, unsigned char b)
{
- if(!crc32)
- crc32_init();
+ crc32_init();
return checksum>>8 ^ crc32[(b^checksum)&0xff];
}
unsigned int crc32_add_string(unsigned int checksum, const char*s)
{
+ crc32_init();
if(!s)
return checksum;
while(*s) {
- checksum = crc32_add_byte(checksum, *s);
+ checksum = checksum>>8 ^ crc32[(*s^checksum)&0xff];
s++;
}
return checksum;
{
int t;
unsigned int checksum = 0;
- if(!crc32)
- crc32_init();
+ crc32_init();
for(t=0;t<str->len;t++) {
checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff];
}
{
unsigned int checksum = 0;
const char*p = str;
- if(!crc32)
- crc32_init();
+ crc32_init();
while(*p) {
checksum = checksum>>8 ^ crc32[(*p^checksum)&0xff];
p++;
}
unsigned int ptr_hash(const void*o)
{
- return string_hash3(o, sizeof(o));
+ return string_hash3((const char*)&o, sizeof(o));
}
void* ptr_dup(const void*o)
{
char stringstruct_equals(const void*o1, const void*o2)
{
+ if(!o1 || !o2)
+ return o1==o2;
string_t*s1 = (string_t*)o1;
string_t*s2 = (string_t*)o2;
int l = s1->len<s2->len?s1->len:s2->len;
}
unsigned int stringstruct_hash(const void*o)
{
+ if(!o) return 0;
return string_hash(o);
}
-void*stringstruct_dup(const void*o)
+string_t*string_dup3(string_t*o)
{
- string_t*s = malloc(sizeof(string_t));
- string_set2(s, ((string_t*)o)->str, ((string_t*)o)->len);
+ if(!o) return 0;
+ if(!o->str) {
+ string_t*s = malloc(sizeof(string_t));
+ s->str=0;
+ s->len=0;
+ return s;
+ }
+ string_t*s = rfx_alloc(sizeof(string_t)+o->len+1);
+ s->len = o->len;
+ s->str = (const char*)(s+1);
+ memcpy((char*)s->str, o->str, s->len);
+ ((char*)s->str)[s->len]=0;
return s;
}
void stringstruct_free(void*o)
{
- rfx_free((void*)(((string_t*)o)->str));
- rfx_free((void*)o);
+ if(o)
+ string_free(o);
}
type_t ptr_type = {
type_t stringstruct_type = {
equals: stringstruct_equals,
hash: stringstruct_hash,
- dup: stringstruct_dup,
+ dup: (dup_func)string_dup3,
free: stringstruct_free,
};
h->num = 0;
h->key_type = &charptr_type;
}
+void dict_init2(dict_t*h, type_t*t, int size)
+{
+ memset(h, 0, sizeof(dict_t));
+ h->hashsize = size;
+ h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
+ h->num = 0;
+ h->key_type = t;
+}
dict_t*dict_clone(dict_t*o)
{
{
unsigned int hash = h->key_type->hash(key);
dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
+
+ if(!h->hashsize)
+ dict_expand(h, 1);
+
unsigned int hash2 = hash % h->hashsize;
e->key = h->key_type->dup(key);
return h->num;
}
-void* dict_lookup(dict_t*h, const void*key)
+static inline dictentry_t* dict_do_lookup(dict_t*h, const void*key)
{
- if(!h->num)
+ if(!h->num) {
return 0;
+ }
unsigned int ohash = h->key_type->hash(key);
unsigned int hash = ohash % h->hashsize;
/* check first entry for match */
dictentry_t*e = h->slots[hash];
if(e && h->key_type->equals(e->key, key)) {
- return e->data;
+ return e;
} else if(e) {
e = e->next;
}
dict_expand(h, newsize);
hash = ohash % h->hashsize;
e = h->slots[hash];
+ if(e && h->key_type->equals(e->key, key)) {
+ // omit move to front
+ return e;
+ } else if(e) {
+ e = e->next;
+ }
}
/* check subsequent entries for a match */
+ dictentry_t*last = h->slots[hash];
while(e) {
if(h->key_type->equals(e->key, key)) {
- return e->data;
+ /* move to front- makes a difference of about 10% in most applications */
+ last->next = e->next;
+ e->next = h->slots[hash];
+ h->slots[hash] = e;
+ return e;
}
+ last=e;
e = e->next;
}
return 0;
}
+void* dict_lookup(dict_t*h, const void*key)
+{
+ dictentry_t*e = dict_do_lookup(h, key);
+ if(e)
+ return e->data;
+ return 0;
+}
+char dict_contains(dict_t*h, const void*key)
+{
+ dictentry_t*e = dict_do_lookup(h, key);
+ return !!e;
+}
+
char dict_del(dict_t*h, const void*key)
{
if(!h->num)
while(e) {
if(h->key_type->equals(e->key, key)) {
dictentry_t*next = e->next;
- rfx_free((void*)e->key);
+ h->key_type->free(e->key);
memset(e, 0, sizeof(dictentry_t));
rfx_free(e);
if(e == head) {
- h->slots[hash] = 0;
+ h->slots[hash] = next;
} else {
assert(prev);
prev->next = next;
}
}
-void dict_free_all(dict_t*h, void (*freeFunction)(void*))
+void dict_free_all(dict_t*h, char free_keys, void (*free_data_function)(void*))
{
int t;
for(t=0;t<h->hashsize;t++) {
dictentry_t*e = h->slots[t];
while(e) {
dictentry_t*next = e->next;
- h->key_type->free(e->key);
- if(freeFunction) {
- freeFunction(e->data);
+ if(free_keys) {
+ h->key_type->free(e->key);
+ }
+ if(free_data_function) {
+ free_data_function(e->data);
}
memset(e, 0, sizeof(dictentry_t));
rfx_free(e);
memset(h, 0, sizeof(dict_t));
}
+void dict_clear_shallow(dict_t*h)
+{
+ dict_free_all(h, 0, 0);
+}
+
void dict_clear(dict_t*h)
{
- dict_free_all(h, 0);
+ dict_free_all(h, 1, 0);
+}
+
+void dict_destroy_shallow(dict_t*dict)
+{
+ dict_clear_shallow(dict);
+ rfx_free(dict);
}
void dict_destroy(dict_t*dict)
{
+ if(!dict)
+ return;
dict_clear(dict);
rfx_free(dict);
}
void map_clear(map_t*map)
{
map_internal_t*m = (map_internal_t*)map->internal;
- dict_free_all(&m->d, freestring);
+ dict_free_all(&m->d, 1, freestring);
rfx_free(m);
}
void map_destroy(map_t*map)
void*array_getkey(array_t*array, int nr) {
if(nr > array->num || nr<0) {
printf("error: reference to element %d in array[%d]\n", nr, array->num);
- *(int*)0 = 0xdead;
return 0;
}
return array->d[nr].name;
void*array_getvalue(array_t*array, int nr) {
if(nr > array->num || nr<0) {
printf("error: reference to element %d in array[%d]\n", nr, array->num);
- *(int*)0 = 0xdead;
return 0;
}
return array->d[nr].data;
return 0;
return l->info[0].size;
}
+void list_concat_(void*_l1, void*_l2)
+{
+ commonlist_t**l1 = (commonlist_t**)_l1;
+ commonlist_t**l2 = (commonlist_t**)_l2;
+
+ if(!*l1) {
+ *l1 = *l2;
+ } else if(*l2) {
+ (*l1)->info[0].last->next = *l2;
+ (*l1)->info[0].last = (*l2)->info[0].last;
+ (*l1)->info[0].size += (*l2)->info[0].size;
+ }
+ *l2 = 0;
+}
void list_append_(void*_list, void*entry)
{
commonlist_t**list = (commonlist_t**)_list;
}
*list = 0;
}
+void list_deep_free_(void*_list)
+{
+ commonlist_t**list = (commonlist_t**)_list;
+ commonlist_t*l = *list;
+ while(l) {
+ commonlist_t*next = l->next;
+ if(l->entry) {
+ free(l->entry);l->entry=0;
+ }
+ free(l);
+ l = next;
+ }
+ *list = 0;
+}
void*list_clone_(void*_list)
{
commonlist_t*l = *(commonlist_t**)_list;
return dest;
}
+
git.asbjorn.biz / swftools.git / blobdiff