diff options
Diffstat (limited to 'ht.c')
| -rw-r--r-- | ht.c | 32 |
1 files changed, 26 insertions, 6 deletions
@@ -10,7 +10,7 @@ #define FNV_PRIME 0x01000193 // fnv-1a -uint32_t hash(char *s, size_t len) { +uint32_t hash_string(char *s, size_t len) { uint32_t h = FNV_BASIS; for(int i = 0; i < len; i++) { h ^= s[i]; @@ -25,8 +25,10 @@ Ht ht_new() { static HtEntry *find(HtEntry *b, size_t cap, ObjString *k) { size_t ix = k->hash % cap; + if (cap == 0) return NULL; for (;;) { HtEntry *ent = &b[ix]; + // XXX tombstones if (ent->k == k || ent->k == NULL) { return ent; } @@ -34,6 +36,25 @@ static HtEntry *find(HtEntry *b, size_t cap, ObjString *k) { } } +ObjString *ht_findstring(State *S, Ht *h, char *s, size_t len, uint32_t hash) { + const size_t cap = h->cap; + if (cap == 0) return NULL; + size_t ix = hash % cap; + + for (;;) { + HtEntry *ent = &h->d[ix]; + // XXX tombstones + if (ent->k == NULL) + return NULL; + else if (ent->k->hash == hash + && ent->k->len == len + && memcmp(ent->k->d, s, len) == 0) + return ent->k; + + ix = (ix+1)%cap; + } +} + static void grow(State *S, Ht *h) { HtEntry *old = h->d; size_t newsz = h->cap == 0 ? 8 : h->cap * 2; @@ -74,12 +95,11 @@ void ht_put(State *S, Ht *h, ObjString *k, Val v) { Val ht_get(State *S, Ht *h, ObjString *k) { HtEntry *ent = find(h->d, h->cap, k); - if (ent->k == NULL) { + if (ent == NULL) + return VAL_NIL; + else if (ent->k == NULL) return VAL_NIL; - } else { + else return ent->v; - } } - - |