Changeset 1518 for trunk/lib


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

Location:
trunk/lib/symtab
Files:
6 edited

Legend:

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

    r1391 r1518  
    4242        inline unsigned int BitStreamDivHashTable::Lookup_Name(char * name, const int hashvalue)
    4343{
    44     unsigned int hash = getIndex(hashvalue);
     44    unsigned int bucket = getBucket(hashvalue, g_tableSize);
    4545
    4646    // Look up the value in the chain
    47     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
     47    for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
    4848#if DEBUG_BHT
    4949        printf ("Check symbol: %s\n", chain->key);
     
    6868        inline unsigned int BitStreamDivHashTable::Lookup_Name_Delimiter(char * name, const int hashvalue)
    6969{
    70     unsigned int hash = getIndex(hashvalue);
     70    unsigned int bucket = getBucket(hashvalue, g_tableSize);
    7171
    7272    // Look up the value in the chain
    73     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
     73    for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
    7474#if DEBUG_BHT
    7575        printf ("Check key: %s\n", chain->key);
     
    8585
    8686    // Flip the last bit of the hash value
    87     unsigned int flipped_hash = getIndex(flipLastBit<L>(hashvalue));
     87    unsigned int newBucket = getBucket(flipBit<L+1>(hashvalue), g_tableSize);
     88
    8889#if DEBUG_BHT
    89         printf ("hash: %i | flipped_hash %i\n", hash, flipped_hash);
     90    print_general_register_32 ("hash", hashvalue);
     91    print_general_register_32 ("flipped hash", flipBit<L+1>(hashvalue));
     92    printf ("\n");
    9093#endif
    9194    // FIXME: Should we check?
    92     if (hash == flipped_hash)
     95    if (bucket == newBucket)
    9396    {
    9497        return 0;
     
    9699
    97100    // Look up the value in the chain
    98     for(CHAIN* chain = g_table[flipped_hash]; chain != NULL; chain = chain->next) {
     101    for(CHAIN* chain = g_table[newBucket]; chain != NULL; chain = chain->next) {
    99102#if DEBUG_BHT
    100103        printf ("Check key: %s\n", chain->key);
  • trunk/lib/symtab/bitstream_hash_table.cpp

    r1462 r1518  
     1#include <stdlib.h>
     2#include <stdio.h>
    13#include "bitstream_hash_table.h"
    2 #include <stdlib.h>
    34#include "pbgs_utilities.h"
    45#include "ls_symbol_table_util.h"
    56
     7#define MAX_CHAIN 2
     8
    69BitStreamHashTable::BitStreamHashTable()
     10    :g_tableSize(DEFAULT_TABLE_SIZE)
    711{
    8     g_table = (CHAIN**) calloc(TABLE_SIZE, sizeof(CHAIN*));
    9     memset(g_table, 0, TABLE_SIZE*sizeof(CHAIN*));
     12    g_table = allocateHashTable(g_tableSize);
    1013}
    1114
    1215BitStreamHashTable::~BitStreamHashTable()
    1316{
    14     for(int hash = 0; hash < TABLE_SIZE; hash++)
    15     {
    16         free_chain(g_table[hash]);
    17     }
    18     free(g_table);
     17    deallocateHashTable(g_tableSize, g_table);
    1918}
    2019
     
    2221unsigned int BitStreamHashTable::Lookup_Name_17(char * name, const int hashvalue, int L)
    2322{
    24     unsigned int hash = getIndex(hashvalue);
     23    unsigned int bucket = getBucket(hashvalue, g_tableSize);
    2524
    2625    // Look up the value in the chain
    27     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
     26    for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
    2827#if DEBUG_BHT
    2928        printf ("Check symbol: %s\n", chain->key);
     
    4443}
    4544
    46 void BitStreamHashTable::Insert_Name(char * name, const int hashvalue, const unsigned int gid)
     45void BitStreamHashTable::Insert_Name(const char * name, const int hashvalue, const unsigned int gid)
    4746{
    48     unsigned int hash = getIndex(hashvalue);
     47    unsigned int bucket = getBucket(hashvalue, g_tableSize);
    4948
    5049    // If it was not found, add it
    51     CHAIN* next = g_table[hash];
    52     g_table[hash] = (CHAIN*) malloc(sizeof(CHAIN*));
    53     g_table[hash]->next = next;
    54     g_table[hash]->key = name;
    55     g_table[hash]->GID = gid;
     50    CHAIN* next = g_table[bucket];
     51    unsigned int chainlgth = chainLength(next);
     52    if (chainlgth == MAX_CHAIN)
     53    {
     54        //current chain length is maximum, expand the table
     55        expandHashTable();
     56        bucket = getBucket(hashvalue, g_tableSize);
     57        next = g_table[bucket];
     58    }
     59    CHAIN* curr = (CHAIN*) malloc(sizeof(CHAIN));
     60    curr->next = next;
     61    curr->key = name;
     62    curr->hashvalue = hashvalue;
     63    curr->GID = gid;
     64    g_table[bucket] = curr;
    5665
    5766#if DEBUG_BHT
     
    6069}
    6170
    62 void BitStreamHashTable::Insert_Name(char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth)
     71void BitStreamHashTable::Insert_Name(const char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth)
    6372{
    64     unsigned int hash = getIndex(hashvalue);
     73    unsigned int bucket = getBucket(hashvalue, g_tableSize);
    6574
    6675    // If it was not found, add it
    67     CHAIN* next = g_table[hash];
    68     g_table[hash] = (CHAIN*) malloc(sizeof(CHAIN*));
    69     g_table[hash]->next = next;
    70     g_table[hash]->key = name;
    71     g_table[hash]->GID = gid;
    72     g_table[hash]->lgth = lgth;
     76    CHAIN* next = g_table[bucket];
     77    unsigned int chainlgth = chainLength(next);
     78    if (chainlgth == MAX_CHAIN)
     79    {
     80        //current chain length is maximum, expand the table
     81        expandHashTable();
     82        bucket = getBucket(hashvalue, g_tableSize);
     83        next = g_table[bucket];
     84    }
     85    CHAIN* curr = (CHAIN*) malloc(sizeof(CHAIN));
     86    curr->next = next;
     87    curr->key = name;
     88    curr->hashvalue = hashvalue;
     89    curr->GID = gid;
     90    curr->lgth = lgth;
     91    g_table[bucket] = curr;
    7392
    7493#if DEBUG_BHT
     
    7796}
    7897
     98void BitStreamHashTable::expandHashTable()
     99{
     100    unsigned int tempTableSize = nextTableSize();
     101    CHAIN** tempTable = allocateHashTable(tempTableSize);
     102
     103    for(unsigned int bucket = 0; bucket < g_tableSize; bucket++)
     104    {
     105        CHAIN* curr = g_table[bucket];
     106        g_table[bucket] = NULL;
     107
     108        while (curr != NULL)
     109        {
     110            CHAIN* next = curr->next;
     111
     112            //insert to new table
     113            unsigned int tempIndex = getBucket(curr->hashvalue, tempTableSize);
     114            CHAIN* tempNext = tempTable[tempIndex];
     115            curr->next = tempNext;
     116            tempTable[tempIndex] = curr;
     117
     118            //update curr
     119            curr = next;
     120        }
     121    }
     122
     123    // Deallocate g_table
     124    deallocateHashTable(g_tableSize, g_table);
     125
     126    // Reassign g_table
     127    g_table = tempTable;
     128    g_tableSize = tempTableSize;
     129}
     130
    79131void BitStreamHashTable::Print_Symbol_Table_Distribution()
    80132{
    81     for(int hash = 0; hash < TABLE_SIZE; hash++)
     133    for(unsigned int bucket = 0; bucket < g_tableSize; bucket++)
    82134    {
    83         int items = 0;
    84         for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next)
    85         {
    86             items++;
    87         }
     135        int items = chainLength(g_table[bucket]);
    88136        if (items >= 1)
    89137        {
    90             fprintf (stderr, "\tBucket: %i | #items: %i\n", hash, items);
     138            fprintf (stderr, "\tBucket: %i | #items: %i\n", bucket, items);
    91139        }
    92140    }
    93141}
    94142
    95 void BitStreamHashTable::free_chain(CHAIN* chain)
     143void BitStreamHashTable::free_chain(CHAIN* &chain)
    96144{
    97145    if (chain == NULL)
     
    99147        return;
    100148    }
    101 
    102     if (chain->next != NULL)
    103     {
    104         free_chain(chain->next);
    105     }
    106149    free(chain);
    107150    chain = NULL;
  • 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
  • trunk/lib/symtab/bitstream_id_hash_table.h

    r1462 r1518  
    3030        unsigned int BitStreamIdentityHashTable::Lookup_Name(char * name, const int hashvalue)
    3131{
    32     unsigned int hash = getIndex(hashvalue);
     32    unsigned int bucket = getBucket(hashvalue, g_tableSize);
    3333
    3434    // Look up the value in the chain
    35     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
     35    for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
    3636#if DEBUG_BHT
    3737        printf ("Check symbol: %s\n", chain->key);
  • trunk/lib/symtab/bitstream_log_hash_table.h

    r1462 r1518  
    4444inline unsigned int BitStreamLogHashTable::Lookup_Name_1(char * name, const int hashvalue)
    4545{
    46     unsigned int hash = getIndex(hashvalue);
     46    unsigned int bucket = getBucket(hashvalue, g_tableSize);
    4747
    4848    // Look up the value in the chain
    49     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
     49    for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
    5050#if DEBUG_BHT
    5151        printf ("Check symbol: %s\n", chain->key);
     
    6868inline unsigned int BitStreamLogHashTable::Lookup_Name_2(char * name, const int hashvalue)
    6969{
    70     unsigned int hash = getIndex(hashvalue);
     70    unsigned int bucket = getBucket(hashvalue, g_tableSize);
    7171
    7272    // Look up the value in the chain
    73     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
     73    for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
    7474#if DEBUG_BHT
    7575        printf ("Check symbol: %s\n", chain->key);
     
    9393inline unsigned int BitStreamLogHashTable::Lookup_Name_4(char * name, const int hashvalue, int L)
    9494{
    95     unsigned int hash = getIndex(hashvalue);
     95    unsigned int bucket = getBucket(hashvalue, g_tableSize);
    9696
    9797    // Look up the value in the chain
    98     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
     98    for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
    9999#if DEBUG_BHT
    100100        printf ("Check symbol: %s\n", chain->key);
     
    124124inline unsigned int BitStreamLogHashTable::Lookup_Name_8(char * name, const int hashvalue, int L)
    125125{
    126     unsigned int hash = getIndex(hashvalue);
     126    unsigned int bucket = getBucket(hashvalue, g_tableSize);
    127127
    128128    // Look up the value in the chain
    129     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
     129    for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
    130130#if DEBUG_BHT
    131131        printf ("Check symbol: %s\n", chain->key);
     
    149149inline unsigned int BitStreamLogHashTable::Lookup_Name_16(char * name, const int hashvalue, int L)
    150150{
    151     unsigned int hash = getIndex(hashvalue);
     151    unsigned int bucket = getBucket(hashvalue, g_tableSize);
    152152
    153153    // Look up the value in the chain
    154     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
     154    for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
    155155#if DEBUG_BHT
    156156        printf ("Check symbol: %s\n", chain->key);
  • trunk/lib/symtab/pbgs_utilities.h

    r1462 r1518  
    147147
    148148
     149// flip bit at position L
    149150template <size_t L>
    150         inline int flipLastBit(const int value);
     151        inline int flipBit(const int value);
    151152
    152 template <> inline int flipLastBit<1>(const int value)
     153template <> inline int flipBit<2>(const int value)
    153154{
    154     return (value & 0x2) ^ value;
     155    return value ^ 0x2;
    155156}
    156157
    157 template <> inline int flipLastBit<3>(const int value)
     158template <> inline int flipBit<4>(const int value)
    158159{
    159     return (value & 0x8) ^ value;
     160    return value ^ 0x8;
    160161}
    161162
    162 template <> inline int flipLastBit<5>(const int value)
     163template <> inline int flipBit<6>(const int value)
    163164{
    164     return (value & 0x20) ^ value;
     165    return value ^ 0x20;
    165166}
    166167
    167 template <> inline int flipLastBit<7>(const int value)
     168template <> inline int flipBit<8>(const int value)
    168169{
    169     return (value & 0x80) ^ value;
     170    return value ^ 0x80;
    170171}
    171172
    172 template <> inline int flipLastBit<9>(const int value)
     173template <> inline int flipBit<10>(const int value)
    173174{
    174     return (value & 0x200) ^ value;
     175    return value ^ 0x200;
    175176}
    176177
    177 template <> inline int flipLastBit<11>(const int value)
     178template <> inline int flipBit<12>(const int value)
    178179{
    179     return (value & 0x800) ^ value;
     180    return value ^ 0x800;
    180181}
    181182
    182 template <> inline int flipLastBit<13>(const int value)
     183template <> inline int flipBit<14>(const int value)
    183184{
    184     return (value & 0x2000) ^ value;
     185    return value ^ 0x2000;
    185186}
    186187
    187 template <> inline int flipLastBit<15>(const int value)
     188template <> inline int flipBit<16>(const int value)
    188189{
    189     return (value & 0x8000) ^ value;
     190    return value ^ 0x8000;
    190191}
    191192#endif /* PBGS_DIV_UTILITIES_H_ */
Note: See TracChangeset for help on using the changeset viewer.