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