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_hash_table.h

    r1387 r1391  
    11/*
    2  * Created: 2011
     2 * Created on: 26-August-2011
    33 * Author: Vera Lukman
    44 *
    55 * This hash table is almost an exact copy of HashSymbolTable except that
    66 * BitStreamDivHashTable accepts a hashvalue to insert or lookup for a key.
    7  * This hash table is designed specifically for Parallel Bitstream-Based Length Sorting
    8  * identity and log grouping strategy.
     7 * This hash table is designed specifically for Parallel Bitstream-Based Length Sorting Symbol Table.
     8 * It is the base class of BitstreamIdentityHashTable, BitstreamLogHashTable and BitstreamDivHashTable.
     9 *
     10 * Each grouping strategy use different comparison strategy
     11 * Identity group sorting        f(L) = L
     12 * Log group sorting             f(L) = ceil (log(L))
     13 * Division group sorting        f(L) = floor( (L-1)/2^k )
    914 *
    1015 */
     
    1520#define DEBUG_BHT 0
    1621
    17 #define USE_FUNCTION_TEMPLATES
    1822#define TABLE_SIZE 256
    1923#define TABLE_SIZE_MASK TABLE_SIZE-1
    2024
    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 )
     25#include <stdlib.h>
     26#include "pbgs_utilities.h"
     27#include "ls_symbol_table_util.h"
    2628
    27 //#define USE_MASK_COMPARE    //Comparison using masking technique.
    28                             //This technique only applies to USE_LOG_SORT
    29 
    30 #include <stdlib.h>
    31 #include "equal_compare.h"
    32 #include "ls_symbol_table_util.h"
    33 #include "limits.h"
    3429
    3530class BitStreamHashTable
    3631{
     32
     33public:
     34    BitStreamHashTable();
     35    ~BitStreamHashTable();
     36
     37    // Symbol length > 16
     38    inline unsigned int Lookup_Name_17(char * name, const int hashvalue, int L);
     39
     40    inline void Insert_Name(char * name, const int hashvalue, const unsigned int gid);
     41    inline void Insert_Name(char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth);
     42
     43    // DEBUG FUNCTIONS
     44    void Print_Symbol_Table_Distribution();
     45
     46protected:
    3747    struct CHAIN {
    3848        const char* key;
     
    4252    };
    4353
    44 public:
    45     BitStreamHashTable()
    46     {
    47         g_table = (CHAIN**) calloc(TABLE_SIZE, sizeof(CHAIN*));
    48         memset(g_table, 0, TABLE_SIZE*sizeof(CHAIN*));
    49     }
    50 
    51     ~BitStreamHashTable()
    52     {
    53         for(int hash = 0; hash < TABLE_SIZE; hash++)
    54         {
    55             free_chain(g_table[hash]);
    56         }
    57         free(g_table);
    58     }
    59 
    60 
    61     //Returns 0 upon failure
    62 #if defined(USE_IDENTITY_SORT) || defined(USE_DIV_SORT)
    63     // Symbol length [1,32]
    64     template <int L> inline unsigned int Lookup_Name(char * name, const int hashvalue);
    65 #endif
    66 #if defined (USE_LOG_SORT)
    67     // Symbol length 1
    68     inline unsigned int Lookup_Name_1(char * name, const int hashvalue);
    69 
    70     // Symbol length 2
    71     inline unsigned int Lookup_Name_2(char * name, const int hashvalue);
    72 
    73     // Symbol length [3,4]
    74     inline unsigned int Lookup_Name_4(char * name, const int hashvalue, int L);
    75 
    76     // Symbol length [5,8]
    77     inline unsigned int Lookup_Name_8(char * name, const int hashvalue, int L);
    78 
    79     // Symbol length [9,16]
    80     inline unsigned int Lookup_Name_16(char * name, const int hashvalue, int L);
    81 #endif
    82 
    83     // Symbol length [17,32]
    84     inline unsigned int Lookup_Name_32(char * name, const int hashvalue, int L);
    85 
    86     // Symbol length > 32
    87     inline unsigned int Lookup_Name(char * name, const int hashvalue, int L);
    88 
    89     inline void Insert_Name(char * name, const int hashvalue, const unsigned int gid);
    90     inline void Insert_Name(char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth);
    91 
    92     // DEBUG FUNCTION
    93     void Print_Symbol_Table_Distribution();
    94 
    95     void free_chain(CHAIN* chain);
     54    CHAIN ** g_table;
     55    inline unsigned int getIndex(const int hashvalue);
    9656
    9757private:
    98     CHAIN ** g_table;
    99 
     58    void free_chain(CHAIN* chain);
    10059    inline void SetTableSize(unsigned int table_bits, unsigned int table_bits_factor);
    101 
    102     inline unsigned int getIndex(const int hashvalue);
    103 
    10460    inline unsigned int NextLog2(unsigned int x);
    10561};
    10662
    107 #if defined(USE_IDENTITY_SORT) || defined(USE_DIV_SORT)
    108 template <int L>
    109         inline unsigned int BitStreamHashTable::Lookup_Name(char * name, const int hashvalue)
     63BitStreamHashTable::BitStreamHashTable()
    11064{
    111     unsigned int hash = getIndex(hashvalue);
    112 
    113     // Look up the value in the chain
    114     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
    115 #if DEBUG_BHT
    116         printf ("Check symbol: %s\n", chain->key);
    117 #endif
    118         if( equal_compare <L> ((unsigned char*)chain->key, (unsigned char*)name) )
    119         {
    120 #if DEBUG_BHT
    121             printf ("Found GID: %i\n", chain->GID);
    122 #endif
    123             return chain->GID;
    124         }
    125     }
    126 
    127 #if DEBUG_BHT
    128     printf ("Not Found GID: %i\n", 0);
    129 #endif
    130     return 0;
    131 }
    132 #endif
    133 
    134 #if defined (USE_LOG_SORT)
    135 inline unsigned int BitStreamHashTable::Lookup_Name_1(char * name, const int hashvalue)
    136 {
    137     unsigned int hash = getIndex(hashvalue);
    138 
    139     // Look up the value in the chain
    140     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
    141 #if DEBUG_BHT
    142         printf ("Check symbol: %s\n", chain->key);
    143 #endif
    144         if( equal_compare_1 ((unsigned char*)chain->key, (unsigned char*)name) )
    145         {
    146 #if DEBUG_BHT
    147             printf ("Found GID: %i\n", chain->GID);
    148 #endif
    149             return chain->GID;
    150         }
    151     }
    152 
    153 #if DEBUG_BHT
    154     printf ("Not Found GID: %i\n", 0);
    155 #endif
    156     return 0;
     65    g_table = (CHAIN**) calloc(TABLE_SIZE, sizeof(CHAIN*));
     66    memset(g_table, 0, TABLE_SIZE*sizeof(CHAIN*));
    15767}
    15868
    159 inline unsigned int BitStreamHashTable::Lookup_Name_2(char * name, const int hashvalue)
     69BitStreamHashTable::~BitStreamHashTable()
    16070{
    161     unsigned int hash = getIndex(hashvalue);
    162 
    163     // Look up the value in the chain
    164     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
    165 #if DEBUG_BHT
    166         printf ("Check symbol: %s\n", chain->key);
    167 #endif
    168         if( equal_compare_2 ((unsigned char*)chain->key, (unsigned char*)name) )
    169         {
    170 #if DEBUG_BHT
    171             printf ("Found GID: %i\n", chain->GID);
    172 #endif
    173             return chain->GID;
    174         }
     71    for(int hash = 0; hash < TABLE_SIZE; hash++)
     72    {
     73        free_chain(g_table[hash]);
    17574    }
    176 
    177 #if DEBUG_BHT
    178     printf ("Not Found GID: %i\n", 0);
    179 #endif
    180     return 0;
     75    free(g_table);
    18176}
    18277
    183 // Use this method if L is in [3,4]
    184 inline unsigned int BitStreamHashTable::Lookup_Name_4(char * name, const int hashvalue, int L)
    185 {
    186     unsigned int hash = getIndex(hashvalue);
    187 
    188     // Look up the value in the chain
    189     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
    190 #if DEBUG_BHT
    191         printf ("Check symbol: %s\n", chain->key);
    192 #endif
    193 
    194 #ifdef USE_MASK_COMPARE
    195         if( equal_compare_4 ((unsigned char*)chain->key, (unsigned char*)name, L) )
    196         {
    197 #else
    198         if( equal_compare<uint16_t>((unsigned char*)chain->key, (unsigned char*)name, chain->lgth, L) )
    199         {
    200 #endif
    201 #if DEBUG_BHT
    202             printf ("Found GID: %i\n", chain->GID);
    203 #endif
    204             return chain->GID;
    205         }
    206     }
    207 
    208 #if DEBUG_BHT
    209     printf ("Not Found GID: %i\n", 0);
    210 #endif
    211     return 0;
    212 }
    213 
    214 // Use this method if L is in [5,8]
    215 inline unsigned int BitStreamHashTable::Lookup_Name_8(char * name, const int hashvalue, int L)
    216 {
    217     unsigned int hash = getIndex(hashvalue);
    218 
    219     // Look up the value in the chain
    220     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
    221 #if DEBUG_BHT
    222         printf ("Check symbol: %s\n", chain->key);
    223 #endif
    224         if( equal_compare<uint32_t> ((unsigned char*)chain->key, (unsigned char*)name, chain->lgth, L) )
    225         {
    226 #if DEBUG_BHT
    227             printf ("Found GID: %i\n", chain->GID);
    228 #endif
    229             return chain->GID;
    230         }
    231     }
    232 
    233 #if DEBUG_BHT
    234     printf ("Not Found GID: %i\n", 0);
    235 #endif
    236     return 0;
    237 }
    238 
    239 // Use this method if L is in [9,16]
    240 inline unsigned int BitStreamHashTable::Lookup_Name_16(char * name, const int hashvalue, int L)
    241 {
    242     unsigned int hash = getIndex(hashvalue);
    243 
    244     // Look up the value in the chain
    245     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
    246 #if DEBUG_BHT
    247         printf ("Check symbol: %s\n", chain->key);
    248 #endif
    249         if( equal_compare<uint64_t> ((unsigned char*)chain->key, (unsigned char*)name, chain->lgth, L) )
    250         {
    251 #if DEBUG_BHT
    252             printf ("Found GID: %i\n", chain->GID);
    253 #endif
    254             return chain->GID;
    255         }
    256     }
    257 
    258 #if DEBUG_BHT
    259     printf ("Not Found GID: %i\n", 0);
    260 #endif
    261     return 0;
    262 }
    263 
    264 #endif // #if defined (USE_LOG_SORT)
    265 
    266 
    267 // Use this method if L is in [17,32]
    268 inline unsigned int BitStreamHashTable::Lookup_Name_32(char * name, const int hashvalue, int L)
    269 {
    270     unsigned int hash = getIndex(hashvalue);
    271 
    272     // Look up the value in the chain
    273     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
    274 #if DEBUG_BHT
    275         printf ("Check symbol: %s\n", chain->key);
    276 #endif
    277         if( equal_compare<SIMD_type> ((unsigned char*)chain->key, (unsigned char*)name, chain->lgth, L) )
    278         {
    279 #if DEBUG_BHT
    280             printf ("Found GID: %i\n", chain->GID);
    281 #endif
    282             return chain->GID;
    283         }
    284     }
    285 
    286 #if DEBUG_BHT
    287     printf ("Not Found GID: %i\n", 0);
    288 #endif
    289     return 0;
    290 }
    291 
    292 // Use this method if L > 32
    293 inline unsigned int BitStreamHashTable::Lookup_Name(char * name, const int hashvalue, int L)
     78// Use this method if L > 16
     79unsigned int BitStreamHashTable::Lookup_Name_17(char * name, const int hashvalue, int L)
    29480{
    29581    unsigned int hash = getIndex(hashvalue);
Note: See TracChangeset for help on using the changeset viewer.