source: trunk/symtab/pbgs_log_symbol_table.h @ 2088

Last change on this file since 2088 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: 5.8 KB
Line 
1/*
2 * Created: 2011
3 * Author: Vera Lukman
4 *
5 * This symbol table is designed specifically for Parallel Bitstream-Based Length Sorting
6 * Log grouping strategy.
7 *
8 * Log group sorting             f(L) = ceil (log(L))
9 *
10 */
11
12
13#ifndef PBGS_SYMBOL_TABLE_H
14#define PBGS_SYMBOL_TABLE_H
15
16#define DEBUG_PBGS_LOG 0
17
18// Define either one of grouping functions
19//#define USE_IDENTITY_SORT     // f(L) = L
20#define USE_LOG_SORT            // f(L) = ceil (log(L))
21//#define USE_DIV_SORT          // f(L) = floor( (L-1)/2^k )
22
23//#define USE_MASK_COMPARE    //Comparison using masking technique.
24
25#define TOTAL_GROUPS 6
26#define LAST_GROUP TOTAL_GROUPS-1
27
28#define USE_FUNCTION_TEMPLATES
29#include "stringpool.h"
30#include "bitstream_log_hash_table.h"
31#include "ls_symbol_table_compare.h"
32#include "ls_symbol_table_util.h"
33
34#if DEBUG_PBGS_LOG
35#include <iostream>
36using namespace std;
37#endif
38
39class PBGSLogSymbolTable
40{
41public:
42    PBGSLogSymbolTable()
43        :m_globalNameCount(1)
44    {};
45
46    // Symbol length 1
47    inline int Lookup_or_Insert_Name_1(char* name, int hashvalue);
48
49    // Symbol length 2
50    inline int Lookup_or_Insert_Name_2(char* name, int hashvalue);
51
52    // Symbol length [3,4]
53    inline int Lookup_or_Insert_Name_4(char* name, int hashvalue, int length);
54
55    // Symbol length [5,8]
56    inline int Lookup_or_Insert_Name_8(char* name, int hashvalue, int length);
57
58    // Symbol length [9,16]
59    inline int Lookup_or_Insert_Name_16(char* name, int hashvalue, int length);
60
61    // Symbol length > 16
62    inline int Lookup_or_Insert_Name(char* name, int hashvalue, int L);
63
64    //DEBUG
65    void Print_Symbol_Table_Distribution();
66
67private:
68    StringPool <4096,100> m_pool;
69    BitStreamLogHashTable m_hashTable[TOTAL_GROUPS];
70    int m_globalNameCount;
71};
72
73inline int PBGSLogSymbolTable::Lookup_or_Insert_Name_1(char* name, int hashvalue)
74{
75    int GID = 0;
76
77    //Lookup
78    GID = m_hashTable[0].Lookup_Name_1(name, hashvalue);
79
80    //Insert
81    if (!GID) //symbol not found
82    {
83        char* c = m_pool.Insert(name, 1);
84        GID = m_globalNameCount;
85
86#ifdef USE_MASK_COMPARE
87        m_hashTable[0].Insert_Name(c, hashvalue, m_globalNameCount);
88#else
89        m_hashTable[0].Insert_Name(c, hashvalue, m_globalNameCount, 1);
90#endif
91        m_globalNameCount++;
92    }
93#if DEBUG_PBGS_LOG
94    int L = 1;
95    int group = 0;
96    delim = name[L];
97    name[L] = '\0';
98    cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << endl;
99    name[L] = delim;
100#endif
101
102    return GID;
103}
104
105inline int PBGSLogSymbolTable::Lookup_or_Insert_Name_2(char* name, int hashvalue)
106{
107    int GID = 0;
108
109    //Lookup
110    GID = m_hashTable[1].Lookup_Name_2(name, hashvalue);
111
112    //Insert
113    if (!GID) //symbol not found
114    {
115        char* c = m_pool.Insert(name, 2);
116        GID = m_globalNameCount;
117
118#ifdef USE_MASK_COMPARE
119        m_hashTable[1].Insert_Name(c, hashvalue, m_globalNameCount);
120#else
121        m_hashTable[1].Insert_Name(c, hashvalue, m_globalNameCount, 2);
122#endif
123        m_globalNameCount++;
124    }
125#if DEBUG_PBGS_LOG
126    int L = 2;
127    int group = 1;
128    delim = name[L];
129    name[L] = '\0';
130    cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << endl;
131    name[L] = delim;
132#endif
133
134    return GID;
135}
136
137inline int PBGSLogSymbolTable::Lookup_or_Insert_Name_4(char* name, int hashvalue, int length)
138{
139    int GID = 0;
140
141    //Lookup
142    GID = m_hashTable[2].Lookup_Name_4(name, hashvalue, length);
143
144    //Insert
145    if (!GID) //symbol not found
146    {
147        GID = m_globalNameCount;
148
149        char* c = m_pool.Insert(name, length);
150#ifdef USE_MASK_COMPARE
151        m_hashTable[2].Insert_Name(c, hashvalue, m_globalNameCount);
152#else
153        m_hashTable[2].Insert_Name(c, hashvalue, m_globalNameCount, length);
154#endif
155        m_globalNameCount++;
156    }
157#if DEBUG_PBGS_LOG
158    int group = 2;
159    int L = length;
160    delim = name[L];
161    name[L] = '\0';
162    cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << endl;
163    name[L] = delim;
164#endif
165
166    return GID;
167}
168
169inline int PBGSLogSymbolTable::Lookup_or_Insert_Name_8(char* name, int hashvalue, int length)
170{
171    int GID = 0;
172
173    //Lookup
174    GID = m_hashTable[3].Lookup_Name_8(name, hashvalue, length);
175
176    //Insert
177    if (!GID) //symbol not found
178    {
179        GID = m_globalNameCount;
180        char* c = m_pool.Insert(name, length);
181        m_hashTable[3].Insert_Name(c, hashvalue, m_globalNameCount, length);
182        m_globalNameCount++;
183    }
184#if DEBUG_PBGS_LOG
185    int group = 3;
186    int L = length;
187    delim = name[L];
188    name[L] = '\0';
189    cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << endl;
190    name[L] = delim;
191#endif
192
193    return GID;
194}
195
196inline int PBGSLogSymbolTable::Lookup_or_Insert_Name_16(char* name, int hashvalue, int length)
197{
198    int GID = 0;
199
200    //Lookup
201    GID = m_hashTable[4].Lookup_Name_16(name, hashvalue, length);
202
203    //Insert
204    if (!GID) //symbol not found
205    {
206        char* c = m_pool.Insert(name, length);
207        GID = m_globalNameCount;
208
209        m_hashTable[4].Insert_Name(c, hashvalue, m_globalNameCount, length);
210        m_globalNameCount++;
211    }
212#if DEBUG_PBGS_LOG
213    int group = 4;
214    int L = length;
215    delim = name[L];
216    name[L] = '\0';
217    cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << endl;
218    name[L] = delim;
219#endif
220
221    return GID;
222}
223
224// Use this function for L > 16
225inline int PBGSLogSymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue, int L)
226{
227    int GID = 0;
228
229#if DEBUG_PBGS_LOG
230    cout << "Lookup or Insert: " << name << endl;
231#endif
232
233    //Lookup
234    GID = m_hashTable[LAST_GROUP].Lookup_Name_17(name, hashvalue,L);
235
236    //Insert
237    if (!GID) //symbol not found
238    {
239        char* c = m_pool.Insert(name, L);
240        GID = m_globalNameCount;
241
242        m_hashTable[LAST_GROUP].Insert_Name(c, hashvalue, m_globalNameCount);
243        m_globalNameCount++;
244    }
245    return GID;
246}
247
248void PBGSLogSymbolTable::Print_Symbol_Table_Distribution()
249{
250    for (int i = 0; i < TOTAL_GROUPS; i++)
251    {
252        fprintf (stderr, "Group #%i\n", i );
253        m_hashTable[i].Print_Symbol_Table_Distribution();
254    }
255}
256#endif // PBLS_SYMBOL_TABLE_H
Note: See TracBrowser for help on using the repository browser.