src/mesa/main/hash.c

   1 /**
   2  * \file hash.c
   3  * Generic hash table.
   4  *
   5  * Used for display lists, texture objects, vertex/fragment programs,
   6  * buffer objects, etc.  The hash functions are 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:  6.3
  16  *
  17  * Copyright (C) 1999-2005  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
  43
  44 #define TABLE_SIZE 1023  /**< Size of lookup table/array */
  45
  46 #define HASH_FUNC(K)  ((K) % TABLE_SIZE)
  47
  48
  49 /**
  50  * An entry in the hash table.
  51  *
  52  * This struct is private to this file.
  53  */
  54 struct HashEntry {
  55    GLuint Key;             /**< the entry's key */
  56    void *Data;             /**< the entry's data */
  57    struct HashEntry *Next; /**< pointer to next entry */
  58 };
  59
  60 /**
  61  * The hash table data structure.
  62  *
  63  * This is an opaque types (it's not defined in hash.h file).
  64  */
  65 struct _mesa_HashTable {
  66    struct HashEntry *Table[TABLE_SIZE];  /**< the lookup table */
  67    GLuint MaxKey;                        /**< highest key inserted so far */
  68    _glthread_Mutex Mutex;                /**< mutual exclusion lock */
  69 };
  70
  71
  72 /**
  73  * Create a new hash table.
  74  *
  75  * \return pointer to a new, empty hash table.
  76  */
  77 struct _mesa_HashTable *
  78 _mesa_NewHashTable(void)
  79 {
  80    struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable);
  81    if (table) {
  82       _glthread_INIT_MUTEX(table->Mutex);
  83    }
  84    return table;
  85 }
  86
  87
  88
  89 /**
  90  * Delete a hash table.
  91  * Frees each entry on the hash table and then the hash table structure itself.
  92  * Note that the caller should have already traversed the table and deleted
  93  * the objects in the table (i.e. We don't free the entries' data pointer).
  94  *
  95  * \param table the hash table to delete.
  96  */
  97 void
  98 _mesa_DeleteHashTable(struct _mesa_HashTable *table)
  99 {
 100    GLuint i;
 101    assert(table);
 102    for (i = 0; i < TABLE_SIZE; i++) {
 103       struct HashEntry *entry = table->Table[i];
 104       while (entry) {
 105          struct HashEntry *next = entry->Next;
 106          FREE(entry);
 107          entry = next;
 108       }
 109    }
 110    _glthread_DESTROY_MUTEX(table->Mutex);
 111    FREE(table);
 112 }
 113
 114
 115
 116 /**
 117  * Lookup an entry in the hash table.
 118  *
 119  * \param table the hash table.
 120  * \param key the key.
 121  *
 122  * \return pointer to user's data or NULL if key not in table
 123  */
 124 void *
 125 _mesa_HashLookup(const struct _mesa_HashTable *table, GLuint key)
 126 {
 127    GLuint pos;
 128    const struct HashEntry *entry;
 129
 130    assert(table);
 131    assert(key);
 132
 133    pos = HASH_FUNC(key);
 134    entry = table->Table[pos];
 135    while (entry) {
 136       if (entry->Key == key) {
 137          return entry->Data;
 138       }
 139       entry = entry->Next;
 140    }
 141    return NULL;
 142 }
 143
 144
 145
 146 /**
 147  * Insert a key/pointer pair into the hash table.
 148  * If an entry with this key already exists we'll replace the existing entry.
 149  *
 150  * \param table the hash table.
 151  * \param key the key (not zero).
 152  * \param data pointer to user data.
 153  */
 154 void
 155 _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 = HASH_FUNC(key);
 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
 203 _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)
 204 {
 205    GLuint pos;
 206    struct HashEntry *entry, *prev;
 207
 208    assert(table);
 209    assert(key);
 210
 211    _glthread_LOCK_MUTEX(table->Mutex);
 212
 213    pos = HASH_FUNC(key);
 214    prev = NULL;
 215    entry = table->Table[pos];
 216    while (entry) {
 217       if (entry->Key == key) {
 218          /* found it! */
 219          if (prev) {
 220             prev->Next = entry->Next;
 221          }
 222          else {
 223             table->Table[pos] = entry->Next;
 224          }
 225          FREE(entry);
 226          _glthread_UNLOCK_MUTEX(table->Mutex);
 227          return;
 228       }
 229       prev = entry;
 230       entry = entry->Next;
 231    }
 232
 233    _glthread_UNLOCK_MUTEX(table->Mutex);
 234 }
 235
 236
 237
 238 /**
 239  * Get the key of the "first" entry in the hash table.
 240  *
 241  * This is used in the course of deleting all display lists when
 242  * a context is destroyed.
 243  *
 244  * \param table the hash table
 245  *
 246  * \return key for the "first" entry in the hash table.
 247  *
 248  * While holding the lock, walks through all table positions until finding
 249  * the first entry of the first non-empty one.
 250  */
 251 GLuint
 252 _mesa_HashFirstEntry(struct _mesa_HashTable *table)
 253 {
 254    GLuint pos;
 255    assert(table);
 256    _glthread_LOCK_MUTEX(table->Mutex);
 257    for (pos=0; pos < TABLE_SIZE; pos++) {
 258       if (table->Table[pos]) {
 259          _glthread_UNLOCK_MUTEX(table->Mutex);
 260          return table->Table[pos]->Key;
 261       }
 262    }
 263    _glthread_UNLOCK_MUTEX(table->Mutex);
 264    return 0;
 265 }
 266
 267
 268 /**
 269  * Given a hash table key, return the next key.  This is used to walk
 270  * over all entries in the table.  Note that the keys returned during
 271  * walking won't be in any particular order.
 272  * \return next hash key or 0 if end of table.
 273  */
 274 GLuint
 275 _mesa_HashNextEntry(const struct _mesa_HashTable *table, GLuint key)
 276 {
 277    const struct HashEntry *entry;
 278    GLuint pos;
 279
 280    assert(table);
 281    assert(key);
 282
 283    /* Find the entry with given key */
 284    pos = HASH_FUNC(key);
 285    entry = table->Table[pos];
 286    while (entry) {
 287       if (entry->Key == key) {
 288          break;
 289       }
 290       entry = entry->Next;
 291    }
 292
 293    if (!entry) {
 294       /* the key was not found, we can't find next entry */
 295       return 0;
 296    }
 297
 298    if (entry->Next) {
 299       /* return next in linked list */
 300       return entry->Next->Key;
 301    }
 302    else {
 303       /* look for next non-empty table slot */
 304       pos++;
 305       while (pos < TABLE_SIZE) {
 306          if (table->Table[pos]) {
 307             return table->Table[pos]->Key;
 308          }
 309          pos++;
 310       }
 311       return 0;
 312    }
 313 }
 314
 315
 316 /**
 317  * Dump contents of hash table for debugging.
 318  *
 319  * \param table the hash table.
 320  */
 321 void
 322 _mesa_HashPrint(const struct _mesa_HashTable *table)
 323 {
 324    GLuint i;
 325    assert(table);
 326    for (i=0;i<TABLE_SIZE;i++) {
 327       const struct HashEntry *entry = table->Table[i];
 328       while (entry) {
 329          _mesa_debug(NULL, "%u %p\n", entry->Key, entry->Data);
 330          entry = entry->Next;
 331       }
 332    }
 333 }
 334
 335
 336
 337 /**
 338  * Find a block of adjacent unused hash keys.
 339  *
 340  * \param table the hash table.
 341  * \param numKeys number of keys needed.
 342  *
 343  * \return Starting key of free block or 0 if failure.
 344  *
 345  * If there are enough free keys between the maximum key existing in the table
 346  * (_mesa_HashTable::MaxKey) and the maximum key possible, then simply return
 347  * the adjacent key. Otherwise do a full search for a free key block in the
 348  * allowable key range.
 349  */
 350 GLuint
 351 _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys)
 352 {
 353    GLuint maxKey = ~((GLuint) 0);
 354    _glthread_LOCK_MUTEX(table->Mutex);
 355    if (maxKey - numKeys > table->MaxKey) {
 356       /* the quick solution */
 357       _glthread_UNLOCK_MUTEX(table->Mutex);
 358       return table->MaxKey + 1;
 359    }
 360    else {
 361       /* the slow solution */
 362       GLuint freeCount = 0;
 363       GLuint freeStart = 1;
 364       GLuint key;
 365       for (key=1; key!=maxKey; key++) {
 366          if (_mesa_HashLookup(table, key)) {
 367             /* darn, this key is already in use */
 368             freeCount = 0;
 369             freeStart = key+1;
 370          }
 371          else {
 372             /* this key not in use, check if we've found enough */
 373             freeCount++;
 374             if (freeCount == numKeys) {
 375                _glthread_UNLOCK_MUTEX(table->Mutex);
 376                return freeStart;
 377             }
 378          }
 379       }
 380       /* cannot allocate a block of numKeys consecutive keys */
 381       _glthread_UNLOCK_MUTEX(table->Mutex);
 382       return 0;
 383    }
 384 }
 385
 386
 387 /**
 388  * Test walking over all the entries in a hash table.
 389  */
 390 static void
 391 test_hash_walking(void)
 392 {
 393    struct _mesa_HashTable *t = _mesa_NewHashTable();
 394    const GLuint limit = 50000;
 395    GLuint i;
 396
 397    /* create some entries */
 398    for (i = 0; i < limit; i++) {
 399       GLuint dummy;
 400       GLuint k = (rand() % (limit * 10)) + 1;
 401       while (_mesa_HashLookup(t, k)) {
 402          /* id already in use, try another */
 403          k = (rand() % (limit * 10)) + 1;
 404       }
 405       _mesa_HashInsert(t, k, &dummy);
 406    }
 407
 408    /* walk over all entries */
 409    {
 410       GLuint k = _mesa_HashFirstEntry(t);
 411       GLuint count = 0;
 412       while (k) {
 413          GLuint knext = _mesa_HashNextEntry(t, k);
 414          assert(knext != k);
 415          _mesa_HashRemove(t, k);
 416          count++;
 417          k = knext;
 418       }
 419       assert(count == limit);
 420       k = _mesa_HashFirstEntry(t);
 421       assert(k==0);
 422    }
 423
 424    _mesa_DeleteHashTable(t);
 425 }
 426
 427
 428 void
 429 _mesa_test_hash_functions(void)
 430 {
 431    int a, b, c;
 432    struct _mesa_HashTable *t;
 433
 434    t = _mesa_NewHashTable();
 435    _mesa_HashInsert(t, 501, &a);
 436    _mesa_HashInsert(t, 10, &c);
 437    _mesa_HashInsert(t, 0xfffffff8, &b);
 438    /*_mesa_HashPrint(t);*/
 439
 440    assert(_mesa_HashLookup(t,501));
 441    assert(!_mesa_HashLookup(t,1313));
 442    assert(_mesa_HashFindFreeKeyBlock(t, 100));
 443
 444    _mesa_DeleteHashTable(t);
 445
 446    test_hash_walking();
 447 }