From 6ce701137e44f06b68e772d2b8cbaef72800cd31 Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Mon, 9 Nov 2009 18:02:10 -0800 Subject: Add hash table growth. --- ChangeLog | 10 ++++++++++ hash.c | 34 ++++++++++++++++++++++++++++++++-- hash.h | 2 +- 3 files changed, 43 insertions(+), 3 deletions(-) diff --git a/ChangeLog b/ChangeLog index a90801f0..e0cd1670 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,13 @@ +2009-11-06 Kaz Kylheku + + Add hash table growth. + + hash.c (hash_grow): New function. + (l_gethash): Renamed to gethash_l. Increment count; if load + factor gets to two, call hash_grow to double the size. + + hash.h (l_gethash): Declaration changed to gethash_l. + 2009-11-06 Kaz Kylheku Changing representation of objects to allow the NUM type to be diff --git a/hash.c b/hash.c index 05db2fdd..7516a128 100644 --- a/hash.c +++ b/hash.c @@ -189,6 +189,32 @@ static struct cobj_ops hash_ops = { hash_mark, }; +void hash_grow(struct hash *h) +{ + long i; + list_collect_decl (conses, ptr); + + bug_unless (h->modulus < LONG_MAX/2); + h->modulus *= 2; + vec_set_fill(h->table, num(h->modulus)); + + for (i = 0; i < h->modulus; i++) { + obj_t **pchain = vecref_l(h->table, num(i)); + list_collect_nconc(ptr, *pchain); + *pchain = nil; + } + + 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; + } +} + obj_t *make_hash(obj_t *weak_keys, obj_t *weak_vals) { int flags = ((weak_vals != nil) << 1) | (weak_keys != nil); @@ -201,11 +227,15 @@ obj_t *make_hash(obj_t *weak_keys, obj_t *weak_vals) return cobj((void *) h, hash_t, &hash_ops); } -obj_t **l_gethash(obj_t *hash, obj_t *key) +obj_t **gethash_l(obj_t *hash, obj_t *key) { struct hash *h = (struct hash *) hash->co.handle; obj_t **pchain = vecref_l(h->table, num(ll_hash(key) % h->modulus)); - return acons_new_l(pchain, key); + obj_t *old = *pchain; + obj_t **place = acons_new_l(pchain, key); + if (old != *pchain && ++h->count > 2 * h->modulus) + hash_grow(h); + return place; } obj_t *gethash(obj_t *hash, obj_t *key) diff --git a/hash.h b/hash.h index e5a1e510..0240546a 100644 --- a/hash.h +++ b/hash.h @@ -26,7 +26,7 @@ obj_t *hash_obj(obj_t *); obj_t *make_hash(obj_t *weak_keys, obj_t *weak_vals); -obj_t **l_gethash(obj_t *hash, obj_t *key); +obj_t **gethash_l(obj_t *hash, obj_t *key); obj_t *gethash(obj_t *hash, obj_t *key); void hash_process_weak(void); -- cgit v1.2.3