ralloc_free(ht);
}
+/**
+ * Deletes all entries of the given hash table without deleting the table
+ * itself or changing its structure.
+ *
+ * If delete_function is passed, it gets called on each entry present.
+ */
+void
+_mesa_hash_table_clear(struct hash_table *ht,
+ void (*delete_function)(struct hash_entry *entry))
+{
+ struct hash_entry *entry;
+
+ for (entry = ht->table; entry != ht->table + ht->size; entry++) {
+ if (entry->key == NULL)
+ continue;
+
+ if (delete_function != NULL && entry->key != ht->deleted_key)
+ delete_function(entry);
+
+ entry->key = NULL;
+ }
+
+ ht->entries = 0;
+ ht->deleted_entries = 0;
+}
+
/** Sets the value of the key pointer used for deleted entries in the table.
*
* The assumption is that usually keys are actual pointers, so we use a
const void *key, void *data);
static void
-_mesa_hash_table_rehash(struct hash_table *ht, int new_size_index)
+_mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index)
{
struct hash_table old_ht;
struct hash_entry *table, *entry;
const void *key, void *data)
{
uint32_t start_hash_address, hash_address;
+ struct hash_entry *available_entry = NULL;
+
+ assert(key != NULL);
if (ht->entries >= ht->max_entries) {
_mesa_hash_table_rehash(ht, ht->size_index + 1);
uint32_t double_hash;
if (!entry_is_present(ht, entry)) {
- if (entry_is_deleted(ht, entry))
- ht->deleted_entries--;
- entry->hash = hash;
- entry->key = key;
- entry->data = data;
- 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
* required to avoid memory leaks, perform a search
* before inserting.
*/
- if (entry->hash == hash &&
+ if (!entry_is_deleted(ht, entry) &&
+ entry->hash == hash &&
ht->key_equals_function(key, entry->key)) {
entry->key = key;
entry->data = data;
hash_address = (hash_address + double_hash) % ht->size;
} while (hash_address != start_hash_address);
+ if (available_entry) {
+ if (entry_is_deleted(ht, available_entry))
+ ht->deleted_entries--;
+ available_entry->hash = hash;
+ available_entry->key = key;
+ available_entry->data = data;
+ ht->entries++;
+ return available_entry;
+ }
+
/* We could hit here if a required resize failed. An unchecked-malloc
* application could ignore this result.
*/
}
struct hash_entry *
-_mesa_hash_table_insert_with_hash(struct hash_table *ht, uint32_t hash,
- const void *key, void *data)
+_mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash,
+ const void *key, void *data)
{
assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key));
return hash_table_insert(ht, hash, key, data);
uint32_t
_mesa_hash_data(const void *data, size_t size)
{
- uint32_t hash = 2166136261ul;
- const uint8_t *bytes = data;
-
- while (size-- != 0) {
- hash ^= *bytes;
- hash = hash * 0x01000193;
- bytes++;
- }
-
- return hash;
+ return _mesa_fnv32_1a_accumulate_block(_mesa_fnv32_1a_offset_bias,
+ data, size);
}
/** FNV-1a string hash implementation */
uint32_t
_mesa_hash_string(const char *key)
{
- uint32_t hash = 2166136261ul;
+ uint32_t hash = _mesa_fnv32_1a_offset_bias;
while (*key != 0) {
- hash ^= *key;
- hash = hash * 0x01000193;
+ hash = _mesa_fnv32_1a_accumulate(hash, *key);
key++;
}