X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;ds=sidebyside;f=src%2Fmesa%2Fmain%2Fhash.c;h=4b250ad546874c6cfb0d5600789b93026f7d25db;hb=bda361e0d47a670f318664abcdf0a065bef22883;hp=ce5fdee93163a694ee4cedb284c7ab83896b1e02;hpb=485f04074151686fa24d40e3eeb83029d3d8c425;p=mesa.git diff --git a/src/mesa/main/hash.c b/src/mesa/main/hash.c index ce5fdee9316..4b250ad5468 100644 --- a/src/mesa/main/hash.c +++ b/src/mesa/main/hash.c @@ -1,21 +1,31 @@ -/* $Id: hash.c,v 1.2 1999/10/08 09:27:10 keithw Exp $ */ +/** + * \file hash.c + * Generic hash table. + * + * Used for display lists, texture objects, vertex/fragment programs, + * buffer objects, etc. The hash functions are thread-safe. + * + * \note key=0 is illegal. + * + * \author Brian Paul + */ /* * Mesa 3-D graphics library - * Version: 3.1 - * - * Copyright (C) 1999 Brian Paul All Rights Reserved. - * + * Version: 6.5.1 + * + * Copyright (C) 1999-2006 Brian Paul All Rights Reserved. + * * Permission is hereby granted, free of charge, to any person obtaining a * copy of this software and associated documentation files (the "Software"), * to deal in the Software without restriction, including without limitation * the rights to use, copy, modify, merge, publish, distribute, sublicense, * and/or sell copies of the Software, and to permit persons to whom the * Software is furnished to do so, subject to the following conditions: - * + * * The above copyright notice and this permission notice shall be included * in all copies or substantial portions of the Software. - * + * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL @@ -25,83 +35,96 @@ */ - - - -#ifdef PC_HEADER -#include "all.h" -#else -#ifndef XFree86Server -#include -#include -#include -#else -#include "GL/xf86glx.h" -#endif +#include "glheader.h" +#include "imports.h" +#include "glapi/glthread.h" #include "hash.h" -#endif -/* - * Generic hash table. Only dependency is the GLuint datatype. - * - * This is used to implement display list and texture object lookup. - * NOTE: key=0 is illegal. - */ +#define TABLE_SIZE 1023 /**< Size of lookup table/array */ +#define HASH_FUNC(K) ((K) % TABLE_SIZE) -#define TABLE_SIZE 1024 +/** + * An entry in the hash table. + */ struct HashEntry { - GLuint Key; - void *Data; - struct HashEntry *Next; + GLuint Key; /**< the entry's key */ + void *Data; /**< the entry's data */ + struct HashEntry *Next; /**< pointer to next entry */ }; -struct HashTable { - struct HashEntry *Table[TABLE_SIZE]; - GLuint MaxKey; + +/** + * The hash table data structure. + */ +struct _mesa_HashTable { + struct HashEntry *Table[TABLE_SIZE]; /**< the lookup table */ + GLuint MaxKey; /**< highest key inserted so far */ + _glthread_Mutex Mutex; /**< mutual exclusion lock */ + _glthread_Mutex WalkMutex; /**< for _mesa_HashWalk() */ + GLboolean InDeleteAll; /**< Debug check */ }; -/* - * Return pointer to a new, empty hash table. +/** + * Create a new hash table. + * + * \return pointer to a new, empty hash table. */ -struct HashTable *NewHashTable(void) +struct _mesa_HashTable * +_mesa_NewHashTable(void) { - return (struct HashTable *) calloc(sizeof (struct HashTable), 1); + struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable); + if (table) { + _glthread_INIT_MUTEX(table->Mutex); + _glthread_INIT_MUTEX(table->WalkMutex); + } + 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 DeleteHashTable(struct HashTable *table) +void +_mesa_DeleteHashTable(struct _mesa_HashTable *table) { - GLuint i; + GLuint pos; assert(table); - for (i=0;iTable[i]; + 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; } } + _glthread_DESTROY_MUTEX(table->Mutex); + _glthread_DESTROY_MUTEX(table->WalkMutex); free(table); } -/* - * Lookup an entry in the hash table. - * Input: table - the hash table - * key - the key - * Return: user data pointer or NULL if key not in table +/** + * Lookup an entry in the hash table, without locking. + * \sa _mesa_HashLookup */ -void *HashLookup(const struct HashTable *table, GLuint key) +static inline void * +_mesa_HashLookup_unlocked(struct _mesa_HashTable *table, GLuint key) { GLuint pos; const struct HashEntry *entry; @@ -109,11 +132,11 @@ void *HashLookup(const struct HashTable *table, GLuint key) assert(table); assert(key); - pos = key & (TABLE_SIZE-1); + pos = HASH_FUNC(key); entry = table->Table[pos]; while (entry) { if (entry->Key == key) { - return entry->Data; + return entry->Data; } entry = entry->Next; } @@ -121,15 +144,36 @@ void *HashLookup(const struct HashTable *table, GLuint key) } +/** + * 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 * +_mesa_HashLookup(struct _mesa_HashTable *table, GLuint key) +{ + void *res; + assert(table); + _glthread_LOCK_MUTEX(table->Mutex); + res = _mesa_HashLookup_unlocked(table, key); + _glthread_UNLOCK_MUTEX(table->Mutex); + return res; +} + -/* - * Insert into the hash table. If an entry with this key already exists - * we'll replace the existing entry. - * Input: table - the hash table - * key - the key (not zero) - * data - pointer to user data +/** + * 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 HashInsert(struct HashTable *table, GLuint key, void *data) +void +_mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data) { /* search for existing entry with this key */ GLuint pos; @@ -138,36 +182,53 @@ void HashInsert(struct HashTable *table, GLuint key, void *data) 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) { + 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; } - entry = entry->Next; } /* alloc and insert new table entry */ - entry = (struct HashEntry *) calloc(sizeof(struct HashEntry), 1); - entry->Key = key; - entry->Data = data; - entry->Next = table->Table[pos]; - table->Table[pos] = 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); } -/* +/** * Remove an entry from the hash table. - * Input: table - the hash table - * key - key of entry to remove + * + * \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 HashRemove(struct HashTable *table, GLuint key) +void +_mesa_HashRemove(struct _mesa_HashTable *table, GLuint key) { GLuint pos; struct HashEntry *entry, *prev; @@ -175,7 +236,16 @@ void HashRemove(struct HashTable *table, GLuint key) assert(table); assert(key); - pos = key & (TABLE_SIZE-1); + /* have to check this outside of mutex lock */ + if (table->InDeleteAll) { + _mesa_problem(NULL, "_mesa_HashRemove illegally called from " + "_mesa_HashDeleteAll callback function"); + return; + } + + _glthread_LOCK_MUTEX(table->Mutex); + + pos = HASH_FUNC(key); prev = NULL; entry = table->Table[pos]; while (entry) { @@ -188,44 +258,171 @@ void HashRemove(struct HashTable *table, GLuint key) table->Table[pos] = entry->Next; } free(entry); + _glthread_UNLOCK_MUTEX(table->Mutex); return; } prev = entry; entry = entry->Next; } + + _glthread_UNLOCK_MUTEX(table->Mutex); } -/* +/** + * Delete all entries in a hash table, but don't delete the table itself. + * Invoke the given callback function for each table entry. + * + * \param table the hash table to delete + * \param callback the callback function + * \param userData arbitrary pointer to pass along to the callback + * (this is typically a struct gl_context pointer) + */ +void +_mesa_HashDeleteAll(struct _mesa_HashTable *table, + void (*callback)(GLuint key, void *data, void *userData), + void *userData) +{ + GLuint pos; + 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; + } + table->InDeleteAll = GL_FALSE; + _glthread_UNLOCK_MUTEX(table->Mutex); +} + + +/** + * Walk over all entries in a hash table, calling callback function for each. + * Note: we use a separate mutex in this function to avoid a recursive + * locking deadlock (in case the callback calls _mesa_HashRemove()) and to + * prevent multiple threads/contexts from getting tangled up. + * A lock-less version of this function could be used when the table will + * not be modified. + * \param table the hash table to walk + * \param callback the callback function + * \param userData arbitrary pointer to pass along to the callback + * (this is typically a struct gl_context pointer) + */ +void +_mesa_HashWalk(const struct _mesa_HashTable *table, + void (*callback)(GLuint key, void *data, void *userData), + void *userData) +{ + /* cast-away const */ + struct _mesa_HashTable *table2 = (struct _mesa_HashTable *) table; + GLuint pos; + 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); + } + } + _glthread_UNLOCK_MUTEX(table2->WalkMutex); +} + + +/** * Return the key of the "first" entry in the hash table. - * By calling this function until zero is returned we can get - * the keys of all entries in the 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 HashFirstEntry(const struct HashTable *table) +GLuint +_mesa_HashFirstEntry(struct _mesa_HashTable *table) { GLuint pos; assert(table); - for (pos=0; pos < TABLE_SIZE; pos++) { - if (table->Table[pos]) + _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) +{ + 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; + } +} + + +/** * Dump contents of hash table for debugging. + * + * \param table the hash table. */ -void HashPrint(const struct HashTable *table) +void +_mesa_HashPrint(const struct _mesa_HashTable *table) { - GLuint i; + GLuint pos; assert(table); - for (i=0;iTable[i]; + for (pos = 0; pos < TABLE_SIZE; pos++) { + const struct HashEntry *entry = table->Table[pos]; while (entry) { - printf("%u %p\n", entry->Key, entry->Data); + _mesa_debug(NULL, "%u %p\n", entry->Key, entry->Data); entry = entry->Next; } } @@ -233,26 +430,36 @@ void HashPrint(const struct HashTable *table) -/* - * Find a block of 'numKeys' adjacent unused hash keys. - * Input: table - the hash table - * numKeys - number of keys needed - * Return: startint key of free block or 0 if failure +/** + * Find a block of adjacent unused hash keys. + * + * \param table the hash table. + * \param numKeys number of keys needed. + * + * \return Starting key of free block or 0 if failure. + * + * If there are enough free keys between the maximum key existing in the table + * (_mesa_HashTable::MaxKey) and the maximum key possible, then simply return + * the adjacent key. Otherwise do a full search for a free key block in the + * allowable key range. */ -GLuint HashFindFreeKeyBlock(const struct HashTable *table, GLuint numKeys) +GLuint +_mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys) { - GLuint maxKey = ~((GLuint) 0); + const GLuint maxKey = ~((GLuint) 0); + _glthread_LOCK_MUTEX(table->Mutex); if (maxKey - numKeys > table->MaxKey) { /* the quick solution */ + _glthread_UNLOCK_MUTEX(table->Mutex); return table->MaxKey + 1; } else { /* the slow solution */ GLuint freeCount = 0; - GLuint freeStart = 0; + GLuint freeStart = 1; GLuint key; - for (key=0; key!=maxKey; key++) { - if (HashLookup(table, key)) { + for (key = 1; key != maxKey; key++) { + if (_mesa_HashLookup_unlocked(table, key)) { /* darn, this key is already in use */ freeCount = 0; freeStart = key+1; @@ -261,36 +468,80 @@ GLuint HashFindFreeKeyBlock(const struct HashTable *table, GLuint numKeys) /* this key not in use, check if we've found enough */ freeCount++; if (freeCount == numKeys) { + _glthread_UNLOCK_MUTEX(table->Mutex); return freeStart; } } } /* cannot allocate a block of numKeys consecutive keys */ + _glthread_UNLOCK_MUTEX(table->Mutex); return 0; } } +#if 0 /* debug only */ -#ifdef HASH_TEST_HARNESS -int main(int argc, char *argv[]) +/** + * 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 HashTable *t; + struct _mesa_HashTable *t; - printf("&a = %p\n", &a); - 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);*/ - t = NewHashTable(); - HashInsert(t, 501, &a); - HashInsert(t, 10, &c); - HashInsert(t, 0xfffffff8, &b); - HashPrint(t); - printf("Find 501: %p\n", HashLookup(t,501)); - printf("Find 1313: %p\n", HashLookup(t,1313)); - printf("Find block of 100: %d\n", HashFindFreeKeyBlock(t, 100)); - DeleteHashTable(t); + assert(_mesa_HashLookup(t,501)); + assert(!_mesa_HashLookup(t,1313)); + assert(_mesa_HashFindFreeKeyBlock(t, 100)); - return 0; + _mesa_DeleteHashTable(t); + + test_hash_walking(); } + #endif