source: trunk/lib/symtab/bitstream_hash_table.h @ 1391

Last change on this file since 1391 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: 4.6 KB
Line 
1/*
2 * Created on: 26-August-2011
3 * Author: Vera Lukman
4 *
5 * This hash table is almost an exact copy of HashSymbolTable except that
6 * BitStreamDivHashTable accepts a hashvalue to insert or lookup for a key.
7 * This hash table is designed specifically for Parallel Bitstream-Based Length Sorting Symbol Table.
8 * It is the base class of BitstreamIdentityHashTable, BitstreamLogHashTable and BitstreamDivHashTable.
9 *
10 * Each grouping strategy use different comparison strategy
11 * Identity group sorting        f(L) = L
12 * Log group sorting             f(L) = ceil (log(L))
13 * Division group sorting        f(L) = floor( (L-1)/2^k )
14 *
15 */
16
17#ifndef BITSTREAM_HASH_TABLE_H
18#define BITSTREAM_HASH_TABLE_H
19
20#define DEBUG_BHT 0
21
22#define TABLE_SIZE 256
23#define TABLE_SIZE_MASK TABLE_SIZE-1
24
25#include <stdlib.h>
26#include "pbgs_utilities.h"
27#include "ls_symbol_table_util.h"
28
29
30class BitStreamHashTable
31{
32
33public:
34    BitStreamHashTable();
35    ~BitStreamHashTable();
36
37    // Symbol length > 16
38    inline unsigned int Lookup_Name_17(char * name, const int hashvalue, int L);
39
40    inline void Insert_Name(char * name, const int hashvalue, const unsigned int gid);
41    inline void Insert_Name(char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth);
42
43    // DEBUG FUNCTIONS
44    void Print_Symbol_Table_Distribution();
45
46protected:
47    struct CHAIN {
48        const char* key;
49        struct CHAIN* next;
50        unsigned int GID;
51        unsigned int lgth;
52    };
53
54    CHAIN ** g_table;
55    inline unsigned int getIndex(const int hashvalue);
56
57private:
58    void free_chain(CHAIN* chain);
59    inline void SetTableSize(unsigned int table_bits, unsigned int table_bits_factor);
60    inline unsigned int NextLog2(unsigned int x);
61};
62
63BitStreamHashTable::BitStreamHashTable()
64{
65    g_table = (CHAIN**) calloc(TABLE_SIZE, sizeof(CHAIN*));
66    memset(g_table, 0, TABLE_SIZE*sizeof(CHAIN*));
67}
68
69BitStreamHashTable::~BitStreamHashTable()
70{
71    for(int hash = 0; hash < TABLE_SIZE; hash++)
72    {
73        free_chain(g_table[hash]);
74    }
75    free(g_table);
76}
77
78// Use this method if L > 16
79unsigned int BitStreamHashTable::Lookup_Name_17(char * name, const int hashvalue, int L)
80{
81    unsigned int hash = getIndex(hashvalue);
82
83    // Look up the value in the chain
84    for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
85#if DEBUG_BHT
86        printf ("Check symbol: %s\n", chain->key);
87#endif
88        if( simd_compare ((unsigned char*)chain->key, (unsigned char*)name, L) )
89        {
90#if DEBUG_BHT
91            printf ("Found GID: %i\n", chain->GID);
92#endif
93            return chain->GID;
94        }
95    }
96
97#if DEBUG_BHT
98    printf ("Not Found GID: %i\n", 0);
99#endif
100    return 0;
101}
102
103inline void BitStreamHashTable::Insert_Name(char * name, const int hashvalue, const unsigned int gid)
104{
105    unsigned int hash = getIndex(hashvalue);
106
107    // If it was not found, add it
108    CHAIN* next = g_table[hash];
109    g_table[hash] = (CHAIN*) malloc(sizeof(CHAIN*));
110    g_table[hash]->next = next;
111    g_table[hash]->key = name;
112    g_table[hash]->GID = gid;
113
114#if DEBUG_BHT
115    printf ("Given GID: %i | Stored GID: %i\n", gid, g_table[hash]->GID);
116#endif
117}
118
119inline void BitStreamHashTable::Insert_Name(char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth)
120{
121    unsigned int hash = getIndex(hashvalue);
122
123    // If it was not found, add it
124    CHAIN* next = g_table[hash];
125    g_table[hash] = (CHAIN*) malloc(sizeof(CHAIN*));
126    g_table[hash]->next = next;
127    g_table[hash]->key = name;
128    g_table[hash]->GID = gid;
129    g_table[hash]->lgth = lgth;
130
131#if DEBUG_BHT
132    printf ("Given GID: %i | Stored GID: %i\n", gid, g_table[hash]->GID);
133#endif
134}
135
136inline unsigned int BitStreamHashTable::getIndex(const int hashvalue)
137{
138    return hashvalue & TABLE_SIZE_MASK;
139}
140
141inline unsigned int BitStreamHashTable::NextLog2(unsigned int x)
142{
143    // Henry Warren, "Hacker's Delight", ch. 5.3
144    if(x <= 1) return x;
145    x--;
146    unsigned int n = 0;
147    unsigned int y;
148    y = x >>16; if(y) {n += 16; x = y;}
149    y = x >> 8; if(y) {n +=  8; x = y;}
150    y = x >> 4; if(y) {n +=  4; x = y;}
151    y = x >> 2; if(y) {n +=  2; x = y;}
152    y = x >> 1; if(y) return n + 2;
153    return n + x;
154}
155
156void BitStreamHashTable::Print_Symbol_Table_Distribution()
157{
158    for(int hash = 0; hash < TABLE_SIZE; hash++)
159    {
160        int items = 0;
161        for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next)
162        {
163            items++;
164        }
165        if (items >= 1)
166        {
167            fprintf (stderr, "\tBucket: %i | #items: %i\n", hash, items);
168        }
169    }
170}
171
172void BitStreamHashTable::free_chain(CHAIN* chain)
173{
174    if (chain == NULL)
175    {
176        return;
177    }
178
179    if (chain->next != NULL)
180    {
181        free_chain(chain->next);
182    }
183    free(chain);
184    chain = NULL;
185}
186
187#endif // BITSTREAM_HASH_TABLE_H
Note: See TracBrowser for help on using the repository browser.