home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / mesa5.zip / mesa5src.zip / MesaDLL / hash.cpp < prev    next >
C/C++ Source or Header  |  2002-10-24  |  8KB  |  324 lines
  1. /* $Id: hash.c,v 1.14 2002/10/24 23:57:21 brianp Exp $ */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  4.1
  6.  *
  7.  * Copyright (C) 1999-2002  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. #include "glheader.h"
  28. #include "imports.h"
  29. #include "glthread.h"
  30. #include "hash.h"
  31. #include "context.h"
  32.  
  33.  
  34. /**
  35.  * \file hash.c
  36.  * \brief Generic hash table.  Used for display lists and texture objects.
  37.  * The hash functions are thread-safe.
  38.  * \author Brian Paul
  39.  * \note key=0 is illegal
  40.  */
  41.  
  42.  
  43. #define TABLE_SIZE 1023  /**< Size of lookup table/array */
  44.  
  45. /**
  46.  * An entry in the hash table.  This struct is private to this file.
  47.  */
  48. struct HashEntry {
  49.    GLuint Key;             /**< the entry's key */
  50.    void *Data;             /**< the entry's data */
  51.    struct HashEntry *Next; /**< pointer to next entry */
  52. };
  53.  
  54. /**
  55.  * The hashtable data structure.  This is an opaque types (it's not
  56.  * defined in the .h file).
  57.  */
  58. struct _mesa_HashTable {
  59.    struct HashEntry *Table[TABLE_SIZE];  /**< the lookup table */
  60.    GLuint MaxKey;                        /**< highest key inserted so far */
  61.    _glthread_Mutex Mutex;                /**< mutual exclusion lock */
  62. };
  63.  
  64.  
  65.  
  66. /**
  67.  * Create a new hash table.
  68.  * \return pointer to a new, empty hash table.
  69.  */
  70. struct _mesa_HashTable *_mesa_NewHashTable(void)
  71. {
  72.    struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable);
  73.    if (table) {
  74.       _glthread_INIT_MUTEX(table->Mutex);
  75.    }
  76.    return table;
  77. }
  78.  
  79.  
  80.  
  81. /**
  82.  * Delete a hash table.
  83.  * \param table - the hash table to delete
  84.  */
  85. void _mesa_DeleteHashTable(struct _mesa_HashTable *table)
  86. {
  87.    GLuint i;
  88.    assert(table);
  89.    for (i=0;i<TABLE_SIZE;i++) {
  90.       struct HashEntry *entry = table->Table[i];
  91.       while (entry) {
  92.      struct HashEntry *next = entry->Next;
  93.      FREE(entry);
  94.      entry = next;
  95.       }
  96.    }
  97.    FREE(table);
  98. }
  99.  
  100.  
  101.  
  102. /**
  103.  * Lookup an entry in the hash table.
  104.  * \param table - the hash table
  105.  * \param key - the key
  106.  * \return pointer to user's data or NULL if key not in table
  107.  */
  108. void *_mesa_HashLookup(const struct _mesa_HashTable *table, GLuint key)
  109. {
  110.    GLuint pos;
  111.    const struct HashEntry *entry;
  112.  
  113.    assert(table);
  114.    assert(key);
  115.  
  116.    pos = key & (TABLE_SIZE-1);
  117.    entry = table->Table[pos];
  118.    while (entry) {
  119.       if (entry->Key == key) {
  120.      return entry->Data;
  121.       }
  122.       entry = entry->Next;
  123.    }
  124.    return NULL;
  125. }
  126.  
  127.  
  128.  
  129. /**
  130.  * Insert into the hash table.  If an entry with this key already exists
  131.  * we'll replace the existing entry.
  132.  * \param table - the hash table
  133.  * \param key - the key (not zero)
  134.  * \param data - pointer to user data
  135.  */
  136. void _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data)
  137. {
  138.    /* search for existing entry with this key */
  139.    GLuint pos;
  140.    struct HashEntry *entry;
  141.  
  142.    assert(table);
  143.    assert(key);
  144.  
  145.    _glthread_LOCK_MUTEX(table->Mutex);
  146.  
  147.    if (key > table->MaxKey)
  148.       table->MaxKey = key;
  149.  
  150.    pos = key & (TABLE_SIZE-1);
  151.    entry = table->Table[pos];
  152.    while (entry) {
  153.       if (entry->Key == key) {
  154.          /* replace entry's data */
  155.      entry->Data = data;
  156.          _glthread_UNLOCK_MUTEX(table->Mutex);
  157.      return;
  158.       }
  159.       entry = entry->Next;
  160.    }
  161.  
  162.    /* alloc and insert new table entry */
  163.    entry = MALLOC_STRUCT(HashEntry);
  164.    entry->Key = key;
  165.    entry->Data = data;
  166.    entry->Next = table->Table[pos];
  167.    table->Table[pos] = entry;
  168.  
  169.    _glthread_UNLOCK_MUTEX(table->Mutex);
  170. }
  171.  
  172.  
  173.  
  174. /**
  175.  * Remove an entry from the hash table.
  176.  * \param table - the hash table
  177.  * \param key - key of entry to remove
  178.  */
  179. void _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)
  180. {
  181.    GLuint pos;
  182.    struct HashEntry *entry, *prev;
  183.  
  184.    assert(table);
  185.    assert(key);
  186.  
  187.    _glthread_LOCK_MUTEX(table->Mutex);
  188.  
  189.    pos = key & (TABLE_SIZE-1);
  190.    prev = NULL;
  191.    entry = table->Table[pos];
  192.    while (entry) {
  193.       if (entry->Key == key) {
  194.          /* found it! */
  195.          if (prev) {
  196.             prev->Next = entry->Next;
  197.          }
  198.          else {
  199.             table->Table[pos] = entry->Next;
  200.          }
  201.          FREE(entry);
  202.          _glthread_UNLOCK_MUTEX(table->Mutex);
  203.      return;
  204.       }
  205.       prev = entry;
  206.       entry = entry->Next;
  207.    }
  208.  
  209.    _glthread_UNLOCK_MUTEX(table->Mutex);
  210. }
  211.  
  212.  
  213.  
  214. /**
  215.  * Get the key of the "first" entry in the hash table.
  216.  * This is used in the course of deleting all display lists when
  217.  * a context is destroyed.
  218.  * \param table - the hash table
  219.  * \return key for the "first" entry in the hash table.
  220.  */
  221. GLuint _mesa_HashFirstEntry(struct _mesa_HashTable *table)
  222. {
  223.    GLuint pos;
  224.    assert(table);
  225.    _glthread_LOCK_MUTEX(table->Mutex);
  226.    for (pos=0; pos < TABLE_SIZE; pos++) {
  227.       if (table->Table[pos]) {
  228.          _glthread_UNLOCK_MUTEX(table->Mutex);
  229.          return table->Table[pos]->Key;
  230.       }
  231.    }
  232.    _glthread_UNLOCK_MUTEX(table->Mutex);
  233.    return 0;
  234. }
  235.  
  236.  
  237.  
  238. /**
  239.  * Dump contents of hash table for debugging.
  240.  * \param table - the hash table
  241.  */
  242. void _mesa_HashPrint(const struct _mesa_HashTable *table)
  243. {
  244.    GLuint i;
  245.    assert(table);
  246.    for (i=0;i<TABLE_SIZE;i++) {
  247.       const struct HashEntry *entry = table->Table[i];
  248.       while (entry) {
  249.      _mesa_debug(NULL, "%u %p\n", entry->Key, entry->Data);
  250.      entry = entry->Next;
  251.       }
  252.    }
  253. }
  254.  
  255.  
  256.  
  257. /**
  258.  * Find a block of 'numKeys' adjacent unused hash keys.
  259.  * \param table - the hash table
  260.  * \param numKeys - number of keys needed
  261.  * \return Starting key of free block or 0 if failure
  262.  */
  263. GLuint _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys)
  264. {
  265.    GLuint maxKey = ~((GLuint) 0);
  266.    _glthread_LOCK_MUTEX(table->Mutex);
  267.    if (maxKey - numKeys > table->MaxKey) {
  268.       /* the quick solution */
  269.       _glthread_UNLOCK_MUTEX(table->Mutex);
  270.       return table->MaxKey + 1;
  271.    }
  272.    else {
  273.       /* the slow solution */
  274.       GLuint freeCount = 0;
  275.       GLuint freeStart = 1;
  276.       GLuint key;
  277.       for (key=1; key!=maxKey; key++) {
  278.      if (_mesa_HashLookup(table, key)) {
  279.         /* darn, this key is already in use */
  280.         freeCount = 0;
  281.         freeStart = key+1;
  282.      }
  283.      else {
  284.         /* this key not in use, check if we've found enough */
  285.         freeCount++;
  286.         if (freeCount == numKeys) {
  287.                _glthread_UNLOCK_MUTEX(table->Mutex);
  288.            return freeStart;
  289.         }
  290.      }
  291.       }
  292.       /* cannot allocate a block of numKeys consecutive keys */
  293.       _glthread_UNLOCK_MUTEX(table->Mutex);
  294.       return 0;
  295.    }
  296. }
  297.  
  298.  
  299.  
  300. #ifdef HASH_TEST_HARNESS
  301. int main(int argc, char *argv[])
  302. {
  303.    int a, b, c;
  304.    struct HashTable *t;
  305.  
  306.    _mesa_printf("&a = %p\n", &a);
  307.    _mesa_printf("&b = %p\n", &b);
  308.  
  309.    t = _mesa_NewHashTable();
  310.    _mesa_HashInsert(t, 501, &a);
  311.    _mesa_HashInsert(t, 10, &c);
  312.    _mesa_HashInsert(t, 0xfffffff8, &b);
  313.    _mesa_HashPrint(t);
  314.  
  315.    _mesa_printf("Find 501: %p\n", _mesa_HashLookup(t,501));
  316.    _mesa_printf("Find 1313: %p\n", _mesa_HashLookup(t,1313));
  317.    _mesa_printf("Find block of 100: %d\n", _mesa_HashFindFreeKeyBlock(t, 100));
  318.  
  319.    _mesa_DeleteHashTable(t);
  320.  
  321.    return 0;
  322. }
  323. #endif
  324.