diff options
-rw-r--r-- | tanja.c | 160 | ||||
-rw-r--r-- | tanja.h | 4 | ||||
-rw-r--r-- | test/json.c | 2 | ||||
-rw-r--r-- | test/tuple.c | 44 |
4 files changed, 153 insertions, 57 deletions
@@ -160,9 +160,11 @@ void tn_el_free(tn_el el) { free(el.v.a); break; case TN_VT_MAP: - for(i=0; i<el.count; i++) { - free(el.v.m[i].key); - tn_el_free(el.v.m[i].val); + for(i=0; i<el.size; i++) { + if(el.v.m[i].key) { + free(el.v.m[i].key); + tn_el_free(el.v.m[i].val); + } } free(el.v.m); break; @@ -207,10 +209,13 @@ tn_el tn_el_copy(tn_el el) { r.v.a[i] = tn_el_copy(el.v.a[i]); break; case TN_VT_MAP: - r.v.m = malloc(el.count*sizeof(tn_map_el)); - for(i=0; i<el.count; i++) { - r.v.m[i].key = strdup(el.v.m[i].key); - r.v.m[i].val = tn_el_copy(el.v.m[i].val); + if(el.v.m) + r.v.m = malloc(el.size*sizeof(tn_map_el)); + for(i=0; i<el.size; i++) { + if(el.v.m[i].key) { + r.v.m[i].key = strdup(el.v.m[i].key); + r.v.m[i].val = tn_el_copy(el.v.m[i].val); + } } break; } @@ -346,51 +351,98 @@ void tn_array_append(tn_el *a, char *lst, ...) { } -tn_el tn_map_new(char *lst, ...) { - tn_el a; - a.count = a.size = strlen(lst); - a.type = TN_VT_MAP; - va_list va; - va_start(va, lst); - if(a.count) { - a.v.m = malloc(a.size*sizeof(tn_map_el)); - int i; - for(i=0; i<a.count; i++) { - a.v.m[i].key = va_arg(va, char *); - a.v.m[i].val = el_newv(lst[i], va); +// A map is implemented as a simple hash table using open addressing, linear +// probing and grows as soon as the table is 75% full. (3/4 is easy for integer +// calculation). Uses a string hash function provided by khash.h and +// power-of-two table sizes (it is assumes that the hash function is random +// enough). Uses key=NULL to indicate unused buckets. Deletion is not +// supported, so that simplifies things a bit. + +// Get the index of item with the given key. If the returned index' .key = +// NULL, then no such item exists and the index is the location where it should +// be inserted. Assumes the table is not full. +static inline int tn_map_getidx(tn_el m, const char *key) { + int i = kh_str_hash_func(key) & (m.size-1); + while(m.v.m[i].key && strcmp(key, m.v.m[i].key) != 0) + i = (i+1) & (m.size-1); + return i; +} + + +static inline void tn_map_grow(tn_el *m, int new) { + if(!m->count && !new) + return; + int s = m->size; + if(!s) + s = 32; + while(s < ((m->count+new)*4)/3) + s <<= 2; + assert(s < UINT16_MAX); // Might want to handle this + if(s == m->size) + return; + + // Now we'll have to grow. This is a simple yet not-very-space-efficient solution. + tn_el n = *m; + n.size = s; + n.v.m = calloc(n.size, sizeof(tn_map_el)); + int i; + for(i=0; i<m->size; i++) + if(m->v.m[i].key) { + int idx = tn_map_getidx(n, m->v.m[i].key); + n.v.m[idx].key = m->v.m[i].key; + n.v.m[idx].val = m->v.m[i].val; } + free(m->v.m); + *m = n; +} + + +// Frees and overwrites an previous item if there already was one with the same key. +static inline void tn_map_set_one(tn_el *m, char *key, tn_el val) { + int i = tn_map_getidx(*m, key); + if(m->v.m[i].key) { + free(m->v.m[i].key); + tn_el_free(m->v.m[i].val); } else - a.v.m = NULL; - va_end(va); - return a; + m->count++; + m->v.m[i].key = key; + m->v.m[i].val = val; } -static inline void tn_map_grow(tn_el *m, int new) { - if(m->count+new > m->size) { - m->size *= 2; - if(m->size < m->count+new) - m->size = m->count+new; - m->v.m = realloc(m->v.m, m->size*sizeof(tn_map_el)); +tn_el tn_map_new(int s, char *lst, ...) { + tn_el a; + a.type = TN_VT_MAP; + a.v.m = NULL; + a.size = a.count = 0; + + int len = strlen(lst); + if(s < len) + s = len; + tn_map_grow(&a, s); + + va_list va; + va_start(va, lst); + int i; + for(i=0; i<len; i++) { + char *k = va_arg(va, char *); + tn_map_set_one(&a, k, el_newv(lst[i], va)); } + va_end(va); + return a; } -// Appends key/values to the map. Currently doesn't overwrite existing keys, -// though it probably should. void tn_map_set(tn_el *m, char *lst, ...) { assert(m && m->type == TN_VT_MAP); - - int n = strlen(lst); - tn_map_grow(m, n); - + int len = strlen(lst); + tn_map_grow(m, len); va_list va; va_start(va, lst); int i; - for(i=0; i<n; i++) { - m->v.m[m->count].key = va_arg(va, char *); - m->v.m[m->count].val = el_newv(lst[i], va); - m->count++; + for(i=0; i<len; i++) { + char *k = va_arg(va, char *); + tn_map_set_one(m, k, el_newv(lst[i], va)); } va_end(va); } @@ -398,10 +450,9 @@ void tn_map_set(tn_el *m, char *lst, ...) { tn_el tn_map_get(tn_el m, const char *key) { assert(m.type == TN_VT_MAP); - int i; - for(i=0; i<m.count; i++) - if(strcmp(key, m.v.m[i].key) == 0) - return m.v.m[i].val; + int i = tn_map_getidx(m, key); + if(m.v.m[i].key) + return m.v.m[i].val; tn_el r; r.type = TN_VT_INV; return r; @@ -529,12 +580,15 @@ static void json_fmt_el(tn_el e, lbuf *buf) { break; case TN_VT_MAP: ac('{'); - for(i=0; i<e.count; i++) { - if(i) - ac(','); - json_fmt_string(e.v.m[i].key, buf); - ac(':'); - json_fmt_el(e.v.m[i].val, buf); + int p = 0; + for(i=0; i<e.size; i++) { + if(e.v.m[i].key) { + if(p++) + ac(','); + json_fmt_string(e.v.m[i].key, buf); + ac(':'); + json_fmt_el(e.v.m[i].val, buf); + } } ac('}'); break; @@ -805,7 +859,7 @@ err: static tn_el tn_json_parse_map(char **buf, int *len, int lvl) { con(1); // consume '{' character - tn_el el = tn_map_new(""); + tn_el el = tn_map_new(0, ""); int first = 1; while(1) { cons(); @@ -834,7 +888,6 @@ static tn_el tn_json_parse_map(char **buf, int *len, int lvl) { tn_el key = tn_json_parse_string(buf, len); if(!key.type) goto err; - el.v.m[el.count].key = key.v.s; // consume separator cons(); if(!*len || **buf != ':') { @@ -848,12 +901,13 @@ static tn_el tn_json_parse_map(char **buf, int *len, int lvl) { goto err; } // get value - el.v.m[el.count].val = tn_json_parse_val(buf, len, lvl); - if(!el.v.m[el.count].val.type) { + tn_el val = tn_json_parse_val(buf, len, lvl); + if(!val.type) { free(key.v.s); goto err; } - el.count++; + tn_map_grow(&el, 1); + tn_map_set_one(&el, key.v.s, val); } err: tn_el_free(el); @@ -59,7 +59,7 @@ struct tn_el { double n; char *s; // TODO: Allow statically allocated strings tn_el *a; - tn_map_el *m; // TODO: Hash table? Or ordered list to allow binary search? + tn_map_el *m; } v; }; @@ -104,7 +104,7 @@ double tn_el_num(tn_el); char *tn_el_str(tn_el, char *); tn_el tn_array_new(char *, ...); void tn_array_append(tn_el *, char *, ...); -tn_el tn_map_new(char *, ...); +tn_el tn_map_new(int, char *, ...); void tn_map_set(tn_el *, char *, ...); tn_el tn_map_get(tn_el, const char *); void tn_tuple_ref(tn_tuple *); diff --git a/test/json.c b/test/json.c index 7759aa8..821f786 100644 --- a/test/json.c +++ b/test/json.c @@ -125,7 +125,7 @@ static void test_tuples() { t("[ { } ]", "[{}]"); t("[{\"\":true}]", "[{\"\":1}]"); e("[{\"a\":null,\"b\":\"str\"}]"); - t("[{\"1\" : \"1\" , \"\\t\" \t : {} } ]", "[{\"1\":\"1\",\"\\t\":{}}]"); + t("[{\"1\" : \"1\" , \"\\t\" \t : {} } ]", "[{\"\\t\":{},\"1\":\"1\"}]"); // order depends on hash function f("[{1:2}]", 2); f("[{\"1\"}]", 5); f("[{\"\":}]", 5); diff --git a/test/tuple.c b/test/tuple.c index 0091f15..40da4aa 100644 --- a/test/tuple.c +++ b/test/tuple.c @@ -33,11 +33,12 @@ static int test_num = 0; #define t_assert(n) printf("%sok %d - " __FILE__ ":%d: " #n "\n", (n)?"":"not ", ++test_num, __LINE__) int main() { - tn_el e; + tn_el e, v; int64_t i; double d; char *s; char buf[25]; + int k; e = tn_el_new(TN_VT_INT, (int64_t)1023); t_assert(e.type == TN_VT_INT); @@ -104,6 +105,47 @@ int main() { t_assert(tn_el_num(e) == 1021.2); tn_el_free(e); + e = tn_map_new(0, "si", strdup("str"), strdup("strval"), strdup("int"), 42); + t_assert(e.type == TN_VT_MAP); + t_assert(e.count == 2); + v = tn_map_get(e, "str"); + t_assert(tn_el_isvalid(v)); + t_assert(v.type == TN_VT_STR); + t_assert(v.v.s && strcmp(v.v.s, "strval") == 0); + v = tn_map_get(e, "b"); + t_assert(!tn_el_isvalid(v)); + v = tn_map_get(e, "int"); + t_assert(tn_el_isvalid(v)); + t_assert(v.type == TN_VT_INT); + t_assert(v.v.i == 42); + tn_el_free(e); + + e = tn_map_new(0, ""); + t_assert(e.count == 0); + for(k=0; k<10000; k++) { + snprintf(buf, 25, "%d", k); + tn_map_set(&e, "i", strdup(buf), (int64_t)k); + } + t_assert(e.count == k); + v = tn_map_get(e, "1234"); + t_assert(tn_el_int(v) == 1234); + v = tn_map_get(e, "0"); + t_assert(tn_el_int(v) == 0); + v = tn_map_get(e, "9999"); + t_assert(tn_el_int(v) == 9999); + for(k=5000; k<15000; k++) { + snprintf(buf, 25, "%d", k); + tn_map_set(&e, "i", strdup(buf), (int64_t)(k*100)); + } + t_assert(e.count == k); + v = tn_map_get(e, "1234"); + t_assert(tn_el_int(v) == 1234); + v = tn_map_get(e, "9999"); + t_assert(tn_el_int(v) == 999900); + v = tn_map_get(e, "14999"); + t_assert(tn_el_int(v) == 1499900); + tn_el_free(e); + printf("1..%d\n", test_num); return 0; } |