+/* INTERFACE:
+
+ Hash tables are a technique used to implement mapping between
+ objects with near-constant-time access and storage. The table
+ associates keys to values, and a value can be very quickly
+ retrieved by providing the key. Fast lookup tables are typically
+ implemented as hash tables.
+
+ The entry points are
+ hash_table_new -- creates the table.
+ hash_table_destroy -- destroys the table.
+ hash_table_put -- establishes or updates key->value mapping.
+ hash_table_get -- retrieves value of key.
+ hash_table_get_pair -- get key/value pair for key.
+ hash_table_contains -- test whether the table contains key.
+ hash_table_remove -- remove key->value mapping for given key.
+ hash_table_for_each -- call function for each table entry.
+ hash_table_iterate -- iterate over entries in hash table.
+ hash_table_iter_next -- return next element during iteration.
+ hash_table_clear -- clear hash table contents.
+ hash_table_count -- return the number of entries in the table.
+
+ The hash table grows internally as new entries are added and is not
+ limited in size, except by available memory. The table doubles
+ with each resize, which ensures that the amortized time per
+ operation remains constant.
+
+ If not instructed otherwise, tables created by hash_table_new
+ consider the keys to be equal if their pointer values are the same.
+ You can use make_string_hash_table to create tables whose keys are
+ considered equal if their string contents are the same. In the
+ general case, the criterion of equality used to compare keys is
+ specified at table creation time with two callback functions,
+ "hash" and "test". The hash function transforms the key into an
+ arbitrary number that must be the same for two equal keys. The
+ test function accepts two keys and returns non-zero if they are to
+ be considered equal.
+
+ Note that neither keys nor values are copied when inserted into the
+ hash table, so they must exist for the lifetime of the table. This
+ means that e.g. the use of static strings is OK, but objects with a
+ shorter life-time probably need to be copied (with strdup() or the
+ like in the case of strings) before being inserted. */
+
+/* IMPLEMENTATION:
+
+ The hash table is implemented as an open-addressed table with
+ linear probing collision resolution.
+
+ The above means that all the cells (each cell containing a key and
+ a value pointer) are stored in a contiguous array. Array position
+ of each cell is determined by the hash value of its key and the
+ size of the table: location := hash(key) % size. If two different
+ keys end up on the same position (collide), the one that came
+ second is stored in the first unoccupied cell that follows it.
+ This collision resolution technique is called "linear probing".
+
+ There are more advanced collision resolution methods (quadratic
+ probing, double hashing), but we don't use them because they incur
+ more non-sequential access to the array, which results in worse CPU
+ cache behavior. Linear probing works well as long as the
+ count/size ratio (fullness) is kept below 75%. We make sure to
+ grow and rehash the table whenever this threshold is exceeded.
+
+ Collisions complicate deletion because simply clearing a cell
+ followed by previously collided entries would cause those neighbors
+ to not be picked up by find_cell later. One solution is to leave a
+ "tombstone" marker instead of clearing the cell, and another is to
+ recalculate the positions of adjacent cells. We take the latter
+ approach because it results in less bookkeeping garbage and faster
+ retrieval at the (slight) expense of deletion. */
+
+/* Maximum allowed fullness: when hash table's fullness exceeds this
+ value, the table is resized. */
+#define HASH_MAX_FULLNESS 0.75
+
+/* The hash table size is multiplied by this factor (and then rounded
+ to the next prime) with each resize. This guarantees infrequent
+ resizes. */
+#define HASH_RESIZE_FACTOR 2
+
+struct cell {