sl@0: /* GLIB - Library of useful routines for C programming
sl@0:  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
sl@0:  * Copyright (C) 1999 The Free Software Foundation
sl@0:  * Portion Copyright © 2008-09 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.
sl@0:  * This library is free software; you can redistribute it and/or
sl@0:  * modify it under the terms of the GNU Lesser General Public
sl@0:  * License as published by the Free Software Foundation; either
sl@0:  * version 2 of the License, or (at your option) any later version.
sl@0:  *
sl@0:  * This library is distributed in the hope that it will be useful,
sl@0:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
sl@0:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
sl@0:  * Lesser General Public License for more details.
sl@0:  *
sl@0:  * You should have received a copy of the GNU Lesser General Public
sl@0:  * License along with this library; if not, write to the
sl@0:  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
sl@0:  * Boston, MA 02111-1307, USA.
sl@0:  */
sl@0: 
sl@0: /*
sl@0:  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
sl@0:  * file for a list of people on the GLib Team.  See the ChangeLog
sl@0:  * files for a list of changes.  These files are distributed with
sl@0:  * GLib at ftp://ftp.gtk.org/pub/gtk/. 
sl@0:  */
sl@0: 
sl@0: #undef G_DISABLE_ASSERT
sl@0: #undef G_LOG_DOMAIN
sl@0: 
sl@0: #ifdef HAVE_CONFIG_H
sl@0: #  include <config.h>
sl@0: #endif
sl@0: 
sl@0: #if STDC_HEADERS
sl@0: #include <stdio.h>
sl@0: #include <string.h>
sl@0: #include <stdlib.h>
sl@0: #endif
sl@0: 
sl@0: #include <glib.h>
sl@0: 
sl@0: 
sl@0: #ifdef SYMBIAN
sl@0: #include "mrt2_glib2_test.h"
sl@0: #endif /*SYMBIAN*/
sl@0: 
sl@0: 
sl@0: 
sl@0: int array[10000];
sl@0: 
sl@0: 
sl@0: 
sl@0: static gboolean
sl@0: my_hash_callback_remove (gpointer key,
sl@0: 			 gpointer value,
sl@0: 			 gpointer user_data)
sl@0: {
sl@0:   int *d = value;
sl@0: 
sl@0:   if ((*d) % 2)
sl@0:     return TRUE;
sl@0: 
sl@0:   return FALSE;
sl@0: }
sl@0: 
sl@0: static void
sl@0: my_hash_callback_remove_test (gpointer key,
sl@0: 			      gpointer value,
sl@0: 			      gpointer user_data)
sl@0: {
sl@0:   int *d = value;
sl@0: 
sl@0:   if ((*d) % 2)
sl@0:     g_assert_not_reached ();
sl@0: }
sl@0: 
sl@0: static void
sl@0: my_hash_callback (gpointer key,
sl@0: 		  gpointer value,
sl@0: 		  gpointer user_data)
sl@0: {
sl@0:   int *d = value;
sl@0:   *d = 1;
sl@0: }
sl@0: 
sl@0: static guint
sl@0: my_hash (gconstpointer key)
sl@0: {
sl@0:   return (guint) *((const gint*) key);
sl@0: }
sl@0: 
sl@0: static gboolean
sl@0: my_hash_equal (gconstpointer a,
sl@0: 	       gconstpointer b)
sl@0: {
sl@0:   return *((const gint*) a) == *((const gint*) b);
sl@0: }
sl@0: 
sl@0: 
sl@0: 
sl@0: /*
sl@0:  * This is a simplified version of the pathalias hashing function.
sl@0:  * Thanks to Steve Belovin and Peter Honeyman
sl@0:  *
sl@0:  * hash a string into a long int.  31 bit crc (from andrew appel).
sl@0:  * the crc table is computed at run time by crcinit() -- we could
sl@0:  * precompute, but it takes 1 clock tick on a 750.
sl@0:  *
sl@0:  * This fast table calculation works only if POLY is a prime polynomial
sl@0:  * in the field of integers modulo 2.  Since the coefficients of a
sl@0:  * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is
sl@0:  * implicit.  IT MUST ALSO BE THE CASE that the coefficients of orders
sl@0:  * 31 down to 25 are zero.  Happily, we have candidates, from
sl@0:  * E. J.  Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
sl@0:  *	x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
sl@0:  *	x^31 + x^3 + x^0
sl@0:  *
sl@0:  * We reverse the bits to get:
sl@0:  *	111101010000000000000000000000001 but drop the last 1
sl@0:  *         f   5   0   0   0   0   0   0
sl@0:  *	010010000000000000000000000000001 ditto, for 31-bit crc
sl@0:  *	   4   8   0   0   0   0   0   0
sl@0:  */
sl@0: 
sl@0: #define POLY 0x48000000L	/* 31-bit polynomial (avoids sign problems) */
sl@0: 
sl@0: static guint CrcTable[128];
sl@0: 
sl@0: /*
sl@0:  - crcinit - initialize tables for hash function
sl@0:  */
sl@0: static void crcinit(void)
sl@0: {
sl@0: 	int i, j;
sl@0: 	guint sum;
sl@0: 
sl@0: 	for (i = 0; i < 128; ++i) {
sl@0: 		sum = 0L;
sl@0: 		for (j = 7 - 1; j >= 0; --j)
sl@0: 			if (i & (1 << j))
sl@0: 				sum ^= POLY >> j;
sl@0: 		CrcTable[i] = sum;
sl@0: 	}
sl@0: }
sl@0: 
sl@0: /*
sl@0:  - hash - Honeyman's nice hashing function
sl@0:  */
sl@0: static guint honeyman_hash(gconstpointer key)
sl@0: {
sl@0: 	const gchar *name = (const gchar *) key;
sl@0: 	gint size;
sl@0: 	guint sum = 0;
sl@0: 
sl@0: 	g_assert (name != NULL);
sl@0: 	g_assert (*name != 0);
sl@0: 
sl@0: 	size = strlen(name);
sl@0: 
sl@0: 	while (size--) {
sl@0: 		sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
sl@0: 	}
sl@0: 
sl@0: 	return(sum);
sl@0: }
sl@0: 
sl@0: 
sl@0: static gboolean second_hash_cmp (gconstpointer a, gconstpointer b)
sl@0: {
sl@0:   return (strcmp (a, b) == 0);
sl@0: }
sl@0: 
sl@0: 
sl@0: 
sl@0: static guint one_hash(gconstpointer key)
sl@0: {
sl@0:   return 1;
sl@0: }
sl@0: 
sl@0: 
sl@0: static void not_even_foreach (gpointer       key,
sl@0: 				 gpointer       value,
sl@0: 				 gpointer	user_data)
sl@0: {
sl@0:   const char *_key = (const char *) key;
sl@0:   const char *_value = (const char *) value;
sl@0:   int i;
sl@0:   char val [20];
sl@0: 
sl@0:   g_assert (_key != NULL);
sl@0:   g_assert (*_key != 0);
sl@0:   g_assert (_value != NULL);
sl@0:   g_assert (*_value != 0);
sl@0: 
sl@0:   i = atoi (_key);
sl@0: 
sl@0:   sprintf (val, "%d value", i);
sl@0:   g_assert (strcmp (_value, val) == 0);
sl@0: 
sl@0:   g_assert ((i % 2) != 0);
sl@0:   g_assert (i != 3);
sl@0: }
sl@0: 
sl@0: 
sl@0: static gboolean remove_even_foreach (gpointer       key,
sl@0: 				 gpointer       value,
sl@0: 				 gpointer	user_data)
sl@0: {
sl@0:   const char *_key = (const char *) key;
sl@0:   const char *_value = (const char *) value;
sl@0:   int i;
sl@0:   char val [20];
sl@0: 
sl@0:   g_assert (_key != NULL);
sl@0:   g_assert (*_key != 0);
sl@0:   g_assert (_value != NULL);
sl@0:   g_assert (*_value != 0);
sl@0: 
sl@0:   i = atoi (_key);
sl@0: 
sl@0:   sprintf (val, "%d value", i);
sl@0:   g_assert (strcmp (_value, val) == 0);
sl@0: 
sl@0:   return ((i % 2) == 0) ? TRUE : FALSE;
sl@0: }
sl@0: 
sl@0: 
sl@0: 
sl@0: 
sl@0: static void second_hash_test (gboolean simple_hash)
sl@0: {
sl@0:      int       i;
sl@0:      char      key[20] = "", val[20]="", *v, *orig_key, *orig_val;
sl@0:      GHashTable     *h;
sl@0:      gboolean found;
sl@0: 
sl@0:      crcinit ();
sl@0: 
sl@0:      h = g_hash_table_new (simple_hash ? one_hash : honeyman_hash,
sl@0:      			   second_hash_cmp);
sl@0:      g_assert (h != NULL);
sl@0:      for (i=0; i<20; i++)
sl@0:           {
sl@0:           sprintf (key, "%d", i);
sl@0: 	  g_assert (atoi (key) == i);
sl@0: 
sl@0: 	  sprintf (val, "%d value", i);
sl@0: 	  g_assert (atoi (val) == i);
sl@0: 
sl@0:           g_hash_table_insert (h, g_strdup (key), g_strdup (val));
sl@0:           }
sl@0: 
sl@0:      g_assert (g_hash_table_size (h) == 20);
sl@0: 
sl@0:      for (i=0; i<20; i++)
sl@0:           {
sl@0:           sprintf (key, "%d", i);
sl@0: 	  g_assert (atoi(key) == i);
sl@0: 
sl@0:           v = (char *) g_hash_table_lookup (h, key);
sl@0: 
sl@0: 	  g_assert (v != NULL);
sl@0: 	  g_assert (*v != 0);
sl@0: 	  g_assert (atoi (v) == i);
sl@0:           }
sl@0: 
sl@0:      sprintf (key, "%d", 3);
sl@0:      g_hash_table_remove (h, key);
sl@0:      g_hash_table_foreach_remove (h, remove_even_foreach, NULL);
sl@0:      g_hash_table_foreach (h, not_even_foreach, NULL);
sl@0: 
sl@0:      for (i=0; i<20; i++)
sl@0:           {
sl@0: 	  if ((i % 2) == 0 || i == 3)
sl@0:   	      continue;
sl@0: 
sl@0:           sprintf (key, "%d", i);
sl@0: 	  g_assert (atoi(key) == i);
sl@0: 
sl@0: 	  sprintf (val, "%d value", i);
sl@0: 	  g_assert (atoi (val) == i);
sl@0: 
sl@0: 	  orig_key = orig_val = NULL;
sl@0:           found = g_hash_table_lookup_extended (h, key,
sl@0: 	  					(gpointer)&orig_key,
sl@0: 						(gpointer)&orig_val);
sl@0: 	  g_assert (found);
sl@0: 
sl@0: 	  g_hash_table_remove (h, key);
sl@0: 
sl@0: 	  g_assert (orig_key != NULL);
sl@0: 	  g_assert (strcmp (key, orig_key) == 0);
sl@0: 	  g_free (orig_key);
sl@0: 
sl@0: 	  g_assert (orig_val != NULL);
sl@0: 	  g_assert (strcmp (val, orig_val) == 0);
sl@0: 	  g_free (orig_val);
sl@0:           }
sl@0: 
sl@0:     g_hash_table_destroy (h);
sl@0: }
sl@0: 
sl@0: static gboolean find_first     (gpointer key, 
sl@0: 				gpointer value, 
sl@0: 				gpointer user_data)
sl@0: {
sl@0:   gint *v = value; 
sl@0:   gint *test = user_data;
sl@0:   return (*v == *test);
sl@0: }
sl@0: 
sl@0: 
sl@0: static void direct_hash_test (void)
sl@0: {
sl@0:      gint       i, rc;
sl@0:      GHashTable     *h;
sl@0: 
sl@0:      h = g_hash_table_new (NULL, NULL);
sl@0:      g_assert (h != NULL);
sl@0:      for (i=1; i<=20; i++)
sl@0:           {
sl@0:           g_hash_table_insert (h, GINT_TO_POINTER (i),
sl@0: 	  		       GINT_TO_POINTER (i + 42));
sl@0:           }
sl@0: 
sl@0:      g_assert (g_hash_table_size (h) == 20);
sl@0: 
sl@0:      for (i=1; i<=20; i++)
sl@0:           {
sl@0:           rc = GPOINTER_TO_INT (
sl@0: 	  	g_hash_table_lookup (h, GINT_TO_POINTER (i)));
sl@0: 
sl@0: 	  g_assert (rc != 0);
sl@0: 	  g_assert ((rc - 42) == i);
sl@0:           }
sl@0: 
sl@0:     g_hash_table_destroy (h);
sl@0: }
sl@0: 
sl@0: 
sl@0: 
sl@0: int
sl@0: main (int   argc,
sl@0:       char *argv[])
sl@0: {
sl@0:   GHashTable *hash_table;
sl@0:   gint i;
sl@0:   gint value = 120;
sl@0:   gint *pvalue; 
sl@0:   
sl@0:   #ifdef SYMBIAN
sl@0:   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);
sl@0:   g_set_print_handler(mrtPrintHandler);
sl@0:   #endif /*SYMBIAN*/
sl@0: 	  
sl@0: 
sl@0:   hash_table = g_hash_table_new (my_hash, my_hash_equal);
sl@0:   for (i = 0; i < 10000; i++)
sl@0:     {
sl@0:       array[i] = i;
sl@0:       g_hash_table_insert (hash_table, &array[i], &array[i]);
sl@0:     }
sl@0:   pvalue = g_hash_table_find (hash_table, find_first, &value);
sl@0:   if (!pvalue || *pvalue != value)
sl@0:     g_assert_not_reached();
sl@0:   
sl@0:   g_hash_table_foreach (hash_table, my_hash_callback, NULL);
sl@0: 
sl@0:   for (i = 0; i < 10000; i++)
sl@0:     if (array[i] == 0)
sl@0:       g_assert_not_reached();
sl@0: 
sl@0:   for (i = 0; i < 10000; i++)
sl@0:     g_hash_table_remove (hash_table, &array[i]);
sl@0: 
sl@0:   for (i = 0; i < 10000; i++)
sl@0:     {
sl@0:       array[i] = i;
sl@0:       g_hash_table_insert (hash_table, &array[i], &array[i]);
sl@0:     }
sl@0: 
sl@0:   if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||
sl@0:       g_hash_table_size (hash_table) != 5000)
sl@0:     g_assert_not_reached();
sl@0: 
sl@0:   g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
sl@0: 
sl@0: 
sl@0:   g_hash_table_destroy (hash_table);
sl@0: 
sl@0:   second_hash_test (TRUE);
sl@0:   second_hash_test (FALSE);
sl@0:   direct_hash_test ();
sl@0:   
sl@0:   #if SYMBIAN
sl@0:   testResultXml("hash-test");
sl@0:   #endif /* EMULATOR */
sl@0: 
sl@0:   return 0;
sl@0: 
sl@0: }