glib/tests/hash.c

/* GLIB - Library of useful routines for C programming
 * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
 * Copyright (C) 1999 The Free Software Foundation
 *
 * 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/.
 */

#undef G_DISABLE_ASSERT
#undef G_LOG_DOMAIN

#include <config.h>

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include <glib.h>


int array[10000];

static void
fill_hash_table_and_array (GHashTable *hash_table)
{
  int i;

  for (i = 0; i < 10000; i++)
    {
      array[i] = i;
      g_hash_table_insert (hash_table, &array[i], &array[i]);
    }
}

static void
init_result_array (int result_array[10000])
{
  int i;

  for (i = 0; i < 10000; i++)
    result_array[i] = -1;
}

static void
verify_result_array (int array[10000])
{
  int i;

  for (i = 0; i < 10000; i++)
    g_assert (array[i] == i);
}

static void
handle_pair (gpointer key, gpointer value, int result_array[10000])
{
  int n;

  g_assert (key == value);

  n = *((int *) value);

  g_assert (n >= 0 && n < 10000);
  g_assert (result_array[n] == -1);

  result_array[n] = n;
}

static gboolean
my_hash_callback_remove (gpointer key,
                         gpointer value,
                         gpointer user_data)
{
  int *d = value;

  if ((*d) % 2)
    return TRUE;

  return FALSE;
}

static void
my_hash_callback_remove_test (gpointer key,
                              gpointer value,
                              gpointer user_data)
{
  int *d = value;

  if ((*d) % 2)
    g_assert_not_reached ();
}

static void
my_hash_callback (gpointer key,
                  gpointer value,
                  gpointer user_data)
{
  handle_pair (key, value, user_data);
}

static guint
my_hash (gconstpointer key)
{
  return (guint) *((const gint*) key);
}

static gboolean
my_hash_equal (gconstpointer a,
               gconstpointer b)
{
  return *((const gint*) a) == *((const gint*) b);
}


/*
 * This is a simplified version of the pathalias hashing function.
 * Thanks to Steve Belovin and Peter Honeyman
 *
 * hash a string into a long int.  31 bit crc (from andrew appel).
 * the crc table is computed at run time by crcinit() -- we could
 * precompute, but it takes 1 clock tick on a 750.
 *
 * This fast table calculation works only if POLY is a prime polynomial
 * in the field of integers modulo 2.  Since the coefficients of a
 * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is
 * implicit.  IT MUST ALSO BE THE CASE that the coefficients of orders
 * 31 down to 25 are zero.  Happily, we have candidates, from
 * E. J.  Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
 *      x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
 *      x^31 + x^3 + x^0
 *
 * We reverse the bits to get:
 *      111101010000000000000000000000001 but drop the last 1
 *         f   5   0   0   0   0   0   0
 *      010010000000000000000000000000001 ditto, for 31-bit crc
 *         4   8   0   0   0   0   0   0
 */

#define POLY 0x48000000L        /* 31-bit polynomial (avoids sign problems) */

static guint CrcTable[128];

/*
 - crcinit - initialize tables for hash function
 */
static void crcinit(void)
{
  int i, j;
  guint sum;

  for (i = 0; i < 128; ++i)
    {
      sum = 0L;
      for (j = 7 - 1; j >= 0; --j)
        if (i & (1 << j))
          sum ^= POLY >> j;
      CrcTable[i] = sum;
    }
}

/*
 - hash - Honeyman's nice hashing function
 */
static guint
honeyman_hash (gconstpointer key)
{
  const gchar *name = (const gchar *) key;
  gsize size;
  guint sum = 0;

  g_assert (name != NULL);
  g_assert (*name != 0);

  size = strlen (name);

  while (size--)
    sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];

  return sum;
}


static gboolean
second_hash_cmp (gconstpointer a, gconstpointer b)
{
  return strcmp (a, b) == 0;
}


static guint
one_hash (gconstpointer key)
{
  return 1;
}


static void
not_even_foreach (gpointer key,
                  gpointer value,
                  gpointer user_data)
{
  const char *_key = (const char *) key;
  const char *_value = (const char *) value;
  int i;
  char val [20];

  g_assert (_key != NULL);
  g_assert (*_key != 0);
  g_assert (_value != NULL);
  g_assert (*_value != 0);

  i = atoi (_key);

  sprintf (val, "%d value", i);
  g_assert (strcmp (_value, val) == 0);

  g_assert ((i % 2) != 0);
  g_assert (i != 3);
}

static gboolean
remove_even_foreach (gpointer key,
                     gpointer value,
                     gpointer user_data)
{
  const char *_key = (const char *) key;
  const char *_value = (const char *) value;
  int i;
  char val [20];

  g_assert (_key != NULL);
  g_assert (*_key != 0);
  g_assert (_value != NULL);
  g_assert (*_value != 0);

  i = atoi (_key);

  sprintf (val, "%d value", i);
  g_assert (strcmp (_value, val) == 0);

  return ((i % 2) == 0) ? TRUE : FALSE;
}


static void
second_hash_test (gconstpointer d)
{
  gboolean simple_hash = GPOINTER_TO_INT (d);

  int       i;
  char      key[20] = "", val[20]="", *v, *orig_key, *orig_val;
  GHashTable     *h;
  gboolean found;

  crcinit ();

  h = g_hash_table_new_full (simple_hash ? one_hash : honeyman_hash,
                             second_hash_cmp,
                             g_free, g_free);
  g_assert (h != NULL);
  for (i = 0; i < 20; i++)
    {
      sprintf (key, "%d", i);
      g_assert (atoi (key) == i);

      sprintf (val, "%d value", i);
      g_assert (atoi (val) == i);

      g_hash_table_insert (h, g_strdup (key), g_strdup (val));
    }

  g_assert (g_hash_table_size (h) == 20);

  for (i = 0; i < 20; i++)
    {
      sprintf (key, "%d", i);
      g_assert (atoi(key) == i);

      v = (char *) g_hash_table_lookup (h, key);

      g_assert (v != NULL);
      g_assert (*v != 0);
      g_assert (atoi (v) == i);
    }

  sprintf (key, "%d", 3);
  g_hash_table_remove (h, key);
  g_assert (g_hash_table_size (h) == 19);
  g_hash_table_foreach_remove (h, remove_even_foreach, NULL);
  g_assert (g_hash_table_size (h) == 9);
  g_hash_table_foreach (h, not_even_foreach, NULL);

  for (i = 0; i < 20; i++)
    {
      sprintf (key, "%d", i);
      g_assert (atoi(key) == i);

      sprintf (val, "%d value", i);
      g_assert (atoi (val) == i);

      orig_key = orig_val = NULL;
      found = g_hash_table_lookup_extended (h, key,
                                            (gpointer)&orig_key,
                                            (gpointer)&orig_val);
      if ((i % 2) == 0 || i == 3)
        {
          g_assert (!found);
          continue;
        }

      g_assert (found);

      g_assert (orig_key != NULL);
      g_assert (strcmp (key, orig_key) == 0);

      g_assert (orig_val != NULL);
      g_assert (strcmp (val, orig_val) == 0);
    }

  g_hash_table_destroy (h);
}

static gboolean
find_first (gpointer key,
            gpointer value,
            gpointer user_data)
{
  gint *v = value;
  gint *test = user_data;
  return (*v == *test);
}

static void
direct_hash_test (void)
{
  gint       i, rc;
  GHashTable     *h;

  h = g_hash_table_new (NULL, NULL);
  g_assert (h != NULL);
  for (i = 1; i <= 20; i++)
    g_hash_table_insert (h, GINT_TO_POINTER (i),
                         GINT_TO_POINTER (i + 42));

  g_assert (g_hash_table_size (h) == 20);

  for (i = 1; i <= 20; i++)
    {
      rc = GPOINTER_TO_INT (g_hash_table_lookup (h, GINT_TO_POINTER (i)));

      g_assert (rc != 0);
      g_assert ((rc - 42) == i);
    }

  g_hash_table_destroy (h);
}

static void
direct_hash_test2 (void)
{
  gint       i, rc;
  GHashTable     *h;

  h = g_hash_table_new (g_direct_hash, g_direct_equal);
  g_assert (h != NULL);
  for (i = 1; i <= 20; i++)
    g_hash_table_insert (h, GINT_TO_POINTER (i),
                         GINT_TO_POINTER (i + 42));

  g_assert (g_hash_table_size (h) == 20);

  for (i = 1; i <= 20; i++)
    {
      rc = GPOINTER_TO_INT (g_hash_table_lookup (h, GINT_TO_POINTER (i)));

      g_assert (rc != 0);
      g_assert ((rc - 42) == i);
    }

  g_hash_table_destroy (h);
}

static void
int_hash_test (void)
{
  gint       i, rc;
  GHashTable     *h;
  gint     values[20];
  gint key;

  h = g_hash_table_new (g_int_hash, g_int_equal);
  g_assert (h != NULL);
  for (i = 0; i < 20; i++)
    {
      values[i] = i + 42;
      g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
    }

  g_assert (g_hash_table_size (h) == 20);

  for (i = 0; i < 20; i++)
    {
      key = i + 42;
      rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));

      g_assert_cmpint (rc, ==, i + 42);
    }

  g_hash_table_destroy (h);
}

static void
int64_hash_test (void)
{
  gint       i, rc;
  GHashTable     *h;
  gint64     values[20];
  gint64 key;

  h = g_hash_table_new (g_int64_hash, g_int64_equal);
  g_assert (h != NULL);
  for (i = 0; i < 20; i++)
    {
      values[i] = i + 42;
      g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
    }

  g_assert (g_hash_table_size (h) == 20);

  for (i = 0; i < 20; i++)
    {
      key = i + 42;
      rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));

      g_assert_cmpint (rc, ==, i + 42);
    }

  g_hash_table_destroy (h);
}

static void
double_hash_test (void)
{
  gint       i, rc;
  GHashTable     *h;
  gdouble values[20];
  gdouble key;

  h = g_hash_table_new (g_double_hash, g_double_equal);
  g_assert (h != NULL);
  for (i = 0; i < 20; i++)
    {
      values[i] = i + 42.5;
      g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
    }

  g_assert (g_hash_table_size (h) == 20);

  for (i = 0; i < 20; i++)
    {
      key = i + 42.5;
      rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));

      g_assert_cmpint (rc, ==, i + 42);
    }

  g_hash_table_destroy (h);
}

static void
string_free (gpointer data)
{
  GString *s = data;

  g_string_free (s, TRUE);
}

static void
string_hash_test (void)
{
  gint       i, rc;
  GHashTable     *h;
  GString *s;

  h = g_hash_table_new_full ((GHashFunc)g_string_hash, (GEqualFunc)g_string_equal, string_free, NULL);
  g_assert (h != NULL);
  for (i = 0; i < 20; i++)
    {
      s = g_string_new ("");
      g_string_append_printf (s, "%d", i + 42);
      g_string_append_c (s, '.');
      g_string_prepend_unichar (s, 0x2301);
      g_hash_table_insert (h, s, GINT_TO_POINTER (i + 42));
    }

  g_assert (g_hash_table_size (h) == 20);

  s = g_string_new ("");
  for (i = 0; i < 20; i++)
    {
      g_string_assign (s, "");
      g_string_append_printf (s, "%d", i + 42);
      g_string_append_c (s, '.');
      g_string_prepend_unichar (s, 0x2301);
      rc = GPOINTER_TO_INT (g_hash_table_lookup (h, s));

      g_assert_cmpint (rc, ==, i + 42);
    }

  g_string_free (s, TRUE);
  g_hash_table_destroy (h);
}

static void
set_check (gpointer key,
           gpointer value,
           gpointer user_data)
{
  int *pi = user_data;
  if (key != value)
    g_assert_not_reached ();

  g_assert_cmpint (atoi (key) % 7, ==, 2);

  (*pi)++;
}

static void
set_hash_test (void)
{
  GHashTable *hash_table =
    g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
  int i;

  for (i = 2; i < 5000; i += 7)
    {
      char *s = g_strdup_printf ("%d", i);
      g_assert (g_hash_table_add (hash_table, s));
    }

  g_assert (!g_hash_table_add (hash_table, g_strdup_printf ("%d", 2)));

  i = 0;
  g_hash_table_foreach (hash_table, set_check, &i);
  g_assert_cmpint (i, ==, g_hash_table_size (hash_table));

  g_assert (g_hash_table_contains (hash_table, "2"));
  g_assert (g_hash_table_contains (hash_table, "9"));
  g_assert (!g_hash_table_contains (hash_table, "a"));

  /* this will cause the hash table to loose set nature */
  g_assert (g_hash_table_insert (hash_table, g_strdup ("a"), "b"));
  g_assert (!g_hash_table_insert (hash_table, g_strdup ("a"), "b"));

  g_assert (g_hash_table_replace (hash_table, g_strdup ("c"), "d"));
  g_assert (!g_hash_table_replace (hash_table, g_strdup ("c"), "d"));

  g_assert_cmpstr (g_hash_table_lookup (hash_table, "2"), ==, "2");
  g_assert_cmpstr (g_hash_table_lookup (hash_table, "a"), ==, "b");

  g_hash_table_destroy (hash_table);
}


static void
test_hash_misc (void)
{
  GHashTable *hash_table;
  gint i;
  gint value = 120;
  gint *pvalue;
  GList *keys, *values;
  gsize keys_len, values_len;
  GHashTableIter iter;
  gpointer ikey, ivalue;
  int result_array[10000];
  int n_array[1];

  hash_table = g_hash_table_new (my_hash, my_hash_equal);
  fill_hash_table_and_array (hash_table);
  pvalue = g_hash_table_find (hash_table, find_first, &value);
  if (!pvalue || *pvalue != value)
    g_assert_not_reached();

  keys = g_hash_table_get_keys (hash_table);
  if (!keys)
    g_assert_not_reached ();

  values = g_hash_table_get_values (hash_table);
  if (!values)
    g_assert_not_reached ();

  keys_len = g_list_length (keys);
  values_len = g_list_length (values);
  if (values_len != keys_len &&  keys_len != g_hash_table_size (hash_table))
    g_assert_not_reached ();

  g_list_free (keys);
  g_list_free (values);

  init_result_array (result_array);
  g_hash_table_iter_init (&iter, hash_table);
  for (i = 0; i < 10000; i++)
    {
      g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));

      handle_pair (ikey, ivalue, result_array);

      if (i % 2)
        g_hash_table_iter_remove (&iter);
    }
  g_assert (! g_hash_table_iter_next (&iter, &ikey, &ivalue));
  g_assert (g_hash_table_size (hash_table) == 5000);
  verify_result_array (result_array);

  fill_hash_table_and_array (hash_table);

  init_result_array (result_array);
  g_hash_table_foreach (hash_table, my_hash_callback, result_array);
  verify_result_array (result_array);

  for (i = 0; i < 10000; i++)
    g_hash_table_remove (hash_table, &array[i]);

  fill_hash_table_and_array (hash_table);

  if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||
      g_hash_table_size (hash_table) != 5000)
    g_assert_not_reached();

  g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
  g_hash_table_destroy (hash_table);

  hash_table = g_hash_table_new (my_hash, my_hash_equal);
  fill_hash_table_and_array (hash_table);

  n_array[0] = 1;

  g_hash_table_iter_init (&iter, hash_table);
  for (i = 0; i < 10000; i++)
    {
      g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
      g_hash_table_iter_replace (&iter, &n_array[0]);
    }

  g_hash_table_iter_init (&iter, hash_table);
  for (i = 0; i < 10000; i++)
    {
      g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));

      g_assert (ivalue == &n_array[0]);
    }

  g_hash_table_destroy (hash_table);
}

static gint destroy_counter;

static void
value_destroy (gpointer value)
{
  destroy_counter++;
}

static void
test_hash_ref (void)
{
  GHashTable *h;
  GHashTableIter iter;
  gchar *key, *value;
  gboolean abc_seen = FALSE;
  gboolean cde_seen = FALSE;
  gboolean xyz_seen = FALSE;

  h = g_hash_table_new_full (g_str_hash, g_str_equal, NULL, value_destroy);
  g_hash_table_insert (h, "abc", "ABC");
  g_hash_table_insert (h, "cde", "CDE");
  g_hash_table_insert (h, "xyz", "XYZ");

  g_assert_cmpint (g_hash_table_size (h), == , 3);

  g_hash_table_iter_init (&iter, h);

  while (g_hash_table_iter_next (&iter, (gpointer*)&key, (gpointer*)&value))
    {
      if (strcmp (key, "abc") == 0)
        {
          g_assert_cmpstr (value, ==, "ABC");
          abc_seen = TRUE;
          g_hash_table_iter_steal (&iter);
        }
      else if (strcmp (key, "cde") == 0)
        {
          g_assert_cmpstr (value, ==, "CDE");
          cde_seen = TRUE;
        }
      else if (strcmp (key, "xyz") == 0)
        {
          g_assert_cmpstr (value, ==, "XYZ");
          xyz_seen = TRUE;
        }
    }
  g_assert_cmpint (destroy_counter, ==, 0);

  g_assert (g_hash_table_iter_get_hash_table (&iter) == h);
  g_assert (abc_seen && cde_seen && xyz_seen);
  g_assert_cmpint (g_hash_table_size (h), == , 2);

  g_hash_table_ref (h);
  g_hash_table_destroy (h);
  g_assert_cmpint (g_hash_table_size (h), == , 0);
  g_assert_cmpint (destroy_counter, ==, 2);
  g_hash_table_insert (h, "uvw", "UVW");
  g_hash_table_unref (h);
  g_assert_cmpint (destroy_counter, ==, 3);
}

static guint
null_safe_str_hash (gconstpointer key)
{
  if (key == NULL)
    return 0;
  else
    return g_str_hash (key);
}

static gboolean
null_safe_str_equal (gconstpointer a, gconstpointer b)
{
  return g_strcmp0 (a, b) == 0;
}

static void
test_lookup_null_key (void)
{
  GHashTable *h;
  gboolean res;
  gpointer key;
  gpointer value;

  g_test_bug ("https://bugzilla.gnome.org/show_bug.cgi?id=642944");

  h = g_hash_table_new (null_safe_str_hash, null_safe_str_equal);
  g_hash_table_insert (h, "abc", "ABC");

  res = g_hash_table_lookup_extended (h, NULL, &key, &value);
  g_assert (!res);

  g_hash_table_insert (h, NULL, "NULL");

  res = g_hash_table_lookup_extended (h, NULL, &key, &value);
  g_assert (res);
  g_assert_cmpstr (value, ==, "NULL");

  g_hash_table_unref (h);
}

static gint destroy_key_counter;

static void
key_destroy (gpointer key)
{
  destroy_key_counter++;
}

static void
test_remove_all (void)
{
  GHashTable *h;
  gboolean res;

  h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, value_destroy);

  g_hash_table_insert (h, "abc", "cde");
  g_hash_table_insert (h, "cde", "xyz");
  g_hash_table_insert (h, "xyz", "abc");

  destroy_counter = 0;
  destroy_key_counter = 0;

  g_hash_table_steal_all (h);
  g_assert_cmpint (destroy_counter, ==, 0);
  g_assert_cmpint (destroy_key_counter, ==, 0);

  /* Test stealing on an empty hash table. */
  g_hash_table_steal_all (h);
  g_assert_cmpint (destroy_counter, ==, 0);
  g_assert_cmpint (destroy_key_counter, ==, 0);

  g_hash_table_insert (h, "abc", "ABC");
  g_hash_table_insert (h, "cde", "CDE");
  g_hash_table_insert (h, "xyz", "XYZ");

  res = g_hash_table_steal (h, "nosuchkey");
  g_assert (!res);
  g_assert_cmpint (destroy_counter, ==, 0);
  g_assert_cmpint (destroy_key_counter, ==, 0);

  res = g_hash_table_steal (h, "xyz");
  g_assert (res);
  g_assert_cmpint (destroy_counter, ==, 0);
  g_assert_cmpint (destroy_key_counter, ==, 0);

  g_hash_table_remove_all (h);
  g_assert_cmpint (destroy_counter, ==, 2);
  g_assert_cmpint (destroy_key_counter, ==, 2);

  g_hash_table_remove_all (h);
  g_assert_cmpint (destroy_counter, ==, 2);
  g_assert_cmpint (destroy_key_counter, ==, 2);

  g_hash_table_unref (h);
}

GHashTable *recursive_destruction_table = NULL;
static void
recursive_value_destroy (gpointer value)
{
  destroy_counter++;

  if (recursive_destruction_table)
    g_hash_table_remove (recursive_destruction_table, value);
}

static void
test_recursive_remove_all_subprocess (void)
{
  GHashTable *h;

  h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, recursive_value_destroy);
  recursive_destruction_table = h;

  /* Add more items compared to test_remove_all, as it would not fail otherwise. */
  g_hash_table_insert (h, "abc", "cde");
  g_hash_table_insert (h, "cde", "fgh");
  g_hash_table_insert (h, "fgh", "ijk");
  g_hash_table_insert (h, "ijk", "lmn");
  g_hash_table_insert (h, "lmn", "opq");
  g_hash_table_insert (h, "opq", "rst");
  g_hash_table_insert (h, "rst", "uvw");
  g_hash_table_insert (h, "uvw", "xyz");
  g_hash_table_insert (h, "xyz", "abc");

  destroy_counter = 0;
  destroy_key_counter = 0;

  g_hash_table_remove_all (h);
  g_assert_cmpint (destroy_counter, ==, 9);
  g_assert_cmpint (destroy_key_counter, ==, 9);

  g_hash_table_unref (h);
}

static void
test_recursive_remove_all (void)
{
  g_test_trap_subprocess ("/hash/recursive-remove-all/subprocess", 1000000, 0);
  g_test_trap_assert_passed ();
}

typedef struct {
  gint ref_count;
  const gchar *key;
} RefCountedKey;

static guint
hash_func (gconstpointer key)
{
  const RefCountedKey *rkey = key;

  return g_str_hash (rkey->key);
}

static gboolean
eq_func (gconstpointer a, gconstpointer b)
{
  const RefCountedKey *aa = a;
  const RefCountedKey *bb = b;

  return g_strcmp0 (aa->key, bb->key) == 0;
}

static void
key_unref (gpointer data)
{
  RefCountedKey *key = data;

  g_assert (key->ref_count > 0);

  key->ref_count -= 1;

  if (key->ref_count == 0)
    g_free (key);
}

static RefCountedKey *
key_ref (RefCountedKey *key)
{
  key->ref_count += 1;

  return key;
}

static RefCountedKey *
key_new (const gchar *key)
{
  RefCountedKey *rkey;

  rkey = g_new (RefCountedKey, 1);

  rkey->ref_count = 1;
  rkey->key = key;

  return rkey;
}

static void
set_ref_hash_test (void)
{
  GHashTable *h;
  RefCountedKey *key1;
  RefCountedKey *key2;

  h = g_hash_table_new_full (hash_func, eq_func, key_unref, key_unref);

  key1 = key_new ("a");
  key2 = key_new ("a");

  g_assert_cmpint (key1->ref_count, ==, 1);
  g_assert_cmpint (key2->ref_count, ==, 1);

  g_hash_table_insert (h, key_ref (key1), key_ref (key1));

  g_assert_cmpint (key1->ref_count, ==, 3);
  g_assert_cmpint (key2->ref_count, ==, 1);

  g_hash_table_replace (h, key_ref (key2), key_ref (key2));

  g_assert_cmpint (key1->ref_count, ==, 1);
  g_assert_cmpint (key2->ref_count, ==, 3);

  g_hash_table_remove (h, key1);

  g_assert_cmpint (key1->ref_count, ==, 1);
  g_assert_cmpint (key2->ref_count, ==, 1);

  g_hash_table_unref (h);

  key_unref (key1);
  key_unref (key2);
}

GHashTable *h;

typedef struct {
    gchar *string;
    gboolean freed;
} FakeFreeData;

GPtrArray *fake_free_data;

static void
fake_free (gpointer dead)
{
  guint i;

  for (i = 0; i < fake_free_data->len; i++)
    {
      FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);

      if (ffd->string == (gchar *) dead)
        {
          g_assert (!ffd->freed);
          ffd->freed = TRUE;
          return;
        }
    }

  g_assert_not_reached ();
}

static void
value_destroy_insert (gpointer value)
{
  g_hash_table_remove_all (h);
}

static void
test_destroy_modify (void)
{
  FakeFreeData *ffd;
  guint i;

  g_test_bug ("https://bugzilla.gnome.org/show_bug.cgi?id=650459");

  fake_free_data = g_ptr_array_new ();

  h = g_hash_table_new_full (g_str_hash, g_str_equal, fake_free, value_destroy_insert);

  ffd = g_new0 (FakeFreeData, 1);
  ffd->string = g_strdup ("a");
  g_ptr_array_add (fake_free_data, ffd);
  g_hash_table_insert (h, ffd->string, "b");

  ffd = g_new0 (FakeFreeData, 1);
  ffd->string = g_strdup ("c");
  g_ptr_array_add (fake_free_data, ffd);
  g_hash_table_insert (h, ffd->string, "d");

  ffd = g_new0 (FakeFreeData, 1);
  ffd->string = g_strdup ("e");
  g_ptr_array_add (fake_free_data, ffd);
  g_hash_table_insert (h, ffd->string, "f");

  ffd = g_new0 (FakeFreeData, 1);
  ffd->string = g_strdup ("g");
  g_ptr_array_add (fake_free_data, ffd);
  g_hash_table_insert (h, ffd->string, "h");

  ffd = g_new0 (FakeFreeData, 1);
  ffd->string = g_strdup ("h");
  g_ptr_array_add (fake_free_data, ffd);
  g_hash_table_insert (h, ffd->string, "k");

  ffd = g_new0 (FakeFreeData, 1);
  ffd->string = g_strdup ("a");
  g_ptr_array_add (fake_free_data, ffd);
  g_hash_table_insert (h, ffd->string, "c");

  g_hash_table_remove (h, "c");

  /* that removed everything... */
  for (i = 0; i < fake_free_data->len; i++)
    {
      FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);

      g_assert (ffd->freed);
      g_free (ffd->string);
      g_free (ffd);
    }

  g_ptr_array_unref (fake_free_data);

  /* ... so this is a no-op */
  g_hash_table_remove (h, "e");

  g_hash_table_unref (h);
}

static gboolean
find_str (gpointer key, gpointer value, gpointer data)
{
  return g_str_equal (key, data);
}

static void
test_find (void)
{
  GHashTable *hash;
  const gchar *value;

  hash = g_hash_table_new (g_str_hash, g_str_equal);

  g_hash_table_insert (hash, "a", "A");
  g_hash_table_insert (hash, "b", "B");
  g_hash_table_insert (hash, "c", "C");
  g_hash_table_insert (hash, "d", "D");
  g_hash_table_insert (hash, "e", "E");
  g_hash_table_insert (hash, "f", "F");

  value = g_hash_table_find (hash, find_str, "a");
  g_assert_cmpstr (value, ==, "A");

  value = g_hash_table_find (hash, find_str, "b");
  g_assert_cmpstr (value, ==, "B");

  value = g_hash_table_find (hash, find_str, "c");
  g_assert_cmpstr (value, ==, "C");

  value = g_hash_table_find (hash, find_str, "d");
  g_assert_cmpstr (value, ==, "D");

  value = g_hash_table_find (hash, find_str, "e");
  g_assert_cmpstr (value, ==, "E");

  value = g_hash_table_find (hash, find_str, "f");
  g_assert_cmpstr (value, ==, "F");

  value = g_hash_table_find (hash, find_str, "0");
  g_assert (value == NULL);

  g_hash_table_unref (hash);
}

gboolean seen_key[6];

static void
foreach_func (gpointer key, gpointer value, gpointer data)
{
  seen_key[((char*)key)[0] - 'a'] = TRUE;
}

static void
test_foreach (void)
{
  GHashTable *hash;
  gint i;

  hash = g_hash_table_new (g_str_hash, g_str_equal);

  g_hash_table_insert (hash, "a", "A");
  g_hash_table_insert (hash, "b", "B");
  g_hash_table_insert (hash, "c", "C");
  g_hash_table_insert (hash, "d", "D");
  g_hash_table_insert (hash, "e", "E");
  g_hash_table_insert (hash, "f", "F");

  for (i = 0; i < 6; i++)
    seen_key[i] = FALSE;

  g_hash_table_foreach (hash, foreach_func, NULL);

  for (i = 0; i < 6; i++)
    g_assert (seen_key[i]);

  g_hash_table_unref (hash);
}

static gboolean
foreach_steal_func (gpointer key, gpointer value, gpointer data)
{
  GHashTable *hash2 = data;

  if (strstr ("ace", (gchar*)key))
    {
      g_hash_table_insert (hash2, key, value);
      return TRUE;
    }

  return FALSE;
}


static void
test_foreach_steal (void)
{
  GHashTable *hash;
  GHashTable *hash2;

  hash = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
  hash2 = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);

  g_hash_table_insert (hash, g_strdup ("a"), g_strdup ("A"));
  g_hash_table_insert (hash, g_strdup ("b"), g_strdup ("B"));
  g_hash_table_insert (hash, g_strdup ("c"), g_strdup ("C"));
  g_hash_table_insert (hash, g_strdup ("d"), g_strdup ("D"));
  g_hash_table_insert (hash, g_strdup ("e"), g_strdup ("E"));
  g_hash_table_insert (hash, g_strdup ("f"), g_strdup ("F"));

  g_hash_table_foreach_steal (hash, foreach_steal_func, hash2);

  g_assert_cmpint (g_hash_table_size (hash), ==, 3);
  g_assert_cmpint (g_hash_table_size (hash2), ==, 3);

  g_assert_cmpstr (g_hash_table_lookup (hash2, "a"), ==, "A");
  g_assert_cmpstr (g_hash_table_lookup (hash, "b"), ==, "B");
  g_assert_cmpstr (g_hash_table_lookup (hash2, "c"), ==, "C");
  g_assert_cmpstr (g_hash_table_lookup (hash, "d"), ==, "D");
  g_assert_cmpstr (g_hash_table_lookup (hash2, "e"), ==, "E");
  g_assert_cmpstr (g_hash_table_lookup (hash, "f"), ==, "F");

  g_hash_table_unref (hash);
  g_hash_table_unref (hash2);
}

/* Test g_hash_table_steal_extended() works properly with existing and
 * non-existing keys. */
static void
test_steal_extended (void)
{
  GHashTable *hash;
  gchar *stolen_key = NULL, *stolen_value = NULL;

  hash = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);

  g_hash_table_insert (hash, g_strdup ("a"), g_strdup ("A"));
  g_hash_table_insert (hash, g_strdup ("b"), g_strdup ("B"));
  g_hash_table_insert (hash, g_strdup ("c"), g_strdup ("C"));
  g_hash_table_insert (hash, g_strdup ("d"), g_strdup ("D"));
  g_hash_table_insert (hash, g_strdup ("e"), g_strdup ("E"));
  g_hash_table_insert (hash, g_strdup ("f"), g_strdup ("F"));

  g_assert_true (g_hash_table_steal_extended (hash, "a",
                                              (gpointer *) &stolen_key,
                                              (gpointer *) &stolen_value));
  g_assert_cmpstr (stolen_key, ==, "a");
  g_assert_cmpstr (stolen_value, ==, "A");
  g_clear_pointer (&stolen_key, g_free);
  g_clear_pointer (&stolen_value, g_free);

  g_assert_cmpuint (g_hash_table_size (hash), ==, 5);

  g_assert_false (g_hash_table_steal_extended (hash, "a",
                                               (gpointer *) &stolen_key,
                                               (gpointer *) &stolen_value));
  g_assert_null (stolen_key);
  g_assert_null (stolen_value);

  g_assert_false (g_hash_table_steal_extended (hash, "never a key",
                                               (gpointer *) &stolen_key,
                                               (gpointer *) &stolen_value));
  g_assert_null (stolen_key);
  g_assert_null (stolen_value);

  g_assert_cmpuint (g_hash_table_size (hash), ==, 5);

  g_hash_table_unref (hash);
}

/* Test that passing %NULL to the optional g_hash_table_steal_extended()
 * arguments works. */
static void
test_steal_extended_optional (void)
{
  GHashTable *hash;
  const gchar *stolen_key = NULL, *stolen_value = NULL;

  hash = g_hash_table_new_full (g_str_hash, g_str_equal, NULL, NULL);

  g_hash_table_insert (hash, "b", "B");
  g_hash_table_insert (hash, "c", "C");
  g_hash_table_insert (hash, "d", "D");
  g_hash_table_insert (hash, "e", "E");
  g_hash_table_insert (hash, "f", "F");

  g_assert_true (g_hash_table_steal_extended (hash, "b",
                                              (gpointer *) &stolen_key,
                                              NULL));
  g_assert_cmpstr (stolen_key, ==, "b");

  g_assert_cmpuint (g_hash_table_size (hash), ==, 4);

  g_assert_false (g_hash_table_steal_extended (hash, "b",
                                               (gpointer *) &stolen_key,
                                               NULL));
  g_assert_null (stolen_key);

  g_assert_true (g_hash_table_steal_extended (hash, "c",
                                              NULL,
                                              (gpointer *) &stolen_value));
  g_assert_cmpstr (stolen_value, ==, "C");

  g_assert_cmpuint (g_hash_table_size (hash), ==, 3);

  g_assert_false (g_hash_table_steal_extended (hash, "c",
                                               NULL,
                                               (gpointer *) &stolen_value));
  g_assert_null (stolen_value);

  g_assert_true (g_hash_table_steal_extended (hash, "d", NULL, NULL));

  g_assert_cmpuint (g_hash_table_size (hash), ==, 2);

  g_assert_false (g_hash_table_steal_extended (hash, "d", NULL, NULL));

  g_assert_cmpuint (g_hash_table_size (hash), ==, 2);

  g_hash_table_unref (hash);
}

/* Test g_hash_table_lookup_extended() works with its optional parameters
 * sometimes set to %NULL. */
static void
test_lookup_extended (void)
{
  GHashTable *hash;
  const gchar *original_key = NULL, *value = NULL;

  hash = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);

  g_hash_table_insert (hash, g_strdup ("a"), g_strdup ("A"));
  g_hash_table_insert (hash, g_strdup ("b"), g_strdup ("B"));
  g_hash_table_insert (hash, g_strdup ("c"), g_strdup ("C"));
  g_hash_table_insert (hash, g_strdup ("d"), g_strdup ("D"));
  g_hash_table_insert (hash, g_strdup ("e"), g_strdup ("E"));
  g_hash_table_insert (hash, g_strdup ("f"), g_strdup ("F"));

  g_assert_true (g_hash_table_lookup_extended (hash, "a",
                                               (gpointer *) &original_key,
                                               (gpointer *) &value));
  g_assert_cmpstr (original_key, ==, "a");
  g_assert_cmpstr (value, ==, "A");

  g_assert_true (g_hash_table_lookup_extended (hash, "b",
                                               NULL,
                                               (gpointer *) &value));
  g_assert_cmpstr (value, ==, "B");

  g_assert_true (g_hash_table_lookup_extended (hash, "c",
                                               (gpointer *) &original_key,
                                               NULL));
  g_assert_cmpstr (original_key, ==, "c");

  g_assert_true (g_hash_table_lookup_extended (hash, "d", NULL, NULL));

  g_assert_false (g_hash_table_lookup_extended (hash, "not a key",
                                                (gpointer *) &original_key,
                                                (gpointer *) &value));
  g_assert_null (original_key);
  g_assert_null (value);

  g_assert_false (g_hash_table_lookup_extended (hash, "not a key",
                                                NULL,
                                                (gpointer *) &value));
  g_assert_null (value);

  g_assert_false (g_hash_table_lookup_extended (hash, "not a key",
                                                (gpointer *) &original_key,
                                                NULL));
  g_assert_null (original_key);

  g_assert_false (g_hash_table_lookup_extended (hash, "not a key", NULL, NULL));

  g_hash_table_unref (hash);
}

struct _GHashTable
{
  gsize            size;
  gint             mod;
  guint            mask;
  gint             nnodes;
  gint             noccupied;  /* nnodes + tombstones */

  guint            have_big_keys : 1;
  guint            have_big_values : 1;

  gpointer        *keys;
  guint           *hashes;
  gpointer        *values;

  GHashFunc        hash_func;
  GEqualFunc       key_equal_func;
  gint             ref_count;  /* (atomic) */

#ifndef G_DISABLE_ASSERT
  int              version;
#endif
  GDestroyNotify   key_destroy_func;
  GDestroyNotify   value_destroy_func;
};

static void
count_keys (GHashTable *h, gint *unused, gint *occupied, gint *tombstones)
{
  gsize i;

  *unused = 0;
  *occupied = 0;
  *tombstones = 0;
  for (i = 0; i < h->size; i++)
    {
      if (h->hashes[i] == 0)
        (*unused)++;
      else if (h->hashes[i] == 1)
        (*tombstones)++;
      else
        (*occupied)++;
    }
}

#define BIG_ENTRY_SIZE (SIZEOF_VOID_P)
#define SMALL_ENTRY_SIZE (SIZEOF_INT)

#if SMALL_ENTRY_SIZE < BIG_ENTRY_SIZE
# define USE_SMALL_ARRAYS
#endif

static gpointer
fetch_key_or_value (gpointer a, guint index, gboolean is_big)
{
#ifdef USE_SMALL_ARRAYS
  return is_big ? *(((gpointer *) a) + index) : GUINT_TO_POINTER (*(((guint *) a) + index));
#else
  return *(((gpointer *) a) + index);
#endif
}

static void
check_data (GHashTable *h)
{
  gsize i;

  for (i = 0; i < h->size; i++)
    {
      if (h->hashes[i] >= 2)
        {
          g_assert_cmpint (h->hashes[i], ==, h->hash_func (fetch_key_or_value (h->keys, i, h->have_big_keys)));
        }
    }
}

static void
check_consistency (GHashTable *h)
{
  gint unused;
  gint occupied;
  gint tombstones;

  count_keys (h, &unused, &occupied, &tombstones);

  g_assert_cmpint (occupied, ==, h->nnodes);
  g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
  g_assert_cmpint (occupied + tombstones + unused, ==, h->size);

  check_data (h);
}

static void
check_counts (GHashTable *h, gint occupied, gint tombstones)
{
  g_assert_cmpint (occupied, ==, h->nnodes);
  g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
}

static void
trivial_key_destroy (gpointer key)
{
}

static void
test_internal_consistency (void)
{
  GHashTable *h;

  h = g_hash_table_new_full (g_str_hash, g_str_equal, trivial_key_destroy, NULL);

  check_counts (h, 0, 0);
  check_consistency (h);

  g_hash_table_insert (h, "a", "A");
  g_hash_table_insert (h, "b", "B");
  g_hash_table_insert (h, "c", "C");
  g_hash_table_insert (h, "d", "D");
  g_hash_table_insert (h, "e", "E");
  g_hash_table_insert (h, "f", "F");

  check_counts (h, 6, 0);
  check_consistency (h);

  g_hash_table_remove (h, "a");
  check_counts (h, 5, 1);
  check_consistency (h);

  g_hash_table_remove (h, "b");
  check_counts (h, 4, 2);
  check_consistency (h);

  g_hash_table_insert (h, "c", "c");
  check_counts (h, 4, 2);
  check_consistency (h);

  g_hash_table_insert (h, "a", "A");
  check_counts (h, 5, 1);
  check_consistency (h);

  g_hash_table_remove_all (h);
  check_counts (h, 0, 0);
  check_consistency (h);

  g_hash_table_unref (h);
}

static void
my_key_free (gpointer v)
{
  gchar *s = v;
  g_assert (s[0] != 'x');
  s[0] = 'x';
  g_free (v);
}

static void
my_value_free (gpointer v)
{
  gchar *s = v;
  g_assert (s[0] != 'y');
  s[0] = 'y';
  g_free (v);
}

static void
test_iter_replace (void)
{
  GHashTable *h;
  GHashTableIter iter;
  gpointer k, v;
  gchar *s;

  g_test_bug ("https://bugzilla.gnome.org/show_bug.cgi?id=662544");

  h = g_hash_table_new_full (g_str_hash, g_str_equal, my_key_free, my_value_free);

  g_hash_table_insert (h, g_strdup ("A"), g_strdup ("a"));
  g_hash_table_insert (h, g_strdup ("B"), g_strdup ("b"));
  g_hash_table_insert (h, g_strdup ("C"), g_strdup ("c"));

  g_hash_table_iter_init (&iter, h);

  while (g_hash_table_iter_next (&iter, &k, &v))
    {
       s = (gchar*)v;
       g_assert (g_ascii_islower (s[0]));
       g_hash_table_iter_replace (&iter, g_strdup (k));
    }

  g_hash_table_unref (h);
}

static void
replace_first_character (gchar *string)
{
  string[0] = 'b';
}

static void
test_set_insert_corruption (void)
{
  GHashTable *hash_table =
    g_hash_table_new_full (g_str_hash, g_str_equal,
        (GDestroyNotify) replace_first_character, NULL);
  GHashTableIter iter;
  gchar a[] = "foo";
  gchar b[] = "foo";
  gpointer key, value;

  g_test_bug ("https://bugzilla.gnome.org/show_bug.cgi?id=692815");

  g_hash_table_insert (hash_table, a, a);
  g_assert (g_hash_table_contains (hash_table, "foo"));

  g_hash_table_insert (hash_table, b, b);

  g_assert_cmpuint (g_hash_table_size (hash_table), ==, 1);
  g_hash_table_iter_init (&iter, hash_table);
  if (!g_hash_table_iter_next (&iter, &key, &value))
    g_assert_not_reached();

  /* per the documentation to g_hash_table_insert(), 'b' has now been freed,
   * and the sole key in 'hash_table' should be 'a'.
   */
  g_assert (key != b);
  g_assert (key == a);

  g_assert_cmpstr (b, ==, "boo");

  /* g_hash_table_insert() also says that the value should now be 'b',
   * which is probably not what the caller intended but is precisely what they
   * asked for.
   */
  g_assert (value == b);

  /* even though the hash has now been de-set-ified: */
  g_assert (g_hash_table_contains (hash_table, "foo"));

  g_hash_table_unref (hash_table);
}

static void
test_set_to_strv (void)
{
  GHashTable *set;
  gchar **strv;
  guint n;

  set = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
  g_hash_table_add (set, g_strdup ("xyz"));
  g_hash_table_add (set, g_strdup ("xyz"));
  g_hash_table_add (set, g_strdup ("abc"));
  strv = (gchar **) g_hash_table_get_keys_as_array (set, &n);
  g_hash_table_steal_all (set);
  g_hash_table_unref (set);
  g_assert_cmpint (n, ==, 2);
  n = g_strv_length (strv);
  g_assert_cmpint (n, ==, 2);
  if (g_str_equal (strv[0], "abc"))
    g_assert_cmpstr (strv[1], ==, "xyz");
  else
    {
    g_assert_cmpstr (strv[0], ==, "xyz");
    g_assert_cmpstr (strv[1], ==, "abc");
    }
  g_strfreev (strv);
}

static gboolean
is_prime (guint p)
{
  guint i;

  if (p % 2 == 0)
    return FALSE;

  i = 3;
  while (TRUE)
    {
      if (i * i > p)
        return TRUE;

      if (p % i == 0)
        return FALSE;

      i += 2;
    }
}

static void
test_primes (void)
{
  guint p, q;
  gdouble r, min, max;

  max = 1.0;
  min = 10.0;
  q = 1;
  while (1) {
    p = q;
    q = g_spaced_primes_closest (p);
    g_assert (is_prime (q));
    if (p == 1) continue;
    if (q == p) break;
    r = q / (gdouble) p;
    min = MIN (min, r);
    max = MAX (max, r);
  };

  g_assert_cmpfloat (1.3, <, min);
  g_assert_cmpfloat (max, <, 2.0);
}

int
main (int argc, char *argv[])
{
  g_test_init (&argc, &argv, NULL);

  g_test_add_func ("/hash/misc", test_hash_misc);
  g_test_add_data_func ("/hash/one", GINT_TO_POINTER (TRUE), second_hash_test);
  g_test_add_data_func ("/hash/honeyman", GINT_TO_POINTER (FALSE), second_hash_test);
  g_test_add_func ("/hash/direct", direct_hash_test);
  g_test_add_func ("/hash/direct2", direct_hash_test2);
  g_test_add_func ("/hash/int", int_hash_test);
  g_test_add_func ("/hash/int64", int64_hash_test);
  g_test_add_func ("/hash/double", double_hash_test);
  g_test_add_func ("/hash/string", string_hash_test);
  g_test_add_func ("/hash/set", set_hash_test);
  g_test_add_func ("/hash/set-ref", set_ref_hash_test);
  g_test_add_func ("/hash/ref", test_hash_ref);
  g_test_add_func ("/hash/remove-all", test_remove_all);
  g_test_add_func ("/hash/recursive-remove-all", test_recursive_remove_all);
  g_test_add_func ("/hash/recursive-remove-all/subprocess", test_recursive_remove_all_subprocess);
  g_test_add_func ("/hash/find", test_find);
  g_test_add_func ("/hash/foreach", test_foreach);
  g_test_add_func ("/hash/foreach-steal", test_foreach_steal);
  g_test_add_func ("/hash/steal-extended", test_steal_extended);
  g_test_add_func ("/hash/steal-extended/optional", test_steal_extended_optional);
  g_test_add_func ("/hash/lookup-extended", test_lookup_extended);

  /* tests for individual bugs */
  g_test_add_func ("/hash/lookup-null-key", test_lookup_null_key);
  g_test_add_func ("/hash/destroy-modify", test_destroy_modify);
  g_test_add_func ("/hash/consistency", test_internal_consistency);
  g_test_add_func ("/hash/iter-replace", test_iter_replace);
  g_test_add_func ("/hash/set-insert-corruption", test_set_insert_corruption);
  g_test_add_func ("/hash/set-to-strv", test_set_to_strv);
  g_test_add_func ("/hash/primes", test_primes);

  return g_test_run ();

}