src/mesa/main/hash.c

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