Module: Mesa Branch: master Commit: 31e546a762b7ed4c73d7207868ace87fcc01f063 URL: http://cgit.freedesktop.org/mesa/mesa/commit/?id=31e546a762b7ed4c73d7207868ace87fcc01f063
Author: Mike Blumenkrantz <[email protected]> Date: Tue Jan 12 14:49:48 2021 -0500 util/hash_table: add macro for destructively iterating entries a common usage for hash tables is for tracking exactly one instance of a pointer for a given period of time, after which the table'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 <[email protected]> Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/8498> --- src/util/hash_table.c | 21 +++++++++++++++++++++ src/util/hash_table.h | 11 +++++++++++ src/util/tests/hash_table/clear.c | 10 ++++++++++ 3 files changed, 42 insertions(+) diff --git a/src/util/hash_table.c b/src/util/hash_table.c index 92897c1bc83..079427bd951 100644 --- a/src/util/hash_table.c +++ b/src/util/hash_table.c @@ -524,6 +524,27 @@ void _mesa_hash_table_remove_key(struct hash_table *ht, _mesa_hash_table_remove(ht, _mesa_hash_table_search(ht, key)); } +/** + * This function is an iterator over the hash_table when no deleted entries are present. + * + * Pass in NULL for the first entry, as in the start of a for loop. + */ +struct hash_entry * +_mesa_hash_table_next_entry_unsafe(const struct hash_table *ht, struct hash_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_hash_table_next_entry_unsafe(ht, entry); + + return NULL; +} + /** * This function is an iterator over the hash table. * diff --git a/src/util/hash_table.h b/src/util/hash_table.h index 9281b917318..ff3b3bef576 100644 --- a/src/util/hash_table.h +++ b/src/util/hash_table.h @@ -103,6 +103,8 @@ void _mesa_hash_table_remove_key(struct hash_table *ht, struct hash_entry *_mesa_hash_table_next_entry(struct hash_table *ht, struct hash_entry *entry); +struct hash_entry *_mesa_hash_table_next_entry_unsafe(const struct hash_table *ht, + struct hash_entry *entry); struct hash_entry * _mesa_hash_table_random_entry(struct hash_table *ht, bool (*predicate)(struct hash_entry *entry)); @@ -136,6 +138,15 @@ _mesa_hash_table_reserve(struct hash_table *ht, unsigned size); for (struct hash_entry *entry = _mesa_hash_table_next_entry(ht, NULL); \ entry != NULL; \ entry = _mesa_hash_table_next_entry(ht, entry)) +/** + * This foreach function destroys the table as it iterates. + * It is not safe to use when inserting or removing entries. + */ +#define hash_table_foreach_remove(ht, entry) \ + for (struct hash_entry *entry = _mesa_hash_table_next_entry_unsafe(ht, NULL); \ + (ht)->entries; \ + entry->hash = 0, entry->key = (void*)NULL, entry->data = NULL, \ + (ht)->entries--, entry = _mesa_hash_table_next_entry_unsafe(ht, entry)) static inline void hash_table_call_foreach(struct hash_table *ht, diff --git a/src/util/tests/hash_table/clear.c b/src/util/tests/hash_table/clear.c index 90ca30e3a1c..eaa316ff02c 100644 --- a/src/util/tests/hash_table/clear.c +++ b/src/util/tests/hash_table/clear.c @@ -93,6 +93,16 @@ int main() assert(0); } + for (i = 0; i < SIZE; ++i) { + flags[i] = false; + _mesa_hash_table_insert(ht, make_key(i), &flags[i]); + } + hash_table_foreach_remove(ht, entry) { + assert(key_id(entry->key) < SIZE); + } + assert(!ht->entries); + assert(!ht->deleted_entries); + _mesa_hash_table_destroy(ht, NULL); return 0; _______________________________________________ mesa-commit mailing list [email protected] https://lists.freedesktop.org/mailman/listinfo/mesa-commit
