[Mesa-dev] [PATCH 18/18] util: Just cut the hash in the pointer table
Thomas Helland
thomashelland90 at gmail.com
Wed Apr 11 18:48:27 UTC 2018
Meant for testing. Defeats some of the benefits of the implementation,
however it still seems to be better than the current hash table,
and the complexity is undeniably very low.
---
src/util/pointer_map.c | 99 +++++++++++++++++---------------------------------
src/util/pointer_map.h | 1 -
2 files changed, 33 insertions(+), 67 deletions(-)
diff --git a/src/util/pointer_map.c b/src/util/pointer_map.c
index 463fa19282..7632218b91 100644
--- a/src/util/pointer_map.c
+++ b/src/util/pointer_map.c
@@ -39,28 +39,25 @@
#include "ralloc.h"
#include "macros.h"
-static inline uint8_t
-get_hash(uint8_t *metadata)
-{
- return *metadata & 0x7F;
-}
+static const uint32_t deleted_key_value;
+static const void *deleted_key = &deleted_key_value;
-static inline void
-set_hash(uint8_t *metadata, uint32_t hash)
+static bool
+entry_is_free(const struct map_entry *entry)
{
- *metadata = (*metadata & ~0x7F) | (((uint8_t) hash) & 0x7F);
+ return entry->key == NULL;
}
-static inline bool
-entry_is_free(uint8_t *metadata)
+static bool
+entry_is_deleted(const struct pointer_map *pm, struct map_entry *entry)
{
- return !(*metadata >> 7);
+ return entry->key == pm->deleted_key;
}
-static inline void
-set_occupied(uint8_t *metadata, bool occupied)
+static bool
+entry_is_present(const struct pointer_map *pm, struct map_entry *entry)
{
- *metadata = occupied ? *metadata | 0x80 : *metadata & 0x7F;
+ return entry->key != NULL && entry->key != pm->deleted_key;
}
static inline uint32_t
@@ -70,15 +67,6 @@ hash_pointer(const void *pointer)
return (uint32_t) ((num >> 2) ^ (num >> 6) ^ (num >> 10) ^ (num >> 14));
}
-static bool
-entry_is_deleted(struct pointer_map *map, uint8_t *metadata)
-{
- if (get_hash(metadata) != 0)
- return false;
-
- return map->map[metadata - map->metadata].key == NULL;
-}
-
struct pointer_map *
_mesa_pointer_map_create(void *mem_ctx)
{
@@ -91,9 +79,9 @@ _mesa_pointer_map_create(void *mem_ctx)
map->size = 1 << 4;
map->max_entries = map->size * 0.6;
map->map = rzalloc_array(map, struct map_entry, map->size);
- map->metadata = rzalloc_array(map, uint8_t, map->size);
map->entries = 0;
map->deleted_entries = 0;
+ map->deleted_key = deleted_key;
if (map->map == NULL) {
ralloc_free(map);
@@ -113,15 +101,13 @@ _mesa_pointer_map_clone(struct pointer_map *src, void *dst_mem_ctx)
memcpy(pm, src, sizeof(struct pointer_map));
pm->map = ralloc_array(pm, struct map_entry, pm->size);
- pm->metadata = ralloc_array(pm, uint8_t, pm->size);
- if (pm->map == NULL || pm->metadata == NULL) {
+ if (pm->map == NULL) {
ralloc_free(pm);
return NULL;
}
memcpy(pm->map, src->map, pm->size * sizeof(struct map_entry));
- memcpy(pm->metadata, src->metadata, pm->size * sizeof(uint8_t));
return pm;
}
@@ -154,7 +140,6 @@ _mesa_pointer_map_destroy(struct pointer_map *map,
void
_mesa_pointer_map_clear(struct pointer_map *map)
{
- memset(map->metadata, 0, map->size * sizeof(uint8_t));
memset(map->map, 0, sizeof(struct map_entry) * map->size);
map->entries = 0;
map->deleted_entries = 0;
@@ -173,15 +158,14 @@ _mesa_pointer_map_search(struct pointer_map *map, const void *key)
uint32_t start_hash_address = hash & (map->size - 1);
uint32_t hash_address = start_hash_address;
+ struct map_entry *entry = NULL;
do {
- uint8_t *metadata = map->metadata + hash_address;
+ entry = map->map + hash_address;
- if (entry_is_free(metadata)) {
+ if (entry_is_free(entry)) {
return NULL;
- } else if (get_hash(metadata) == (hash & 0x7F)) {
- if (map->map[hash_address].key == key) {
- return &map->map[hash_address];
- }
+ } else if (entry->key == key) {
+ return entry;
}
hash_address = (hash_address + 1) & (map->size - 1);
@@ -195,7 +179,6 @@ _mesa_pointer_map_rehash(struct pointer_map *map, unsigned new_size)
{
struct pointer_map old_map;
struct map_entry *map_entries, *entry;
- uint8_t *metadatas;
old_map = *map;
@@ -206,12 +189,7 @@ _mesa_pointer_map_rehash(struct pointer_map *map, unsigned new_size)
if (map_entries == NULL)
return;
- metadatas = rzalloc_array(map, uint8_t, map->size);
- if (metadatas == NULL)
- return;
-
map->map = map_entries;
- map->metadata = metadatas;
map->entries = 0;
map->deleted_entries = 0;
@@ -220,7 +198,6 @@ _mesa_pointer_map_rehash(struct pointer_map *map, unsigned new_size)
}
ralloc_free(old_map.map);
- ralloc_free(old_map.metadata);
}
/**
@@ -232,7 +209,7 @@ struct map_entry *
_mesa_pointer_map_insert(struct pointer_map *map, const void *key, void *data)
{
uint32_t start_hash_address, hash_address, hash;
- uint8_t *available_entry = NULL;
+ struct map_entry *available_entry = NULL;
assert(key != NULL);
if (map->entries >= map->max_entries) {
@@ -245,16 +222,17 @@ _mesa_pointer_map_insert(struct pointer_map *map, const void *key, void *data)
start_hash_address = hash & (map->size - 1);
hash_address = start_hash_address;
+ struct map_entry *entry = NULL;
+
do {
- uint8_t *entry = map->metadata + hash_address;
+ entry = map->map + hash_address;
- if (entry_is_free(entry)) {
- /* If we have not found a deleted entry yet, then we want
- * to take the free slot at the end of the group
- */
+ if (!entry_is_present(map, entry)) {
+ /* Stash the first available entry we find */
if (available_entry == NULL)
available_entry = entry;
- break;
+ if (entry_is_free(entry))
+ break;
}
/* Implement replacement when another insert happens
@@ -268,18 +246,9 @@ _mesa_pointer_map_insert(struct pointer_map *map, const void *key, void *data)
* required to avoid memory leaks, perform a search
* before inserting.
*/
- if (get_hash(entry) == (hash & 0x7F) &&
- map->map[hash_address].key == key) {
- set_hash(entry, hash);
- map->map[hash_address].data = data;
- set_occupied(entry, true);
- return &map->map[hash_address];
- }
-
- // Stash the first deleted entry in the group
- if (entry_is_deleted(map, entry) &&
- available_entry == NULL) {
- available_entry = entry;
+ if (!entry_is_deleted(map, entry) && key == entry->key) {
+ entry->data = data;
+ return entry;
}
hash_address = (hash_address + 1) & (map->size - 1);
@@ -288,12 +257,10 @@ _mesa_pointer_map_insert(struct pointer_map *map, const void *key, void *data)
if (available_entry) {
if (entry_is_deleted(map, available_entry))
map->deleted_entries--;
- set_hash(available_entry, hash);
- set_occupied(available_entry, true);
- map->map[hash_address].key = key;
- map->map[hash_address].data = data;
+ available_entry->key = key;
+ available_entry->data = data;
map->entries++;
- return &map->map[hash_address];
+ return available_entry;
}
/* We could hit here if a required resize failed. An unchecked-malloc
@@ -316,7 +283,7 @@ _mesa_pointer_map_remove(struct pointer_map *map,
return;
entry->key = NULL;
- set_hash(map->metadata + (entry - map->map), 0);
+ entry->key = map->deleted_key;
map->entries--;
map->deleted_entries++;
}
diff --git a/src/util/pointer_map.h b/src/util/pointer_map.h
index f92e67d40d..0eccb8a4bd 100644
--- a/src/util/pointer_map.h
+++ b/src/util/pointer_map.h
@@ -42,7 +42,6 @@ struct map_entry {
struct pointer_map {
struct map_entry *map;
- uint8_t *metadata;
const void *deleted_key;
--
2.16.2
More information about the mesa-dev
mailing list