source: trunk/lib/symtab/pbgs_identity_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.4 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 * Identity grouping strategy.
7 *
8 */
9
10#ifndef PBGS_LENGTH_SYMBOL_TABLE_H
11#define PBGS_LENGTH_SYMBOL_TABLE_H
12
13#define DEBUG_PBGS 0
14
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
20#define TOTAL_GROUPS 18
21#define LAST_GROUP TOTAL_GROUPS-1
22
23#define USE_FUNCTION_TEMPLATES
24#include "stringpool.h"
25#include "bitstream_hash_table.h"
26#include "ls_symbol_table_compare.h"
27#include "ls_symbol_table_util.h"
28
29#if DEBUG_PBGS
30#include <iostream>
31using namespace std;
32#endif
33
34class PBGSIdentitySymbolTable
35{
36public:
37    PBGSIdentitySymbolTable()
38        :m_globalNameCount(1)
39    {};
40
41    // Use this function for 1 <= L <= 16
42    template <int L> inline int Lookup_or_Insert_Name(char* name, int hashvalue);
43
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
48    inline int Lookup_or_Insert_Name(char* name, int hashvalue, int L);
49
50    void Print_Symbol_Table_Distribution();
51
52private:
53    StringPool <4096,100> m_pool;
54    BitStreamHashTable m_hashTable[TOTAL_GROUPS];
55
56    inline int getHashTableIndex(int L);
57    int m_globalNameCount;
58};
59
60template <>
61        inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name<3>(char* name, int hashvalue)
62{
63    int GID = 0;
64    int group = getHashTableIndex(3);
65
66    //Lookup
67    GID = m_hashTable[group].Lookup_Name<3>(name, hashvalue);
68
69    //Insert
70    if (!GID) //symbol not found
71    {
72        char* c = m_pool.Insert(name, 3, 1);
73        GID = m_globalNameCount;
74
75        m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
76        m_globalNameCount++;
77    }
78#if DEBUG_PBGS
79    int advance = 1;
80    int L = 3;
81    char delim = name[L];
82    name[L] = '\0';
83    cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << " | advance: " << advance << endl;
84    name[L] = delim;
85#endif
86
87    return GID;
88}
89
90template <>
91        inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name<5>(char* name, int hashvalue)
92{
93    int GID = 0;
94    int group = getHashTableIndex(5);
95
96    //Lookup
97    GID = m_hashTable[group].Lookup_Name<5>(name, hashvalue);
98
99    //Insert
100    if (!GID) //symbol not found
101    {
102        char* c = m_pool.Insert(name, 5, 3);
103        GID = m_globalNameCount;
104
105        m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
106        m_globalNameCount++;
107    }
108#if DEBUG_PBGS
109    int advance = 3;
110    int L = 5;
111    char delim = name[L];
112    name[L] = '\0';
113    cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << " | advance: " << advance << endl;
114    name[L] = delim;
115#endif
116
117    return GID;
118}
119
120template <>
121        inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name<6>(char* name, int hashvalue)
122{
123    int GID = 0;
124    int group = getHashTableIndex(6);
125
126    //Lookup
127    GID = m_hashTable[group].Lookup_Name<6>(name, hashvalue);
128
129    //Insert
130    if (!GID) //symbol not found
131    {
132        char* c = m_pool.Insert(name, 6, 2);
133        GID = m_globalNameCount;
134
135        m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
136        m_globalNameCount++;
137    }
138#if DEBUG_PBGS
139    int advance = 2;
140    int L = 6;
141    char delim = name[L];
142    name[L] = '\0';
143    cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << " | advance: " << advance << endl;
144    name[L] = delim;
145#endif
146
147    return GID;
148}
149
150template <>
151        inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name<7>(char* name, int hashvalue)
152{
153    int GID = 0;
154    int group = getHashTableIndex(7);
155
156    //Lookup
157    GID = m_hashTable[group].Lookup_Name<7>(name, hashvalue);
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
169    int advance = 1;
170    int L = 7;
171    char 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
181template <int L> inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue)
182{
183    int GID = 0;
184    int group = getHashTableIndex(L);
185
186    //Lookup
187    GID = m_hashTable[group].Lookup_Name<L>(name, hashvalue);
188
189    //Insert
190    if (!GID) //symbol not found
191    {
192        char* c = m_pool.Insert(name, L);
193        GID = m_globalNameCount;
194
195        m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
196        m_globalNameCount++;
197    }
198#if DEBUG_PBGS
199    char delim = name[L];
200    name[L] = '\0';
201    cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << endl;
202    name[L] = delim;
203#endif
204
205    return GID;
206}
207
208// Use this function for 17 <= L <= 32
209inline 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
236inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue, int L)
237{
238    int GID = 0;
239
240#if DEBUG_PBGS
241    cout << "Lookup or Insert: " << name << endl;
242#endif
243    int group = getHashTableIndex(L);
244
245    //Lookup
246    GID = m_hashTable[group].Lookup_Name(name, hashvalue,L);
247
248    //Insert
249    if (!GID) //symbol not found
250    {
251        char* c = m_pool.Insert(name, L);
252        GID = m_globalNameCount;
253
254        m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
255        m_globalNameCount++;
256    }
257    return GID;
258}
259
260inline int PBGSIdentitySymbolTable::getHashTableIndex(int L)
261{
262    if (L > 16)
263        return LAST_GROUP;
264    else
265        return L;
266}
267
268void PBGSIdentitySymbolTable::Print_Symbol_Table_Distribution()
269{
270    for (int i = 0; i < TOTAL_GROUPS; i++)
271    {
272        fprintf (stderr, "Bucket #%i\n", i );
273        m_hashTable[i].Print_Symbol_Table_Distribution();
274    }
275}
276#endif // PBGS_LENGTH_SYMBOL_TABLE_H
277
278
Note: See TracBrowser for help on using the repository browser.