summaryrefslogtreecommitdiff
path: root/src/egl/main/eglhash.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/egl/main/eglhash.c')
-rw-r--r--src/egl/main/eglhash.c347
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 0000000000..8e3da2e906
--- /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;
+}
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-14 19:33:09 +0000