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 #include "mono-hash.h"
33 #include "metadata/gc-internals.h"
34 #include <mono/utils/checked-build.h>
35 #include <mono/utils/mono-threads-coop.h>
38 #define mg_new0(type,n) ((type *) GC_MALLOC(sizeof(type) * (n)))
39 #define mg_new(type,n) ((type *) GC_MALLOC(sizeof(type) * (n)))
40 #define mg_free(x) do { } while (0)
42 #define mg_new0(x,n) g_new0(x,n)
43 #define mg_new(type,n) g_new(type,n)
44 #define mg_free(x) g_free(x)
47 typedef struct _Slot Slot;
55 static gpointer KEYMARKER_REMOVED = &KEYMARKER_REMOVED;
57 struct _MonoGHashTable {
59 GEqualFunc key_equal_func;
66 GDestroyNotify value_destroy_func, key_destroy_func;
67 MonoGHashGCType gc_type;
68 MonoGCRootSource source;
72 static MonoGHashTable *
73 mono_g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func);
76 static MonoGCDescriptor table_hash_descr = MONO_GC_DESCRIPTOR_NULL;
78 static void mono_g_hash_mark (void *addr, MonoGCMarkFunc mark_func, void *gc_data);
82 new_slot (MonoGHashTable *hash)
84 return mg_new (Slot, 1);
88 free_slot (MonoGHashTable *hash, Slot *slot)
99 for (n = 3; n< (int)sqrt (x); n += 2) {
105 // There is only one even prime - 2.
114 for (i = (x & (~1))-1; i< G_MAXINT32; i += 2) {
123 mono_g_hash_table_new_type (GHashFunc hash_func, GEqualFunc key_equal_func, MonoGHashGCType type, MonoGCRootSource source, const char *msg)
125 MonoGHashTable *hash = mono_g_hash_table_new (hash_func, key_equal_func);
127 hash->gc_type = type;
128 hash->source = source;
131 if (type > MONO_HASH_KEY_VALUE_GC)
132 g_error ("wrong type for gc hashtable");
136 * We use a user defined marking function to avoid having to register a GC root for
139 if (!table_hash_descr)
140 table_hash_descr = mono_gc_make_root_descr_user (mono_g_hash_mark);
141 mono_gc_register_root_wbarrier ((char*)hash, sizeof (MonoGHashTable), table_hash_descr, source, msg);
147 static MonoGHashTable *
148 mono_g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func)
150 MonoGHashTable *hash;
152 if (hash_func == NULL)
153 hash_func = g_direct_hash;
154 if (key_equal_func == NULL)
155 key_equal_func = g_direct_equal;
156 hash = mg_new0 (MonoGHashTable, 1);
158 hash->hash_func = hash_func;
159 hash->key_equal_func = key_equal_func;
161 hash->table_size = g_spaced_primes_closest (1);
162 hash->table = mg_new0 (Slot *, hash->table_size);
163 hash->last_rehash = hash->table_size;
169 MonoGHashTable *hash;
175 do_rehash (void *_data)
177 RehashData *data = (RehashData *)_data;
178 MonoGHashTable *hash = data->hash;
182 /* printf ("Resizing diff=%d slots=%d\n", hash->in_use - hash->last_rehash, hash->table_size); */
183 hash->last_rehash = hash->table_size;
184 current_size = hash->table_size;
185 hash->table_size = data->new_size;
186 /* printf ("New size: %d\n", hash->table_size); */
188 hash->table = data->table;
190 for (i = 0; i < current_size; i++){
193 for (s = table [i]; s != NULL; s = next){
194 guint hashcode = ((*hash->hash_func) (s->key)) % hash->table_size;
197 s->next = hash->table [hashcode];
198 hash->table [hashcode] = s;
205 rehash (MonoGHashTable *hash)
207 MONO_REQ_GC_UNSAFE_MODE; //we must run in unsafe mode to make rehash safe
209 int diff = ABS (hash->last_rehash - hash->in_use);
211 void *old_table G_GNUC_UNUSED; /* unused on Boehm */
213 /* These are the factors to play with to change the rehashing strategy */
214 /* I played with them with a large range, and could not really get */
215 /* something that was too good, maybe the tests are not that great */
216 if (!(diff * 0.75 > hash->table_size * 2))
220 data.new_size = g_spaced_primes_closest (hash->in_use);
221 data.table = mg_new0 (Slot *, data.new_size);
223 if (!mono_threads_is_coop_enabled ()) {
224 old_table = mono_gc_invoke_with_gc_lock (do_rehash, &data);
226 /* We cannot be preempted */
227 old_table = do_rehash (&data);
234 mono_g_hash_table_size (MonoGHashTable *hash)
236 g_return_val_if_fail (hash != NULL, 0);
242 mono_g_hash_table_lookup (MonoGHashTable *hash, gconstpointer key)
244 gpointer orig_key, value;
246 if (mono_g_hash_table_lookup_extended (hash, key, &orig_key, &value))
253 mono_g_hash_table_lookup_extended (MonoGHashTable *hash, gconstpointer key, gpointer *orig_key, gpointer *value)
259 g_return_val_if_fail (hash != NULL, FALSE);
260 equal = hash->key_equal_func;
262 hashcode = ((*hash->hash_func) (key)) % hash->table_size;
264 for (s = hash->table [hashcode]; s != NULL; s = s->next){
265 if ((*equal)(s->key, key)){
275 mono_g_hash_table_foreach (MonoGHashTable *hash, GHFunc func, gpointer user_data)
279 g_return_if_fail (hash != NULL);
280 g_return_if_fail (func != NULL);
282 for (i = 0; i < hash->table_size; i++){
285 for (s = hash->table [i]; s != NULL; s = s->next)
286 (*func)(s->key, s->value, user_data);
291 mono_g_hash_table_find (MonoGHashTable *hash, GHRFunc predicate, gpointer user_data)
295 g_return_val_if_fail (hash != NULL, NULL);
296 g_return_val_if_fail (predicate != NULL, NULL);
298 for (i = 0; i < hash->table_size; i++){
301 for (s = hash->table [i]; s != NULL; s = s->next)
302 if ((*predicate)(s->key, s->value, user_data))
309 mono_g_hash_table_remove (MonoGHashTable *hash, gconstpointer key)
315 g_return_val_if_fail (hash != NULL, FALSE);
316 equal = hash->key_equal_func;
318 hashcode = ((*hash->hash_func)(key)) % hash->table_size;
320 for (s = hash->table [hashcode]; s != NULL; s = s->next){
321 if ((*equal)(s->key, key)){
322 if (hash->key_destroy_func != NULL)
323 (*hash->key_destroy_func)(s->key);
324 if (hash->value_destroy_func != NULL)
325 (*hash->value_destroy_func)(s->value);
327 hash->table [hashcode] = s->next;
329 last->next = s->next;
340 mono_g_hash_table_foreach_remove (MonoGHashTable *hash, GHRFunc func, gpointer user_data)
345 g_return_val_if_fail (hash != NULL, 0);
346 g_return_val_if_fail (func != NULL, 0);
348 for (i = 0; i < hash->table_size; i++){
352 for (s = hash->table [i]; s != NULL; ){
353 if ((*func)(s->key, s->value, user_data)){
356 if (hash->key_destroy_func != NULL)
357 (*hash->key_destroy_func)(s->key);
358 if (hash->value_destroy_func != NULL)
359 (*hash->value_destroy_func)(s->value);
361 hash->table [i] = s->next;
364 last->next = s->next;
383 mono_g_hash_table_destroy (MonoGHashTable *hash)
387 g_return_if_fail (hash != NULL);
390 mono_gc_deregister_root ((char*)hash);
393 for (i = 0; i < hash->table_size; i++){
396 for (s = hash->table [i]; s != NULL; s = next){
399 if (hash->key_destroy_func != NULL)
400 (*hash->key_destroy_func)(s->key);
401 if (hash->value_destroy_func != NULL)
402 (*hash->value_destroy_func)(s->value);
406 mg_free (hash->table);
411 mono_g_hash_table_insert_replace (MonoGHashTable *hash, gpointer key, gpointer value, gboolean replace)
417 g_return_if_fail (hash != NULL);
419 equal = hash->key_equal_func;
420 if (hash->in_use >= hash->threshold)
423 hashcode = ((*hash->hash_func) (key)) % hash->table_size;
424 for (s = hash->table [hashcode]; s != NULL; s = s->next){
425 if ((*equal) (s->key, key)){
427 if (hash->key_destroy_func != NULL)
428 (*hash->key_destroy_func)(s->key);
429 s->key = (MonoObject *)key;
431 if (hash->value_destroy_func != NULL)
432 (*hash->value_destroy_func) (s->value);
433 s->value = (MonoObject *)value;
438 s->key = (MonoObject *)key;
439 s->value = (MonoObject *)value;
440 s->next = hash->table [hashcode];
441 hash->table [hashcode] = s;
446 mono_g_hash_table_insert (MonoGHashTable *h, gpointer k, gpointer v)
448 mono_g_hash_table_insert_replace (h, k, v, FALSE);
452 mono_g_hash_table_replace(MonoGHashTable *h, gpointer k, gpointer v)
454 mono_g_hash_table_insert_replace (h, k, v, TRUE);
458 mono_g_hash_table_print_stats (MonoGHashTable *table)
460 int i, chain_size, max_chain_size;
464 for (i = 0; i < table->table_size; i++) {
466 for (node = table->table [i]; node; node = node->next)
468 max_chain_size = MAX(max_chain_size, chain_size);
471 printf ("Size: %d Table Size: %d Max Chain Length: %d\n", table->in_use, table->table_size, max_chain_size);
476 /* GC marker function */
478 mono_g_hash_mark (void *addr, MonoGCMarkFunc mark_func, void *gc_data)
480 MonoGHashTable *table = (MonoGHashTable*)addr;
484 if (table->gc_type == MONO_HASH_KEY_GC) {
485 for (i = 0; i < table->table_size; i++) {
486 for (node = table->table [i]; node; node = node->next) {
488 mark_func (&node->key, gc_data);
491 } else if (table->gc_type == MONO_HASH_VALUE_GC) {
492 for (i = 0; i < table->table_size; i++) {
493 for (node = table->table [i]; node; node = node->next) {
495 mark_func (&node->value, gc_data);
498 } else if (table->gc_type == MONO_HASH_KEY_VALUE_GC) {
499 for (i = 0; i < table->table_size; i++) {
500 for (node = table->table [i]; node; node = node->next) {
502 mark_func (&node->key, gc_data);
504 mark_func (&node->value, gc_data);