summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--tanja.c160
-rw-r--r--tanja.h4
-rw-r--r--test/json.c2
-rw-r--r--test/tuple.c44
4 files changed, 153 insertions, 57 deletions
diff --git a/tanja.c b/tanja.c
index b361892..e41cd77 100644
--- a/tanja.c
+++ b/tanja.c
@@ -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);
diff --git a/tanja.h b/tanja.h
index 8a8f41e..a2a208a 100644
--- a/tanja.h
+++ b/tanja.h
@@ -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;
}