source: trunk/symtab/bitstream_id_hash_table.h @ 3028

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

SymbolTable?: implemented auto-resize and custom hashing for different symbol length for division and identity length grouping

File size: 2.3 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
8 * identity grouping strategy.
9 *
10 * Identity group sorting        f(L) = L
11 */
12
13#ifndef BITSTREAM_ID_HASH_TABLE_H
14#define BITSTREAM_ID_HASH_TABLE_H
15#include "pbgs_utilities.h"
16#include "pbgs_hash_functions.h"
17#include "bitstream_super_hash_table.h"
18#undef BitStreamHashTableImpl
19#define BitStreamHashTableImpl BitStreamIdentityHashTable
20
21#define DEBUG_BHT 0
22// Use L = 17 to indicate a group for symbols with length > 16
23template <int L>
24class BitStreamIdentityHashTable : public BitStreamSuperHashTable
25{
26public:
27
28    //Returns 0 upon failure
29    // Symbol length [1,16]
30    inline unsigned int Lookup_Name(char * name, const int hashvalue);
31
32    // Symbol length > 16
33    unsigned int Lookup_Name_17(char * name, const int hashvalue, int length);
34
35    // Use this method for identity and div2 grouping, L <= 16
36    void Insert_Name(const char * name, const int hashvalue, const unsigned int gid);
37
38    // Use this method for arbitrary length.
39    void Insert_Name(const char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth);
40
41protected:
42    // Use this for L in [1,16]
43    inline unsigned int getBucket(const char* name, const int hashvalue, unsigned int tableSize);
44
45    // Use this for L > 16
46    inline unsigned int getBucket(const int hashvalue, unsigned int tableSize, unsigned int length);
47
48private:
49    void expandHashTable();
50};
51
52template <int L>
53unsigned int BitStreamIdentityHashTable<L>::Lookup_Name(char * name, const int hashvalue)
54{
55    unsigned int bucket = getBucket(name, hashvalue, m_tableSize);
56
57    // Look up the value in the chain
58    for(CHAIN* chain = m_table[bucket]; chain != NULL; chain = chain->next) {
59#if DEBUG_BHT
60        printf ("Check symbol: %s\n", chain->key);
61#endif
62        if( id_equal_compare <L> ((unsigned char*)chain->key, (unsigned char*)name) )
63        {
64#if DEBUG_BHT
65            printf ("%s%i Found GID: %i\n", __FUNCTION__, L, chain->GID);
66#endif
67            return chain->GID;
68        }
69    }
70
71#if DEBUG_BHT
72    printf ("%s%i Not Found GID: %i\n", __FUNCTION__, L,  0);
73#endif
74
75    return 0;
76}
77
78#include "bitstream_hash_table_impl.h"
79#endif // BITSTREAM_ID_HASH_TABLE_H
Note: See TracBrowser for help on using the repository browser.