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
48 fill_hash_table_and_array (GHashTable
*hash_table
)
52 for (i
= 0; i
< 10000; i
++)
55 g_hash_table_insert (hash_table
, &array
[i
], &array
[i
]);
60 init_result_array (int result_array
[10000])
64 for (i
= 0; i
< 10000; i
++)
69 verify_result_array (int array
[10000])
73 for (i
= 0; i
< 10000; i
++)
74 g_assert (array
[i
] == i
);
78 handle_pair (gpointer key
, gpointer value
, int result_array
[10000])
82 g_assert (key
== value
);
86 g_assert (n
>= 0 && n
< 10000);
87 g_assert (result_array
[n
] == -1);
93 my_hash_callback_remove (gpointer key
,
106 my_hash_callback_remove_test (gpointer key
,
113 g_assert_not_reached ();
117 my_hash_callback (gpointer key
,
121 handle_pair (key
, value
, user_data
);
125 my_hash (gconstpointer key
)
127 return (guint
) *((const gint
*) key
);
131 my_hash_equal (gconstpointer a
,
134 return *((const gint
*) a
) == *((const gint
*) b
);
140 * This is a simplified version of the pathalias hashing function.
141 * Thanks to Steve Belovin and Peter Honeyman
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.
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
156 * We reverse the bits to get:
157 * 111101010000000000000000000000001 but drop the last 1
159 * 010010000000000000000000000000001 ditto, for 31-bit crc
163 #define POLY 0x48000000L /* 31-bit polynomial (avoids sign problems) */
165 static guint CrcTable
[128];
168 - crcinit - initialize tables for hash function
170 static void crcinit(void)
175 for (i
= 0; i
< 128; ++i
) {
177 for (j
= 7 - 1; j
>= 0; --j
)
185 - hash - Honeyman's nice hashing function
187 static guint
honeyman_hash(gconstpointer key
)
189 const gchar
*name
= (const gchar
*) key
;
193 g_assert (name
!= NULL
);
194 g_assert (*name
!= 0);
199 sum
= (sum
>> 7) ^ CrcTable
[(sum
^ (*name
++)) & 0x7f];
206 static gboolean
second_hash_cmp (gconstpointer a
, gconstpointer b
)
208 return (strcmp (a
, b
) == 0);
213 static guint
one_hash(gconstpointer key
)
219 static void not_even_foreach (gpointer key
,
223 const char *_key
= (const char *) key
;
224 const char *_value
= (const char *) value
;
228 g_assert (_key
!= NULL
);
229 g_assert (*_key
!= 0);
230 g_assert (_value
!= NULL
);
231 g_assert (*_value
!= 0);
235 sprintf (val
, "%d value", i
);
236 g_assert (strcmp (_value
, val
) == 0);
238 g_assert ((i
% 2) != 0);
243 static gboolean
remove_even_foreach (gpointer key
,
247 const char *_key
= (const char *) key
;
248 const char *_value
= (const char *) value
;
252 g_assert (_key
!= NULL
);
253 g_assert (*_key
!= 0);
254 g_assert (_value
!= NULL
);
255 g_assert (*_value
!= 0);
259 sprintf (val
, "%d value", i
);
260 g_assert (strcmp (_value
, val
) == 0);
262 return ((i
% 2) == 0) ? TRUE
: FALSE
;
268 static void second_hash_test (gboolean simple_hash
)
271 char key
[20] = "", val
[20]="", *v
, *orig_key
, *orig_val
;
277 h
= g_hash_table_new_full (simple_hash
? one_hash
: honeyman_hash
,
280 g_assert (h
!= NULL
);
283 sprintf (key
, "%d", i
);
284 g_assert (atoi (key
) == i
);
286 sprintf (val
, "%d value", i
);
287 g_assert (atoi (val
) == i
);
289 g_hash_table_insert (h
, g_strdup (key
), g_strdup (val
));
292 g_assert (g_hash_table_size (h
) == 20);
296 sprintf (key
, "%d", i
);
297 g_assert (atoi(key
) == i
);
299 v
= (char *) g_hash_table_lookup (h
, key
);
301 g_assert (v
!= NULL
);
303 g_assert (atoi (v
) == i
);
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
);
315 sprintf (key
, "%d", i
);
316 g_assert (atoi(key
) == i
);
318 sprintf (val
, "%d value", i
);
319 g_assert (atoi (val
) == i
);
321 orig_key
= orig_val
= NULL
;
322 found
= g_hash_table_lookup_extended (h
, key
,
324 (gpointer
)&orig_val
);
325 if ((i
% 2) == 0 || i
== 3)
333 g_assert (orig_key
!= NULL
);
334 g_assert (strcmp (key
, orig_key
) == 0);
336 g_assert (orig_val
!= NULL
);
337 g_assert (strcmp (val
, orig_val
) == 0);
340 g_hash_table_destroy (h
);
343 static gboolean
find_first (gpointer key
,
348 gint
*test
= user_data
;
349 return (*v
== *test
);
353 static void direct_hash_test (void)
358 h
= g_hash_table_new (NULL
, NULL
);
359 g_assert (h
!= NULL
);
360 for (i
=1; i
<=20; i
++)
362 g_hash_table_insert (h
, GINT_TO_POINTER (i
),
363 GINT_TO_POINTER (i
+ 42));
366 g_assert (g_hash_table_size (h
) == 20);
368 for (i
=1; i
<=20; i
++)
370 rc
= GPOINTER_TO_INT (
371 g_hash_table_lookup (h
, GINT_TO_POINTER (i
)));
374 g_assert ((rc
- 42) == i
);
377 g_hash_table_destroy (h
);
386 GHashTable
*hash_table
;
390 GList
*keys
, *values
;
391 gint keys_len
, values_len
;
393 gpointer ikey
, ivalue
;
394 int result_array
[10000];
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();
402 keys
= g_hash_table_get_keys (hash_table
);
404 g_assert_not_reached ();
406 values
= g_hash_table_get_values (hash_table
);
408 g_assert_not_reached ();
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 ();
416 g_list_free (values
);
418 init_result_array (result_array
);
419 g_hash_table_iter_init (&iter
, hash_table
);
420 for (i
= 0; i
< 10000; i
++)
422 g_assert (g_hash_table_iter_next (&iter
, &ikey
, &ivalue
));
424 handle_pair (ikey
, ivalue
, result_array
);
427 g_hash_table_iter_remove (&iter
);
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
);
433 fill_hash_table_and_array (hash_table
);
435 init_result_array (result_array
);
436 g_hash_table_foreach (hash_table
, my_hash_callback
, result_array
);
437 verify_result_array (result_array
);
439 for (i
= 0; i
< 10000; i
++)
440 g_hash_table_remove (hash_table
, &array
[i
]);
442 fill_hash_table_and_array (hash_table
);
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();
448 g_hash_table_foreach (hash_table
, my_hash_callback_remove_test
, NULL
);
451 g_hash_table_destroy (hash_table
);
453 second_hash_test (TRUE
);
454 second_hash_test (FALSE
);