[Minor] [minor commit] r669 - trunk/include/minor

[jimb at red-bean.com]

Author: jimb
Date: Tue Oct 24 05:25:45 2006
New Revision: 669

Modified:
   trunk/include/minor/hash-tables.h

Log:
First cut at hash table iteration interface.


Modified: trunk/include/minor/hash-tables.h
==============================================================================
--- trunk/include/minor/hash-tables.h	(original)
+++ trunk/include/minor/hash-tables.h	Tue Oct 24 05:25:45 2006
@@ -48,4 +48,87 @@
    If SRC and DEST are not both hash tables, abort.  */
 void mn_hash_table_merge (mn_call_t *, mn_ref_t *dest, mn_ref_t *src);
 
+
+/* A hash table iterator represents a subset of entries in a hash
+   table.  There are five essential operations used with iterators:
+
+   - Given a hash table, you can call mn_hash_table_iter to get an
+     iterator representing all its entries.
+
+   - If an iterator represents a non-empty subset of a table's
+     entries, it has a "current entry".  Given the iterator and the
+     table, you can get the current entry's key and value with
+     mn_hash_iter_key and mn_hash_iter_value.  If the iterator is
+     empty, these functions return NULL.
+
+     The hash table implementation gets to pick the "current entry"
+     from the iterator's subset however it pleases.  However, a given
+     iterator's current entry doesn't change unless the hash table
+     itself does.
+
+   - Given an iterator I, you can get a new iterator J whose subset is
+     the same as I, but with the current entry removed.
+     mn_hash_iter_next does this, and frees I.
+
+   - You can free an iterator with mn_free_hash_iter.
+
+   This means you can loop over the entries of a hash table H in a
+   call C with code like this:
+
+     mn_hash_iter_t *i;
+     mn_ref_t *key;
+
+     for (i = mn_hash_table_iter (C, H);
+          key = mn_hash_iter_key (C, H, i);
+          i = mn_hash_iter_next (C, H, i))
+       ...;
+     mn_free_hash_iter (C, H, i);
+
+   You could just as well use mn_hash_iter_value in the loop's
+   condition.
+
+   Adding entries to or removing entries from a hash table doesn't
+   invalidate iterators on that hash table, but it may change the
+   subsets they refer to arbitrarily, which is just as bad.  (These
+   operations could cause the hash table to be resized, which scatters
+   entries about arbitrarily.  As far as I can tell, Python
+   dictionaries have the same restriction, so I'm assuming it's not
+   fatal; if that's not so, let me know.)
+
+   I'm torn: in the current implementation of hash tables, iterators
+   are just integers; we cast back and forth between mn_hash_iter_t *
+   and an integer type, so there's really no storage behind it at all.
+   mn_free_hash_iter is a no-op.  But that may not always be so, and
+   we don't want to commit to a particular representation; hash tables
+   with buckets, for example, would need something more complex.  */
+
+/* The type of an iterator over a hash table.  */
+typedef struct mn_hash_iter_t mn_hash_iter_t;
+
+/* Return an iterator representing all entries in TABLE.  If TABLE is
+   not a hash table, abort.  */
+mn_hash_iter_t *mn_hash_table_iter (mn_call *, mn_ref_t *table);
+
+/* If ITER's subset of TABLE is not empty, return the key / value of
+   ITER's current entry.  If ITER's subset is entry, return NULL.  If
+   TABLE is not a hash table, abort.  */
+mn_ref_t *mn_hash_iter_key (mn_call_t *, mn_ref_t *table, 
+                            mn_hash_iter_t *iter);
+mn_ref_t *mn_hash_iter_value (mn_call_t *, mn_ref_t *table,
+                              mn_hash_iter_t *iter);
+
+/* Free ITER, and return a new iterator representing the same subset
+   of TABLE's entries that ITER did, but with ITER's current entry
+   removed.  */
+mn_hash_iter_t *mn_hash_iter_next (mn_call_t *, mn_ref_t *table,
+                                   mn_hash_iter_t *iter);
+
+/* Return a new iterator representing the same subset of TABLE as ITER.  */
+mn_hash_iter_t *mn_copy_hash_iter (mn_call_t *, mn_ref_t *table,
+                                   mn_hash_iter_t *iter);
+
+/* Free ITER.  */
+void mn_free_hash_iter (mn_call_t *, mn_ref_t *table, mn_hash_iter_t *iter);
+
+
 #endif /* MN_HASH_H */