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

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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
Note: See TracChangeset for help on using the changeset viewer.