3 * Hashtable implementation
6 * Miguel de Icaza (miguel@novell.com)
8 * (C) 2006 Novell, Inc.
10 * Permission is hereby granted, free of charge, to any person obtaining
11 * a copy of this software and associated documentation files (the
12 * "Software"), to deal in the Software without restriction, including
13 * without limitation the rights to use, copy, modify, merge, publish,
14 * distribute, sublicense, and/or sell copies of the Software, and to
15 * permit persons to whom the Software is furnished to do so, subject to
16 * the following conditions:
18 * The above copyright notice and this permission notice shall be
19 * included in all copies or substantial portions of the Software.
21 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
22 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
23 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
24 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
25 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
26 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
27 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
34 #include "mono-hash.h"
35 #include "mono-hash-internals.h"
36 #include "metadata/gc-internals.h"
38 #include <mono/utils/checked-build.h>
39 #include <mono/utils/mono-threads-coop.h>
40 #include <mono/utils/unlocked.h>
42 gint32 mono_g_hash_table_max_chain_length
;
44 struct _MonoGHashTable
{
46 GEqualFunc key_equal_func
;
52 GDestroyNotify value_destroy_func
, key_destroy_func
;
53 MonoGHashGCType gc_type
;
54 MonoGCRootSource source
;
65 for (n
= 3; n
< (int)sqrt (x
); n
+= 2) {
71 // There is only one even prime - 2.
80 for (i
= (x
& (~1))-1; i
< G_MAXINT32
; i
+= 2) {
88 #define HASH_TABLE_MAX_LOAD_FACTOR 0.7f
89 /* We didn't really do compaction before, keep it lenient for now */
90 #define HASH_TABLE_MIN_LOAD_FACTOR 0.05f
91 /* We triple the table size at rehash time, similar with previous implementation */
92 #define HASH_TABLE_RESIZE_RATIO 3
94 static void mono_g_hash_table_key_store (MonoGHashTable
*hash
, int slot
, MonoObject
* key
)
96 MonoObject
**key_addr
= &hash
->keys
[slot
];
97 if (hash
->gc_type
& MONO_HASH_KEY_GC
)
98 mono_gc_wbarrier_generic_store_internal (key_addr
, key
);
103 static void mono_g_hash_table_value_store (MonoGHashTable
*hash
, int slot
, MonoObject
* value
)
105 MonoObject
**value_addr
= &hash
->values
[slot
];
106 if (hash
->gc_type
& MONO_HASH_VALUE_GC
)
107 mono_gc_wbarrier_generic_store_internal (value_addr
, value
);
112 /* Returns position of key or of an empty slot for it */
113 static int mono_g_hash_table_find_slot (MonoGHashTable
*hash
, const MonoObject
*key
)
115 guint start
= ((*hash
->hash_func
) (key
)) % hash
->table_size
;
118 if (hash
->key_equal_func
) {
119 GEqualFunc equal
= hash
->key_equal_func
;
121 while (hash
->keys
[i
] && !(*equal
) (hash
->keys
[i
], key
)) {
123 if (i
== hash
->table_size
)
127 while (hash
->keys
[i
] && hash
->keys
[i
] != key
) {
129 if (i
== hash
->table_size
)
134 gint32 max_length
= UnlockedRead (&mono_g_hash_table_max_chain_length
);
135 if (i
> start
&& (i
- start
) > max_length
)
136 UnlockedWrite (&mono_g_hash_table_max_chain_length
, i
- start
);
137 else if (i
< start
&& (hash
->table_size
- (start
- i
)) > max_length
)
138 UnlockedWrite (&mono_g_hash_table_max_chain_length
, hash
->table_size
- (start
- i
));
144 mono_g_hash_table_new_type_internal (GHashFunc hash_func
, GEqualFunc key_equal_func
, MonoGHashGCType type
, MonoGCRootSource source
, void *key
, const char *msg
)
146 MONO_REQ_GC_UNSAFE_MODE
;
147 MonoGHashTable
*hash
;
150 hash_func
= g_direct_hash
;
152 hash
= g_new0 (MonoGHashTable
, 1);
154 hash
->hash_func
= hash_func
;
155 hash
->key_equal_func
= key_equal_func
;
157 hash
->table_size
= g_spaced_primes_closest (1);
158 hash
->keys
= g_new0 (MonoObject
*, hash
->table_size
);
159 hash
->values
= g_new0 (MonoObject
*, hash
->table_size
);
161 hash
->gc_type
= type
;
162 hash
->source
= source
;
166 if (type
> MONO_HASH_KEY_VALUE_GC
)
167 g_error ("wrong type for gc hashtable");
169 if (hash
->gc_type
& MONO_HASH_KEY_GC
)
170 mono_gc_register_root_wbarrier ((char*)hash
->keys
, sizeof (MonoObject
*) * hash
->table_size
, mono_gc_make_vector_descr (), hash
->source
, hash
->key
, hash
->msg
);
171 if (hash
->gc_type
& MONO_HASH_VALUE_GC
)
172 mono_gc_register_root_wbarrier ((char*)hash
->values
, sizeof (MonoObject
*) * hash
->table_size
, mono_gc_make_vector_descr (), hash
->source
, hash
->key
, hash
->msg
);
178 MonoGHashTable
*hash
;
185 do_rehash (void *_data
)
187 RehashData
*data
= (RehashData
*)_data
;
188 MonoGHashTable
*hash
= data
->hash
;
190 MonoObject
**old_keys
;
191 MonoObject
**old_values
;
193 current_size
= hash
->table_size
;
194 hash
->table_size
= data
->new_size
;
195 old_keys
= hash
->keys
;
196 old_values
= hash
->values
;
197 hash
->keys
= data
->keys
;
198 hash
->values
= data
->values
;
200 for (i
= 0; i
< current_size
; i
++) {
202 int slot
= mono_g_hash_table_find_slot (hash
, old_keys
[i
]);
203 mono_g_hash_table_key_store (hash
, slot
, old_keys
[i
]);
204 mono_g_hash_table_value_store (hash
, slot
, old_values
[i
]);
211 rehash (MonoGHashTable
*hash
)
213 MONO_REQ_GC_UNSAFE_MODE
; //we must run in unsafe mode to make rehash safe
216 void *old_keys
= hash
->keys
;
217 void *old_values
= hash
->values
;
221 * Rehash to a size that can fit the current elements. Rehash relative to in_use
222 * to allow also for compaction.
224 data
.new_size
= g_spaced_primes_closest (hash
->in_use
/ HASH_TABLE_MAX_LOAD_FACTOR
* HASH_TABLE_RESIZE_RATIO
);
225 data
.keys
= g_new0 (MonoObject
*, data
.new_size
);
226 data
.values
= g_new0 (MonoObject
*, data
.new_size
);
228 if (hash
->gc_type
& MONO_HASH_KEY_GC
)
229 mono_gc_register_root_wbarrier ((char*)data
.keys
, sizeof (MonoObject
*) * data
.new_size
, mono_gc_make_vector_descr (), hash
->source
, hash
->key
, hash
->msg
);
230 if (hash
->gc_type
& MONO_HASH_VALUE_GC
)
231 mono_gc_register_root_wbarrier ((char*)data
.values
, sizeof (MonoObject
*) * data
.new_size
, mono_gc_make_vector_descr (), hash
->source
, hash
->key
, hash
->msg
);
233 if (!mono_threads_are_safepoints_enabled ()) {
234 mono_gc_invoke_with_gc_lock (do_rehash
, &data
);
236 /* We cannot be preempted */
240 if (hash
->gc_type
& MONO_HASH_KEY_GC
)
241 mono_gc_deregister_root ((char*)old_keys
);
242 if (hash
->gc_type
& MONO_HASH_VALUE_GC
)
243 mono_gc_deregister_root ((char*)old_values
);
250 * mono_g_hash_table_size:
253 mono_g_hash_table_size (MonoGHashTable
*hash
)
255 g_return_val_if_fail (hash
!= NULL
, 0);
261 * mono_g_hash_table_lookup:
264 mono_g_hash_table_lookup (MonoGHashTable
*hash
, gconstpointer key
)
266 gpointer orig_key
, value
;
268 if (mono_g_hash_table_lookup_extended (hash
, key
, &orig_key
, &value
))
275 * mono_g_hash_table_lookup_extended:
278 mono_g_hash_table_lookup_extended (MonoGHashTable
*hash
, gconstpointer key
, gpointer
*orig_key
, gpointer
*value
)
282 g_return_val_if_fail (hash
!= NULL
, FALSE
);
284 slot
= mono_g_hash_table_find_slot (hash
, (MonoObject
*)key
);
286 if (hash
->keys
[slot
]) {
288 *orig_key
= hash
->keys
[slot
];
290 *value
= hash
->values
[slot
];
298 * mono_g_hash_table_foreach:
301 mono_g_hash_table_foreach (MonoGHashTable
*hash
, GHFunc func
, gpointer user_data
)
305 g_return_if_fail (hash
!= NULL
);
306 g_return_if_fail (func
!= NULL
);
308 for (i
= 0; i
< hash
->table_size
; i
++) {
310 (*func
)(hash
->keys
[i
], hash
->values
[i
], user_data
);
315 mono_g_hash_table_find (MonoGHashTable
*hash
, GHRFunc predicate
, gpointer user_data
)
319 g_return_val_if_fail (hash
!= NULL
, NULL
);
320 g_return_val_if_fail (predicate
!= NULL
, NULL
);
322 for (i
= 0; i
< hash
->table_size
; i
++) {
323 if (hash
->keys
[i
] && (*predicate
)(hash
->keys
[i
], hash
->values
[i
], user_data
))
324 return hash
->values
[i
];
330 * mono_g_hash_table_remove:
333 mono_g_hash_table_remove (MonoGHashTable
*hash
, gconstpointer key
)
335 int slot
, last_clear_slot
;
337 g_return_val_if_fail (hash
!= NULL
, FALSE
);
338 slot
= mono_g_hash_table_find_slot (hash
, (MonoObject
*)key
);
340 if (!hash
->keys
[slot
])
343 if (hash
->key_destroy_func
)
344 (*hash
->key_destroy_func
)(hash
->keys
[slot
]);
345 hash
->keys
[slot
] = NULL
;
346 if (hash
->value_destroy_func
)
347 (*hash
->value_destroy_func
)(hash
->values
[slot
]);
348 hash
->values
[slot
] = NULL
;
352 * When we insert in the hashtable, if the required position is occupied we
353 * consecutively try out following positions. In order to be able to find
354 * if a key exists or not in the array (without traversing the entire hash)
355 * we maintain the constraint that there can be no free slots between two
356 * entries that are hashed to the same position. This means that, at search
357 * time, when we encounter a free slot we can stop looking for collissions.
358 * Similarly, at remove time, we need to shift all following slots to their
359 * normal slot, until we reach an empty slot.
361 last_clear_slot
= slot
;
362 slot
= (slot
+ 1) % hash
->table_size
;
363 while (hash
->keys
[slot
]) {
364 guint hashcode
= ((*hash
->hash_func
)(hash
->keys
[slot
])) % hash
->table_size
;
366 * We try to move the current element to last_clear_slot, but only if
367 * it brings it closer to its normal position (hashcode)
369 if ((last_clear_slot
< slot
&& (hashcode
> slot
|| hashcode
<= last_clear_slot
)) ||
370 (last_clear_slot
> slot
&& (hashcode
> slot
&& hashcode
<= last_clear_slot
))) {
371 mono_g_hash_table_key_store (hash
, last_clear_slot
, hash
->keys
[slot
]);
372 mono_g_hash_table_value_store (hash
, last_clear_slot
, hash
->values
[slot
]);
373 hash
->keys
[slot
] = NULL
;
374 hash
->values
[slot
] = NULL
;
375 last_clear_slot
= slot
;
378 if (slot
== hash
->table_size
)
385 * mono_g_hash_table_foreach_remove:
388 mono_g_hash_table_foreach_remove (MonoGHashTable
*hash
, GHRFunc func
, gpointer user_data
)
393 g_return_val_if_fail (hash
!= NULL
, 0);
394 g_return_val_if_fail (func
!= NULL
, 0);
396 for (i
= 0; i
< hash
->table_size
; i
++) {
397 if (hash
->keys
[i
] && (*func
)(hash
->keys
[i
], hash
->values
[i
], user_data
)) {
398 mono_g_hash_table_remove (hash
, hash
->keys
[i
]);
400 /* Retry current slot in case the removal shifted elements */
404 if (hash
->in_use
< hash
->table_size
* HASH_TABLE_MIN_LOAD_FACTOR
)
410 * mono_g_hash_table_destroy:
413 mono_g_hash_table_destroy (MonoGHashTable
*hash
)
417 g_return_if_fail (hash
!= NULL
);
419 if (hash
->gc_type
& MONO_HASH_KEY_GC
)
420 mono_gc_deregister_root ((char*)hash
->keys
);
421 if (hash
->gc_type
& MONO_HASH_VALUE_GC
)
422 mono_gc_deregister_root ((char*)hash
->values
);
424 for (i
= 0; i
< hash
->table_size
; i
++) {
425 if (hash
->keys
[i
]) {
426 if (hash
->key_destroy_func
)
427 (*hash
->key_destroy_func
)(hash
->keys
[i
]);
428 if (hash
->value_destroy_func
)
429 (*hash
->value_destroy_func
)(hash
->values
[i
]);
433 g_free (hash
->values
);
438 mono_g_hash_table_insert_replace (MonoGHashTable
*hash
, gpointer key
, gpointer value
, gboolean replace
)
440 MONO_REQ_GC_UNSAFE_MODE
;
442 g_return_if_fail (hash
!= NULL
);
444 if (hash
->in_use
> (hash
->table_size
* HASH_TABLE_MAX_LOAD_FACTOR
))
447 slot
= mono_g_hash_table_find_slot (hash
, (MonoObject
*)key
);
449 if (hash
->keys
[slot
]) {
451 if (hash
->key_destroy_func
)
452 (*hash
->key_destroy_func
)(hash
->keys
[slot
]);
453 mono_g_hash_table_key_store (hash
, slot
, (MonoObject
*)key
);
455 if (hash
->value_destroy_func
)
456 (*hash
->value_destroy_func
) (hash
->values
[slot
]);
457 mono_g_hash_table_value_store (hash
, slot
, (MonoObject
*)value
);
459 mono_g_hash_table_key_store (hash
, slot
, (MonoObject
*)key
);
460 mono_g_hash_table_value_store (hash
, slot
, (MonoObject
*)value
);
466 * mono_g_hash_table_insert:
469 mono_g_hash_table_insert (MonoGHashTable
*h
, gpointer k
, gpointer v
)
471 MONO_ENTER_GC_UNSAFE
;
472 mono_g_hash_table_insert_internal (h
, k
, v
);
477 mono_g_hash_table_insert_internal (MonoGHashTable
*h
, gpointer k
, gpointer v
)
479 MONO_REQ_GC_UNSAFE_MODE
;
480 mono_g_hash_table_insert_replace (h
, k
, v
, FALSE
);
484 * mono_g_hash_table_replace:
487 mono_g_hash_table_replace(MonoGHashTable
*h
, gpointer k
, gpointer v
)
489 mono_g_hash_table_insert_replace (h
, k
, v
, TRUE
);
493 mono_g_hash_table_print_stats (MonoGHashTable
*hash
)
495 int i
= 0, chain_size
= 0, max_chain_size
= 0;
496 gboolean wrapped_around
= FALSE
;
499 if (hash
->keys
[i
]) {
502 max_chain_size
= MAX(max_chain_size
, chain_size
);
508 if (i
== (hash
->table_size
- 1)) {
509 wrapped_around
= TRUE
;
515 /* Rehash to a size that can fit the current elements */
516 printf ("Size: %d Table Size: %d Max Chain Length: %d\n", hash
->in_use
, hash
->table_size
, max_chain_size
);