#include "glheader.h"
#include "imports.h"
#include "glthread.h"
#include "hash.h"
#include "context.h"
#define TABLE_SIZE 1023
struct HashEntry {
GLuint Key;
void *Data;
struct HashEntry *Next;
};
struct _mesa_HashTable {
struct HashEntry *Table[TABLE_SIZE];
GLuint MaxKey;
_glthread_Mutex Mutex;
};
struct _mesa_HashTable *_mesa_NewHashTable(void)
{
struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable);
if (table) {
_glthread_INIT_MUTEX(table->Mutex);
}
return table;
}
void _mesa_DeleteHashTable(struct _mesa_HashTable *table)
{
GLuint i;
assert(table);
for (i=0;i<TABLE_SIZE;i++) {
struct HashEntry *entry = table->Table[i];
while (entry) {
struct HashEntry *next = entry->Next;
FREE(entry);
entry = next;
}
}
_glthread_DESTROY_MUTEX(table->Mutex);
FREE(table);
}
void *_mesa_HashLookup(const struct _mesa_HashTable *table, GLuint key)
{
GLuint pos;
const struct HashEntry *entry;
assert(table);
assert(key);
pos = key & (TABLE_SIZE-1);
entry = table->Table[pos];
while (entry) {
if (entry->Key == key) {
return entry->Data;
}
entry = entry->Next;
}
return NULL;
}
void _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data)
{
GLuint pos;
struct HashEntry *entry;
assert(table);
assert(key);
_glthread_LOCK_MUTEX(table->Mutex);
if (key > table->MaxKey)
table->MaxKey = key;
pos = key & (TABLE_SIZE-1);
entry = table->Table[pos];
while (entry) {
if (entry->Key == key) {
entry->Data = data;
_glthread_UNLOCK_MUTEX(table->Mutex);
return;
}
entry = entry->Next;
}
entry = MALLOC_STRUCT(HashEntry);
entry->Key = key;
entry->Data = data;
entry->Next = table->Table[pos];
table->Table[pos] = entry;
_glthread_UNLOCK_MUTEX(table->Mutex);
}
void _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)
{
GLuint pos;
struct HashEntry *entry, *prev;
assert(table);
assert(key);
_glthread_LOCK_MUTEX(table->Mutex);
pos = key & (TABLE_SIZE-1);
prev = NULL;
entry = table->Table[pos];
while (entry) {
if (entry->Key == key) {
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;
}
_glthread_UNLOCK_MUTEX(table->Mutex);
}
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;
}
void _mesa_HashPrint(const struct _mesa_HashTable *table)
{
GLuint i;
assert(table);
for (i=0;i<TABLE_SIZE;i++) {
const struct HashEntry *entry = table->Table[i];
while (entry) {
_mesa_debug(NULL, "%u %p\n", entry->Key, entry->Data);
entry = entry->Next;
}
}
}
GLuint _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys)
{
GLuint maxKey = ~((GLuint) 0);
_glthread_LOCK_MUTEX(table->Mutex);
if (maxKey - numKeys > table->MaxKey) {
_glthread_UNLOCK_MUTEX(table->Mutex);
return table->MaxKey + 1;
}
else {
GLuint freeCount = 0;
GLuint freeStart = 1;
GLuint key;
for (key=1; key!=maxKey; key++) {
if (_mesa_HashLookup(table, key)) {
freeCount = 0;
freeStart = key+1;
}
else {
freeCount++;
if (freeCount == numKeys) {
_glthread_UNLOCK_MUTEX(table->Mutex);
return freeStart;
}
}
}
_glthread_UNLOCK_MUTEX(table->Mutex);
return 0;
}
}
#ifdef HASH_TEST_HARNESS
int main(int argc, char *argv[])
{
int a, b, c;
struct HashTable *t;
_mesa_printf("&a = %p\n", &a);
_mesa_printf("&b = %p\n", &b);
t = _mesa_NewHashTable();
_mesa_HashInsert(t, 501, &a);
_mesa_HashInsert(t, 10, &c);
_mesa_HashInsert(t, 0xfffffff8, &b);
_mesa_HashPrint(t);
_mesa_printf("Find 501: %p\n", _mesa_HashLookup(t,501));
_mesa_printf("Find 1313: %p\n", _mesa_HashLookup(t,1313));
_mesa_printf("Find block of 100: %d\n", _mesa_HashFindFreeKeyBlock(t, 100));
_mesa_DeleteHashTable(t);
return 0;
}
#endif