Symaptic: os/ossrv/glib/tsrc/BC/tests/hash-test.c@260cb5ec6c19

     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  */

    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  */

    28 #undef G_DISABLE_ASSERT

    29 #undef G_LOG_DOMAIN

    31 #ifdef HAVE_CONFIG_H

    32 #  include <config.h>

    33 #endif

    35 #if STDC_HEADERS

    36 #include <stdio.h>

    37 #include <string.h>

    38 #include <stdlib.h>

    39 #endif

    41 #include <glib.h>

    44 #ifdef SYMBIAN

    45 #include "mrt2_glib2_test.h"

    46 #endif /*SYMBIAN*/

    50 int array[10000];

    54 static gboolean

    55 my_hash_callback_remove (gpointer key,

    56 			 gpointer value,

    57 			 gpointer user_data)

    58 {

    59   int *d = value;

    61   if ((*d) % 2)

    62     return TRUE;

    64   return FALSE;

    65 }

    67 static void

    68 my_hash_callback_remove_test (gpointer key,

    69 			      gpointer value,

    70 			      gpointer user_data)

    71 {

    72   int *d = value;

    74   if ((*d) % 2)

    75     g_assert_not_reached ();

    76 }

    78 static void

    79 my_hash_callback (gpointer key,

    80 		  gpointer value,

    81 		  gpointer user_data)

    82 {

    83   int *d = value;

    84   *d = 1;

    85 }

    87 static guint

    88 my_hash (gconstpointer key)

    89 {

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

    91 }

    93 static gboolean

    94 my_hash_equal (gconstpointer a,

    95 	       gconstpointer b)

    96 {

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

    98 }

   102 /*

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

   104  * Thanks to Steve Belovin and Peter Honeyman

   105  *

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

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

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

   109  *

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

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

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

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

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

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

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

   117  *	x^31 + x^3 + x^0

   118  *

   119  * We reverse the bits to get:

   120  *	111101010000000000000000000000001 but drop the last 1

   121  *         f   5   0   0   0   0   0   0

   122  *	010010000000000000000000000000001 ditto, for 31-bit crc

   123  *	   4   8   0   0   0   0   0   0

   124  */

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

   128 static guint CrcTable[128];

   130 /*

   131  - crcinit - initialize tables for hash function

   132  */

   133 static void crcinit(void)

   134 {

   135 	int i, j;

   136 	guint sum;

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

   139 		sum = 0L;

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

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

   142 				sum ^= POLY >> j;

   143 		CrcTable[i] = sum;

   144 	}

   145 }

   147 /*

   148  - hash - Honeyman's nice hashing function

   149  */

   150 static guint honeyman_hash(gconstpointer key)

   151 {

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

   153 	gint size;

   154 	guint sum = 0;

   156 	g_assert (name != NULL);

   157 	g_assert (*name != 0);

   159 	size = strlen(name);

   161 	while (size--) {

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

   163 	}

   165 	return(sum);

   166 }

   169 static gboolean second_hash_cmp (gconstpointer a, gconstpointer b)

   170 {

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

   172 }

   176 static guint one_hash(gconstpointer key)

   177 {

   178   return 1;

   179 }

   182 static void not_even_foreach (gpointer       key,

   183 				 gpointer       value,

   184 				 gpointer	user_data)

   185 {

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

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

   188   int i;

   189   char val [20];

   191   g_assert (_key != NULL);

   192   g_assert (*_key != 0);

   193   g_assert (_value != NULL);

   194   g_assert (*_value != 0);

   196   i = atoi (_key);

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

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

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

   202   g_assert (i != 3);

   203 }

   206 static gboolean remove_even_foreach (gpointer       key,

   207 				 gpointer       value,

   208 				 gpointer	user_data)

   209 {

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

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

   212   int i;

   213   char val [20];

   215   g_assert (_key != NULL);

   216   g_assert (*_key != 0);

   217   g_assert (_value != NULL);

   218   g_assert (*_value != 0);

   220   i = atoi (_key);

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

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

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

   226 }

   231 static void second_hash_test (gboolean simple_hash)

   232 {

   233      int       i;

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

   235      GHashTable     *h;

   236      gboolean found;

   238      crcinit ();

   240      h = g_hash_table_new (simple_hash ? one_hash : honeyman_hash,

   241      			   second_hash_cmp);

   242      g_assert (h != NULL);

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

   244           {

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

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

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

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

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

   252           }

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

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

   257           {

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

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

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

   263 	  g_assert (v != NULL);

   264 	  g_assert (*v != 0);

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

   266           }

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

   269      g_hash_table_remove (h, key);

   270      g_hash_table_foreach_remove (h, remove_even_foreach, NULL);

   271      g_hash_table_foreach (h, not_even_foreach, NULL);

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

   274           {

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

   276   	      continue;

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

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

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

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

   284 	  orig_key = orig_val = NULL;

   285           found = g_hash_table_lookup_extended (h, key,

   286 	  					(gpointer)&orig_key,

   287 						(gpointer)&orig_val);

   288 	  g_assert (found);

   290 	  g_hash_table_remove (h, key);

   292 	  g_assert (orig_key != NULL);

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

   294 	  g_free (orig_key);

   296 	  g_assert (orig_val != NULL);

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

   298 	  g_free (orig_val);

   299           }

   301     g_hash_table_destroy (h);

   302 }

   304 static gboolean find_first     (gpointer key,

   305 				gpointer value,

   306 				gpointer user_data)

   307 {

   308   gint *v = value;

   309   gint *test = user_data;

   310   return (*v == *test);

   311 }

   314 static void direct_hash_test (void)

   315 {

   316      gint       i, rc;

   317      GHashTable     *h;

   319      h = g_hash_table_new (NULL, NULL);

   320      g_assert (h != NULL);

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

   322           {

   323           g_hash_table_insert (h, GINT_TO_POINTER (i),

   324 	  		       GINT_TO_POINTER (i + 42));

   325           }

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

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

   330           {

   331           rc = GPOINTER_TO_INT (

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

   334 	  g_assert (rc != 0);

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

   336           }

   338     g_hash_table_destroy (h);

   339 }

   343 int

   344 main (int   argc,

   345       char *argv[])

   346 {

   347   GHashTable *hash_table;

   348   gint i;

   349   gint value = 120;

   350   gint *pvalue;

   352   #ifdef SYMBIAN

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

   354   g_set_print_handler(mrtPrintHandler);

   355   #endif /*SYMBIAN*/

   358   hash_table = g_hash_table_new (my_hash, my_hash_equal);

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

   360     {

   361       array[i] = i;

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

   363     }

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

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

   366     g_assert_not_reached();

   368   g_hash_table_foreach (hash_table, my_hash_callback, NULL);

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

   371     if (array[i] == 0)

   372       g_assert_not_reached();

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

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

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

   378     {

   379       array[i] = i;

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

   381     }

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

   384       g_hash_table_size (hash_table) != 5000)

   385     g_assert_not_reached();

   387   g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);

   390   g_hash_table_destroy (hash_table);

   392   second_hash_test (TRUE);

   393   second_hash_test (FALSE);

   394   direct_hash_test ();

   396   #if SYMBIAN

   397   testResultXml("hash-test");

   398   #endif /* EMULATOR */

   400   return 0;

   402 }

author	sl
	Tue, 10 Jun 2014 14:32:02 +0200
changeset 1	260cb5ec6c19
permissions	-rw-r--r--