*/
#include <stdlib.h>
+#include <assert.h>
#include "macros.h"
#include "ralloc.h"
struct set *
_mesa_set_create(void *mem_ctx,
+ uint32_t (*key_hash_function)(const void *key),
bool (*key_equals_function)(const void *a,
const void *b))
{
ht->size = hash_sizes[ht->size_index].size;
ht->rehash = hash_sizes[ht->size_index].rehash;
ht->max_entries = hash_sizes[ht->size_index].max_entries;
+ ht->key_hash_function = key_hash_function;
ht->key_equals_function = key_equals_function;
ht->table = rzalloc_array(ht, struct set_entry, ht->size);
ht->entries = 0;
*
* Returns NULL if no entry is found.
*/
-struct set_entry *
-_mesa_set_search(const struct set *ht, uint32_t hash, const void *key)
+static struct set_entry *
+set_search(const struct set *ht, uint32_t hash, const void *key)
{
uint32_t hash_address;
return NULL;
}
+struct set_entry *
+_mesa_set_search(const struct set *set, const void *key)
+{
+ assert(set->key_hash_function);
+ return set_search(set, set->key_hash_function(key), key);
+}
+
+struct set_entry *
+_mesa_set_search_pre_hashed(const struct set *set, uint32_t hash,
+ const void *key)
+{
+ assert(set->key_hash_function == NULL ||
+ hash == set->key_hash_function(key));
+ return set_search(set, hash, key);
+}
+
+static struct set_entry *
+set_add(struct set *ht, uint32_t hash, const void *key);
+
static void
-set_rehash(struct set *ht, int new_size_index)
+set_rehash(struct set *ht, unsigned new_size_index)
{
struct set old_ht;
struct set_entry *table, *entry;
entry != old_ht.table + old_ht.size;
entry++) {
if (entry_is_present(entry)) {
- _mesa_set_add(ht, entry->hash, entry->key);
+ set_add(ht, entry->hash, entry->key);
}
}
* Note that insertion may rearrange the table on a resize or rehash,
* so previously found hash_entries are no longer valid after this function.
*/
-struct set_entry *
-_mesa_set_add(struct set *ht, uint32_t hash, const void *key)
+static struct set_entry *
+set_add(struct set *ht, uint32_t hash, const void *key)
{
uint32_t hash_address;
+ struct set_entry *available_entry = NULL;
if (ht->entries >= ht->max_entries) {
set_rehash(ht, ht->size_index + 1);
uint32_t double_hash;
if (!entry_is_present(entry)) {
- if (entry_is_deleted(entry))
- ht->deleted_entries--;
- entry->hash = hash;
- entry->key = key;
- ht->entries++;
- return entry;
+ /* Stash the first available entry we find */
+ if (available_entry == NULL)
+ available_entry = entry;
+ if (entry_is_free(entry))
+ break;
}
/* Implement replacement when another insert happens
* If freeing of old keys is required to avoid memory leaks,
* perform a search before inserting.
*/
- if (entry->hash == hash &&
+ if (!entry_is_deleted(entry) &&
+ entry->hash == hash &&
ht->key_equals_function(key, entry->key)) {
entry->key = key;
return entry;
hash_address = (hash_address + double_hash) % ht->size;
} while (hash_address != hash % ht->size);
+ if (available_entry) {
+ if (entry_is_deleted(available_entry))
+ ht->deleted_entries--;
+ available_entry->hash = hash;
+ available_entry->key = key;
+ ht->entries++;
+ return available_entry;
+ }
+
/* We could hit here if a required resize failed. An unchecked-malloc
* application could ignore this result.
*/
return NULL;
}
+struct set_entry *
+_mesa_set_add(struct set *set, const void *key)
+{
+ assert(set->key_hash_function);
+ return set_add(set, set->key_hash_function(key), key);
+}
+
+struct set_entry *
+_mesa_set_add_pre_hashed(struct set *set, uint32_t hash, const void *key)
+{
+ assert(set->key_hash_function == NULL ||
+ hash == set->key_hash_function(key));
+ return set_add(set, hash, key);
+}
+
/**
* This function deletes the given hash table entry.
*