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 * 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 45 int array[10000]; 46 47 static void 48 fill_hash_table_and_array (GHashTable *hash_table) 49 { 50 int i; 51 52 for (i = 0; i < 10000; i++) 53 { 54 array[i] = i; 55 g_hash_table_insert (hash_table, &array[i], &array[i]); 56 } 57 } 58 59 static void 60 init_result_array (int result_array[10000]) 61 { 62 int i; 63 64 for (i = 0; i < 10000; i++) 65 result_array[i] = -1; 66 } 67 68 static void 69 verify_result_array (int array[10000]) 70 { 71 int i; 72 73 for (i = 0; i < 10000; i++) 74 g_assert (array[i] == i); 75 } 76 77 static void 78 handle_pair (gpointer key, gpointer value, int result_array[10000]) 79 { 80 int n; 81 82 g_assert (key == value); 83 84 n = *((int *) value); 85 86 g_assert (n >= 0 && n < 10000); 87 g_assert (result_array[n] == -1); 88 89 result_array[n] = n; 90 } 91 92 static gboolean 93 my_hash_callback_remove (gpointer key, 94 gpointer value, 95 gpointer user_data) 96 { 97 int *d = value; 98 99 if ((*d) % 2) 100 return TRUE; 101 102 return FALSE; 103 } 104 105 static void 106 my_hash_callback_remove_test (gpointer key, 107 gpointer value, 108 gpointer user_data) 109 { 110 int *d = value; 111 112 if ((*d) % 2) 113 g_assert_not_reached (); 114 } 115 116 static void 117 my_hash_callback (gpointer key, 118 gpointer value, 119 gpointer user_data) 120 { 121 handle_pair (key, value, user_data); 122 } 123 124 static guint 125 my_hash (gconstpointer key) 126 { 127 return (guint) *((const gint*) key); 128 } 129 130 static gboolean 131 my_hash_equal (gconstpointer a, 132 gconstpointer b) 133 { 134 return *((const gint*) a) == *((const gint*) b); 135 } 136 137 138 139 /* 140 * This is a simplified version of the pathalias hashing function. 141 * Thanks to Steve Belovin and Peter Honeyman 142 * 143 * hash a string into a long int. 31 bit crc (from andrew appel). 144 * the crc table is computed at run time by crcinit() -- we could 145 * precompute, but it takes 1 clock tick on a 750. 146 * 147 * This fast table calculation works only if POLY is a prime polynomial 148 * in the field of integers modulo 2. Since the coefficients of a 149 * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is 150 * implicit. IT MUST ALSO BE THE CASE that the coefficients of orders 151 * 31 down to 25 are zero. Happily, we have candidates, from 152 * E. J. Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962): 153 * x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0 154 * x^31 + x^3 + x^0 155 * 156 * We reverse the bits to get: 157 * 111101010000000000000000000000001 but drop the last 1 158 * f 5 0 0 0 0 0 0 159 * 010010000000000000000000000000001 ditto, for 31-bit crc 160 * 4 8 0 0 0 0 0 0 161 */ 162 163 #define POLY 0x48000000L /* 31-bit polynomial (avoids sign problems) */ 164 165 static guint CrcTable[128]; 166 167 /* 168 - crcinit - initialize tables for hash function 169 */ 170 static void crcinit(void) 171 { 172 int i, j; 173 guint sum; 174 175 for (i = 0; i < 128; ++i) { 176 sum = 0L; 177 for (j = 7 - 1; j >= 0; --j) 178 if (i & (1 << j)) 179 sum ^= POLY >> j; 180 CrcTable[i] = sum; 181 } 182 } 183 184 /* 185 - hash - Honeyman's nice hashing function 186 */ 187 static guint honeyman_hash(gconstpointer key) 188 { 189 const gchar *name = (const gchar *) key; 190 gint size; 191 guint sum = 0; 192 193 g_assert (name != NULL); 194 g_assert (*name != 0); 195 196 size = strlen(name); 197 198 while (size--) { 199 sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f]; 200 } 201 202 return(sum); 203 } 204 205 206 static gboolean second_hash_cmp (gconstpointer a, gconstpointer b) 207 { 208 return (strcmp (a, b) == 0); 209 } 210 211 212 213 static guint one_hash(gconstpointer key) 214 { 215 return 1; 216 } 217 218 219 static void not_even_foreach (gpointer key, 220 gpointer value, 221 gpointer user_data) 222 { 223 const char *_key = (const char *) key; 224 const char *_value = (const char *) value; 225 int i; 226 char val [20]; 227 228 g_assert (_key != NULL); 229 g_assert (*_key != 0); 230 g_assert (_value != NULL); 231 g_assert (*_value != 0); 232 233 i = atoi (_key); 234 235 sprintf (val, "%d value", i); 236 g_assert (strcmp (_value, val) == 0); 237 238 g_assert ((i % 2) != 0); 239 g_assert (i != 3); 240 } 241 242 243 static gboolean remove_even_foreach (gpointer key, 244 gpointer value, 245 gpointer user_data) 246 { 247 const char *_key = (const char *) key; 248 const char *_value = (const char *) value; 249 int i; 250 char val [20]; 251 252 g_assert (_key != NULL); 253 g_assert (*_key != 0); 254 g_assert (_value != NULL); 255 g_assert (*_value != 0); 256 257 i = atoi (_key); 258 259 sprintf (val, "%d value", i); 260 g_assert (strcmp (_value, val) == 0); 261 262 return ((i % 2) == 0) ? TRUE : FALSE; 263 } 264 265 266 267 268 static void second_hash_test (gboolean simple_hash) 269 { 270 int i; 271 char key[20] = "", val[20]="", *v, *orig_key, *orig_val; 272 GHashTable *h; 273 gboolean found; 274 275 crcinit (); 276 277 h = g_hash_table_new_full (simple_hash ? one_hash : honeyman_hash, 278 second_hash_cmp, 279 g_free, g_free); 280 g_assert (h != NULL); 281 for (i=0; i<20; i++) 282 { 283 sprintf (key, "%d", i); 284 g_assert (atoi (key) == i); 285 286 sprintf (val, "%d value", i); 287 g_assert (atoi (val) == i); 288 289 g_hash_table_insert (h, g_strdup (key), g_strdup (val)); 290 } 291 292 g_assert (g_hash_table_size (h) == 20); 293 294 for (i=0; i<20; i++) 295 { 296 sprintf (key, "%d", i); 297 g_assert (atoi(key) == i); 298 299 v = (char *) g_hash_table_lookup (h, key); 300 301 g_assert (v != NULL); 302 g_assert (*v != 0); 303 g_assert (atoi (v) == i); 304 } 305 306 sprintf (key, "%d", 3); 307 g_hash_table_remove (h, key); 308 g_assert (g_hash_table_size (h) == 19); 309 g_hash_table_foreach_remove (h, remove_even_foreach, NULL); 310 g_assert (g_hash_table_size (h) == 9); 311 g_hash_table_foreach (h, not_even_foreach, NULL); 312 313 for (i=0; i<20; i++) 314 { 315 sprintf (key, "%d", i); 316 g_assert (atoi(key) == i); 317 318 sprintf (val, "%d value", i); 319 g_assert (atoi (val) == i); 320 321 orig_key = orig_val = NULL; 322 found = g_hash_table_lookup_extended (h, key, 323 (gpointer)&orig_key, 324 (gpointer)&orig_val); 325 if ((i % 2) == 0 || i == 3) 326 { 327 g_assert (!found); 328 continue; 329 } 330 331 g_assert (found); 332 333 g_assert (orig_key != NULL); 334 g_assert (strcmp (key, orig_key) == 0); 335 336 g_assert (orig_val != NULL); 337 g_assert (strcmp (val, orig_val) == 0); 338 } 339 340 g_hash_table_destroy (h); 341 } 342 343 static gboolean find_first (gpointer key, 344 gpointer value, 345 gpointer user_data) 346 { 347 gint *v = value; 348 gint *test = user_data; 349 return (*v == *test); 350 } 351 352 353 static void direct_hash_test (void) 354 { 355 gint i, rc; 356 GHashTable *h; 357 358 h = g_hash_table_new (NULL, NULL); 359 g_assert (h != NULL); 360 for (i=1; i<=20; i++) 361 { 362 g_hash_table_insert (h, GINT_TO_POINTER (i), 363 GINT_TO_POINTER (i + 42)); 364 } 365 366 g_assert (g_hash_table_size (h) == 20); 367 368 for (i=1; i<=20; i++) 369 { 370 rc = GPOINTER_TO_INT ( 371 g_hash_table_lookup (h, GINT_TO_POINTER (i))); 372 373 g_assert (rc != 0); 374 g_assert ((rc - 42) == i); 375 } 376 377 g_hash_table_destroy (h); 378 } 379 380 381 382 int 383 main (int argc, 384 char *argv[]) 385 { 386 GHashTable *hash_table; 387 gint i; 388 gint value = 120; 389 gint *pvalue; 390 GList *keys, *values; 391 gint keys_len, values_len; 392 GHashTableIter iter; 393 gpointer ikey, ivalue; 394 int result_array[10000]; 395 396 hash_table = g_hash_table_new (my_hash, my_hash_equal); 397 fill_hash_table_and_array (hash_table); 398 pvalue = g_hash_table_find (hash_table, find_first, &value); 399 if (!pvalue || *pvalue != value) 400 g_assert_not_reached(); 401 402 keys = g_hash_table_get_keys (hash_table); 403 if (!keys) 404 g_assert_not_reached (); 405 406 values = g_hash_table_get_values (hash_table); 407 if (!values) 408 g_assert_not_reached (); 409 410 keys_len = g_list_length (keys); 411 values_len = g_list_length (values); 412 if (values_len != keys_len && keys_len != g_hash_table_size (hash_table)) 413 g_assert_not_reached (); 414 415 g_list_free (keys); 416 g_list_free (values); 417 418 init_result_array (result_array); 419 g_hash_table_iter_init (&iter, hash_table); 420 for (i = 0; i < 10000; i++) 421 { 422 g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue)); 423 424 handle_pair (ikey, ivalue, result_array); 425 426 if (i % 2) 427 g_hash_table_iter_remove (&iter); 428 } 429 g_assert (! g_hash_table_iter_next (&iter, &ikey, &ivalue)); 430 g_assert (g_hash_table_size (hash_table) == 5000); 431 verify_result_array (result_array); 432 433 fill_hash_table_and_array (hash_table); 434 435 init_result_array (result_array); 436 g_hash_table_foreach (hash_table, my_hash_callback, result_array); 437 verify_result_array (result_array); 438 439 for (i = 0; i < 10000; i++) 440 g_hash_table_remove (hash_table, &array[i]); 441 442 fill_hash_table_and_array (hash_table); 443 444 if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 || 445 g_hash_table_size (hash_table) != 5000) 446 g_assert_not_reached(); 447 448 g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL); 449 450 451 g_hash_table_destroy (hash_table); 452 453 second_hash_test (TRUE); 454 second_hash_test (FALSE); 455 direct_hash_test (); 456 457 return 0; 458 459 } 460
