src/mesa/main/hash.c

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