-/* GLIB - Library of useful routines for C programming
- * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
+/*
+ * ghashtable.c: Hashtable implementation
*
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2 of the License, or (at your option) any later version.
+ * Author:
+ * Miguel de Icaza (miguel@novell.com)
*
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * Lesser General Public License for more details.
+ * (C) 2006 Novell, Inc.
*
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library; if not, write to the
- * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- * Boston, MA 02111-1307, USA.
- */
-
-/*
- * Modified by the GLib Team and others 1997-2000. See the AUTHORS
- * file for a list of people on the GLib Team. See the ChangeLog
- * files for a list of changes. These files are distributed with
- * GLib at ftp://ftp.gtk.org/pub/gtk/.
- */
-
-/*
- * MT safe
- */
-
-/*
- * Imported in mono cvs from version 1.32 of gnome cvs.
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+ * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+ * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+ * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/
-
-#ifdef HAVE_CONFIG_H
#include <config.h>
-#endif
-
+#include <stdio.h>
+#include <math.h>
#include <glib.h>
#include "mono-hash.h"
#include "metadata/gc-internal.h"
-#define HASH_TABLE_MIN_SIZE 11
-#define HASH_TABLE_MAX_SIZE 13845163
-
-typedef struct _MonoGHashNode MonoGHashNode;
+#ifdef HAVE_BOEHM_GC
+#define mg_new0(type,n) ((type *) GC_MALLOC(sizeof(type) * (n)))
+#define mg_new(type,n) ((type *) GC_MALLOC(sizeof(type) * (n)))
+#define mg_free(x) do { } while (0)
+#else
+#define mg_new0(x,n) g_new0(x,n)
+#define mg_new(type,n) g_new(type,n)
+#define mg_free(x) g_free(x)
+#endif
-struct _MonoGHashNode
-{
- gpointer key;
- gpointer value;
- MonoGHashNode *next;
-};
+typedef struct _Slot Slot;
-struct _MonoGHashTable
-{
- gint size;
- gint nnodes;
- MonoGHashNode **nodes;
- GHashFunc hash_func;
- GEqualFunc key_equal_func;
- GDestroyNotify key_destroy_func;
- GDestroyNotify value_destroy_func;
- MonoGHashGCType gc_type;
+struct _Slot {
+ gpointer key;
+ gpointer value;
+ Slot *next;
};
-#define G_HASH_TABLE_RESIZE(hash_table) \
- G_STMT_START { \
- if ((hash_table->size >= 3 * hash_table->nnodes && \
- hash_table->size > HASH_TABLE_MIN_SIZE) || \
- (3 * hash_table->size <= hash_table->nnodes && \
- hash_table->size < HASH_TABLE_MAX_SIZE)) \
- g_hash_table_resize (hash_table); \
- } G_STMT_END
-
-static void g_hash_table_resize (MonoGHashTable *hash_table);
-static MonoGHashNode** g_hash_table_lookup_node (MonoGHashTable *hash_table,
- gconstpointer key);
-static MonoGHashNode* g_hash_node_new (gpointer key,
- gpointer value,
- gint gc_type);
-static void g_hash_node_destroy (MonoGHashNode *hash_node,
- MonoGHashGCType type,
- GDestroyNotify key_destroy_func,
- GDestroyNotify value_destroy_func);
-static void g_hash_nodes_destroy (MonoGHashNode *hash_node,
- MonoGHashGCType type,
- GDestroyNotify key_destroy_func,
- GDestroyNotify value_destroy_func);
-static guint g_hash_table_foreach_remove_or_steal (MonoGHashTable *hash_table,
- GHRFunc func,
- gpointer user_data,
- gboolean notify);
+static gpointer KEYMARKER_REMOVED = &KEYMARKER_REMOVED;
-#ifdef HAVE_SGEN_GC
-static void mono_g_hash_mark (void *addr, MonoGCCopyFunc mark_func);
-#endif
+struct _MonoGHashTable {
+ GHashFunc hash_func;
+ GEqualFunc key_equal_func;
-G_LOCK_DEFINE_STATIC (g_hash_global);
+ Slot **table;
+ int table_size;
+ int in_use;
+ int threshold;
+ int last_rehash;
+ GDestroyNotify value_destroy_func, key_destroy_func;
+ MonoGHashGCType gc_type;
+};
-#if defined(HAVE_NULL_GC)
-static GMemChunk *node_mem_chunk = NULL;
-#endif
-#if defined(HAVE_SGEN_GC)
-static MonoGHashNode *node_free_lists [4] = {NULL};
-static void *hash_descr = NULL;
-static GMemChunk *node_mem_chunk = NULL;
-#else
-static void *node_gc_descs [4] = {NULL};
-static MonoGHashNode *node_free_lists [4] = {NULL};
-#endif
+static const int prime_tbl[] = {
+ 11, 19, 37, 73, 109, 163, 251, 367, 557, 823, 1237,
+ 1861, 2777, 4177, 6247, 9371, 14057, 21089, 31627,
+ 47431, 71143, 106721, 160073, 240101, 360163,
+ 540217, 810343, 1215497, 1823231, 2734867, 4102283,
+ 6153409, 9230113, 13845163
+};
#ifdef HAVE_SGEN_GC
-#define SET_NODE_KEY(node, gc_type, val) do { \
- gpointer __val = (val); \
- if (gc_type == MONO_HASH_KEY_GC || gc_type == MONO_HASH_KEY_VALUE_GC) \
- MONO_ROOT_SETREF ((node), key, __val); \
- else \
- (node)->key = __val; \
- } while (0)
-#define SET_NODE_VALUE(node, gc_type, val) do { \
- gpointer __val = (val); \
- if (gc_type == MONO_HASH_VALUE_GC || gc_type == MONO_HASH_KEY_VALUE_GC) \
- MONO_ROOT_SETREF ((node), value, __val); \
- else \
- (node)->value = __val; \
- } while (0)
-#else
-#define SET_NODE_KEY(node, gc_type, val) do { (node)->key = (val); } while (0)
-#define SET_NODE_VALUE(node, gc_type, val) do { (node)->value = (val); } while (0)
-#endif
+static void *table_hash_descr = NULL;
-/**
- * g_hash_table_new:
- * @hash_func: a function to create a hash value from a key.
- * Hash values are used to determine where keys are stored within the
- * #GHashTable data structure. The g_direct_hash(), g_int_hash() and
- * g_str_hash() functions are provided for some common types of keys.
- * If hash_func is %NULL, g_direct_hash() is used.
- * @key_equal_func: a function to check two keys for equality. This is
- * used when looking up keys in the #GHashTable. The g_direct_equal(),
- * g_int_equal() and g_str_equal() functions are provided for the most
- * common types of keys. If @key_equal_func is %NULL, keys are compared
- * directly in a similar fashion to g_direct_equal(), but without the
- * overhead of a function call.
- *
- * Creates a new #GHashTable.
- *
- * Return value: a new #GHashTable.
- **/
-MonoGHashTable*
-mono_g_hash_table_new (GHashFunc hash_func,
- GEqualFunc key_equal_func)
-{
- return mono_g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
-}
+static void mono_g_hash_mark (void *addr, MonoGCMarkFunc mark_func);
-MonoGHashTable*
-mono_g_hash_table_new_type (GHashFunc hash_func,
- GEqualFunc key_equal_func,
- MonoGHashGCType type)
+static Slot*
+new_slot (MonoGHashTable *hash)
{
- MonoGHashTable *table = mono_g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
- if (type == MONO_HASH_KEY_GC || type == MONO_HASH_KEY_VALUE_GC)
- g_assert (hash_func);
- table->gc_type = type;
-#if defined(HAVE_SGEN_GC)
- if (type < 0 || type > MONO_HASH_KEY_VALUE_GC)
- g_error ("wrong type for gc hashtable");
- /*
- * We use a user defined marking function to avoid having to register a GC root for
- * each hash node.
- */
- if (!hash_descr)
- hash_descr = mono_gc_make_root_descr_user (mono_g_hash_mark);
- if (type != MONO_HASH_CONSERVATIVE_GC)
- mono_gc_register_root_wbarrier ((char*)table, sizeof (MonoGHashTable), hash_descr);
-#elif defined(HAVE_BOEHM_GC)
- if (type < 0 || type > MONO_HASH_KEY_VALUE_GC)
- g_error ("wrong type for gc hashtable");
- if (!node_gc_descs [type] && type > MONO_HASH_CONSERVATIVE_GC) {
- gsize bmap = 0;
- if (type & MONO_HASH_KEY_GC)
- bmap |= 1; /* the first field in the node is the key */
- if (type & MONO_HASH_VALUE_GC)
- bmap |= 2; /* the second is the value */
- bmap |= 4; /* next */
- node_gc_descs [type] = mono_gc_make_descr_from_bitmap (&bmap, 3);
-
- MONO_GC_REGISTER_ROOT (node_free_lists [type]);
- }
-#endif
- return table;
+ if (hash->gc_type == MONO_HASH_CONSERVATIVE_GC)
+ return mono_gc_alloc_fixed (sizeof (Slot), NULL);
+ else
+ return mg_new (Slot, 1);
}
-
-
-/**
- * g_hash_table_new_full:
- * @hash_func: a function to create a hash value from a key.
- * @key_equal_func: a function to check two keys for equality.
- * @key_destroy_func: a function to free the memory allocated for the key
- * used when removing the entry from the #GHashTable or %NULL if you
- * don't want to supply such a function.
- * @value_destroy_func: a function to free the memory allocated for the
- * value used when removing the entry from the #GHashTable or %NULL if
- * you don't want to supply such a function.
- *
- * Creates a new #GHashTable like g_hash_table_new() and allows to specify
- * functions to free the memory allocated for the key and value that get
- * called when removing the entry from the #GHashTable.
- *
- * Return value: a new #GHashTable.
- **/
-MonoGHashTable*
-mono_g_hash_table_new_full (GHashFunc hash_func,
- GEqualFunc key_equal_func,
- GDestroyNotify key_destroy_func,
- GDestroyNotify value_destroy_func)
+static void
+free_slot (MonoGHashTable *hash, Slot *slot)
{
- MonoGHashTable *hash_table;
-#if HAVE_BOEHM_GC
- static gboolean inited = FALSE;
- if (!inited) {
- MONO_GC_REGISTER_ROOT (node_free_lists [0]);
- inited = TRUE;
- }
-
- hash_table = GC_MALLOC (sizeof (MonoGHashTable));
-#else
- hash_table = g_new (MonoGHashTable, 1);
-#endif
- hash_table->size = HASH_TABLE_MIN_SIZE;
- hash_table->nnodes = 0;
- hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
- hash_table->key_equal_func = key_equal_func == g_direct_equal ? NULL : key_equal_func;
- hash_table->key_destroy_func = key_destroy_func;
- hash_table->value_destroy_func = value_destroy_func;
-#if HAVE_BOEHM_GC
- hash_table->nodes = GC_MALLOC (sizeof (MonoGHashNode*) * hash_table->size);
-#else
- hash_table->nodes = g_new0 (MonoGHashNode*, hash_table->size);
-#endif
- hash_table->gc_type = 0;
-
- return hash_table;
+ if (hash->gc_type == MONO_HASH_CONSERVATIVE_GC)
+ mono_gc_free_fixed (slot);
+ else
+ mg_free (slot);
}
-
-/**
- * g_hash_table_destroy:
- * @hash_table: a #GHashTable.
- *
- * Destroys the #GHashTable. If keys and/or values are dynamically
- * allocated, you should either free them first or create the #GHashTable
- * using g_hash_table_new_full(). In the latter case the destroy functions
- * you supplied will be called on all keys and values before destroying
- * the #GHashTable.
- **/
-void
-mono_g_hash_table_destroy (MonoGHashTable *hash_table)
-{
- guint i;
-
- g_return_if_fail (hash_table != NULL);
-
- for (i = 0; i < hash_table->size; i++)
- g_hash_nodes_destroy (hash_table->nodes[i], hash_table->gc_type,
- hash_table->key_destroy_func,
- hash_table->value_destroy_func);
-
-#if HAVE_BOEHM_GC
#else
-#if HAVE_SGEN_GC
- mono_gc_deregister_root ((char*)hash_table);
-#endif
- g_free (hash_table->nodes);
- g_free (hash_table);
+#define new_slot(h) mg_new(Slot,1)
+#define free_slot(h,s) mg_free((s))
#endif
-}
-static inline MonoGHashNode**
-g_hash_table_lookup_node (MonoGHashTable *hash_table,
- gconstpointer key)
+#if UNUSED
+static gboolean
+test_prime (int x)
{
- MonoGHashNode **node;
-
- node = &hash_table->nodes
- [(* hash_table->hash_func) (key) % hash_table->size];
-
- /* Hash table lookup needs to be fast.
- * We therefore remove the extra conditional of testing
- * whether to call the key_equal_func or not from
- * the inner loop.
- */
- if (hash_table->key_equal_func)
- while (*node && !(*hash_table->key_equal_func) ((*node)->key, key))
- node = &(*node)->next;
- else
- while (*node && (*node)->key != key)
- node = &(*node)->next;
-
- return node;
+ if ((x & 1) != 0) {
+ int n;
+ for (n = 3; n< (int)sqrt (x); n += 2) {
+ if ((x % n) == 0)
+ return FALSE;
+ }
+ return TRUE;
+ }
+ // There is only one even prime - 2.
+ return (x == 2);
}
-/**
- * g_hash_table_lookup:
- * @hash_table: a #GHashTable.
- * @key: the key to look up.
- *
- * Looks up a key in a #GHashTable.
- *
- * Return value: the associated value, or %NULL if the key is not found.
- **/
-gpointer
-mono_g_hash_table_lookup (MonoGHashTable *hash_table,
- gconstpointer key)
+static int
+calc_prime (int x)
{
- MonoGHashNode *node;
-
- g_return_val_if_fail (hash_table != NULL, NULL);
-
- node = *g_hash_table_lookup_node (hash_table, key);
-
- return node ? node->value : NULL;
+ int i;
+
+ for (i = (x & (~1))-1; i< G_MAXINT32; i += 2) {
+ if (test_prime (i))
+ return i;
+ }
+ return x;
}
+#endif
-/**
- * g_hash_table_lookup_extended:
- * @hash_table: a #GHashTable.
- * @lookup_key: the key to look up.
- * @orig_key: returns the original key.
- * @value: returns the value associated with the key.
- *
- * Looks up a key in the #GHashTable, returning the original key and the
- * associated value and a #gboolean which is %TRUE if the key was found. This
- * is useful if you need to free the memory allocated for the original key,
- * for example before calling g_hash_table_remove().
- *
- * Return value: %TRUE if the key was found in the #GHashTable.
- **/
-gboolean
-mono_g_hash_table_lookup_extended (MonoGHashTable *hash_table,
- gconstpointer lookup_key,
- gpointer *orig_key,
- gpointer *value)
+MonoGHashTable *
+mono_g_hash_table_new_type (GHashFunc hash_func, GEqualFunc key_equal_func, MonoGHashGCType type)
{
- MonoGHashNode *node;
-
- g_return_val_if_fail (hash_table != NULL, FALSE);
-
- node = *g_hash_table_lookup_node (hash_table, lookup_key);
-
- if (node)
- {
- if (orig_key)
- *orig_key = node->key;
- if (value)
- *value = node->value;
- return TRUE;
- }
- else
- return FALSE;
-}
+ MonoGHashTable *hash = mono_g_hash_table_new (hash_func, key_equal_func);
-static inline MonoGHashNode*
-g_hash_node_new (gpointer key,
- gpointer value,
- gint gc_type)
-{
- MonoGHashNode *hash_node = NULL;
-
-#if HAVE_BOEHM_GC
- if (node_free_lists [gc_type]) {
- G_LOCK (g_hash_global);
-
- if (node_free_lists [gc_type]) {
- hash_node = node_free_lists [gc_type];
- node_free_lists [gc_type] = node_free_lists [gc_type]->next;
- }
- G_UNLOCK (g_hash_global);
- }
- if (!hash_node) {
- if (gc_type != MONO_HASH_CONSERVATIVE_GC) {
- //hash_node = GC_MALLOC (sizeof (MonoGHashNode));
- hash_node = GC_MALLOC_EXPLICITLY_TYPED (sizeof (MonoGHashNode), (GC_descr)node_gc_descs [gc_type]);
- } else {
- hash_node = GC_MALLOC (sizeof (MonoGHashNode));
- }
- }
-#elif defined(HAVE_SGEN_GC)
- if (node_free_lists [gc_type]) {
- G_LOCK (g_hash_global);
-
- if (node_free_lists [gc_type]) {
- hash_node = node_free_lists [gc_type];
- node_free_lists [gc_type] = node_free_lists [gc_type]->next;
- }
- G_UNLOCK (g_hash_global);
- }
- if (!hash_node) {
- if (gc_type != MONO_HASH_CONSERVATIVE_GC) {
- /*
- * Marking is handled by the marker function, no need to allocate GC visible
- * memory.
- */
- if (!node_mem_chunk)
- node_mem_chunk = g_mem_chunk_new ("hash node mem chunk",
- sizeof (MonoGHashNode),
- 1024, G_ALLOC_ONLY);
- hash_node = g_chunk_new (MonoGHashNode, node_mem_chunk);
- } else {
- hash_node = mono_gc_alloc_fixed (sizeof (MonoGHashNode), NULL);
- }
- }
-#else
- G_LOCK (g_hash_global);
- if (node_free_list)
- {
- hash_node = node_free_list;
- node_free_list = node_free_list->next;
- }
- else
- {
- if (!node_mem_chunk)
- node_mem_chunk = g_mem_chunk_new ("hash node mem chunk",
- sizeof (MonoGHashNode),
- 1024, G_ALLOC_ONLY);
-
- hash_node = g_chunk_new (MonoGHashNode, node_mem_chunk);
- }
- G_UNLOCK (g_hash_global);
+ hash->gc_type = type;
+
+#ifdef HAVE_SGEN_GC
+ if (type < 0 || type > MONO_HASH_KEY_VALUE_GC)
+ g_error ("wrong type for gc hashtable");
+ /*
+ * We use a user defined marking function to avoid having to register a GC root for
+ * each hash node.
+ */
+ if (!table_hash_descr)
+ table_hash_descr = mono_gc_make_root_descr_user (mono_g_hash_mark);
+ if (type != MONO_HASH_CONSERVATIVE_GC)
+ mono_gc_register_root_wbarrier ((char*)hash, sizeof (MonoGHashTable), table_hash_descr);
#endif
- SET_NODE_KEY (hash_node, gc_type, key);
- SET_NODE_VALUE (hash_node, gc_type, value);
- hash_node->next = NULL;
-
- return hash_node;
+ return hash;
}
-/**
- * g_hash_table_insert:
- * @hash_table: a #GHashTable.
- * @key: a key to insert.
- * @value: the value to associate with the key.
- *
- * Inserts a new key and value into a #GHashTable.
- *
- * If the key already exists in the #GHashTable its current value is replaced
- * with the new value. If you supplied a @value_destroy_func when creating the
- * #GHashTable, the old value is freed using that function. If you supplied
- * a @key_destroy_func when creating the #GHashTable, the passed key is freed
- * using that function.
- **/
-void
-mono_g_hash_table_insert (MonoGHashTable *hash_table,
- gpointer key,
- gpointer value)
+MonoGHashTable *
+mono_g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func)
{
- MonoGHashNode **node;
-
- g_return_if_fail (hash_table != NULL);
-
- node = g_hash_table_lookup_node (hash_table, key);
-
- if (*node)
- {
- /* do not reset node->key in this place, keeping
- * the old key is the intended behaviour.
- * g_hash_table_replace() can be used instead.
- */
-
- /* free the passed key */
- if (hash_table->key_destroy_func)
- hash_table->key_destroy_func (key);
-
- if (hash_table->value_destroy_func)
- hash_table->value_destroy_func ((*node)->value);
-
- SET_NODE_VALUE ((*node), hash_table->gc_type, value);
- }
- else
- {
- *node = g_hash_node_new (key, value, hash_table->gc_type);
- hash_table->nnodes++;
- G_HASH_TABLE_RESIZE (hash_table);
- }
+ MonoGHashTable *hash;
+
+ if (hash_func == NULL)
+ hash_func = g_direct_hash;
+ if (key_equal_func == NULL)
+ key_equal_func = g_direct_equal;
+ hash = mg_new0 (MonoGHashTable, 1);
+
+ hash->hash_func = hash_func;
+ hash->key_equal_func = key_equal_func;
+
+ hash->table_size = g_spaced_primes_closest (1);
+ hash->table = mg_new0 (Slot *, hash->table_size);
+ hash->last_rehash = hash->table_size;
+
+ return hash;
}
-/**
- * g_hash_table_replace:
- * @hash_table: a #GHashTable.
- * @key: a key to insert.
- * @value: the value to associate with the key.
- *
- * Inserts a new key and value into a #GHashTable similar to
- * g_hash_table_insert(). The difference is that if the key already exists
- * in the #GHashTable, it gets replaced by the new key. If you supplied a
- * @value_destroy_func when creating the #GHashTable, the old value is freed
- * using that function. If you supplied a @key_destroy_func when creating the
- * #GHashTable, the old key is freed using that function.
- **/
-void
-mono_g_hash_table_replace (MonoGHashTable *hash_table,
- gpointer key,
- gpointer value)
+MonoGHashTable *
+mono_g_hash_table_new_full (GHashFunc hash_func, GEqualFunc key_equal_func,
+ GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func)
{
- MonoGHashNode **node;
-
- g_return_if_fail (hash_table != NULL);
-
- node = g_hash_table_lookup_node (hash_table, key);
-
- if (*node)
- {
- if (hash_table->key_destroy_func)
- hash_table->key_destroy_func ((*node)->key);
-
- if (hash_table->value_destroy_func)
- hash_table->value_destroy_func ((*node)->value);
-
- SET_NODE_KEY ((*node), hash_table->gc_type, key);
- SET_NODE_VALUE ((*node), hash_table->gc_type, value);
- }
- else
- {
- *node = g_hash_node_new (key, value, hash_table->gc_type);
- hash_table->nnodes++;
- G_HASH_TABLE_RESIZE (hash_table);
- }
+ MonoGHashTable *hash = mono_g_hash_table_new (hash_func, key_equal_func);
+ if (hash == NULL)
+ return NULL;
+
+ hash->key_destroy_func = key_destroy_func;
+ hash->value_destroy_func = value_destroy_func;
+
+ return hash;
}
-/**
- * g_hash_table_remove:
- * @hash_table: a #GHashTable.
- * @key: the key to remove.
- *
- * Removes a key and its associated value from a #GHashTable.
- *
- * If the #GHashTable was created using g_hash_table_new_full(), the
- * key and value are freed using the supplied destroy functions, otherwise
- * you have to make sure that any dynamically allocated values are freed
- * yourself.
- *
- * Return value: %TRUE if the key was found and removed from the #GHashTable.
- **/
-gboolean
-mono_g_hash_table_remove (MonoGHashTable *hash_table,
- gconstpointer key)
+typedef struct {
+ MonoGHashTable *hash;
+ int new_size;
+ Slot **table;
+} RehashData;
+
+static void*
+do_rehash (void *_data)
{
- MonoGHashNode **node, *dest;
-
- g_return_val_if_fail (hash_table != NULL, FALSE);
-
- node = g_hash_table_lookup_node (hash_table, key);
- if (*node)
- {
- dest = *node;
- (*node) = dest->next;
- g_hash_node_destroy (dest, hash_table->gc_type,
- hash_table->key_destroy_func,
- hash_table->value_destroy_func);
- hash_table->nnodes--;
-
- G_HASH_TABLE_RESIZE (hash_table);
-
- return TRUE;
- }
-
- return FALSE;
+ RehashData *data = _data;
+ MonoGHashTable *hash = data->hash;
+ int current_size, i;
+ Slot **table;
+
+ /* printf ("Resizing diff=%d slots=%d\n", hash->in_use - hash->last_rehash, hash->table_size); */
+ hash->last_rehash = hash->table_size;
+ current_size = hash->table_size;
+ hash->table_size = data->new_size;
+ /* printf ("New size: %d\n", hash->table_size); */
+ table = hash->table;
+ hash->table = data->table;
+
+ for (i = 0; i < current_size; i++){
+ Slot *s, *next;
+
+ for (s = table [i]; s != NULL; s = next){
+ guint hashcode = ((*hash->hash_func) (s->key)) % hash->table_size;
+ next = s->next;
+
+ s->next = hash->table [hashcode];
+ hash->table [hashcode] = s;
+ }
+ }
+ return table;
}
-/**
- * g_hash_table_steal:
- * @hash_table: a #GHashTable.
- * @key: the key to remove.
- *
- * Removes a key and its associated value from a #GHashTable without
- * calling the key and value destroy functions.
- *
- * Return value: %TRUE if the key was found and removed from the #GHashTable.
- **/
-gboolean
-mono_g_hash_table_steal (MonoGHashTable *hash_table,
- gconstpointer key)
+static void
+rehash (MonoGHashTable *hash)
{
- MonoGHashNode **node, *dest;
-
- g_return_val_if_fail (hash_table != NULL, FALSE);
-
- node = g_hash_table_lookup_node (hash_table, key);
- if (*node)
- {
- dest = *node;
- (*node) = dest->next;
- g_hash_node_destroy (dest, hash_table->gc_type, NULL, NULL);
- hash_table->nnodes--;
-
- G_HASH_TABLE_RESIZE (hash_table);
-
- return TRUE;
- }
-
- return FALSE;
+ int diff = ABS (hash->last_rehash - hash->in_use);
+ RehashData data;
+ void *old_table;
+
+ /* These are the factors to play with to change the rehashing strategy */
+ /* I played with them with a large range, and could not really get */
+ /* something that was too good, maybe the tests are not that great */
+ if (!(diff * 0.75 > hash->table_size * 2))
+ return;
+
+ data.hash = hash;
+ data.new_size = g_spaced_primes_closest (hash->in_use);
+ data.table = mg_new0 (Slot *, data.new_size);
+
+ old_table = mono_gc_invoke_with_gc_lock (do_rehash, &data);
+ mg_free (old_table);
}
-/**
- * g_hash_table_foreach_remove:
- * @hash_table: a #GHashTable.
- * @func: the function to call for each key/value pair.
- * @user_data: user data to pass to the function.
- *
- * Calls the given function for each key/value pair in the #GHashTable.
- * If the function returns %TRUE, then the key/value pair is removed from the
- * #GHashTable. If you supplied key or value destroy functions when creating
- * the #GHashTable, they are used to free the memory allocated for the removed
- * keys and values.
- *
- * Return value: the number of key/value pairs removed.
- **/
guint
-mono_g_hash_table_foreach_remove (MonoGHashTable *hash_table,
- GHRFunc func,
- gpointer user_data)
+mono_g_hash_table_size (MonoGHashTable *hash)
{
- g_return_val_if_fail (hash_table != NULL, 0);
- g_return_val_if_fail (func != NULL, 0);
-
- return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
+ g_return_val_if_fail (hash != NULL, 0);
+
+ return hash->in_use;
}
-/**
- * g_hash_table_foreach_steal:
- * @hash_table: a #GHashTable.
- * @func: the function to call for each key/value pair.
- * @user_data: user data to pass to the function.
- *
- * Calls the given function for each key/value pair in the #GHashTable.
- * If the function returns %TRUE, then the key/value pair is removed from the
- * #GHashTable, but no key or value destroy functions are called.
- *
- * Return value: the number of key/value pairs removed.
- **/
-guint
-mono_g_hash_table_foreach_steal (MonoGHashTable *hash_table,
- GHRFunc func,
- gpointer user_data)
+gpointer
+mono_g_hash_table_lookup (MonoGHashTable *hash, gconstpointer key)
{
- g_return_val_if_fail (hash_table != NULL, 0);
- g_return_val_if_fail (func != NULL, 0);
-
- return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
+ gpointer orig_key, value;
+
+ if (mono_g_hash_table_lookup_extended (hash, key, &orig_key, &value))
+ return value;
+ else
+ return NULL;
}
-static guint
-g_hash_table_foreach_remove_or_steal (MonoGHashTable *hash_table,
- GHRFunc func,
- gpointer user_data,
- gboolean notify)
+gboolean
+mono_g_hash_table_lookup_extended (MonoGHashTable *hash, gconstpointer key, gpointer *orig_key, gpointer *value)
{
- MonoGHashNode *node, *prev;
- guint i;
- guint deleted = 0;
-
- for (i = 0; i < hash_table->size; i++)
- {
- restart:
-
- prev = NULL;
-
- for (node = hash_table->nodes[i]; node; prev = node, node = node->next)
- {
- if ((* func) (node->key, node->value, user_data))
- {
- deleted += 1;
-
- hash_table->nnodes -= 1;
-
- if (prev)
- {
- prev->next = node->next;
- g_hash_node_destroy (node, hash_table->gc_type,
- notify ? hash_table->key_destroy_func : NULL,
- notify ? hash_table->value_destroy_func : NULL);
- node = prev;
- }
- else
- {
- hash_table->nodes[i] = node->next;
- g_hash_node_destroy (node, hash_table->gc_type,
- notify ? hash_table->key_destroy_func : NULL,
- notify ? hash_table->value_destroy_func : NULL);
- goto restart;
+ GEqualFunc equal;
+ Slot *s;
+ guint hashcode;
+
+ g_return_val_if_fail (hash != NULL, FALSE);
+ equal = hash->key_equal_func;
+
+ hashcode = ((*hash->hash_func) (key)) % hash->table_size;
+
+ for (s = hash->table [hashcode]; s != NULL; s = s->next){
+ if ((*equal)(s->key, key)){
+ *orig_key = s->key;
+ *value = s->value;
+ return TRUE;
}
- }
}
- }
-
- G_HASH_TABLE_RESIZE (hash_table);
-
- return deleted;
+ return FALSE;
}
-/**
- * g_hash_table_foreach:
- * @hash_table: a #GHashTable.
- * @func: the function to call for each key/value pair.
- * @user_data: user data to pass to the function.
- *
- * Calls the given function for each of the key/value pairs in the
- * #GHashTable. The function is passed the key and value of each
- * pair, and the given @user_data parameter. The hash table may not
- * be modified while iterating over it (you can't add/remove
- * items). To remove all items matching a predicate, use
- * g_hash_table_remove().
- **/
void
-mono_g_hash_table_foreach (MonoGHashTable *hash_table,
- GHFunc func,
- gpointer user_data)
+mono_g_hash_table_foreach (MonoGHashTable *hash, GHFunc func, gpointer user_data)
{
- MonoGHashNode *node;
- gint i;
-
- g_return_if_fail (hash_table != NULL);
- g_return_if_fail (func != NULL);
-
- for (i = 0; i < hash_table->size; i++)
- for (node = hash_table->nodes[i]; node; node = node->next)
- (* func) (node->key, node->value, user_data);
+ int i;
+
+ g_return_if_fail (hash != NULL);
+ g_return_if_fail (func != NULL);
+
+ for (i = 0; i < hash->table_size; i++){
+ Slot *s;
+
+ for (s = hash->table [i]; s != NULL; s = s->next)
+ (*func)(s->key, s->value, user_data);
+ }
}
gpointer
-mono_g_hash_table_find (MonoGHashTable *hash_table, GHRFunc predicate, gpointer user_data)
+mono_g_hash_table_find (MonoGHashTable *hash, GHRFunc predicate, gpointer user_data)
{
int i;
- MonoGHashNode *node;
- g_return_val_if_fail (hash_table != NULL, NULL);
+ g_return_val_if_fail (hash != NULL, NULL);
g_return_val_if_fail (predicate != NULL, NULL);
- for (i = 0; i < hash_table->size; i++){
- for (node = hash_table->nodes[i]; node; node = node->next)
- if ((*predicate)(node->key, node->value, user_data))
- return node->value;
+ for (i = 0; i < hash->table_size; i++){
+ Slot *s;
+
+ for (s = hash->table [i]; s != NULL; s = s->next)
+ if ((*predicate)(s->key, s->value, user_data))
+ return s->value;
}
return NULL;
}
-/**
- * g_hash_table_size:
- * @hash_table: a #GHashTable.
- *
- * Returns the number of elements contained in the #GHashTable.
- *
- * Return value: the number of key/value pairs in the #GHashTable.
- **/
-guint
-mono_g_hash_table_size (MonoGHashTable *hash_table)
+gboolean
+mono_g_hash_table_remove (MonoGHashTable *hash, gconstpointer key)
{
- g_return_val_if_fail (hash_table != NULL, 0);
-
- return hash_table->nnodes;
+ GEqualFunc equal;
+ Slot *s, *last;
+ guint hashcode;
+
+ g_return_val_if_fail (hash != NULL, FALSE);
+ equal = hash->key_equal_func;
+
+ hashcode = ((*hash->hash_func)(key)) % hash->table_size;
+ last = NULL;
+ for (s = hash->table [hashcode]; s != NULL; s = s->next){
+ if ((*equal)(s->key, key)){
+ if (hash->key_destroy_func != NULL)
+ (*hash->key_destroy_func)(s->key);
+ if (hash->value_destroy_func != NULL)
+ (*hash->value_destroy_func)(s->value);
+ if (last == NULL)
+ hash->table [hashcode] = s->next;
+ else
+ last->next = s->next;
+ free_slot (hash, s);
+ hash->in_use--;
+ return TRUE;
+ }
+ last = s;
+ }
+ return FALSE;
}
-/**
- * mono_g_hash_table_remap:
- *
- * Calls the given function for each key-value pair in the hash table,
- * and replaces the value stored in the hash table by the value returned by
- * the function.
- *
- **/
-void
-mono_g_hash_table_remap (MonoGHashTable *hash_table,
- MonoGRemapperFunc func,
- gpointer user_data)
+guint
+mono_g_hash_table_foreach_remove (MonoGHashTable *hash, GHRFunc func, gpointer user_data)
{
- MonoGHashNode *node;
- gint i;
-
- g_return_if_fail (hash_table != NULL);
- g_return_if_fail (func != NULL);
-
- for (i = 0; i < hash_table->size; i++)
- for (node = hash_table->nodes[i]; node; node = node->next) {
- gpointer new_val = (* func) (node->key, node->value, user_data);
- SET_NODE_VALUE (node, hash_table->gc_type, new_val);
- }
+ int i;
+ int count = 0;
+
+ g_return_val_if_fail (hash != NULL, 0);
+ g_return_val_if_fail (func != NULL, 0);
+
+ for (i = 0; i < hash->table_size; i++){
+ Slot *s, *last;
+
+ last = NULL;
+ for (s = hash->table [i]; s != NULL; ){
+ if ((*func)(s->key, s->value, user_data)){
+ Slot *n;
+
+ if (hash->key_destroy_func != NULL)
+ (*hash->key_destroy_func)(s->key);
+ if (hash->value_destroy_func != NULL)
+ (*hash->value_destroy_func)(s->value);
+ if (last == NULL){
+ hash->table [i] = s->next;
+ n = s->next;
+ } else {
+ last->next = s->next;
+ n = last->next;
+ }
+ free_slot (hash, s);
+ hash->in_use--;
+ count++;
+ s = n;
+ } else {
+ last = s;
+ s = s->next;
+ }
+ }
+ }
+ if (count > 0)
+ rehash (hash);
+ return count;
}
-static void
-g_hash_table_resize (MonoGHashTable *hash_table)
+void
+mono_g_hash_table_destroy (MonoGHashTable *hash)
{
- MonoGHashNode **new_nodes;
- MonoGHashNode *node;
- MonoGHashNode *next;
- guint hash_val;
- gint new_size;
- gint i;
-
- new_size = g_spaced_primes_closest (hash_table->nnodes);
- new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
-
-#if HAVE_BOEHM_GC
- new_nodes = GC_MALLOC (sizeof (MonoGHashNode*) * new_size);
-#else
- new_nodes = g_new0 (MonoGHashNode*, new_size);
-#endif
-
- for (i = 0; i < hash_table->size; i++)
- for (node = hash_table->nodes[i]; node; node = next)
- {
- next = node->next;
-
- hash_val = (* hash_table->hash_func) (node->key) % new_size;
-
- node->next = new_nodes[hash_val];
- new_nodes[hash_val] = node;
- }
-
-#if HAVE_BOEHM_GC
-#else
- g_free (hash_table->nodes);
+ int i;
+
+ g_return_if_fail (hash != NULL);
+
+#ifdef HAVE_SGEN_GC
+ mono_gc_deregister_root ((char*)hash);
#endif
- hash_table->nodes = new_nodes;
- hash_table->size = new_size;
+
+ for (i = 0; i < hash->table_size; i++){
+ Slot *s, *next;
+
+ for (s = hash->table [i]; s != NULL; s = next){
+ next = s->next;
+
+ if (hash->key_destroy_func != NULL)
+ (*hash->key_destroy_func)(s->key);
+ if (hash->value_destroy_func != NULL)
+ (*hash->value_destroy_func)(s->value);
+ free_slot (hash, s);
+ }
+ }
+ mg_free (hash->table);
+ mg_free (hash);
}
static void
-g_hash_node_destroy (MonoGHashNode *hash_node,
- MonoGHashGCType type,
- GDestroyNotify key_destroy_func,
- GDestroyNotify value_destroy_func)
+mono_g_hash_table_insert_replace (MonoGHashTable *hash, gpointer key, gpointer value, gboolean replace)
{
- if (key_destroy_func)
- key_destroy_func (hash_node->key);
- if (value_destroy_func)
- value_destroy_func (hash_node->value);
-
- hash_node->key = NULL;
- hash_node->value = NULL;
-
- G_LOCK (g_hash_global);
-#if defined(HAVE_SGEN_GC) || defined(HAVE_BOEHM_GC)
- hash_node->next = node_free_lists [type];
- node_free_lists [type] = hash_node;
-#else
- hash_node->next = node_free_list;
- node_free_list = hash_node;
-#endif
- G_UNLOCK (g_hash_global);
+ guint hashcode;
+ Slot *s;
+ GEqualFunc equal;
+
+ g_return_if_fail (hash != NULL);
+
+ equal = hash->key_equal_func;
+ if (hash->in_use >= hash->threshold)
+ rehash (hash);
+
+ hashcode = ((*hash->hash_func) (key)) % hash->table_size;
+ for (s = hash->table [hashcode]; s != NULL; s = s->next){
+ if ((*equal) (s->key, key)){
+ if (replace){
+ if (hash->key_destroy_func != NULL)
+ (*hash->key_destroy_func)(s->key);
+ s->key = key;
+ }
+ if (hash->value_destroy_func != NULL)
+ (*hash->value_destroy_func) (s->value);
+ s->value = value;
+ return;
+ }
+ }
+ s = new_slot (hash);
+ s->key = key;
+ s->value = value;
+ s->next = hash->table [hashcode];
+ hash->table [hashcode] = s;
+ hash->in_use++;
}
-static void
-g_hash_nodes_destroy (MonoGHashNode *hash_node,
- MonoGHashGCType type,
- GFreeFunc key_destroy_func,
- GFreeFunc value_destroy_func)
+void
+mono_g_hash_table_insert (MonoGHashTable *h, gpointer k, gpointer v)
{
- if (hash_node)
- {
- MonoGHashNode *node = hash_node;
-
- while (node->next)
- {
- if (key_destroy_func)
- key_destroy_func (node->key);
- if (value_destroy_func)
- value_destroy_func (node->value);
-
- node->key = NULL;
- node->value = NULL;
-
- node = node->next;
- }
+ mono_g_hash_table_insert_replace (h, k, v, FALSE);
+}
- if (key_destroy_func)
- key_destroy_func (node->key);
- if (value_destroy_func)
- value_destroy_func (node->value);
-
- node->key = NULL;
- node->value = NULL;
-
- G_LOCK (g_hash_global);
-#if defined(HAVE_SGEN_GC) || defined(HAVE_BOEHM_GC)
- node->next = node_free_lists [type];
- node_free_lists [type] = hash_node;
-#else
- node->next = node_free_list;
- node_free_list = hash_node;
-#endif
- G_UNLOCK (g_hash_global);
- }
+void
+mono_g_hash_table_replace(MonoGHashTable *h, gpointer k, gpointer v)
+{
+ mono_g_hash_table_insert_replace (h, k, v, TRUE);
}
#ifdef HAVE_SGEN_GC
/* GC marker function */
static void
-mono_g_hash_mark (void *addr, MonoGCCopyFunc mark_func)
+mono_g_hash_mark (void *addr, MonoGCMarkFunc mark_func)
{
MonoGHashTable *table = (MonoGHashTable*)addr;
- MonoGHashNode *node;
+ Slot *node;
int i;
if (table->gc_type == MONO_HASH_KEY_GC) {
- for (i = 0; i < table->size; i++) {
- for (node = table->nodes [i]; node; node = node->next) {
+ for (i = 0; i < table->table_size; i++) {
+ for (node = table->table [i]; node; node = node->next) {
if (node->key)
- node->key = mark_func (node->key);
+ mark_func (&node->key);
}
}
} else if (table->gc_type == MONO_HASH_VALUE_GC) {
- for (i = 0; i < table->size; i++) {
- for (node = table->nodes [i]; node; node = node->next) {
+ for (i = 0; i < table->table_size; i++) {
+ for (node = table->table [i]; node; node = node->next) {
if (node->value)
- node->value = mark_func (node->value);
+ mark_func (&node->value);
}
}
} else if (table->gc_type == MONO_HASH_KEY_VALUE_GC) {
- for (i = 0; i < table->size; i++) {
- for (node = table->nodes [i]; node; node = node->next) {
+ for (i = 0; i < table->table_size; i++) {
+ for (node = table->table [i]; node; node = node->next) {
if (node->key)
- node->key = mark_func (node->key);
+ mark_func (&node->key);
if (node->value)
- node->value = mark_func (node->value);
+ mark_func (&node->value);
}
}
}
projects / mono.git / blobdiff