+typedef struct
+{
+ GHashTable *hash_table;
+ gpointer dummy1;
+ gpointer dummy2;
+ int position;
+ gboolean dummy3;
+ int version;
+} RealIter;
+
+G_STATIC_ASSERT (sizeof (GHashTableIter) == sizeof (RealIter));
+G_STATIC_ASSERT (_g_alignof (GHashTableIter) >= _g_alignof (RealIter));
+
+/* Each table size has an associated prime modulo (the first prime
+ * lower than the table size) used to find the initial bucket. Probing
+ * then works modulo 2^n. The prime modulo is necessary to get a
+ * good distribution with poor hash functions.
+ */
+static const gint prime_mod [] =
+{
+ 1, /* For 1 << 0 */
+ 2,
+ 3,
+ 7,
+ 13,
+ 31,
+ 61,
+ 127,
+ 251,
+ 509,
+ 1021,
+ 2039,
+ 4093,
+ 8191,
+ 16381,
+ 32749,
+ 65521, /* For 1 << 16 */
+ 131071,
+ 262139,
+ 524287,
+ 1048573,
+ 2097143,
+ 4194301,
+ 8388593,
+ 16777213,
+ 33554393,
+ 67108859,
+ 134217689,
+ 268435399,
+ 536870909,
+ 1073741789,
+ 2147483647 /* For 1 << 31 */
+};
+
+static void
+g_hash_table_set_shift (GHashTable *hash_table, gint shift)
+{
+ gint i;
+ guint mask = 0;
+
+ hash_table->size = 1 << shift;
+ hash_table->mod = prime_mod [shift];
+
+ for (i = 0; i < shift; i++)
+ {
+ mask <<= 1;
+ mask |= 1;
+ }
+
+ hash_table->mask = mask;
+}
+
+static gint
+g_hash_table_find_closest_shift (gint n)
+{
+ gint i;
+
+ for (i = 0; n; i++)
+ n >>= 1;
+
+ return i;
+}
+
+static void
+g_hash_table_set_shift_from_size (GHashTable *hash_table, gint size)
+{
+ gint shift;
+
+ shift = g_hash_table_find_closest_shift (size);
+ shift = MAX (shift, HASH_TABLE_MIN_SHIFT);
+
+ g_hash_table_set_shift (hash_table, shift);
+}
+
+/*
+ * g_hash_table_lookup_node:
+ * @hash_table: our #GHashTable
+ * @key: the key to lookup against
+ * @hash_return: key hash return location
+ *
+ * Performs a lookup in the hash table, preserving extra information
+ * usually needed for insertion.
+ *
+ * This function first computes the hash value of the key using the
+ * user's hash function.
+ *
+ * If an entry in the table matching @key is found then this function
+ * returns the index of that entry in the table, and if not, the
+ * index of an unused node (empty or tombstone) where the key can be
+ * inserted.
+ *
+ * The computed hash value is returned in the variable pointed to
+ * by @hash_return. This is to save insertions from having to compute
+ * the hash record again for the new record.
+ *
+ * Returns: index of the described node
+ */
+static inline guint
+g_hash_table_lookup_node (GHashTable *hash_table,
+ gconstpointer key,
+ guint *hash_return)
+{
+ guint node_index;
+ guint node_hash;
+ guint hash_value;
+ guint first_tombstone = 0;
+ gboolean have_tombstone = FALSE;
+ guint step = 0;
+
+ hash_value = hash_table->hash_func (key);
+ if (G_UNLIKELY (!HASH_IS_REAL (hash_value)))
+ hash_value = 2;
+
+ *hash_return = hash_value;
+
+ node_index = hash_value % hash_table->mod;
+ node_hash = hash_table->hashes[node_index];
+
+ while (!HASH_IS_UNUSED (node_hash))
+ {
+ /* We first check if our full hash values
+ * are equal so we can avoid calling the full-blown
+ * key equality function in most cases.
+ */
+ if (node_hash == hash_value)
+ {
+ gpointer node_key = hash_table->keys[node_index];
+
+ if (hash_table->key_equal_func)
+ {
+ if (hash_table->key_equal_func (node_key, key))
+ return node_index;
+ }
+ else if (node_key == key)
+ {
+ return node_index;
+ }
+ }
+ else if (HASH_IS_TOMBSTONE (node_hash) && !have_tombstone)
+ {
+ first_tombstone = node_index;
+ have_tombstone = TRUE;
+ }
+
+ step++;
+ node_index += step;
+ node_index &= hash_table->mask;
+ node_hash = hash_table->hashes[node_index];
+ }
+
+ if (have_tombstone)
+ return first_tombstone;
+
+ return node_index;
+}
+
+/*
+ * g_hash_table_remove_node:
+ * @hash_table: our #GHashTable
+ * @node: pointer to node to remove
+ * @notify: %TRUE if the destroy notify handlers are to be called
+ *
+ * Removes a node from the hash table and updates the node count.
+ * The node is replaced by a tombstone. No table resize is performed.
+ *
+ * If @notify is %TRUE then the destroy notify functions are called
+ * for the key and value of the hash node.
+ */
+static void
+g_hash_table_remove_node (GHashTable *hash_table,
+ gint i,
+ gboolean notify)
+{
+ gpointer key;
+ gpointer value;
+
+ key = hash_table->keys[i];
+ value = hash_table->values[i];
+
+ /* Erect tombstone */
+ hash_table->hashes[i] = TOMBSTONE_HASH_VALUE;
+
+ /* Be GC friendly */
+ hash_table->keys[i] = NULL;
+ hash_table->values[i] = NULL;
+
+ hash_table->nnodes--;
+
+ if (notify && hash_table->key_destroy_func)
+ hash_table->key_destroy_func (key);
+
+ if (notify && hash_table->value_destroy_func)
+ hash_table->value_destroy_func (value);
+
+}
+
+/*
+ * g_hash_table_remove_all_nodes:
+ * @hash_table: our #GHashTable
+ * @notify: %TRUE if the destroy notify handlers are to be called
+ *
+ * Removes all nodes from the table. Since this may be a precursor to
+ * freeing the table entirely, no resize is performed.
+ *
+ * If @notify is %TRUE then the destroy notify functions are called
+ * for the key and value of the hash node.
+ */
+static void
+g_hash_table_remove_all_nodes (GHashTable *hash_table,
+ gboolean notify)
+{
+ int i;
+ gpointer key;
+ gpointer value;
+
+ hash_table->nnodes = 0;
+ hash_table->noccupied = 0;
+
+ if (!notify ||
+ (hash_table->key_destroy_func == NULL &&
+ hash_table->value_destroy_func == NULL))
+ {
+ memset (hash_table->hashes, 0, hash_table->size * sizeof (guint));
+ memset (hash_table->keys, 0, hash_table->size * sizeof (gpointer));
+ memset (hash_table->values, 0, hash_table->size * sizeof (gpointer));
+
+ return;
+ }
+
+ for (i = 0; i < hash_table->size; i++)
+ {
+ if (HASH_IS_REAL (hash_table->hashes[i]))
+ {
+ key = hash_table->keys[i];
+ value = hash_table->values[i];
+
+ hash_table->hashes[i] = UNUSED_HASH_VALUE;
+ hash_table->keys[i] = NULL;
+ hash_table->values[i] = NULL;
+
+ if (hash_table->key_destroy_func != NULL)
+ hash_table->key_destroy_func (key);
+
+ if (hash_table->value_destroy_func != NULL)
+ hash_table->value_destroy_func (value);
+ }
+ else if (HASH_IS_TOMBSTONE (hash_table->hashes[i]))
+ {
+ hash_table->hashes[i] = UNUSED_HASH_VALUE;
+ }
+ }
+}
+
+/*
+ * g_hash_table_resize:
+ * @hash_table: our #GHashTable
+ *
+ * Resizes the hash table to the optimal size based on the number of
+ * nodes currently held. If you call this function then a resize will
+ * occur, even if one does not need to occur.
+ * Use g_hash_table_maybe_resize() instead.
+ *
+ * This function may "resize" the hash table to its current size, with
+ * the side effect of cleaning up tombstones and otherwise optimizing
+ * the probe sequences.
+ */
+static void
+g_hash_table_resize (GHashTable *hash_table)
+{
+ gpointer *new_keys;
+ gpointer *new_values;
+ guint *new_hashes;
+ gint old_size;
+ gint i;
+
+ old_size = hash_table->size;
+ g_hash_table_set_shift_from_size (hash_table, hash_table->nnodes * 2);
+
+ new_keys = g_new0 (gpointer, hash_table->size);
+ if (hash_table->keys == hash_table->values)
+ new_values = new_keys;
+ else
+ new_values = g_new0 (gpointer, hash_table->size);
+ new_hashes = g_new0 (guint, hash_table->size);
+
+ for (i = 0; i < old_size; i++)
+ {
+ guint node_hash = hash_table->hashes[i];
+ guint hash_val;
+ guint step = 0;
+
+ if (!HASH_IS_REAL (node_hash))
+ continue;
+
+ hash_val = node_hash % hash_table->mod;
+
+ while (!HASH_IS_UNUSED (new_hashes[hash_val]))
+ {
+ step++;
+ hash_val += step;
+ hash_val &= hash_table->mask;
+ }
+
+ new_hashes[hash_val] = hash_table->hashes[i];
+ new_keys[hash_val] = hash_table->keys[i];
+ new_values[hash_val] = hash_table->values[i];
+ }
+
+ if (hash_table->keys != hash_table->values)
+ g_free (hash_table->values);
+
+ g_free (hash_table->keys);
+ g_free (hash_table->hashes);
+
+ hash_table->keys = new_keys;
+ hash_table->values = new_values;
+ hash_table->hashes = new_hashes;
+
+ hash_table->noccupied = hash_table->nnodes;
+}
+
+/*
+ * g_hash_table_maybe_resize:
+ * @hash_table: our #GHashTable
+ *
+ * Resizes the hash table, if needed.
+ *
+ * Essentially, calls g_hash_table_resize() if the table has strayed
+ * too far from its ideal size for its number of nodes.
+ */
+static inline void
+g_hash_table_maybe_resize (GHashTable *hash_table)
+{
+ gint noccupied = hash_table->noccupied;
+ gint size = hash_table->size;
+
+ if ((size > hash_table->nnodes * 4 && size > 1 << HASH_TABLE_MIN_SHIFT) ||
+ (size <= noccupied + (noccupied / 16)))
+ g_hash_table_resize (hash_table);
+}