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

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

Reorganized SymbolTable? library

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