source: trunk/symtab/pbgs_identity_symbol_table.h @ 2136

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

SymbolTable?: Fixed custom hashing function for parallel bitstream based grouping

File size: 4.7 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 * Identity group sorting        f(L) = L
9 *
10 */
11
12#ifndef PBGS_LENGTH_SYMBOL_TABLE_H
13#define PBGS_LENGTH_SYMBOL_TABLE_H
14
15#define DEBUG_PBGS 0
16
17#define TOTAL_GROUPS 18
18#define LAST_GROUP TOTAL_GROUPS-1
19
20#define USE_FUNCTION_TEMPLATES
21#include "stringpool.h"
22#include "bitstream_super_hash_table.h"
23#include "bitstream_id_hash_table.h"
24#include "ls_symbol_table_compare.h"
25#include "ls_symbol_table_util.h"
26
27#if DEBUG_PBGS
28#include <iostream>
29using namespace std;
30#endif
31
32class PBGSIdentitySymbolTable
33{
34public:
35    PBGSIdentitySymbolTable();
36    ~PBGSIdentitySymbolTable();
37
38    // Use this function for 1 <= L <= 16
39    template <int L> inline int Lookup_or_Insert_Name(char* name, int hashvalue);
40
41    // Use this function for L > 16
42    inline int Lookup_or_Insert_Name(char* name, int hashvalue, int L);
43
44    void Print_Symbol_Table_Distribution();
45
46private:
47    StringPool <4096,100> m_pool;
48    BitStreamSuperHashTable* m_hashTable[TOTAL_GROUPS];
49
50    inline int getGroup(int L);
51    int m_globalNameCount;
52
53    template <int L> inline char* Store_Name(const char* name);
54};
55
56PBGSIdentitySymbolTable::PBGSIdentitySymbolTable()
57    :m_globalNameCount(1)
58{
59    m_hashTable[1] = new BitStreamIdentityHashTable<1>();
60    m_hashTable[2] = new BitStreamIdentityHashTable<2>();
61    m_hashTable[3] = new BitStreamIdentityHashTable<3>();
62    m_hashTable[4] = new BitStreamIdentityHashTable<4>();
63    m_hashTable[5] = new BitStreamIdentityHashTable<5>();
64    m_hashTable[6] = new BitStreamIdentityHashTable<6>();
65    m_hashTable[7] = new BitStreamIdentityHashTable<7>();
66    m_hashTable[8] = new BitStreamIdentityHashTable<8>();
67    m_hashTable[9] = new BitStreamIdentityHashTable<9>();
68    m_hashTable[10] = new BitStreamIdentityHashTable<10>();
69    m_hashTable[11] = new BitStreamIdentityHashTable<11>();
70    m_hashTable[12] = new BitStreamIdentityHashTable<12>();
71    m_hashTable[13] = new BitStreamIdentityHashTable<13>();
72    m_hashTable[14] = new BitStreamIdentityHashTable<14>();
73    m_hashTable[15] = new BitStreamIdentityHashTable<15>();
74    m_hashTable[16] = new BitStreamIdentityHashTable<16>();
75    m_hashTable[17] = new BitStreamIdentityHashTable<17>();
76};
77
78PBGSIdentitySymbolTable::~PBGSIdentitySymbolTable()
79{
80    for (int i = 1; i < TOTAL_GROUPS; i ++)
81    {
82        delete m_hashTable[i];
83        m_hashTable[i] = NULL;
84    }
85}
86
87template <> inline char* PBGSIdentitySymbolTable::Store_Name<3>(const char* name)
88{
89    return m_pool.Insert(name, 3, 1);
90}
91
92template <> inline char* PBGSIdentitySymbolTable::Store_Name<5>(const char* name)
93{
94    return m_pool.Insert(name, 5, 3);
95}
96
97template <> inline char* PBGSIdentitySymbolTable::Store_Name<6>(const char* name)
98{
99    return m_pool.Insert(name, 6, 2);
100}
101
102template <> inline char* PBGSIdentitySymbolTable::Store_Name<7>(const char* name)
103{
104    return m_pool.Insert(name, 7, 1);
105}
106
107template <int L> inline char* PBGSIdentitySymbolTable::Store_Name(const char* name)
108{
109    return m_pool.Insert(name, L);
110}
111
112// Use this function for 1 <= L <= 16
113template <int L> inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue)
114{
115    int GID = 0;
116    int group = getGroup(L);
117
118    //Lookup
119    GID = ((BitStreamIdentityHashTable<L>*)m_hashTable[group])->Lookup_Name(name, hashvalue);
120
121    //Insert
122    if (!GID) //symbol not found
123    {
124        char* c = Store_Name<L>(name);
125        GID = m_globalNameCount;
126
127        ((BitStreamIdentityHashTable<L>*)m_hashTable[group])->Insert_Name(c, hashvalue, m_globalNameCount);
128        m_globalNameCount++;
129    }
130#if DEBUG_PBGS
131    char delim = name[L];
132    name[L] = '\0';
133    cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << endl;
134    name[L] = delim;
135#endif
136
137    return GID;
138}
139
140// Use this function for L > 16
141inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue, int lgth)
142{
143    int GID = 0;
144
145#if DEBUG_PBGS
146    cout << "Lookup or Insert: " << name << endl;
147#endif
148
149    //Lookup
150    GID = ((BitStreamIdentityHashTable<17>*)m_hashTable[LAST_GROUP])->Lookup_Name_17(name, hashvalue, lgth);
151
152    //Insert
153    if (!GID) //symbol not found
154    {
155        char* c = m_pool.Insert(name, lgth);
156        GID = m_globalNameCount;
157
158        ((BitStreamIdentityHashTable<17>*)m_hashTable[LAST_GROUP])->Insert_Name(c, hashvalue, m_globalNameCount, lgth);
159        m_globalNameCount++;
160    }
161    return GID;
162}
163
164inline int PBGSIdentitySymbolTable::getGroup(int L)
165{
166    if (L > 16)
167        return LAST_GROUP;
168    else
169        return L;
170}
171
172void PBGSIdentitySymbolTable::Print_Symbol_Table_Distribution()
173{
174    for (int i = 1; i < TOTAL_GROUPS; i ++)
175    {
176        printf ("Group #%i\n", i );
177        m_hashTable[i]->Print_Symbol_Table_Distribution();
178    }
179
180}
181#endif // PBGS_LENGTH_SYMBOL_TABLE_H
182
183
Note: See TracBrowser for help on using the repository browser.