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/os/gc_wrapper.h>
41 #include "mono-hash.h"
42 #include "metadata/gc-internal.h"
44 #define HASH_TABLE_MIN_SIZE 11
45 #define HASH_TABLE_MAX_SIZE 13845163
47 typedef struct _MonoGHashNode MonoGHashNode;
56 struct _MonoGHashTable
60 MonoGHashNode **nodes;
62 GEqualFunc key_equal_func;
63 GDestroyNotify key_destroy_func;
64 GDestroyNotify value_destroy_func;
65 MonoGHashGCType gc_type;
68 #define G_HASH_TABLE_RESIZE(hash_table) \
70 if ((hash_table->size >= 3 * hash_table->nnodes && \
71 hash_table->size > HASH_TABLE_MIN_SIZE) || \
72 (3 * hash_table->size <= hash_table->nnodes && \
73 hash_table->size < HASH_TABLE_MAX_SIZE)) \
74 g_hash_table_resize (hash_table); \
77 static void g_hash_table_resize (MonoGHashTable *hash_table);
78 static MonoGHashNode** g_hash_table_lookup_node (MonoGHashTable *hash_table,
80 static MonoGHashNode* g_hash_node_new (gpointer key,
83 static void g_hash_node_destroy (MonoGHashNode *hash_node,
85 GDestroyNotify key_destroy_func,
86 GDestroyNotify value_destroy_func);
87 static void g_hash_nodes_destroy (MonoGHashNode *hash_node,
89 GDestroyNotify key_destroy_func,
90 GDestroyNotify value_destroy_func);
91 static guint g_hash_table_foreach_remove_or_steal (MonoGHashTable *hash_table,
97 G_LOCK_DEFINE_STATIC (g_hash_global);
99 #if defined(HAVE_NULL_GC)
100 static GMemChunk *node_mem_chunk = NULL;
102 #if defined(HAVE_SGEN_GC)
103 static void *node_gc_descs [4] = {NULL};
104 static MonoGHashNode *node_free_lists [4] = {NULL};
106 static MonoGHashNode *node_free_list = NULL;
111 * @hash_func: a function to create a hash value from a key.
112 * Hash values are used to determine where keys are stored within the
113 * #GHashTable data structure. The g_direct_hash(), g_int_hash() and
114 * g_str_hash() functions are provided for some common types of keys.
115 * If hash_func is %NULL, g_direct_hash() is used.
116 * @key_equal_func: a function to check two keys for equality. This is
117 * used when looking up keys in the #GHashTable. The g_direct_equal(),
118 * g_int_equal() and g_str_equal() functions are provided for the most
119 * common types of keys. If @key_equal_func is %NULL, keys are compared
120 * directly in a similar fashion to g_direct_equal(), but without the
121 * overhead of a function call.
123 * Creates a new #GHashTable.
125 * Return value: a new #GHashTable.
128 mono_g_hash_table_new (GHashFunc hash_func,
129 GEqualFunc key_equal_func)
131 return mono_g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
135 mono_g_hash_table_new_type (GHashFunc hash_func,
136 GEqualFunc key_equal_func,
137 MonoGHashGCType type)
139 MonoGHashTable *table = mono_g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
140 table->gc_type = type;
141 #if defined(HAVE_SGEN_GC)
142 if (type < 0 || type > MONO_HASH_KEY_VALUE_GC)
143 g_error ("wrong type for gc hashtable");
144 if (!node_gc_descs [type] && type > MONO_HASH_CONSERVATIVE_GC) {
146 if (type & MONO_HASH_KEY_GC)
147 bmap |= 1; /* the first field in the node is the key */
148 if (type & MONO_HASH_VALUE_GC)
149 bmap |= 2; /* the second is the value */
150 node_gc_descs [type] = mono_gc_make_descr_from_bitmap (&bmap, 2);
159 * g_hash_table_new_full:
160 * @hash_func: a function to create a hash value from a key.
161 * @key_equal_func: a function to check two keys for equality.
162 * @key_destroy_func: a function to free the memory allocated for the key
163 * used when removing the entry from the #GHashTable or %NULL if you
164 * don't want to supply such a function.
165 * @value_destroy_func: a function to free the memory allocated for the
166 * value used when removing the entry from the #GHashTable or %NULL if
167 * you don't want to supply such a function.
169 * Creates a new #GHashTable like g_hash_table_new() and allows to specify
170 * functions to free the memory allocated for the key and value that get
171 * called when removing the entry from the #GHashTable.
173 * Return value: a new #GHashTable.
176 mono_g_hash_table_new_full (GHashFunc hash_func,
177 GEqualFunc key_equal_func,
178 GDestroyNotify key_destroy_func,
179 GDestroyNotify value_destroy_func)
181 MonoGHashTable *hash_table;
183 static gboolean inited = FALSE;
185 MONO_GC_REGISTER_ROOT (node_free_list);
189 hash_table = GC_MALLOC (sizeof (MonoGHashTable));
191 hash_table = g_new (MonoGHashTable, 1);
193 hash_table->size = HASH_TABLE_MIN_SIZE;
194 hash_table->nnodes = 0;
195 hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
196 hash_table->key_equal_func = key_equal_func == g_direct_equal ? NULL : key_equal_func;
197 hash_table->key_destroy_func = key_destroy_func;
198 hash_table->value_destroy_func = value_destroy_func;
200 hash_table->nodes = GC_MALLOC (sizeof (MonoGHashNode*) * hash_table->size);
202 hash_table->nodes = g_new0 (MonoGHashNode*, hash_table->size);
204 hash_table->gc_type = 0;
210 * g_hash_table_destroy:
211 * @hash_table: a #GHashTable.
213 * Destroys the #GHashTable. If keys and/or values are dynamically
214 * allocated, you should either free them first or create the #GHashTable
215 * using g_hash_table_new_full(). In the latter case the destroy functions
216 * you supplied will be called on all keys and values before destroying
220 mono_g_hash_table_destroy (MonoGHashTable *hash_table)
224 g_return_if_fail (hash_table != NULL);
226 for (i = 0; i < hash_table->size; i++)
227 g_hash_nodes_destroy (hash_table->nodes[i], hash_table->gc_type,
228 hash_table->key_destroy_func,
229 hash_table->value_destroy_func);
233 g_free (hash_table->nodes);
238 static inline MonoGHashNode**
239 g_hash_table_lookup_node (MonoGHashTable *hash_table,
242 MonoGHashNode **node;
244 node = &hash_table->nodes
245 [(* hash_table->hash_func) (key) % hash_table->size];
247 /* Hash table lookup needs to be fast.
248 * We therefore remove the extra conditional of testing
249 * whether to call the key_equal_func or not from
252 if (hash_table->key_equal_func)
253 while (*node && !(*hash_table->key_equal_func) ((*node)->key, key))
254 node = &(*node)->next;
256 while (*node && (*node)->key != key)
257 node = &(*node)->next;
263 * g_hash_table_lookup:
264 * @hash_table: a #GHashTable.
265 * @key: the key to look up.
267 * Looks up a key in a #GHashTable.
269 * Return value: the associated value, or %NULL if the key is not found.
272 mono_g_hash_table_lookup (MonoGHashTable *hash_table,
277 g_return_val_if_fail (hash_table != NULL, NULL);
279 node = *g_hash_table_lookup_node (hash_table, key);
281 return node ? node->value : NULL;
285 * g_hash_table_lookup_extended:
286 * @hash_table: a #GHashTable.
287 * @lookup_key: the key to look up.
288 * @orig_key: returns the original key.
289 * @value: returns the value associated with the key.
291 * Looks up a key in the #GHashTable, returning the original key and the
292 * associated value and a #gboolean which is %TRUE if the key was found. This
293 * is useful if you need to free the memory allocated for the original key,
294 * for example before calling g_hash_table_remove().
296 * Return value: %TRUE if the key was found in the #GHashTable.
299 mono_g_hash_table_lookup_extended (MonoGHashTable *hash_table,
300 gconstpointer lookup_key,
306 g_return_val_if_fail (hash_table != NULL, FALSE);
308 node = *g_hash_table_lookup_node (hash_table, lookup_key);
313 *orig_key = node->key;
315 *value = node->value;
322 static inline MonoGHashNode*
323 g_hash_node_new (gpointer key,
327 MonoGHashNode *hash_node = NULL;
330 if (node_free_list) {
331 G_LOCK (g_hash_global);
333 if (node_free_list) {
334 hash_node = node_free_list;
335 node_free_list = node_free_list->next;
337 G_UNLOCK (g_hash_global);
340 hash_node = GC_MALLOC (sizeof (MonoGHashNode));
341 #elif defined(HAVE_SGEN_GC)
342 if (node_free_lists [gc_type]) {
343 G_LOCK (g_hash_global);
345 if (node_free_lists [gc_type]) {
346 hash_node = node_free_lists [gc_type];
347 node_free_lists [gc_type] = node_free_lists [gc_type]->next;
349 G_UNLOCK (g_hash_global);
352 hash_node = mono_gc_alloc_fixed (sizeof (MonoGHashNode), node_gc_descs [gc_type]);
354 G_LOCK (g_hash_global);
357 hash_node = node_free_list;
358 node_free_list = node_free_list->next;
363 node_mem_chunk = g_mem_chunk_new ("hash node mem chunk",
364 sizeof (MonoGHashNode),
367 hash_node = g_chunk_new (MonoGHashNode, node_mem_chunk);
369 G_UNLOCK (g_hash_global);
372 hash_node->key = key;
373 hash_node->value = value;
374 hash_node->next = NULL;
380 * g_hash_table_insert:
381 * @hash_table: a #GHashTable.
382 * @key: a key to insert.
383 * @value: the value to associate with the key.
385 * Inserts a new key and value into a #GHashTable.
387 * If the key already exists in the #GHashTable its current value is replaced
388 * with the new value. If you supplied a @value_destroy_func when creating the
389 * #GHashTable, the old value is freed using that function. If you supplied
390 * a @key_destroy_func when creating the #GHashTable, the passed key is freed
391 * using that function.
394 mono_g_hash_table_insert (MonoGHashTable *hash_table,
398 MonoGHashNode **node;
400 g_return_if_fail (hash_table != NULL);
402 node = g_hash_table_lookup_node (hash_table, key);
406 /* do not reset node->key in this place, keeping
407 * the old key is the intended behaviour.
408 * g_hash_table_replace() can be used instead.
411 /* free the passed key */
412 if (hash_table->key_destroy_func)
413 hash_table->key_destroy_func (key);
415 if (hash_table->value_destroy_func)
416 hash_table->value_destroy_func ((*node)->value);
418 (*node)->value = value;
422 *node = g_hash_node_new (key, value, hash_table->gc_type);
423 hash_table->nnodes++;
424 G_HASH_TABLE_RESIZE (hash_table);
429 * g_hash_table_replace:
430 * @hash_table: a #GHashTable.
431 * @key: a key to insert.
432 * @value: the value to associate with the key.
434 * Inserts a new key and value into a #GHashTable similar to
435 * g_hash_table_insert(). The difference is that if the key already exists
436 * in the #GHashTable, it gets replaced by the new key. If you supplied a
437 * @value_destroy_func when creating the #GHashTable, the old value is freed
438 * using that function. If you supplied a @key_destroy_func when creating the
439 * #GHashTable, the old key is freed using that function.
442 mono_g_hash_table_replace (MonoGHashTable *hash_table,
446 MonoGHashNode **node;
448 g_return_if_fail (hash_table != NULL);
450 node = g_hash_table_lookup_node (hash_table, key);
454 if (hash_table->key_destroy_func)
455 hash_table->key_destroy_func ((*node)->key);
457 if (hash_table->value_destroy_func)
458 hash_table->value_destroy_func ((*node)->value);
461 (*node)->value = value;
465 *node = g_hash_node_new (key, value, hash_table->gc_type);
466 hash_table->nnodes++;
467 G_HASH_TABLE_RESIZE (hash_table);
472 * g_hash_table_remove:
473 * @hash_table: a #GHashTable.
474 * @key: the key to remove.
476 * Removes a key and its associated value from a #GHashTable.
478 * If the #GHashTable was created using g_hash_table_new_full(), the
479 * key and value are freed using the supplied destroy functions, otherwise
480 * you have to make sure that any dynamically allocated values are freed
483 * Return value: %TRUE if the key was found and removed from the #GHashTable.
486 mono_g_hash_table_remove (MonoGHashTable *hash_table,
489 MonoGHashNode **node, *dest;
491 g_return_val_if_fail (hash_table != NULL, FALSE);
493 node = g_hash_table_lookup_node (hash_table, key);
497 (*node) = dest->next;
498 g_hash_node_destroy (dest, hash_table->gc_type,
499 hash_table->key_destroy_func,
500 hash_table->value_destroy_func);
501 hash_table->nnodes--;
503 G_HASH_TABLE_RESIZE (hash_table);
512 * g_hash_table_steal:
513 * @hash_table: a #GHashTable.
514 * @key: the key to remove.
516 * Removes a key and its associated value from a #GHashTable without
517 * calling the key and value destroy functions.
519 * Return value: %TRUE if the key was found and removed from the #GHashTable.
522 mono_g_hash_table_steal (MonoGHashTable *hash_table,
525 MonoGHashNode **node, *dest;
527 g_return_val_if_fail (hash_table != NULL, FALSE);
529 node = g_hash_table_lookup_node (hash_table, key);
533 (*node) = dest->next;
534 g_hash_node_destroy (dest, hash_table->gc_type, NULL, NULL);
535 hash_table->nnodes--;
537 G_HASH_TABLE_RESIZE (hash_table);
546 * g_hash_table_foreach_remove:
547 * @hash_table: a #GHashTable.
548 * @func: the function to call for each key/value pair.
549 * @user_data: user data to pass to the function.
551 * Calls the given function for each key/value pair in the #GHashTable.
552 * If the function returns %TRUE, then the key/value pair is removed from the
553 * #GHashTable. If you supplied key or value destroy functions when creating
554 * the #GHashTable, they are used to free the memory allocated for the removed
557 * Return value: the number of key/value pairs removed.
560 mono_g_hash_table_foreach_remove (MonoGHashTable *hash_table,
564 g_return_val_if_fail (hash_table != NULL, 0);
565 g_return_val_if_fail (func != NULL, 0);
567 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
571 * g_hash_table_foreach_steal:
572 * @hash_table: a #GHashTable.
573 * @func: the function to call for each key/value pair.
574 * @user_data: user data to pass to the function.
576 * Calls the given function for each key/value pair in the #GHashTable.
577 * If the function returns %TRUE, then the key/value pair is removed from the
578 * #GHashTable, but no key or value destroy functions are called.
580 * Return value: the number of key/value pairs removed.
583 mono_g_hash_table_foreach_steal (MonoGHashTable *hash_table,
587 g_return_val_if_fail (hash_table != NULL, 0);
588 g_return_val_if_fail (func != NULL, 0);
590 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
594 g_hash_table_foreach_remove_or_steal (MonoGHashTable *hash_table,
599 MonoGHashNode *node, *prev;
603 for (i = 0; i < hash_table->size; i++)
609 for (node = hash_table->nodes[i]; node; prev = node, node = node->next)
611 if ((* func) (node->key, node->value, user_data))
615 hash_table->nnodes -= 1;
619 prev->next = node->next;
620 g_hash_node_destroy (node, hash_table->gc_type,
621 notify ? hash_table->key_destroy_func : NULL,
622 notify ? hash_table->value_destroy_func : NULL);
627 hash_table->nodes[i] = node->next;
628 g_hash_node_destroy (node, hash_table->gc_type,
629 notify ? hash_table->key_destroy_func : NULL,
630 notify ? hash_table->value_destroy_func : NULL);
637 G_HASH_TABLE_RESIZE (hash_table);
643 * g_hash_table_foreach:
644 * @hash_table: a #GHashTable.
645 * @func: the function to call for each key/value pair.
646 * @user_data: user data to pass to the function.
648 * Calls the given function for each of the key/value pairs in the
649 * #GHashTable. The function is passed the key and value of each
650 * pair, and the given @user_data parameter. The hash table may not
651 * be modified while iterating over it (you can't add/remove
652 * items). To remove all items matching a predicate, use
653 * g_hash_table_remove().
656 mono_g_hash_table_foreach (MonoGHashTable *hash_table,
663 g_return_if_fail (hash_table != NULL);
664 g_return_if_fail (func != NULL);
666 for (i = 0; i < hash_table->size; i++)
667 for (node = hash_table->nodes[i]; node; node = node->next)
668 (* func) (node->key, node->value, user_data);
673 * @hash_table: a #GHashTable.
675 * Returns the number of elements contained in the #GHashTable.
677 * Return value: the number of key/value pairs in the #GHashTable.
680 mono_g_hash_table_size (MonoGHashTable *hash_table)
682 g_return_val_if_fail (hash_table != NULL, 0);
684 return hash_table->nnodes;
688 * mono_g_hash_table_remap:
690 * Calls the given function for each key-value pair in the hash table,
691 * and replaces the value stored in the hash table by the value returned by
696 mono_g_hash_table_remap (MonoGHashTable *hash_table,
697 MonoGRemapperFunc func,
703 g_return_if_fail (hash_table != NULL);
704 g_return_if_fail (func != NULL);
706 for (i = 0; i < hash_table->size; i++)
707 for (node = hash_table->nodes[i]; node; node = node->next)
708 node->value = (* func) (node->key, node->value, user_data);
712 g_hash_table_resize (MonoGHashTable *hash_table)
714 MonoGHashNode **new_nodes;
721 new_size = g_spaced_primes_closest (hash_table->nnodes);
722 new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
725 new_nodes = GC_MALLOC (sizeof (MonoGHashNode*) * new_size);
727 new_nodes = g_new0 (MonoGHashNode*, new_size);
730 for (i = 0; i < hash_table->size; i++)
731 for (node = hash_table->nodes[i]; node; node = next)
735 hash_val = (* hash_table->hash_func) (node->key) % new_size;
737 node->next = new_nodes[hash_val];
738 new_nodes[hash_val] = node;
743 g_free (hash_table->nodes);
745 hash_table->nodes = new_nodes;
746 hash_table->size = new_size;
750 g_hash_node_destroy (MonoGHashNode *hash_node,
751 MonoGHashGCType type,
752 GDestroyNotify key_destroy_func,
753 GDestroyNotify value_destroy_func)
755 if (key_destroy_func)
756 key_destroy_func (hash_node->key);
757 if (value_destroy_func)
758 value_destroy_func (hash_node->value);
760 hash_node->key = NULL;
761 hash_node->value = NULL;
763 G_LOCK (g_hash_global);
764 #if defined(HAVE_SGEN_GC)
765 hash_node->next = node_free_lists [type];
766 node_free_lists [type] = hash_node;
768 hash_node->next = node_free_list;
769 node_free_list = hash_node;
771 G_UNLOCK (g_hash_global);
775 g_hash_nodes_destroy (MonoGHashNode *hash_node,
776 MonoGHashGCType type,
777 GFreeFunc key_destroy_func,
778 GFreeFunc value_destroy_func)
782 MonoGHashNode *node = hash_node;
786 if (key_destroy_func)
787 key_destroy_func (node->key);
788 if (value_destroy_func)
789 value_destroy_func (node->value);
797 if (key_destroy_func)
798 key_destroy_func (node->key);
799 if (value_destroy_func)
800 value_destroy_func (node->value);
805 G_LOCK (g_hash_global);
806 #if defined(HAVE_SGEN_GC)
807 node->next = node_free_lists [type];
808 node_free_lists [type] = hash_node;
810 node->next = node_free_list;
811 node_free_list = hash_node;
813 G_UNLOCK (g_hash_global);