diff options
Diffstat (limited to 'src/egl/main/eglhash.c')
-rw-r--r-- | src/egl/main/eglhash.c | 347 |
1 files changed, 347 insertions, 0 deletions
diff --git a/src/egl/main/eglhash.c b/src/egl/main/eglhash.c new file mode 100644 index 00000000000..8e3da2e9061 --- /dev/null +++ b/src/egl/main/eglhash.c @@ -0,0 +1,347 @@ +/** + * \file hash.c + * Generic hash table. + * + * This code taken from Mesa and adapted. + */ + +#include <assert.h> +#include <stdlib.h> +#include <stdio.h> +#include "eglhash.h" + + +#define TABLE_SIZE 1023 /**< Size of lookup table/array */ + +#define HASH_FUNC(K) ((K) % TABLE_SIZE) + + +/* + * Unfinished mutex stuff + */ + +typedef int _EGLMutex; + +static void +_eglInitMutex(_EGLMutex m) +{ +} + +static void +_eglDestroyMutex(_EGLMutex m) +{ +} + +static void +_eglLockMutex(_EGLMutex m) +{ +} + +static void +_eglUnlockMutex(_EGLMutex m) +{ +} + + + +typedef struct _egl_hashentry _EGLHashentry; + +struct _egl_hashentry +{ + EGLuint Key; /**< the entry's key */ + void *Data; /**< the entry's data */ + _EGLHashentry *Next; /**< pointer to next entry */ +}; + + +struct _egl_hashtable +{ + _EGLHashentry *Table[TABLE_SIZE]; /**< the lookup table */ + EGLuint MaxKey; /**< highest key inserted so far */ + _EGLMutex Mutex; /**< mutual exclusion lock */ +}; + + +/** + * Create a new hash table. + * + * \return pointer to a new, empty hash table. + */ +_EGLHashtable * +_eglNewHashTable(void) +{ + _EGLHashtable *table = (_EGLHashtable *) calloc(1, sizeof(_EGLHashtable)); + if (table) { + _eglInitMutex(table->Mutex); + table->MaxKey = 1; + } + return table; +} + + + +/** + * Delete a hash table. + * Frees each entry on the hash table and then the hash table structure itself. + * Note that the caller should have already traversed the table and deleted + * the objects in the table (i.e. We don't free the entries' data pointer). + * + * \param table the hash table to delete. + */ +void +_eglDeleteHashTable(_EGLHashtable *table) +{ + EGLuint i; + assert(table); + for (i = 0; i < TABLE_SIZE; i++) { + _EGLHashentry *entry = table->Table[i]; + while (entry) { + _EGLHashentry *next = entry->Next; + free(entry); + entry = next; + } + } + _eglDestroyMutex(table->Mutex); + free(table); +} + + + +/** + * Lookup an entry in the hash table. + * + * \param table the hash table. + * \param key the key. + * + * \return pointer to user's data or NULL if key not in table + */ +void * +_eglHashLookup(const _EGLHashtable *table, EGLuint key) +{ + EGLuint pos; + const _EGLHashentry *entry; + + assert(table); + + if (!key) + return NULL; + + pos = HASH_FUNC(key); + entry = table->Table[pos]; + while (entry) { + if (entry->Key == key) { + return entry->Data; + } + entry = entry->Next; + } + return NULL; +} + + + +/** + * Insert a key/pointer pair into the hash table. + * If an entry with this key already exists we'll replace the existing entry. + * + * \param table the hash table. + * \param key the key (not zero). + * \param data pointer to user data. + */ +void +_eglHashInsert(_EGLHashtable *table, EGLuint key, void *data) +{ + /* search for existing entry with this key */ + EGLuint pos; + _EGLHashentry *entry; + + assert(table); + assert(key); + + _eglLockMutex(table->Mutex); + + if (key > table->MaxKey) + table->MaxKey = key; + + pos = HASH_FUNC(key); + entry = table->Table[pos]; + while (entry) { + if (entry->Key == key) { + /* replace entry's data */ + entry->Data = data; + _eglUnlockMutex(table->Mutex); + return; + } + entry = entry->Next; + } + + /* alloc and insert new table entry */ + entry = (_EGLHashentry *) malloc(sizeof(_EGLHashentry)); + entry->Key = key; + entry->Data = data; + entry->Next = table->Table[pos]; + table->Table[pos] = entry; + + _eglUnlockMutex(table->Mutex); +} + + + +/** + * Remove an entry from the hash table. + * + * \param table the hash table. + * \param key key of entry to remove. + * + * While holding the hash table's lock, searches the entry with the matching + * key and unlinks it. + */ +void +_eglHashRemove(_EGLHashtable *table, EGLuint key) +{ + EGLuint pos; + _EGLHashentry *entry, *prev; + + assert(table); + assert(key); + + _eglLockMutex(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); + _eglUnlockMutex(table->Mutex); + return; + } + prev = entry; + entry = entry->Next; + } + + _eglUnlockMutex(table->Mutex); +} + + + +/** + * Get the key of the "first" entry in the hash table. + * + * This is used in the course of deleting all display lists when + * a context is destroyed. + * + * \param table the hash table + * + * \return key for 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. + */ +EGLuint +_eglHashFirstEntry(_EGLHashtable *table) +{ + EGLuint pos; + assert(table); + _eglLockMutex(table->Mutex); + for (pos = 0; pos < TABLE_SIZE; pos++) { + if (table->Table[pos]) { + _eglUnlockMutex(table->Mutex); + return table->Table[pos]->Key; + } + } + _eglUnlockMutex(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. + */ +EGLuint +_eglHashNextEntry(const _EGLHashtable *table, EGLuint key) +{ + const _EGLHashentry *entry; + EGLuint pos; + + assert(table); + assert(key); + + /* Find the entry with given key */ + pos = HASH_FUNC(key); + entry = table->Table[pos]; + while (entry) { + if (entry->Key == key) { + break; + } + entry = entry->Next; + } + + if (!entry) { + /* the key was not found, we can't find 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; + } +} + + +/** + * Dump contents of hash table for debugging. + * + * \param table the hash table. + */ +void +_eglHashPrint(const _EGLHashtable *table) +{ + EGLuint i; + assert(table); + for (i = 0; i < TABLE_SIZE; i++) { + const _EGLHashentry *entry = table->Table[i]; + while (entry) { + printf("%u %p\n", entry->Key, entry->Data); + entry = entry->Next; + } + } +} + + + +/** + * Return a new, unused hash key. + */ +EGLuint +_eglHashGenKey(_EGLHashtable *table) +{ + EGLuint k; + + _eglLockMutex(table->Mutex); + k = table->MaxKey; + table->MaxKey++; + _eglUnlockMutex(table->Mutex); + return k; +} + |