hash-test.c revision 7c65cf59155b264a709b29436ce577b6385d11b4 
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
47
48
49static gboolean
50my_hash_callback_remove (gpointer key,
51			 gpointer value,
52			 gpointer user_data)
53{
54  int *d = value;
55
56  if ((*d) % 2)
57    return TRUE;
58
59  return FALSE;
60}
61
62static void
63my_hash_callback_remove_test (gpointer key,
64			      gpointer value,
65			      gpointer user_data)
66{
67  int *d = value;
68
69  if ((*d) % 2)
70    g_assert_not_reached ();
71}
72
73static void
74my_hash_callback (gpointer key,
75		  gpointer value,
76		  gpointer user_data)
77{
78  int *d = value;
79  *d = 1;
80}
81
82static guint
83my_hash (gconstpointer key)
84{
85  return (guint) *((const gint*) key);
86}
87
88static gboolean
89my_hash_equal (gconstpointer a,
90	       gconstpointer b)
91{
92  return *((const gint*) a) == *((const gint*) b);
93}
94
95
96
97/*
98 * This is a simplified version of the pathalias hashing function.
99 * Thanks to Steve Belovin and Peter Honeyman
100 *
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.
104 *
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
112 *	x^31 + x^3 + x^0
113 *
114 * We reverse the bits to get:
115 *	111101010000000000000000000000001 but drop the last 1
116 *         f   5   0   0   0   0   0   0
117 *	010010000000000000000000000000001 ditto, for 31-bit crc
118 *	   4   8   0   0   0   0   0   0
119 */
120
121#define POLY 0x48000000L	/* 31-bit polynomial (avoids sign problems) */
122
123static guint CrcTable[128];
124
125/*
126 - crcinit - initialize tables for hash function
127 */
128static void crcinit(void)
129{
130	int i, j;
131	guint sum;
132
133	for (i = 0; i < 128; ++i) {
134		sum = 0L;
135		for (j = 7 - 1; j >= 0; --j)
136			if (i & (1 << j))
137				sum ^= POLY >> j;
138		CrcTable[i] = sum;
139	}
140}
141
142/*
143 - hash - Honeyman's nice hashing function
144 */
145static guint honeyman_hash(gconstpointer key)
146{
147	const gchar *name = (const gchar *) key;
148	gint size;
149	guint sum = 0;
150
151	g_assert (name != NULL);
152	g_assert (*name != 0);
153
154	size = strlen(name);
155
156	while (size--) {
157		sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
158	}
159
160	return(sum);
161}
162
163
164static gboolean second_hash_cmp (gconstpointer a, gconstpointer b)
165{
166  return (strcmp (a, b) == 0);
167}
168
169
170
171static guint one_hash(gconstpointer key)
172{
173  return 1;
174}
175
176
177static void not_even_foreach (gpointer       key,
178				 gpointer       value,
179				 gpointer	user_data)
180{
181  const char *_key = (const char *) key;
182  const char *_value = (const char *) value;
183  int i;
184  char val [20];
185
186  g_assert (_key != NULL);
187  g_assert (*_key != 0);
188  g_assert (_value != NULL);
189  g_assert (*_value != 0);
190
191  i = atoi (_key);
192
193  sprintf (val, "%d value", i);
194  g_assert (strcmp (_value, val) == 0);
195
196  g_assert ((i % 2) != 0);
197  g_assert (i != 3);
198}
199
200
201static gboolean remove_even_foreach (gpointer       key,
202				 gpointer       value,
203				 gpointer	user_data)
204{
205  const char *_key = (const char *) key;
206  const char *_value = (const char *) value;
207  int i;
208  char val [20];
209
210  g_assert (_key != NULL);
211  g_assert (*_key != 0);
212  g_assert (_value != NULL);
213  g_assert (*_value != 0);
214
215  i = atoi (_key);
216
217  sprintf (val, "%d value", i);
218  g_assert (strcmp (_value, val) == 0);
219
220  return ((i % 2) == 0) ? TRUE : FALSE;
221}
222
223
224
225
226static void second_hash_test (gboolean simple_hash)
227{
228     int       i;
229     char      key[20] = "", val[20]="", *v, *orig_key, *orig_val;
230     GHashTable     *h;
231     gboolean found;
232
233     crcinit ();
234
235     h = g_hash_table_new_full (simple_hash ? one_hash : honeyman_hash,
236     			        second_hash_cmp,
237                                g_free, g_free);
238     g_assert (h != NULL);
239     for (i=0; i<20; i++)
240          {
241          sprintf (key, "%d", i);
242	  g_assert (atoi (key) == i);
243
244	  sprintf (val, "%d value", i);
245	  g_assert (atoi (val) == i);
246
247          g_hash_table_insert (h, g_strdup (key), g_strdup (val));
248          }
249
250     g_assert (g_hash_table_size (h) == 20);
251
252     for (i=0; i<20; i++)
253          {
254          sprintf (key, "%d", i);
255	  g_assert (atoi(key) == i);
256
257          v = (char *) g_hash_table_lookup (h, key);
258
259	  g_assert (v != NULL);
260	  g_assert (*v != 0);
261	  g_assert (atoi (v) == i);
262          }
263
264     sprintf (key, "%d", 3);
265     g_hash_table_remove (h, key);
266     g_assert (g_hash_table_size (h) == 19);
267     g_hash_table_foreach_remove (h, remove_even_foreach, NULL);
268     g_assert (g_hash_table_size (h) == 9);
269     g_hash_table_foreach (h, not_even_foreach, NULL);
270
271     for (i=0; i<20; i++)
272          {
273          sprintf (key, "%d", i);
274	  g_assert (atoi(key) == i);
275
276	  sprintf (val, "%d value", i);
277	  g_assert (atoi (val) == i);
278
279	  orig_key = orig_val = NULL;
280          found = g_hash_table_lookup_extended (h, key,
281	  					(gpointer)&orig_key,
282						(gpointer)&orig_val);
283	  if ((i % 2) == 0 || i == 3)
284            {
285              g_assert (!found);
286  	      continue;
287            }
288
289	  g_assert (found);
290
291	  g_assert (orig_key != NULL);
292	  g_assert (strcmp (key, orig_key) == 0);
293
294	  g_assert (orig_val != NULL);
295	  g_assert (strcmp (val, orig_val) == 0);
296          }
297
298    g_hash_table_destroy (h);
299}
300
301static gboolean find_first     (gpointer key,
302				gpointer value,
303				gpointer user_data)
304{
305  gint *v = value;
306  gint *test = user_data;
307  return (*v == *test);
308}
309
310
311static void direct_hash_test (void)
312{
313     gint       i, rc;
314     GHashTable     *h;
315
316     h = g_hash_table_new (NULL, NULL);
317     g_assert (h != NULL);
318     for (i=1; i<=20; i++)
319          {
320          g_hash_table_insert (h, GINT_TO_POINTER (i),
321	  		       GINT_TO_POINTER (i + 42));
322          }
323
324     g_assert (g_hash_table_size (h) == 20);
325
326     for (i=1; i<=20; i++)
327          {
328          rc = GPOINTER_TO_INT (
329	  	g_hash_table_lookup (h, GINT_TO_POINTER (i)));
330
331	  g_assert (rc != 0);
332	  g_assert ((rc - 42) == i);
333          }
334
335    g_hash_table_destroy (h);
336}
337
338
339
340int
341main (int   argc,
342      char *argv[])
343{
344  GHashTable *hash_table;
345  gint i;
346  gint value = 120;
347  gint *pvalue;
348  GList *keys, *values;
349  gint keys_len, values_len;
350
351  hash_table = g_hash_table_new (my_hash, my_hash_equal);
352  for (i = 0; i < 10000; i++)
353    {
354      array[i] = i;
355      g_hash_table_insert (hash_table, &array[i], &array[i]);
356    }
357  pvalue = g_hash_table_find (hash_table, find_first, &value);
358  if (!pvalue || *pvalue != value)
359    g_assert_not_reached();
360
361  keys = g_hash_table_get_keys (hash_table);
362  if (!keys)
363    g_assert_not_reached ();
364
365  values = g_hash_table_get_values (hash_table);
366  if (!values)
367    g_assert_not_reached ();
368
369  keys_len = g_list_length (keys);
370  values_len = g_list_length (values);
371  if (values_len != keys_len &&  keys_len != g_hash_table_size (hash_table))
372    g_assert_not_reached ();
373
374  g_list_free (keys);
375  g_list_free (values);
376
377  g_hash_table_foreach (hash_table, my_hash_callback, NULL);
378
379  for (i = 0; i < 10000; i++)
380    if (array[i] == 0)
381      g_assert_not_reached();
382
383  for (i = 0; i < 10000; i++)
384    g_hash_table_remove (hash_table, &array[i]);
385
386  for (i = 0; i < 10000; i++)
387    {
388      array[i] = i;
389      g_hash_table_insert (hash_table, &array[i], &array[i]);
390    }
391
392  if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||
393      g_hash_table_size (hash_table) != 5000)
394    g_assert_not_reached();
395
396  g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
397
398
399  g_hash_table_destroy (hash_table);
400
401  second_hash_test (TRUE);
402  second_hash_test (FALSE);
403  direct_hash_test ();
404
405  return 0;
406
407}
408