2 * ghashtable.c: Hashtable implementation
5 * Miguel de Icaza (miguel@novell.com)
7 * (C) 2006 Novell, Inc.
9 * Permission is hereby granted, free of charge, to any person obtaining
10 * a copy of this software and associated documentation files (the
11 * "Software"), to deal in the Software without restriction, including
12 * without limitation the rights to use, copy, modify, merge, publish,
13 * distribute, sublicense, and/or sell copies of the Software, and to
14 * permit persons to whom the Software is furnished to do so, subject to
15 * the following conditions:
17 * The above copyright notice and this permission notice shall be
18 * included in all copies or substantial portions of the Software.
20 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
21 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
22 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
23 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
24 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
25 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
26 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
32 typedef struct _Slot Slot;
40 static gpointer KEYMARKER_REMOVED = &KEYMARKER_REMOVED;
44 GEqualFunc key_equal_func;
51 GDestroyNotify value_destroy_func, key_destroy_func;
60 static const guint prime_tbl[] = {
61 11, 19, 37, 73, 109, 163, 251, 367, 557, 823, 1237,
62 1861, 2777, 4177, 6247, 9371, 14057, 21089, 31627,
63 47431, 71143, 106721, 160073, 240101, 360163,
64 540217, 810343, 1215497, 1823231, 2734867, 4102283,
65 6153409, 9230113, 13845163
73 for (n = 3; n< (int)sqrt (x); n += 2) {
79 // There is only one even prime - 2.
88 for (i = (x & (~1))-1; i< G_MAXINT32; i += 2) {
96 g_spaced_primes_closest (guint x)
100 for (i = 0; i < G_N_ELEMENTS (prime_tbl); i++) {
101 if (x <= prime_tbl [i])
102 return prime_tbl [i];
104 return calc_prime (x);
108 g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func)
112 if (hash_func == NULL)
113 hash_func = g_direct_hash;
114 if (key_equal_func == NULL)
115 key_equal_func = g_direct_equal;
116 hash = g_new0 (GHashTable, 1);
118 hash->hash_func = hash_func;
119 hash->key_equal_func = key_equal_func;
121 hash->table_size = g_spaced_primes_closest (1);
122 hash->table = g_new0 (Slot *, hash->table_size);
123 hash->last_rehash = hash->table_size;
129 g_hash_table_new_full (GHashFunc hash_func, GEqualFunc key_equal_func,
130 GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func)
132 GHashTable *hash = g_hash_table_new (hash_func, key_equal_func);
136 hash->key_destroy_func = key_destroy_func;
137 hash->value_destroy_func = value_destroy_func;
144 dump_hash_table (GHashTable *hash)
148 for (i = 0; i < hash->table_size; i++) {
151 for (s = hash->table [i]; s != NULL; s = s->next){
152 guint hashcode = (*hash->hash_func) (s->key);
153 guint slot = (hashcode) % hash->table_size;
154 printf ("key %p hash %x on slot %d correct slot %d tb size %d\n", s->key, hashcode, i, slot, hash->table_size);
162 sanity_check (GHashTable *hash)
166 for (i = 0; i < hash->table_size; i++) {
169 for (s = hash->table [i]; s != NULL; s = s->next){
170 guint hashcode = (*hash->hash_func) (s->key);
171 guint slot = (hashcode) % hash->table_size;
173 dump_hashcode_func = 1;
174 hashcode = (*hash->hash_func) (s->key);
175 dump_hashcode_func = 0;
176 g_error ("Key %p (bucket %d) on invalid bucket %d (hashcode %x) (tb size %d)", s->key, slot, i, hashcode, hash->table_size);
183 #define sanity_check(HASH) do {}while(0)
188 do_rehash (GHashTable *hash)
193 /* printf ("Resizing diff=%d slots=%d\n", hash->in_use - hash->last_rehash, hash->table_size); */
194 hash->last_rehash = hash->table_size;
195 current_size = hash->table_size;
196 hash->table_size = g_spaced_primes_closest (hash->in_use);
197 /* printf ("New size: %d\n", hash->table_size); */
199 hash->table = g_new0 (Slot *, hash->table_size);
201 for (i = 0; i < current_size; i++){
204 for (s = table [i]; s != NULL; s = next){
205 guint hashcode = ((*hash->hash_func) (s->key)) % hash->table_size;
208 s->next = hash->table [hashcode];
209 hash->table [hashcode] = s;
216 rehash (GHashTable *hash)
218 int diff = ABS (hash->last_rehash - hash->in_use);
220 /* These are the factors to play with to change the rehashing strategy */
221 /* I played with them with a large range, and could not really get */
222 /* something that was too good, maybe the tests are not that great */
223 if (!(diff * 0.75 > hash->table_size * 2))
230 g_hash_table_insert_replace (GHashTable *hash, gpointer key, gpointer value, gboolean replace)
236 g_return_if_fail (hash != NULL);
239 equal = hash->key_equal_func;
240 if (hash->in_use >= hash->threshold)
243 hashcode = ((*hash->hash_func) (key)) % hash->table_size;
244 for (s = hash->table [hashcode]; s != NULL; s = s->next){
245 if ((*equal) (s->key, key)){
247 if (hash->key_destroy_func != NULL)
248 (*hash->key_destroy_func)(s->key);
251 if (hash->value_destroy_func != NULL)
252 (*hash->value_destroy_func) (s->value);
261 s->next = hash->table [hashcode];
262 hash->table [hashcode] = s;
268 g_hash_table_get_keys (GHashTable *hash)
274 g_hash_table_iter_init (&iter, hash);
276 while (g_hash_table_iter_next (&iter, &key, NULL))
277 rv = g_list_prepend (rv, key);
279 return g_list_reverse (rv);
283 g_hash_table_get_values (GHashTable *hash)
289 g_hash_table_iter_init (&iter, hash);
291 while (g_hash_table_iter_next (&iter, NULL, &value))
292 rv = g_list_prepend (rv, value);
294 return g_list_reverse (rv);
299 g_hash_table_size (GHashTable *hash)
301 g_return_val_if_fail (hash != NULL, 0);
307 g_hash_table_lookup (GHashTable *hash, gconstpointer key)
309 gpointer orig_key, value;
311 if (g_hash_table_lookup_extended (hash, key, &orig_key, &value))
318 g_hash_table_lookup_extended (GHashTable *hash, gconstpointer key, gpointer *orig_key, gpointer *value)
324 g_return_val_if_fail (hash != NULL, FALSE);
326 equal = hash->key_equal_func;
328 hashcode = ((*hash->hash_func) (key)) % hash->table_size;
330 for (s = hash->table [hashcode]; s != NULL; s = s->next){
331 if ((*equal)(s->key, key)){
343 g_hash_table_foreach (GHashTable *hash, GHFunc func, gpointer user_data)
347 g_return_if_fail (hash != NULL);
348 g_return_if_fail (func != NULL);
350 for (i = 0; i < hash->table_size; i++){
353 for (s = hash->table [i]; s != NULL; s = s->next)
354 (*func)(s->key, s->value, user_data);
359 g_hash_table_find (GHashTable *hash, GHRFunc predicate, gpointer user_data)
363 g_return_val_if_fail (hash != NULL, NULL);
364 g_return_val_if_fail (predicate != NULL, NULL);
366 for (i = 0; i < hash->table_size; i++){
369 for (s = hash->table [i]; s != NULL; s = s->next)
370 if ((*predicate)(s->key, s->value, user_data))
377 g_hash_table_remove_all (GHashTable *hash)
381 g_return_if_fail (hash != NULL);
383 for (i = 0; i < hash->table_size; i++){
386 while (hash->table [i]) {
388 g_hash_table_remove (hash, s->key);
394 g_hash_table_remove (GHashTable *hash, gconstpointer key)
400 g_return_val_if_fail (hash != NULL, FALSE);
402 equal = hash->key_equal_func;
404 hashcode = ((*hash->hash_func)(key)) % hash->table_size;
406 for (s = hash->table [hashcode]; s != NULL; s = s->next){
407 if ((*equal)(s->key, key)){
408 if (hash->key_destroy_func != NULL)
409 (*hash->key_destroy_func)(s->key);
410 if (hash->value_destroy_func != NULL)
411 (*hash->value_destroy_func)(s->value);
413 hash->table [hashcode] = s->next;
415 last->next = s->next;
428 g_hash_table_foreach_remove (GHashTable *hash, GHRFunc func, gpointer user_data)
433 g_return_val_if_fail (hash != NULL, 0);
434 g_return_val_if_fail (func != NULL, 0);
437 for (i = 0; i < hash->table_size; i++){
441 for (s = hash->table [i]; s != NULL; ){
442 if ((*func)(s->key, s->value, user_data)){
445 if (hash->key_destroy_func != NULL)
446 (*hash->key_destroy_func)(s->key);
447 if (hash->value_destroy_func != NULL)
448 (*hash->value_destroy_func)(s->value);
450 hash->table [i] = s->next;
453 last->next = s->next;
473 g_hash_table_steal (GHashTable *hash, gconstpointer key)
479 g_return_val_if_fail (hash != NULL, FALSE);
481 equal = hash->key_equal_func;
483 hashcode = ((*hash->hash_func)(key)) % hash->table_size;
485 for (s = hash->table [hashcode]; s != NULL; s = s->next){
486 if ((*equal)(s->key, key)) {
488 hash->table [hashcode] = s->next;
490 last->next = s->next;
504 g_hash_table_foreach_steal (GHashTable *hash, GHRFunc func, gpointer user_data)
509 g_return_val_if_fail (hash != NULL, 0);
510 g_return_val_if_fail (func != NULL, 0);
513 for (i = 0; i < hash->table_size; i++){
517 for (s = hash->table [i]; s != NULL; ){
518 if ((*func)(s->key, s->value, user_data)){
522 hash->table [i] = s->next;
525 last->next = s->next;
545 g_hash_table_destroy (GHashTable *hash)
549 g_return_if_fail (hash != NULL);
551 for (i = 0; i < hash->table_size; i++){
554 for (s = hash->table [i]; s != NULL; s = next){
557 if (hash->key_destroy_func != NULL)
558 (*hash->key_destroy_func)(s->key);
559 if (hash->value_destroy_func != NULL)
560 (*hash->value_destroy_func)(s->value);
564 g_free (hash->table);
570 g_hash_table_print_stats (GHashTable *table)
572 int i, max_chain_index, chain_size, max_chain_size;
576 max_chain_index = -1;
577 for (i = 0; i < table->table_size; i++) {
579 for (node = table->table [i]; node; node = node->next)
581 if (chain_size > max_chain_size) {
582 max_chain_size = chain_size;
587 printf ("Size: %d Table Size: %d Max Chain Length: %d at %d\n", table->in_use, table->table_size, max_chain_size, max_chain_index);
591 g_hash_table_iter_init (GHashTableIter *it, GHashTable *hash_table)
593 Iter *iter = (Iter*)it;
595 memset (iter, 0, sizeof (Iter));
596 iter->ht = hash_table;
597 iter->slot_index = -1;
600 gboolean g_hash_table_iter_next (GHashTableIter *it, gpointer *key, gpointer *value)
602 Iter *iter = (Iter*)it;
604 GHashTable *hash = iter->ht;
606 g_assert (iter->slot_index != -2);
607 g_assert (sizeof (Iter) <= sizeof (GHashTableIter));
612 if (iter->slot_index >= hash->table_size) {
613 iter->slot_index = -2;
616 if (hash->table [iter->slot_index])
619 iter->slot = hash->table [iter->slot_index];
623 *key = iter->slot->key;
625 *value = iter->slot->value;
626 iter->slot = iter->slot->next;
632 g_direct_equal (gconstpointer v1, gconstpointer v2)
638 g_direct_hash (gconstpointer v1)
640 return GPOINTER_TO_UINT (v1);
644 g_int_equal (gconstpointer v1, gconstpointer v2)
646 return *(gint *)v1 == *(gint *)v2;
650 g_int_hash (gconstpointer v1)
656 g_str_equal (gconstpointer v1, gconstpointer v2)
658 return strcmp (v1, v2) == 0;
662 g_str_hash (gconstpointer v1)
665 char *p = (char *) v1;
668 hash = (hash << 5) - (hash + *p);