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
45int array[10000];
46
47static void
48fill_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
59static void
60init_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
68static void
69verify_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
77static void
78handle_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
92static gboolean
93my_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
105static void
106my_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
116static void
117my_hash_callback (gpointer key,
118		  gpointer value,
119		  gpointer user_data)
120{
121  handle_pair (key, value, user_data);
122}
123
124static guint
125my_hash (gconstpointer key)
126{
127  return (guint) *((const gint*) key);
128}
129
130static gboolean
131my_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
165static guint CrcTable[128];
166
167/*
168 - crcinit - initialize tables for hash function
169 */
170static 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 */
187static 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
206static gboolean second_hash_cmp (gconstpointer a, gconstpointer b)
207{
208  return (strcmp (a, b) == 0);
209}
210
211
212
213static guint one_hash(gconstpointer key)
214{
215  return 1;
216}
217
218
219static 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
243static 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
268static 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
343static 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
353static 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
382int
383main (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