home *** CD-ROM | disk | FTP | other *** search
/ Amiga Magazin: Amiga-CD 2000 April & May / AMIGA_2000_04.iso / patches / mesa3.1 / mesa-3_1.lha / src / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  2000-01-07  |  6.3 KB  |  296 lines
  1. /* $Id: hash.c,v 1.3.2.1 2000/01/04 08:15:26 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:  starting 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 = 1;
  252.       GLuint key;
  253.       for (key=1; 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
  296.