diff options
Diffstat (limited to 'mesalib/src/mesa/main/hash.c')
| -rw-r--r-- | mesalib/src/mesa/main/hash.c | 371 |
1 files changed, 113 insertions, 258 deletions
diff --git a/mesalib/src/mesa/main/hash.c b/mesalib/src/mesa/main/hash.c index 61c369a80..8c763e20a 100644 --- a/mesalib/src/mesa/main/hash.c +++ b/mesalib/src/mesa/main/hash.c @@ -34,40 +34,75 @@ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ - #include "glheader.h" #include "imports.h" #include "glapi/glthread.h" #include "hash.h" - - -#define TABLE_SIZE 1023 /**< Size of lookup table/array */ - -#define HASH_FUNC(K) ((K) % TABLE_SIZE) - +#include "hash_table.h" /** - * An entry in the hash table. + * Magic GLuint object name that gets stored outside of the struct hash_table. + * + * The hash table needs a particular pointer to be the marker for a key that + * was deleted from the table, along with NULL for the "never allocated in the + * table" marker. Legacy GL allows any GLuint to be used as a GL object name, + * and we use a 1:1 mapping from GLuints to key pointers, so we need to be + * able to track a GLuint that happens to match the deleted key outside of + * struct hash_table. We tell the hash table to use "1" as the deleted key + * value, so that we test the deleted-key-in-the-table path as best we can. */ -struct HashEntry { - GLuint Key; /**< the entry's key */ - void *Data; /**< the entry's data */ - struct HashEntry *Next; /**< pointer to next entry */ -}; - +#define DELETED_KEY_VALUE 1 /** * The hash table data structure. */ struct _mesa_HashTable { - struct HashEntry *Table[TABLE_SIZE]; /**< the lookup table */ + struct hash_table *ht; GLuint MaxKey; /**< highest key inserted so far */ _glthread_Mutex Mutex; /**< mutual exclusion lock */ _glthread_Mutex WalkMutex; /**< for _mesa_HashWalk() */ GLboolean InDeleteAll; /**< Debug check */ + /** Value that would be in the table for DELETED_KEY_VALUE. */ + void *deleted_key_data; }; +/** @{ + * Mapping from our use of GLuint as both the key and the hash value to the + * hash_table.h API + * + * There exist many integer hash functions, designed to avoid collisions when + * the integers are spread across key space with some patterns. In GL, the + * pattern (in the case of glGen*()ed object IDs) is that the keys are unique + * contiguous integers starting from 1. Because of that, we just use the key + * as the hash value, to minimize the cost of the hash function. If objects + * are never deleted, we will never see a collision in the table, because the + * table resizes itself when it approaches full, and thus key % table_size == + * key. + * + * The case where we could have collisions for genned objects would be + * something like: glGenBuffers(&a, 100); glDeleteBuffers(&a + 50, 50); + * glGenBuffers(&b, 100), because objects 1-50 and 101-200 are allocated at + * the end of that sequence, instead of 1-150. So far it doesn't appear to be + * a problem. + */ +static bool +uint_key_compare(const void *a, const void *b) +{ + return a == b; +} + +static uint32_t +uint_hash(GLuint id) +{ + return id; +} +static void * +uint_key(GLuint id) +{ + return (void *)(uintptr_t) id; +} +/** @} */ /** * Create a new hash table. @@ -78,6 +113,9 @@ struct _mesa_HashTable * _mesa_NewHashTable(void) { struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable); + + table->ht = _mesa_hash_table_create(NULL, uint_key_compare); + _mesa_hash_table_set_deleted_key(table->ht, uint_key(DELETED_KEY_VALUE)); if (table) { _glthread_INIT_MUTEX(table->Mutex); _glthread_INIT_MUTEX(table->WalkMutex); @@ -98,20 +136,14 @@ _mesa_NewHashTable(void) void _mesa_DeleteHashTable(struct _mesa_HashTable *table) { - GLuint pos; assert(table); - for (pos = 0; pos < TABLE_SIZE; pos++) { - struct HashEntry *entry = table->Table[pos]; - while (entry) { - struct HashEntry *next = entry->Next; - if (entry->Data) { - _mesa_problem(NULL, - "In _mesa_DeleteHashTable, found non-freed data"); - } - free(entry); - entry = next; - } + + if (_mesa_hash_table_next_entry(table->ht, NULL) != NULL) { + _mesa_problem(NULL, "In _mesa_DeleteHashTable, found non-freed data"); } + + _mesa_hash_table_destroy(table->ht, NULL); + _glthread_DESTROY_MUTEX(table->Mutex); _glthread_DESTROY_MUTEX(table->WalkMutex); free(table); @@ -126,21 +158,19 @@ _mesa_DeleteHashTable(struct _mesa_HashTable *table) static inline void * _mesa_HashLookup_unlocked(struct _mesa_HashTable *table, GLuint key) { - GLuint pos; - const struct HashEntry *entry; + const struct hash_entry *entry; assert(table); assert(key); - pos = HASH_FUNC(key); - entry = table->Table[pos]; - while (entry) { - if (entry->Key == key) { - return entry->Data; - } - entry = entry->Next; - } - return NULL; + if (key == DELETED_KEY_VALUE) + return table->deleted_key_data; + + entry = _mesa_hash_table_search(table->ht, uint_hash(key), uint_key(key)); + if (!entry) + return NULL; + + return entry->data; } @@ -175,9 +205,8 @@ _mesa_HashLookup(struct _mesa_HashTable *table, GLuint key) void _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data) { - /* search for existing entry with this key */ - GLuint pos; - struct HashEntry *entry; + uint32_t hash = uint_hash(key); + struct hash_entry *entry; assert(table); assert(key); @@ -187,32 +216,17 @@ _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data) if (key > table->MaxKey) table->MaxKey = key; - pos = HASH_FUNC(key); - - /* check if replacing an existing entry with same key */ - for (entry = table->Table[pos]; entry; entry = entry->Next) { - if (entry->Key == key) { - /* replace entry's data */ -#if 0 /* not sure this check is always valid */ - if (entry->Data) { - _mesa_problem(NULL, "Memory leak detected in _mesa_HashInsert"); - } -#endif - entry->Data = data; - _glthread_UNLOCK_MUTEX(table->Mutex); - return; + if (key == DELETED_KEY_VALUE) { + table->deleted_key_data = data; + } else { + entry = _mesa_hash_table_search(table->ht, hash, uint_key(key)); + if (entry) { + entry->data = data; + } else { + _mesa_hash_table_insert(table->ht, hash, uint_key(key), data); } } - /* alloc and insert new table entry */ - entry = MALLOC_STRUCT(HashEntry); - if (entry) { - entry->Key = key; - entry->Data = data; - entry->Next = table->Table[pos]; - table->Table[pos] = entry; - } - _glthread_UNLOCK_MUTEX(table->Mutex); } @@ -230,8 +244,7 @@ _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data) void _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key) { - GLuint pos; - struct HashEntry *entry, *prev; + struct hash_entry *entry; assert(table); assert(key); @@ -244,27 +257,12 @@ _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key) } _glthread_LOCK_MUTEX(table->Mutex); - - pos = HASH_FUNC(key); - prev = NULL; - entry = table->Table[pos]; - while (entry) { - if (entry->Key == key) { - /* found it! */ - if (prev) { - prev->Next = entry->Next; - } - else { - table->Table[pos] = entry->Next; - } - free(entry); - _glthread_UNLOCK_MUTEX(table->Mutex); - return; - } - prev = entry; - entry = entry->Next; + if (key == DELETED_KEY_VALUE) { + table->deleted_key_data = NULL; + } else { + entry = _mesa_hash_table_search(table->ht, uint_hash(key), uint_key(key)); + _mesa_hash_table_remove(table->ht, entry); } - _glthread_UNLOCK_MUTEX(table->Mutex); } @@ -284,19 +282,19 @@ _mesa_HashDeleteAll(struct _mesa_HashTable *table, void (*callback)(GLuint key, void *data, void *userData), void *userData) { - GLuint pos; + struct hash_entry *entry; + ASSERT(table); ASSERT(callback); _glthread_LOCK_MUTEX(table->Mutex); table->InDeleteAll = GL_TRUE; - for (pos = 0; pos < TABLE_SIZE; pos++) { - struct HashEntry *entry, *next; - for (entry = table->Table[pos]; entry; entry = next) { - callback(entry->Key, entry->Data, userData); - next = entry->Next; - free(entry); - } - table->Table[pos] = NULL; + hash_table_foreach(table->ht, entry) { + callback((uintptr_t)entry->key, entry->data, userData); + _mesa_hash_table_remove(table->ht, entry); + } + if (table->deleted_key_data) { + callback(DELETED_KEY_VALUE, table->deleted_key_data, userData); + table->deleted_key_data = NULL; } table->InDeleteAll = GL_FALSE; _glthread_UNLOCK_MUTEX(table->Mutex); @@ -322,93 +320,25 @@ _mesa_HashWalk(const struct _mesa_HashTable *table, { /* cast-away const */ struct _mesa_HashTable *table2 = (struct _mesa_HashTable *) table; - GLuint pos; + struct hash_entry *entry; + ASSERT(table); ASSERT(callback); _glthread_LOCK_MUTEX(table2->WalkMutex); - for (pos = 0; pos < TABLE_SIZE; pos++) { - struct HashEntry *entry, *next; - for (entry = table->Table[pos]; entry; entry = next) { - /* save 'next' pointer now in case the callback deletes the entry */ - next = entry->Next; - callback(entry->Key, entry->Data, userData); - } + hash_table_foreach(table->ht, entry) { + callback((uintptr_t)entry->key, entry->data, userData); } + if (table->deleted_key_data) + callback(DELETED_KEY_VALUE, table->deleted_key_data, userData); _glthread_UNLOCK_MUTEX(table2->WalkMutex); } - -/** - * Return the key of the "first" entry in the hash table. - * While holding the lock, walks through all table positions until finding - * the first entry of the first non-empty one. - * - * \param table the hash table - * \return key for the "first" entry in the hash table. - */ -GLuint -_mesa_HashFirstEntry(struct _mesa_HashTable *table) -{ - GLuint pos; - assert(table); - _glthread_LOCK_MUTEX(table->Mutex); - for (pos = 0; pos < TABLE_SIZE; pos++) { - if (table->Table[pos]) { - _glthread_UNLOCK_MUTEX(table->Mutex); - return table->Table[pos]->Key; - } - } - _glthread_UNLOCK_MUTEX(table->Mutex); - return 0; -} - - -/** - * Given a hash table key, return the next key. This is used to walk - * over all entries in the table. Note that the keys returned during - * walking won't be in any particular order. - * \return next hash key or 0 if end of table. - */ -GLuint -_mesa_HashNextEntry(const struct _mesa_HashTable *table, GLuint key) +static void +debug_print_entry(GLuint key, void *data, void *userData) { - const struct HashEntry *entry; - GLuint pos; - - assert(table); - assert(key); - - /* Find the entry with given key */ - pos = HASH_FUNC(key); - for (entry = table->Table[pos]; entry ; entry = entry->Next) { - if (entry->Key == key) { - break; - } - } - - if (!entry) { - /* the given key was not found, so we can't find the next entry */ - return 0; - } - - if (entry->Next) { - /* return next in linked list */ - return entry->Next->Key; - } - else { - /* look for next non-empty table slot */ - pos++; - while (pos < TABLE_SIZE) { - if (table->Table[pos]) { - return table->Table[pos]->Key; - } - pos++; - } - return 0; - } + _mesa_debug(NULL, "%u %p\n", key, data); } - /** * Dump contents of hash table for debugging. * @@ -417,19 +347,12 @@ _mesa_HashNextEntry(const struct _mesa_HashTable *table, GLuint key) void _mesa_HashPrint(const struct _mesa_HashTable *table) { - GLuint pos; - assert(table); - for (pos = 0; pos < TABLE_SIZE; pos++) { - const struct HashEntry *entry = table->Table[pos]; - while (entry) { - _mesa_debug(NULL, "%u %p\n", entry->Key, entry->Data); - entry = entry->Next; - } - } + if (table->deleted_key_data) + debug_print_entry(DELETED_KEY_VALUE, table->deleted_key_data, NULL); + _mesa_HashWalk(table, debug_print_entry, NULL); } - /** * Find a block of adjacent unused hash keys. * @@ -446,7 +369,7 @@ _mesa_HashPrint(const struct _mesa_HashTable *table) GLuint _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys) { - const GLuint maxKey = ~((GLuint) 0); + const GLuint maxKey = ~((GLuint) 0) - 1; _glthread_LOCK_MUTEX(table->Mutex); if (maxKey - numKeys > table->MaxKey) { /* the quick solution */ @@ -486,82 +409,14 @@ _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys) GLuint _mesa_HashNumEntries(const struct _mesa_HashTable *table) { - GLuint pos, count = 0; + struct hash_entry *entry; + GLuint count = 0; - for (pos = 0; pos < TABLE_SIZE; pos++) { - const struct HashEntry *entry; - for (entry = table->Table[pos]; entry; entry = entry->Next) { - count++; - } - } + if (table->deleted_key_data) + count++; - return count; -} - - - -#if 0 /* debug only */ + hash_table_foreach(table->ht, entry) + count++; -/** - * Test walking over all the entries in a hash table. - */ -static void -test_hash_walking(void) -{ - struct _mesa_HashTable *t = _mesa_NewHashTable(); - const GLuint limit = 50000; - GLuint i; - - /* create some entries */ - for (i = 0; i < limit; i++) { - GLuint dummy; - GLuint k = (rand() % (limit * 10)) + 1; - while (_mesa_HashLookup(t, k)) { - /* id already in use, try another */ - k = (rand() % (limit * 10)) + 1; - } - _mesa_HashInsert(t, k, &dummy); - } - - /* walk over all entries */ - { - GLuint k = _mesa_HashFirstEntry(t); - GLuint count = 0; - while (k) { - GLuint knext = _mesa_HashNextEntry(t, k); - assert(knext != k); - _mesa_HashRemove(t, k); - count++; - k = knext; - } - assert(count == limit); - k = _mesa_HashFirstEntry(t); - assert(k==0); - } - - _mesa_DeleteHashTable(t); -} - - -void -_mesa_test_hash_functions(void) -{ - int a, b, c; - struct _mesa_HashTable *t; - - t = _mesa_NewHashTable(); - _mesa_HashInsert(t, 501, &a); - _mesa_HashInsert(t, 10, &c); - _mesa_HashInsert(t, 0xfffffff8, &b); - /*_mesa_HashPrint(t);*/ - - assert(_mesa_HashLookup(t,501)); - assert(!_mesa_HashLookup(t,1313)); - assert(_mesa_HashFindFreeKeyBlock(t, 100)); - - _mesa_DeleteHashTable(t); - - test_hash_walking(); + return count; } - -#endif |