From 2f62f352f603b837a5cf032c257531052530c410 Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Tue, 10 Nov 2009 13:17:25 -0800 Subject: hash.c (hash_grow): Rewritten to avoid resizing the vector in place, and thus having to pulling all conses into a big list. TODO: avoid recomputing the hash function over the keys. We could enhance cons cells with two more fields without using additional storage. --- ChangeLog | 8 ++++++++ hash.c | 35 +++++++++++++++++++---------------- 2 files changed, 27 insertions(+), 16 deletions(-) diff --git a/ChangeLog b/ChangeLog index 4ed23e2b..2799b9b2 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,11 @@ +2009-11-10 Kaz Kylheku + + hash.c (hash_grow): Rewritten to avoid resizing the vector + in place, and thus having to pulling all conses into a big list. + TODO: avoid recomputing the hash function over the keys. + We could enhance cons cells with two more fields without using + additional storage. + 2009-11-06 Kaz Kylheku Changing representation of objects to allow for unboxed characters. diff --git a/hash.c b/hash.c index 390d7662..8acf7a5e 100644 --- a/hash.c +++ b/hash.c @@ -192,27 +192,30 @@ static struct cobj_ops hash_ops = { void hash_grow(struct hash *h) { long i; - list_collect_decl (conses, ptr); + long new_modulus = 2 * h->modulus; + obj_t *new_table = vector(num(new_modulus)); - bug_unless (h->modulus < LONG_MAX/2); - h->modulus *= 2; - vec_set_fill(h->table, num(h->modulus)); + bug_unless (new_modulus > h->modulus); + + vec_set_fill(new_table, num(new_modulus)); for (i = 0; i < h->modulus; i++) { - obj_t **pchain = vecref_l(h->table, num(i)); - list_collect_nconc(ptr, *pchain); - *pchain = nil; + obj_t *conses = *vecref_l(h->table, num(i)); + + while (conses) { + obj_t *entry = car(conses); + obj_t *next = cdr(conses); + obj_t *key = car(entry); + obj_t **pchain = vecref_l(new_table, + num(ll_hash(key) % new_modulus)); + *cdr_l(conses) = *pchain; + *pchain = conses; + conses = next; + } } - while (conses) { - obj_t *entry = car(conses); - obj_t *next = cdr(conses); - obj_t *key = car(entry); - obj_t **pchain = vecref_l(h->table, num(ll_hash(key) % h->modulus)); - *cdr_l(conses) = *pchain; - *pchain = conses; - conses = next; - } + h->modulus = new_modulus; + h->table = new_table; } obj_t *make_hash(obj_t *weak_keys, obj_t *weak_vals) -- cgit v1.2.3