src/mesa/main/hash.c

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