|
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 * Portion Copyright © 2008-09 Nokia Corporation and/or its subsidiary(-ies). All rights reserved. |
|
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 #ifdef __SYMBIAN32__ |
|
45 #include "mrt2_glib2_test.h" |
|
46 #endif /*__SYMBIAN32__*/ |
|
47 |
|
48 int array[10000]; |
|
49 |
|
50 static void |
|
51 fill_hash_table_and_array (GHashTable *hash_table) |
|
52 { |
|
53 int i; |
|
54 |
|
55 for (i = 0; i < 10000; i++) |
|
56 { |
|
57 array[i] = i; |
|
58 g_hash_table_insert (hash_table, &array[i], &array[i]); |
|
59 } |
|
60 } |
|
61 |
|
62 static void |
|
63 init_result_array (int *result_array) |
|
64 { |
|
65 int i; |
|
66 |
|
67 for (i = 0; i < 10000; i++) |
|
68 result_array[i] = -1; |
|
69 } |
|
70 |
|
71 static void |
|
72 verify_result_array (int *array) |
|
73 { |
|
74 int i; |
|
75 |
|
76 for (i = 0; i < 10000; i++) |
|
77 g_assert (array[i] == i); |
|
78 } |
|
79 |
|
80 static void |
|
81 handle_pair (gpointer key, gpointer value, int *result_array) |
|
82 { |
|
83 int n; |
|
84 |
|
85 g_assert (key == value); |
|
86 |
|
87 n = *((int *) value); |
|
88 |
|
89 g_assert (n >= 0 && n < 10000); |
|
90 g_assert (result_array[n] == -1); |
|
91 |
|
92 result_array[n] = n; |
|
93 } |
|
94 |
|
95 static gboolean |
|
96 my_hash_callback_remove (gpointer key, |
|
97 gpointer value, |
|
98 gpointer user_data) |
|
99 { |
|
100 int *d = value; |
|
101 |
|
102 if ((*d) % 2) |
|
103 return TRUE; |
|
104 |
|
105 return FALSE; |
|
106 } |
|
107 |
|
108 static void |
|
109 my_hash_callback_remove_test (gpointer key, |
|
110 gpointer value, |
|
111 gpointer user_data) |
|
112 { |
|
113 int *d = value; |
|
114 |
|
115 if ((*d) % 2) |
|
116 g_assert_not_reached (); |
|
117 } |
|
118 |
|
119 static void |
|
120 my_hash_callback (gpointer key, |
|
121 gpointer value, |
|
122 gpointer user_data) |
|
123 { |
|
124 handle_pair (key, value, user_data); |
|
125 } |
|
126 |
|
127 static guint |
|
128 my_hash (gconstpointer key) |
|
129 { |
|
130 return (guint) *((const gint*) key); |
|
131 } |
|
132 |
|
133 static gboolean |
|
134 my_hash_equal (gconstpointer a, |
|
135 gconstpointer b) |
|
136 { |
|
137 return *((const gint*) a) == *((const gint*) b); |
|
138 } |
|
139 |
|
140 |
|
141 |
|
142 /* |
|
143 * This is a simplified version of the pathalias hashing function. |
|
144 * Thanks to Steve Belovin and Peter Honeyman |
|
145 * |
|
146 * hash a string into a long int. 31 bit crc (from andrew appel). |
|
147 * the crc table is computed at run time by crcinit() -- we could |
|
148 * precompute, but it takes 1 clock tick on a 750. |
|
149 * |
|
150 * This fast table calculation works only if POLY is a prime polynomial |
|
151 * in the field of integers modulo 2. Since the coefficients of a |
|
152 * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is |
|
153 * implicit. IT MUST ALSO BE THE CASE that the coefficients of orders |
|
154 * 31 down to 25 are zero. Happily, we have candidates, from |
|
155 * E. J. Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962): |
|
156 * x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0 |
|
157 * x^31 + x^3 + x^0 |
|
158 * |
|
159 * We reverse the bits to get: |
|
160 * 111101010000000000000000000000001 but drop the last 1 |
|
161 * f 5 0 0 0 0 0 0 |
|
162 * 010010000000000000000000000000001 ditto, for 31-bit crc |
|
163 * 4 8 0 0 0 0 0 0 |
|
164 */ |
|
165 |
|
166 #define POLY 0x48000000L /* 31-bit polynomial (avoids sign problems) */ |
|
167 |
|
168 static guint CrcTable[128]; |
|
169 |
|
170 /* |
|
171 - crcinit - initialize tables for hash function |
|
172 */ |
|
173 static void crcinit(void) |
|
174 { |
|
175 int i, j; |
|
176 guint sum; |
|
177 |
|
178 for (i = 0; i < 128; ++i) { |
|
179 sum = 0L; |
|
180 for (j = 7 - 1; j >= 0; --j) |
|
181 if (i & (1 << j)) |
|
182 sum ^= POLY >> j; |
|
183 CrcTable[i] = sum; |
|
184 } |
|
185 } |
|
186 |
|
187 /* |
|
188 - hash - Honeyman's nice hashing function |
|
189 */ |
|
190 static guint honeyman_hash(gconstpointer key) |
|
191 { |
|
192 const gchar *name = (const gchar *) key; |
|
193 gint size; |
|
194 guint sum = 0; |
|
195 |
|
196 g_assert (name != NULL); |
|
197 g_assert (*name != 0); |
|
198 |
|
199 size = strlen(name); |
|
200 |
|
201 while (size--) { |
|
202 sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f]; |
|
203 } |
|
204 |
|
205 return(sum); |
|
206 } |
|
207 |
|
208 |
|
209 static gboolean second_hash_cmp (gconstpointer a, gconstpointer b) |
|
210 { |
|
211 return (strcmp (a, b) == 0); |
|
212 } |
|
213 |
|
214 |
|
215 |
|
216 static guint one_hash(gconstpointer key) |
|
217 { |
|
218 return 1; |
|
219 } |
|
220 |
|
221 |
|
222 static void not_even_foreach (gpointer key, |
|
223 gpointer value, |
|
224 gpointer user_data) |
|
225 { |
|
226 const char *_key = (const char *) key; |
|
227 const char *_value = (const char *) value; |
|
228 int i; |
|
229 char val [20]; |
|
230 |
|
231 g_assert (_key != NULL); |
|
232 g_assert (*_key != 0); |
|
233 g_assert (_value != NULL); |
|
234 g_assert (*_value != 0); |
|
235 |
|
236 i = atoi (_key); |
|
237 |
|
238 sprintf (val, "%d value", i); |
|
239 g_assert (strcmp (_value, val) == 0); |
|
240 |
|
241 g_assert ((i % 2) != 0); |
|
242 g_assert (i != 3); |
|
243 } |
|
244 |
|
245 |
|
246 static gboolean remove_even_foreach (gpointer key, |
|
247 gpointer value, |
|
248 gpointer user_data) |
|
249 { |
|
250 const char *_key = (const char *) key; |
|
251 const char *_value = (const char *) value; |
|
252 int i; |
|
253 char val [20]; |
|
254 |
|
255 g_assert (_key != NULL); |
|
256 g_assert (*_key != 0); |
|
257 g_assert (_value != NULL); |
|
258 g_assert (*_value != 0); |
|
259 |
|
260 i = atoi (_key); |
|
261 |
|
262 sprintf (val, "%d value", i); |
|
263 g_assert (strcmp (_value, val) == 0); |
|
264 |
|
265 return ((i % 2) == 0) ? TRUE : FALSE; |
|
266 } |
|
267 |
|
268 |
|
269 |
|
270 |
|
271 static void second_hash_test (gboolean simple_hash) |
|
272 { |
|
273 int i; |
|
274 char key[20] = "", val[20]="", *v, *orig_key, *orig_val; |
|
275 GHashTable *h; |
|
276 gboolean found; |
|
277 |
|
278 crcinit (); |
|
279 |
|
280 h = g_hash_table_new_full (simple_hash ? one_hash : honeyman_hash, |
|
281 second_hash_cmp, |
|
282 g_free, g_free); |
|
283 g_assert (h != NULL); |
|
284 for (i=0; i<20; i++) |
|
285 { |
|
286 sprintf (key, "%d", i); |
|
287 g_assert (atoi (key) == i); |
|
288 |
|
289 sprintf (val, "%d value", i); |
|
290 g_assert (atoi (val) == i); |
|
291 |
|
292 g_hash_table_insert (h, g_strdup (key), g_strdup (val)); |
|
293 } |
|
294 |
|
295 g_assert (g_hash_table_size (h) == 20); |
|
296 |
|
297 for (i=0; i<20; i++) |
|
298 { |
|
299 sprintf (key, "%d", i); |
|
300 g_assert (atoi(key) == i); |
|
301 |
|
302 v = (char *) g_hash_table_lookup (h, key); |
|
303 |
|
304 g_assert (v != NULL); |
|
305 g_assert (*v != 0); |
|
306 g_assert (atoi (v) == i); |
|
307 } |
|
308 |
|
309 sprintf (key, "%d", 3); |
|
310 g_hash_table_remove (h, key); |
|
311 g_assert (g_hash_table_size (h) == 19); |
|
312 g_hash_table_foreach_remove (h, remove_even_foreach, NULL); |
|
313 g_assert (g_hash_table_size (h) == 9); |
|
314 g_hash_table_foreach (h, not_even_foreach, NULL); |
|
315 |
|
316 for (i=0; i<20; i++) |
|
317 { |
|
318 sprintf (key, "%d", i); |
|
319 g_assert (atoi(key) == i); |
|
320 |
|
321 sprintf (val, "%d value", i); |
|
322 g_assert (atoi (val) == i); |
|
323 |
|
324 orig_key = orig_val = NULL; |
|
325 found = g_hash_table_lookup_extended (h, key, |
|
326 (gpointer)&orig_key, |
|
327 (gpointer)&orig_val); |
|
328 if ((i % 2) == 0 || i == 3) |
|
329 { |
|
330 g_assert (!found); |
|
331 continue; |
|
332 } |
|
333 |
|
334 g_assert (found); |
|
335 |
|
336 g_assert (orig_key != NULL); |
|
337 g_assert (strcmp (key, orig_key) == 0); |
|
338 |
|
339 g_assert (orig_val != NULL); |
|
340 g_assert (strcmp (val, orig_val) == 0); |
|
341 } |
|
342 |
|
343 g_hash_table_destroy (h); |
|
344 } |
|
345 |
|
346 static gboolean find_first (gpointer key, |
|
347 gpointer value, |
|
348 gpointer user_data) |
|
349 { |
|
350 gint *v = value; |
|
351 gint *test = user_data; |
|
352 return (*v == *test); |
|
353 } |
|
354 |
|
355 |
|
356 static void direct_hash_test (void) |
|
357 { |
|
358 gint i, rc; |
|
359 GHashTable *h; |
|
360 |
|
361 h = g_hash_table_new (NULL, NULL); |
|
362 g_assert (h != NULL); |
|
363 for (i=1; i<=20; i++) |
|
364 { |
|
365 g_hash_table_insert (h, GINT_TO_POINTER (i), |
|
366 GINT_TO_POINTER (i + 42)); |
|
367 } |
|
368 |
|
369 g_assert (g_hash_table_size (h) == 20); |
|
370 |
|
371 for (i=1; i<=20; i++) |
|
372 { |
|
373 rc = GPOINTER_TO_INT ( |
|
374 g_hash_table_lookup (h, GINT_TO_POINTER (i))); |
|
375 |
|
376 g_assert (rc != 0); |
|
377 g_assert ((rc - 42) == i); |
|
378 } |
|
379 |
|
380 g_hash_table_destroy (h); |
|
381 } |
|
382 |
|
383 |
|
384 |
|
385 int |
|
386 main (int argc, |
|
387 char *argv[]) |
|
388 { |
|
389 GHashTable *hash_table; |
|
390 gint i; |
|
391 gint value = 120; |
|
392 gint *pvalue; |
|
393 GList *keys, *values; |
|
394 gint keys_len, values_len; |
|
395 GHashTableIter iter; |
|
396 gpointer ikey, ivalue; |
|
397 int result_array[10000]; |
|
398 |
|
399 #ifdef __SYMBIAN32__ |
|
400 g_log_set_handler (NULL, G_LOG_FLAG_FATAL| G_LOG_FLAG_RECURSION | G_LOG_LEVEL_CRITICAL | G_LOG_LEVEL_WARNING | G_LOG_LEVEL_MESSAGE | G_LOG_LEVEL_INFO | G_LOG_LEVEL_DEBUG, &mrtLogHandler, NULL); |
|
401 g_set_print_handler(mrtPrintHandler); |
|
402 #endif /*__SYMBIAN32__*/ |
|
403 |
|
404 |
|
405 hash_table = g_hash_table_new (my_hash, my_hash_equal); |
|
406 fill_hash_table_and_array (hash_table); |
|
407 pvalue = g_hash_table_find (hash_table, find_first, &value); |
|
408 if (!pvalue || *pvalue != value) |
|
409 g_assert_not_reached(); |
|
410 |
|
411 keys = g_hash_table_get_keys (hash_table); |
|
412 if (!keys) |
|
413 g_assert_not_reached (); |
|
414 |
|
415 values = g_hash_table_get_values (hash_table); |
|
416 if (!values) |
|
417 g_assert_not_reached (); |
|
418 |
|
419 keys_len = g_list_length (keys); |
|
420 values_len = g_list_length (values); |
|
421 if (values_len != keys_len && keys_len != g_hash_table_size (hash_table)) |
|
422 g_assert_not_reached (); |
|
423 |
|
424 g_list_free (keys); |
|
425 g_list_free (values); |
|
426 |
|
427 init_result_array (result_array); |
|
428 g_hash_table_iter_init (&iter, hash_table); |
|
429 for (i = 0; i < 10000; i++) |
|
430 { |
|
431 g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue)); |
|
432 |
|
433 handle_pair (ikey, ivalue, result_array); |
|
434 |
|
435 if (i % 2) |
|
436 g_hash_table_iter_remove (&iter); |
|
437 } |
|
438 g_assert (! g_hash_table_iter_next (&iter, &ikey, &ivalue)); |
|
439 g_assert (g_hash_table_size (hash_table) == 5000); |
|
440 verify_result_array (result_array); |
|
441 |
|
442 fill_hash_table_and_array (hash_table); |
|
443 |
|
444 init_result_array (result_array); |
|
445 g_hash_table_foreach (hash_table, my_hash_callback, result_array); |
|
446 verify_result_array (result_array); |
|
447 |
|
448 for (i = 0; i < 10000; i++) |
|
449 g_hash_table_remove (hash_table, &array[i]); |
|
450 |
|
451 fill_hash_table_and_array (hash_table); |
|
452 |
|
453 if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 || |
|
454 g_hash_table_size (hash_table) != 5000) |
|
455 g_assert_not_reached(); |
|
456 |
|
457 g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL); |
|
458 |
|
459 |
|
460 g_hash_table_destroy (hash_table); |
|
461 |
|
462 second_hash_test (TRUE); |
|
463 second_hash_test (FALSE); |
|
464 direct_hash_test (); |
|
465 |
|
466 #if __SYMBIAN32__ |
|
467 testResultXml("hash-test"); |
|
468 #endif /* EMULATOR */ |
|
469 |
|
470 return 0; |
|
471 |
|
472 } |