home *** CD-ROM | disk | FTP | other *** search
/ Magazyn Amiga 5 / MA_Cover_5.iso / ppc / mesa / src / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-01-31  |  6.2 KB  |  300 lines
  1. /* $Id: hash.c,v 1.3 1997/09/22 02:33:07 brianp Exp $ */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  2.5
  6.  * Copyright (C) 1995-1997  Brian Paul
  7.  *
  8.  * This library is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU Library General Public
  10.  * License as published by the Free Software Foundation; either
  11.  * version 2 of the License, or (at your option) any later version.
  12.  *
  13.  * This library is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16.  * Library General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU Library General Public
  19.  * License along with this library; if not, write to the Free
  20.  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  */
  22.  
  23.  
  24. /*
  25.  * $Log: hash.c,v $
  26.  * Revision 1.3  1997/09/22 02:33:07  brianp
  27.  * added HashRemove() and HashFirstEntry()
  28.  *
  29.  * Revision 1.2  1997/09/03 13:13:45  brianp
  30.  * added a few pointer casts
  31.  *
  32.  * Revision 1.1  1997/08/22 01:15:10  brianp
  33.  * Initial revision
  34.  *
  35.  */
  36.  
  37.  
  38. #ifdef PC_HEADER
  39. #include "all.h"
  40. #else
  41. #include <assert.h>
  42. #include <stdlib.h>
  43. #include <stdio.h>
  44. #include "hash.h"
  45. #endif
  46.  
  47.  
  48. /*
  49.  * Generic hash table.  Only dependency is the GLuint datatype.
  50.  *
  51.  * This is used to implement display list and texture object lookup.
  52.  * NOTE: key=0 is illegal.
  53.  */
  54.  
  55.  
  56. #define TABLE_SIZE 1001
  57.  
  58. struct HashEntry {
  59.    GLuint Key;
  60.    void *Data;
  61.    struct HashEntry *Next;
  62. };
  63.  
  64. struct HashTable {
  65.    struct HashEntry *Table[TABLE_SIZE];
  66.    GLuint MaxKey;
  67. };
  68.  
  69.  
  70.  
  71. /*
  72.  * Return pointer to a new, empty hash table.
  73.  */
  74. struct HashTable *NewHashTable(void)
  75. {
  76.    return (struct HashTable *) calloc(sizeof (struct HashTable), 1);
  77. }
  78.  
  79.  
  80.  
  81. /*
  82.  * Delete a hash table.
  83.  */
  84. void DeleteHashTable(struct HashTable *table)
  85. {
  86.    GLuint i;
  87.    assert(table);
  88.    for (i=0;i<TABLE_SIZE;i++) {
  89.       struct HashEntry *entry = table->Table[i];
  90.       while (entry) {
  91.      struct HashEntry *next = entry->Next;
  92.      free(entry);
  93.      entry = next;
  94.       }
  95.    }
  96.    free(table);
  97. }
  98.  
  99.  
  100.  
  101. /*
  102.  * Lookup an entry in the hash table.
  103.  * Input:  table - the hash table
  104.  *         key - the key
  105.  * Return:  user data pointer or NULL if key not in table
  106.  */
  107. void *HashLookup(const struct HashTable *table, GLuint key)
  108. {
  109.    GLuint pos;
  110.    struct HashEntry *entry;
  111.  
  112.    assert(table);
  113.    assert(key);
  114.  
  115.    pos = key % TABLE_SIZE;
  116.    entry = table->Table[pos];
  117.    while (entry) {
  118.       if (entry->Key == key) {
  119.      return entry->Data;
  120.       }
  121.       entry = entry->Next;
  122.    }
  123.    return NULL;
  124. }
  125.  
  126.  
  127.  
  128. /*
  129.  * Insert into the hash table.  If an entry with this key already exists
  130.  * we'll replace the existing entry.
  131.  * Input:  table - the hash table
  132.  *         key - the key (not zero)
  133.  *         data - pointer to user data
  134.  */
  135. void HashInsert(struct HashTable *table, GLuint key, void *data)
  136. {
  137.    /* search for existing entry with this key */
  138.    GLuint pos;
  139.    struct HashEntry *entry;
  140.  
  141.    assert(table);
  142.    assert(key);
  143.  
  144.    if (key > table->MaxKey)
  145.       table->MaxKey = key;
  146.  
  147.    pos = key % TABLE_SIZE;
  148.    entry = table->Table[pos];
  149.    while (entry) {
  150.       if (entry->Key == key) {
  151.          /* replace entry's data */
  152.      entry->Data = data;
  153.      return;
  154.       }
  155.       entry = entry->Next;
  156.    }
  157.  
  158.    /* alloc and insert new table entry */
  159.    entry = (struct HashEntry *) calloc(sizeof(struct HashEntry), 1);
  160.    entry->Key = key;
  161.    entry->Data = data;
  162.    entry->Next = table->Table[pos];
  163.    table->Table[pos] = entry;
  164. }
  165.  
  166.  
  167.  
  168. /*
  169.  * Remove an entry from the hash table.
  170.  * Input:  table - the hash table
  171.  *         key - key of entry to remove
  172.  */
  173. void HashRemove(struct HashTable *table, GLuint key)
  174. {
  175.    GLuint pos;
  176.    struct HashEntry *entry, *prev;
  177.  
  178.    assert(table);
  179.    assert(key);
  180.  
  181.    pos = key % TABLE_SIZE;
  182.    prev = NULL;
  183.    entry = table->Table[pos];
  184.    while (entry) {
  185.       if (entry->Key == key) {
  186.          /* found it! */
  187.          if (prev) {
  188.             prev->Next = entry->Next;
  189.          }
  190.          else {
  191.             table->Table[pos] = entry->Next;
  192.          }
  193.          free(entry);
  194.      return;
  195.       }
  196.       prev = entry;
  197.       entry = entry->Next;
  198.    }
  199. }
  200.  
  201.  
  202.  
  203. /*
  204.  * Return the key of the "first" entry in the hash table.
  205.  * By calling this function until zero is returned we can get
  206.  * the keys of all entries in the table.
  207.  */
  208. GLuint HashFirstEntry(const struct HashTable *table)
  209. {
  210.    GLuint pos;
  211.    assert(table);
  212.    for (pos=0; pos < TABLE_SIZE; pos++) {
  213.       if (table->Table[pos])
  214.          return table->Table[pos]->Key;
  215.    }
  216.    return 0;
  217. }
  218.  
  219.  
  220.  
  221. /*
  222.  * Dump contents of hash table for debugging.
  223.  */
  224. void HashPrint(const struct HashTable *table)
  225. {
  226.    GLuint i;
  227.    assert(table);
  228.    for (i=0;i<TABLE_SIZE;i++) {
  229.       struct HashEntry *entry = table->Table[i];
  230.       while (entry) {
  231.      printf("%u %p\n", entry->Key, entry->Data);
  232.      entry = entry->Next;
  233.       }
  234.    }
  235. }
  236.  
  237.  
  238.  
  239. /*
  240.  * Find a block of 'numKeys' adjacent unused hash keys.
  241.  * Input:  table - the hash table
  242.  *         numKeys - number of keys needed
  243.  * Return:  startint key of free block or 0 if failure
  244.  */
  245. GLuint HashFindFreeKeyBlock(const struct HashTable *table, GLuint numKeys)
  246. {
  247.    GLuint maxKey = ~0;
  248.    if (maxKey - numKeys > table->MaxKey) {
  249.       /* the quick solution */
  250.       return table->MaxKey + 1;
  251.    }
  252.    else {
  253.       /* the slow solution */
  254.       GLuint freeCount = 0;
  255.       GLuint freeStart = 0;
  256.       GLuint key;
  257.       for (key=0; key!=maxKey; key++) {
  258.      if (HashLookup(table, key)) {
  259.         /* darn, this key is already in use */
  260.         freeCount = 0;
  261.         freeStart = key+1;
  262.      }
  263.      else {
  264.         /* this key not in use, check if we've found enough */
  265.         freeCount++;
  266.         if (freeCount == numKeys) {
  267.            return freeStart;
  268.         }
  269.      }
  270.       }
  271.       /* cannot allocate a block of numKeys consecutive keys */
  272.       return 0;
  273.    }
  274. }
  275.  
  276.  
  277.  
  278. #ifdef HASH_TEST_HARNESS
  279. int main(int argc, char *argv[])
  280. {
  281.    int a, b, c;
  282.    struct HashTable *t;
  283.  
  284.    printf("&a = %p\n", &a);
  285.    printf("&b = %p\n", &b);
  286.  
  287.    t = NewHashTable();
  288.    HashInsert(t, 501, &a);
  289.    HashInsert(t, 10, &c);
  290.    HashInsert(t, 0xfffffff8, &b);
  291.    HashPrint(t);
  292.    printf("Find 501: %p\n", HashLookup(t,501));
  293.    printf("Find 1313: %p\n", HashLookup(t,1313));
  294.    printf("Find block of 100: %d\n", HashFindFreeKeyBlock(t, 100));
  295.    DeleteHashTable(t);
  296.  
  297.    return 0;
  298. }
  299. #endif
  300.