src/mesa/main/hash.c

   1 /* $Id: hash.c,v 1.7 2000/01/31 23:11:39 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  * By calling this function until zero is returned we can get
 207  * the keys of all entries in the table.
 208  */
 209 GLuint _mesa_HashFirstEntry(const struct _mesa_HashTable *table)
 210 {
 211    GLuint pos;
 212    assert(table);
 213    for (pos=0; pos < TABLE_SIZE; pos++) {
 214       if (table->Table[pos])
 215          return table->Table[pos]->Key;
 216    }
 217    return 0;
 218 }
 219
 220
 221
 222 /*
 223  * Dump contents of hash table for debugging.
 224  */
 225 void _mesa_HashPrint(const struct _mesa_HashTable *table)
 226 {
 227    GLuint i;
 228    assert(table);
 229    for (i=0;i<TABLE_SIZE;i++) {
 230       const struct HashEntry *entry = table->Table[i];
 231       while (entry) {
 232          printf("%u %p\n", entry->Key, entry->Data);
 233          entry = entry->Next;
 234       }
 235    }
 236 }
 237
 238
 239
 240 /*
 241  * Find a block of 'numKeys' adjacent unused hash keys.
 242  * Input:  table - the hash table
 243  *         numKeys - number of keys needed
 244  * Return:  starting key of free block or 0 if failure
 245  */
 246 GLuint _mesa_HashFindFreeKeyBlock(const struct _mesa_HashTable *table, GLuint numKeys)
 247 {
 248    GLuint maxKey = ~((GLuint) 0);
 249    if (maxKey - numKeys > table->MaxKey) {
 250       /* the quick solution */
 251       return table->MaxKey + 1;
 252    }
 253    else {
 254       /* the slow solution */
 255       GLuint freeCount = 0;
 256       GLuint freeStart = 1;
 257       GLuint key;
 258       for (key=1; key!=maxKey; key++) {
 259          if (_mesa_HashLookup(table, key)) {
 260             /* darn, this key is already in use */
 261             freeCount = 0;
 262             freeStart = key+1;
 263          }
 264          else {
 265             /* this key not in use, check if we've found enough */
 266             freeCount++;
 267             if (freeCount == numKeys) {
 268                return freeStart;
 269             }
 270          }
 271       }
 272       /* cannot allocate a block of numKeys consecutive keys */
 273       return 0;
 274    }
 275 }
 276
 277
 278
 279 #ifdef HASH_TEST_HARNESS
 280 int main(int argc, char *argv[])
 281 {
 282    int a, b, c;
 283    struct HashTable *t;
 284
 285    printf("&a = %p\n", &a);
 286    printf("&b = %p\n", &b);
 287
 288    t = _mesa_NewHashTable();
 289    _mesa_HashInsert(t, 501, &a);
 290    _mesa_HashInsert(t, 10, &c);
 291    _mesa_HashInsert(t, 0xfffffff8, &b);
 292    _mesa_HashPrint(t);
 293    printf("Find 501: %p\n", _mesa_HashLookup(t,501));
 294    printf("Find 1313: %p\n", _mesa_HashLookup(t,1313));
 295    printf("Find block of 100: %d\n", _mesa_HashFindFreeKeyBlock(t, 100));
 296    _mesa_DeleteHashTable(t);
 297
 298    return 0;
 299 }
 300 #endif