1 /* GLIB - Library of useful routines for C programming

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

     3  * Copyright (C) 1999 The Free Software Foundation

     4  * Portion Copyright © 2008-09 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.

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

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

     7  * License as published by the Free Software Foundation; either

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

     9  *

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

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

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

    13  * Lesser General Public License for more details.

    14  *

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

    16  * License along with this library; if not, write to the

    17  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,

    18  * Boston, MA 02111-1307, USA.

    19  */

    20 

    21 /*

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

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

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

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

    26  */

    27 

    28 #undef G_DISABLE_ASSERT

    29 #undef G_LOG_DOMAIN

    30 

    31 #ifdef HAVE_CONFIG_H

    32 #include "config.h"

    33 #endif

    34 

    35 #if STDC_HEADERS

    36 #include <stdio.h>

    37 #include <string.h>

    38 #include <stdlib.h>

    39 #endif

    40 

    41 #include <glib.h>

    42 

    43 

    44 #ifdef __SYMBIAN32__

    45 #include "mrt2_glib2_test.h"

    46 #endif /*__SYMBIAN32__*/

    47 

    48 int array[10000];

    49 

    50 static void

    51 fill_hash_table_and_array (GHashTable *hash_table)

    52 {

    53   int i;

    54 

    55   for (i = 0; i < 10000; i++)

    56     {

    57       array[i] = i;

    58       g_hash_table_insert (hash_table, &array[i], &array[i]);

    59     }

    60 }

    61 

    62 static void

    63 init_result_array (int *result_array)

    64 {

    65   int i;

    66 

    67   for (i = 0; i < 10000; i++)

    68     result_array[i] = -1;

    69 }

    70 

    71 static void

    72 verify_result_array (int *array)

    73 {

    74   int i;

    75 

    76   for (i = 0; i < 10000; i++)

    77     g_assert (array[i] == i);

    78 }

    79 

    80 static void

    81 handle_pair (gpointer key, gpointer value, int *result_array)

    82 {

    83   int n;

    84 

    85   g_assert (key == value);

    86 

    87   n = *((int *) value);

    88 

    89   g_assert (n >= 0 && n < 10000);

    90   g_assert (result_array[n] == -1);

    91 

    92   result_array[n] = n;

    93 }

    94 

    95 static gboolean

    96 my_hash_callback_remove (gpointer key,

    97 			 gpointer value,

    98 			 gpointer user_data)

    99 {

   100   int *d = value;

   101 

   102   if ((*d) % 2)

   103     return TRUE;

   104 

   105   return FALSE;

   106 }

   107 

   108 static void

   109 my_hash_callback_remove_test (gpointer key,

   110 			      gpointer value,

   111 			      gpointer user_data)

   112 {

   113   int *d = value;

   114 

   115   if ((*d) % 2)

   116     g_assert_not_reached ();

   117 }

   118 

   119 static void

   120 my_hash_callback (gpointer key,

   121 		  gpointer value,

   122 		  gpointer user_data)

   123 {

   124   handle_pair (key, value, user_data);

   125 }

   126 

   127 static guint

   128 my_hash (gconstpointer key)

   129 {

   130   return (guint) *((const gint*) key);

   131 }

   132 

   133 static gboolean

   134 my_hash_equal (gconstpointer a,

   135 	       gconstpointer b)

   136 {

   137   return *((const gint*) a) == *((const gint*) b);

   138 }

   139 

   140 

   141 

   142 /*

   143  * This is a simplified version of the pathalias hashing function.

   144  * Thanks to Steve Belovin and Peter Honeyman

   145  *

   146  * hash a string into a long int.  31 bit crc (from andrew appel).

   147  * the crc table is computed at run time by crcinit() -- we could

   148  * precompute, but it takes 1 clock tick on a 750.

   149  *

   150  * This fast table calculation works only if POLY is a prime polynomial

   151  * in the field of integers modulo 2.  Since the coefficients of a

   152  * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is

   153  * implicit.  IT MUST ALSO BE THE CASE that the coefficients of orders

   154  * 31 down to 25 are zero.  Happily, we have candidates, from

   155  * E. J.  Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):

   156  *	x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0

   157  *	x^31 + x^3 + x^0

   158  *

   159  * We reverse the bits to get:

   160  *	111101010000000000000000000000001 but drop the last 1

   161  *         f   5   0   0   0   0   0   0

   162  *	010010000000000000000000000000001 ditto, for 31-bit crc

   163  *	   4   8   0   0   0   0   0   0

   164  */

   165 

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

   167 

   168 static guint CrcTable[128];

   169 

   170 /*

   171  - crcinit - initialize tables for hash function

   172  */

   173 static void crcinit(void)

   174 {

   175 	int i, j;

   176 	guint sum;

   177 

   178 	for (i = 0; i < 128; ++i) {

   179 		sum = 0L;

   180 		for (j = 7 - 1; j >= 0; --j)

   181 			if (i & (1 << j))

   182 				sum ^= POLY >> j;

   183 		CrcTable[i] = sum;

   184 	}

   185 }

   186 

   187 /*

   188  - hash - Honeyman's nice hashing function

   189  */

   190 static guint honeyman_hash(gconstpointer key)

   191 {

   192 	const gchar *name = (const gchar *) key;

   193 	gint size;

   194 	guint sum = 0;

   195 

   196 	g_assert (name != NULL);

   197 	g_assert (*name != 0);

   198 

   199 	size = strlen(name);

   200 

   201 	while (size--) {

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

   203 	}

   204 

   205 	return(sum);

   206 }

   207 

   208 

   209 static gboolean second_hash_cmp (gconstpointer a, gconstpointer b)

   210 {

   211   return (strcmp (a, b) == 0);

   212 }

   213 

   214 

   215 

   216 static guint one_hash(gconstpointer key)

   217 {

   218   return 1;

   219 }

   220 

   221 

   222 static void not_even_foreach (gpointer       key,

   223 				 gpointer       value,

   224 				 gpointer	user_data)

   225 {

   226   const char *_key = (const char *) key;

   227   const char *_value = (const char *) value;

   228   int i;

   229   char val [20];

   230 

   231   g_assert (_key != NULL);

   232   g_assert (*_key != 0);

   233   g_assert (_value != NULL);

   234   g_assert (*_value != 0);

   235 

   236   i = atoi (_key);

   237 

   238   sprintf (val, "%d value", i);

   239   g_assert (strcmp (_value, val) == 0);

   240 

   241   g_assert ((i % 2) != 0);

   242   g_assert (i != 3);

   243 }

   244 

   245 

   246 static gboolean remove_even_foreach (gpointer       key,

   247 				 gpointer       value,

   248 				 gpointer	user_data)

   249 {

   250   const char *_key = (const char *) key;

   251   const char *_value = (const char *) value;

   252   int i;

   253   char val [20];

   254 

   255   g_assert (_key != NULL);

   256   g_assert (*_key != 0);

   257   g_assert (_value != NULL);

   258   g_assert (*_value != 0);

   259 

   260   i = atoi (_key);

   261 

   262   sprintf (val, "%d value", i);

   263   g_assert (strcmp (_value, val) == 0);

   264 

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

   266 }

   267 

   268 

   269 

   270 

   271 static void second_hash_test (gboolean simple_hash)

   272 {

   273      int       i;

   274      char      key[20] = "", val[20]="", *v, *orig_key, *orig_val;

   275      GHashTable     *h;

   276      gboolean found;

   277 

   278      crcinit ();

   279 

   280      h = g_hash_table_new_full (simple_hash ? one_hash : honeyman_hash,

   281      			        second_hash_cmp,

   282                                 g_free, g_free);

   283      g_assert (h != NULL);

   284      for (i=0; i<20; i++)

   285           {

   286           sprintf (key, "%d", i);

   287 	  g_assert (atoi (key) == i);

   288 

   289 	  sprintf (val, "%d value", i);

   290 	  g_assert (atoi (val) == i);

   291 

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

   293           }

   294 

   295      g_assert (g_hash_table_size (h) == 20);

   296 

   297      for (i=0; i<20; i++)

   298           {

   299           sprintf (key, "%d", i);

   300 	  g_assert (atoi(key) == i);

   301 

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

   303 

   304 	  g_assert (v != NULL);

   305 	  g_assert (*v != 0);

   306 	  g_assert (atoi (v) == i);

   307           }

   308 

   309      sprintf (key, "%d", 3);

   310      g_hash_table_remove (h, key);

   311      g_assert (g_hash_table_size (h) == 19);

   312      g_hash_table_foreach_remove (h, remove_even_foreach, NULL);

   313      g_assert (g_hash_table_size (h) == 9);

   314      g_hash_table_foreach (h, not_even_foreach, NULL);

   315 

   316      for (i=0; i<20; i++)

   317           {

   318           sprintf (key, "%d", i);

   319 	  g_assert (atoi(key) == i);

   320 

   321 	  sprintf (val, "%d value", i);

   322 	  g_assert (atoi (val) == i);

   323 

   324 	  orig_key = orig_val = NULL;

   325           found = g_hash_table_lookup_extended (h, key,

   326 	  					(gpointer)&orig_key,

   327 						(gpointer)&orig_val);

   328 	  if ((i % 2) == 0 || i == 3)

   329             {

   330               g_assert (!found);

   331   	      continue;

   332             }

   333 

   334 	  g_assert (found);

   335 

   336 	  g_assert (orig_key != NULL);

   337 	  g_assert (strcmp (key, orig_key) == 0);

   338 

   339 	  g_assert (orig_val != NULL);

   340 	  g_assert (strcmp (val, orig_val) == 0);

   341           }

   342 

   343     g_hash_table_destroy (h);

   344 }

   345 

   346 static gboolean find_first     (gpointer key, 

   347 				gpointer value, 

   348 				gpointer user_data)

   349 {

   350   gint *v = value; 

   351   gint *test = user_data;

   352   return (*v == *test);

   353 }

   354 

   355 

   356 static void direct_hash_test (void)

   357 {

   358      gint       i, rc;

   359      GHashTable     *h;

   360 

   361      h = g_hash_table_new (NULL, NULL);

   362      g_assert (h != NULL);

   363      for (i=1; i<=20; i++)

   364           {

   365           g_hash_table_insert (h, GINT_TO_POINTER (i),

   366 	  		       GINT_TO_POINTER (i + 42));

   367           }

   368 

   369      g_assert (g_hash_table_size (h) == 20);

   370 

   371      for (i=1; i<=20; i++)

   372           {

   373           rc = GPOINTER_TO_INT (

   374 	  	g_hash_table_lookup (h, GINT_TO_POINTER (i)));

   375 

   376 	  g_assert (rc != 0);

   377 	  g_assert ((rc - 42) == i);

   378           }

   379 

   380     g_hash_table_destroy (h);

   381 }

   382 

   383 

   384 

   385 int

   386 main (int   argc,

   387       char *argv[])

   388 {

   389   GHashTable *hash_table;

   390   gint i;

   391   gint value = 120;

   392   gint *pvalue;

   393   GList *keys, *values;

   394   gint keys_len, values_len;

   395   GHashTableIter iter;

   396   gpointer ikey, ivalue;

   397   int result_array[10000];

   398   

   399   #ifdef __SYMBIAN32__

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

   401   g_set_print_handler(mrtPrintHandler);

   402   #endif /*__SYMBIAN32__*/

   403 	  

   404 

   405   hash_table = g_hash_table_new (my_hash, my_hash_equal);

   406   fill_hash_table_and_array (hash_table);

   407   pvalue = g_hash_table_find (hash_table, find_first, &value);

   408   if (!pvalue || *pvalue != value)

   409     g_assert_not_reached();

   410 

   411   keys = g_hash_table_get_keys (hash_table);

   412   if (!keys)

   413     g_assert_not_reached ();

   414 

   415   values = g_hash_table_get_values (hash_table);

   416   if (!values)

   417     g_assert_not_reached ();

   418 

   419   keys_len = g_list_length (keys);

   420   values_len = g_list_length (values);

   421   if (values_len != keys_len &&  keys_len != g_hash_table_size (hash_table))

   422     g_assert_not_reached ();

   423 

   424   g_list_free (keys);

   425   g_list_free (values);

   426 

   427   init_result_array (result_array);

   428   g_hash_table_iter_init (&iter, hash_table);

   429   for (i = 0; i < 10000; i++)

   430     {

   431       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));

   432 

   433       handle_pair (ikey, ivalue, result_array);

   434 

   435       if (i % 2)

   436 	g_hash_table_iter_remove (&iter);

   437     }

   438   g_assert (! g_hash_table_iter_next (&iter, &ikey, &ivalue));

   439   g_assert (g_hash_table_size (hash_table) == 5000);

   440   verify_result_array (result_array);

   441 

   442   fill_hash_table_and_array (hash_table);

   443 

   444   init_result_array (result_array);

   445   g_hash_table_foreach (hash_table, my_hash_callback, result_array);

   446   verify_result_array (result_array);

   447 

   448   for (i = 0; i < 10000; i++)

   449     g_hash_table_remove (hash_table, &array[i]);

   450 

   451   fill_hash_table_and_array (hash_table);

   452 

   453   if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||

   454       g_hash_table_size (hash_table) != 5000)

   455     g_assert_not_reached();

   456 

   457   g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);

   458 

   459 

   460   g_hash_table_destroy (hash_table);

   461 

   462   second_hash_test (TRUE);

   463   second_hash_test (FALSE);

   464   direct_hash_test ();

   465   

   466   #if __SYMBIAN32__

   467   testResultXml("hash-test");

   468   #endif /* EMULATOR */

   469 

   470   return 0;

   471 

   472 }