#include <assert.h>
#include <memory.h>
#include "mem.h"
+#include "types.h"
#include "q.h"
// ------------------------------- malloc, alloc routines ---------------------
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 -------------------------------
return nodes;
}
+// ------------------------------- trie --------------------------------------
+
+void trie_put(trie_t**t, unsigned const char*id)
+{
+ if(!*t) {
+ (*t) = rfx_calloc(sizeof(trie_t));
+ (*t)->rest = (unsigned char*)strdup(id);
+ return;
+ }
+ if((*t)->rest && (*t)->rest[0]) {
+ // shift whatever's currently in here one node down
+ trie_put(&(*t)->row[(*t)->rest[0]], (*t)->rest+1);
+ (*t)->rest = 0;
+ }
+ if(id[0]) {
+ trie_put(&(*t)->row[id[0]], id+1);
+ } else {
+ (*t)->rest = "";
+ }
+}
+
+int trie_lookup(trie_t*t, unsigned const char*id)
+{
+ while(t) {
+ if(t->rest && !strcmp(t->rest, id))
+ return 1;
+ t = t->row[id[0]];
+ if(!*id)
+ return 0;
+ id++;
+ }
+ return 0;
+}
+
// ------------------------------- crc32 --------------------------------------
static unsigned int*crc32 = 0;
static void crc32_init(void)
}
void string_set(string_t*str, const char*text)
{
- str->len = strlen(text);
+ if(text) {
+ str->len = strlen(text);
+ } else {
+ str->len = 0;
+ }
str->str = text;
}
string_t string_new(const char*text, int len)
string_t string_new2(const char*text)
{
string_t s;
- s.len = strlen(text);
+ if(text) {
+ s.len = strlen(text);
+ } else {
+ s.len = 0;
+ }
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);
}
-unsigned int string_hash(string_t*str)
+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();
+ return checksum>>8 ^ crc32[(b^checksum)&0xff];
+}
+unsigned int crc32_add_string(unsigned int checksum, const char*s)
+{
+ if(!crc32)
+ crc32_init();
+ if(!s)
+ return checksum;
+ while(*s) {
+ checksum = checksum>>8 ^ crc32[(*s^checksum)&0xff];
+ s++;
+ }
+ return checksum;
+}
+
+unsigned int string_hash(const string_t*str)
{
int t;
unsigned int checksum = 0;
rfx_free(sa);
}
+// ------------------------------- type_t -------------------------------
+
+char ptr_equals(const void*o1, const void*o2)
+{
+ return o1==o2;
+}
+unsigned int ptr_hash(const void*o)
+{
+ return string_hash3((const char*)&o, sizeof(o));
+}
+void* ptr_dup(const void*o)
+{
+ return (void*)o;
+}
+void ptr_free(void*o)
+{
+ return;
+}
+
+char charptr_equals(const void*o1, const void*o2)
+{
+ if(!o1 || !o2)
+ return o1==o2;
+ return !strcmp(o1,o2);
+}
+unsigned int charptr_hash(const void*o)
+{
+ if(!o)
+ return 0;
+ return string_hash2(o);
+}
+void* charptr_dup(const void*o)
+{
+ if(!o)
+ return 0;
+ return strdup(o);
+}
+void charptr_free(void*o)
+{
+ if(o) {
+ rfx_free(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;
+ int r = memcmp(s1->str, s2->str, l);
+ if(r)
+ return 0;
+ else
+ return s1->len==s2->len;
+}
+unsigned int stringstruct_hash(const void*o)
+{
+ if(!o) return 0;
+ return string_hash(o);
+}
+string_t*string_dup3(string_t*o)
+{
+ 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)
+{
+ if(o)
+ string_free(o);
+}
+
+type_t ptr_type = {
+ equals: ptr_equals,
+ hash: ptr_hash,
+ dup: ptr_dup,
+ free: ptr_free,
+};
+
+type_t charptr_type = {
+ equals: charptr_equals,
+ hash: charptr_hash,
+ dup: charptr_dup,
+ free: charptr_free,
+};
+
+type_t stringstruct_type = {
+ equals: stringstruct_equals,
+ hash: stringstruct_hash,
+ dup: (dup_func)string_dup3,
+ free: stringstruct_free,
+};
// ------------------------------- dictionary_t -------------------------------
-#define INITIAL_SIZE 63
+#define INITIAL_SIZE 1
+
+static int max(int x, int y) {
+ return x>y?x:y;
+}
dict_t*dict_new()
{
dict_t*d = rfx_alloc(sizeof(dict_t));
- dict_init(d);
+ dict_init(d, INITIAL_SIZE);
return d;
}
-void dict_init(dict_t*h)
+dict_t*dict_new2(type_t*t)
+{
+ dict_t*d = rfx_alloc(sizeof(dict_t));
+ dict_init(d, INITIAL_SIZE);
+ d->key_type = t;
+ return d;
+}
+void dict_init(dict_t*h, 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 = &charptr_type;
+}
+void dict_init2(dict_t*h, type_t*t, int size)
{
memset(h, 0, sizeof(dict_t));
- h->hashsize = INITIAL_SIZE;
+ 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)
+{
+ dict_t*h = rfx_alloc(sizeof(dict_t));
+ memcpy(h, o, sizeof(dict_t));
+ h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
+ int t;
+ for(t=0;t<o->hashsize;t++) {
+ dictentry_t*e = o->slots[t];
+ while(e) {
+ dictentry_t*n = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
+ memcpy(n, e, sizeof(dictentry_t));
+ n->key = h->key_type->dup(e->key);
+ n->data = e->data;
+ n->next = h->slots[t];
+ h->slots[t] = n;
+ e = e->next;
+ }
+ }
+ return h;
}
+
static void dict_expand(dict_t*h, int newlen)
{
assert(h->hashsize < newlen);
h->slots = newslots;
h->hashsize = newlen;
}
-void dict_put(dict_t*h, string_t s, void* data)
+
+dictentry_t* dict_put(dict_t*h, const void*key, void* data)
{
- unsigned int hash = string_hash(&s);
+ unsigned int hash = h->key_type->hash(key);
dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
-
- unsigned int hash2 = string_hash(&s) % h->hashsize;
- char*sdata = rfx_alloc(s.len);
- memcpy(sdata, s.str, s.len);
- e->s = sdata;
- e->len = s.len;
+ unsigned int hash2 = hash % h->hashsize;
+
+ e->key = h->key_type->dup(key);
e->hash = hash; //for resizing
e->next = h->slots[hash2];
e->data = data;
h->slots[hash2] = e;
h->num++;
+ return e;
}
void dict_put2(dict_t*h, const char*s, void*data)
{
- string_t s2;
- string_set(&s2, s);
- dict_put(h, s2, data);
-}
-void dict_put3(dict_t*h, const char* s, int len, void*data)
-{
- string_t s3;
- string_set2(&s3, s, len);
- dict_put(h, s3, data);
+ assert(h->key_type == &charptr_type);
+ dict_put(h, s, data);
}
void dict_dump(dict_t*h, FILE*fi, const char*prefix)
{
for(t=0;t<h->hashsize;t++) {
dictentry_t*e = h->slots[t];
while(e) {
- char*s = strdup_n(e->s, e->len);
- fprintf(fi, "%s%s=%08x\n", prefix, e->s, e->data);
- rfx_free(s);
+ if(h->key_type!=&charptr_type) {
+ fprintf(fi, "%s%08x=%08x\n", prefix, e->key, e->data);
+ } else {
+ fprintf(fi, "%s%s=%08x\n", prefix, e->key, e->data);
+ }
e = e->next;
}
}
}
+
int dict_count(dict_t*h)
{
return h->num;
}
-void* dict_lookup2(dict_t*h, const char*s, int len)
+
+static inline dictentry_t* dict_do_lookup(dict_t*h, const void*key)
{
- if(!h->num)
+ if(!h->num) {
return 0;
-
- if(h->num*3 >= h->hashsize*2) {
- /* if dict is 2/3 filled, double the size */
- dict_expand(h, (h->hashsize+1)*2-1);
}
-
- unsigned int ohash = string_hash2(s);
+
+ 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;
+ } else if(e) {
+ e = e->next;
+ }
+
+ /* if dict is 2/3 filled, double the size. Do
+ this the first time we have to actually iterate
+ through a slot to find our data */
+ if(e && h->num*3 >= h->hashsize*2) {
+ int newsize = h->hashsize;
+ while(h->num*3 >= newsize*2) {
+ newsize = newsize<15?15:(newsize+1)*2-1;
+ }
+ 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(e->len == len && !memcmp(e->s, s, len)) {
- return e->data;
+ if(h->key_type->equals(e->key, key)) {
+ /* 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 char*s)
+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)
{
- int l = strlen(s);
- return dict_lookup2(h, s, l);
+ dictentry_t*e = dict_do_lookup(h, key);
+ return !!e;
}
-char dict_del(dict_t*h, const char*s)
+
+char dict_del(dict_t*h, const void*key)
{
if(!h->num)
return 0;
- unsigned int hash = string_hash2(s) % h->hashsize;
- int l = strlen(s);
+ unsigned int hash = h->key_type->hash(key) % h->hashsize;
dictentry_t*head = h->slots[hash];
dictentry_t*e = head, *prev=0;
while(e) {
- if(e->len ==l && !memcmp(e->s, s, l)) {
+ if(h->key_type->equals(e->key, key)) {
dictentry_t*next = e->next;
- rfx_free((void*)e->s);
+ rfx_free((void*)e->key);
memset(e, 0, sizeof(dictentry_t));
rfx_free(e);
if(e == head) {
}
return 0;
}
-void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const char*key, void*val), void*data)
+
+dictentry_t* dict_get_slot(dict_t*h, const void*key)
+{
+ if(!h->num)
+ return 0;
+ unsigned int ohash = h->key_type->hash(key);
+ unsigned int hash = ohash % h->hashsize;
+ return h->slots[hash];
+}
+
+void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const void*key, void*val), void*data)
{
int t;
for(t=0;t<h->hashsize;t++) {
while(e) {
dictentry_t*next = e->next;
if(runFunction) {
- char*s = strdup_n(e->s, e->len); //append \0
- runFunction(data, s, e->data);
- rfx_free(s);
+ runFunction(data, e->key, e->data);
}
e = e->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;
- rfx_free((void*)e->s);
- 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);
e = next;
}
+ h->slots[t]=0;
}
rfx_free(h->slots);
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)
{
dict_clear(dict);
map_internal_t*m;
map->internal = (map_internal_t*)rfx_calloc(sizeof(map_internal_t));
m = (map_internal_t*)map->internal;
- dict_init(&m->d);
+ dict_init(&m->d, INITIAL_SIZE);
}
void map_put(map_t*map, string_t t1, string_t t2)
{
{
rfx_free(data);
}
-static void dumpmapentry(void*data, const char*key, void*value)
+static void dumpmapentry(void*data, const void*key, void*value)
{
FILE*fi = (FILE*)data;
fprintf(fi, "%s=%s\n", key, (char*)value);
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)
rfx_free(map);
}
+// ------------------------------- array_t --------------------------------------
+
+array_t* array_new() {
+ array_t*d = malloc(sizeof(array_t));
+ memset(d, 0, sizeof(array_t));
+ d->entry2pos = dict_new();
+ return d;
+}
+array_t* array_new2(type_t*type) {
+ array_t*d = malloc(sizeof(array_t));
+ memset(d, 0, sizeof(array_t));
+ d->entry2pos = dict_new2(type);
+ return d;
+}
+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);
+ 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);
+ return 0;
+ }
+ return array->d[nr].data;
+}
+int array_append(array_t*array, const void*name, void*data) {
+ while(array->size <= array->num) {
+ array->size += 64;
+ if(!array->d) {
+ array->d = malloc(sizeof(array_entry_t)*array->size);
+ } else {
+ array->d = realloc(array->d, sizeof(array_entry_t)*array->size);
+ }
+ }
+
+ dictentry_t*e = dict_put(array->entry2pos, name, (void*)(ptroff_t)(array->num+1));
+
+ if(name) {
+ array->d[array->num].name = e->key;
+ } else {
+ array->d[array->num].name = 0;
+ }
+ array->d[array->num].data = (void*)data;
+ return array->num++;
+}
+int array_find(array_t*array, const void*name)
+{
+ int pos = (int)(ptroff_t)dict_lookup(array->entry2pos, name);
+ return pos-1;
+}
+int array_find2(array_t*array, const void*name, void*data)
+{
+ dict_t*h= array->entry2pos;
+ dictentry_t*e = dict_get_slot(array->entry2pos, name);
+
+ while(e) {
+ int index = ((int)(ptroff_t)e->data) - 1;
+ if(h->key_type->equals(e->key, name) && array->d[index].data == data) {
+ return index;
+ }
+ e = e->next;
+ }
+ return -1;
+}
+int array_update(array_t*array, const void*name, void*data) {
+ int pos = array_find(array, name);
+ if(pos>=0) {
+ array->d[pos].data = data;
+ return pos;
+ }
+ return array_append(array, name, data);
+}
+int array_append_if_new(array_t*array, const void*name, void*data) {
+ int pos = array_find(array, name);
+ if(pos>=0)
+ return pos;
+ return array_append(array, name, data);
+}
+void array_free(array_t*array) {
+ dict_destroy(array->entry2pos);
+ if(array->d) {
+ free(array->d);array->d = 0;
+ }
+ free(array);
+}
+
+// ------------------------------- list_t --------------------------------------
+
+struct _commonlist;
+typedef struct _listinfo {
+ int size;
+ struct _commonlist*last;
+} listinfo_t;
+
+typedef struct _commonlist {
+ void*entry;
+ struct _commonlist*next;
+ listinfo_t info[0];
+} commonlist_t;
+
+int list_length_(void*_list)
+{
+ commonlist_t*l = (commonlist_t*)_list;
+ if(!l)
+ 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;
+ commonlist_t* n = 0;
+ if(!*list) {
+ n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
+ *list = n;
+ (*list)->info[0].size = 0;
+ } else {
+ n = malloc(sizeof(commonlist_t));
+ (*list)->info[0].last->next = n;
+ }
+ n->next = 0;
+ n->entry = entry;
+ (*list)->info[0].last = n;
+ (*list)->info[0].size++;
+}
+/* notice: prepending uses slighly more space than appending */
+void list_prepend_(void*_list, void*entry)
+{
+ commonlist_t**list = (commonlist_t**)_list;
+ commonlist_t* n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
+ int size = 0;
+ commonlist_t* last = 0;
+ if(*list) {
+ last = (*list)->info[0].last;
+ size = (*list)->info[0].size;
+ }
+ n->next = *list;
+ n->entry = entry;
+ *list = n;
+ (*list)->info[0].last = last;
+ (*list)->info[0].size = size+1;
+}
+void list_free_(void*_list)
+{
+ commonlist_t**list = (commonlist_t**)_list;
+ commonlist_t*l = *list;
+ while(l) {
+ commonlist_t*next = l->next;
+ free(l);
+ l = next;
+ }
+ *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;
+
+ void*dest = 0;
+ while(l) {
+ commonlist_t*next = l->next;
+ list_append_(&dest, l->entry);
+ l = next;
+ }
+ return dest;
+
+}