Ignore:
Timestamp:
Aug 26, 2011, 3:33:01 PM (8 years ago)
Author:
vla24
Message:

Symbol Table: Refactored code. Split HashTable? implementation into 3 classes according to grouping strategies.

File:
1 edited

Legend:

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

    r1387 r1391  
    66 * BitStreamDivHashTable accepts a hashvalue to insert or lookup for a key.
    77 * This hash table is designed specifically for Parallel Bitstream-Based Length Sorting
    8  * Division by 2 grouping strategy.
     8 * log grouping strategy.
     9 *
     10 * Division group sorting        f(L) = floor( (L-1)/2^k )
    911 *
    1012 */
     
    1517#define DEBUG_BHT 0
    1618
    17 #define USE_FUNCTION_TEMPLATES
    18 #define TABLE_SIZE 256
    19 #define TABLE_SIZE_MASK TABLE_SIZE-1
    20 
    21 // Define either one of grouping functions
    22 // Each grouping strategy use different comparison strategy
    23 //#define USE_IDENTITY_SORT     // f(L) = L
    24 //#define USE_LOG_SORT          // f(L) = ceil (log(L))
    25 #define USE_DIV_SORT            // f(L) = floor( (L-1)/2^k )
    26 
    27 //#define USE_MASK_COMPARE    //Comparison using masking technique.
    28                               //This technique only applies to USE_LOG_SORT
    29 
    3019#include <stdlib.h>
    31 #include "pbgs_div_utilities.h"
     20#include "bitstream_hash_table.h"
     21#include "pbgs_utilities.h"
    3222#include "ls_symbol_table_util.h"
    3323#include "limits.h"
    3424
    35 class BitStreamDivHashTable
     25class BitStreamDivHashTable : public BitStreamHashTable
    3626{
    37     struct CHAIN {
    38         const char* key;
    39         struct CHAIN* next;
    40         unsigned int GID;
    41         unsigned int lgth;
    42     };
    43 
    4427public:
    45     BitStreamDivHashTable()
    46     {
    47         g_table = (CHAIN**) calloc(TABLE_SIZE, sizeof(CHAIN*));
    48         memset(g_table, 0, TABLE_SIZE*sizeof(CHAIN*));
    49     }
    50 
    51     ~BitStreamDivHashTable()
    52     {
    53         for(int hash = 0; hash < TABLE_SIZE; hash++)
    54         {
    55             free_chain(g_table[hash]);
    56         }
    57         free(g_table);
    58     }
    59 
    6028
    6129    //Returns 0 upon failure
     
    6937    // character is a delimiter
    7038    template <int L> inline unsigned int Lookup_Name_Delimiter(char * name, const int hashvalue);
    71 
    72     // Symbol length > 16
    73     inline unsigned int Lookup_Name(char * name, const int hashvalue, int L);
    74 
    75     inline void Insert_Name(char * name, const int hashvalue, const unsigned int gid);
    76     inline void Insert_Name(char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth);
    77 
    78     // DEBUG FUNCTION
    79     void Print_Symbol_Table_Distribution();
    80 
    81     void free_chain(CHAIN* chain);
    82 
    83 private:
    84     CHAIN ** g_table;
    85 
    86     inline void SetTableSize(unsigned int table_bits, unsigned int table_bits_factor);
    87 
    88     inline unsigned int getIndex(const int hashvalue);
    89 
    90     inline unsigned int NextLog2(unsigned int x);
    9139};
    9240
     
    10149        printf ("Check symbol: %s\n", chain->key);
    10250#endif
    103         if( equal_compare <L> ((unsigned char*)chain->key, (unsigned char*)name) )
     51        if( div_equal_compare <L> ((unsigned char*)chain->key, (unsigned char*)name) )
    10452        {
    10553#if DEBUG_BHT
     
    12775        printf ("Check key: %s\n", chain->key);
    12876#endif
    129         if( equal_compare <L> ((unsigned char*)chain->key, (unsigned char*)name) )
     77        if( div_equal_compare <L> ((unsigned char*)chain->key, (unsigned char*)name) )
    13078        {
    13179#if DEBUG_BHT
     
    152100        printf ("Check key: %s\n", chain->key);
    153101#endif
    154         if( equal_compare <L> ((unsigned char*)chain->key, (unsigned char*)name) )
     102        if( div_equal_compare <L> ((unsigned char*)chain->key, (unsigned char*)name) )
    155103        {
    156104#if DEBUG_BHT
     
    167115}
    168116
    169 // Use this method if L > 16
    170 inline unsigned int BitStreamDivHashTable::Lookup_Name(char * name, const int hashvalue, int L)
    171 {
    172     unsigned int hash = getIndex(hashvalue);
    173 
    174     // Look up the value in the chain
    175     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
    176 #if DEBUG_BHT
    177         printf ("Check symbol: %s\n", chain->key);
    178 #endif
    179         if( simd_compare ((unsigned char*)chain->key, (unsigned char*)name, L) )
    180         {
    181 #if DEBUG_BHT
    182             printf ("Found GID: %i\n", chain->GID);
    183 #endif
    184             return chain->GID;
    185         }
    186     }
    187 
    188 #if DEBUG_BHT
    189     printf ("Not Found GID: %i\n", 0);
    190 #endif
    191     return 0;
    192 }
    193 
    194 inline void BitStreamDivHashTable::Insert_Name(char * name, const int hashvalue, const unsigned int gid)
    195 {
    196     unsigned int hash = getIndex(hashvalue);
    197 
    198     // If it was not found, add it
    199     CHAIN* next = g_table[hash];
    200     g_table[hash] = (CHAIN*) malloc(sizeof(CHAIN*));
    201     g_table[hash]->next = next;
    202     g_table[hash]->key = name;
    203     g_table[hash]->GID = gid;
    204 
    205 #if DEBUG_BHT
    206     printf ("Given GID: %i | Stored GID: %i\n", gid, g_table[hash]->GID);
    207 #endif
    208 }
    209 
    210 inline void BitStreamDivHashTable::Insert_Name(char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth)
    211 {
    212     unsigned int hash = getIndex(hashvalue);
    213 
    214     // If it was not found, add it
    215     CHAIN* next = g_table[hash];
    216     g_table[hash] = (CHAIN*) malloc(sizeof(CHAIN*));
    217     g_table[hash]->next = next;
    218     g_table[hash]->key = name;
    219     g_table[hash]->GID = gid;
    220     g_table[hash]->lgth = lgth;
    221 
    222 #if DEBUG_BHT
    223     printf ("Given GID: %i | Stored GID: %i\n", gid, g_table[hash]->GID);
    224 #endif
    225 }
    226 
    227 inline unsigned int BitStreamDivHashTable::getIndex(const int hashvalue)
    228 {
    229     return hashvalue & TABLE_SIZE_MASK;
    230 }
    231 
    232 inline unsigned int BitStreamDivHashTable::NextLog2(unsigned int x)
    233 {
    234     // Henry Warren, "Hacker's Delight", ch. 5.3
    235     if(x <= 1) return x;
    236     x--;
    237     unsigned int n = 0;
    238     unsigned int y;
    239     y = x >>16; if(y) {n += 16; x = y;}
    240     y = x >> 8; if(y) {n +=  8; x = y;}
    241     y = x >> 4; if(y) {n +=  4; x = y;}
    242     y = x >> 2; if(y) {n +=  2; x = y;}
    243     y = x >> 1; if(y) return n + 2;
    244     return n + x;
    245 }
    246 
    247 void BitStreamDivHashTable::Print_Symbol_Table_Distribution()
    248 {
    249     for(int hash = 0; hash < TABLE_SIZE; hash++)
    250     {
    251         int items = 0;
    252         for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next)
    253         {
    254             items++;
    255         }
    256         if (items >= 1)
    257         {
    258             fprintf (stderr, "\tBucket: %i | #items: %i\n", hash, items);
    259         }
    260     }
    261 }
    262 
    263 void BitStreamDivHashTable::free_chain(CHAIN* chain)
    264 {
    265     if (chain == NULL)
    266     {
    267         return;
    268     }
    269 
    270     if (chain->next != NULL)
    271     {
    272         free_chain(chain->next);
    273     }
    274     free(chain);
    275     chain = NULL;
    276 }
    277 
    278 
    279117#endif // BITSTREAM_DIV_HASH_TABLE_H
Note: See TracChangeset for help on using the changeset viewer.