Author: miguel
Date: 2006-08-21 01:55:48 -0400 (Mon, 21 Aug 2006)
New Revision: 64121
Modified:
trunk/mono/eglib/ChangeLog
trunk/mono/eglib/src/ghashtable.c
trunk/mono/eglib/src/glib.h
trunk/mono/eglib/test/hashtable.c
Log:
2006-08-21 Miguel de Icaza <[EMAIL PROTECTED]>
* src/glib.h (g_hash_table_new_full): Add missing prototype.
Replace g_free(x) with plain free, so it can be used as a function
argument.
Add ABS
* src/ghashtable.c: Add rehashing.
* test/hashtable.c: Add a bunch of extra tests.
Modified: trunk/mono/eglib/ChangeLog
===================================================================
--- trunk/mono/eglib/ChangeLog 2006-08-21 05:11:02 UTC (rev 64120)
+++ trunk/mono/eglib/ChangeLog 2006-08-21 05:55:48 UTC (rev 64121)
@@ -1,5 +1,14 @@
2006-08-21 Miguel de Icaza <[EMAIL PROTECTED]>
+ * src/glib.h (g_hash_table_new_full): Add missing prototype.
+ Replace g_free(x) with plain free, so it can be used as a function
+ argument.
+ Add ABS
+
+ * src/ghashtable.c: Add rehashing.
+
+ * test/hashtable.c: Add a bunch of extra tests.
+
* src/goutput.c: Fix g_log so it actually formats the data.
* src/ghashtable.c (g_hash_table_new): The glib test suite
Modified: trunk/mono/eglib/src/ghashtable.c
===================================================================
--- trunk/mono/eglib/src/ghashtable.c 2006-08-21 05:11:02 UTC (rev 64120)
+++ trunk/mono/eglib/src/ghashtable.c 2006-08-21 05:55:48 UTC (rev 64121)
@@ -47,6 +47,7 @@
int table_size;
int in_use;
int threshold;
+ int last_rehash;
GDestroyNotify value_destroy_func, key_destroy_func;
};
@@ -97,16 +98,6 @@
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)
{
@@ -123,7 +114,7 @@
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;
}
@@ -143,9 +134,42 @@
}
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
*/
+ if (!(diff * 0.75 > hash->table_size * 2))
+ return;
+ do_rehash (hash);
}
void
Modified: trunk/mono/eglib/src/glib.h
===================================================================
--- trunk/mono/eglib/src/glib.h 2006-08-21 05:11:02 UTC (rev 64120)
+++ trunk/mono/eglib/src/glib.h 2006-08-21 05:55:48 UTC (rev 64121)
@@ -50,6 +50,8 @@
#define G_STMT_START do
#define G_STMT_END while (0)
+#define ABS(a,b) (((a)>(b)) ? ((a)-(b)) : ((b)-(a)))
+
#define G_STRUCT_OFFSET(p_type,field) \
((long) (((char *) (&(((p_type)NULL)->field))) - ((char *) NULL)))
@@ -59,7 +61,6 @@
*/
#define g_new(type,size) ((type *) malloc (sizeof (type) * (size)))
#define g_new0(type,size) ((type *) calloc (sizeof (type), (size)))
-#define g_free(obj) free (obj)
#define g_realloc(obj,size) realloc((obj), (size))
#define g_strdup(x) strdup(x)
#define g_malloc(x) malloc(x)
@@ -69,6 +70,7 @@
#define g_memmove(dest,src,len) memmove (dest, src, len)
#define g_renew(struct_type, mem, n_structs) realloc (mem, sizeof
(struct_type) * n_structs)
#define g_alloca(size) alloca (size)
+#define g_free free
gpointer g_memdup (gconstpointer mem, guint byte_size);
@@ -101,6 +103,8 @@
typedef gboolean (*GEqualFunc) (gconstpointer a, gconstpointer b);
GHashTable *g_hash_table_new (GHashFunc hash_func, GEqualFunc
key_equal_func);
+GHashTable *g_hash_table_new_full (GHashFunc hash_func, GEqualFunc
key_equal_func,
+ GDestroyNotify key_destroy_func,
GDestroyNotify value_destroy_func);
void g_hash_table_insert_replace (GHashTable *hash, gpointer key,
gpointer value, gboolean replace);
guint g_hash_table_size (GHashTable *hash);
gpointer g_hash_table_lookup (GHashTable *hash, gconstpointer
key);
Modified: trunk/mono/eglib/test/hashtable.c
===================================================================
--- trunk/mono/eglib/test/hashtable.c 2006-08-21 05:11:02 UTC (rev 64120)
+++ trunk/mono/eglib/test/hashtable.c 2006-08-21 05:55:48 UTC (rev 64121)
@@ -50,9 +50,92 @@
return OK;
}
+RESULT hash_default (void)
+{
+ GHashTable *hash = g_hash_table_new (NULL, NULL);
+
+ if (hash == NULL)
+ return FAILED ("g_hash_table_new should return a valid hash");
+
+ return NULL;
+}
+
+RESULT
+hash_null_lookup (void)
+{
+ GHashTable *hash = g_hash_table_new (NULL, NULL);
+ gpointer ok, ov;
+
+ g_hash_table_insert (hash, NULL, GINT_TO_POINTER (1));
+ g_hash_table_insert (hash, GINT_TO_POINTER(1), GINT_TO_POINTER(2));
+
+ if (!g_hash_table_lookup_extended (hash, NULL, &ok, &ov))
+ return FAILED ("Did not find the NULL");
+ if (ok != NULL)
+ return FAILED ("Incorrect key found");
+ if (ov != GINT_TO_POINTER (1))
+ return FAILED ("Got wrong value %p\n", ov);
+
+ if (!g_hash_table_lookup_extended (hash, GINT_TO_POINTER(1), &ok, &ov))
+ return FAILED ("Did not find the 1");
+ if (ok != GINT_TO_POINTER(1))
+ return FAILED ("Incorrect key found");
+ if (ov != GINT_TO_POINTER (2))
+ return FAILED ("Got wrong value %p\n", ov);
+
+ g_hash_table_destroy (hash);
+
+ return NULL;
+}
+
+static void
+counter (gpointer key, gpointer value, gpointer user_data)
+{
+ int *counter = (int *) user_data;
+
+ (*counter)++;
+}
+
+RESULT hash_grow (void)
+{
+ GHashTable *hash = g_hash_table_new_full (g_str_hash, g_str_equal,
g_free, g_free);
+ int i, count = 0;
+
+ for (i = 0; i < 1000; i++)
+ g_hash_table_insert (hash, g_strdup_printf ("%d", i),
g_strdup_printf ("x-%d", i));
+
+ for (i = 0; i < 1000; i++){
+ char buffer [30];
+ gpointer value;
+
+ sprintf (buffer, "%d", i);
+
+ value = g_hash_table_lookup (hash, buffer);
+ sprintf (buffer, "x-%d", i);
+ if (strcmp (value, buffer) != 0){
+ return FAILED ("Failed to lookup the key %d, the value
was %s\n", i, value);
+ }
+ }
+
+ if (g_hash_table_size (hash) != 1000)
+ return FAILED ("Did not find 1000 elements on the hash, found
%d\n", g_hash_table_size (hash));
+
+ /* Now do the manual count, lets not trust the internals */
+ g_hash_table_foreach (hash, counter, &count);
+ if (count != 1000){
+ return FAILED ("Foreach count is not 1000");
+ }
+
+ g_hash_table_destroy (hash);
+ return NULL;
+}
+
static Test hashtable_tests [] = {
{"hash_t1", hash_t1},
{"hash_t2", hash_t2},
+ {"hash_grow", hash_grow},
+ {"hash_default", hash_default},
+ {"hash_null_lookup", hash_null_lookup},
{NULL, NULL}
};
_______________________________________________
Mono-patches maillist - [email protected]
http://lists.ximian.com/mailman/listinfo/mono-patches
