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"
43 #define HASH_TABLE_MIN_SIZE 11
44 #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
;
67 #define G_HASH_TABLE_RESIZE(hash_table) \
69 if ((hash_table->size >= 3 * hash_table->nnodes && \
70 hash_table->size > HASH_TABLE_MIN_SIZE) || \
71 (3 * hash_table->size <= hash_table->nnodes && \
72 hash_table->size < HASH_TABLE_MAX_SIZE)) \
73 g_hash_table_resize (hash_table); \
76 static void g_hash_table_resize (MonoGHashTable
*hash_table
);
77 static MonoGHashNode
** g_hash_table_lookup_node (MonoGHashTable
*hash_table
,
79 static MonoGHashNode
* g_hash_node_new (gpointer key
,
81 static void g_hash_node_destroy (MonoGHashNode
*hash_node
,
82 GDestroyNotify key_destroy_func
,
83 GDestroyNotify value_destroy_func
);
84 static void g_hash_nodes_destroy (MonoGHashNode
*hash_node
,
85 GDestroyNotify key_destroy_func
,
86 GDestroyNotify value_destroy_func
);
87 static guint
g_hash_table_foreach_remove_or_steal (MonoGHashTable
*hash_table
,
93 G_LOCK_DEFINE_STATIC (g_hash_global
);
96 static GMemChunk
*node_mem_chunk
= NULL
;
98 static MonoGHashNode
*node_free_list
= NULL
;
102 * @hash_func: a function to create a hash value from a key.
103 * Hash values are used to determine where keys are stored within the
104 * #GHashTable data structure. The g_direct_hash(), g_int_hash() and
105 * g_str_hash() functions are provided for some common types of keys.
106 * If hash_func is %NULL, g_direct_hash() is used.
107 * @key_equal_func: a function to check two keys for equality. This is
108 * used when looking up keys in the #GHashTable. The g_direct_equal(),
109 * g_int_equal() and g_str_equal() functions are provided for the most
110 * common types of keys. If @key_equal_func is %NULL, keys are compared
111 * directly in a similar fashion to g_direct_equal(), but without the
112 * overhead of a function call.
114 * Creates a new #GHashTable.
116 * Return value: a new #GHashTable.
119 mono_g_hash_table_new (GHashFunc hash_func
,
120 GEqualFunc key_equal_func
)
122 return mono_g_hash_table_new_full (hash_func
, key_equal_func
, NULL
, NULL
);
127 * g_hash_table_new_full:
128 * @hash_func: a function to create a hash value from a key.
129 * @key_equal_func: a function to check two keys for equality.
130 * @key_destroy_func: a function to free the memory allocated for the key
131 * used when removing the entry from the #GHashTable or %NULL if you
132 * don't want to supply such a function.
133 * @value_destroy_func: a function to free the memory allocated for the
134 * value used when removing the entry from the #GHashTable or %NULL if
135 * you don't want to supply such a function.
137 * Creates a new #GHashTable like g_hash_table_new() and allows to specify
138 * functions to free the memory allocated for the key and value that get
139 * called when removing the entry from the #GHashTable.
141 * Return value: a new #GHashTable.
144 mono_g_hash_table_new_full (GHashFunc hash_func
,
145 GEqualFunc key_equal_func
,
146 GDestroyNotify key_destroy_func
,
147 GDestroyNotify value_destroy_func
)
149 MonoGHashTable
*hash_table
;
150 static gboolean inited
= FALSE
;
152 MONO_GC_REGISTER_ROOT (node_free_list
);
157 hash_table
= GC_MALLOC (sizeof (MonoGHashTable
));
159 hash_table
= g_new (MonoGHashTable
, 1);
161 hash_table
->size
= HASH_TABLE_MIN_SIZE
;
162 hash_table
->nnodes
= 0;
163 hash_table
->hash_func
= hash_func
? hash_func
: g_direct_hash
;
164 hash_table
->key_equal_func
= key_equal_func
== g_direct_equal
? NULL
: key_equal_func
;
165 hash_table
->key_destroy_func
= key_destroy_func
;
166 hash_table
->value_destroy_func
= value_destroy_func
;
168 hash_table
->nodes
= GC_MALLOC (sizeof (MonoGHashNode
*) * hash_table
->size
);
170 hash_table
->nodes
= g_new0 (MonoGHashNode
*, hash_table
->size
);
177 * g_hash_table_destroy:
178 * @hash_table: a #GHashTable.
180 * Destroys the #GHashTable. If keys and/or values are dynamically
181 * allocated, you should either free them first or create the #GHashTable
182 * using g_hash_table_new_full(). In the latter case the destroy functions
183 * you supplied will be called on all keys and values before destroying
187 mono_g_hash_table_destroy (MonoGHashTable
*hash_table
)
191 g_return_if_fail (hash_table
!= NULL
);
193 for (i
= 0; i
< hash_table
->size
; i
++)
194 g_hash_nodes_destroy (hash_table
->nodes
[i
],
195 hash_table
->key_destroy_func
,
196 hash_table
->value_destroy_func
);
200 g_free (hash_table
->nodes
);
205 static inline MonoGHashNode
**
206 g_hash_table_lookup_node (MonoGHashTable
*hash_table
,
209 MonoGHashNode
**node
;
211 node
= &hash_table
->nodes
212 [(* hash_table
->hash_func
) (key
) % hash_table
->size
];
214 /* Hash table lookup needs to be fast.
215 * We therefore remove the extra conditional of testing
216 * whether to call the key_equal_func or not from
219 if (hash_table
->key_equal_func
)
220 while (*node
&& !(*hash_table
->key_equal_func
) ((*node
)->key
, key
))
221 node
= &(*node
)->next
;
223 while (*node
&& (*node
)->key
!= key
)
224 node
= &(*node
)->next
;
230 * g_hash_table_lookup:
231 * @hash_table: a #GHashTable.
232 * @key: the key to look up.
234 * Looks up a key in a #GHashTable.
236 * Return value: the associated value, or %NULL if the key is not found.
239 mono_g_hash_table_lookup (MonoGHashTable
*hash_table
,
244 g_return_val_if_fail (hash_table
!= NULL
, NULL
);
246 node
= *g_hash_table_lookup_node (hash_table
, key
);
248 return node
? node
->value
: NULL
;
252 * g_hash_table_lookup_extended:
253 * @hash_table: a #GHashTable.
254 * @lookup_key: the key to look up.
255 * @orig_key: returns the original key.
256 * @value: returns the value associated with the key.
258 * Looks up a key in the #GHashTable, returning the original key and the
259 * associated value and a #gboolean which is %TRUE if the key was found. This
260 * is useful if you need to free the memory allocated for the original key,
261 * for example before calling g_hash_table_remove().
263 * Return value: %TRUE if the key was found in the #GHashTable.
266 mono_g_hash_table_lookup_extended (MonoGHashTable
*hash_table
,
267 gconstpointer lookup_key
,
273 g_return_val_if_fail (hash_table
!= NULL
, FALSE
);
275 node
= *g_hash_table_lookup_node (hash_table
, lookup_key
);
280 *orig_key
= node
->key
;
282 *value
= node
->value
;
289 static inline MonoGHashNode
*
290 g_hash_node_new (gpointer key
,
293 MonoGHashNode
*hash_node
= NULL
;
296 if (node_free_list
) {
297 G_LOCK (g_hash_global
);
299 if (node_free_list
) {
300 hash_node
= node_free_list
;
301 node_free_list
= node_free_list
->next
;
303 G_UNLOCK (g_hash_global
);
306 hash_node
= GC_MALLOC (sizeof (MonoGHashNode
));
308 G_LOCK (g_hash_global
);
311 hash_node
= node_free_list
;
312 node_free_list
= node_free_list
->next
;
317 node_mem_chunk
= g_mem_chunk_new ("hash node mem chunk",
318 sizeof (MonoGHashNode
),
321 hash_node
= g_chunk_new (MonoGHashNode
, node_mem_chunk
);
323 G_UNLOCK (g_hash_global
);
326 hash_node
->key
= key
;
327 hash_node
->value
= value
;
328 hash_node
->next
= NULL
;
334 * g_hash_table_insert:
335 * @hash_table: a #GHashTable.
336 * @key: a key to insert.
337 * @value: the value to associate with the key.
339 * Inserts a new key and value into a #GHashTable.
341 * If the key already exists in the #GHashTable its current value is replaced
342 * with the new value. If you supplied a @value_destroy_func when creating the
343 * #GHashTable, the old value is freed using that function. If you supplied
344 * a @key_destroy_func when creating the #GHashTable, the passed key is freed
345 * using that function.
348 mono_g_hash_table_insert (MonoGHashTable
*hash_table
,
352 MonoGHashNode
**node
;
354 g_return_if_fail (hash_table
!= NULL
);
356 node
= g_hash_table_lookup_node (hash_table
, key
);
360 /* do not reset node->key in this place, keeping
361 * the old key is the intended behaviour.
362 * g_hash_table_replace() can be used instead.
365 /* free the passed key */
366 if (hash_table
->key_destroy_func
)
367 hash_table
->key_destroy_func (key
);
369 if (hash_table
->value_destroy_func
)
370 hash_table
->value_destroy_func ((*node
)->value
);
372 (*node
)->value
= value
;
376 *node
= g_hash_node_new (key
, value
);
377 hash_table
->nnodes
++;
378 G_HASH_TABLE_RESIZE (hash_table
);
383 * g_hash_table_replace:
384 * @hash_table: a #GHashTable.
385 * @key: a key to insert.
386 * @value: the value to associate with the key.
388 * Inserts a new key and value into a #GHashTable similar to
389 * g_hash_table_insert(). The difference is that if the key already exists
390 * in the #GHashTable, it gets replaced by the new key. If you supplied a
391 * @value_destroy_func when creating the #GHashTable, the old value is freed
392 * using that function. If you supplied a @key_destroy_func when creating the
393 * #GHashTable, the old key is freed using that function.
396 mono_g_hash_table_replace (MonoGHashTable
*hash_table
,
400 MonoGHashNode
**node
;
402 g_return_if_fail (hash_table
!= NULL
);
404 node
= g_hash_table_lookup_node (hash_table
, key
);
408 if (hash_table
->key_destroy_func
)
409 hash_table
->key_destroy_func ((*node
)->key
);
411 if (hash_table
->value_destroy_func
)
412 hash_table
->value_destroy_func ((*node
)->value
);
415 (*node
)->value
= value
;
419 *node
= g_hash_node_new (key
, value
);
420 hash_table
->nnodes
++;
421 G_HASH_TABLE_RESIZE (hash_table
);
426 * g_hash_table_remove:
427 * @hash_table: a #GHashTable.
428 * @key: the key to remove.
430 * Removes a key and its associated value from a #GHashTable.
432 * If the #GHashTable was created using g_hash_table_new_full(), the
433 * key and value are freed using the supplied destroy functions, otherwise
434 * you have to make sure that any dynamically allocated values are freed
437 * Return value: %TRUE if the key was found and removed from the #GHashTable.
440 mono_g_hash_table_remove (MonoGHashTable
*hash_table
,
443 MonoGHashNode
**node
, *dest
;
445 g_return_val_if_fail (hash_table
!= NULL
, FALSE
);
447 node
= g_hash_table_lookup_node (hash_table
, key
);
451 (*node
) = dest
->next
;
452 g_hash_node_destroy (dest
,
453 hash_table
->key_destroy_func
,
454 hash_table
->value_destroy_func
);
455 hash_table
->nnodes
--;
457 G_HASH_TABLE_RESIZE (hash_table
);
466 * g_hash_table_steal:
467 * @hash_table: a #GHashTable.
468 * @key: the key to remove.
470 * Removes a key and its associated value from a #GHashTable without
471 * calling the key and value destroy functions.
473 * Return value: %TRUE if the key was found and removed from the #GHashTable.
476 mono_g_hash_table_steal (MonoGHashTable
*hash_table
,
479 MonoGHashNode
**node
, *dest
;
481 g_return_val_if_fail (hash_table
!= NULL
, FALSE
);
483 node
= g_hash_table_lookup_node (hash_table
, key
);
487 (*node
) = dest
->next
;
488 g_hash_node_destroy (dest
, NULL
, NULL
);
489 hash_table
->nnodes
--;
491 G_HASH_TABLE_RESIZE (hash_table
);
500 * g_hash_table_foreach_remove:
501 * @hash_table: a #GHashTable.
502 * @func: the function to call for each key/value pair.
503 * @user_data: user data to pass to the function.
505 * Calls the given function for each key/value pair in the #GHashTable.
506 * If the function returns %TRUE, then the key/value pair is removed from the
507 * #GHashTable. If you supplied key or value destroy functions when creating
508 * the #GHashTable, they are used to free the memory allocated for the removed
511 * Return value: the number of key/value pairs removed.
514 mono_g_hash_table_foreach_remove (MonoGHashTable
*hash_table
,
518 g_return_val_if_fail (hash_table
!= NULL
, 0);
519 g_return_val_if_fail (func
!= NULL
, 0);
521 return g_hash_table_foreach_remove_or_steal (hash_table
, func
, user_data
, TRUE
);
525 * g_hash_table_foreach_steal:
526 * @hash_table: a #GHashTable.
527 * @func: the function to call for each key/value pair.
528 * @user_data: user data to pass to the function.
530 * Calls the given function for each key/value pair in the #GHashTable.
531 * If the function returns %TRUE, then the key/value pair is removed from the
532 * #GHashTable, but no key or value destroy functions are called.
534 * Return value: the number of key/value pairs removed.
537 mono_g_hash_table_foreach_steal (MonoGHashTable
*hash_table
,
541 g_return_val_if_fail (hash_table
!= NULL
, 0);
542 g_return_val_if_fail (func
!= NULL
, 0);
544 return g_hash_table_foreach_remove_or_steal (hash_table
, func
, user_data
, FALSE
);
548 g_hash_table_foreach_remove_or_steal (MonoGHashTable
*hash_table
,
553 MonoGHashNode
*node
, *prev
;
557 for (i
= 0; i
< hash_table
->size
; i
++)
563 for (node
= hash_table
->nodes
[i
]; node
; prev
= node
, node
= node
->next
)
565 if ((* func
) (node
->key
, node
->value
, user_data
))
569 hash_table
->nnodes
-= 1;
573 prev
->next
= node
->next
;
574 g_hash_node_destroy (node
,
575 notify
? hash_table
->key_destroy_func
: NULL
,
576 notify
? hash_table
->value_destroy_func
: NULL
);
581 hash_table
->nodes
[i
] = node
->next
;
582 g_hash_node_destroy (node
,
583 notify
? hash_table
->key_destroy_func
: NULL
,
584 notify
? hash_table
->value_destroy_func
: NULL
);
591 G_HASH_TABLE_RESIZE (hash_table
);
597 * g_hash_table_foreach:
598 * @hash_table: a #GHashTable.
599 * @func: the function to call for each key/value pair.
600 * @user_data: user data to pass to the function.
602 * Calls the given function for each of the key/value pairs in the
603 * #GHashTable. The function is passed the key and value of each
604 * pair, and the given @user_data parameter. The hash table may not
605 * be modified while iterating over it (you can't add/remove
606 * items). To remove all items matching a predicate, use
607 * g_hash_table_remove().
610 mono_g_hash_table_foreach (MonoGHashTable
*hash_table
,
617 g_return_if_fail (hash_table
!= NULL
);
618 g_return_if_fail (func
!= NULL
);
620 for (i
= 0; i
< hash_table
->size
; i
++)
621 for (node
= hash_table
->nodes
[i
]; node
; node
= node
->next
)
622 (* func
) (node
->key
, node
->value
, user_data
);
627 * @hash_table: a #GHashTable.
629 * Returns the number of elements contained in the #GHashTable.
631 * Return value: the number of key/value pairs in the #GHashTable.
634 mono_g_hash_table_size (MonoGHashTable
*hash_table
)
636 g_return_val_if_fail (hash_table
!= NULL
, 0);
638 return hash_table
->nnodes
;
642 * mono_g_hash_table_remap:
644 * Calls the given function for each key-value pair in the hash table,
645 * and replaces the value stored in the hash table by the value returned by
650 mono_g_hash_table_remap (MonoGHashTable
*hash_table
,
651 MonoGRemapperFunc func
,
657 g_return_if_fail (hash_table
!= NULL
);
658 g_return_if_fail (func
!= NULL
);
660 for (i
= 0; i
< hash_table
->size
; i
++)
661 for (node
= hash_table
->nodes
[i
]; node
; node
= node
->next
)
662 node
->value
= (* func
) (node
->key
, node
->value
, user_data
);
666 g_hash_table_resize (MonoGHashTable
*hash_table
)
668 MonoGHashNode
**new_nodes
;
675 new_size
= g_spaced_primes_closest (hash_table
->nnodes
);
676 new_size
= CLAMP (new_size
, HASH_TABLE_MIN_SIZE
, HASH_TABLE_MAX_SIZE
);
679 new_nodes
= GC_MALLOC (sizeof (MonoGHashNode
*) * new_size
);
681 new_nodes
= g_new0 (MonoGHashNode
*, new_size
);
684 for (i
= 0; i
< hash_table
->size
; i
++)
685 for (node
= hash_table
->nodes
[i
]; node
; node
= next
)
689 hash_val
= (* hash_table
->hash_func
) (node
->key
) % new_size
;
691 node
->next
= new_nodes
[hash_val
];
692 new_nodes
[hash_val
] = node
;
697 g_free (hash_table
->nodes
);
699 hash_table
->nodes
= new_nodes
;
700 hash_table
->size
= new_size
;
704 g_hash_node_destroy (MonoGHashNode
*hash_node
,
705 GDestroyNotify key_destroy_func
,
706 GDestroyNotify value_destroy_func
)
708 if (key_destroy_func
)
709 key_destroy_func (hash_node
->key
);
710 if (value_destroy_func
)
711 value_destroy_func (hash_node
->value
);
713 hash_node
->key
= NULL
;
714 hash_node
->value
= NULL
;
716 G_LOCK (g_hash_global
);
717 hash_node
->next
= node_free_list
;
718 node_free_list
= hash_node
;
719 G_UNLOCK (g_hash_global
);
723 g_hash_nodes_destroy (MonoGHashNode
*hash_node
,
724 GFreeFunc key_destroy_func
,
725 GFreeFunc value_destroy_func
)
729 MonoGHashNode
*node
= hash_node
;
733 if (key_destroy_func
)
734 key_destroy_func (node
->key
);
735 if (value_destroy_func
)
736 value_destroy_func (node
->value
);
744 if (key_destroy_func
)
745 key_destroy_func (node
->key
);
746 if (value_destroy_func
)
747 value_destroy_func (node
->value
);
752 G_LOCK (g_hash_global
);
753 node
->next
= node_free_list
;
754 node_free_list
= hash_node
;
755 G_UNLOCK (g_hash_global
);