X-Git-Url: http://wien.tomnetworks.com/gitweb/?a=blobdiff_plain;f=eglib%2Fsrc%2Fghashtable.c;h=fbe079336c5bbaab4f6ded01afc4c08b2a9dba08;hb=a2b8537da3747d7eb506ecdbb91a8a2bc35a2248;hp=e675ba4708fc465e410c6f37ed4fcba3a1a62eb0;hpb=89d0ba3968d36576553e0f483b0c69465f94e8ae;p=mono.git

diff --git a/eglib/src/ghashtable.c b/eglib/src/ghashtable.c
index e675ba4708f..fbe079336c5 100644
--- a/eglib/src/ghashtable.c
+++ b/eglib/src/ghashtable.c
@@ -51,7 +51,13 @@ struct _GHashTable {
 	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,
@@ -86,8 +92,8 @@ calc_prime (int x)
 	return x;
 }
 
-static int
-to_prime (int x)
+guint
+g_spaced_primes_closest (guint x)
 {
 	int i;
 	
@@ -112,7 +118,7 @@ g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func)
 	hash->hash_func = hash_func;
 	hash->key_equal_func = key_equal_func;
 
-	hash->table_size = to_prime (1);
+	hash->table_size = g_spaced_primes_closest (1);
 	hash->table = g_new0 (Slot *, hash->table_size);
 	hash->last_rehash = hash->table_size;
 	
@@ -133,7 +139,52 @@ g_hash_table_new_full (GHashFunc hash_func, GEqualFunc key_equal_func,
 	return hash;
 }
 
-void
+#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
+sanity_check (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;
+			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;
@@ -142,7 +193,7 @@ do_rehash (GHashTable *hash)
 	/* 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);
+	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);
@@ -161,10 +212,10 @@ do_rehash (GHashTable *hash)
 	g_free (table);
 }
 
-void
+static void
 rehash (GHashTable *hash)
 {
-	int diff = ABS (hash->last_rehash, hash->in_use);
+	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 */
@@ -172,6 +223,7 @@ rehash (GHashTable *hash)
 	if (!(diff * 0.75 > hash->table_size * 2))
 		return;
 	do_rehash (hash);
+	sanity_check (hash);
 }
 
 void
@@ -182,6 +234,7 @@ g_hash_table_insert_replace (GHashTable *hash, gpointer key, gpointer value, gbo
 	GEqualFunc equal;
 	
 	g_return_if_fail (hash != NULL);
+	sanity_check (hash);
 
 	equal = hash->key_equal_func;
 	if (hash->in_use >= hash->threshold)
@@ -198,6 +251,7 @@ g_hash_table_insert_replace (GHashTable *hash, gpointer key, gpointer value, gbo
 			if (hash->value_destroy_func != NULL)
 				(*hash->value_destroy_func) (s->value);
 			s->value = value;
+			sanity_check (hash);
 			return;
 		}
 	}
@@ -207,6 +261,7 @@ g_hash_table_insert_replace (GHashTable *hash, gpointer key, gpointer value, gbo
 	s->next = hash->table [hashcode];
 	hash->table [hashcode] = s;
 	hash->in_use++;
+	sanity_check (hash);
 }
 
 guint
@@ -236,6 +291,7 @@ g_hash_table_lookup_extended (GHashTable *hash, gconstpointer key, gpointer *ori
 	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;
@@ -284,6 +340,23 @@ g_hash_table_find (GHashTable *hash, GHRFunc predicate, gpointer user_data)
 	return NULL;
 }
 
+void
+g_hash_table_remove_all (GHashTable *hash)
+{
+	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)
 {
@@ -292,6 +365,7 @@ g_hash_table_remove (GHashTable *hash, gconstpointer key)
 	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;
@@ -308,10 +382,12 @@ g_hash_table_remove (GHashTable *hash, gconstpointer key)
 				last->next = s->next;
 			g_free (s);
 			hash->in_use--;
+			sanity_check (hash);
 			return TRUE;
 		}
 		last = s;
 	}
+	sanity_check (hash);
 	return FALSE;
 }
 
@@ -324,6 +400,7 @@ g_hash_table_foreach_remove (GHashTable *hash, GHRFunc func, gpointer user_data)
 	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;
 
@@ -353,6 +430,48 @@ g_hash_table_foreach_remove (GHashTable *hash, GHRFunc func, gpointer user_data)
 			}
 		}
 	}
+	sanity_check (hash);
+	if (count > 0)
+		rehash (hash);
+	return count;
+}
+
+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);
+
+	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 (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;
@@ -383,6 +502,68 @@ g_hash_table_destroy (GHashTable *hash)
 	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)
 {
@@ -398,13 +579,13 @@ g_direct_hash (gconstpointer v1)
 gboolean
 g_int_equal (gconstpointer v1, gconstpointer v2)
 {
-	return GPOINTER_TO_INT (v1) == GPOINTER_TO_INT (v2);
+	return *(gint *)v1 == *(gint *)v2;
 }
 
 guint
 g_int_hash (gconstpointer v1)
 {
-	return GPOINTER_TO_UINT(v1);
+	return *(guint *)v1;
 }
 
 gboolean