1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
21 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
22 * file for a list of people on the GLib Team. See the ChangeLog
23 * files for a list of changes. These files are distributed with
24 * GLib at ftp://ftp.gtk.org/pub/gtk/.
32 * Imported in mono cvs from version 1.32 of gnome cvs.
40 #include "mono-hash.h"
41 #include "metadata/gc-internal.h"
43 #define HASH_TABLE_MIN_SIZE 11
44 #define HASH_TABLE_MAX_SIZE 13845163
46 typedef struct _MonoGHashNode MonoGHashNode;
55 struct _MonoGHashTable
59 MonoGHashNode **nodes;
61 GEqualFunc key_equal_func;
62 GDestroyNotify key_destroy_func;
63 GDestroyNotify value_destroy_func;
64 MonoGHashGCType gc_type;
67 #define G_HASH_TABLE_RESIZE(hash_table) \
69 if ((hash_table->size >= 3 * hash_table->nnodes && \
70 hash_table->size > HASH_TABLE_MIN_SIZE) || \
71 (3 * hash_table->size <= hash_table->nnodes && \
72 hash_table->size < HASH_TABLE_MAX_SIZE)) \
73 g_hash_table_resize (hash_table); \
76 static void g_hash_table_resize (MonoGHashTable *hash_table);
77 static MonoGHashNode** g_hash_table_lookup_node (MonoGHashTable *hash_table,
79 static MonoGHashNode* g_hash_node_new (gpointer key,
82 static void g_hash_node_destroy (MonoGHashNode *hash_node,
84 GDestroyNotify key_destroy_func,
85 GDestroyNotify value_destroy_func);
86 static void g_hash_nodes_destroy (MonoGHashNode *hash_node,
88 GDestroyNotify key_destroy_func,
89 GDestroyNotify value_destroy_func);
90 static guint g_hash_table_foreach_remove_or_steal (MonoGHashTable *hash_table,
96 G_LOCK_DEFINE_STATIC (g_hash_global);
98 #if defined(HAVE_NULL_GC)
99 static GMemChunk *node_mem_chunk = NULL;
101 #if defined(HAVE_SGEN_GC)
102 static void *node_gc_descs [4] = {NULL};
103 static MonoGHashNode *node_free_lists [4] = {NULL};
105 static MonoGHashNode *node_free_list = NULL;
110 * @hash_func: a function to create a hash value from a key.
111 * Hash values are used to determine where keys are stored within the
112 * #GHashTable data structure. The g_direct_hash(), g_int_hash() and
113 * g_str_hash() functions are provided for some common types of keys.
114 * If hash_func is %NULL, g_direct_hash() is used.
115 * @key_equal_func: a function to check two keys for equality. This is
116 * used when looking up keys in the #GHashTable. The g_direct_equal(),
117 * g_int_equal() and g_str_equal() functions are provided for the most
118 * common types of keys. If @key_equal_func is %NULL, keys are compared
119 * directly in a similar fashion to g_direct_equal(), but without the
120 * overhead of a function call.
122 * Creates a new #GHashTable.
124 * Return value: a new #GHashTable.
127 mono_g_hash_table_new (GHashFunc hash_func,
128 GEqualFunc key_equal_func)
130 return mono_g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
134 mono_g_hash_table_new_type (GHashFunc hash_func,
135 GEqualFunc key_equal_func,
136 MonoGHashGCType type)
138 MonoGHashTable *table = mono_g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
139 table->gc_type = type;
140 #if defined(HAVE_SGEN_GC)
141 if (type < 0 || type > MONO_HASH_KEY_VALUE_GC)
142 g_error ("wrong type for gc hashtable");
143 if (!node_gc_descs [type] && type > MONO_HASH_CONSERVATIVE_GC) {
145 if (type & MONO_HASH_KEY_GC)
146 bmap |= 1; /* the first field in the node is the key */
147 if (type & MONO_HASH_VALUE_GC)
148 bmap |= 2; /* the second is the value */
149 node_gc_descs [type] = mono_gc_make_descr_from_bitmap (&bmap, 2);
158 * g_hash_table_new_full:
159 * @hash_func: a function to create a hash value from a key.
160 * @key_equal_func: a function to check two keys for equality.
161 * @key_destroy_func: a function to free the memory allocated for the key
162 * used when removing the entry from the #GHashTable or %NULL if you
163 * don't want to supply such a function.
164 * @value_destroy_func: a function to free the memory allocated for the
165 * value used when removing the entry from the #GHashTable or %NULL if
166 * you don't want to supply such a function.
168 * Creates a new #GHashTable like g_hash_table_new() and allows to specify
169 * functions to free the memory allocated for the key and value that get
170 * called when removing the entry from the #GHashTable.
172 * Return value: a new #GHashTable.
175 mono_g_hash_table_new_full (GHashFunc hash_func,
176 GEqualFunc key_equal_func,
177 GDestroyNotify key_destroy_func,
178 GDestroyNotify value_destroy_func)
180 MonoGHashTable *hash_table;
182 static gboolean inited = FALSE;
184 MONO_GC_REGISTER_ROOT (node_free_list);
188 hash_table = GC_MALLOC (sizeof (MonoGHashTable));
190 hash_table = g_new (MonoGHashTable, 1);
192 hash_table->size = HASH_TABLE_MIN_SIZE;
193 hash_table->nnodes = 0;
194 hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
195 hash_table->key_equal_func = key_equal_func == g_direct_equal ? NULL : key_equal_func;
196 hash_table->key_destroy_func = key_destroy_func;
197 hash_table->value_destroy_func = value_destroy_func;
199 hash_table->nodes = GC_MALLOC (sizeof (MonoGHashNode*) * hash_table->size);
201 hash_table->nodes = g_new0 (MonoGHashNode*, hash_table->size);
203 hash_table->gc_type = 0;
209 * g_hash_table_destroy:
210 * @hash_table: a #GHashTable.
212 * Destroys the #GHashTable. If keys and/or values are dynamically
213 * allocated, you should either free them first or create the #GHashTable
214 * using g_hash_table_new_full(). In the latter case the destroy functions
215 * you supplied will be called on all keys and values before destroying
219 mono_g_hash_table_destroy (MonoGHashTable *hash_table)
223 g_return_if_fail (hash_table != NULL);
225 for (i = 0; i < hash_table->size; i++)
226 g_hash_nodes_destroy (hash_table->nodes[i], hash_table->gc_type,
227 hash_table->key_destroy_func,
228 hash_table->value_destroy_func);
232 g_free (hash_table->nodes);
237 static inline MonoGHashNode**
238 g_hash_table_lookup_node (MonoGHashTable *hash_table,
241 MonoGHashNode **node;
243 node = &hash_table->nodes
244 [(* hash_table->hash_func) (key) % hash_table->size];
246 /* Hash table lookup needs to be fast.
247 * We therefore remove the extra conditional of testing
248 * whether to call the key_equal_func or not from
251 if (hash_table->key_equal_func)
252 while (*node && !(*hash_table->key_equal_func) ((*node)->key, key))
253 node = &(*node)->next;
255 while (*node && (*node)->key != key)
256 node = &(*node)->next;
262 * g_hash_table_lookup:
263 * @hash_table: a #GHashTable.
264 * @key: the key to look up.
266 * Looks up a key in a #GHashTable.
268 * Return value: the associated value, or %NULL if the key is not found.
271 mono_g_hash_table_lookup (MonoGHashTable *hash_table,
276 g_return_val_if_fail (hash_table != NULL, NULL);
278 node = *g_hash_table_lookup_node (hash_table, key);
280 return node ? node->value : NULL;
284 * g_hash_table_lookup_extended:
285 * @hash_table: a #GHashTable.
286 * @lookup_key: the key to look up.
287 * @orig_key: returns the original key.
288 * @value: returns the value associated with the key.
290 * Looks up a key in the #GHashTable, returning the original key and the
291 * associated value and a #gboolean which is %TRUE if the key was found. This
292 * is useful if you need to free the memory allocated for the original key,
293 * for example before calling g_hash_table_remove().
295 * Return value: %TRUE if the key was found in the #GHashTable.
298 mono_g_hash_table_lookup_extended (MonoGHashTable *hash_table,
299 gconstpointer lookup_key,
305 g_return_val_if_fail (hash_table != NULL, FALSE);
307 node = *g_hash_table_lookup_node (hash_table, lookup_key);
312 *orig_key = node->key;
314 *value = node->value;
321 static inline MonoGHashNode*
322 g_hash_node_new (gpointer key,
326 MonoGHashNode *hash_node = NULL;
329 if (node_free_list) {
330 G_LOCK (g_hash_global);
332 if (node_free_list) {
333 hash_node = node_free_list;
334 node_free_list = node_free_list->next;
336 G_UNLOCK (g_hash_global);
339 hash_node = GC_MALLOC (sizeof (MonoGHashNode));
340 #elif defined(HAVE_SGEN_GC)
341 if (node_free_lists [gc_type]) {
342 G_LOCK (g_hash_global);
344 if (node_free_lists [gc_type]) {
345 hash_node = node_free_lists [gc_type];
346 node_free_lists [gc_type] = node_free_lists [gc_type]->next;
348 G_UNLOCK (g_hash_global);
351 hash_node = mono_gc_alloc_fixed (sizeof (MonoGHashNode), node_gc_descs [gc_type]);
353 G_LOCK (g_hash_global);
356 hash_node = node_free_list;
357 node_free_list = node_free_list->next;
362 node_mem_chunk = g_mem_chunk_new ("hash node mem chunk",
363 sizeof (MonoGHashNode),
366 hash_node = g_chunk_new (MonoGHashNode, node_mem_chunk);
368 G_UNLOCK (g_hash_global);
371 hash_node->key = key;
372 hash_node->value = value;
373 hash_node->next = NULL;
379 * g_hash_table_insert:
380 * @hash_table: a #GHashTable.
381 * @key: a key to insert.
382 * @value: the value to associate with the key.
384 * Inserts a new key and value into a #GHashTable.
386 * If the key already exists in the #GHashTable its current value is replaced
387 * with the new value. If you supplied a @value_destroy_func when creating the
388 * #GHashTable, the old value is freed using that function. If you supplied
389 * a @key_destroy_func when creating the #GHashTable, the passed key is freed
390 * using that function.
393 mono_g_hash_table_insert (MonoGHashTable *hash_table,
397 MonoGHashNode **node;
399 g_return_if_fail (hash_table != NULL);
401 node = g_hash_table_lookup_node (hash_table, key);
405 /* do not reset node->key in this place, keeping
406 * the old key is the intended behaviour.
407 * g_hash_table_replace() can be used instead.
410 /* free the passed key */
411 if (hash_table->key_destroy_func)
412 hash_table->key_destroy_func (key);
414 if (hash_table->value_destroy_func)
415 hash_table->value_destroy_func ((*node)->value);
417 (*node)->value = value;
421 *node = g_hash_node_new (key, value, hash_table->gc_type);
422 hash_table->nnodes++;
423 G_HASH_TABLE_RESIZE (hash_table);
428 * g_hash_table_replace:
429 * @hash_table: a #GHashTable.
430 * @key: a key to insert.
431 * @value: the value to associate with the key.
433 * Inserts a new key and value into a #GHashTable similar to
434 * g_hash_table_insert(). The difference is that if the key already exists
435 * in the #GHashTable, it gets replaced by the new key. If you supplied a
436 * @value_destroy_func when creating the #GHashTable, the old value is freed
437 * using that function. If you supplied a @key_destroy_func when creating the
438 * #GHashTable, the old key is freed using that function.
441 mono_g_hash_table_replace (MonoGHashTable *hash_table,
445 MonoGHashNode **node;
447 g_return_if_fail (hash_table != NULL);
449 node = g_hash_table_lookup_node (hash_table, key);
453 if (hash_table->key_destroy_func)
454 hash_table->key_destroy_func ((*node)->key);
456 if (hash_table->value_destroy_func)
457 hash_table->value_destroy_func ((*node)->value);
460 (*node)->value = value;
464 *node = g_hash_node_new (key, value, hash_table->gc_type);
465 hash_table->nnodes++;
466 G_HASH_TABLE_RESIZE (hash_table);
471 * g_hash_table_remove:
472 * @hash_table: a #GHashTable.
473 * @key: the key to remove.
475 * Removes a key and its associated value from a #GHashTable.
477 * If the #GHashTable was created using g_hash_table_new_full(), the
478 * key and value are freed using the supplied destroy functions, otherwise
479 * you have to make sure that any dynamically allocated values are freed
482 * Return value: %TRUE if the key was found and removed from the #GHashTable.
485 mono_g_hash_table_remove (MonoGHashTable *hash_table,
488 MonoGHashNode **node, *dest;
490 g_return_val_if_fail (hash_table != NULL, FALSE);
492 node = g_hash_table_lookup_node (hash_table, key);
496 (*node) = dest->next;
497 g_hash_node_destroy (dest, hash_table->gc_type,
498 hash_table->key_destroy_func,
499 hash_table->value_destroy_func);
500 hash_table->nnodes--;
502 G_HASH_TABLE_RESIZE (hash_table);
511 * g_hash_table_steal:
512 * @hash_table: a #GHashTable.
513 * @key: the key to remove.
515 * Removes a key and its associated value from a #GHashTable without
516 * calling the key and value destroy functions.
518 * Return value: %TRUE if the key was found and removed from the #GHashTable.
521 mono_g_hash_table_steal (MonoGHashTable *hash_table,
524 MonoGHashNode **node, *dest;
526 g_return_val_if_fail (hash_table != NULL, FALSE);
528 node = g_hash_table_lookup_node (hash_table, key);
532 (*node) = dest->next;
533 g_hash_node_destroy (dest, hash_table->gc_type, NULL, NULL);
534 hash_table->nnodes--;
536 G_HASH_TABLE_RESIZE (hash_table);
545 * g_hash_table_foreach_remove:
546 * @hash_table: a #GHashTable.
547 * @func: the function to call for each key/value pair.
548 * @user_data: user data to pass to the function.
550 * Calls the given function for each key/value pair in the #GHashTable.
551 * If the function returns %TRUE, then the key/value pair is removed from the
552 * #GHashTable. If you supplied key or value destroy functions when creating
553 * the #GHashTable, they are used to free the memory allocated for the removed
556 * Return value: the number of key/value pairs removed.
559 mono_g_hash_table_foreach_remove (MonoGHashTable *hash_table,
563 g_return_val_if_fail (hash_table != NULL, 0);
564 g_return_val_if_fail (func != NULL, 0);
566 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
570 * g_hash_table_foreach_steal:
571 * @hash_table: a #GHashTable.
572 * @func: the function to call for each key/value pair.
573 * @user_data: user data to pass to the function.
575 * Calls the given function for each key/value pair in the #GHashTable.
576 * If the function returns %TRUE, then the key/value pair is removed from the
577 * #GHashTable, but no key or value destroy functions are called.
579 * Return value: the number of key/value pairs removed.
582 mono_g_hash_table_foreach_steal (MonoGHashTable *hash_table,
586 g_return_val_if_fail (hash_table != NULL, 0);
587 g_return_val_if_fail (func != NULL, 0);
589 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
593 g_hash_table_foreach_remove_or_steal (MonoGHashTable *hash_table,
598 MonoGHashNode *node, *prev;
602 for (i = 0; i < hash_table->size; i++)
608 for (node = hash_table->nodes[i]; node; prev = node, node = node->next)
610 if ((* func) (node->key, node->value, user_data))
614 hash_table->nnodes -= 1;
618 prev->next = node->next;
619 g_hash_node_destroy (node, hash_table->gc_type,
620 notify ? hash_table->key_destroy_func : NULL,
621 notify ? hash_table->value_destroy_func : NULL);
626 hash_table->nodes[i] = node->next;
627 g_hash_node_destroy (node, hash_table->gc_type,
628 notify ? hash_table->key_destroy_func : NULL,
629 notify ? hash_table->value_destroy_func : NULL);
636 G_HASH_TABLE_RESIZE (hash_table);
642 * g_hash_table_foreach:
643 * @hash_table: a #GHashTable.
644 * @func: the function to call for each key/value pair.
645 * @user_data: user data to pass to the function.
647 * Calls the given function for each of the key/value pairs in the
648 * #GHashTable. The function is passed the key and value of each
649 * pair, and the given @user_data parameter. The hash table may not
650 * be modified while iterating over it (you can't add/remove
651 * items). To remove all items matching a predicate, use
652 * g_hash_table_remove().
655 mono_g_hash_table_foreach (MonoGHashTable *hash_table,
662 g_return_if_fail (hash_table != NULL);
663 g_return_if_fail (func != NULL);
665 for (i = 0; i < hash_table->size; i++)
666 for (node = hash_table->nodes[i]; node; node = node->next)
667 (* func) (node->key, node->value, user_data);
672 * @hash_table: a #GHashTable.
674 * Returns the number of elements contained in the #GHashTable.
676 * Return value: the number of key/value pairs in the #GHashTable.
679 mono_g_hash_table_size (MonoGHashTable *hash_table)
681 g_return_val_if_fail (hash_table != NULL, 0);
683 return hash_table->nnodes;
687 * mono_g_hash_table_remap:
689 * Calls the given function for each key-value pair in the hash table,
690 * and replaces the value stored in the hash table by the value returned by
695 mono_g_hash_table_remap (MonoGHashTable *hash_table,
696 MonoGRemapperFunc func,
702 g_return_if_fail (hash_table != NULL);
703 g_return_if_fail (func != NULL);
705 for (i = 0; i < hash_table->size; i++)
706 for (node = hash_table->nodes[i]; node; node = node->next)
707 node->value = (* func) (node->key, node->value, user_data);
711 g_hash_table_resize (MonoGHashTable *hash_table)
713 MonoGHashNode **new_nodes;
720 new_size = g_spaced_primes_closest (hash_table->nnodes);
721 new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
724 new_nodes = GC_MALLOC (sizeof (MonoGHashNode*) * new_size);
726 new_nodes = g_new0 (MonoGHashNode*, new_size);
729 for (i = 0; i < hash_table->size; i++)
730 for (node = hash_table->nodes[i]; node; node = next)
734 hash_val = (* hash_table->hash_func) (node->key) % new_size;
736 node->next = new_nodes[hash_val];
737 new_nodes[hash_val] = node;
742 g_free (hash_table->nodes);
744 hash_table->nodes = new_nodes;
745 hash_table->size = new_size;
749 g_hash_node_destroy (MonoGHashNode *hash_node,
750 MonoGHashGCType type,
751 GDestroyNotify key_destroy_func,
752 GDestroyNotify value_destroy_func)
754 if (key_destroy_func)
755 key_destroy_func (hash_node->key);
756 if (value_destroy_func)
757 value_destroy_func (hash_node->value);
759 hash_node->key = NULL;
760 hash_node->value = NULL;
762 G_LOCK (g_hash_global);
763 #if defined(HAVE_SGEN_GC)
764 hash_node->next = node_free_lists [type];
765 node_free_lists [type] = hash_node;
767 hash_node->next = node_free_list;
768 node_free_list = hash_node;
770 G_UNLOCK (g_hash_global);
774 g_hash_nodes_destroy (MonoGHashNode *hash_node,
775 MonoGHashGCType type,
776 GFreeFunc key_destroy_func,
777 GFreeFunc value_destroy_func)
781 MonoGHashNode *node = hash_node;
785 if (key_destroy_func)
786 key_destroy_func (node->key);
787 if (value_destroy_func)
788 value_destroy_func (node->value);
796 if (key_destroy_func)
797 key_destroy_func (node->key);
798 if (value_destroy_func)
799 value_destroy_func (node->value);
804 G_LOCK (g_hash_global);
805 #if defined(HAVE_SGEN_GC)
806 node->next = node_free_lists [type];
807 node_free_lists [type] = hash_node;
809 node->next = node_free_list;
810 node_free_list = hash_node;
812 G_UNLOCK (g_hash_global);