Changeset 1653


Ignore:
Timestamp:
Nov 2, 2011, 8:34:40 PM (7 years ago)
Author:
vla24
Message:

SymbolTable?: implemented auto-resize and custom hashing for different symbol length for division and identity length grouping

Location:
trunk/symtab
Files:
3 added
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/symtab/bitstream_div_hash_table.h

    r1518 r1653  
    1818
    1919#include <stdlib.h>
    20 #include "bitstream_hash_table.h"
    2120#include "pbgs_utilities.h"
    22 #include "ls_symbol_table_util.h"
    23 #include "limits.h"
     21#include "bitstream_super_hash_table.h"
     22#include "pbgs_hash_functions.h"
     23#include "bitstream_id_hash_table.h"
     24#undef BitStreamHashTableImpl
     25#define BitStreamHashTableImpl BitStreamDivHashTable
    2426
    25 class BitStreamDivHashTable : public BitStreamHashTable
     27// Use L = 17 to indicate a group for symbols with length > 16
     28// if L in [1,16], L should be an even number.
     29template <int L>
     30class BitStreamDivHashTable : public BitStreamSuperHashTable
    2631{
    2732public:
    2833
    29     //Returns 0 upon failure
    30     // Symbol L in [1,16] and L should be an even number.
     34    BitStreamDivHashTable() {};
     35    ~BitStreamDivHashTable() {};
     36
     37    // Returns 0 upon failure
     38    // Symbol L in [1,16]
    3139    // Use this method to do _first_ symbol lookup: _before_ checking if the last
    3240    // character is a delimiter
    33     template <int L> inline unsigned int Lookup_Name(char * name, const int hashvalue);
     41    inline unsigned int Lookup_Name(char * name, const int hashvalue);
    3442
    35     // Symbol L in [1,16] and L should be an _odd_ number.
     43    // Symbol L in [1,16]
    3644    // Use this method to do _second_ symbol lookup: _after_ checking if the last
    3745    // character is a delimiter
    38     template <int L> inline unsigned int Lookup_Name_Delimiter(char * name, const int hashvalue);
     46    inline unsigned int Lookup_Name_Odd(char * name, const int hashvalue);
     47
     48    // Symbol length > 16
     49    unsigned int Lookup_Name_17(char * name, const int hashvalue, int length);
     50
     51    // Use this method for identity and div2 grouping, L <= 16
     52    void Insert_Name(const char * name, const int hashvalue, const unsigned int gid);
     53
     54    // Use this method for arbitrary length.
     55    void Insert_Name(const char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth);
     56
     57    // Use this method for identity and div2 grouping, L <= 16
     58    inline void Insert_Name_Odd_Symbol(const char * name, const int hashvalue, const unsigned int gid);
     59
     60protected:
     61    // Use this for L in [1,16]
     62    inline unsigned int getBucket(const char* name, const int hashvalue, unsigned int tableSize);
     63
     64    // Use this for L > 16
     65    inline unsigned int getBucket(const int hashvalue, unsigned int tableSize, unsigned int length);
     66
     67private:
     68    void expandHashTable();
     69    BitStreamIdentityHashTable<L-1> m_oddSymbolTable;
    3970};
    4071
     72// L in [1,16]
    4173template <int L>
    42         inline unsigned int BitStreamDivHashTable::Lookup_Name(char * name, const int hashvalue)
     74        inline unsigned int BitStreamDivHashTable<L>::Lookup_Name(char * name, const int hashvalue)
    4375{
    44     unsigned int bucket = getBucket(hashvalue, g_tableSize);
     76    unsigned int bucket = getBucket(name, hashvalue, m_tableSize);
    4577
    4678    // Look up the value in the chain
    47     for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
     79    for(CHAIN* chain = m_table[bucket]; chain != NULL; chain = chain->next) {
    4880#if DEBUG_BHT
    4981        printf ("Check symbol: %s\n", chain->key);
    … …  
    6496}
    6597
    66 // L is odd
     98// L in [1,16]
    6799template <int L>
    68         inline unsigned int BitStreamDivHashTable::Lookup_Name_Delimiter(char * name, const int hashvalue)
     100        inline unsigned int BitStreamDivHashTable<L>::Lookup_Name_Odd(char * name, const int hashvalue)
    69101{
    70     unsigned int bucket = getBucket(hashvalue, g_tableSize);
    71 
    72     // Look up the value in the chain
    73     for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
    74 #if DEBUG_BHT
    75         printf ("Check key: %s\n", chain->key);
    76 #endif
    77         if( div_equal_compare <L> ((unsigned char*)chain->key, (unsigned char*)name) )
    78         {
    79 #if DEBUG_BHT
    80             printf ("Found GID: %i\n", chain->GID);
    81 #endif
    82             return chain->GID;
    83         }
    84     }
    85 
    86     // Flip the last bit of the hash value
    87     unsigned int newBucket = getBucket(flipBit<L+1>(hashvalue), g_tableSize);
    88 
    89 #if DEBUG_BHT
    90     print_general_register_32 ("hash", hashvalue);
    91     print_general_register_32 ("flipped hash", flipBit<L+1>(hashvalue));
    92     printf ("\n");
    93 #endif
    94     // FIXME: Should we check?
    95     if (bucket == newBucket)
    96     {
    97         return 0;
    98     }
    99 
    100     // Look up the value in the chain
    101     for(CHAIN* chain = g_table[newBucket]; chain != NULL; chain = chain->next) {
    102 #if DEBUG_BHT
    103         printf ("Check key: %s\n", chain->key);
    104 #endif
    105         if( div_equal_compare <L> ((unsigned char*)chain->key, (unsigned char*)name) )
    106         {
    107 #if DEBUG_BHT
    108             printf ("Found GID: %i\n", chain->GID);
    109 #endif
    110             return chain->GID;
    111         }
    112     }
    113 
    114 #if DEBUG_BHT
    115     printf ("Not Found GID: %i\n", 0);
    116 #endif
    117     return 0;
     102    return m_oddSymbolTable.Lookup_Name(name, hashvalue);
    118103}
    119104
     105//Use this method for L in [1,16], name has odd length
     106template <int L>
     107        void BitStreamDivHashTable<L>::Insert_Name_Odd_Symbol(const char * name, const int hashvalue, const unsigned int gid)
     108{
     109    m_oddSymbolTable.Insert_Name(name, hashvalue, gid);
     110}
     111
     112#include "bitstream_hash_table_impl.h"
     113
    120114#endif // BITSTREAM_DIV_HASH_TABLE_H

  • trunk/symtab/bitstream_id_hash_table.h

    r1518 r1653  
    1313#ifndef BITSTREAM_ID_HASH_TABLE_H
    1414#define BITSTREAM_ID_HASH_TABLE_H
    15 #define USE_IDENTITY_SORT
     15#include "pbgs_utilities.h"
     16#include "pbgs_hash_functions.h"
     17#include "bitstream_super_hash_table.h"
     18#undef BitStreamHashTableImpl
     19#define BitStreamHashTableImpl BitStreamIdentityHashTable
    1620
    17 #include "bitstream_hash_table.h"
    18 #include "pbgs_utilities.h"
    19 
    20 class BitStreamIdentityHashTable : public BitStreamHashTable
     21#define DEBUG_BHT 0
     22// Use L = 17 to indicate a group for symbols with length > 16
     23template <int L>
     24class BitStreamIdentityHashTable : public BitStreamSuperHashTable
    2125{
    2226public:
    … …  
    2428    //Returns 0 upon failure
    2529    // Symbol length [1,16]
    26     template <int L> inline unsigned int Lookup_Name(char * name, const int hashvalue);
     30    inline unsigned int Lookup_Name(char * name, const int hashvalue);
     31
     32    // Symbol length > 16
     33    unsigned int Lookup_Name_17(char * name, const int hashvalue, int length);
     34
     35    // Use this method for identity and div2 grouping, L <= 16
     36    void Insert_Name(const char * name, const int hashvalue, const unsigned int gid);
     37
     38    // Use this method for arbitrary length.
     39    void Insert_Name(const char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth);
     40
     41protected:
     42    // Use this for L in [1,16]
     43    inline unsigned int getBucket(const char* name, const int hashvalue, unsigned int tableSize);
     44
     45    // Use this for L > 16
     46    inline unsigned int getBucket(const int hashvalue, unsigned int tableSize, unsigned int length);
     47
     48private:
     49    void expandHashTable();
    2750};
    2851
    2952template <int L>
    30         unsigned int BitStreamIdentityHashTable::Lookup_Name(char * name, const int hashvalue)
     53unsigned int BitStreamIdentityHashTable<L>::Lookup_Name(char * name, const int hashvalue)
    3154{
    32     unsigned int bucket = getBucket(hashvalue, g_tableSize);
     55    unsigned int bucket = getBucket(name, hashvalue, m_tableSize);
    3356
    3457    // Look up the value in the chain
    35     for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
     58    for(CHAIN* chain = m_table[bucket]; chain != NULL; chain = chain->next) {
    3659#if DEBUG_BHT
    3760        printf ("Check symbol: %s\n", chain->key);
    … …  
    4063        {
    4164#if DEBUG_BHT
    42             printf ("Found GID: %i\n", chain->GID);
     65            printf ("%s%i Found GID: %i\n", __FUNCTION__, L, chain->GID);
    4366#endif
    4467            return chain->GID;
    … …  
    4770
    4871#if DEBUG_BHT
    49     printf ("Not Found GID: %i\n", 0);
     72    printf ("%s%i Not Found GID: %i\n", __FUNCTION__, L, 0);
    5073#endif
    5174
    5275    return 0;
    5376}
     77
     78#include "bitstream_hash_table_impl.h"
    5479#endif // BITSTREAM_ID_HASH_TABLE_H

  • trunk/symtab/bitstream_log_hash_table.h

    r1518 r1653  
    4444inline unsigned int BitStreamLogHashTable::Lookup_Name_1(char * name, const int hashvalue)
    4545{
    46     unsigned int bucket = getBucket(hashvalue, g_tableSize);
     46    unsigned int bucket = getBucket(hashvalue, m_tableSize);
     47    unsigned int chainlgth = m_table->size(bucket);
    4748
    4849    // Look up the value in the chain
    49     for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
     50    for(unsigned int i = 0; i < chainlgth; i++) {
     51        CHAIN chain = m_table->get(bucket, i);
    5052#if DEBUG_BHT
    51         printf ("Check symbol: %s\n", chain->key);
     53        printf ("Check symbol: %s\n", chain.key);
    5254#endif
    53         if( log_equal_compare_1 ((unsigned char*)chain->key, (unsigned char*)name) )
     55        if( log_equal_compare_1 ((unsigned char*)chain.key, (unsigned char*)name) )
    5456        {
    5557#if DEBUG_BHT
    56             printf ("Found GID: %i\n", chain->GID);
     58            printf ("Found GID: %i\n", chain.GID);
    5759#endif
    58             return chain->GID;
     60            return chain.GID;
    5961        }
    6062    }
    … …  
    6870inline unsigned int BitStreamLogHashTable::Lookup_Name_2(char * name, const int hashvalue)
    6971{
    70     unsigned int bucket = getBucket(hashvalue, g_tableSize);
     72    unsigned int bucket = getBucket(hashvalue, m_tableSize);
     73    unsigned int chainlgth = m_table->size(bucket);
    7174
    7275    // Look up the value in the chain
    73     for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
     76    for(unsigned int i = 0; i < chainlgth; i++) {
     77        CHAIN chain = m_table->get(bucket, i);
    7478#if DEBUG_BHT
    75         printf ("Check symbol: %s\n", chain->key);
     79        printf ("Check symbol: %s\n", chain.key);
    7680#endif
    77         if( log_equal_compare_2 ((unsigned char*)chain->key, (unsigned char*)name) )
     81        if( log_equal_compare_2 ((unsigned char*)chain.key, (unsigned char*)name) )
    7882        {
    7983#if DEBUG_BHT
    80             printf ("Found GID: %i\n", chain->GID);
     84            printf ("Found GID: %i\n", chain.GID);
    8185#endif
    82             return chain->GID;
     86            return chain.GID;
    8387        }
    8488    }
    … …  
    9397inline unsigned int BitStreamLogHashTable::Lookup_Name_4(char * name, const int hashvalue, int L)
    9498{
    95     unsigned int bucket = getBucket(hashvalue, g_tableSize);
     99    unsigned int bucket = getBucket(hashvalue, m_tableSize);
     100    unsigned int chainlgth = m_table->size(bucket);
    96101
    97102    // Look up the value in the chain
    98     for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
     103    for(unsigned int i = 0; i < chainlgth; i++) {
     104        CHAIN chain = m_table->get(bucket, i);
    99105#if DEBUG_BHT
    100         printf ("Check symbol: %s\n", chain->key);
     106        printf ("Check symbol: %s\n", chain.key);
    101107#endif
    102108
    103109#ifdef USE_MASK_COMPARE
    104         if( log_equal_compare_4 ((unsigned char*)chain->key, (unsigned char*)name, L) )
     110        if( log_equal_compare_4 ((unsigned char*)chain.key, (unsigned char*)name, L) )
    105111        {
    106112#else
    107         if( overlap_compare<uint16_t>((unsigned char*)chain->key, (unsigned char*)name, chain->lgth, L) )
     113        if( overlap_compare<uint16_t>((unsigned char*)chain.key, (unsigned char*)name, chain.lgth, L) )
    108114        {
    109115#endif
    110116#if DEBUG_BHT
    111             printf ("Found GID: %i\n", chain->GID);
     117            printf ("Found GID: %i\n", chain.GID);
    112118#endif
    113             return chain->GID;
     119            return chain.GID;
    114120        }
    115121    }
    … …  
    124130inline unsigned int BitStreamLogHashTable::Lookup_Name_8(char * name, const int hashvalue, int L)
    125131{
    126     unsigned int bucket = getBucket(hashvalue, g_tableSize);
     132    unsigned int bucket = getBucket(hashvalue, m_tableSize);
     133    unsigned int chainlgth = m_table->size(bucket);
    127134
    128135    // Look up the value in the chain
    129     for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
     136    for(unsigned int i = 0; i < chainlgth; i++) {
     137        CHAIN chain = m_table->get(bucket, i);
    130138#if DEBUG_BHT
    131         printf ("Check symbol: %s\n", chain->key);
     139        printf ("Check symbol: %s\n", chain.key);
    132140#endif
    133         if( overlap_compare<uint32_t> ((unsigned char*)chain->key, (unsigned char*)name, chain->lgth, L) )
     141        if( overlap_compare<uint32_t> ((unsigned char*)chain.key, (unsigned char*)name, chain.lgth, L) )
    134142        {
    135143#if DEBUG_BHT
    136             printf ("Found GID: %i\n", chain->GID);
     144            printf ("Found GID: %i\n", chain.GID);
    137145#endif
    138             return chain->GID;
     146            return chain.GID;
    139147        }
    140148    }
    … …  
    149157inline unsigned int BitStreamLogHashTable::Lookup_Name_16(char * name, const int hashvalue, int L)
    150158{
    151     unsigned int bucket = getBucket(hashvalue, g_tableSize);
     159    unsigned int bucket = getBucket(hashvalue, m_tableSize);
     160    unsigned int chainlgth = m_table->size(bucket);
    152161
    153162    // Look up the value in the chain
    154     for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
     163    for(unsigned int i = 0; i < chainlgth; i++) {
     164        CHAIN chain = m_table->get(bucket, i);
    155165#if DEBUG_BHT
    156         printf ("Check symbol: %s\n", chain->key);
     166        printf ("Check symbol: %s\n", chain.key);
    157167#endif
    158         if( overlap_compare<uint64_t> ((unsigned char*)chain->key, (unsigned char*)name, chain->lgth, L) )
     168        if( overlap_compare<uint64_t> ((unsigned char*)chain.key, (unsigned char*)name, chain.lgth, L) )
    159169        {
    160170#if DEBUG_BHT
    161             printf ("Found GID: %i\n", chain->GID);
     171            printf ("Found GID: %i\n", chain.GID);
    162172#endif
    163             return chain->GID;
     173            return chain.GID;
    164174        }
    165175    }

  • trunk/symtab/pbgs_div_symbol_table.h

    r1517 r1653  
    2323#define USE_FUNCTION_TEMPLATES
    2424#include "stringpool.h"
     25#include "bitstream_super_hash_table.h"
    2526#include "bitstream_div_hash_table.h"
    2627#include "ls_symbol_table_compare.h"
    … …  
    3738{
    3839public:
    39     PBGSDivSymbolTable()
    40         :m_globalNameCount(1)
    41     {};
     40    PBGSDivSymbolTable();
     41    ~PBGSDivSymbolTable();
    4242
    4343    template <int L> inline int Lookup_or_Insert_Name(char* name, int hashvalue);
    … …  
    5151private:
    5252    StringPool <4096,100> m_pool;
    53     BitStreamDivHashTable m_hashTable[TOTAL_GROUPS];
     53    BitStreamSuperHashTable* m_hashTable[TOTAL_GROUPS];
    5454    int m_globalNameCount;
    5555
    56     inline int getHashTableIndex(int L);
     56    inline int getGroup(int L);
    5757    inline bool isDelimiter(const char c);
     58
     59    template <int L> inline char* Store_Name(const char* name);
    5860};
    5961
     62PBGSDivSymbolTable::PBGSDivSymbolTable()
     63    :m_globalNameCount(1)
     64{
     65    m_hashTable[1] = new BitStreamDivHashTable<2>();
     66    m_hashTable[2] = new BitStreamDivHashTable<4>();
     67    m_hashTable[3] = new BitStreamDivHashTable<6>();
     68    m_hashTable[4] = new BitStreamDivHashTable<8>();
     69    m_hashTable[5] = new BitStreamDivHashTable<10>();
     70    m_hashTable[6] = new BitStreamDivHashTable<12>();
     71    m_hashTable[7] = new BitStreamDivHashTable<14>();
     72    m_hashTable[8] = new BitStreamDivHashTable<16>();
     73    m_hashTable[9] = new BitStreamDivHashTable<17>();
     74};
     75
     76PBGSDivSymbolTable::~PBGSDivSymbolTable()
     77{
     78    for (int i = 1; i < TOTAL_GROUPS; i ++)
     79    {
     80        delete m_hashTable[i];
     81        m_hashTable[i] = NULL;
     82    }
     83}
     84
     85template <> inline char* PBGSDivSymbolTable::Store_Name<3>(const char* name)
     86{
     87    return m_pool.Insert(name, 3, 1);
     88}
     89
     90template <> inline char* PBGSDivSymbolTable::Store_Name<5>(const char* name)
     91{
     92    return m_pool.Insert(name, 5, 3);
     93}
     94
     95template <> inline char* PBGSDivSymbolTable::Store_Name<6>(const char* name)
     96{
     97    return m_pool.Insert(name, 6, 2);
     98}
     99
     100template <> inline char* PBGSDivSymbolTable::Store_Name<7>(const char* name)
     101{
     102    return m_pool.Insert(name, 7, 1);
     103}
     104
     105template <int L> inline char* PBGSDivSymbolTable::Store_Name(const char* name)
     106{
     107    return m_pool.Insert(name, L);
     108}
     109
    60110// L should be an even number, L is in [1,16]
    61 template <int L> inline int PBGSDivSymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue)
     111template <int L>
     112        inline int PBGSDivSymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue)
    62113{
    63114    int GID = 0;
    64     int group = getHashTableIndex(L);
     115    int group = getGroup(L);
    65116
    66117    //Lookup
    67     GID = m_hashTable[group].Lookup_Name<L>(name, hashvalue);
     118    GID = ((BitStreamDivHashTable<L>*)m_hashTable[group])->Lookup_Name(name, hashvalue);
    68119
    69120    if (!GID) //symbol not found
    70121    {
     122        // Store the symbol
     123        char* c = Store_Name<L>(name);
     124
    71125        //Check if the last character is a delimiter
    72126        if (isDelimiter(name[L-1]))
    73127        {
    74128            //Do another lookup for name with L = L-1
    75             GID = m_hashTable[group].Lookup_Name_Delimiter<L-1>(name, hashvalue);
    76 
    77             if (GID)
     129            GID = ((BitStreamDivHashTable<L>*)m_hashTable[group])->Lookup_Name_Odd(name, hashvalue);
     130
     131            if (!GID)
    78132            {
    79                 //Symbol found, return immediately
    80                 return GID;
     133                //Symbol is not found in odd table
     134                GID = m_globalNameCount;
     135                m_globalNameCount++;
     136
     137                // Store symbol for odd length. We need to do this because the symbol-key comparison
     138                // in the hash table does not mask out characters.
     139                char* oddSymbol = Store_Name<L-1>(name);
     140
     141                // Insert into odd table
     142                ((BitStreamDivHashTable<L>*)m_hashTable[group])->Insert_Name_Odd_Symbol(oddSymbol, hashvalue, GID);
    81143            }
    82144        }
    83 
    84         //Insert
    85         char* c = m_pool.Insert(name, L);
    86         GID = m_globalNameCount;
    87 
    88         m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
    89         m_globalNameCount++;
     145        else
     146        {
     147            //even length symbol
     148            GID = m_globalNameCount;
     149            m_globalNameCount++;
     150        }
     151
     152        //Insert into even table
     153        ((BitStreamDivHashTable<L>*)m_hashTable[group])->Insert_Name(c, hashvalue, GID);
    90154    }
    91155#if DEBUG_PBGS_DIV
    … …  
    100164
    101165// Use this function for L > 16
    102 inline int PBGSDivSymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue, int L)
     166inline int PBGSDivSymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue, int lgth)
    103167{
    104168    int GID = 0;
    … …  
    107171    cout << "Lookup or Insert: " << name << endl;
    108172#endif
    109     int group = getHashTableIndex(L);
    110173
    111174    //Lookup
    112     GID = m_hashTable[group].Lookup_Name_17(name, hashvalue,L);
     175    GID = ((BitStreamDivHashTable<17>*)m_hashTable[LAST_GROUP])->Lookup_Name_17(name, hashvalue, lgth);
    113176
    114177    //Insert
    115178    if (!GID) //symbol not found
    116179    {
    117         char* c = m_pool.Insert(name, L);
     180        char* c = m_pool.Insert(name, lgth);
    118181        GID = m_globalNameCount;
    119182
    120         m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
     183        ((BitStreamDivHashTable<17>*)m_hashTable[LAST_GROUP])->Insert_Name(c, hashvalue, m_globalNameCount, lgth);
    121184        m_globalNameCount++;
    122185    }
    … …  
    130193}
    131194
    132 inline int PBGSDivSymbolTable::getHashTableIndex(int L)
     195inline int PBGSDivSymbolTable::getGroup(int L)
    133196{
    134197    if (L > 16)
    … …  
    140203void PBGSDivSymbolTable::Print_Symbol_Table_Distribution()
    141204{
    142     for (int i = 0; i < TOTAL_GROUPS; i++)
     205    for (int i = 1; i < TOTAL_GROUPS; i ++)
    143206    {
    144207        fprintf (stderr, "Group #%i\n", i );
    145         m_hashTable[i].Print_Symbol_Table_Distribution();
    146     }
     208        m_hashTable[i]->Print_Symbol_Table_Distribution();
     209    }
     210
    147211}
    148212#endif // PBGS_DIV_SYMBOL_TABLE_H

  • trunk/symtab/pbgs_identity_symbol_table.h

    r1517 r1653  
    2020#define USE_FUNCTION_TEMPLATES
    2121#include "stringpool.h"
     22#include "bitstream_super_hash_table.h"
    2223#include "bitstream_id_hash_table.h"
    2324#include "ls_symbol_table_compare.h"
    … …  
    3233{
    3334public:
    34     PBGSIdentitySymbolTable()
    35         :m_globalNameCount(1)
    36     {};
     35    PBGSIdentitySymbolTable();
     36    ~PBGSIdentitySymbolTable();
    3737
    3838    // Use this function for 1 <= L <= 16
    … …  
    4646private:
    4747    StringPool <4096,100> m_pool;
    48     BitStreamIdentityHashTable m_hashTable[TOTAL_GROUPS];
     48    BitStreamSuperHashTable* m_hashTable[TOTAL_GROUPS];
    4949
    50     inline int getHashTableIndex(int L);
     50    inline int getGroup(int L);
    5151    int m_globalNameCount;
     52
     53    template <int L> inline char* Store_Name(const char* name);
    5254};
    5355
    54 template <>
    55         inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name<3>(char* name, int hashvalue)
     56PBGSIdentitySymbolTable::PBGSIdentitySymbolTable()
     57    :m_globalNameCount(1)
     58{
     59    m_hashTable[1] = new BitStreamIdentityHashTable<1>();
     60    m_hashTable[2] = new BitStreamIdentityHashTable<2>();
     61    m_hashTable[3] = new BitStreamIdentityHashTable<3>();
     62    m_hashTable[4] = new BitStreamIdentityHashTable<4>();
     63    m_hashTable[5] = new BitStreamIdentityHashTable<5>();
     64    m_hashTable[6] = new BitStreamIdentityHashTable<6>();
     65    m_hashTable[7] = new BitStreamIdentityHashTable<7>();
     66    m_hashTable[8] = new BitStreamIdentityHashTable<8>();
     67    m_hashTable[9] = new BitStreamIdentityHashTable<9>();
     68    m_hashTable[10] = new BitStreamIdentityHashTable<10>();
     69    m_hashTable[11] = new BitStreamIdentityHashTable<11>();
     70    m_hashTable[12] = new BitStreamIdentityHashTable<12>();
     71    m_hashTable[13] = new BitStreamIdentityHashTable<13>();
     72    m_hashTable[14] = new BitStreamIdentityHashTable<14>();
     73    m_hashTable[15] = new BitStreamIdentityHashTable<15>();
     74    m_hashTable[16] = new BitStreamIdentityHashTable<16>();
     75    m_hashTable[17] = new BitStreamIdentityHashTable<17>();
     76};
     77
     78PBGSIdentitySymbolTable::~PBGSIdentitySymbolTable()
     79{
     80    for (int i = 1; i < TOTAL_GROUPS; i ++)
     81    {
     82        delete m_hashTable[i];
     83        m_hashTable[i] = NULL;
     84    }
     85}
     86
     87template <> inline char* PBGSIdentitySymbolTable::Store_Name<3>(const char* name)
     88{
     89    return m_pool.Insert(name, 3, 1);
     90}
     91
     92template <> inline char* PBGSIdentitySymbolTable::Store_Name<5>(const char* name)
     93{
     94    return m_pool.Insert(name, 5, 3);
     95}
     96
     97template <> inline char* PBGSIdentitySymbolTable::Store_Name<6>(const char* name)
     98{
     99    return m_pool.Insert(name, 6, 2);
     100}
     101
     102template <> inline char* PBGSIdentitySymbolTable::Store_Name<7>(const char* name)
     103{
     104    return m_pool.Insert(name, 7, 1);
     105}
     106
     107template <int L> inline char* PBGSIdentitySymbolTable::Store_Name(const char* name)
     108{
     109    return m_pool.Insert(name, L);
     110}
     111
     112// Use this function for 1 <= L <= 16
     113template <int L> inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue)
    56114{
    57115    int GID = 0;
    58     int group = getHashTableIndex(3);
     116    int group = getGroup(L);
    59117
    60118    //Lookup
    61     GID = m_hashTable[group].Lookup_Name<3>(name, hashvalue);
     119    GID = ((BitStreamIdentityHashTable<L>*)m_hashTable[group])->Lookup_Name(name, hashvalue);
    62120
    63121    //Insert
    64122    if (!GID) //symbol not found
    65123    {
    66         char* c = m_pool.Insert(name, 3, 1);
     124        char* c = Store_Name<L>(name);
    67125        GID = m_globalNameCount;
    68126
    69         m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
    70         m_globalNameCount++;
    71     }
    72 #if DEBUG_PBGS
    73     int advance = 1;
    74     int L = 3;
    75     char delim = name[L];
    76     name[L] = '\0';
    77     cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << " | advance: " << advance << endl;
    78     name[L] = delim;
    79 #endif
    80 
    81     return GID;
    82 }
    83 
    84 template <>
    85         inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name<5>(char* name, int hashvalue)
    86 {
    87     int GID = 0;
    88     int group = getHashTableIndex(5);
    89 
    90     //Lookup
    91     GID = m_hashTable[group].Lookup_Name<5>(name, hashvalue);
    92 
    93     //Insert
    94     if (!GID) //symbol not found
    95     {
    96         char* c = m_pool.Insert(name, 5, 3);
    97         GID = m_globalNameCount;
    98 
    99         m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
    100         m_globalNameCount++;
    101     }
    102 #if DEBUG_PBGS
    103     int advance = 3;
    104     int L = 5;
    105     char delim = name[L];
    106     name[L] = '\0';
    107     cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << " | advance: " << advance << endl;
    108     name[L] = delim;
    109 #endif
    110 
    111     return GID;
    112 }
    113 
    114 template <>
    115         inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name<6>(char* name, int hashvalue)
    116 {
    117     int GID = 0;
    118     int group = getHashTableIndex(6);
    119 
    120     //Lookup
    121     GID = m_hashTable[group].Lookup_Name<6>(name, hashvalue);
    122 
    123     //Insert
    124     if (!GID) //symbol not found
    125     {
    126         char* c = m_pool.Insert(name, 6, 2);
    127         GID = m_globalNameCount;
    128 
    129         m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
    130         m_globalNameCount++;
    131     }
    132 #if DEBUG_PBGS
    133     int advance = 2;
    134     int L = 6;
    135     char delim = name[L];
    136     name[L] = '\0';
    137     cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << " | advance: " << advance << endl;
    138     name[L] = delim;
    139 #endif
    140 
    141     return GID;
    142 }
    143 
    144 template <>
    145         inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name<7>(char* name, int hashvalue)
    146 {
    147     int GID = 0;
    148     int group = getHashTableIndex(7);
    149 
    150     //Lookup
    151     GID = m_hashTable[group].Lookup_Name<7>(name, hashvalue);
    152 
    153     //Insert
    154     if (!GID) //symbol not found
    155     {
    156         char* c = m_pool.Insert(name, 7, 1);
    157         GID = m_globalNameCount;
    158 
    159         m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
    160         m_globalNameCount++;
    161     }
    162 #if DEBUG_PBGS
    163     int advance = 1;
    164     int L = 7;
    165     char delim = name[L];
    166     name[L] = '\0';
    167     cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << " | advance: " << advance << endl;
    168     name[L] = delim;
    169 #endif
    170 
    171     return GID;
    172 }
    173 
    174 // Use this function for 1,2, 4, 8 <= L <= 32
    175 template <int L> inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue)
    176 {
    177     int GID = 0;
    178     int group = getHashTableIndex(L);
    179 
    180     //Lookup
    181     GID = m_hashTable[group].Lookup_Name<L>(name, hashvalue);
    182 
    183     //Insert
    184     if (!GID) //symbol not found
    185     {
    186         char* c = m_pool.Insert(name, L);
    187         GID = m_globalNameCount;
    188 
    189         m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
     127        ((BitStreamIdentityHashTable<L>*)m_hashTable[group])->Insert_Name(c, hashvalue, m_globalNameCount);
    190128        m_globalNameCount++;
    191129    }
    … …  
    201139
    202140// Use this function for L > 16
    203 inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue, int L)
     141inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue, int lgth)
    204142{
    205143    int GID = 0;
    … …  
    208146    cout << "Lookup or Insert: " << name << endl;
    209147#endif
    210     int group = getHashTableIndex(L);
    211148
    212149    //Lookup
    213     GID = m_hashTable[group].Lookup_Name_17(name, hashvalue, L);
     150    GID = ((BitStreamIdentityHashTable<17>*)m_hashTable[LAST_GROUP])->Lookup_Name_17(name, hashvalue, lgth);
    214151
    215152    //Insert
    216153    if (!GID) //symbol not found
    217154    {
    218         char* c = m_pool.Insert(name, L);
     155        char* c = m_pool.Insert(name, lgth);
    219156        GID = m_globalNameCount;
    220157
    221         m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
     158        ((BitStreamIdentityHashTable<17>*)m_hashTable[LAST_GROUP])->Insert_Name(c, hashvalue, m_globalNameCount, lgth);
    222159        m_globalNameCount++;
    223160    }
    … …  
    225162}
    226163
    227 inline int PBGSIdentitySymbolTable::getHashTableIndex(int L)
     164inline int PBGSIdentitySymbolTable::getGroup(int L)
    228165{
    229166    if (L > 16)
    … …  
    235172void PBGSIdentitySymbolTable::Print_Symbol_Table_Distribution()
    236173{
    237     for (int i = 0; i < TOTAL_GROUPS; i++)
     174    for (int i = 1; i < TOTAL_GROUPS; i ++)
    238175    {
    239         fprintf (stderr, "Group #%i\n", i );
    240         m_hashTable[i].Print_Symbol_Table_Distribution();
     176        fprintf (stderr, "Group #%i\n", i );
     177        m_hashTable[i]->Print_Symbol_Table_Distribution();
    241178    }
     179
    242180}
    243181#endif // PBGS_LENGTH_SYMBOL_TABLE_H

  • trunk/symtab/pbgs_utilities.h

    r1518 r1653  
    121121}
    122122
    123 
    124 //template<>
    125 //inline bool div_equal_compare<3>(const unsigned char * key, const unsigned char * symbol) {
    126 //    return ((* ((uint32_t *) key)) ==
    127 //                              ((* ((uint32_t *) symbol)) & (0xFFFFFF << LOW_BYTE_SHIFT))); // s4int32()
    128 //}
    129 
    130 //template<>
    131 //inline bool div_equal_compare<5>(const unsigned char * key, const unsigned char * symbol) {
    132 //    return ((* ((uint64_t *) key)) ==
    133 //                      ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFULL << (3 * LOW_BYTE_SHIFT)))); // s8int64()
    134 //}
    135 
    136 //template<>
    137 //inline bool div_equal_compare<6>(const unsigned char * key, const unsigned char * symbol) {
    138 //    return ((* ((uint64_t *) key)) ==
    139 //                      ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFFFULL << (2 * LOW_BYTE_SHIFT)))); // s8int64()
    140 //}
    141 
    142 //template<>
    143 //inline bool div_equal_compare<7>(const unsigned char * key, const unsigned char * symbol) {
    144 //    return ((* ((uint64_t *) key)) ==
    145 //                      ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFFFFFULL << LOW_BYTE_SHIFT))); // s8int64()
    146 //}
     123template<>
     124inline bool div_equal_compare<3>(const unsigned char * key, const unsigned char * symbol) {
     125    return ((* ((uint32_t *) key)) ==
     126                                ((* ((uint32_t *) symbol)) & (0xFFFFFF << LOW_BYTE_SHIFT))); // s4int32()
     127}
     128
     129template<>
     130inline bool div_equal_compare<5>(const unsigned char * key, const unsigned char * symbol) {
     131    return ((* ((uint64_t *) key)) ==
     132                        ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFULL << (3 * LOW_BYTE_SHIFT)))); // s8int64()
     133}
     134
     135template<>
     136inline bool div_equal_compare<6>(const unsigned char * key, const unsigned char * symbol) {
     137    return ((* ((uint64_t *) key)) ==
     138                        ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFFFULL << (2 * LOW_BYTE_SHIFT)))); // s8int64()
     139}
     140
     141template<>
     142inline bool div_equal_compare<7>(const unsigned char * key, const unsigned char * symbol) {
     143    return ((* ((uint64_t *) key)) ==
     144                        ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFFFFFULL << LOW_BYTE_SHIFT))); // s8int64()
     145}
    147146
    148147
    … …  
    190189    return value ^ 0x8000;
    191190}
     191
     192// Returns a mask for L bits
     193// eg. mask<3> returns 0x7 (0000...00111)
     194template <size_t L>
     195        inline unsigned int maskBit()
     196{
     197    return ~(~0 << L);
     198}
     199
    192200#endif /* PBGS_DIV_UTILITIES_H_ */
Note: See TracChangeset for help on using the changeset viewer.