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 typedef struct _Slot Slot
;
40 static gpointer KEYMARKER_REMOVED
= &KEYMARKER_REMOVED
;
44 GEqualFunc key_equal_func
;
51 GDestroyNotify value_destroy_func
, key_destroy_func
;
54 static const guint prime_tbl
[] = {
55 11, 19, 37, 73, 109, 163, 251, 367, 557, 823, 1237,
56 1861, 2777, 4177, 6247, 9371, 14057, 21089, 31627,
57 47431, 71143, 106721, 160073, 240101, 360163,
58 540217, 810343, 1215497, 1823231, 2734867, 4102283,
59 6153409, 9230113, 13845163
67 for (n
= 3; n
< (int)sqrt (x
); n
+= 2) {
73 // There is only one even prime - 2.
82 for (i
= (x
& (~1))-1; i
< G_MAXINT32
; i
+= 2) {
90 g_spaced_primes_closest (guint x
)
94 for (i
= 0; i
< G_N_ELEMENTS (prime_tbl
); i
++) {
95 if (x
<= prime_tbl
[i
])
98 return calc_prime (x
);
102 g_hash_table_new (GHashFunc hash_func
, GEqualFunc key_equal_func
)
106 if (hash_func
== NULL
)
107 hash_func
= g_direct_hash
;
108 if (key_equal_func
== NULL
)
109 key_equal_func
= g_direct_equal
;
110 hash
= g_new0 (GHashTable
, 1);
112 hash
->hash_func
= hash_func
;
113 hash
->key_equal_func
= key_equal_func
;
115 hash
->table_size
= g_spaced_primes_closest (1);
116 hash
->table
= g_new0 (Slot
*, hash
->table_size
);
117 hash
->last_rehash
= hash
->table_size
;
123 g_hash_table_new_full (GHashFunc hash_func
, GEqualFunc key_equal_func
,
124 GDestroyNotify key_destroy_func
, GDestroyNotify value_destroy_func
)
126 GHashTable
*hash
= g_hash_table_new (hash_func
, key_equal_func
);
130 hash
->key_destroy_func
= key_destroy_func
;
131 hash
->value_destroy_func
= value_destroy_func
;
137 do_rehash (GHashTable
*hash
)
142 /* printf ("Resizing diff=%d slots=%d\n", hash->in_use - hash->last_rehash, hash->table_size); */
143 hash
->last_rehash
= hash
->table_size
;
144 current_size
= hash
->table_size
;
145 hash
->table_size
= g_spaced_primes_closest (hash
->in_use
);
146 /* printf ("New size: %d\n", hash->table_size); */
148 hash
->table
= g_new0 (Slot
*, hash
->table_size
);
150 for (i
= 0; i
< current_size
; i
++){
153 for (s
= table
[i
]; s
!= NULL
; s
= next
){
154 guint hashcode
= ((*hash
->hash_func
) (s
->key
)) % hash
->table_size
;
157 s
->next
= hash
->table
[hashcode
];
158 hash
->table
[hashcode
] = s
;
165 rehash (GHashTable
*hash
)
167 int diff
= ABS (hash
->last_rehash
- hash
->in_use
);
169 /* These are the factors to play with to change the rehashing strategy */
170 /* I played with them with a large range, and could not really get */
171 /* something that was too good, maybe the tests are not that great */
172 if (!(diff
* 0.75 > hash
->table_size
* 2))
178 g_hash_table_insert_replace (GHashTable
*hash
, gpointer key
, gpointer value
, gboolean replace
)
184 g_return_if_fail (hash
!= NULL
);
186 equal
= hash
->key_equal_func
;
187 if (hash
->in_use
>= hash
->threshold
)
190 hashcode
= ((*hash
->hash_func
) (key
)) % hash
->table_size
;
191 for (s
= hash
->table
[hashcode
]; s
!= NULL
; s
= s
->next
){
192 if ((*equal
) (s
->key
, key
)){
194 if (hash
->key_destroy_func
!= NULL
)
195 (*hash
->key_destroy_func
)(s
->key
);
198 if (hash
->value_destroy_func
!= NULL
)
199 (*hash
->value_destroy_func
) (s
->value
);
207 s
->next
= hash
->table
[hashcode
];
208 hash
->table
[hashcode
] = s
;
213 g_hash_table_size (GHashTable
*hash
)
215 g_return_val_if_fail (hash
!= NULL
, 0);
221 g_hash_table_lookup (GHashTable
*hash
, gconstpointer key
)
223 gpointer orig_key
, value
;
225 if (g_hash_table_lookup_extended (hash
, key
, &orig_key
, &value
))
232 g_hash_table_lookup_extended (GHashTable
*hash
, gconstpointer key
, gpointer
*orig_key
, gpointer
*value
)
238 g_return_val_if_fail (hash
!= NULL
, FALSE
);
239 equal
= hash
->key_equal_func
;
241 hashcode
= ((*hash
->hash_func
) (key
)) % hash
->table_size
;
243 for (s
= hash
->table
[hashcode
]; s
!= NULL
; s
= s
->next
){
244 if ((*equal
)(s
->key
, key
)){
254 g_hash_table_foreach (GHashTable
*hash
, GHFunc func
, gpointer user_data
)
258 g_return_if_fail (hash
!= NULL
);
259 g_return_if_fail (func
!= NULL
);
261 for (i
= 0; i
< hash
->table_size
; i
++){
264 for (s
= hash
->table
[i
]; s
!= NULL
; s
= s
->next
)
265 (*func
)(s
->key
, s
->value
, user_data
);
270 g_hash_table_find (GHashTable
*hash
, GHRFunc predicate
, gpointer user_data
)
274 g_return_val_if_fail (hash
!= NULL
, NULL
);
275 g_return_val_if_fail (predicate
!= NULL
, NULL
);
277 for (i
= 0; i
< hash
->table_size
; i
++){
280 for (s
= hash
->table
[i
]; s
!= NULL
; s
= s
->next
)
281 if ((*predicate
)(s
->key
, s
->value
, user_data
))
288 g_hash_table_remove (GHashTable
*hash
, gconstpointer key
)
294 g_return_val_if_fail (hash
!= NULL
, FALSE
);
295 equal
= hash
->key_equal_func
;
297 hashcode
= ((*hash
->hash_func
)(key
)) % hash
->table_size
;
299 for (s
= hash
->table
[hashcode
]; s
!= NULL
; s
= s
->next
){
300 if ((*equal
)(s
->key
, key
)){
301 if (hash
->key_destroy_func
!= NULL
)
302 (*hash
->key_destroy_func
)(s
->key
);
303 if (hash
->value_destroy_func
!= NULL
)
304 (*hash
->value_destroy_func
)(s
->value
);
306 hash
->table
[hashcode
] = s
->next
;
308 last
->next
= s
->next
;
319 g_hash_table_foreach_remove (GHashTable
*hash
, GHRFunc func
, gpointer user_data
)
324 g_return_val_if_fail (hash
!= NULL
, 0);
325 g_return_val_if_fail (func
!= NULL
, 0);
327 for (i
= 0; i
< hash
->table_size
; i
++){
331 for (s
= hash
->table
[i
]; s
!= NULL
; ){
332 if ((*func
)(s
->key
, s
->value
, user_data
)){
335 if (hash
->key_destroy_func
!= NULL
)
336 (*hash
->key_destroy_func
)(s
->key
);
337 if (hash
->value_destroy_func
!= NULL
)
338 (*hash
->value_destroy_func
)(s
->value
);
340 hash
->table
[i
] = s
->next
;
343 last
->next
= s
->next
;
362 g_hash_table_foreach_steal (GHashTable
*hash
, GHRFunc func
, gpointer user_data
)
367 g_return_val_if_fail (hash
!= NULL
, 0);
368 g_return_val_if_fail (func
!= NULL
, 0);
370 for (i
= 0; i
< hash
->table_size
; i
++){
374 for (s
= hash
->table
[i
]; s
!= NULL
; ){
375 if ((*func
)(s
->key
, s
->value
, user_data
)){
379 hash
->table
[i
] = s
->next
;
382 last
->next
= s
->next
;
401 g_hash_table_destroy (GHashTable
*hash
)
405 g_return_if_fail (hash
!= NULL
);
407 for (i
= 0; i
< hash
->table_size
; i
++){
410 for (s
= hash
->table
[i
]; s
!= NULL
; s
= next
){
413 if (hash
->key_destroy_func
!= NULL
)
414 (*hash
->key_destroy_func
)(s
->key
);
415 if (hash
->value_destroy_func
!= NULL
)
416 (*hash
->value_destroy_func
)(s
->value
);
420 g_free (hash
->table
);
426 g_direct_equal (gconstpointer v1
, gconstpointer v2
)
432 g_direct_hash (gconstpointer v1
)
434 return GPOINTER_TO_UINT (v1
);
438 g_int_equal (gconstpointer v1
, gconstpointer v2
)
440 return GPOINTER_TO_INT (v1
) == GPOINTER_TO_INT (v2
);
444 g_int_hash (gconstpointer v1
)
446 return GPOINTER_TO_UINT(v1
);
450 g_str_equal (gconstpointer v1
, gconstpointer v2
)
452 return strcmp (v1
, v2
) == 0;
456 g_str_hash (gconstpointer v1
)
459 char *p
= (char *) v1
;
462 hash
= (hash
<< 5) - (hash
+ *p
);