source: trunk/lib/symtab/pbgs_div_symbol_table.h @ 1391

Last change on this file since 1391 was 1391, checked in by vla24, 8 years ago

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

File size: 3.1 KB
Line 
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
10#ifndef PBGS_DIV_SYMBOL_TABLE_H
11#define PBGS_DIV_SYMBOL_TABLE_H
12
13#define DEBUG_PBGS_DIV 0
14
15// Define either one of grouping functions
16//#define USE_LENGTH_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)
19
20#define TOTAL_GROUPS 10
21#define LAST_GROUP TOTAL_GROUPS-1
22
23#define USE_FUNCTION_TEMPLATES
24#include "stringpool.h"
25#include "bitstream_div_hash_table.h"
26#include "ls_symbol_table_compare.h"
27#include "ls_symbol_table_util.h"
28
29#if DEBUG_PBGS_DIV
30#include <iostream>
31using namespace std;
32#endif
33                           //0     1     2    3     4    5    6    7
34static char delimiters[] = {' ', '\0', '\0', ';', '\0', '=', '>', '/'};
35
36class PBGSDivSymbolTable
37{
38public:
39    PBGSDivSymbolTable()
40        :m_globalNameCount(1)
41    {};
42
43    template <int L> inline int Lookup_or_Insert_Name(char* name, int hashvalue);
44
45    inline int Lookup_or_Insert_Name_32(char* name, int hashvalue, int L);
46
47    inline int Lookup_or_Insert_Name(char* name, int hashvalue, int L);
48
49private:
50    StringPool <4096,100> m_pool;
51    BitStreamDivHashTable m_hashTable[TOTAL_GROUPS];
52    int m_globalNameCount;
53
54    inline int getHashTableIndex(int L);
55    inline bool isDelimiter(const char c);
56};
57
58// L should be an even number, L is in [1,16]
59template <int L> inline int PBGSDivSymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue)
60{
61    int GID = 0;
62    int group = getHashTableIndex(L);
63
64    //Lookup
65    GID = m_hashTable[group].Lookup_Name<L>(name, hashvalue);
66
67    if (!GID) //symbol not found
68    {
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
83        char* c = m_pool.Insert(name, L);
84        GID = m_globalNameCount;
85
86        m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
87        m_globalNameCount++;
88    }
89#if DEBUG_PBGS_DIV
90    char delim = name[L];
91    name[L] = '\0';
92    cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << endl;
93    name[L] = delim;
94#endif
95
96    return GID;
97}
98
99// Use this function for L > 16
100inline int PBGSDivSymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue, int L)
101{
102    int GID = 0;
103
104#if DEBUG_PBGS_DIV
105    cout << "Lookup or Insert: " << name << endl;
106#endif
107    int group = getHashTableIndex(L);
108
109    //Lookup
110    GID = m_hashTable[group].Lookup_Name_17(name, hashvalue,L);
111
112    //Insert
113    if (!GID) //symbol not found
114    {
115        char* c = m_pool.Insert(name, L);
116        GID = m_globalNameCount;
117
118        m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
119        m_globalNameCount++;
120    }
121    return GID;
122}
123
124
125inline bool PBGSDivSymbolTable::isDelimiter(const char c)
126{
127    return c == delimiters[(unsigned int) c & 0x7];
128}
129
130inline int PBGSDivSymbolTable::getHashTableIndex(int L)
131{
132    if (L > 16)
133        return LAST_GROUP;
134    else
135        return (L+1)/2;
136}
137#endif // PBGS_DIV_SYMBOL_TABLE_H
138
139
Note: See TracBrowser for help on using the repository browser.