Changeset 1391


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

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

Files:
3 added
2 deleted
6 edited

Legend:

Unmodified
Added
Removed
  • proto/SymbolTable/automate-build.sh

    r1232 r1391  
    1 make symtab_id
     1make symtab_pbgs_log
    22cd src
    33make all
  • 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
  • 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);
  • trunk/lib/symtab/pbgs_div_symbol_table.h

    r1387 r1391  
    108108
    109109    //Lookup
    110     GID = m_hashTable[group].Lookup_Name(name, hashvalue,L);
     110    GID = m_hashTable[group].Lookup_Name_17(name, hashvalue,L);
    111111
    112112    //Insert
  • trunk/lib/symtab/pbgs_identity_symbol_table.h

    r1387 r1391  
    66 * Identity grouping strategy.
    77 *
     8 * Identity group sorting        f(L) = L
     9 *
    810 */
    911
     
    1315#define DEBUG_PBGS 0
    1416
    15 // Define either one of grouping functions
    16 #define USE_IDENTITY_SORT       // f(L) = L
    17 //#define USE_LOG_SORT          // f(L) = ceil (log(L))
    18 //#define USE_DIV_SORT          // f(L) = floor( (L-1)/2^k )
    19 
    2017#define TOTAL_GROUPS 18
    2118#define LAST_GROUP TOTAL_GROUPS-1
     
    2320#define USE_FUNCTION_TEMPLATES
    2421#include "stringpool.h"
    25 #include "bitstream_hash_table.h"
     22#include "bitstream_id_hash_table.h"
    2623#include "ls_symbol_table_compare.h"
    2724#include "ls_symbol_table_util.h"
     
    4239    template <int L> inline int Lookup_or_Insert_Name(char* name, int hashvalue);
    4340
    44     // Use this function for 17 <= L <= 32
    45     inline int Lookup_or_Insert_Name_32(char* name, int hashvalue, int L);
    46 
    47     // Use this function for L > 32
     41    // Use this function for L > 16
    4842    inline int Lookup_or_Insert_Name(char* name, int hashvalue, int L);
    4943
     
    5246private:
    5347    StringPool <4096,100> m_pool;
    54     BitStreamHashTable m_hashTable[TOTAL_GROUPS];
     48    BitStreamIdentityHashTable m_hashTable[TOTAL_GROUPS];
    5549
    5650    inline int getHashTableIndex(int L);
     
    206200}
    207201
    208 // Use this function for 17 <= L <= 32
    209 inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name_32(char* name, int hashvalue, int L)
    210 {
    211     int GID = 0;
    212 
    213     //Lookup
    214     GID = m_hashTable[LAST_GROUP].Lookup_Name_32(name, hashvalue, L);
    215 
    216     //Insert
    217     if (!GID) //symbol not found
    218     {
    219         char* c = m_pool.Insert(name, L);
    220         GID = m_globalNameCount;
    221 
    222         m_hashTable[LAST_GROUP].Insert_Name(c, hashvalue, m_globalNameCount, L);
    223         m_globalNameCount++;
    224     }
    225 #if DEBUG_PBGS
    226     char delim = name[L];
    227     name[L] = '\0';
    228     cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << LAST_GROUP << endl;
    229     name[L] = delim;
    230 #endif
    231 
    232     return GID;
    233 }
    234 
    235 // Use this function for L > 32
     202// Use this function for L > 16
    236203inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue, int L)
    237204{
     
    244211
    245212    //Lookup
    246     GID = m_hashTable[group].Lookup_Name(name, hashvalue,L);
     213    GID = m_hashTable[group].Lookup_Name_17(name, hashvalue, L);
    247214
    248215    //Insert
  • trunk/lib/symtab/pbgs_log_symbol_table.h

    r1387 r1391  
    66 * Log grouping strategy.
    77 *
     8 * Log group sorting             f(L) = ceil (log(L))
     9 *
    810 */
    911
     
    2628#define USE_FUNCTION_TEMPLATES
    2729#include "stringpool.h"
    28 #include "bitstream_hash_table.h"
     30#include "bitstream_log_hash_table.h"
    2931#include "ls_symbol_table_compare.h"
    3032#include "ls_symbol_table_util.h"
     
    5759    inline int Lookup_or_Insert_Name_16(char* name, int hashvalue, int length);
    5860
    59     // Symbol length [17,32]
    60     inline int Lookup_or_Insert_Name_32(char* name, int hashvalue, int length);
    61 
    62     // Symbol length > 32
     61    // Symbol length > 16
    6362    inline int Lookup_or_Insert_Name(char* name, int hashvalue, int L);
    6463
     
    6867private:
    6968    StringPool <4096,100> m_pool;
    70     BitStreamHashTable m_hashTable[TOTAL_GROUPS];
     69    BitStreamLogHashTable m_hashTable[TOTAL_GROUPS];
    7170    int m_globalNameCount;
    7271};
     
    223222}
    224223
    225 // Use this function for 17 <= L <= 32
    226 inline int PBGSLogSymbolTable::Lookup_or_Insert_Name_32(char* name, int hashvalue, int L)
    227 {
    228     int GID = 0;
    229 
    230     //Lookup
    231     GID = m_hashTable[LAST_GROUP].Lookup_Name_32(name, hashvalue, L);
    232 
    233     //Insert
    234     if (!GID) //symbol not found
    235     {
    236         char* c = m_pool.Insert(name, L);
    237         GID = m_globalNameCount;
    238 
    239         m_hashTable[LAST_GROUP].Insert_Name(c, hashvalue, m_globalNameCount, L);
    240         m_globalNameCount++;
    241     }
    242 #if DEBUG_PBGS
    243     delim = name[L];
    244     name[L] = '\0';
    245     cout << "Lookup or Insert: " << name << " | lgth: " << L << " | bucket: " << LAST_BUCKET << endl;
    246     name[L] = delim;
    247 #endif
    248 
    249     return GID;
    250 }
    251 
    252 // Use this function for L > 32
     224// Use this function for L > 16
    253225inline int PBGSLogSymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue, int L)
    254226{
     
    260232
    261233    //Lookup
    262     GID = m_hashTable[LAST_GROUP].Lookup_Name(name, hashvalue,L);
     234    GID = m_hashTable[LAST_GROUP].Lookup_Name_17(name, hashvalue,L);
    263235
    264236    //Insert
Note: See TracChangeset for help on using the changeset viewer.