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
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.
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.
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.
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/.
28 #undef G_DISABLE_ASSERT
50 my_hash_callback_remove (gpointer key,
63 my_hash_callback_remove_test (gpointer key,
70 g_assert_not_reached ();
74 my_hash_callback (gpointer key,
83 my_hash (gconstpointer key)
85 return (guint) *((const gint*) key);
89 my_hash_equal (gconstpointer a,
92 return *((const gint*) a) == *((const gint*) b);
98 * This is a simplified version of the pathalias hashing function.
99 * Thanks to Steve Belovin and Peter Honeyman
101 * hash a string into a long int. 31 bit crc (from andrew appel).
102 * the crc table is computed at run time by crcinit() -- we could
103 * precompute, but it takes 1 clock tick on a 750.
105 * This fast table calculation works only if POLY is a prime polynomial
106 * in the field of integers modulo 2. Since the coefficients of a
107 * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is
108 * implicit. IT MUST ALSO BE THE CASE that the coefficients of orders
109 * 31 down to 25 are zero. Happily, we have candidates, from
110 * E. J. Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
111 * x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
114 * We reverse the bits to get:
115 * 111101010000000000000000000000001 but drop the last 1
117 * 010010000000000000000000000000001 ditto, for 31-bit crc
121 #define POLY 0x48000000L /* 31-bit polynomial (avoids sign problems) */
123 static guint CrcTable[128];
126 - crcinit - initialize tables for hash function
128 static void crcinit(void)
133 for (i = 0; i < 128; ++i) {
135 for (j = 7 - 1; j >= 0; --j)
143 - hash - Honeyman's nice hashing function
145 static guint honeyman_hash(gconstpointer key)
147 const gchar *name = (const gchar *) key;
151 g_assert (name != NULL);
152 g_assert (*name != 0);
157 sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
164 static gboolean second_hash_cmp (gconstpointer a, gconstpointer b)
166 return (strcmp (a, b) == 0);
171 static guint one_hash(gconstpointer key)
177 static void not_even_foreach (gpointer key,
181 const char *_key = (const char *) key;
182 const char *_value = (const char *) value;
186 g_assert (_key != NULL);
187 g_assert (*_key != 0);
188 g_assert (_value != NULL);
189 g_assert (*_value != 0);
192 g_assert (atoi (_key) > 0);
194 sprintf (val, "%d value", i);
195 g_assert (strcmp (_value, val) == 0);
197 g_assert ((i % 2) != 0);
202 static gboolean remove_even_foreach (gpointer key,
206 const char *_key = (const char *) key;
207 const char *_value = (const char *) value;
211 g_assert (_key != NULL);
212 g_assert (*_key != 0);
213 g_assert (_value != NULL);
214 g_assert (*_value != 0);
219 sprintf (val, "%d value", i);
220 g_assert (strcmp (_value, val) == 0);
222 return ((i % 2) == 0) ? TRUE : FALSE;
228 static void second_hash_test (gboolean simple_hash)
231 char key[20] = "", val[20]="", *v, *orig_key, *orig_val;
237 h = g_hash_table_new (simple_hash ? one_hash : honeyman_hash,
239 g_assert (h != NULL);
242 sprintf (key, "%d", i);
243 g_assert (atoi (key) == i);
245 sprintf (val, "%d value", i);
246 g_assert (atoi (val) == i);
248 g_hash_table_insert (h, g_strdup (key), g_strdup (val));
251 g_assert (g_hash_table_size (h) == 20);
255 sprintf (key, "%d", i);
256 g_assert (atoi(key) == i);
258 v = (char *) g_hash_table_lookup (h, key);
260 g_assert (v != NULL);
262 g_assert (atoi (v) == i);
265 /**** future test stuff, yet to be debugged
266 sprintf (key, "%d", 3);
267 g_hash_table_remove (h, key);
268 g_hash_table_foreach_remove (h, remove_even_foreach, NULL);
269 g_hash_table_foreach (h, not_even_foreach, NULL);
274 if (((i % 2) == 0) || (i == 3))
277 sprintf (key, "%d", i);
278 g_assert (atoi(key) == i);
280 sprintf (val, "%d value", i);
281 g_assert (atoi (val) == i);
283 orig_key = orig_val = NULL;
284 found = g_hash_table_lookup_extended (h, key,
286 (gpointer)&orig_val);
289 g_assert (orig_key != NULL);
290 g_assert (strcmp (key, orig_key) == 0);
293 g_assert (orig_val != NULL);
294 g_assert (strcmp (val, orig_val) == 0);
298 g_hash_table_destroy (h);
302 static void direct_hash_test (void)
307 h = g_hash_table_new (NULL, NULL);
308 g_assert (h != NULL);
309 for (i=1; i<=20; i++)
311 g_hash_table_insert (h, GINT_TO_POINTER (i),
312 GINT_TO_POINTER (i + 42));
315 g_assert (g_hash_table_size (h) == 20);
317 for (i=1; i<=20; i++)
319 rc = GPOINTER_TO_INT (
320 g_hash_table_lookup (h, GINT_TO_POINTER (i)));
323 g_assert ((rc - 42) == i);
326 g_hash_table_destroy (h);
335 GHashTable *hash_table;
338 hash_table = g_hash_table_new (my_hash, my_hash_equal);
339 for (i = 0; i < 10000; i++)
342 g_hash_table_insert (hash_table, &array[i], &array[i]);
344 g_hash_table_foreach (hash_table, my_hash_callback, NULL);
346 for (i = 0; i < 10000; i++)
348 g_assert_not_reached();
350 for (i = 0; i < 10000; i++)
351 g_hash_table_remove (hash_table, &array[i]);
353 for (i = 0; i < 10000; i++)
356 g_hash_table_insert (hash_table, &array[i], &array[i]);
359 if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||
360 g_hash_table_size (hash_table) != 5000)
361 g_assert_not_reached();
363 g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
366 g_hash_table_destroy (hash_table);
368 second_hash_test (TRUE);
369 second_hash_test (FALSE);