src/mesa/main/hash.c

   1 /* $Id: hash.c,v 1.9 2000/03/21 22:20:42 brianp Exp $ */
   2
   3 /*
   4  * Mesa 3-D graphics library
   5  * Version:  3.3
   6  *
   7  * Copyright (C) 1999-2000  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
  28 #ifdef PC_HEADER
  29 #include "all.h"
  30 #else
  31 #include "glheader.h"
  32 #include "glthread.h"
  33 #include "hash.h"
  34 #include "mem.h"
  35 #endif
  36
  37
  38 /*
  39  * Generic hash table.
  40  *
  41  * This is used to implement display list and texture object lookup.
  42  * NOTE: key=0 is illegal.
  43  */
  44
  45
  46 #define TABLE_SIZE 1024
  47
  48 struct HashEntry {
  49    GLuint Key;
  50    void *Data;
  51    struct HashEntry *Next;
  52 };
  53
  54 struct _mesa_HashTable {
  55    struct HashEntry *Table[TABLE_SIZE];
  56    GLuint MaxKey;
  57    _glthread_Mutex Mutex;
  58 };
  59
  60
  61
  62 /*
  63  * Return pointer to a new, empty hash table.
  64  */
  65 struct _mesa_HashTable *_mesa_NewHashTable(void)
  66 {
  67    return CALLOC_STRUCT(_mesa_HashTable);
  68 }
  69
  70
  71
  72 /*
  73  * Delete a hash table.
  74  */
  75 void _mesa_DeleteHashTable(struct _mesa_HashTable *table)
  76 {
  77    GLuint i;
  78    assert(table);
  79    for (i=0;i<TABLE_SIZE;i++) {
  80       struct HashEntry *entry = table->Table[i];
  81       while (entry) {
  82          struct HashEntry *next = entry->Next;
  83          FREE(entry);
  84          entry = next;
  85       }
  86    }
  87    FREE(table);
  88 }
  89
  90
  91
  92 /*
  93  * Lookup an entry in the hash table.
  94  * Input:  table - the hash table
  95  *         key - the key
  96  * Return:  user data pointer or NULL if key not in table
  97  */
  98 void *_mesa_HashLookup(const struct _mesa_HashTable *table, GLuint key)
  99 {
 100    GLuint pos;
 101    const struct HashEntry *entry;
 102
 103    assert(table);
 104    assert(key);
 105
 106    pos = key & (TABLE_SIZE-1);
 107    entry = table->Table[pos];
 108    while (entry) {
 109       if (entry->Key == key) {
 110          return entry->Data;
 111       }
 112       entry = entry->Next;
 113    }
 114    return NULL;
 115 }
 116
 117
 118
 119 /*
 120  * Insert into the hash table.  If an entry with this key already exists
 121  * we'll replace the existing entry.
 122  * Input:  table - the hash table
 123  *         key - the key (not zero)
 124  *         data - pointer to user data
 125  */
 126 void _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data)
 127 {
 128    /* search for existing entry with this key */
 129    GLuint pos;
 130    struct HashEntry *entry;
 131
 132    assert(table);
 133    assert(key);
 134
 135    _glthread_LOCK_MUTEX(table->Mutex);
 136
 137    if (key > table->MaxKey)
 138       table->MaxKey = key;
 139
 140    pos = key & (TABLE_SIZE-1);
 141    entry = table->Table[pos];
 142    while (entry) {
 143       if (entry->Key == key) {
 144          /* replace entry's data */
 145          entry->Data = data;
 146          _glthread_UNLOCK_MUTEX(table->Mutex);
 147          return;
 148       }
 149       entry = entry->Next;
 150    }
 151
 152    /* alloc and insert new table entry */
 153    entry = MALLOC_STRUCT(HashEntry);
 154    entry->Key = key;
 155    entry->Data = data;
 156    entry->Next = table->Table[pos];
 157    table->Table[pos] = entry;
 158
 159    _glthread_UNLOCK_MUTEX(table->Mutex);
 160 }
 161
 162
 163
 164 /*
 165  * Remove an entry from the hash table.
 166  * Input:  table - the hash table
 167  *         key - key of entry to remove
 168  */
 169 void _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)
 170 {
 171    GLuint pos;
 172    struct HashEntry *entry, *prev;
 173
 174    assert(table);
 175    assert(key);
 176
 177    _glthread_LOCK_MUTEX(table->Mutex);
 178
 179    pos = key & (TABLE_SIZE-1);
 180    prev = NULL;
 181    entry = table->Table[pos];
 182    while (entry) {
 183       if (entry->Key == key) {
 184          /* found it! */
 185          if (prev) {
 186             prev->Next = entry->Next;
 187          }
 188          else {
 189             table->Table[pos] = entry->Next;
 190          }
 191          FREE(entry);
 192          _glthread_UNLOCK_MUTEX(table->Mutex);
 193          return;
 194       }
 195       prev = entry;
 196       entry = entry->Next;
 197    }
 198
 199    _glthread_UNLOCK_MUTEX(table->Mutex);
 200 }
 201
 202
 203
 204 /*
 205  * Return the key of the "first" entry in the hash table.
 206  * This is used in the course of deleting all display lists when
 207  * a context is destroyed.
 208  */
 209 GLuint _mesa_HashFirstEntry(struct _mesa_HashTable *table)
 210 {
 211    GLuint pos;
 212    assert(table);
 213    _glthread_LOCK_MUTEX(table->Mutex);
 214    for (pos=0; pos < TABLE_SIZE; pos++) {
 215       if (table->Table[pos]) {
 216          _glthread_UNLOCK_MUTEX(table->Mutex);
 217          return table->Table[pos]->Key;
 218       }
 219    }
 220    _glthread_UNLOCK_MUTEX(table->Mutex);
 221    return 0;
 222 }
 223
 224
 225
 226 /*
 227  * Dump contents of hash table for debugging.
 228  */
 229 void _mesa_HashPrint(const struct _mesa_HashTable *table)
 230 {
 231    GLuint i;
 232    assert(table);
 233    for (i=0;i<TABLE_SIZE;i++) {
 234       const struct HashEntry *entry = table->Table[i];
 235       while (entry) {
 236          printf("%u %p\n", entry->Key, entry->Data);
 237          entry = entry->Next;
 238       }
 239    }
 240 }
 241
 242
 243
 244 /*
 245  * Find a block of 'numKeys' adjacent unused hash keys.
 246  * Input:  table - the hash table
 247  *         numKeys - number of keys needed
 248  * Return:  starting key of free block or 0 if failure
 249  */
 250 GLuint _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys)
 251 {
 252    GLuint maxKey = ~((GLuint) 0);
 253    _glthread_LOCK_MUTEX(table->Mutex);
 254    if (maxKey - numKeys > table->MaxKey) {
 255       /* the quick solution */
 256       _glthread_UNLOCK_MUTEX(table->Mutex);
 257       return table->MaxKey + 1;
 258    }
 259    else {
 260       /* the slow solution */
 261       GLuint freeCount = 0;
 262       GLuint freeStart = 1;
 263       GLuint key;
 264       for (key=1; key!=maxKey; key++) {
 265          if (_mesa_HashLookup(table, key)) {
 266             /* darn, this key is already in use */
 267             freeCount = 0;
 268             freeStart = key+1;
 269          }
 270          else {
 271             /* this key not in use, check if we've found enough */
 272             freeCount++;
 273             if (freeCount == numKeys) {
 274                _glthread_UNLOCK_MUTEX(table->Mutex);
 275                return freeStart;
 276             }
 277          }
 278       }
 279       /* cannot allocate a block of numKeys consecutive keys */
 280       _glthread_UNLOCK_MUTEX(table->Mutex);
 281       return 0;
 282    }
 283 }
 284
 285
 286
 287 #ifdef HASH_TEST_HARNESS
 288 int main(int argc, char *argv[])
 289 {
 290    int a, b, c;
 291    struct HashTable *t;
 292
 293    printf("&a = %p\n", &a);
 294    printf("&b = %p\n", &b);
 295
 296    t = _mesa_NewHashTable();
 297    _mesa_HashInsert(t, 501, &a);
 298    _mesa_HashInsert(t, 10, &c);
 299    _mesa_HashInsert(t, 0xfffffff8, &b);
 300    _mesa_HashPrint(t);
 301    printf("Find 501: %p\n", _mesa_HashLookup(t,501));
 302    printf("Find 1313: %p\n", _mesa_HashLookup(t,1313));
 303    printf("Find block of 100: %d\n", _mesa_HashFindFreeKeyBlock(t, 100));
 304    _mesa_DeleteHashTable(t);
 305
 306    return 0;
 307 }
 308 #endif