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