diff -r 4332f0f7be53 -r acd3cd4aaceb glib/tests/hash-test.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/glib/tests/hash-test.c Tue Aug 31 16:54:36 2010 +0300 @@ -0,0 +1,472 @@ +/* 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 + * Portion Copyright © 2008-09 Nokia Corporation and/or its subsidiary(-ies). All rights reserved. + * 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. + * + * 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, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + +/* + * 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 + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#if STDC_HEADERS +#include +#include +#include +#endif + +#include + + +#ifdef __SYMBIAN32__ +#include "mrt2_glib2_test.h" +#endif /*__SYMBIAN32__*/ + +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) +{ + int i; + + for (i = 0; i < 10000; i++) + result_array[i] = -1; +} + +static void +verify_result_array (int *array) +{ + int i; + + for (i = 0; i < 10000; i++) + g_assert (array[i] == i); +} + +static void +handle_pair (gpointer key, gpointer value, int *result_array) +{ + 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; + gint 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 (gboolean simple_hash) +{ + 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); +} + + + +int +main (int argc, + char *argv[]) +{ + GHashTable *hash_table; + gint i; + gint value = 120; + gint *pvalue; + GList *keys, *values; + gint keys_len, values_len; + GHashTableIter iter; + gpointer ikey, ivalue; + int result_array[10000]; + + #ifdef __SYMBIAN32__ + g_log_set_handler (NULL, G_LOG_FLAG_FATAL| G_LOG_FLAG_RECURSION | G_LOG_LEVEL_CRITICAL | G_LOG_LEVEL_WARNING | G_LOG_LEVEL_MESSAGE | G_LOG_LEVEL_INFO | G_LOG_LEVEL_DEBUG, &mrtLogHandler, NULL); + g_set_print_handler(mrtPrintHandler); + #endif /*__SYMBIAN32__*/ + + + 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); + + second_hash_test (TRUE); + second_hash_test (FALSE); + direct_hash_test (); + + #if __SYMBIAN32__ + testResultXml("hash-test"); + #endif /* EMULATOR */ + + return 0; + +}