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

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

SymbolTable?: Changed hash table memory allocation. Previously we pre-allocated the memory, now we allocate the memory as we need.

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