Ignore:
Timestamp:
Aug 26, 2011, 11:42:51 AM (8 years ago)
Author:
vla24
Message:

Symbol Table: Implemented division by 2 grouping strategy

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/lib/symtab/pbgs_div_symbol_table.h

    r1229 r1387  
     1/*
     2 * Created on: 8-August-2011
     3 * Author: Vera Lukman
     4 *
     5 * This symbol table is designed specifically for Parallel Bitstream-Based Length Sorting
     6 * Division by 2 grouping strategy.
     7 *
     8 */
     9
    110#ifndef PBGS_DIV_SYMBOL_TABLE_H
    211#define PBGS_DIV_SYMBOL_TABLE_H
     
    716//#define USE_LENGTH_SORT       // f(L) = L
    817//#define USE_LOG_SORT          // f(L) = ceil (log(L))
    9 #define USE_DIV_SORT            // f(L) = floor( (L-1)/2^k )
     18#define USE_DIV_SORT            // f(L) = floor ((L+1)/2)
    1019
    11 #define TOTAL_GROUPS 5
     20#define TOTAL_GROUPS 10
    1221#define LAST_GROUP TOTAL_GROUPS-1
    1322
    1423#define USE_FUNCTION_TEMPLATES
    1524#include "stringpool.h"
    16 #include "bitstream_hash_table.h"
     25#include "bitstream_div_hash_table.h"
    1726#include "ls_symbol_table_compare.h"
    1827#include "ls_symbol_table_util.h"
     
    2231using namespace std;
    2332#endif
     33                           //0     1     2    3     4    5    6    7
     34static char delimiters[] = {' ', '\0', '\0', ';', '\0', '=', '>', '/'};
    2435
    2536class PBGSDivSymbolTable
     
    3243    template <int L> inline int Lookup_or_Insert_Name(char* name, int hashvalue);
    3344
     45    inline int Lookup_or_Insert_Name_32(char* name, int hashvalue, int L);
     46
    3447    inline int Lookup_or_Insert_Name(char* name, int hashvalue, int L);
    3548
    3649private:
    3750    StringPool <4096,100> m_pool;
    38     BitStreamHashTable m_hashTable[TOTAL_GROUPS];
     51    BitStreamDivHashTable m_hashTable[TOTAL_GROUPS];
     52    int m_globalNameCount;
    3953
    4054    inline int getHashTableIndex(int L);
    41     int m_globalNameCount;
     55    inline bool isDelimiter(const char c);
    4256};
    4357
    44 template <>
    45         inline int PBGSDivSymbolTable::Lookup_or_Insert_Name<3>(char* name, int hashvalue)
    46 {
    47     int GID = 0;
    48 
    49     char delim = name[3];
    50     name[3] = '\0';
    51     int group = getHashTableIndex(3);
    52 
    53     //Lookup
    54     GID = m_hashTable[group].Lookup_Name<3>(name, hashvalue);
    55     name[3] = delim;
    56 
    57     //Insert
    58     if (!GID) //symbol not found
    59     {
    60         char* c = m_pool.Insert(name, 3, 1);
    61         GID = m_globalNameCount;
    62 
    63         m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
    64         m_globalNameCount++;
    65     }
    66 #if DEBUG_PBGS_DIV
    67     int advance = 1;
    68     int L = 3;
    69     delim = name[L];
    70     name[L] = '\0';
    71     cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << " | advance: " << advance << endl;
    72     name[L] = delim;
    73 #endif
    74 
    75     return GID;
    76 }
    77 
    78 template <>
    79         inline int PBGSDivSymbolTable::Lookup_or_Insert_Name<5>(char* name, int hashvalue)
    80 {
    81     int GID = 0;
    82 
    83     char delim = name[5];
    84     name[5] = '\0';
    85     int group = getHashTableIndex(5);
    86 
    87     //Lookup
    88     GID = m_hashTable[group].Lookup_Name<5>(name, hashvalue);
    89     name[5] = delim;
    90 
    91     //Insert
    92     if (!GID) //symbol not found
    93     {
    94         char* c = m_pool.Insert(name, 5, 3);
    95         GID = m_globalNameCount;
    96 
    97         m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
    98         m_globalNameCount++;
    99     }
    100 #if DEBUG_PBGS_DIV
    101     int advance = 3;
    102     int L = 5;
    103     delim = name[L];
    104     name[L] = '\0';
    105     cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << " | advance: " << advance << endl;
    106     name[L] = delim;
    107 #endif
    108 
    109     return GID;
    110 }
    111 
    112 template <>
    113         inline int PBGSDivSymbolTable::Lookup_or_Insert_Name<6>(char* name, int hashvalue)
    114 {
    115     int GID = 0;
    116 
    117     char delim = name[6];
    118     name[6] = '\0';
    119     int group = getHashTableIndex(6);
    120 
    121     //Lookup
    122     GID = m_hashTable[group].Lookup_Name<6>(name, hashvalue);
    123     name[6] = delim;
    124 
    125     //Insert
    126     if (!GID) //symbol not found
    127     {
    128         char* c = m_pool.Insert(name, 6, 2);
    129         GID = m_globalNameCount;
    130 
    131         m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
    132         m_globalNameCount++;
    133     }
    134 #if DEBUG_PBGS_DIV
    135     int advance = 2;
    136     int L = 6;
    137     delim = name[L];
    138     name[L] = '\0';
    139     cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << " | advance: " << advance << endl;
    140     name[L] = delim;
    141 #endif
    142 
    143     return GID;
    144 }
    145 
    146 template <>
    147         inline int PBGSDivSymbolTable::Lookup_or_Insert_Name<7>(char* name, int hashvalue)
    148 {
    149     int GID = 0;
    150 
    151     char delim = name[7];
    152     name[7] = '\0';
    153     int group = getHashTableIndex(7);
    154 
    155     //Lookup
    156     GID = m_hashTable[group].Lookup_Name<7>(name, hashvalue);
    157     name[7] = delim;
    158 
    159     //Insert
    160     if (!GID) //symbol not found
    161     {
    162         char* c = m_pool.Insert(name, 7, 1);
    163         GID = m_globalNameCount;
    164 
    165         m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
    166         m_globalNameCount++;
    167     }
    168 #if DEBUG_PBGS_DIV
    169     int advance = 1;
    170     int L = 7;
    171     delim = name[L];
    172     name[L] = '\0';
    173     cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << " | advance: " << advance << endl;
    174     name[L] = delim;
    175 #endif
    176 
    177     return GID;
    178 }
    179 
    180 // Use this function for 1,2, 4, 8 <= L <= 32
     58// L should be an even number, L is in [1,16]
    18159template <int L> inline int PBGSDivSymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue)
    18260{
    18361    int GID = 0;
    184 
    185     char delim = name[L];
    186     name[L] = '\0';
    18762    int group = getHashTableIndex(L);
    18863
    18964    //Lookup
    19065    GID = m_hashTable[group].Lookup_Name<L>(name, hashvalue);
    191     name[L] = delim;
    19266
    193     //Insert
    19467    if (!GID) //symbol not found
    19568    {
     69        //Check if the last character is a delimiter
     70        if (isDelimiter(name[L-1]))
     71        {
     72            //Do another lookup for name with L = L-1
     73            GID = m_hashTable[group].Lookup_Name_Delimiter<L-1>(name, hashvalue);
     74
     75            if (GID)
     76            {
     77                //Symbol found, return immediately
     78                return GID;
     79            }
     80        }
     81
     82        //Insert
    19683        char* c = m_pool.Insert(name, L);
    19784        GID = m_globalNameCount;
     
    20188    }
    20289#if DEBUG_PBGS_DIV
    203     delim = name[L];
     90    char delim = name[L];
    20491    name[L] = '\0';
    20592    cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << endl;
     
    21097}
    21198
    212 // Use this function for L > 32
     99// Use this function for L > 16
    213100inline int PBGSDivSymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue, int L)
    214101{
    215102    int GID = 0;
    216 
    217     char delim = name[L];
    218     name[L] = '\0';
    219103
    220104#if DEBUG_PBGS_DIV
     
    225109    //Lookup
    226110    GID = m_hashTable[group].Lookup_Name(name, hashvalue,L);
    227 
    228     name[L] = delim;
    229111
    230112    //Insert
     
    240122}
    241123
     124
     125inline bool PBGSDivSymbolTable::isDelimiter(const char c)
     126{
     127    return c == delimiters[(unsigned int) c & 0x7];
     128}
     129
    242130inline int PBGSDivSymbolTable::getHashTableIndex(int L)
    243131{
     
    245133        return LAST_GROUP;
    246134    else
    247         return L/4;
     135        return (L+1)/2;
    248136}
    249137#endif // PBGS_DIV_SYMBOL_TABLE_H
Note: See TracChangeset for help on using the changeset viewer.