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 */
_______________________________________________
Minor mailing list
Minorred-bean.com
http:/
/www.red-bean.com/mailman/listinfo/minor
|