Add hash table growth.

3 files changed, 43 insertions, 3 deletions

diff --git a/ChangeLog b/ChangeLog
index a90801f0..e0cd1670 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,15 @@
 2009-11-06  Kaz Kylheku  <kkylheku@gmail.com>
 
+	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  <kkylheku@gmail.com>
+
 	Changing representation of objects to allow the NUM type to be
 	unboxed. If the lowest bit of the obj_t * pointer is 1, then
 	the remaining bits are a number. A lot of assumptions are made:
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);