Mesa (master): util/set: add macro for destructively iterating set entries
GitLab Mirror
gitlab-mirror at kemper.freedesktop.org
Wed Apr 7 23:24:34 UTC 2021
Module: Mesa
Branch: master
Commit: 759cc914501fa13d0093cfe8a9b0fc32e36bfb5c
URL: http://cgit.freedesktop.org/mesa/mesa/commit/?id=759cc914501fa13d0093cfe8a9b0fc32e36bfb5c
Author: Mike Blumenkrantz <michael.blumenkrantz at gmail.com>
Date: Tue Jan 12 14:49:48 2021 -0500
util/set: add macro for destructively iterating set entries
a common usage for sets is for tracking exactly one instance of a pointer
for a given period of time, after which the set's entries are purged and it
is reused
this macro enables the purge phase of such usage to reset the table to a
pristine state, avoiding future rehashing due to ballooning of deleted entries
Reviewed-by: Adam Jackson <ajax at redhat.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/8498>
---
src/util/set.c | 21 +++++++++++++++++++++
src/util/set.h | 11 +++++++++++
src/util/tests/set/set_test.cpp | 14 ++++++++++++++
3 files changed, 46 insertions(+)
diff --git a/src/util/set.c b/src/util/set.c
index db244669185..37bd689e81a 100644
--- a/src/util/set.c
+++ b/src/util/set.c
@@ -560,6 +560,27 @@ _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 set when no deleted entries are present.
+ *
+ * Pass in NULL for the first entry, as in the start of a for loop.
+ */
+struct set_entry *
+_mesa_set_next_entry_unsafe(const struct set *ht, struct set_entry *entry)
+{
+ assert(!ht->deleted_entries);
+ if (!ht->entries)
+ return NULL;
+ if (entry == NULL)
+ entry = ht->table;
+ else
+ entry = entry + 1;
+ if (entry != ht->table + ht->size)
+ return entry->key ? entry : _mesa_set_next_entry_unsafe(ht, entry);
+
+ return NULL;
+}
+
/**
* This function is an iterator over the hash table.
*
diff --git a/src/util/set.h b/src/util/set.h
index 54983138477..36f271fb054 100644
--- a/src/util/set.h
+++ b/src/util/set.h
@@ -111,6 +111,8 @@ _mesa_set_remove_key(struct set *set, const void *key);
struct set_entry *
_mesa_set_next_entry(const struct set *set, struct set_entry *entry);
+struct set_entry *
+_mesa_set_next_entry_unsafe(const struct set *set, struct set_entry *entry);
struct set_entry *
_mesa_set_random_entry(struct set *set,
@@ -132,6 +134,15 @@ _mesa_set_intersects(struct set *a, struct set *b);
entry != NULL; \
entry = _mesa_set_next_entry(set, entry))
+/**
+ * This foreach function destroys the table as it iterates.
+ * It is not safe to use when inserting or removing entries.
+ */
+#define set_foreach_remove(set, entry) \
+ for (struct set_entry *entry = _mesa_set_next_entry_unsafe(set, NULL); \
+ (set)->entries; \
+ entry->hash = 0, entry->key = (void*)NULL, (set)->entries--, entry = _mesa_set_next_entry_unsafe(set, entry))
+
#ifdef __cplusplus
} /* extern C */
#endif
diff --git a/src/util/tests/set/set_test.cpp b/src/util/tests/set/set_test.cpp
index 6b9c993e3fd..67e3085ee6e 100644
--- a/src/util/tests/set/set_test.cpp
+++ b/src/util/tests/set/set_test.cpp
@@ -58,6 +58,20 @@ TEST(set, basic)
GTEST_FAIL();
}
+ _mesa_set_add(s, a);
+ _mesa_set_add(s, b);
+ EXPECT_EQ(s->entries, 2);
+ unsigned count = s->entries;
+ set_foreach_remove(s, he) {
+ EXPECT_TRUE(he->key == a || he->key == b);
+ EXPECT_EQ(s->entries, count--);
+ EXPECT_EQ(s->deleted_entries, 0);
+ }
+ EXPECT_EQ(s->entries, 0);
+ set_foreach(s, he) {
+ GTEST_FAIL();
+ }
+
_mesa_set_destroy(s, NULL);
}
More information about the mesa-commit
mailing list