From 8b11d8cfbfaaf72755e6c200140e253cb3e3fa8a Mon Sep 17 00:00:00 2001 From: =?utf8?q?Nicolai=20H=C3=A4hnle?= Date: Wed, 6 Jan 2016 14:50:46 -0500 Subject: [PATCH] util/hash_table: add _mesa_hash_table_clear (v4) v4: coding style change (Matt Turner) Reviewed-by: Ian Romanick (v3) --- src/util/hash_table.c | 26 ++++++++++ src/util/hash_table.h | 2 + src/util/tests/hash_table/Makefile.am | 1 + src/util/tests/hash_table/clear.c | 91 +++++++++++++++++++++++++++++++++++ 4 files changed, 120 insertions(+) create mode 100644 src/util/tests/hash_table/clear.c diff --git a/src/util/hash_table.c b/src/util/hash_table.c index 3ec65af..4cfe3d9 100644 --- a/src/util/hash_table.c +++ b/src/util/hash_table.c @@ -163,6 +163,32 @@ _mesa_hash_table_destroy(struct hash_table *ht, ralloc_free(ht); } +/** + * Deletes all entries of the given hash table without deleting the table + * itself or changing its structure. + * + * If delete_function is passed, it gets called on each entry present. + */ +void +_mesa_hash_table_clear(struct hash_table *ht, + void (*delete_function)(struct hash_entry *entry)) +{ + struct hash_entry *entry; + + for (entry = ht->table; entry != ht->table + ht->size; entry++) { + if (entry->key == NULL) + continue; + + if (delete_function != NULL && entry->key != ht->deleted_key) + delete_function(entry); + + entry->key = NULL; + } + + ht->entries = 0; + ht->deleted_entries = 0; +} + /** Sets the value of the key pointer used for deleted entries in the table. * * The assumption is that usually keys are actual pointers, so we use a diff --git a/src/util/hash_table.h b/src/util/hash_table.h index eb9dbc3..611dcf8 100644 --- a/src/util/hash_table.h +++ b/src/util/hash_table.h @@ -64,6 +64,8 @@ _mesa_hash_table_create(void *mem_ctx, const void *b)); void _mesa_hash_table_destroy(struct hash_table *ht, void (*delete_function)(struct hash_entry *entry)); +void _mesa_hash_table_clear(struct hash_table *ht, + void (*delete_function)(struct hash_entry *entry)); void _mesa_hash_table_set_deleted_key(struct hash_table *ht, const void *deleted_key); diff --git a/src/util/tests/hash_table/Makefile.am b/src/util/tests/hash_table/Makefile.am index 04a77e3..8f12240 100644 --- a/src/util/tests/hash_table/Makefile.am +++ b/src/util/tests/hash_table/Makefile.am @@ -29,6 +29,7 @@ LDADD = \ $(DLOPEN_LIBS) TESTS = \ + clear \ collision \ delete_and_lookup \ delete_management \ diff --git a/src/util/tests/hash_table/clear.c b/src/util/tests/hash_table/clear.c new file mode 100644 index 0000000..526700b --- /dev/null +++ b/src/util/tests/hash_table/clear.c @@ -0,0 +1,91 @@ +/* + * Copyright (C) 2016 Advanced Micro Devices, Inc. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL + * THE AUTHOR(S) AND/OR THEIR SUPPLIERS BE LIABLE FOR ANY CLAIM, + * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR + * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE + * USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +#include "hash_table.h" + +static void *make_key(uint32_t i) +{ + return (void *)(uintptr_t)(1 + i); +} + +static uint32_t key_id(const void *key) +{ + return (uintptr_t)key - 1; +} + +static uint32_t key_hash(const void *key) +{ + return (uintptr_t)key; +} + +static bool key_equal(const void *a, const void *b) +{ + return a == b; +} + +static void delete_function(struct hash_entry *entry) +{ + bool *deleted = (bool *)entry->data; + assert(!*deleted); + *deleted = true; +} + +int main() +{ + struct hash_table *ht; + struct hash_entry *entry; + const uint32_t size = 1000; + bool flags[size]; + uint32_t i; + + ht = _mesa_hash_table_create(NULL, key_hash, key_equal); + + for (i = 0; i < size; ++i) { + flags[i] = false; + _mesa_hash_table_insert(ht, make_key(i), &flags[i]); + } + + _mesa_hash_table_clear(ht, delete_function); + assert(_mesa_hash_table_next_entry(ht, NULL) == NULL); + + /* Check that delete_function was called and that repopulating the table + * works. */ + for (i = 0; i < size; ++i) { + assert(flags[i]); + flags[i] = false; + _mesa_hash_table_insert(ht, make_key(i), &flags[i]); + } + + /* Check that exactly the right set of entries is in the table. */ + for (i = 0; i < size; ++i) { + assert(_mesa_hash_table_search(ht, make_key(i))); + } + + hash_table_foreach(ht, entry) { + assert(key_id(entry->key) < size); + } + + _mesa_hash_table_destroy(ht, NULL); + + return 0; +} -- 2.7.4