source: trunk/symtab/bitstream_log_hash_table.h @ 1653

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

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

File size: 4.8 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 * log grouping strategy.
9 *
10 * Log group sorting             f(L) = ceil (log(L))
11 *
12 */
13
14#ifndef BITSTREAM_LOG_HASH_TABLE_H
15#define BITSTREAM_LOG_HASH_TABLE_H
16#define USE_LOG_SORT
17
18//#define USE_MASK_COMPARE    //Comparison using masking technique.
19                            //This technique only applies to USE_LOG_SORT
20
21#include "bitstream_hash_table.h"
22#include "pbgs_utilities.h"
23
24class BitStreamLogHashTable : public BitStreamHashTable
25{
26public:
27    //Returns 0 upon failure
28    // Symbol length 1
29    inline unsigned int Lookup_Name_1(char * name, const int hashvalue);
30
31    // Symbol length 2
32    inline unsigned int Lookup_Name_2(char * name, const int hashvalue);
33
34    // Symbol length [3,4]
35    inline unsigned int Lookup_Name_4(char * name, const int hashvalue, int L);
36
37    // Symbol length [5,8]
38    inline unsigned int Lookup_Name_8(char * name, const int hashvalue, int L);
39
40    // Symbol length [9,16]
41    inline unsigned int Lookup_Name_16(char * name, const int hashvalue, int L);
42};
43
44inline unsigned int BitStreamLogHashTable::Lookup_Name_1(char * name, const int hashvalue)
45{
46    unsigned int bucket = getBucket(hashvalue, m_tableSize);
47    unsigned int chainlgth = m_table->size(bucket);
48
49    // Look up the value in the chain
50    for(unsigned int i = 0; i < chainlgth; i++) {
51        CHAIN chain = m_table->get(bucket, i);
52#if DEBUG_BHT
53        printf ("Check symbol: %s\n", chain.key);
54#endif
55        if( log_equal_compare_1 ((unsigned char*)chain.key, (unsigned char*)name) )
56        {
57#if DEBUG_BHT
58            printf ("Found GID: %i\n", chain.GID);
59#endif
60            return chain.GID;
61        }
62    }
63
64#if DEBUG_BHT
65    printf ("Not Found GID: %i\n", 0);
66#endif
67    return 0;
68}
69
70inline unsigned int BitStreamLogHashTable::Lookup_Name_2(char * name, const int hashvalue)
71{
72    unsigned int bucket = getBucket(hashvalue, m_tableSize);
73    unsigned int chainlgth = m_table->size(bucket);
74
75    // Look up the value in the chain
76    for(unsigned int i = 0; i < chainlgth; i++) {
77        CHAIN chain = m_table->get(bucket, i);
78#if DEBUG_BHT
79        printf ("Check symbol: %s\n", chain.key);
80#endif
81        if( log_equal_compare_2 ((unsigned char*)chain.key, (unsigned char*)name) )
82        {
83#if DEBUG_BHT
84            printf ("Found GID: %i\n", chain.GID);
85#endif
86            return chain.GID;
87        }
88    }
89
90#if DEBUG_BHT
91    printf ("Not Found GID: %i\n", 0);
92#endif
93    return 0;
94}
95
96// Use this method if L is in [3,4]
97inline unsigned int BitStreamLogHashTable::Lookup_Name_4(char * name, const int hashvalue, int L)
98{
99    unsigned int bucket = getBucket(hashvalue, m_tableSize);
100    unsigned int chainlgth = m_table->size(bucket);
101
102    // Look up the value in the chain
103    for(unsigned int i = 0; i < chainlgth; i++) {
104        CHAIN chain = m_table->get(bucket, i);
105#if DEBUG_BHT
106        printf ("Check symbol: %s\n", chain.key);
107#endif
108
109#ifdef USE_MASK_COMPARE
110        if( log_equal_compare_4 ((unsigned char*)chain.key, (unsigned char*)name, L) )
111        {
112#else
113        if( overlap_compare<uint16_t>((unsigned char*)chain.key, (unsigned char*)name, chain.lgth, L) )
114        {
115#endif
116#if DEBUG_BHT
117            printf ("Found GID: %i\n", chain.GID);
118#endif
119            return chain.GID;
120        }
121    }
122
123#if DEBUG_BHT
124    printf ("Not Found GID: %i\n", 0);
125#endif
126    return 0;
127}
128
129// Use this method if L is in [5,8]
130inline unsigned int BitStreamLogHashTable::Lookup_Name_8(char * name, const int hashvalue, int L)
131{
132    unsigned int bucket = getBucket(hashvalue, m_tableSize);
133    unsigned int chainlgth = m_table->size(bucket);
134
135    // Look up the value in the chain
136    for(unsigned int i = 0; i < chainlgth; i++) {
137        CHAIN chain = m_table->get(bucket, i);
138#if DEBUG_BHT
139        printf ("Check symbol: %s\n", chain.key);
140#endif
141        if( overlap_compare<uint32_t> ((unsigned char*)chain.key, (unsigned char*)name, chain.lgth, L) )
142        {
143#if DEBUG_BHT
144            printf ("Found GID: %i\n", chain.GID);
145#endif
146            return chain.GID;
147        }
148    }
149
150#if DEBUG_BHT
151    printf ("Not Found GID: %i\n", 0);
152#endif
153    return 0;
154}
155
156// Use this method if L is in [9,16]
157inline unsigned int BitStreamLogHashTable::Lookup_Name_16(char * name, const int hashvalue, int L)
158{
159    unsigned int bucket = getBucket(hashvalue, m_tableSize);
160    unsigned int chainlgth = m_table->size(bucket);
161
162    // Look up the value in the chain
163    for(unsigned int i = 0; i < chainlgth; i++) {
164        CHAIN chain = m_table->get(bucket, i);
165#if DEBUG_BHT
166        printf ("Check symbol: %s\n", chain.key);
167#endif
168        if( overlap_compare<uint64_t> ((unsigned char*)chain.key, (unsigned char*)name, chain.lgth, L) )
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#endif // BITSTREAM_LOG_HASH_TABLE_H
Note: See TracBrowser for help on using the repository browser.