Ignore:
Timestamp:
Oct 5, 2011, 7:41:38 PM (8 years ago)
Author:
vla24
Message:

SymbolTable?: hash table implementation for paralel bitstream based length sorting (PBGS) now auto-resizes. Fixed flipBit function used by Div2 grouping strategy

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/lib/symtab/bitstream_hash_table.h

    r1462 r1518  
    2020#define DEBUG_BHT 0
    2121
    22 #define TABLE_SIZE 256
    23 #define TABLE_SIZE_MASK TABLE_SIZE-1
     22#define DEFAULT_TABLE_SIZE 256
     23#define TABLE_SIZE_MASK(x) x-1
     24
     25#include <string.h>
     26#include <stdlib.h>
     27
     28struct CHAIN {
     29    const char* key;
     30    int hashvalue;
     31    struct CHAIN* next;
     32    unsigned int GID;
     33    unsigned int lgth;
     34};
    2435
    2536class BitStreamHashTable
     
    3344    unsigned int Lookup_Name_17(char * name, const int hashvalue, int L);
    3445
    35     void Insert_Name(char * name, const int hashvalue, const unsigned int gid);
    36     void Insert_Name(char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth);
     46    void Insert_Name(const char * name, const int hashvalue, const unsigned int gid);
     47    void Insert_Name(const char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth);
    3748
    3849    // DEBUG FUNCTIONS
     
    4051
    4152protected:
    42     struct CHAIN {
    43         const char* key;
    44         struct CHAIN* next;
    45         unsigned int GID;
    46         unsigned int lgth;
    47     };
    48 
    4953    CHAIN ** g_table;
    50     inline unsigned int getIndex(const int hashvalue);
     54    unsigned int g_tableSize;
     55    inline unsigned int getBucket(const int hashvalue, unsigned int g_tableSize);
    5156
    5257private:
    53     void free_chain(CHAIN* chain);
     58    void free_chain(CHAIN* &chain);
     59    void expandHashTable();
     60
     61    inline CHAIN** allocateHashTable(unsigned int size);
     62    inline void deallocateHashTable(unsigned int size, CHAIN** &table);
     63    inline unsigned int nextTableSize();
     64    inline unsigned int chainLength(CHAIN* chain);
    5465};
    5566
    56 inline unsigned int BitStreamHashTable::getIndex(const int hashvalue)
     67inline unsigned int BitStreamHashTable::getBucket(const int hashvalue, unsigned int tableSize)
    5768{
    58     return hashvalue & TABLE_SIZE_MASK;
     69//    return hashvalue & TABLE_SIZE_MASK(tableSize);
     70    return hashvalue % tableSize;
     71}
     72
     73inline CHAIN** BitStreamHashTable::allocateHashTable(unsigned int size)
     74{
     75    CHAIN** table = (CHAIN**) calloc(size, sizeof(CHAIN*));
     76    memset(table, 0, g_tableSize*sizeof(CHAIN*));
     77    return table;
     78}
     79
     80inline void BitStreamHashTable::deallocateHashTable(unsigned int size, CHAIN** &table)
     81{
     82    for(unsigned int hash = 0; hash < size; hash++)
     83    {
     84        free_chain(table[hash]);
     85    }
     86    free(table);
     87}
     88
     89inline unsigned int BitStreamHashTable::nextTableSize()
     90{
     91    return g_tableSize << 1; // double the size
     92}
     93
     94unsigned int BitStreamHashTable::chainLength(CHAIN* chain)
     95{
     96   unsigned int items = 0;
     97   CHAIN* curr = chain;
     98   while (curr != NULL)
     99   {
     100       items++;
     101       curr = curr->next;
     102   }
     103   return items;
    59104}
    60105
Note: See TracChangeset for help on using the changeset viewer.