#include <stdlib.h>
#include <assert.h>
+#include <string.h>
+#include "hash_table.h"
#include "macros.h"
#include "ralloc.h"
#include "set.h"
* free to avoid exponential performance degradation as the hash table fills
*/
-uint32_t deleted_key_value;
-const void *deleted_key = &deleted_key_value;
+static const uint32_t deleted_key_value;
+static const void *deleted_key = &deleted_key_value;
static const struct {
uint32_t max_entries, size, rehash;
return ht;
}
+struct set *
+_mesa_set_clone(struct set *set, void *dst_mem_ctx)
+{
+ struct set *clone;
+
+ clone = ralloc(dst_mem_ctx, struct set);
+ if (clone == NULL)
+ return NULL;
+
+ memcpy(clone, set, sizeof(struct set));
+
+ clone->table = ralloc_array(clone, struct set_entry, clone->size);
+ if (clone->table == NULL) {
+ ralloc_free(clone);
+ return NULL;
+ }
+
+ memcpy(clone->table, set->table, clone->size * sizeof(struct set_entry));
+
+ return clone;
+}
+
/**
* Frees the given set.
*
return;
if (delete_function) {
- struct set_entry *entry;
-
set_foreach (ht, entry) {
delete_function(entry);
}
ralloc_free(ht);
}
+/**
+ * Clears all values from the given set.
+ *
+ * If delete_function is passed, it gets called on each entry present before
+ * the set is cleared.
+ */
+void
+_mesa_set_clear(struct set *set, void (*delete_function)(struct set_entry *entry))
+{
+ if (!set)
+ return;
+
+ set_foreach (set, entry) {
+ if (delete_function)
+ delete_function(entry);
+ entry->key = deleted_key;
+ }
+
+ set->entries = set->deleted_entries = 0;
+}
+
/**
* Finds a set entry with the given key and hash of that key.
*
}
static struct set_entry *
-set_add(struct set *ht, uint32_t hash, const void *key);
+set_add(struct set *ht, uint32_t hash, const void *key, bool *replaced);
static void
set_rehash(struct set *ht, unsigned new_size_index)
{
struct set old_ht;
- struct set_entry *table, *entry;
+ struct set_entry *table;
if (new_size_index >= ARRAY_SIZE(hash_sizes))
return;
ht->entries = 0;
ht->deleted_entries = 0;
- for (entry = old_ht.table;
- entry != old_ht.table + old_ht.size;
- entry++) {
- if (entry_is_present(entry)) {
- set_add(ht, entry->hash, entry->key);
- }
+ set_foreach(&old_ht, entry) {
+ set_add(ht, entry->hash, entry->key, NULL);
}
ralloc_free(old_ht.table);
* so previously found hash_entries are no longer valid after this function.
*/
static struct set_entry *
-set_add(struct set *ht, uint32_t hash, const void *key)
+set_add(struct set *ht, uint32_t hash, const void *key, bool *replaced)
{
uint32_t hash_address;
struct set_entry *available_entry = NULL;
* 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;
+ if (replaced)
+ *replaced = true;
return entry;
}
available_entry->hash = hash;
available_entry->key = key;
ht->entries++;
+ if (replaced)
+ *replaced = false;
return available_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);
+ return set_add(set, set->key_hash_function(key), key, NULL);
}
struct set_entry *
{
assert(set->key_hash_function == NULL ||
hash == set->key_hash_function(key));
- return set_add(set, hash, key);
+ return set_add(set, hash, key, NULL);
+}
+
+struct set_entry *
+_mesa_set_search_and_add(struct set *set, const void *key, bool *replaced)
+{
+ assert(set->key_hash_function);
+ return set_add(set, set->key_hash_function(key), key, replaced);
+}
+
+struct set_entry *
+_mesa_set_search_and_add_pre_hashed(struct set *set, uint32_t hash,
+ const void *key, bool *replaced)
+{
+ assert(set->key_hash_function == NULL ||
+ hash == set->key_hash_function(key));
+ return set_add(set, hash, key, replaced);
}
/**
ht->deleted_entries++;
}
+/**
+ * Removes the entry with the corresponding key, if exists.
+ */
+void
+_mesa_set_remove_key(struct set *set, const void *key)
+{
+ _mesa_set_remove(set, _mesa_set_search(set, key));
+}
+
/**
* This function is an iterator over the hash table.
*
return NULL;
}
+
+/**
+ * Helper to create a set with pointer keys.
+ */
+struct set *
+_mesa_pointer_set_create(void *mem_ctx)
+{
+ return _mesa_set_create(mem_ctx, _mesa_hash_pointer,
+ _mesa_key_pointer_equal);
+}