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-internal.h"
36 #define mg_new0(type,n) ((type *) GC_MALLOC(sizeof(type) * (n)))
37 #define mg_new(type,n) ((type *) GC_MALLOC(sizeof(type) * (n)))
38 #define mg_free(x) do { } while (0)
40 #define mg_new0(x,n) g_new0(x,n)
41 #define mg_new(type,n) g_new(type,n)
42 #define mg_free(x) g_free(x)
45 typedef struct _Slot Slot
;
53 static gpointer KEYMARKER_REMOVED
= &KEYMARKER_REMOVED
;
55 struct _MonoGHashTable
{
57 GEqualFunc key_equal_func
;
64 GDestroyNotify value_destroy_func
, key_destroy_func
;
65 MonoGHashGCType gc_type
;
68 static const int prime_tbl
[] = {
69 11, 19, 37, 73, 109, 163, 251, 367, 557, 823, 1237,
70 1861, 2777, 4177, 6247, 9371, 14057, 21089, 31627,
71 47431, 71143, 106721, 160073, 240101, 360163,
72 540217, 810343, 1215497, 1823231, 2734867, 4102283,
73 6153409, 9230113, 13845163
81 for (n
= 3; n
< (int)sqrt (x
); n
+= 2) {
87 // There is only one even prime - 2.
96 for (i
= (x
& (~1))-1; i
< G_MAXINT32
; i
+= 2) {
104 mono_g_hash_table_new_type (GHashFunc hash_func
, GEqualFunc key_equal_func
, MonoGHashGCType type
)
106 MonoGHashTable
*hash
= mono_g_hash_table_new (hash_func
, key_equal_func
);
108 hash
->gc_type
= type
;
114 mono_g_hash_table_new (GHashFunc hash_func
, GEqualFunc key_equal_func
)
116 MonoGHashTable
*hash
;
118 if (hash_func
== NULL
)
119 hash_func
= g_direct_hash
;
120 if (key_equal_func
== NULL
)
121 key_equal_func
= g_direct_equal
;
122 hash
= mg_new0 (MonoGHashTable
, 1);
124 hash
->hash_func
= hash_func
;
125 hash
->key_equal_func
= key_equal_func
;
127 hash
->table_size
= g_spaced_primes_closest (1);
128 hash
->table
= mg_new0 (Slot
*, hash
->table_size
);
129 hash
->last_rehash
= hash
->table_size
;
135 mono_g_hash_table_new_full (GHashFunc hash_func
, GEqualFunc key_equal_func
,
136 GDestroyNotify key_destroy_func
, GDestroyNotify value_destroy_func
)
138 MonoGHashTable
*hash
= mono_g_hash_table_new (hash_func
, key_equal_func
);
142 hash
->key_destroy_func
= key_destroy_func
;
143 hash
->value_destroy_func
= value_destroy_func
;
149 do_rehash (MonoGHashTable
*hash
)
154 /* printf ("Resizing diff=%d slots=%d\n", hash->in_use - hash->last_rehash, hash->table_size); */
155 hash
->last_rehash
= hash
->table_size
;
156 current_size
= hash
->table_size
;
157 hash
->table_size
= g_spaced_primes_closest (hash
->in_use
);
158 /* printf ("New size: %d\n", hash->table_size); */
160 hash
->table
= mg_new0 (Slot
*, hash
->table_size
);
162 for (i
= 0; i
< current_size
; i
++){
165 for (s
= table
[i
]; s
!= NULL
; s
= next
){
166 guint hashcode
= ((*hash
->hash_func
) (s
->key
)) % hash
->table_size
;
169 s
->next
= hash
->table
[hashcode
];
170 hash
->table
[hashcode
] = s
;
177 rehash (MonoGHashTable
*hash
)
179 int diff
= ABS (hash
->last_rehash
- hash
->in_use
);
181 /* These are the factors to play with to change the rehashing strategy */
182 /* I played with them with a large range, and could not really get */
183 /* something that was too good, maybe the tests are not that great */
184 if (!(diff
* 0.75 > hash
->table_size
* 2))
190 mono_g_hash_table_size (MonoGHashTable
*hash
)
192 g_return_val_if_fail (hash
!= NULL
, 0);
198 mono_g_hash_table_lookup (MonoGHashTable
*hash
, gconstpointer key
)
200 gpointer orig_key
, value
;
202 if (mono_g_hash_table_lookup_extended (hash
, key
, &orig_key
, &value
))
209 mono_g_hash_table_lookup_extended (MonoGHashTable
*hash
, gconstpointer key
, gpointer
*orig_key
, gpointer
*value
)
215 g_return_val_if_fail (hash
!= NULL
, FALSE
);
216 equal
= hash
->key_equal_func
;
218 hashcode
= ((*hash
->hash_func
) (key
)) % hash
->table_size
;
220 for (s
= hash
->table
[hashcode
]; s
!= NULL
; s
= s
->next
){
221 if ((*equal
)(s
->key
, key
)){
231 mono_g_hash_table_foreach (MonoGHashTable
*hash
, GHFunc func
, gpointer user_data
)
235 g_return_if_fail (hash
!= NULL
);
236 g_return_if_fail (func
!= NULL
);
238 for (i
= 0; i
< hash
->table_size
; i
++){
241 for (s
= hash
->table
[i
]; s
!= NULL
; s
= s
->next
)
242 (*func
)(s
->key
, s
->value
, user_data
);
247 mono_g_hash_table_remove (MonoGHashTable
*hash
, gconstpointer key
)
253 g_return_val_if_fail (hash
!= NULL
, FALSE
);
254 equal
= hash
->key_equal_func
;
256 hashcode
= ((*hash
->hash_func
)(key
)) % hash
->table_size
;
258 for (s
= hash
->table
[hashcode
]; s
!= NULL
; s
= s
->next
){
259 if ((*equal
)(s
->key
, key
)){
260 if (hash
->key_destroy_func
!= NULL
)
261 (*hash
->key_destroy_func
)(s
->key
);
262 if (hash
->value_destroy_func
!= NULL
)
263 (*hash
->value_destroy_func
)(s
->value
);
265 hash
->table
[hashcode
] = s
->next
;
267 last
->next
= s
->next
;
278 mono_g_hash_table_foreach_remove (MonoGHashTable
*hash
, GHRFunc func
, gpointer user_data
)
283 g_return_val_if_fail (hash
!= NULL
, 0);
284 g_return_val_if_fail (func
!= NULL
, 0);
286 for (i
= 0; i
< hash
->table_size
; i
++){
290 for (s
= hash
->table
[i
]; s
!= NULL
; ){
291 if ((*func
)(s
->key
, s
->value
, user_data
)){
294 if (hash
->key_destroy_func
!= NULL
)
295 (*hash
->key_destroy_func
)(s
->key
);
296 if (hash
->value_destroy_func
!= NULL
)
297 (*hash
->value_destroy_func
)(s
->value
);
299 hash
->table
[i
] = s
->next
;
302 last
->next
= s
->next
;
321 mono_g_hash_table_destroy (MonoGHashTable
*hash
)
325 g_return_if_fail (hash
!= NULL
);
327 for (i
= 0; i
< hash
->table_size
; i
++){
330 for (s
= hash
->table
[i
]; s
!= NULL
; s
= next
){
333 if (hash
->key_destroy_func
!= NULL
)
334 (*hash
->key_destroy_func
)(s
->key
);
335 if (hash
->value_destroy_func
!= NULL
)
336 (*hash
->value_destroy_func
)(s
->value
);
340 mg_free (hash
->table
);
345 mono_g_hash_table_insert_replace (MonoGHashTable
*hash
, gpointer key
, gpointer value
, gboolean replace
)
351 g_return_if_fail (hash
!= NULL
);
353 equal
= hash
->key_equal_func
;
354 if (hash
->in_use
>= hash
->threshold
)
357 hashcode
= ((*hash
->hash_func
) (key
)) % hash
->table_size
;
358 for (s
= hash
->table
[hashcode
]; s
!= NULL
; s
= s
->next
){
359 if ((*equal
) (s
->key
, key
)){
361 if (hash
->key_destroy_func
!= NULL
)
362 (*hash
->key_destroy_func
)(s
->key
);
365 if (hash
->value_destroy_func
!= NULL
)
366 (*hash
->value_destroy_func
) (s
->value
);
371 s
= mg_new (Slot
, 1);
374 s
->next
= hash
->table
[hashcode
];
375 hash
->table
[hashcode
] = s
;
380 mono_g_hash_table_insert (MonoGHashTable
*h
, gpointer k
, gpointer v
)
382 mono_g_hash_table_insert_replace (h
, k
, v
, FALSE
);
386 mono_g_hash_table_replace(MonoGHashTable
*h
, gpointer k
, gpointer v
)
388 mono_g_hash_table_insert_replace (h
, k
, v
, TRUE
);