source: trunk/lib/symtab/bitstream_log_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: 4.5 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, g_tableSize);
47
48    // Look up the value in the chain
49    for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
50#if DEBUG_BHT
51        printf ("Check symbol: %s\n", chain->key);
52#endif
53        if( log_equal_compare_1 ((unsigned char*)chain->key, (unsigned char*)name) )
54        {
55#if DEBUG_BHT
56            printf ("Found GID: %i\n", chain->GID);
57#endif
58            return chain->GID;
59        }
60    }
61
62#if DEBUG_BHT
63    printf ("Not Found GID: %i\n", 0);
64#endif
65    return 0;
66}
67
68inline unsigned int BitStreamLogHashTable::Lookup_Name_2(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 symbol: %s\n", chain->key);
76#endif
77        if( log_equal_compare_2 ((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#if DEBUG_BHT
87    printf ("Not Found GID: %i\n", 0);
88#endif
89    return 0;
90}
91
92// Use this method if L is in [3,4]
93inline unsigned int BitStreamLogHashTable::Lookup_Name_4(char * name, const int hashvalue, int L)
94{
95    unsigned int bucket = getBucket(hashvalue, g_tableSize);
96
97    // Look up the value in the chain
98    for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
99#if DEBUG_BHT
100        printf ("Check symbol: %s\n", chain->key);
101#endif
102
103#ifdef USE_MASK_COMPARE
104        if( log_equal_compare_4 ((unsigned char*)chain->key, (unsigned char*)name, L) )
105        {
106#else
107        if( overlap_compare<uint16_t>((unsigned char*)chain->key, (unsigned char*)name, chain->lgth, L) )
108        {
109#endif
110#if DEBUG_BHT
111            printf ("Found GID: %i\n", chain->GID);
112#endif
113            return chain->GID;
114        }
115    }
116
117#if DEBUG_BHT
118    printf ("Not Found GID: %i\n", 0);
119#endif
120    return 0;
121}
122
123// Use this method if L is in [5,8]
124inline unsigned int BitStreamLogHashTable::Lookup_Name_8(char * name, const int hashvalue, int L)
125{
126    unsigned int bucket = getBucket(hashvalue, g_tableSize);
127
128    // Look up the value in the chain
129    for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
130#if DEBUG_BHT
131        printf ("Check symbol: %s\n", chain->key);
132#endif
133        if( overlap_compare<uint32_t> ((unsigned char*)chain->key, (unsigned char*)name, chain->lgth, L) )
134        {
135#if DEBUG_BHT
136            printf ("Found GID: %i\n", chain->GID);
137#endif
138            return chain->GID;
139        }
140    }
141
142#if DEBUG_BHT
143    printf ("Not Found GID: %i\n", 0);
144#endif
145    return 0;
146}
147
148// Use this method if L is in [9,16]
149inline unsigned int BitStreamLogHashTable::Lookup_Name_16(char * name, const int hashvalue, int L)
150{
151    unsigned int bucket = getBucket(hashvalue, g_tableSize);
152
153    // Look up the value in the chain
154    for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
155#if DEBUG_BHT
156        printf ("Check symbol: %s\n", chain->key);
157#endif
158        if( overlap_compare<uint64_t> ((unsigned char*)chain->key, (unsigned char*)name, chain->lgth, L) )
159        {
160#if DEBUG_BHT
161            printf ("Found GID: %i\n", chain->GID);
162#endif
163            return chain->GID;
164        }
165    }
166
167#if DEBUG_BHT
168    printf ("Not Found GID: %i\n", 0);
169#endif
170    return 0;
171}
172
173#endif // BITSTREAM_LOG_HASH_TABLE_H
Note: See TracBrowser for help on using the repository browser.