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
fill_hash_table_and_array(GHashTable * hash_table)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
init_result_array(int result_array[10000])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
verify_result_array(int array[10000])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
handle_pair(gpointer key,gpointer value,int result_array[10000])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
my_hash_callback_remove(gpointer key,gpointer value,gpointer user_data)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
my_hash_callback_remove_test(gpointer key,gpointer value,gpointer user_data)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
my_hash_callback(gpointer key,gpointer value,gpointer user_data)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
my_hash(gconstpointer key)125 my_hash (gconstpointer key)
126 {
127 return (guint) *((const gint*) key);
128 }
129
130 static gboolean
my_hash_equal(gconstpointer a,gconstpointer b)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 */
crcinit(void)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 */
honeyman_hash(gconstpointer key)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
second_hash_cmp(gconstpointer a,gconstpointer b)206 static gboolean second_hash_cmp (gconstpointer a, gconstpointer b)
207 {
208 return (strcmp (a, b) == 0);
209 }
210
211
212
one_hash(gconstpointer key)213 static guint one_hash(gconstpointer key)
214 {
215 return 1;
216 }
217
218
not_even_foreach(gpointer key,gpointer value,gpointer user_data)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
remove_even_foreach(gpointer key,gpointer value,gpointer user_data)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
second_hash_test(gboolean simple_hash)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
find_first(gpointer key,gpointer value,gpointer user_data)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
direct_hash_test(void)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
main(int argc,char * argv[])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