[Mesa-dev] [PATCH 12/14] util: Rename functions and structs
Thomas Helland
thomashelland90 at gmail.com
Sun Jan 1 18:37:56 UTC 2017
---
src/util/non_replacing_hash_table.c | 112 +++++++++++++++++++-----------------
src/util/non_replacing_hash_table.h | 102 ++++++++++++++++----------------
2 files changed, 111 insertions(+), 103 deletions(-)
diff --git a/src/util/non_replacing_hash_table.c b/src/util/non_replacing_hash_table.c
index 48f42aa7c9..ecec94e2d6 100644
--- a/src/util/non_replacing_hash_table.c
+++ b/src/util/non_replacing_hash_table.c
@@ -93,32 +93,32 @@ static const struct {
};
static int
-entry_is_free(const struct hash_entry *entry)
+entry_is_free(const struct non_replacing_hash_entry *entry)
{
return entry->key == NULL;
}
static int
-entry_is_deleted(const struct hash_table *ht, struct hash_entry *entry)
+entry_is_deleted(const struct non_replacing_hash_table *ht, struct non_replacing_hash_entry *entry)
{
return entry->key == ht->deleted_key;
}
static int
-entry_is_present(const struct hash_table *ht, struct hash_entry *entry)
+entry_is_present(const struct non_replacing_hash_table *ht, struct non_replacing_hash_entry *entry)
{
return entry->key != NULL && entry->key != ht->deleted_key;
}
-struct hash_table *
-_mesa_hash_table_create(void *mem_ctx,
+struct non_replacing_hash_table *
+_mesa_non_replacing_hash_table_create(void *mem_ctx,
uint32_t (*key_hash_function)(const void *key),
bool (*key_equals_function)(const void *a,
const void *b))
{
- struct hash_table *ht;
+ struct non_replacing_hash_table *ht;
- ht = ralloc(mem_ctx, struct hash_table);
+ ht = ralloc(mem_ctx, struct non_replacing_hash_table);
if (ht == NULL)
return NULL;
@@ -128,7 +128,7 @@ _mesa_hash_table_create(void *mem_ctx,
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->table = rzalloc_array(ht, struct non_replacing_hash_entry, ht->size);
ht->entries = 0;
ht->deleted_entries = 0;
ht->deleted_key = &deleted_key_value;
@@ -148,16 +148,16 @@ _mesa_hash_table_create(void *mem_ctx,
* freeing.
*/
void
-_mesa_hash_table_destroy(struct hash_table *ht,
- void (*delete_function)(struct hash_entry *entry))
+_mesa_non_replacing_hash_table_destroy(struct non_replacing_hash_table *ht,
+ void (*delete_function)(struct non_replacing_hash_entry *entry))
{
if (!ht)
return;
if (delete_function) {
- struct hash_entry *entry;
+ struct non_replacing_hash_entry *entry;
- hash_table_foreach(ht, entry) {
+ non_replacing_hash_table_foreach(ht, entry) {
delete_function(entry);
}
}
@@ -171,10 +171,10 @@ _mesa_hash_table_destroy(struct hash_table *ht,
* 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))
+_mesa_non_replacing_hash_table_clear(struct non_replacing_hash_table *ht,
+ void (*delete_function)(struct non_replacing_hash_entry *entry))
{
- struct hash_entry *entry;
+ struct non_replacing_hash_entry *entry;
for (entry = ht->table; entry != ht->table + ht->size; entry++) {
if (entry->key == NULL)
@@ -202,13 +202,14 @@ _mesa_hash_table_clear(struct hash_table *ht,
* This must be called before any keys are actually deleted from the table.
*/
void
-_mesa_hash_table_set_deleted_key(struct hash_table *ht, const void *deleted_key)
+_mesa_non_replacing_hash_table_set_deleted_key(struct non_replacing_hash_table *ht,
+ const void *deleted_key)
{
ht->deleted_key = deleted_key;
}
-static struct hash_entry *
-hash_table_search(struct hash_table *ht, uint32_t hash, const void *key)
+static struct non_replacing_hash_entry *
+hash_table_search(struct non_replacing_hash_table *ht, uint32_t hash, const void *key)
{
uint32_t start_hash_address = hash % ht->size;
uint32_t hash_address = start_hash_address;
@@ -216,13 +217,13 @@ hash_table_search(struct hash_table *ht, uint32_t hash, const void *key)
do {
uint32_t double_hash;
- struct hash_entry *entry = ht->table + hash_address;
+ struct non_replacing_hash_entry *entry = ht->table + hash_address;
if (entry_is_free(entry)) {
return NULL;
} else if (entry_is_present(ht, entry) && entry->hash == hash) {
if (ht->key_equals_function(key, entry->key)) {
- struct hash_entry *previous_entry = entry;
+ struct non_replacing_hash_entry *previous_entry = entry;
/* Follow the chain of matching key's to the end */
while (previous_entry->next_data != 0 ) {
@@ -256,35 +257,36 @@ hash_table_search(struct hash_table *ht, uint32_t hash, const void *key)
* Returns NULL if no entry is found. Note that the data pointer may be
* modified by the user.
*/
-struct hash_entry *
-_mesa_hash_table_search(struct hash_table *ht, const void *key)
+struct non_replacing_hash_entry *
+_mesa_non_replacing_hash_table_search(struct non_replacing_hash_table *ht, const void *key)
{
assert(ht->key_hash_function);
return hash_table_search(ht, ht->key_hash_function(key), key);
}
-struct hash_entry *
-_mesa_hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash,
- const void *key)
+struct non_replacing_hash_entry *
+_mesa_non_replacing_hash_table_search_pre_hashed(struct non_replacing_hash_table *ht,
+ uint32_t hash, const void *key)
{
assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key));
return hash_table_search(ht, hash, key);
}
-static struct hash_entry *
-hash_table_insert(struct hash_table *ht, uint32_t hash,
+static struct non_replacing_hash_entry *
+hash_table_insert(struct non_replacing_hash_table *ht, uint32_t hash,
const void *key, void *data);
static void
-_mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index)
+_mesa_non_replacing_hash_table_rehash(struct non_replacing_hash_table *ht,
+ unsigned new_size_index)
{
- struct hash_table old_ht;
- struct hash_entry *table, *entry;
+ struct non_replacing_hash_table old_ht;
+ struct non_replacing_hash_entry *table, *entry;
if (new_size_index >= ARRAY_SIZE(hash_sizes))
return;
- table = rzalloc_array(ht, struct hash_entry,
+ table = rzalloc_array(ht, struct non_replacing_hash_entry,
hash_sizes[new_size_index].size);
if (table == NULL)
return;
@@ -299,32 +301,32 @@ _mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index)
ht->entries = 0;
ht->deleted_entries = 0;
- hash_table_foreach(&old_ht, entry) {
+ non_replacing_hash_table_foreach(&old_ht, entry) {
hash_table_insert(ht, entry->hash, entry->key, entry->data);
}
ralloc_free(old_ht.table);
}
-static struct hash_entry *
-hash_table_insert(struct hash_table *ht, uint32_t hash,
+static struct non_replacing_hash_entry *
+hash_table_insert(struct non_replacing_hash_table *ht, uint32_t hash,
const void *key, void *data)
{
uint32_t start_hash_address, hash_address;
- struct hash_entry *available_entry = NULL;
+ struct non_replacing_hash_entry *available_entry = NULL;
assert(key != NULL);
if (ht->entries >= ht->max_entries) {
- _mesa_hash_table_rehash(ht, ht->size_index + 1);
+ _mesa_non_replacing_hash_table_rehash(ht, ht->size_index + 1);
} else if (ht->deleted_entries + ht->entries >= ht->max_entries) {
- _mesa_hash_table_rehash(ht, ht->size_index);
+ _mesa_non_replacing_hash_table_rehash(ht, ht->size_index);
}
start_hash_address = hash % ht->size;
hash_address = start_hash_address;
do {
- struct hash_entry *entry = ht->table + hash_address;
+ struct non_replacing_hash_entry *entry = ht->table + hash_address;
uint32_t double_hash;
if (!entry_is_present(ht, entry)) {
@@ -351,7 +353,7 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
if (!entry_is_deleted(ht, entry) &&
entry->hash == hash &&
ht->key_equals_function(key, entry->key)) {
- struct hash_entry *old_entry = entry;
+ struct non_replacing_hash_entry *old_entry = entry;
/* Follow the chain of matching key's to the end */
while (old_entry->next_data != 0) {
@@ -411,16 +413,18 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
* Note that insertion may rearrange the table on a resize or rehash,
* so previously found hash_entries are no longer valid after this function.
*/
-struct hash_entry *
-_mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data)
+struct non_replacing_hash_entry *
+_mesa_non_replacing_hash_table_insert(struct non_replacing_hash_table *ht,
+ const void *key, void *data)
{
assert(ht->key_hash_function);
return hash_table_insert(ht, ht->key_hash_function(key), key, data);
}
-struct hash_entry *
-_mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash,
- const void *key, void *data)
+struct non_replacing_hash_entry *
+_mesa_non_replacing_hash_table_insert_pre_hashed(struct non_replacing_hash_table *ht,
+ uint32_t hash, const void *key,
+ void *data)
{
assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key));
return hash_table_insert(ht, hash, key, data);
@@ -437,8 +441,8 @@ _mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash,
* the chain will be broken, and the table will have unpredictable results.
*/
void
-_mesa_hash_table_remove(struct hash_table *ht,
- struct hash_entry *entry)
+_mesa_non_replacing_hash_table_remove(struct non_replacing_hash_table *ht,
+ struct non_replacing_hash_entry *entry)
{
if (!entry)
return;
@@ -455,9 +459,9 @@ _mesa_hash_table_remove(struct hash_table *ht,
* Pass in NULL for the first entry, as in the start of a for loop. Note that
* an iteration over the table is O(table_size) not O(entries).
*/
-struct hash_entry *
-_mesa_hash_table_next_entry(struct hash_table *ht,
- struct hash_entry *entry)
+struct non_replacing_hash_entry *
+_mesa_non_replacing_hash_table_next_entry(struct non_replacing_hash_table *ht,
+ struct non_replacing_hash_entry *entry)
{
if (entry == NULL)
entry = ht->table;
@@ -481,11 +485,11 @@ _mesa_hash_table_next_entry(struct hash_table *ht,
* implementation. @predicate may be used to filter entries, or may
* be set to NULL for no filtering.
*/
-struct hash_entry *
-_mesa_hash_table_random_entry(struct hash_table *ht,
- bool (*predicate)(struct hash_entry *entry))
+struct non_replacing_hash_entry *
+_mesa_non_replacing_hash_table_random_entry(struct non_replacing_hash_table *ht,
+ bool (*predicate)(struct non_replacing_hash_entry *entry))
{
- struct hash_entry *entry;
+ struct non_replacing_hash_entry *entry;
uint32_t i = rand() % ht->size;
if (ht->entries == 0)
@@ -541,7 +545,7 @@ _mesa_hash_string(const char *key)
/**
* String compare function for use as the comparison callback in
- * _mesa_hash_table_create().
+ * _mesa_non_replacing_hash_table_create().
*/
bool
_mesa_key_string_equal(const void *a, const void *b)
diff --git a/src/util/non_replacing_hash_table.h b/src/util/non_replacing_hash_table.h
index 7550400539..f047ad5c11 100644
--- a/src/util/non_replacing_hash_table.h
+++ b/src/util/non_replacing_hash_table.h
@@ -25,8 +25,8 @@
*
*/
-#ifndef _HASH_TABLE_H
-#define _HASH_TABLE_H
+#ifndef _NON_REPLACING_HASH_TABLE_H
+#define _NON_REPLACING_HASH_TABLE_H
#include <stdlib.h>
#include <inttypes.h>
@@ -38,7 +38,7 @@
extern "C" {
#endif
-struct hash_entry {
+struct non_replacing_hash_entry {
uint32_t hash;
const void *key;
void *data;
@@ -49,8 +49,8 @@ struct hash_entry {
uint32_t next_data;
};
-struct hash_table {
- struct hash_entry *table;
+struct non_replacing_hash_table {
+ struct non_replacing_hash_entry *table;
uint32_t (*key_hash_function)(const void *key);
bool (*key_equals_function)(const void *a, const void *b);
const void *deleted_key;
@@ -62,41 +62,44 @@ struct hash_table {
uint32_t deleted_entries;
};
-struct hash_table *
-_mesa_hash_table_create(void *mem_ctx,
- uint32_t (*key_hash_function)(const void *key),
- bool (*key_equals_function)(const void *a,
- 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);
-
-static inline uint32_t _mesa_hash_table_num_entries(struct hash_table *ht)
+struct non_replacing_hash_table *
+_mesa_non_replacing_hash_table_create(void *mem_ctx,
+ uint32_t (*key_hash_function)(const void *key),
+ bool (*key_equals_function)(const void *a,
+ const void *b));
+void _mesa_non_replacing_hash_table_destroy(struct non_replacing_hash_table *ht,
+ void (*delete_function)(struct non_replacing_hash_entry *entry));
+void _mesa_non_replacing_hash_table_clear(struct non_replacing_hash_table *ht,
+ void (*delete_function)(struct non_replacing_hash_entry *entry));
+void _mesa_non_replacing_hash_table_set_deleted_key(struct non_replacing_hash_table *ht,
+ const void *deleted_key);
+
+static inline uint32_t
+_mesa_non_replacing_hash_table_num_entries(struct non_replacing_hash_table *ht)
{
return ht->entries;
}
-struct hash_entry *
-_mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data);
-struct hash_entry *
-_mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash,
- const void *key, void *data);
-struct hash_entry *
-_mesa_hash_table_search(struct hash_table *ht, const void *key);
-struct hash_entry *
-_mesa_hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash,
- const void *key);
-void _mesa_hash_table_remove(struct hash_table *ht,
- struct hash_entry *entry);
-
-struct hash_entry *_mesa_hash_table_next_entry(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));
+struct non_replacing_hash_entry *
+_mesa_non_replacing_hash_table_insert(struct non_replacing_hash_table *ht, const void *key,
+ void *data);
+struct non_replacing_hash_entry *
+_mesa_non_replacing_hash_table_insert_pre_hashed(struct non_replacing_hash_table *ht, uint32_t hash,
+ const void *key, void *data);
+struct non_replacing_hash_entry *
+_mesa_non_replacing_hash_table_search(struct non_replacing_hash_table *ht, const void *key);
+struct non_replacing_hash_entry *
+_mesa_non_replacing_hash_table_search_pre_hashed(struct non_replacing_hash_table *ht, uint32_t hash,
+ const void *key);
+void _mesa_non_replacing_hash_table_remove(struct non_replacing_hash_table *ht,
+ struct non_replacing_hash_entry *entry);
+
+struct non_replacing_hash_entry *
+_mesa_non_replacing_hash_table_next_entry(struct non_replacing_hash_table *ht,
+ struct non_replacing_hash_entry *entry);
+struct non_replacing_hash_entry *
+_mesa_non_replacing_hash_table_random_entry(struct non_replacing_hash_table *ht,
+ bool (*predicate)(struct non_replacing_hash_entry *entry));
uint32_t _mesa_hash_data(const void *data, size_t size);
uint32_t _mesa_hash_string(const char *key);
@@ -118,7 +121,8 @@ enum {
};
static inline uint32_t
-_mesa_fnv32_1a_accumulate_block(uint32_t hash, const void *data, size_t size)
+_mesa_fnv32_1a_accumulate_block(uint32_t hash, const void *data,
+ size_t size)
{
const uint8_t *bytes = (const uint8_t *)data;
@@ -139,21 +143,21 @@ _mesa_fnv32_1a_accumulate_block(uint32_t hash, const void *data, size_t size)
* an entry's data with the deleted marker), but not against insertion
* (which may rehash the table, making entry a dangling pointer).
*/
-#define hash_table_foreach(ht, entry) \
- for (entry = _mesa_hash_table_next_entry(ht, NULL); \
- entry != NULL; \
- entry = _mesa_hash_table_next_entry(ht, entry))
+#define non_replacing_hash_table_foreach(ht, entry) \
+ for (entry = _mesa_non_replacing_hash_table_next_entry(ht, NULL); \
+ entry != NULL; \
+ entry = _mesa_non_replacing_hash_table_next_entry(ht, entry))
static inline void
-hash_table_call_foreach(struct hash_table *ht,
- void (*callback)(const void *key,
- void *data,
- void *closure),
- void *closure)
+non_replacing_hash_table_call_foreach(struct non_replacing_hash_table *ht,
+ void (*callback)(const void *key,
+ void *data,
+ void *closure),
+ void *closure)
{
- struct hash_entry *entry;
+ struct non_replacing_hash_entry *entry;
- hash_table_foreach(ht, entry)
+ non_replacing_hash_table_foreach(ht, entry)
callback(entry->key, entry->data, closure);
}
@@ -161,4 +165,4 @@ hash_table_call_foreach(struct hash_table *ht,
} /* extern C */
#endif
-#endif /* _HASH_TABLE_H */
+#endif /* _NON_REPLACING_HASH_TABLE_H */
--
2.11.0
More information about the mesa-dev
mailing list