* 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 of the License, or (at your option) any later version.
+ * 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
* 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, write to the
- * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- * Boston, MA 02111-1307, USA.
+ * License along with this library; if not, see <http://www.gnu.org/licenses/>.
*/
/*
#undef G_DISABLE_ASSERT
#undef G_LOG_DOMAIN
-#ifdef HAVE_CONFIG_H
-# include <config.h>
-#endif
+#include <config.h>
-#if STDC_HEADERS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
-#endif
#include <glib.h>
*/
static void crcinit(void)
{
- int i, j;
- guint sum;
+ 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;
- }
+ 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)
+static guint
+honeyman_hash (gconstpointer key)
{
- const gchar *name = (const gchar *) key;
- gint size;
- guint sum = 0;
+ const gchar *name = (const gchar *) key;
+ gsize size;
+ guint sum = 0;
- g_assert (name != NULL);
- g_assert (*name != 0);
+ g_assert (name != NULL);
+ g_assert (*name != 0);
- size = strlen(name);
+ size = strlen (name);
- while (size--) {
- sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
- }
+ while (size--)
+ sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
- return(sum);
+ return sum;
}
-static gboolean second_hash_cmp (gconstpointer a, gconstpointer b)
+static gboolean
+second_hash_cmp (gconstpointer a, gconstpointer b)
{
- return (strcmp (a, b) == 0);
+ return strcmp (a, b) == 0;
}
-static guint one_hash(gconstpointer key)
+static guint
+one_hash (gconstpointer key)
{
return 1;
}
-static void not_even_foreach (gpointer key,
- gpointer value,
- gpointer user_data)
+static void
+not_even_foreach (gpointer key,
+ gpointer value,
+ gpointer user_data)
{
const char *_key = (const char *) key;
const char *_value = (const char *) value;
g_assert (i != 3);
}
-
-static gboolean remove_even_foreach (gpointer key,
- gpointer value,
- gpointer user_data)
+static gboolean
+remove_even_foreach (gpointer key,
+ gpointer value,
+ gpointer user_data)
{
const char *_key = (const char *) key;
const char *_value = (const char *) value;
-static void second_hash_test (gconstpointer d)
+static void
+second_hash_test (gconstpointer d)
{
- gboolean simple_hash = GPOINTER_TO_INT (d);
+ gboolean simple_hash = GPOINTER_TO_INT (d);
- int i;
- char key[20] = "", val[20]="", *v, *orig_key, *orig_val;
- GHashTable *h;
- gboolean found;
+ int i;
+ char key[20] = "", val[20]="", *v, *orig_key, *orig_val;
+ GHashTable *h;
+ gboolean found;
- crcinit ();
+ 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);
+ 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);
+ sprintf (val, "%d value", i);
+ g_assert (atoi (val) == i);
- g_hash_table_insert (h, g_strdup (key), g_strdup (val));
- }
+ g_hash_table_insert (h, g_strdup (key), g_strdup (val));
+ }
- g_assert (g_hash_table_size (h) == 20);
+ g_assert (g_hash_table_size (h) == 20);
- for (i=0; i<20; i++)
- {
- sprintf (key, "%d", i);
- g_assert (atoi(key) == i);
+ for (i = 0; i < 20; i++)
+ {
+ sprintf (key, "%d", i);
+ g_assert (atoi(key) == i);
- v = (char *) g_hash_table_lookup (h, key);
+ v = (char *) g_hash_table_lookup (h, key);
- g_assert (v != NULL);
- g_assert (*v != 0);
- g_assert (atoi (v) == i);
- }
+ 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);
+ 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);
+ 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);
+ 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;
- }
+ 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 (found);
- g_assert (orig_key != NULL);
- g_assert (strcmp (key, orig_key) == 0);
+ 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_assert (orig_val != NULL);
+ g_assert (strcmp (val, orig_val) == 0);
+ }
- g_hash_table_destroy (h);
+ g_hash_table_destroy (h);
}
-static gboolean find_first (gpointer key,
- gpointer value,
- gpointer user_data)
+static gboolean
+find_first (gpointer key,
+ gpointer value,
+ gpointer user_data)
{
- gint *v = value;
+ 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 direct_hash_test (void)
+static void
+string_free (gpointer data)
{
- gint i, rc;
- GHashTable *h;
+ GString *s = data;
+
+ g_string_free (s, TRUE);
+}
- 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));
- }
+static void
+string_hash_test (void)
+{
+ gint i, rc;
+ GHashTable *h;
+ GString *s;
- g_assert (g_hash_table_size (h) == 20);
+ 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));
+ }
- for (i=1; i<=20; i++)
- {
- rc = GPOINTER_TO_INT (
- g_hash_table_lookup (h, GINT_TO_POINTER (i)));
+ g_assert (g_hash_table_size (h) == 20);
- g_assert (rc != 0);
- g_assert ((rc - 42) == i);
- }
+ 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_hash_table_destroy (h);
+ 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 value = 120;
gint *pvalue;
GList *keys, *values;
- gint keys_len, values_len;
+ 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);
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;
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 ("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 ("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 ("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 ("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_bug_base ("http://bugzilla.gnome.org/");
+
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 ();
projects / platform / upstream / glib.git / blobdiff