src/mesa/main/hash.c

   1 /* $Id: hash.c,v 1.15 2002/12/12 13:03:15 keithw Exp $ */
   2
   3 /*
   4  * Mesa 3-D graphics library
   5  * Version:  4.1
   6  *
   7  * Copyright (C) 1999-2002  Brian Paul   All Rights Reserved.
   8  *
   9  * Permission is hereby granted, free of charge, to any person obtaining a
  10  * copy of this software and associated documentation files (the "Software"),
  11  * to deal in the Software without restriction, including without limitation
  12  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  13  * and/or sell copies of the Software, and to permit persons to whom the
  14  * Software is furnished to do so, subject to the following conditions:
  15  *
  16  * The above copyright notice and this permission notice shall be included
  17  * in all copies or substantial portions of the Software.
  18  *
  19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  20  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  21  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  22  * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  23  * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  24  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  */
  26
  27 #include "glheader.h"
  28 #include "imports.h"
  29 #include "glthread.h"
  30 #include "hash.h"
  31 #include "context.h"
  32
  33
  34 /**
  35  * \file hash.c
  36  * \brief Generic hash table.  Used for display lists and texture objects.
  37  * The hash functions are thread-safe.
  38  * \author Brian Paul
  39  * \note key=0 is illegal
  40  */
  41
  42
  43 #define TABLE_SIZE 1023  /**< Size of lookup table/array */
  44
  45 /**
  46  * An entry in the hash table.  This struct is private to this file.
  47  */
  48 struct HashEntry {
  49    GLuint Key;             /**< the entry's key */
  50    void *Data;             /**< the entry's data */
  51    struct HashEntry *Next; /**< pointer to next entry */
  52 };
  53
  54 /**
  55  * The hashtable data structure.  This is an opaque types (it's not
  56  * defined in the .h file).
  57  */
  58 struct _mesa_HashTable {
  59    struct HashEntry *Table[TABLE_SIZE];  /**< the lookup table */
  60    GLuint MaxKey;                        /**< highest key inserted so far */
  61    _glthread_Mutex Mutex;                /**< mutual exclusion lock */
  62 };
  63
  64
  65
  66 /**
  67  * Create a new hash table.
  68  * \return pointer to a new, empty hash table.
  69  */
  70 struct _mesa_HashTable *_mesa_NewHashTable(void)
  71 {
  72    struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable);
  73    if (table) {
  74       _glthread_INIT_MUTEX(table->Mutex);
  75    }
  76    return table;
  77 }
  78
  79
  80
  81 /**
  82  * Delete a hash table.
  83  * \param table - the hash table to delete
  84  */
  85 void _mesa_DeleteHashTable(struct _mesa_HashTable *table)
  86 {
  87    GLuint i;
  88    assert(table);
  89    for (i=0;i<TABLE_SIZE;i++) {
  90       struct HashEntry *entry = table->Table[i];
  91       while (entry) {
  92          struct HashEntry *next = entry->Next;
  93          FREE(entry);
  94          entry = next;
  95       }
  96    }
  97    _glthread_DESTROY_MUTEX(table->Mutex);
  98    FREE(table);
  99 }
 100
 101
 102
 103 /**
 104  * Lookup an entry in the hash table.
 105  * \param table - the hash table
 106  * \param key - the key
 107  * \return pointer to user's data or NULL if key not in table
 108  */
 109 void *_mesa_HashLookup(const struct _mesa_HashTable *table, GLuint key)
 110 {
 111    GLuint pos;
 112    const struct HashEntry *entry;
 113
 114    assert(table);
 115    assert(key);
 116
 117    pos = key & (TABLE_SIZE-1);
 118    entry = table->Table[pos];
 119    while (entry) {
 120       if (entry->Key == key) {
 121          return entry->Data;
 122       }
 123       entry = entry->Next;
 124    }
 125    return NULL;
 126 }
 127
 128
 129
 130 /**
 131  * Insert into the hash table.  If an entry with this key already exists
 132  * we'll replace the existing entry.
 133  * \param table - the hash table
 134  * \param key - the key (not zero)
 135  * \param data - pointer to user data
 136  */
 137 void _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data)
 138 {
 139    /* search for existing entry with this key */
 140    GLuint pos;
 141    struct HashEntry *entry;
 142
 143    assert(table);
 144    assert(key);
 145
 146    _glthread_LOCK_MUTEX(table->Mutex);
 147
 148    if (key > table->MaxKey)
 149       table->MaxKey = key;
 150
 151    pos = key & (TABLE_SIZE-1);
 152    entry = table->Table[pos];
 153    while (entry) {
 154       if (entry->Key == key) {
 155          /* replace entry's data */
 156          entry->Data = data;
 157          _glthread_UNLOCK_MUTEX(table->Mutex);
 158          return;
 159       }
 160       entry = entry->Next;
 161    }
 162
 163    /* alloc and insert new table entry */
 164    entry = MALLOC_STRUCT(HashEntry);
 165    entry->Key = key;
 166    entry->Data = data;
 167    entry->Next = table->Table[pos];
 168    table->Table[pos] = entry;
 169
 170    _glthread_UNLOCK_MUTEX(table->Mutex);
 171 }
 172
 173
 174
 175 /**
 176  * Remove an entry from the hash table.
 177  * \param table - the hash table
 178  * \param key - key of entry to remove
 179  */
 180 void _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)
 181 {
 182    GLuint pos;
 183    struct HashEntry *entry, *prev;
 184
 185    assert(table);
 186    assert(key);
 187
 188    _glthread_LOCK_MUTEX(table->Mutex);
 189
 190    pos = key & (TABLE_SIZE-1);
 191    prev = NULL;
 192    entry = table->Table[pos];
 193    while (entry) {
 194       if (entry->Key == key) {
 195          /* found it! */
 196          if (prev) {
 197             prev->Next = entry->Next;
 198          }
 199          else {
 200             table->Table[pos] = entry->Next;
 201          }
 202          FREE(entry);
 203          _glthread_UNLOCK_MUTEX(table->Mutex);
 204          return;
 205       }
 206       prev = entry;
 207       entry = entry->Next;
 208    }
 209
 210    _glthread_UNLOCK_MUTEX(table->Mutex);
 211 }
 212
 213
 214
 215 /**
 216  * Get the key of the "first" entry in the hash table.
 217  * This is used in the course of deleting all display lists when
 218  * a context is destroyed.
 219  * \param table - the hash table
 220  * \return key for the "first" entry in the hash table.
 221  */
 222 GLuint _mesa_HashFirstEntry(struct _mesa_HashTable *table)
 223 {
 224    GLuint pos;
 225    assert(table);
 226    _glthread_LOCK_MUTEX(table->Mutex);
 227    for (pos=0; pos < TABLE_SIZE; pos++) {
 228       if (table->Table[pos]) {
 229          _glthread_UNLOCK_MUTEX(table->Mutex);
 230          return table->Table[pos]->Key;
 231       }
 232    }
 233    _glthread_UNLOCK_MUTEX(table->Mutex);
 234    return 0;
 235 }
 236
 237
 238
 239 /**
 240  * Dump contents of hash table for debugging.
 241  * \param table - the hash table
 242  */
 243 void _mesa_HashPrint(const struct _mesa_HashTable *table)
 244 {
 245    GLuint i;
 246    assert(table);
 247    for (i=0;i<TABLE_SIZE;i++) {
 248       const struct HashEntry *entry = table->Table[i];
 249       while (entry) {
 250          _mesa_debug(NULL, "%u %p\n", entry->Key, entry->Data);
 251          entry = entry->Next;
 252       }
 253    }
 254 }
 255
 256
 257
 258 /**
 259  * Find a block of 'numKeys' adjacent unused hash keys.
 260  * \param table - the hash table
 261  * \param numKeys - number of keys needed
 262  * \return Starting key of free block or 0 if failure
 263  */
 264 GLuint _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys)
 265 {
 266    GLuint maxKey = ~((GLuint) 0);
 267    _glthread_LOCK_MUTEX(table->Mutex);
 268    if (maxKey - numKeys > table->MaxKey) {
 269       /* the quick solution */
 270       _glthread_UNLOCK_MUTEX(table->Mutex);
 271       return table->MaxKey + 1;
 272    }
 273    else {
 274       /* the slow solution */
 275       GLuint freeCount = 0;
 276       GLuint freeStart = 1;
 277       GLuint key;
 278       for (key=1; key!=maxKey; key++) {
 279          if (_mesa_HashLookup(table, key)) {
 280             /* darn, this key is already in use */
 281             freeCount = 0;
 282             freeStart = key+1;
 283          }
 284          else {
 285             /* this key not in use, check if we've found enough */
 286             freeCount++;
 287             if (freeCount == numKeys) {
 288                _glthread_UNLOCK_MUTEX(table->Mutex);
 289                return freeStart;
 290             }
 291          }
 292       }
 293       /* cannot allocate a block of numKeys consecutive keys */
 294       _glthread_UNLOCK_MUTEX(table->Mutex);
 295       return 0;
 296    }
 297 }
 298
 299
 300
 301 #ifdef HASH_TEST_HARNESS
 302 int main(int argc, char *argv[])
 303 {
 304    int a, b, c;
 305    struct HashTable *t;
 306
 307    _mesa_printf("&a = %p\n", &a);
 308    _mesa_printf("&b = %p\n", &b);
 309
 310    t = _mesa_NewHashTable();
 311    _mesa_HashInsert(t, 501, &a);
 312    _mesa_HashInsert(t, 10, &c);
 313    _mesa_HashInsert(t, 0xfffffff8, &b);
 314    _mesa_HashPrint(t);
 315
 316    _mesa_printf("Find 501: %p\n", _mesa_HashLookup(t,501));
 317    _mesa_printf("Find 1313: %p\n", _mesa_HashLookup(t,1313));
 318    _mesa_printf("Find block of 100: %d\n", _mesa_HashFindFreeKeyBlock(t, 100));
 319
 320    _mesa_DeleteHashTable(t);
 321
 322    return 0;
 323 }
 324 #endif