1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/glib/tsrc/BC/tests/hash-test.c Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,402 @@
1.4 +/* GLIB - Library of useful routines for C programming
1.5 + * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
1.6 + * Copyright (C) 1999 The Free Software Foundation
1.7 + * Portion Copyright © 2008-09 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.
1.8 + * This library is free software; you can redistribute it and/or
1.9 + * modify it under the terms of the GNU Lesser General Public
1.10 + * License as published by the Free Software Foundation; either
1.11 + * version 2 of the License, or (at your option) any later version.
1.12 + *
1.13 + * This library is distributed in the hope that it will be useful,
1.14 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
1.15 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1.16 + * Lesser General Public License for more details.
1.17 + *
1.18 + * You should have received a copy of the GNU Lesser General Public
1.19 + * License along with this library; if not, write to the
1.20 + * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
1.21 + * Boston, MA 02111-1307, USA.
1.22 + */
1.23 +
1.24 +/*
1.25 + * Modified by the GLib Team and others 1997-2000. See the AUTHORS
1.26 + * file for a list of people on the GLib Team. See the ChangeLog
1.27 + * files for a list of changes. These files are distributed with
1.28 + * GLib at ftp://ftp.gtk.org/pub/gtk/.
1.29 + */
1.30 +
1.31 +#undef G_DISABLE_ASSERT
1.32 +#undef G_LOG_DOMAIN
1.33 +
1.34 +#ifdef HAVE_CONFIG_H
1.35 +# include <config.h>
1.36 +#endif
1.37 +
1.38 +#if STDC_HEADERS
1.39 +#include <stdio.h>
1.40 +#include <string.h>
1.41 +#include <stdlib.h>
1.42 +#endif
1.43 +
1.44 +#include <glib.h>
1.45 +
1.46 +
1.47 +#ifdef SYMBIAN
1.48 +#include "mrt2_glib2_test.h"
1.49 +#endif /*SYMBIAN*/
1.50 +
1.51 +
1.52 +
1.53 +int array[10000];
1.54 +
1.55 +
1.56 +
1.57 +static gboolean
1.58 +my_hash_callback_remove (gpointer key,
1.59 + gpointer value,
1.60 + gpointer user_data)
1.61 +{
1.62 + int *d = value;
1.63 +
1.64 + if ((*d) % 2)
1.65 + return TRUE;
1.66 +
1.67 + return FALSE;
1.68 +}
1.69 +
1.70 +static void
1.71 +my_hash_callback_remove_test (gpointer key,
1.72 + gpointer value,
1.73 + gpointer user_data)
1.74 +{
1.75 + int *d = value;
1.76 +
1.77 + if ((*d) % 2)
1.78 + g_assert_not_reached ();
1.79 +}
1.80 +
1.81 +static void
1.82 +my_hash_callback (gpointer key,
1.83 + gpointer value,
1.84 + gpointer user_data)
1.85 +{
1.86 + int *d = value;
1.87 + *d = 1;
1.88 +}
1.89 +
1.90 +static guint
1.91 +my_hash (gconstpointer key)
1.92 +{
1.93 + return (guint) *((const gint*) key);
1.94 +}
1.95 +
1.96 +static gboolean
1.97 +my_hash_equal (gconstpointer a,
1.98 + gconstpointer b)
1.99 +{
1.100 + return *((const gint*) a) == *((const gint*) b);
1.101 +}
1.102 +
1.103 +
1.104 +
1.105 +/*
1.106 + * This is a simplified version of the pathalias hashing function.
1.107 + * Thanks to Steve Belovin and Peter Honeyman
1.108 + *
1.109 + * hash a string into a long int. 31 bit crc (from andrew appel).
1.110 + * the crc table is computed at run time by crcinit() -- we could
1.111 + * precompute, but it takes 1 clock tick on a 750.
1.112 + *
1.113 + * This fast table calculation works only if POLY is a prime polynomial
1.114 + * in the field of integers modulo 2. Since the coefficients of a
1.115 + * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is
1.116 + * implicit. IT MUST ALSO BE THE CASE that the coefficients of orders
1.117 + * 31 down to 25 are zero. Happily, we have candidates, from
1.118 + * E. J. Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
1.119 + * x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
1.120 + * x^31 + x^3 + x^0
1.121 + *
1.122 + * We reverse the bits to get:
1.123 + * 111101010000000000000000000000001 but drop the last 1
1.124 + * f 5 0 0 0 0 0 0
1.125 + * 010010000000000000000000000000001 ditto, for 31-bit crc
1.126 + * 4 8 0 0 0 0 0 0
1.127 + */
1.128 +
1.129 +#define POLY 0x48000000L /* 31-bit polynomial (avoids sign problems) */
1.130 +
1.131 +static guint CrcTable[128];
1.132 +
1.133 +/*
1.134 + - crcinit - initialize tables for hash function
1.135 + */
1.136 +static void crcinit(void)
1.137 +{
1.138 + int i, j;
1.139 + guint sum;
1.140 +
1.141 + for (i = 0; i < 128; ++i) {
1.142 + sum = 0L;
1.143 + for (j = 7 - 1; j >= 0; --j)
1.144 + if (i & (1 << j))
1.145 + sum ^= POLY >> j;
1.146 + CrcTable[i] = sum;
1.147 + }
1.148 +}
1.149 +
1.150 +/*
1.151 + - hash - Honeyman's nice hashing function
1.152 + */
1.153 +static guint honeyman_hash(gconstpointer key)
1.154 +{
1.155 + const gchar *name = (const gchar *) key;
1.156 + gint size;
1.157 + guint sum = 0;
1.158 +
1.159 + g_assert (name != NULL);
1.160 + g_assert (*name != 0);
1.161 +
1.162 + size = strlen(name);
1.163 +
1.164 + while (size--) {
1.165 + sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
1.166 + }
1.167 +
1.168 + return(sum);
1.169 +}
1.170 +
1.171 +
1.172 +static gboolean second_hash_cmp (gconstpointer a, gconstpointer b)
1.173 +{
1.174 + return (strcmp (a, b) == 0);
1.175 +}
1.176 +
1.177 +
1.178 +
1.179 +static guint one_hash(gconstpointer key)
1.180 +{
1.181 + return 1;
1.182 +}
1.183 +
1.184 +
1.185 +static void not_even_foreach (gpointer key,
1.186 + gpointer value,
1.187 + gpointer user_data)
1.188 +{
1.189 + const char *_key = (const char *) key;
1.190 + const char *_value = (const char *) value;
1.191 + int i;
1.192 + char val [20];
1.193 +
1.194 + g_assert (_key != NULL);
1.195 + g_assert (*_key != 0);
1.196 + g_assert (_value != NULL);
1.197 + g_assert (*_value != 0);
1.198 +
1.199 + i = atoi (_key);
1.200 +
1.201 + sprintf (val, "%d value", i);
1.202 + g_assert (strcmp (_value, val) == 0);
1.203 +
1.204 + g_assert ((i % 2) != 0);
1.205 + g_assert (i != 3);
1.206 +}
1.207 +
1.208 +
1.209 +static gboolean remove_even_foreach (gpointer key,
1.210 + gpointer value,
1.211 + gpointer user_data)
1.212 +{
1.213 + const char *_key = (const char *) key;
1.214 + const char *_value = (const char *) value;
1.215 + int i;
1.216 + char val [20];
1.217 +
1.218 + g_assert (_key != NULL);
1.219 + g_assert (*_key != 0);
1.220 + g_assert (_value != NULL);
1.221 + g_assert (*_value != 0);
1.222 +
1.223 + i = atoi (_key);
1.224 +
1.225 + sprintf (val, "%d value", i);
1.226 + g_assert (strcmp (_value, val) == 0);
1.227 +
1.228 + return ((i % 2) == 0) ? TRUE : FALSE;
1.229 +}
1.230 +
1.231 +
1.232 +
1.233 +
1.234 +static void second_hash_test (gboolean simple_hash)
1.235 +{
1.236 + int i;
1.237 + char key[20] = "", val[20]="", *v, *orig_key, *orig_val;
1.238 + GHashTable *h;
1.239 + gboolean found;
1.240 +
1.241 + crcinit ();
1.242 +
1.243 + h = g_hash_table_new (simple_hash ? one_hash : honeyman_hash,
1.244 + second_hash_cmp);
1.245 + g_assert (h != NULL);
1.246 + for (i=0; i<20; i++)
1.247 + {
1.248 + sprintf (key, "%d", i);
1.249 + g_assert (atoi (key) == i);
1.250 +
1.251 + sprintf (val, "%d value", i);
1.252 + g_assert (atoi (val) == i);
1.253 +
1.254 + g_hash_table_insert (h, g_strdup (key), g_strdup (val));
1.255 + }
1.256 +
1.257 + g_assert (g_hash_table_size (h) == 20);
1.258 +
1.259 + for (i=0; i<20; i++)
1.260 + {
1.261 + sprintf (key, "%d", i);
1.262 + g_assert (atoi(key) == i);
1.263 +
1.264 + v = (char *) g_hash_table_lookup (h, key);
1.265 +
1.266 + g_assert (v != NULL);
1.267 + g_assert (*v != 0);
1.268 + g_assert (atoi (v) == i);
1.269 + }
1.270 +
1.271 + sprintf (key, "%d", 3);
1.272 + g_hash_table_remove (h, key);
1.273 + g_hash_table_foreach_remove (h, remove_even_foreach, NULL);
1.274 + g_hash_table_foreach (h, not_even_foreach, NULL);
1.275 +
1.276 + for (i=0; i<20; i++)
1.277 + {
1.278 + if ((i % 2) == 0 || i == 3)
1.279 + continue;
1.280 +
1.281 + sprintf (key, "%d", i);
1.282 + g_assert (atoi(key) == i);
1.283 +
1.284 + sprintf (val, "%d value", i);
1.285 + g_assert (atoi (val) == i);
1.286 +
1.287 + orig_key = orig_val = NULL;
1.288 + found = g_hash_table_lookup_extended (h, key,
1.289 + (gpointer)&orig_key,
1.290 + (gpointer)&orig_val);
1.291 + g_assert (found);
1.292 +
1.293 + g_hash_table_remove (h, key);
1.294 +
1.295 + g_assert (orig_key != NULL);
1.296 + g_assert (strcmp (key, orig_key) == 0);
1.297 + g_free (orig_key);
1.298 +
1.299 + g_assert (orig_val != NULL);
1.300 + g_assert (strcmp (val, orig_val) == 0);
1.301 + g_free (orig_val);
1.302 + }
1.303 +
1.304 + g_hash_table_destroy (h);
1.305 +}
1.306 +
1.307 +static gboolean find_first (gpointer key,
1.308 + gpointer value,
1.309 + gpointer user_data)
1.310 +{
1.311 + gint *v = value;
1.312 + gint *test = user_data;
1.313 + return (*v == *test);
1.314 +}
1.315 +
1.316 +
1.317 +static void direct_hash_test (void)
1.318 +{
1.319 + gint i, rc;
1.320 + GHashTable *h;
1.321 +
1.322 + h = g_hash_table_new (NULL, NULL);
1.323 + g_assert (h != NULL);
1.324 + for (i=1; i<=20; i++)
1.325 + {
1.326 + g_hash_table_insert (h, GINT_TO_POINTER (i),
1.327 + GINT_TO_POINTER (i + 42));
1.328 + }
1.329 +
1.330 + g_assert (g_hash_table_size (h) == 20);
1.331 +
1.332 + for (i=1; i<=20; i++)
1.333 + {
1.334 + rc = GPOINTER_TO_INT (
1.335 + g_hash_table_lookup (h, GINT_TO_POINTER (i)));
1.336 +
1.337 + g_assert (rc != 0);
1.338 + g_assert ((rc - 42) == i);
1.339 + }
1.340 +
1.341 + g_hash_table_destroy (h);
1.342 +}
1.343 +
1.344 +
1.345 +
1.346 +int
1.347 +main (int argc,
1.348 + char *argv[])
1.349 +{
1.350 + GHashTable *hash_table;
1.351 + gint i;
1.352 + gint value = 120;
1.353 + gint *pvalue;
1.354 +
1.355 + #ifdef SYMBIAN
1.356 + 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);
1.357 + g_set_print_handler(mrtPrintHandler);
1.358 + #endif /*SYMBIAN*/
1.359 +
1.360 +
1.361 + hash_table = g_hash_table_new (my_hash, my_hash_equal);
1.362 + for (i = 0; i < 10000; i++)
1.363 + {
1.364 + array[i] = i;
1.365 + g_hash_table_insert (hash_table, &array[i], &array[i]);
1.366 + }
1.367 + pvalue = g_hash_table_find (hash_table, find_first, &value);
1.368 + if (!pvalue || *pvalue != value)
1.369 + g_assert_not_reached();
1.370 +
1.371 + g_hash_table_foreach (hash_table, my_hash_callback, NULL);
1.372 +
1.373 + for (i = 0; i < 10000; i++)
1.374 + if (array[i] == 0)
1.375 + g_assert_not_reached();
1.376 +
1.377 + for (i = 0; i < 10000; i++)
1.378 + g_hash_table_remove (hash_table, &array[i]);
1.379 +
1.380 + for (i = 0; i < 10000; i++)
1.381 + {
1.382 + array[i] = i;
1.383 + g_hash_table_insert (hash_table, &array[i], &array[i]);
1.384 + }
1.385 +
1.386 + if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||
1.387 + g_hash_table_size (hash_table) != 5000)
1.388 + g_assert_not_reached();
1.389 +
1.390 + g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
1.391 +
1.392 +
1.393 + g_hash_table_destroy (hash_table);
1.394 +
1.395 + second_hash_test (TRUE);
1.396 + second_hash_test (FALSE);
1.397 + direct_hash_test ();
1.398 +
1.399 + #if SYMBIAN
1.400 + testResultXml("hash-test");
1.401 + #endif /* EMULATOR */
1.402 +
1.403 + return 0;
1.404 +
1.405 +}