/* GLIB - Library of useful routines for C programming

 * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser General Public

 * License as published by the Free Software Foundation; either

 * version 2.1 of the License, or (at your option) any later version.

 *

 * This library is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser General Public

 * License along with this library; if not, see <http://www.gnu.org/licenses/>.

 */

/*

 * Modified by the GLib Team and others 1997-2000.  See the AUTHORS

 * file for a list of people on the GLib Team.  See the ChangeLog

 * files for a list of changes.  These files are distributed with

 * GLib at ftp://ftp.gtk.org/pub/gtk/.

 */

/*

 * MT safe

 */

#include "config.h"

#include <string.h>  /* memset */

#include "ghash.h"

#include "glib-private.h"

#include "gstrfuncs.h"

#include "gatomic.h"

#include "gtestutils.h"

#include "gslice.h"

/**

 * SECTION:hash_tables

 * @title: Hash Tables

 * @short_description: associations between keys and values so that

 *     given a key the value can be found quickly

 *

 * A #GHashTable provides associations between keys and values which is

 * optimized so that given a key, the associated value can be found

 * very quickly.

 *

 * Note that neither keys nor values are copied when inserted into the

 * #GHashTable, so they must exist for the lifetime of the #GHashTable.

 * This means that the use of static strings is OK, but temporary

 * strings (i.e. those created in buffers and those returned by GTK+

 * widgets) should be copied with g_strdup() before being inserted.

 *

 * If keys or values are dynamically allocated, you must be careful to

 * ensure that they are freed when they are removed from the

 * #GHashTable, and also when they are overwritten by new insertions

 * into the #GHashTable. It is also not advisable to mix static strings

 * and dynamically-allocated strings in a #GHashTable, because it then

 * becomes difficult to determine whether the string should be freed.

 *

 * To create a #GHashTable, use g_hash_table_new().

 *

 * To insert a key and value into a #GHashTable, use

 * g_hash_table_insert().

 *

 * To lookup a value corresponding to a given key, use

 * g_hash_table_lookup() and g_hash_table_lookup_extended().

 *

 * g_hash_table_lookup_extended() can also be used to simply

 * check if a key is present in the hash table.

 *

 * To remove a key and value, use g_hash_table_remove().

 *

 * To call a function for each key and value pair use

 * g_hash_table_foreach() or use a iterator to iterate over the

 * key/value pairs in the hash table, see #GHashTableIter.

 *

 * To destroy a #GHashTable use g_hash_table_destroy().

 *

 * A common use-case for hash tables is to store information about a

 * set of keys, without associating any particular value with each

 * key. GHashTable optimizes one way of doing so: If you store only

 * key-value pairs where key == value, then GHashTable does not

 * allocate memory to store the values, which can be a considerable

 * space saving, if your set is large. The functions

 * g_hash_table_add() and g_hash_table_contains() are designed to be

 * used when using #GHashTable this way.

 *

 * #GHashTable is not designed to be statically initialised with keys and

 * values known at compile time. To build a static hash table, use a tool such

 * as [gperf](https://www.gnu.org/software/gperf/).

 */

/**

 * GHashTable:

 *

 * The #GHashTable struct is an opaque data structure to represent a

 * [Hash Table][glib-Hash-Tables]. It should only be accessed via the

 * following functions.

 */

/**

 * GHashFunc:

 * @key: a key

 *

 * Specifies the type of the hash function which is passed to

 * g_hash_table_new() when a #GHashTable is created.

 *

 * The function is passed a key and should return a #guint hash value.

 * The functions g_direct_hash(), g_int_hash() and g_str_hash() provide

 * hash functions which can be used when the key is a #gpointer, #gint*,

 * and #gchar* respectively.

 *

 * g_direct_hash() is also the appropriate hash function for keys

 * of the form `GINT_TO_POINTER (n)` (or similar macros).

 *

 * A good hash functions should produce

 * hash values that are evenly distributed over a fairly large range.

 * The modulus is taken with the hash table size (a prime number) to

 * find the 'bucket' to place each key into. The function should also

 * be very fast, since it is called for each key lookup.

 *

 * Note that the hash functions provided by GLib have these qualities,

 * but are not particularly robust against manufactured keys that

 * cause hash collisions. Therefore, you should consider choosing

 * a more secure hash function when using a GHashTable with keys

 * that originate in untrusted data (such as HTTP requests).

 * Using g_str_hash() in that situation might make your application

 * vulerable to

 * [Algorithmic Complexity Attacks](https://lwn.net/Articles/474912/).

 *

 * The key to choosing a good hash is unpredictability.  Even

 * cryptographic hashes are very easy to find collisions for when the

 * remainder is taken modulo a somewhat predictable prime number.  There

 * must be an element of randomness that an attacker is unable to guess.

 *

 * Returns: the hash value corresponding to the key

 */

/**

 * GHFunc:

 * @key: a key

 * @value: the value corresponding to the key

 * @user_data: user data passed to g_hash_table_foreach()

 *

 * Specifies the type of the function passed to g_hash_table_foreach().

 * It is called with each key/value pair, together with the @user_data

 * parameter which is passed to g_hash_table_foreach().

 */

/**

 * GHRFunc:

 * @key: a key

 * @value: the value associated with the key

 * @user_data: user data passed to g_hash_table_remove()

 *

 * Specifies the type of the function passed to

 * g_hash_table_foreach_remove(). It is called with each key/value

 * pair, together with the @user_data parameter passed to

 * g_hash_table_foreach_remove(). It should return %TRUE if the

 * key/value pair should be removed from the #GHashTable.

 *

 * Returns: %TRUE if the key/value pair should be removed from the

 *     #GHashTable

 */

/**

 * GEqualFunc:

 * @a: a value

 * @b: a value to compare with

 *

 * Specifies the type of a function used to test two values for

 * equality. The function should return %TRUE if both values are equal

 * and %FALSE otherwise.

 *

 * Returns: %TRUE if @a = @b; %FALSE otherwise

 */

/**

 * GHashTableIter:

 *

 * A GHashTableIter structure represents an iterator that can be used

 * to iterate over the elements of a #GHashTable. GHashTableIter

 * structures are typically allocated on the stack and then initialized

 * with g_hash_table_iter_init().

 */

/**

 * g_hash_table_freeze:

 * @hash_table: a #GHashTable

 *

 * This function is deprecated and will be removed in the next major

 * release of GLib. It does nothing.

 */

/**

 * g_hash_table_thaw:

 * @hash_table: a #GHashTable

 *

 * This function is deprecated and will be removed in the next major

 * release of GLib. It does nothing.

 */

#define HASH_TABLE_MIN_SHIFT 3  /* 1 << 3 == 8 buckets */

#define UNUSED_HASH_VALUE 0

#define TOMBSTONE_HASH_VALUE 1

#define HASH_IS_UNUSED(h_) ((h_) == UNUSED_HASH_VALUE)

#define HASH_IS_TOMBSTONE(h_) ((h_) == TOMBSTONE_HASH_VALUE)

#define HASH_IS_REAL(h_) ((h_) >= 2)

struct _GHashTable

{

  gint             size;

  gint             mod;

  guint            mask;

  gint             nnodes;

  gint             noccupied;  /* nnodes + tombstones */

  gpointer        *keys;

  guint           *hashes;

  gpointer        *values;

  GHashFunc        hash_func;

  GEqualFunc       key_equal_func;

  gint             ref_count;

#ifndef G_DISABLE_ASSERT

  /*

   * Tracks the structure of the hash table, not its contents: is only

   * incremented when a node is added or removed (is not incremented

   * when the key or data of a node is modified).

   */

  int              version;

#endif

  GDestroyNotify   key_destroy_func;

  GDestroyNotify   value_destroy_func;

};

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;

  /* If this happens, then the application is probably doing too much work

   * from a destroy notifier. The alternative would be to crash any second

   * (as keys, etc. will be NULL).

   * Applications need to either use g_hash_table_destroy, or ensure the hash

   * table is empty prior to removing the last reference using g_hash_table_unref(). */

  g_assert (hash_table->ref_count > 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,

                               gboolean    destruction)

{

  int i;

  gpointer key;

  gpointer value;

  gint old_size;

  gpointer *old_keys;

  gpointer *old_values;

  guint    *old_hashes;

  /* If the hash table is already empty, there is nothing to be done. */

  if (hash_table->nnodes == 0)

    return;

  hash_table->nnodes = 0;

  hash_table->noccupied = 0;

  if (!notify ||

      (hash_table->key_destroy_func == NULL &&

       hash_table->value_destroy_func == NULL))

    {

      if (!destruction)

        {

          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;

    }

  /* Keep the old storage space around to iterate over it. */

  old_size = hash_table->size;

  old_keys   = hash_table->keys;

  old_values = hash_table->values;

  old_hashes = hash_table->hashes;

  /* Now create a new storage space; If the table is destroyed we can use the

   * shortcut of not creating a new storage. This saves the allocation at the

   * cost of not allowing any recursive access.

   * However, the application doesn't own any reference anymore, so access

   * is not allowed. If accesses are done, then either an assert or crash

   * *will* happen. */

  g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT);

  if (!destruction)

    {

      hash_table->keys   = g_new0 (gpointer, hash_table->size);

      hash_table->values = hash_table->keys;

      hash_table->hashes = g_new0 (guint, hash_table->size);

    }

  else

    {

      hash_table->keys   = NULL;

      hash_table->values = NULL;

      hash_table->hashes = NULL;

    }

  for (i = 0; i < old_size; i++)

    {

      if (HASH_IS_REAL (old_hashes[i]))

        {

          key = old_keys[i];

          value = old_values[i];

          old_hashes[i] = UNUSED_HASH_VALUE;

          old_keys[i] = NULL;

          old_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);

        }

    }

  /* Destroy old storage space. */

  if (old_keys != old_values)

    g_free (old_values);

  g_free (old_keys);

  g_free (old_hashes);

}

/*

 * 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);

}

/**

 * g_hash_table_new:

 * @hash_func: a function to create a hash value from a key

 * @key_equal_func: a function to check two keys for equality

 *

 * Creates a new #GHashTable with a reference count of 1.

 *

 * Hash values returned by @hash_func are used to determine where keys

 * are stored within the #GHashTable data structure. The g_direct_hash(),

 * g_int_hash(), g_int64_hash(), g_double_hash() and g_str_hash()

 * functions are provided for some common types of keys.

 * If @hash_func is %NULL, g_direct_hash() is used.

 *

 * @key_equal_func is used when looking up keys in the #GHashTable.

 * The g_direct_equal(), g_int_equal(), g_int64_equal(), g_double_equal()

 * and g_str_equal() functions are provided for the most common types

 * of keys. If @key_equal_func is %NULL, keys are compared directly in

 * a similar fashion to g_direct_equal(), but without the overhead of

 * a function call. @key_equal_func is called with the key from the hash table

 * as its first parameter, and the user-provided key to check against as

 * its second.

 *

 * Returns: a new #GHashTable

 */

GHashTable *

g_hash_table_new (GHashFunc  hash_func,

                  GEqualFunc key_equal_func)

{

  return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);

}

/**

 * g_hash_table_new_full:

 * @hash_func: a function to create a hash value from a key

 * @key_equal_func: a function to check two keys for equality

 * @key_destroy_func: (nullable): a function to free the memory allocated for the key

 *     used when removing the entry from the #GHashTable, or %NULL

 *     if you don't want to supply such a function.

 * @value_destroy_func: (nullable): a function to free the memory allocated for the

 *     value used when removing the entry from the #GHashTable, or %NULL

 *     if you don't want to supply such a function.

 *

 * Creates a new #GHashTable like g_hash_table_new() with a reference

 * count of 1 and allows to specify functions to free the memory

 * allocated for the key and value that get called when removing the

 * entry from the #GHashTable.

 *

 * Since version 2.42 it is permissible for destroy notify functions to

 * recursively remove further items from the hash table. This is only

 * permissible if the application still holds a reference to the hash table.

 * This means that you may need to ensure that the hash table is empty by

 * calling g_hash_table_remove_all() before releasing the last reference using

 * g_hash_table_unref().

 *

 * Returns: a new #GHashTable

 */

GHashTable *

g_hash_table_new_full (GHashFunc      hash_func,

                       GEqualFunc     key_equal_func,

                       GDestroyNotify key_destroy_func,

                       GDestroyNotify value_destroy_func)

{

  GHashTable *hash_table;

  hash_table = g_slice_new (GHashTable);

  g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT);

  hash_table->nnodes             = 0;

  hash_table->noccupied          = 0;

  hash_table->hash_func          = hash_func ? hash_func : g_direct_hash;

  hash_table->key_equal_func     = key_equal_func;

  hash_table->ref_count          = 1;

#ifndef G_DISABLE_ASSERT

  hash_table->version            = 0;

#endif

  hash_table->key_destroy_func   = key_destroy_func;

  hash_table->value_destroy_func = value_destroy_func;

  hash_table->keys               = g_new0 (gpointer, hash_table->size);

  hash_table->values             = hash_table->keys;

  hash_table->hashes             = g_new0 (guint, hash_table->size);

  return hash_table;

}

/**

 * 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.

 * |[

 * 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: (out) (optional): a location to store the key

 * @value: (out) (optional) (nullable): a location to store the value

 *

 * 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:

 * |[

 * while (g_hash_table_iter_next (&iter, &key, &value))

 *   {

 *     if (condition)

 *       g_hash_table_iter_remove (&iter);

 *   }

 * ]|