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.5.1
  16  *
  17  * Copyright (C) 1999-2006  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 "glapi/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 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 /**
  60  * The hash table data structure.
  61  */
  62 struct _mesa_HashTable {
  63    struct HashEntry *Table[TABLE_SIZE];  /**< the lookup table */
  64    GLuint MaxKey;                        /**< highest key inserted so far */
  65    _glthread_Mutex Mutex;                /**< mutual exclusion lock */
  66    _glthread_Mutex WalkMutex;            /**< for _mesa_HashWalk() */
  67    GLboolean InDeleteAll;                /**< Debug check */
  68 };
  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       _glthread_INIT_MUTEX(table->WalkMutex);
  84    }
  85    return table;
  86 }
  87
  88
  89
  90 /**
  91  * Delete a hash table.
  92  * Frees each entry on the hash table and then the hash table structure itself.
  93  * Note that the caller should have already traversed the table and deleted
  94  * the objects in the table (i.e. We don't free the entries' data pointer).
  95  *
  96  * \param table the hash table to delete.
  97  */
  98 void
  99 _mesa_DeleteHashTable(struct _mesa_HashTable *table)
 100 {
 101    GLuint pos;
 102    assert(table);
 103    for (pos = 0; pos < TABLE_SIZE; pos++) {
 104       struct HashEntry *entry = table->Table[pos];
 105       while (entry) {
 106          struct HashEntry *next = entry->Next;
 107          if (entry->Data) {
 108             _mesa_problem(NULL,
 109                           "In _mesa_DeleteHashTable, found non-freed data");
 110          }
 111          free(entry);
 112          entry = next;
 113       }
 114    }
 115    _glthread_DESTROY_MUTEX(table->Mutex);
 116    _glthread_DESTROY_MUTEX(table->WalkMutex);
 117    free(table);
 118 }
 119
 120
 121
 122 /**
 123  * Lookup an entry in the hash table, without locking.
 124  * \sa _mesa_HashLookup
 125  */
 126 static INLINE void *
 127 _mesa_HashLookup_unlocked(struct _mesa_HashTable *table, GLuint key)
 128 {
 129    GLuint pos;
 130    const struct HashEntry *entry;
 131
 132    assert(table);
 133    assert(key);
 134
 135    pos = HASH_FUNC(key);
 136    entry = table->Table[pos];
 137    while (entry) {
 138       if (entry->Key == key) {
 139          return entry->Data;
 140       }
 141       entry = entry->Next;
 142    }
 143    return NULL;
 144 }
 145
 146
 147 /**
 148  * Lookup an entry in the hash table.
 149  *
 150  * \param table the hash table.
 151  * \param key the key.
 152  *
 153  * \return pointer to user's data or NULL if key not in table
 154  */
 155 void *
 156 _mesa_HashLookup(struct _mesa_HashTable *table, GLuint key)
 157 {
 158    void *res;
 159    assert(table);
 160    _glthread_LOCK_MUTEX(table->Mutex);
 161    res = _mesa_HashLookup_unlocked(table, key);
 162    _glthread_UNLOCK_MUTEX(table->Mutex);
 163    return res;
 164 }
 165
 166
 167 /**
 168  * Insert a key/pointer pair into the hash table.
 169  * If an entry with this key already exists we'll replace the existing entry.
 170  *
 171  * \param table the hash table.
 172  * \param key the key (not zero).
 173  * \param data pointer to user data.
 174  */
 175 void
 176 _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data)
 177 {
 178    /* search for existing entry with this key */
 179    GLuint pos;
 180    struct HashEntry *entry;
 181
 182    assert(table);
 183    assert(key);
 184
 185    _glthread_LOCK_MUTEX(table->Mutex);
 186
 187    if (key > table->MaxKey)
 188       table->MaxKey = key;
 189
 190    pos = HASH_FUNC(key);
 191
 192    /* check if replacing an existing entry with same key */
 193    for (entry = table->Table[pos]; entry; entry = entry->Next) {
 194       if (entry->Key == key) {
 195          /* replace entry's data */
 196 #if 0 /* not sure this check is always valid */
 197          if (entry->Data) {
 198             _mesa_problem(NULL, "Memory leak detected in _mesa_HashInsert");
 199          }
 200 #endif
 201          entry->Data = data;
 202          _glthread_UNLOCK_MUTEX(table->Mutex);
 203          return;
 204       }
 205    }
 206
 207    /* alloc and insert new table entry */
 208    entry = MALLOC_STRUCT(HashEntry);
 209    if (entry) {
 210       entry->Key = key;
 211       entry->Data = data;
 212       entry->Next = table->Table[pos];
 213       table->Table[pos] = entry;
 214    }
 215
 216    _glthread_UNLOCK_MUTEX(table->Mutex);
 217 }
 218
 219
 220
 221 /**
 222  * Remove an entry from the hash table.
 223  *
 224  * \param table the hash table.
 225  * \param key key of entry to remove.
 226  *
 227  * While holding the hash table's lock, searches the entry with the matching
 228  * key and unlinks it.
 229  */
 230 void
 231 _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)
 232 {
 233    GLuint pos;
 234    struct HashEntry *entry, *prev;
 235
 236    assert(table);
 237    assert(key);
 238
 239    /* have to check this outside of mutex lock */
 240    if (table->InDeleteAll) {
 241       _mesa_problem(NULL, "_mesa_HashRemove illegally called from "
 242                     "_mesa_HashDeleteAll callback function");
 243       return;
 244    }
 245
 246    _glthread_LOCK_MUTEX(table->Mutex);
 247
 248    pos = HASH_FUNC(key);
 249    prev = NULL;
 250    entry = table->Table[pos];
 251    while (entry) {
 252       if (entry->Key == key) {
 253          /* found it! */
 254          if (prev) {
 255             prev->Next = entry->Next;
 256          }
 257          else {
 258             table->Table[pos] = entry->Next;
 259          }
 260          free(entry);
 261          _glthread_UNLOCK_MUTEX(table->Mutex);
 262          return;
 263       }
 264       prev = entry;
 265       entry = entry->Next;
 266    }
 267
 268    _glthread_UNLOCK_MUTEX(table->Mutex);
 269 }
 270
 271
 272
 273 /**
 274  * Delete all entries in a hash table, but don't delete the table itself.
 275  * Invoke the given callback function for each table entry.
 276  *
 277  * \param table  the hash table to delete
 278  * \param callback  the callback function
 279  * \param userData  arbitrary pointer to pass along to the callback
 280  *                  (this is typically a struct gl_context pointer)
 281  */
 282 void
 283 _mesa_HashDeleteAll(struct _mesa_HashTable *table,
 284                     void (*callback)(GLuint key, void *data, void *userData),
 285                     void *userData)
 286 {
 287    GLuint pos;
 288    ASSERT(table);
 289    ASSERT(callback);
 290    _glthread_LOCK_MUTEX(table->Mutex);
 291    table->InDeleteAll = GL_TRUE;
 292    for (pos = 0; pos < TABLE_SIZE; pos++) {
 293       struct HashEntry *entry, *next;
 294       for (entry = table->Table[pos]; entry; entry = next) {
 295          callback(entry->Key, entry->Data, userData);
 296          next = entry->Next;
 297          free(entry);
 298       }
 299       table->Table[pos] = NULL;
 300    }
 301    table->InDeleteAll = GL_FALSE;
 302    _glthread_UNLOCK_MUTEX(table->Mutex);
 303 }
 304
 305
 306 /**
 307  * Walk over all entries in a hash table, calling callback function for each.
 308  * Note: we use a separate mutex in this function to avoid a recursive
 309  * locking deadlock (in case the callback calls _mesa_HashRemove()) and to
 310  * prevent multiple threads/contexts from getting tangled up.
 311  * A lock-less version of this function could be used when the table will
 312  * not be modified.
 313  * \param table  the hash table to walk
 314  * \param callback  the callback function
 315  * \param userData  arbitrary pointer to pass along to the callback
 316  *                  (this is typically a struct gl_context pointer)
 317  */
 318 void
 319 _mesa_HashWalk(const struct _mesa_HashTable *table,
 320                void (*callback)(GLuint key, void *data, void *userData),
 321                void *userData)
 322 {
 323    /* cast-away const */
 324    struct _mesa_HashTable *table2 = (struct _mesa_HashTable *) table;
 325    GLuint pos;
 326    ASSERT(table);
 327    ASSERT(callback);
 328    _glthread_LOCK_MUTEX(table2->WalkMutex);
 329    for (pos = 0; pos < TABLE_SIZE; pos++) {
 330       struct HashEntry *entry, *next;
 331       for (entry = table->Table[pos]; entry; entry = next) {
 332          /* save 'next' pointer now in case the callback deletes the entry */
 333          next = entry->Next;
 334          callback(entry->Key, entry->Data, userData);
 335       }
 336    }
 337    _glthread_UNLOCK_MUTEX(table2->WalkMutex);
 338 }
 339
 340
 341 /**
 342  * Return the key of the "first" entry in the hash table.
 343  * While holding the lock, walks through all table positions until finding
 344  * the first entry of the first non-empty one.
 345  *
 346  * \param table  the hash table
 347  * \return key for the "first" entry in the hash table.
 348  */
 349 GLuint
 350 _mesa_HashFirstEntry(struct _mesa_HashTable *table)
 351 {
 352    GLuint pos;
 353    assert(table);
 354    _glthread_LOCK_MUTEX(table->Mutex);
 355    for (pos = 0; pos < TABLE_SIZE; pos++) {
 356       if (table->Table[pos]) {
 357          _glthread_UNLOCK_MUTEX(table->Mutex);
 358          return table->Table[pos]->Key;
 359       }
 360    }
 361    _glthread_UNLOCK_MUTEX(table->Mutex);
 362    return 0;
 363 }
 364
 365
 366 /**
 367  * Given a hash table key, return the next key.  This is used to walk
 368  * over all entries in the table.  Note that the keys returned during
 369  * walking won't be in any particular order.
 370  * \return next hash key or 0 if end of table.
 371  */
 372 GLuint
 373 _mesa_HashNextEntry(const struct _mesa_HashTable *table, GLuint key)
 374 {
 375    const struct HashEntry *entry;
 376    GLuint pos;
 377
 378    assert(table);
 379    assert(key);
 380
 381    /* Find the entry with given key */
 382    pos = HASH_FUNC(key);
 383    for (entry = table->Table[pos]; entry ; entry = entry->Next) {
 384       if (entry->Key == key) {
 385          break;
 386       }
 387    }
 388
 389    if (!entry) {
 390       /* the given key was not found, so we can't find the next entry */
 391       return 0;
 392    }
 393
 394    if (entry->Next) {
 395       /* return next in linked list */
 396       return entry->Next->Key;
 397    }
 398    else {
 399       /* look for next non-empty table slot */
 400       pos++;
 401       while (pos < TABLE_SIZE) {
 402          if (table->Table[pos]) {
 403             return table->Table[pos]->Key;
 404          }
 405          pos++;
 406       }
 407       return 0;
 408    }
 409 }
 410
 411
 412 /**
 413  * Dump contents of hash table for debugging.
 414  *
 415  * \param table the hash table.
 416  */
 417 void
 418 _mesa_HashPrint(const struct _mesa_HashTable *table)
 419 {
 420    GLuint pos;
 421    assert(table);
 422    for (pos = 0; pos < TABLE_SIZE; pos++) {
 423       const struct HashEntry *entry = table->Table[pos];
 424       while (entry) {
 425          _mesa_debug(NULL, "%u %p\n", entry->Key, entry->Data);
 426          entry = entry->Next;
 427       }
 428    }
 429 }
 430
 431
 432
 433 /**
 434  * Find a block of adjacent unused hash keys.
 435  *
 436  * \param table the hash table.
 437  * \param numKeys number of keys needed.
 438  *
 439  * \return Starting key of free block or 0 if failure.
 440  *
 441  * If there are enough free keys between the maximum key existing in the table
 442  * (_mesa_HashTable::MaxKey) and the maximum key possible, then simply return
 443  * the adjacent key. Otherwise do a full search for a free key block in the
 444  * allowable key range.
 445  */
 446 GLuint
 447 _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys)
 448 {
 449    const GLuint maxKey = ~((GLuint) 0);
 450    _glthread_LOCK_MUTEX(table->Mutex);
 451    if (maxKey - numKeys > table->MaxKey) {
 452       /* the quick solution */
 453       _glthread_UNLOCK_MUTEX(table->Mutex);
 454       return table->MaxKey + 1;
 455    }
 456    else {
 457       /* the slow solution */
 458       GLuint freeCount = 0;
 459       GLuint freeStart = 1;
 460       GLuint key;
 461       for (key = 1; key != maxKey; key++) {
 462          if (_mesa_HashLookup_unlocked(table, key)) {
 463             /* darn, this key is already in use */
 464             freeCount = 0;
 465             freeStart = key+1;
 466          }
 467          else {
 468             /* this key not in use, check if we've found enough */
 469             freeCount++;
 470             if (freeCount == numKeys) {
 471                _glthread_UNLOCK_MUTEX(table->Mutex);
 472                return freeStart;
 473             }
 474          }
 475       }
 476       /* cannot allocate a block of numKeys consecutive keys */
 477       _glthread_UNLOCK_MUTEX(table->Mutex);
 478       return 0;
 479    }
 480 }
 481
 482
 483 #if 0 /* debug only */
 484
 485 /**
 486  * Test walking over all the entries in a hash table.
 487  */
 488 static void
 489 test_hash_walking(void)
 490 {
 491    struct _mesa_HashTable *t = _mesa_NewHashTable();
 492    const GLuint limit = 50000;
 493    GLuint i;
 494
 495    /* create some entries */
 496    for (i = 0; i < limit; i++) {
 497       GLuint dummy;
 498       GLuint k = (rand() % (limit * 10)) + 1;
 499       while (_mesa_HashLookup(t, k)) {
 500          /* id already in use, try another */
 501          k = (rand() % (limit * 10)) + 1;
 502       }
 503       _mesa_HashInsert(t, k, &dummy);
 504    }
 505
 506    /* walk over all entries */
 507    {
 508       GLuint k = _mesa_HashFirstEntry(t);
 509       GLuint count = 0;
 510       while (k) {
 511          GLuint knext = _mesa_HashNextEntry(t, k);
 512          assert(knext != k);
 513          _mesa_HashRemove(t, k);
 514          count++;
 515          k = knext;
 516       }
 517       assert(count == limit);
 518       k = _mesa_HashFirstEntry(t);
 519       assert(k==0);
 520    }
 521
 522    _mesa_DeleteHashTable(t);
 523 }
 524
 525
 526 void
 527 _mesa_test_hash_functions(void)
 528 {
 529    int a, b, c;
 530    struct _mesa_HashTable *t;
 531
 532    t = _mesa_NewHashTable();
 533    _mesa_HashInsert(t, 501, &a);
 534    _mesa_HashInsert(t, 10, &c);
 535    _mesa_HashInsert(t, 0xfffffff8, &b);
 536    /*_mesa_HashPrint(t);*/
 537
 538    assert(_mesa_HashLookup(t,501));
 539    assert(!_mesa_HashLookup(t,1313));
 540    assert(_mesa_HashFindFreeKeyBlock(t, 100));
 541
 542    _mesa_DeleteHashTable(t);
 543
 544    test_hash_walking();
 545 }
 546
 547 #endif