util: Helper to create sets and hashes with pointer keys

[mesa.git] / src / util / hash_table.c

diff --git a/src/util/hash_table.c b/src/util/hash_table.c
index a9d442d6808093de7efc5fa2b04d3542bacc2b27..57a5f247edcec89be20374b4dfbed320c9f36390 100644 (file)
--- a/src/util/hash_table.c
+++ b/src/util/hash_table.c
@@ -110,6 +110,27 @@ entry_is_present(const struct hash_table *ht, struct hash_entry *entry)
    return entry->key != NULL && entry->key != ht->deleted_key;
 }
 
+bool
+_mesa_hash_table_init(struct hash_table *ht,
+                      void *mem_ctx,
+                      uint32_t (*key_hash_function)(const void *key),
+                      bool (*key_equals_function)(const void *a,
+                                                  const void *b))
+{
+   ht->size_index = 0;
+   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(mem_ctx, struct hash_entry, ht->size);
+   ht->entries = 0;
+   ht->deleted_entries = 0;
+   ht->deleted_key = &deleted_key_value;
+
+   return ht->table != NULL;
+}
+
 struct hash_table *
 _mesa_hash_table_create(void *mem_ctx,
                         uint32_t (*key_hash_function)(const void *key),
@@ -118,26 +139,40 @@ _mesa_hash_table_create(void *mem_ctx,
 {
    struct hash_table *ht;
 
+   /* mem_ctx is used to allocate the hash table, but the hash table is used
+    * to allocate all of the suballocations.
+    */
    ht = ralloc(mem_ctx, struct hash_table);
    if (ht == NULL)
       return NULL;
 
-   ht->size_index = 0;
-   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 hash_entry, ht->size);
-   ht->entries = 0;
-   ht->deleted_entries = 0;
-   ht->deleted_key = &deleted_key_value;
+   if (!_mesa_hash_table_init(ht, ht, key_hash_function, key_equals_function)) {
+      ralloc_free(ht);
+      return NULL;
+   }
+
+   return ht;
+}
 
+struct hash_table *
+_mesa_hash_table_clone(struct hash_table *src, void *dst_mem_ctx)
+{
+   struct hash_table *ht;
+
+   ht = ralloc(dst_mem_ctx, struct hash_table);
+   if (ht == NULL)
+      return NULL;
+
+   memcpy(ht, src, sizeof(struct hash_table));
+
+   ht->table = ralloc_array(ht, struct hash_entry, ht->size);
    if (ht->table == NULL) {
       ralloc_free(ht);
       return NULL;
    }
 
+   memcpy(ht->table, src->table, ht->size * sizeof(struct hash_entry));
+
    return ht;
 }
 
@@ -155,8 +190,6 @@ _mesa_hash_table_destroy(struct hash_table *ht,
       return;
 
    if (delete_function) {
-      struct hash_entry *entry;
-
       hash_table_foreach(ht, entry) {
          delete_function(entry);
       }
@@ -262,12 +295,12 @@ static void
 _mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index)
 {
    struct hash_table old_ht;
-   struct hash_entry *table, *entry;
+   struct hash_entry *table;
 
    if (new_size_index >= ARRAY_SIZE(hash_sizes))
       return;
 
-   table = rzalloc_array(ht, struct hash_entry,
+   table = rzalloc_array(ralloc_parent(ht->table), struct hash_entry,
                          hash_sizes[new_size_index].size);
    if (table == NULL)
       return;
@@ -398,6 +431,15 @@ _mesa_hash_table_remove(struct hash_table *ht,
    ht->deleted_entries++;
 }
 
+/**
+ * Removes the entry with the corresponding key, if exists.
+ */
+void _mesa_hash_table_remove_key(struct hash_table *ht,
+                                 const void *key)
+{
+   _mesa_hash_table_remove(ht, _mesa_hash_table_search(ht, key));
+}
+
 /**
  * This function is an iterator over the hash table.
  *
@@ -476,9 +518,10 @@ _mesa_hash_data(const void *data, size_t size)
 
 /** FNV-1a string hash implementation */
 uint32_t
-_mesa_hash_string(const char *key)
+_mesa_hash_string(const void *_key)
 {
    uint32_t hash = _mesa_fnv32_1a_offset_bias;
+   const char *key = _key;
 
    while (*key != 0) {
       hash = _mesa_fnv32_1a_accumulate(hash, *key);
@@ -504,6 +547,16 @@ _mesa_key_pointer_equal(const void *a, const void *b)
    return a == b;
 }
 
+/**
+ * Helper to create a hash table with pointer keys.
+ */
+struct hash_table *
+_mesa_pointer_hash_table_create(void *mem_ctx)
+{
+   return _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
+                                  _mesa_key_pointer_equal);
+}
+
 /**
  * Hash table wrapper which supports 64-bit keys.
  *
@@ -588,7 +641,7 @@ _mesa_hash_table_u64_insert(struct hash_table_u64 *ht, uint64_t key,
    }
 
    if (sizeof(void *) == 8) {
-      _mesa_hash_table_insert(ht->table, (void *)key, data);
+      _mesa_hash_table_insert(ht->table, (void *)(uintptr_t)key, data);
    } else {
       struct hash_key_u64 *_key = CALLOC_STRUCT(hash_key_u64);
 
@@ -604,7 +657,7 @@ static struct hash_entry *
 hash_table_u64_search(struct hash_table_u64 *ht, uint64_t key)
 {
    if (sizeof(void *) == 8) {
-      return _mesa_hash_table_search(ht->table, (void *)key);
+      return _mesa_hash_table_search(ht->table, (void *)(uintptr_t)key);
    } else {
       struct hash_key_u64 _key = { .value = key };
       return _mesa_hash_table_search(ht->table, &_key);