src/mesa/main/hash.c

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