src/mesa/main/hash.c

   1 /* $Id: hash.c,v 1.14 2002/10/24 23:57:21 brianp Exp $ */
   2
   3 /*
   4  * Mesa 3-D graphics library
   5  * Version:  4.1
   6  *
   7  * Copyright (C) 1999-2002  Brian Paul   All Rights Reserved.
   8  *
   9  * Permission is hereby granted, free of charge, to any person obtaining a
  10  * copy of this software and associated documentation files (the "Software"),
  11  * to deal in the Software without restriction, including without limitation
  12  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  13  * and/or sell copies of the Software, and to permit persons to whom the
  14  * Software is furnished to do so, subject to the following conditions:
  15  *
  16  * The above copyright notice and this permission notice shall be included
  17  * in all copies or substantial portions of the Software.
  18  *
  19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  20  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  21  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  22  * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  23  * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  24  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  */
  26
  27 #include "glheader.h"
  28 #include "imports.h"
  29 #include "glthread.h"
  30 #include "hash.h"
  31 #include "context.h"
  32
  33
  34 /**
  35  * \file hash.c
  36  * \brief Generic hash table.  Used for display lists and texture objects.
  37  * The hash functions are thread-safe.
  38  * \author Brian Paul
  39  * \note key=0 is illegal
  40  */
  41
  42
  43 #define TABLE_SIZE 1023  /**< Size of lookup table/array */
  44
  45 /**
  46  * An entry in the hash table.  This struct is private to this file.
  47  */
  48 struct HashEntry {
  49    GLuint Key;             /**< the entry's key */
  50    void *Data;             /**< the entry's data */
  51    struct HashEntry *Next; /**< pointer to next entry */
  52 };
  53
  54 /**
  55  * The hashtable data structure.  This is an opaque types (it's not
  56  * defined in the .h file).
  57  */
  58 struct _mesa_HashTable {
  59    struct HashEntry *Table[TABLE_SIZE];  /**< the lookup table */
  60    GLuint MaxKey;                        /**< highest key inserted so far */
  61    _glthread_Mutex Mutex;                /**< mutual exclusion lock */
  62 };
  63
  64
  65
  66 /**
  67  * Create a new hash table.
  68  * \return pointer to a new, empty hash table.
  69  */
  70 struct _mesa_HashTable *_mesa_NewHashTable(void)
  71 {
  72    struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable);
  73    if (table) {
  74       _glthread_INIT_MUTEX(table->Mutex);
  75    }
  76    return table;
  77 }
  78
  79
  80
  81 /**
  82  * Delete a hash table.
  83  * \param table - the hash table to delete
  84  */
  85 void _mesa_DeleteHashTable(struct _mesa_HashTable *table)
  86 {
  87    GLuint i;
  88    assert(table);
  89    for (i=0;i<TABLE_SIZE;i++) {
  90       struct HashEntry *entry = table->Table[i];
  91       while (entry) {
  92          struct HashEntry *next = entry->Next;
  93          FREE(entry);
  94          entry = next;
  95       }
  96    }
  97    FREE(table);
  98 }
  99
 100
 101
 102 /**
 103  * Lookup an entry in the hash table.
 104  * \param table - the hash table
 105  * \param key - the key
 106  * \return pointer to user's data or NULL if key not in table
 107  */
 108 void *_mesa_HashLookup(const struct _mesa_HashTable *table, GLuint key)
 109 {
 110    GLuint pos;
 111    const struct HashEntry *entry;
 112
 113    assert(table);
 114    assert(key);
 115
 116    pos = key & (TABLE_SIZE-1);
 117    entry = table->Table[pos];
 118    while (entry) {
 119       if (entry->Key == key) {
 120          return entry->Data;
 121       }
 122       entry = entry->Next;
 123    }
 124    return NULL;
 125 }
 126
 127
 128
 129 /**
 130  * Insert into the hash table.  If an entry with this key already exists
 131  * we'll replace the existing entry.
 132  * \param table - the hash table
 133  * \param key - the key (not zero)
 134  * \param data - pointer to user data
 135  */
 136 void _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data)
 137 {
 138    /* search for existing entry with this key */
 139    GLuint pos;
 140    struct HashEntry *entry;
 141
 142    assert(table);
 143    assert(key);
 144
 145    _glthread_LOCK_MUTEX(table->Mutex);
 146
 147    if (key > table->MaxKey)
 148       table->MaxKey = key;
 149
 150    pos = key & (TABLE_SIZE-1);
 151    entry = table->Table[pos];
 152    while (entry) {
 153       if (entry->Key == key) {
 154          /* replace entry's data */
 155          entry->Data = data;
 156          _glthread_UNLOCK_MUTEX(table->Mutex);
 157          return;
 158       }
 159       entry = entry->Next;
 160    }
 161
 162    /* alloc and insert new table entry */
 163    entry = MALLOC_STRUCT(HashEntry);
 164    entry->Key = key;
 165    entry->Data = data;
 166    entry->Next = table->Table[pos];
 167    table->Table[pos] = entry;
 168
 169    _glthread_UNLOCK_MUTEX(table->Mutex);
 170 }
 171
 172
 173
 174 /**
 175  * Remove an entry from the hash table.
 176  * \param table - the hash table
 177  * \param key - key of entry to remove
 178  */
 179 void _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)
 180 {
 181    GLuint pos;
 182    struct HashEntry *entry, *prev;
 183
 184    assert(table);
 185    assert(key);
 186
 187    _glthread_LOCK_MUTEX(table->Mutex);
 188
 189    pos = key & (TABLE_SIZE-1);
 190    prev = NULL;
 191    entry = table->Table[pos];
 192    while (entry) {
 193       if (entry->Key == key) {
 194          /* found it! */
 195          if (prev) {
 196             prev->Next = entry->Next;
 197          }
 198          else {
 199             table->Table[pos] = entry->Next;
 200          }
 201          FREE(entry);
 202          _glthread_UNLOCK_MUTEX(table->Mutex);
 203          return;
 204       }
 205       prev = entry;
 206       entry = entry->Next;
 207    }
 208
 209    _glthread_UNLOCK_MUTEX(table->Mutex);
 210 }
 211
 212
 213
 214 /**
 215  * Get the key of the "first" entry in the hash table.
 216  * This is used in the course of deleting all display lists when
 217  * a context is destroyed.
 218  * \param table - the hash table
 219  * \return key for the "first" entry in the hash table.
 220  */
 221 GLuint _mesa_HashFirstEntry(struct _mesa_HashTable *table)
 222 {
 223    GLuint pos;
 224    assert(table);
 225    _glthread_LOCK_MUTEX(table->Mutex);
 226    for (pos=0; pos < TABLE_SIZE; pos++) {
 227       if (table->Table[pos]) {
 228          _glthread_UNLOCK_MUTEX(table->Mutex);
 229          return table->Table[pos]->Key;
 230       }
 231    }
 232    _glthread_UNLOCK_MUTEX(table->Mutex);
 233    return 0;
 234 }
 235
 236
 237
 238 /**
 239  * Dump contents of hash table for debugging.
 240  * \param table - the hash table
 241  */
 242 void _mesa_HashPrint(const struct _mesa_HashTable *table)
 243 {
 244    GLuint i;
 245    assert(table);
 246    for (i=0;i<TABLE_SIZE;i++) {
 247       const struct HashEntry *entry = table->Table[i];
 248       while (entry) {
 249          _mesa_debug(NULL, "%u %p\n", entry->Key, entry->Data);
 250          entry = entry->Next;
 251       }
 252    }
 253 }
 254
 255
 256
 257 /**
 258  * Find a block of 'numKeys' adjacent unused hash keys.
 259  * \param table - the hash table
 260  * \param numKeys - number of keys needed
 261  * \return Starting key of free block or 0 if failure
 262  */
 263 GLuint _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys)
 264 {
 265    GLuint maxKey = ~((GLuint) 0);
 266    _glthread_LOCK_MUTEX(table->Mutex);
 267    if (maxKey - numKeys > table->MaxKey) {
 268       /* the quick solution */
 269       _glthread_UNLOCK_MUTEX(table->Mutex);
 270       return table->MaxKey + 1;
 271    }
 272    else {
 273       /* the slow solution */
 274       GLuint freeCount = 0;
 275       GLuint freeStart = 1;
 276       GLuint key;
 277       for (key=1; key!=maxKey; key++) {
 278          if (_mesa_HashLookup(table, key)) {
 279             /* darn, this key is already in use */
 280             freeCount = 0;
 281             freeStart = key+1;
 282          }
 283          else {
 284             /* this key not in use, check if we've found enough */
 285             freeCount++;
 286             if (freeCount == numKeys) {
 287                _glthread_UNLOCK_MUTEX(table->Mutex);
 288                return freeStart;
 289             }
 290          }
 291       }
 292       /* cannot allocate a block of numKeys consecutive keys */
 293       _glthread_UNLOCK_MUTEX(table->Mutex);
 294       return 0;
 295    }
 296 }
 297
 298
 299
 300 #ifdef HASH_TEST_HARNESS
 301 int main(int argc, char *argv[])
 302 {
 303    int a, b, c;
 304    struct HashTable *t;
 305
 306    _mesa_printf("&a = %p\n", &a);
 307    _mesa_printf("&b = %p\n", &b);
 308
 309    t = _mesa_NewHashTable();
 310    _mesa_HashInsert(t, 501, &a);
 311    _mesa_HashInsert(t, 10, &c);
 312    _mesa_HashInsert(t, 0xfffffff8, &b);
 313    _mesa_HashPrint(t);
 314
 315    _mesa_printf("Find 501: %p\n", _mesa_HashLookup(t,501));
 316    _mesa_printf("Find 1313: %p\n", _mesa_HashLookup(t,1313));
 317    _mesa_printf("Find block of 100: %d\n", _mesa_HashFindFreeKeyBlock(t, 100));
 318
 319    _mesa_DeleteHashTable(t);
 320
 321    return 0;
 322 }
 323 #endif