2006-10-05 Miguel de Icaza <miguel@novell.com>

[mono.git] / eglib / src / ghashtable.c

diff --git a/eglib/src/ghashtable.c b/eglib/src/ghashtable.c
index aad450a4788f7aa1bf1204b37266ae7438a07dc4..e675ba4708fc465e410c6f37ed4fcba3a1a62eb0 100644 (file)
--- a/eglib/src/ghashtable.c
+++ b/eglib/src/ghashtable.c
@@ -47,6 +47,7 @@ struct _GHashTable {
        int   table_size;
        int   in_use;
        int   threshold;
+       int   last_rehash;
        GDestroyNotify value_destroy_func, key_destroy_func;
 };
 
@@ -97,24 +98,15 @@ to_prime (int x)
        return calc_prime (x);
 }
 
-static void
-adjust_threshold (GHashTable *hash)
-{
-       hash->threshold = (int) hash->table_size * 0.75;
-       if (hash->threshold >= hash->table_size)
-               hash->threshold = hash->table_size-1;
-       if (hash->threshold == 0)
-               hash->threshold = 1;
-}
-       
 GHashTable *
 g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func)
 {
        GHashTable *hash;
 
-       g_return_val_if_fail (hash_func != NULL, NULL);
-       g_return_val_if_fail (key_equal_func != NULL, NULL);
-                         
+       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;
@@ -122,7 +114,7 @@ g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func)
 
        hash->table_size = to_prime (1);
        hash->table = g_new0 (Slot *, hash->table_size);
-       adjust_threshold (hash);
+       hash->last_rehash = hash->table_size;
        
        return hash;
 }
@@ -141,10 +133,45 @@ g_hash_table_new_full (GHashFunc hash_func, GEqualFunc key_equal_func,
        return hash;
 }
 
+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 = to_prime (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);
+}
+
 void
 rehash (GHashTable *hash)
 {
-       /* FIXME */
+       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);
 }
 
 void
@@ -211,7 +238,8 @@ g_hash_table_lookup_extended (GHashTable *hash, gconstpointer key, gpointer *ori
        g_return_val_if_fail (hash != NULL, FALSE);
        equal = hash->key_equal_func;
 
-       hashcode = ((*hash->hash_func) (key)) % hash->table_size;       
+       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;
@@ -260,26 +288,29 @@ gboolean
 g_hash_table_remove (GHashTable *hash, gconstpointer key)
 {
        GEqualFunc equal;
-       Slot *s, **last;
+       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 = &hash->table [hashcode];
-       for (s = *last; s != NULL; s = s->next){
+       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);
-                       *last = s->next;
+                       if (last == NULL)
+                               hash->table [hashcode] = s->next;
+                       else
+                               last->next = s->next;
                        g_free (s);
                        hash->in_use--;
                        return TRUE;
                }
-               last = &s;
+               last = s;
        }
        return FALSE;
 }
@@ -294,19 +325,31 @@ g_hash_table_foreach_remove (GHashTable *hash, GHRFunc func, gpointer user_data)
        g_return_val_if_fail (func != NULL, 0);
 
        for (i = 0; i < hash->table_size; i++){
-               Slot *s, **last;
+               Slot *s, *last;
 
-               last = &hash->table [i];
-               for (s = hash->table [i]; s != NULL; s = s->next){
+               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);
-                               *last = s->next;
+                               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;
                        }
                }
        }