src/mesa/main/hash.c

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