+/**
+ * g_hash_table_iter_init:
+ * @iter: an uninitialized #GHashTableIter
+ * @hash_table: a #GHashTable
+ *
+ * Initializes a key/value pair iterator and associates it with
+ * @hash_table. Modifying the hash table after calling this function
+ * invalidates the returned iterator.
+ * |[<!-- language="C" -->
+ * GHashTableIter iter;
+ * gpointer key, value;
+ *
+ * g_hash_table_iter_init (&iter, hash_table);
+ * while (g_hash_table_iter_next (&iter, &key, &value))
+ * {
+ * // do something with key and value
+ * }
+ * ]|
+ *
+ * Since: 2.16
+ */
+void
+g_hash_table_iter_init (GHashTableIter *iter,
+ GHashTable *hash_table)
+{
+ RealIter *ri = (RealIter *) iter;
+
+ g_return_if_fail (iter != NULL);
+ g_return_if_fail (hash_table != NULL);
+
+ ri->hash_table = hash_table;
+ ri->position = -1;
+#ifndef G_DISABLE_ASSERT
+ ri->version = hash_table->version;
+#endif
+}
+
+/**
+ * g_hash_table_iter_next:
+ * @iter: an initialized #GHashTableIter
+ * @key: (allow-none): a location to store the key, or %NULL
+ * @value: (allow-none): a location to store the value, or %NULL
+ *
+ * Advances @iter and retrieves the key and/or value that are now
+ * pointed to as a result of this advancement. If %FALSE is returned,
+ * @key and @value are not set, and the iterator becomes invalid.
+ *
+ * Returns: %FALSE if the end of the #GHashTable has been reached.
+ *
+ * Since: 2.16
+ */
+gboolean
+g_hash_table_iter_next (GHashTableIter *iter,
+ gpointer *key,
+ gpointer *value)
+{
+ RealIter *ri = (RealIter *) iter;
+ gint position;
+
+ g_return_val_if_fail (iter != NULL, FALSE);
+#ifndef G_DISABLE_ASSERT
+ g_return_val_if_fail (ri->version == ri->hash_table->version, FALSE);
+#endif
+ g_return_val_if_fail (ri->position < ri->hash_table->size, FALSE);
+
+ position = ri->position;
+
+ do
+ {
+ position++;
+ if (position >= ri->hash_table->size)
+ {
+ ri->position = position;
+ return FALSE;
+ }
+ }
+ while (!HASH_IS_REAL (ri->hash_table->hashes[position]));
+
+ if (key != NULL)
+ *key = ri->hash_table->keys[position];
+ if (value != NULL)
+ *value = ri->hash_table->values[position];
+
+ ri->position = position;
+ return TRUE;
+}
+
+/**
+ * g_hash_table_iter_get_hash_table:
+ * @iter: an initialized #GHashTableIter
+ *
+ * Returns the #GHashTable associated with @iter.
+ *
+ * Returns: the #GHashTable associated with @iter.
+ *
+ * Since: 2.16
+ */
+GHashTable *
+g_hash_table_iter_get_hash_table (GHashTableIter *iter)
+{
+ g_return_val_if_fail (iter != NULL, NULL);
+
+ return ((RealIter *) iter)->hash_table;
+}
+
+static void
+iter_remove_or_steal (RealIter *ri, gboolean notify)
+{
+ g_return_if_fail (ri != NULL);
+#ifndef G_DISABLE_ASSERT
+ g_return_if_fail (ri->version == ri->hash_table->version);
+#endif
+ g_return_if_fail (ri->position >= 0);
+ g_return_if_fail (ri->position < ri->hash_table->size);
+
+ g_hash_table_remove_node (ri->hash_table, ri->position, notify);
+
+#ifndef G_DISABLE_ASSERT
+ ri->version++;
+ ri->hash_table->version++;
+#endif
+}
+
+/**
+ * g_hash_table_iter_remove:
+ * @iter: an initialized #GHashTableIter
+ *
+ * Removes the key/value pair currently pointed to by the iterator
+ * from its associated #GHashTable. Can only be called after
+ * g_hash_table_iter_next() returned %TRUE, and cannot be called
+ * more than once for the same key/value pair.
+ *
+ * If the #GHashTable was created using g_hash_table_new_full(),
+ * the key and value are freed using the supplied destroy functions,
+ * otherwise you have to make sure that any dynamically allocated
+ * values are freed yourself.
+ *
+ * It is safe to continue iterating the #GHashTable afterward:
+ * |[<!-- language="C" -->
+ * while (g_hash_table_iter_next (&iter, &key, &value))
+ * {
+ * if (condition)
+ * g_hash_table_iter_remove (&iter);
+ * }
+ * ]|
+ *
+ * Since: 2.16
+ */
+void
+g_hash_table_iter_remove (GHashTableIter *iter)
+{
+ iter_remove_or_steal ((RealIter *) iter, TRUE);
+}
+
+/*
+ * g_hash_table_insert_node:
+ * @hash_table: our #GHashTable
+ * @node_index: pointer to node to insert/replace
+ * @key_hash: key hash
+ * @key: (allow-none): key to replace with, or %NULL
+ * @value: value to replace with
+ * @keep_new_key: whether to replace the key in the node with @key
+ * @reusing_key: whether @key was taken out of the existing node
+ *
+ * Inserts a value at @node_index in the hash table and updates it.
+ *
+ * If @key has been taken out of the existing node (ie it is not
+ * passed in via a g_hash_table_insert/replace) call, then @reusing_key
+ * should be %TRUE.
+ *
+ * Returns: %TRUE if the key did not exist yet
+ */
+static gboolean
+g_hash_table_insert_node (GHashTable *hash_table,
+ guint node_index,
+ guint key_hash,
+ gpointer new_key,
+ gpointer new_value,
+ gboolean keep_new_key,
+ gboolean reusing_key)
+{
+ gboolean already_exists;
+ guint old_hash;
+ gpointer key_to_free = NULL;
+ gpointer value_to_free = NULL;
+
+ old_hash = hash_table->hashes[node_index];
+ already_exists = HASH_IS_REAL (old_hash);
+
+ /* Proceed in three steps. First, deal with the key because it is the
+ * most complicated. Then consider if we need to split the table in
+ * two (because writing the value will result in the set invariant
+ * becoming broken). Then deal with the value.
+ *
+ * There are three cases for the key:
+ *
+ * - entry already exists in table, reusing key:
+ * free the just-passed-in new_key and use the existing value
+ *
+ * - entry already exists in table, not reusing key:
+ * free the entry in the table, use the new key
+ *
+ * - entry not already in table:
+ * use the new key, free nothing
+ *
+ * We update the hash at the same time...
+ */
+ if (already_exists)
+ {
+ /* Note: we must record the old value before writing the new key
+ * because we might change the value in the event that the two
+ * arrays are shared.
+ */
+ value_to_free = hash_table->values[node_index];
+
+ if (keep_new_key)
+ {
+ key_to_free = hash_table->keys[node_index];
+ hash_table->keys[node_index] = new_key;
+ }
+ else
+ key_to_free = new_key;
+ }
+ else
+ {
+ hash_table->hashes[node_index] = key_hash;
+ hash_table->keys[node_index] = new_key;
+ }
+
+ /* Step two: check if the value that we are about to write to the
+ * table is the same as the key in the same position. If it's not,
+ * split the table.
+ */
+ if (G_UNLIKELY (hash_table->keys == hash_table->values && hash_table->keys[node_index] != new_value))
+ hash_table->values = g_memdup (hash_table->keys, sizeof (gpointer) * hash_table->size);
+
+ /* Step 3: Actually do the write */
+ hash_table->values[node_index] = new_value;
+
+ /* Now, the bookkeeping... */
+ if (!already_exists)
+ {
+ hash_table->nnodes++;
+
+ if (HASH_IS_UNUSED (old_hash))
+ {
+ /* We replaced an empty node, and not a tombstone */
+ hash_table->noccupied++;
+ g_hash_table_maybe_resize (hash_table);
+ }
+
+#ifndef G_DISABLE_ASSERT
+ hash_table->version++;
+#endif
+ }
+
+ if (already_exists)
+ {
+ if (hash_table->key_destroy_func && !reusing_key)
+ (* hash_table->key_destroy_func) (key_to_free);
+ if (hash_table->value_destroy_func)
+ (* hash_table->value_destroy_func) (value_to_free);
+ }
+
+ return !already_exists;
+}
+
+/**
+ * g_hash_table_iter_replace:
+ * @iter: an initialized #GHashTableIter
+ * @value: the value to replace with
+ *
+ * Replaces the value currently pointed to by the iterator
+ * from its associated #GHashTable. Can only be called after
+ * g_hash_table_iter_next() returned %TRUE.
+ *
+ * If you supplied a @value_destroy_func when creating the
+ * #GHashTable, the old value is freed using that function.
+ *
+ * Since: 2.30
+ */
+void
+g_hash_table_iter_replace (GHashTableIter *iter,
+ gpointer value)
+{
+ RealIter *ri;
+ guint node_hash;
+ gpointer key;
+
+ ri = (RealIter *) iter;
+
+ g_return_if_fail (ri != NULL);
+#ifndef G_DISABLE_ASSERT
+ g_return_if_fail (ri->version == ri->hash_table->version);
+#endif
+ g_return_if_fail (ri->position >= 0);
+ g_return_if_fail (ri->position < ri->hash_table->size);
+
+ node_hash = ri->hash_table->hashes[ri->position];
+ key = ri->hash_table->keys[ri->position];
+
+ g_hash_table_insert_node (ri->hash_table, ri->position, node_hash, key, value, TRUE, TRUE);
+
+#ifndef G_DISABLE_ASSERT
+ ri->version++;
+ ri->hash_table->version++;
+#endif
+}
+
+/**
+ * g_hash_table_iter_steal:
+ * @iter: an initialized #GHashTableIter
+ *
+ * Removes the key/value pair currently pointed to by the
+ * iterator from its associated #GHashTable, without calling
+ * the key and value destroy functions. Can only be called
+ * after g_hash_table_iter_next() returned %TRUE, and cannot
+ * be called more than once for the same key/value pair.
+ *
+ * Since: 2.16
+ */
+void
+g_hash_table_iter_steal (GHashTableIter *iter)
+{
+ iter_remove_or_steal ((RealIter *) iter, FALSE);
+}
+