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

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

SymbolTable?: clean up and fix idisa library calls

File size: 3.4 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
49    void Print_Symbol_Table_Distribution();
50
51private:
52    StringPool <4096,100> m_pool;
53    BitStreamDivHashTable m_hashTable[TOTAL_GROUPS];
54    int m_globalNameCount;
55
56    inline int getHashTableIndex(int L);
57    inline bool isDelimiter(const char c);
58};
59
60// L should be an even number, L is in [1,16]
61template <int L> inline int PBGSDivSymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue)
62{
63    int GID = 0;
64    int group = getHashTableIndex(L);
65
66    //Lookup
67    GID = m_hashTable[group].Lookup_Name<L>(name, hashvalue);
68
69    if (!GID) //symbol not found
70    {
71        //Check if the last character is a delimiter
72        if (isDelimiter(name[L-1]))
73        {
74            //Do another lookup for name with L = L-1
75            GID = m_hashTable[group].Lookup_Name_Delimiter<L-1>(name, hashvalue);
76
77            if (GID)
78            {
79                //Symbol found, return immediately
80                return GID;
81            }
82        }
83
84        //Insert
85        char* c = m_pool.Insert(name, L);
86        GID = m_globalNameCount;
87
88        m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
89        m_globalNameCount++;
90    }
91#if DEBUG_PBGS_DIV
92    char delim = name[L];
93    name[L] = '\0';
94    cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << endl;
95    name[L] = delim;
96#endif
97
98    return GID;
99}
100
101// Use this function for L > 16
102inline int PBGSDivSymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue, int L)
103{
104    int GID = 0;
105
106#if DEBUG_PBGS_DIV
107    cout << "Lookup or Insert: " << name << endl;
108#endif
109    int group = getHashTableIndex(L);
110
111    //Lookup
112    GID = m_hashTable[group].Lookup_Name_17(name, hashvalue,L);
113
114    //Insert
115    if (!GID) //symbol not found
116    {
117        char* c = m_pool.Insert(name, L);
118        GID = m_globalNameCount;
119
120        m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);
121        m_globalNameCount++;
122    }
123    return GID;
124}
125
126
127inline bool PBGSDivSymbolTable::isDelimiter(const char c)
128{
129    return c == delimiters[(unsigned int) c & 0x7];
130}
131
132inline int PBGSDivSymbolTable::getHashTableIndex(int L)
133{
134    if (L > 16)
135        return LAST_GROUP;
136    else
137        return (L+1)/2;
138}
139
140void PBGSDivSymbolTable::Print_Symbol_Table_Distribution()
141{
142    for (int i = 0; i < TOTAL_GROUPS; i++)
143    {
144        fprintf (stderr, "Group #%i\n", i );
145        m_hashTable[i].Print_Symbol_Table_Distribution();
146    }
147}
148#endif // PBGS_DIV_SYMBOL_TABLE_H
149
150
Note: See TracBrowser for help on using the repository browser.