* Author:
* Miguel de Icaza (miguel@novell.com)
*
- * This is based on the System.Collections.Hashtable from Mono
- * implemented originally by Sergey Chaban (serge@wildwestsoftware.com)
- *
* (C) 2006 Novell, Inc.
+ *
+ * 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.
*/
#include <stdio.h>
-#include <glib.h>
#include <math.h>
+#include <glib.h>
-typedef struct {
+typedef struct _Slot Slot;
+
+struct _Slot {
gpointer key;
gpointer value;
-} Slot;
+ Slot *next;
+};
+
+static gpointer KEYMARKER_REMOVED = &KEYMARKER_REMOVED;
struct _GHashTable {
- GHashFunc hash_func;
- GEqualFunc key_equal_func;
+ GHashFunc hash_func;
+ GEqualFunc key_equal_func;
- float load_factor;
- Slot *table;
+ Slot **table;
int table_size;
- int threshold;
int in_use;
+ int threshold;
+ int last_rehash;
+ GDestroyNotify value_destroy_func, key_destroy_func;
};
-static int prime_tbl[] = {
+typedef struct {
+ GHashTable *ht;
+ int slot_index;
+ Slot *slot;
+} Iter;
+
+static const guint 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,
return x;
}
-static int
-to_prime (int x)
+guint
+g_spaced_primes_closest (guint x)
{
int i;
return calc_prime (x);
}
+GHashTable *
+g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func)
+{
+ GHashTable *hash;
+
+ if (hash_func == NULL)
+ hash_func = g_direct_hash;
+ if (key_equal_func == NULL)
+ key_equal_func = g_direct_equal;
+ hash = g_new0 (GHashTable, 1);
+
+ hash->hash_func = hash_func;
+ hash->key_equal_func = key_equal_func;
+
+ hash->table_size = g_spaced_primes_closest (1);
+ hash->table = g_new0 (Slot *, hash->table_size);
+ hash->last_rehash = hash->table_size;
+
+ return hash;
+}
+
+GHashTable *
+g_hash_table_new_full (GHashFunc hash_func, GEqualFunc key_equal_func,
+ GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func)
+{
+ GHashTable *hash = 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;
+}
+
+#if 0
+static void
+dump_hash_table (GHashTable *hash)
+{
+ int i;
+
+ for (i = 0; i < hash->table_size; i++) {
+ Slot *s;
+
+ for (s = hash->table [i]; s != NULL; s = s->next){
+ guint hashcode = (*hash->hash_func) (s->key);
+ guint slot = (hashcode) % hash->table_size;
+ printf ("key %p hash %x on slot %d correct slot %d tb size %d\n", s->key, hashcode, i, slot, hash->table_size);
+ }
+ }
+}
+#endif
+
+#ifdef SANITY_CHECK
static void
-adjust_threshold (GHashTable *hash)
+sanity_check (GHashTable *hash)
{
- int size = hash->table_size;
+ int i;
+
+ for (i = 0; i < hash->table_size; i++) {
+ Slot *s;
- hash->threshold = (int) hash->table_size * hash->load_factor;
- if (hash->threshold >= hash->table_size)
- hash->threshold = hash->table_size-1;
+ for (s = hash->table [i]; s != NULL; s = s->next){
+ guint hashcode = (*hash->hash_func) (s->key);
+ guint slot = (hashcode) % hash->table_size;
+ if (slot != i) {
+ dump_hashcode_func = 1;
+ hashcode = (*hash->hash_func) (s->key);
+ dump_hashcode_func = 0;
+ g_error ("Key %p (bucket %d) on invalid bucket %d (hashcode %x) (tb size %d)", s->key, slot, i, hashcode, hash->table_size);
+ }
+ }
+ }
}
+#else
+
+#define sanity_check(HASH) do {}while(0)
+
+#endif
+
+static void
+do_rehash (GHashTable *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 = g_spaced_primes_closest (hash->in_use);
+ /* printf ("New size: %d\n", hash->table_size); */
+ table = hash->table;
+ hash->table = g_new0 (Slot *, hash->table_size);
+ 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;
+ }
+ }
+ g_free (table);
+}
+
static void
-set_table (GHashTable *hash, Slot *table)
+rehash (GHashTable *hash)
{
- hash->table = table;
- adjust_threshold (hash);
+ int diff = ABS (hash->last_rehash - hash->in_use);
+
+ /* 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;
+ do_rehash (hash);
+ sanity_check (hash);
}
-GHashTable *
-g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func)
+void
+g_hash_table_insert_replace (GHashTable *hash, gpointer key, gpointer value, gboolean replace)
+{
+ guint hashcode;
+ Slot *s;
+ GEqualFunc equal;
+
+ g_return_if_fail (hash != NULL);
+ sanity_check (hash);
+
+ 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;
+ sanity_check (hash);
+ return;
+ }
+ }
+ s = g_new (Slot, 1);
+ s->key = key;
+ s->value = value;
+ s->next = hash->table [hashcode];
+ hash->table [hashcode] = s;
+ hash->in_use++;
+ sanity_check (hash);
+}
+
+GList*
+g_hash_table_get_keys (GHashTable *hash)
{
- GHashTable *table = g_new0 (GHashTable, 1);
+ GHashTableIter iter;
+ GList *rv = NULL;
+ gpointer key;
- table->hash_func = hash_func;
- table->key_equal_func = key_equal_func;
+ g_hash_table_iter_init (&iter, hash);
+
+ while (g_hash_table_iter_next (&iter, &key, NULL))
+ rv = g_list_prepend (rv, key);
+
+ return g_list_reverse (rv);
+}
+
+GList*
+g_hash_table_get_values (GHashTable *hash)
+{
+ GHashTableIter iter;
+ GList *rv = NULL;
+ gpointer value;
- table->load_factor = 0.75;
+ g_hash_table_iter_init (&iter, hash);
+
+ while (g_hash_table_iter_next (&iter, NULL, &value))
+ rv = g_list_prepend (rv, value);
+
+ return g_list_reverse (rv);
+}
+
+
+guint
+g_hash_table_size (GHashTable *hash)
+{
+ g_return_val_if_fail (hash != NULL, 0);
- table->table_size = to_prime (1);
- set_table (table, g_new0 (Slot, table->table_size));
+ return hash->in_use;
+}
+
+gpointer
+g_hash_table_lookup (GHashTable *hash, gconstpointer key)
+{
+ gpointer orig_key, value;
+
+ if (g_hash_table_lookup_extended (hash, key, &orig_key, &value))
+ return value;
+ else
+ return NULL;
+}
+
+gboolean
+g_hash_table_lookup_extended (GHashTable *hash, gconstpointer key, gpointer *orig_key, gpointer *value)
+{
+ GEqualFunc equal;
+ Slot *s;
+ guint hashcode;
+
+ g_return_val_if_fail (hash != NULL, FALSE);
+ sanity_check (hash);
+ 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)){
+ if (orig_key)
+ *orig_key = s->key;
+ if (value)
+ *value = s->value;
+ return TRUE;
+ }
+ }
+ return FALSE;
+}
+
+void
+g_hash_table_foreach (GHashTable *hash, GHFunc func, gpointer 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
+g_hash_table_find (GHashTable *hash, GHRFunc predicate, gpointer user_data)
+{
+ int i;
- return table;
+ g_return_val_if_fail (hash != NULL, NULL);
+ g_return_val_if_fail (predicate != NULL, NULL);
+
+ 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;
}
void
-g_hash_table_insert (GHashTable *hash, gpointer key, gpointer value)
+g_hash_table_remove_all (GHashTable *hash)
{
- Slot *table, *entry;
- guint size, spot, step;
- int h, free_index, i;
+ int i;
g_return_if_fail (hash != NULL);
+
+ for (i = 0; i < hash->table_size; i++){
+ Slot *s;
+
+ while (hash->table [i]) {
+ s = hash->table [i];
+ g_hash_table_remove (hash, s->key);
+ }
+ }
+}
+
+gboolean
+g_hash_table_remove (GHashTable *hash, gconstpointer key)
+{
+ GEqualFunc equal;
+ Slot *s, *last;
+ guint hashcode;
- if (hash->in_use >= hash->threshold)
+ g_return_val_if_fail (hash != NULL, FALSE);
+ sanity_check (hash);
+ 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;
+ g_free (s);
+ hash->in_use--;
+ sanity_check (hash);
+ return TRUE;
+ }
+ last = s;
+ }
+ sanity_check (hash);
+ return FALSE;
+}
+
+guint
+g_hash_table_foreach_remove (GHashTable *hash, GHRFunc func, gpointer user_data)
+{
+ int i;
+ int count = 0;
+
+ g_return_val_if_fail (hash != NULL, 0);
+ g_return_val_if_fail (func != NULL, 0);
+
+ sanity_check (hash);
+ 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;
+ }
+ g_free (s);
+ hash->in_use--;
+ count++;
+ s = n;
+ } else {
+ last = s;
+ s = s->next;
+ }
+ }
+ }
+ sanity_check (hash);
+ if (count > 0)
rehash (hash);
+ return count;
+}
+
+gboolean
+g_hash_table_steal (GHashTable *hash, gconstpointer key)
+{
+ GEqualFunc equal;
+ Slot *s, *last;
+ guint hashcode;
+
+ g_return_val_if_fail (hash != NULL, FALSE);
+ sanity_check (hash);
+ 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 (last == NULL)
+ hash->table [hashcode] = s->next;
+ else
+ last->next = s->next;
+ g_free (s);
+ hash->in_use--;
+ sanity_check (hash);
+ return TRUE;
+ }
+ last = s;
+ }
+ sanity_check (hash);
+ return FALSE;
+
+}
- size = (guint) hash->table_size;
- h = get_hash (key) & G_MAXINT32;
- spot = (guint) h;
- step = (guint) ((spot>>5)+1) % (size-1)+1;
+guint
+g_hash_table_foreach_steal (GHashTable *hash, GHRFunc func, gpointer user_data)
+{
+ int i;
+ int count = 0;
+
+ g_return_val_if_fail (hash != NULL, 0);
+ g_return_val_if_fail (func != NULL, 0);
- table = hash->table;
- free_index = -1;
+ sanity_check (hash);
+ 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;
- for (i = 0; i < size; i++){
- int indx = (int) (spot % size);
- entry = &table [indx];
+ if (last == NULL){
+ hash->table [i] = s->next;
+ n = s->next;
+ } else {
+ last->next = s->next;
+ n = last->next;
+ }
+ g_free (s);
+ hash->in_use--;
+ count++;
+ s = n;
+ } else {
+ last = s;
+ s = s->next;
+ }
+ }
}
+ sanity_check (hash);
+ if (count > 0)
+ rehash (hash);
+ return count;
+}
+
+void
+g_hash_table_destroy (GHashTable *hash)
+{
+ int i;
+
+ g_return_if_fail (hash != NULL);
+
+ 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);
+ g_free (s);
+ }
+ }
+ g_free (hash->table);
+ g_free (hash);
+}
+
+void
+g_hash_table_print_stats (GHashTable *table)
+{
+ int i, max_chain_index, chain_size, max_chain_size;
+ Slot *node;
+
+ max_chain_size = 0;
+ max_chain_index = -1;
+ for (i = 0; i < table->table_size; i++) {
+ chain_size = 0;
+ for (node = table->table [i]; node; node = node->next)
+ chain_size ++;
+ if (chain_size > max_chain_size) {
+ max_chain_size = chain_size;
+ max_chain_index = i;
+ }
+ }
+
+ printf ("Size: %d Table Size: %d Max Chain Length: %d at %d\n", table->in_use, table->table_size, max_chain_size, max_chain_index);
+}
+
+void
+g_hash_table_iter_init (GHashTableIter *it, GHashTable *hash_table)
+{
+ Iter *iter = (Iter*)it;
+
+ memset (iter, 0, sizeof (Iter));
+ iter->ht = hash_table;
+ iter->slot_index = -1;
+}
+
+gboolean g_hash_table_iter_next (GHashTableIter *it, gpointer *key, gpointer *value)
+{
+ Iter *iter = (Iter*)it;
+
+ GHashTable *hash = iter->ht;
+
+ g_assert (iter->slot_index != -2);
+ g_assert (sizeof (Iter) <= sizeof (GHashTableIter));
+
+ if (!iter->slot) {
+ while (TRUE) {
+ iter->slot_index ++;
+ if (iter->slot_index >= hash->table_size) {
+ iter->slot_index = -2;
+ return FALSE;
+ }
+ if (hash->table [iter->slot_index])
+ break;
+ }
+ iter->slot = hash->table [iter->slot_index];
+ }
+
+ if (key)
+ *key = iter->slot->key;
+ if (value)
+ *value = iter->slot->value;
+ iter->slot = iter->slot->next;
+
+ return TRUE;
+}
+
+gboolean
+g_direct_equal (gconstpointer v1, gconstpointer v2)
+{
+ return v1 == v2;
+}
+
+guint
+g_direct_hash (gconstpointer v1)
+{
+ return GPOINTER_TO_UINT (v1);
+}
+
+gboolean
+g_int_equal (gconstpointer v1, gconstpointer v2)
+{
+ return *(gint *)v1 == *(gint *)v2;
+}
+
+guint
+g_int_hash (gconstpointer v1)
+{
+ return *(guint *)v1;
+}
+
+gboolean
+g_str_equal (gconstpointer v1, gconstpointer v2)
+{
+ return strcmp (v1, v2) == 0;
+}
+
+guint
+g_str_hash (gconstpointer v1)
+{
+ guint hash = 0;
+ char *p = (char *) v1;
+
+ while (*p++)
+ hash = (hash << 5) - (hash + *p);
+
+ return hash;
}
projects / mono.git / blobdiff