source: trunk/symtab/bitstream_log_hash_table.h @ 3937

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

SymbolTable?: Update symtab library for dictionary div2 delimiter. Fixed some compile errors for log grouping

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