Trie compression. Hash table iteration.

Bugfix in typeof.

* filter.c (trie_compress): New function.
(trie_value_at, trie_lookup_feed_char, filter_string): Handle cons cell
nodes in trie.
(build_filter): Call trie_compress.

* gc.c (cobj_destroy_op): Function renamed to cobj_destroy_stub_op
since it doesn't do anything.
(cobj_destroy_free_op): New function.
* hash.c (struct hash_iter): New type.
(hash_destroy): Function removed.
(hash_ops): Reference to hash_destroy replaced with
cobj_destroy_free_op.
(hash_count, hash_iter_mark, hash_begin, hash_next): New functions.
(hash_iter_ops): New static structure.
* hash.h (hash_count, hash_begin, hash_next): New functions declared.
* lib.c (hash_iter_s): New symbol variable.
(typeof): Bugfix: TAG_LIT type tag not handled.
(vecref): New function.
(obj_init): Initialize hash_iter_s.
* lib.h (cobj_destroy_op): Declaration renamed.
(cobj_destroy_free_op, vecref): New functions declared.
(hash_iter_s): New variable declared.
* stream.c (string_in_ops, byte_in_ops): cobj_destroy_op
renamed to cobj_destroy_stub_op.

1 files changed, 54 insertions, 6 deletions

diff --git a/hash.c b/hash.c
index dcd28011..e07ebf56 100644
--- a/hash.c
+++ b/hash.c
@@ -54,6 +54,12 @@ struct hash {
   val userdata;
 };
 
+struct hash_iter {
+  val hash;
+  cnum chain;
+  val cons;
+};
+
 /*
  * Dynamic list built up during gc.
  */
@@ -132,11 +138,6 @@ val hash_obj(val obj)
   return num(ll_hash(obj));
 }
 
-static void hash_destroy(val hash)
-{
-  free(hash->co.handle);
-}
-
 static void hash_mark(val hash)
 {
   struct hash *h = (struct hash *) hash->co.handle;
@@ -190,7 +191,7 @@ static void hash_mark(val hash)
 static struct cobj_ops hash_ops = {
   cobj_equal_op,
   cobj_print_op,
-  hash_destroy,
+  cobj_destroy_free_op,
   hash_mark,
   cobj_hash_op
 };
@@ -287,6 +288,12 @@ val remhash(val hash, val key)
   return nil;
 }
 
+val hash_count(val hash)
+{
+  struct hash *h = (struct hash *) hash->co.handle;
+  return num(h->count);
+}
+
 val get_hash_userdata(val hash)
 {
   struct hash *h = (struct hash *) hash->co.handle;
@@ -306,6 +313,47 @@ val hashp(val obj)
   return typeof(obj) == hash_s ? t : nil;
 }
 
+static void hash_iter_mark(val hash_iter)
+{
+  struct hash_iter *hi = (struct hash_iter *) hash_iter->co.handle;
+  gc_mark(hi->hash);
+  gc_mark(hi->cons);
+}
+
+static struct cobj_ops hash_iter_ops = {
+  cobj_equal_op,
+  cobj_print_op,
+  cobj_destroy_free_op,
+  hash_iter_mark,
+  cobj_hash_op
+};
+
+val hash_begin(val hash)
+{
+  struct hash_iter *hi = (struct hash_iter *) chk_malloc(sizeof *hi);
+  hi->hash = hash;
+  hi->chain = -1;
+  hi->cons = nil;
+  return cobj((mem_t *) hi, hash_iter_s, &hash_iter_ops);
+}
+
+val hash_next(val *iter)
+{
+  struct hash_iter *hi = (struct hash_iter *) (*iter)->co.handle;
+  val hash = hi->hash;
+  struct hash *h = (struct hash *) hash->co.handle;
+  if (hi->cons)
+    hi->cons = cdr(hi->cons);
+  while (nullp(hi->cons)) {
+    if (++hi->chain >= h->modulus) {
+      *iter = nil;
+      return nil;
+    }
+    hi->cons = vecref(h->table, num(hi->chain));
+  }
+  return car(hi->cons);
+}
+
 /*
  * Called from garbage collector. Hash module must process all weak tables
  * that were visited during the marking phase, maintained in the list