source: trunk/lib/symtab/bitstream_hash_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: 9.9 KB
Line 
1/*
2 * Created: 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
8 * identity and log grouping strategy.
9 *
10 */
11
12#ifndef BITSTREAM_HASH_TABLE_H
13#define BITSTREAM_HASH_TABLE_H
14
15#define DEBUG_BHT 0
16
17#define USE_FUNCTION_TEMPLATES
18#define TABLE_SIZE 256
19#define TABLE_SIZE_MASK TABLE_SIZE-1
20
21// Define either one of grouping functions
22// Each grouping strategy use different comparison strategy
23//#define USE_IDENTITY_SORT     // f(L) = L
24//#define USE_LOG_SORT          // f(L) = ceil (log(L))
25//#define USE_DIV_SORT          // f(L) = floor( (L-1)/2^k )
26
27//#define USE_MASK_COMPARE    //Comparison using masking technique.
28                            //This technique only applies to USE_LOG_SORT
29
30#include <stdlib.h>
31#include "equal_compare.h"
32#include "ls_symbol_table_util.h"
33#include "limits.h"
34
35class BitStreamHashTable
36{
37    struct CHAIN {
38        const char* key;
39        struct CHAIN* next;
40        unsigned int GID;
41        unsigned int lgth;
42    };
43
44public:
45    BitStreamHashTable()
46    {
47        g_table = (CHAIN**) calloc(TABLE_SIZE, sizeof(CHAIN*));
48        memset(g_table, 0, TABLE_SIZE*sizeof(CHAIN*));
49    }
50
51    ~BitStreamHashTable()
52    {
53        for(int hash = 0; hash < TABLE_SIZE; hash++)
54        {
55            free_chain(g_table[hash]);
56        }
57        free(g_table);
58    }
59
60
61    //Returns 0 upon failure
62#if defined(USE_IDENTITY_SORT) || defined(USE_DIV_SORT)
63    // Symbol length [1,32]
64    template <int L> inline unsigned int Lookup_Name(char * name, const int hashvalue);
65#endif
66#if defined (USE_LOG_SORT)
67    // Symbol length 1
68    inline unsigned int Lookup_Name_1(char * name, const int hashvalue);
69
70    // Symbol length 2
71    inline unsigned int Lookup_Name_2(char * name, const int hashvalue);
72
73    // Symbol length [3,4]
74    inline unsigned int Lookup_Name_4(char * name, const int hashvalue, int L);
75
76    // Symbol length [5,8]
77    inline unsigned int Lookup_Name_8(char * name, const int hashvalue, int L);
78
79    // Symbol length [9,16]
80    inline unsigned int Lookup_Name_16(char * name, const int hashvalue, int L);
81#endif
82
83    // Symbol length [17,32]
84    inline unsigned int Lookup_Name_32(char * name, const int hashvalue, int L);
85
86    // Symbol length > 32
87    inline unsigned int Lookup_Name(char * name, const int hashvalue, int L);
88
89    inline void Insert_Name(char * name, const int hashvalue, const unsigned int gid);
90    inline void Insert_Name(char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth);
91
92    // DEBUG FUNCTION
93    void Print_Symbol_Table_Distribution();
94
95    void free_chain(CHAIN* chain);
96
97private:
98    CHAIN ** g_table;
99
100    inline void SetTableSize(unsigned int table_bits, unsigned int table_bits_factor);
101
102    inline unsigned int getIndex(const int hashvalue);
103
104    inline unsigned int NextLog2(unsigned int x);
105};
106
107#if defined(USE_IDENTITY_SORT) || defined(USE_DIV_SORT)
108template <int L>
109        inline unsigned int BitStreamHashTable::Lookup_Name(char * name, const int hashvalue)
110{
111    unsigned int hash = getIndex(hashvalue);
112
113    // Look up the value in the chain
114    for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
115#if DEBUG_BHT
116        printf ("Check symbol: %s\n", chain->key);
117#endif
118        if( equal_compare <L> ((unsigned char*)chain->key, (unsigned char*)name) )
119        {
120#if DEBUG_BHT
121            printf ("Found GID: %i\n", chain->GID);
122#endif
123            return chain->GID;
124        }
125    }
126
127#if DEBUG_BHT
128    printf ("Not Found GID: %i\n", 0);
129#endif
130    return 0;
131}
132#endif
133
134#if defined (USE_LOG_SORT)
135inline unsigned int BitStreamHashTable::Lookup_Name_1(char * name, const int hashvalue)
136{
137    unsigned int hash = getIndex(hashvalue);
138
139    // Look up the value in the chain
140    for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
141#if DEBUG_BHT
142        printf ("Check symbol: %s\n", chain->key);
143#endif
144        if( equal_compare_1 ((unsigned char*)chain->key, (unsigned char*)name) )
145        {
146#if DEBUG_BHT
147            printf ("Found GID: %i\n", chain->GID);
148#endif
149            return chain->GID;
150        }
151    }
152
153#if DEBUG_BHT
154    printf ("Not Found GID: %i\n", 0);
155#endif
156    return 0;
157}
158
159inline unsigned int BitStreamHashTable::Lookup_Name_2(char * name, const int hashvalue)
160{
161    unsigned int hash = getIndex(hashvalue);
162
163    // Look up the value in the chain
164    for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
165#if DEBUG_BHT
166        printf ("Check symbol: %s\n", chain->key);
167#endif
168        if( equal_compare_2 ((unsigned char*)chain->key, (unsigned char*)name) )
169        {
170#if DEBUG_BHT
171            printf ("Found GID: %i\n", chain->GID);
172#endif
173            return chain->GID;
174        }
175    }
176
177#if DEBUG_BHT
178    printf ("Not Found GID: %i\n", 0);
179#endif
180    return 0;
181}
182
183// Use this method if L is in [3,4]
184inline unsigned int BitStreamHashTable::Lookup_Name_4(char * name, const int hashvalue, int L)
185{
186    unsigned int hash = getIndex(hashvalue);
187
188    // Look up the value in the chain
189    for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
190#if DEBUG_BHT
191        printf ("Check symbol: %s\n", chain->key);
192#endif
193
194#ifdef USE_MASK_COMPARE
195        if( equal_compare_4 ((unsigned char*)chain->key, (unsigned char*)name, L) )
196        {
197#else
198        if( equal_compare<uint16_t>((unsigned char*)chain->key, (unsigned char*)name, chain->lgth, L) )
199        {
200#endif
201#if DEBUG_BHT
202            printf ("Found GID: %i\n", chain->GID);
203#endif
204            return chain->GID;
205        }
206    }
207
208#if DEBUG_BHT
209    printf ("Not Found GID: %i\n", 0);
210#endif
211    return 0;
212}
213
214// Use this method if L is in [5,8]
215inline unsigned int BitStreamHashTable::Lookup_Name_8(char * name, const int hashvalue, int L)
216{
217    unsigned int hash = getIndex(hashvalue);
218
219    // Look up the value in the chain
220    for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
221#if DEBUG_BHT
222        printf ("Check symbol: %s\n", chain->key);
223#endif
224        if( equal_compare<uint32_t> ((unsigned char*)chain->key, (unsigned char*)name, chain->lgth, L) )
225        {
226#if DEBUG_BHT
227            printf ("Found GID: %i\n", chain->GID);
228#endif
229            return chain->GID;
230        }
231    }
232
233#if DEBUG_BHT
234    printf ("Not Found GID: %i\n", 0);
235#endif
236    return 0;
237}
238
239// Use this method if L is in [9,16]
240inline unsigned int BitStreamHashTable::Lookup_Name_16(char * name, const int hashvalue, int L)
241{
242    unsigned int hash = getIndex(hashvalue);
243
244    // Look up the value in the chain
245    for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
246#if DEBUG_BHT
247        printf ("Check symbol: %s\n", chain->key);
248#endif
249        if( equal_compare<uint64_t> ((unsigned char*)chain->key, (unsigned char*)name, chain->lgth, L) )
250        {
251#if DEBUG_BHT
252            printf ("Found GID: %i\n", chain->GID);
253#endif
254            return chain->GID;
255        }
256    }
257
258#if DEBUG_BHT
259    printf ("Not Found GID: %i\n", 0);
260#endif
261    return 0;
262}
263
264#endif // #if defined (USE_LOG_SORT)
265
266
267// Use this method if L is in [17,32]
268inline unsigned int BitStreamHashTable::Lookup_Name_32(char * name, const int hashvalue, int L)
269{
270    unsigned int hash = getIndex(hashvalue);
271
272    // Look up the value in the chain
273    for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
274#if DEBUG_BHT
275        printf ("Check symbol: %s\n", chain->key);
276#endif
277        if( equal_compare<SIMD_type> ((unsigned char*)chain->key, (unsigned char*)name, chain->lgth, L) )
278        {
279#if DEBUG_BHT
280            printf ("Found GID: %i\n", chain->GID);
281#endif
282            return chain->GID;
283        }
284    }
285
286#if DEBUG_BHT
287    printf ("Not Found GID: %i\n", 0);
288#endif
289    return 0;
290}
291
292// Use this method if L > 32
293inline unsigned int BitStreamHashTable::Lookup_Name(char * name, const int hashvalue, int L)
294{
295    unsigned int hash = getIndex(hashvalue);
296
297    // Look up the value in the chain
298    for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
299#if DEBUG_BHT
300        printf ("Check symbol: %s\n", chain->key);
301#endif
302        if( simd_compare ((unsigned char*)chain->key, (unsigned char*)name, L) )
303        {
304#if DEBUG_BHT
305            printf ("Found GID: %i\n", chain->GID);
306#endif
307            return chain->GID;
308        }
309    }
310
311#if DEBUG_BHT
312    printf ("Not Found GID: %i\n", 0);
313#endif
314    return 0;
315}
316
317inline void BitStreamHashTable::Insert_Name(char * name, const int hashvalue, const unsigned int gid)
318{
319    unsigned int hash = getIndex(hashvalue);
320
321    // If it was not found, add it
322    CHAIN* next = g_table[hash];
323    g_table[hash] = (CHAIN*) malloc(sizeof(CHAIN*));
324    g_table[hash]->next = next;
325    g_table[hash]->key = name;
326    g_table[hash]->GID = gid;
327
328#if DEBUG_BHT
329    printf ("Given GID: %i | Stored GID: %i\n", gid, g_table[hash]->GID);
330#endif
331}
332
333inline void BitStreamHashTable::Insert_Name(char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth)
334{
335    unsigned int hash = getIndex(hashvalue);
336
337    // If it was not found, add it
338    CHAIN* next = g_table[hash];
339    g_table[hash] = (CHAIN*) malloc(sizeof(CHAIN*));
340    g_table[hash]->next = next;
341    g_table[hash]->key = name;
342    g_table[hash]->GID = gid;
343    g_table[hash]->lgth = lgth;
344
345#if DEBUG_BHT
346    printf ("Given GID: %i | Stored GID: %i\n", gid, g_table[hash]->GID);
347#endif
348}
349
350inline unsigned int BitStreamHashTable::getIndex(const int hashvalue)
351{
352    return hashvalue & TABLE_SIZE_MASK;
353}
354
355inline unsigned int BitStreamHashTable::NextLog2(unsigned int x)
356{
357    // Henry Warren, "Hacker's Delight", ch. 5.3
358    if(x <= 1) return x;
359    x--;
360    unsigned int n = 0;
361    unsigned int y;
362    y = x >>16; if(y) {n += 16; x = y;}
363    y = x >> 8; if(y) {n +=  8; x = y;}
364    y = x >> 4; if(y) {n +=  4; x = y;}
365    y = x >> 2; if(y) {n +=  2; x = y;}
366    y = x >> 1; if(y) return n + 2;
367    return n + x;
368}
369
370void BitStreamHashTable::Print_Symbol_Table_Distribution()
371{
372    for(int hash = 0; hash < TABLE_SIZE; hash++)
373    {
374        int items = 0;
375        for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next)
376        {
377            items++;
378        }
379        if (items >= 1)
380        {
381            fprintf (stderr, "\tBucket: %i | #items: %i\n", hash, items);
382        }
383    }
384}
385
386void BitStreamHashTable::free_chain(CHAIN* chain)
387{
388    if (chain == NULL)
389    {
390        return;
391    }
392
393    if (chain->next != NULL)
394    {
395        free_chain(chain->next);
396    }
397    free(chain);
398    chain = NULL;
399}
400
401#endif // BITSTREAM_HASH_TABLE_H
Note: See TracBrowser for help on using the repository browser.