util/set: Add a search_and_add function

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

diff --git a/src/util/set.c b/src/util/set.c
index d71f771807f48913dff867e22c5f9da148dc338e..2fd54a71a6f04a7fcb9d7c472d6421f957a8014d 100644 (file)
--- a/src/util/set.c
+++ b/src/util/set.c
@@ -34,7 +34,9 @@
 
 #include <stdlib.h>
 #include <assert.h>
+#include <string.h>
 
+#include "hash_table.h"
 #include "macros.h"
 #include "ralloc.h"
 #include "set.h"
@@ -132,6 +134,28 @@ _mesa_set_create(void *mem_ctx,
    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.
  *
@@ -145,8 +169,6 @@ _mesa_set_destroy(struct set *ht, void (*delete_function)(struct set_entry *entr
       return;
 
    if (delete_function) {
-      struct set_entry *entry;
-
       set_foreach (ht, entry) {
          delete_function(entry);
       }
@@ -155,6 +177,27 @@ _mesa_set_destroy(struct set *ht, void (*delete_function)(struct set_entry *entr
    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.
  *
@@ -204,13 +247,13 @@ _mesa_set_search_pre_hashed(const struct set *set, uint32_t hash,
 }
 
 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;
@@ -231,7 +274,7 @@ set_rehash(struct set *ht, unsigned new_size_index)
    ht->deleted_entries = 0;
 
    set_foreach(&old_ht, entry) {
-      set_add(ht, entry->hash, entry->key);
+      set_add(ht, entry->hash, entry->key, NULL);
    }
 
    ralloc_free(old_ht.table);
@@ -244,7 +287,7 @@ set_rehash(struct set *ht, unsigned new_size_index)
  * 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;
@@ -282,6 +325,8 @@ set_add(struct set *ht, uint32_t hash, const void *key)
           entry->hash == hash &&
           ht->key_equals_function(key, entry->key)) {
          entry->key = key;
+         if (replaced)
+            *replaced = true;
          return entry;
       }
 
@@ -296,6 +341,8 @@ set_add(struct set *ht, uint32_t hash, const void *key)
       available_entry->hash = hash;
       available_entry->key = key;
       ht->entries++;
+      if (replaced)
+         *replaced = false;
       return available_entry;
    }
 
@@ -309,7 +356,7 @@ 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);
+   return set_add(set, set->key_hash_function(key), key, NULL);
 }
 
 struct set_entry *
@@ -317,7 +364,23 @@ _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);
+   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);
 }
 
 /**
@@ -337,6 +400,15 @@ _mesa_set_remove(struct set *ht, struct set_entry *entry)
    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.
  *
@@ -386,3 +458,13 @@ _mesa_set_random_entry(struct set *ht,
 
    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);
+}