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