- 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;
+ slot = mono_g_hash_table_find_slot (hash, key);
+
+ if (!hash->keys [slot])
+ return FALSE;
+
+ if (hash->key_destroy_func)
+ (*hash->key_destroy_func)(hash->keys [slot]);
+ hash->keys [slot] = NULL;
+ if (hash->value_destroy_func)
+ (*hash->value_destroy_func)(hash->values [slot]);
+ hash->values [slot] = NULL;
+ hash->in_use--;
+
+ /*
+ * When we insert in the hashtable, if the required position is occupied we
+ * consecutively try out following positions. In order to be able to find
+ * if a key exists or not in the array (without traversing the entire hash)
+ * we maintain the constraint that there can be no free slots between two
+ * entries that are hashed to the same position. This means that, at search
+ * time, when we encounter a free slot we can stop looking for collissions.
+ * Similarly, at remove time, we need to shift all following slots to their
+ * normal slot, until we reach an empty slot.
+ */
+ last_clear_slot = slot;
+ slot = (slot + 1) % hash->table_size;
+ while (hash->keys [slot]) {
+ guint hashcode = ((*hash->hash_func)(hash->keys [slot])) % hash->table_size;
+ /*
+ * We try to move the current element to last_clear_slot, but only if
+ * it brings it closer to its normal position (hashcode)
+ */
+ if ((last_clear_slot < slot && (hashcode > slot || hashcode <= last_clear_slot)) ||
+ (last_clear_slot > slot && (hashcode > slot && hashcode <= last_clear_slot))) {
+ mono_g_hash_table_key_store (hash, last_clear_slot, hash->keys [slot]);
+ mono_g_hash_table_value_store (hash, last_clear_slot, hash->values [slot]);
+ hash->keys [slot] = NULL;
+ hash->values [slot] = NULL;
+ last_clear_slot = slot;