source: trunk/lib/symtab/pbgs_log_symbol_table.h @ 1387

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

Symbol Table: Implemented division by 2 grouping strategy

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