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

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

SymbolTable?: hash table implementation for paralel bitstream based length sorting (PBGS) now auto-resizes. Fixed flipBit function used by Div2 grouping strategy

File size: 3.2 KB
Line 
1/*
2 * Created on: 25-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
8 * log grouping strategy.
9 *
10 * Division group sorting        f(L) = floor( (L-1)/2^k )
11 *
12 */
13
14#ifndef BITSTREAM_DIV_HASH_TABLE_H
15#define BITSTREAM_DIV_HASH_TABLE_H
16
17#define DEBUG_BHT 0
18
19#include <stdlib.h>
20#include "bitstream_hash_table.h"
21#include "pbgs_utilities.h"
22#include "ls_symbol_table_util.h"
23#include "limits.h"
24
25class BitStreamDivHashTable : public BitStreamHashTable
26{
27public:
28
29    //Returns 0 upon failure
30    // Symbol L in [1,16] and L should be an even number.
31    // Use this method to do _first_ symbol lookup: _before_ checking if the last
32    // character is a delimiter
33    template <int L> inline unsigned int Lookup_Name(char * name, const int hashvalue);
34
35    // Symbol L in [1,16] and L should be an _odd_ number.
36    // Use this method to do _second_ symbol lookup: _after_ checking if the last
37    // character is a delimiter
38    template <int L> inline unsigned int Lookup_Name_Delimiter(char * name, const int hashvalue);
39};
40
41template <int L>
42        inline unsigned int BitStreamDivHashTable::Lookup_Name(char * name, const int hashvalue)
43{
44    unsigned int bucket = getBucket(hashvalue, g_tableSize);
45
46    // Look up the value in the chain
47    for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
48#if DEBUG_BHT
49        printf ("Check symbol: %s\n", chain->key);
50#endif
51        if( div_equal_compare <L> ((unsigned char*)chain->key, (unsigned char*)name) )
52        {
53#if DEBUG_BHT
54            printf ("Found GID: %i\n", chain->GID);
55#endif
56            return chain->GID;
57        }
58    }
59
60#if DEBUG_BHT
61    printf ("Not Found GID: %i\n", 0);
62#endif
63    return 0;
64}
65
66// L is odd
67template <int L>
68        inline unsigned int BitStreamDivHashTable::Lookup_Name_Delimiter(char * name, const int hashvalue)
69{
70    unsigned int bucket = getBucket(hashvalue, g_tableSize);
71
72    // Look up the value in the chain
73    for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
74#if DEBUG_BHT
75        printf ("Check key: %s\n", chain->key);
76#endif
77        if( div_equal_compare <L> ((unsigned char*)chain->key, (unsigned char*)name) )
78        {
79#if DEBUG_BHT
80            printf ("Found GID: %i\n", chain->GID);
81#endif
82            return chain->GID;
83        }
84    }
85
86    // Flip the last bit of the hash value
87    unsigned int newBucket = getBucket(flipBit<L+1>(hashvalue), g_tableSize);
88
89#if DEBUG_BHT
90    print_general_register_32 ("hash", hashvalue);
91    print_general_register_32 ("flipped hash", flipBit<L+1>(hashvalue));
92    printf ("\n");
93#endif
94    // FIXME: Should we check?
95    if (bucket == newBucket)
96    {
97        return 0;
98    }
99
100    // Look up the value in the chain
101    for(CHAIN* chain = g_table[newBucket]; chain != NULL; chain = chain->next) {
102#if DEBUG_BHT
103        printf ("Check key: %s\n", chain->key);
104#endif
105        if( div_equal_compare <L> ((unsigned char*)chain->key, (unsigned char*)name) )
106        {
107#if DEBUG_BHT
108            printf ("Found GID: %i\n", chain->GID);
109#endif
110            return chain->GID;
111        }
112    }
113
114#if DEBUG_BHT
115    printf ("Not Found GID: %i\n", 0);
116#endif
117    return 0;
118}
119
120#endif // BITSTREAM_DIV_HASH_TABLE_H
Note: See TracBrowser for help on using the repository browser.