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