source: trunk/symtab/bitstream_div_hash_table.h @ 2694

Last change on this file since 2694 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: 3.5 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 "pbgs_utilities.h"
21#include "bitstream_super_hash_table.h"
22#include "pbgs_hash_functions.h"
23#include "bitstream_id_hash_table.h"
24#undef BitStreamHashTableImpl
25#define BitStreamHashTableImpl BitStreamDivHashTable
26
27// Use L = 17 to indicate a group for symbols with length > 16
28// if L in [1,16], L should be an even number.
29template <int L>
30class BitStreamDivHashTable : public BitStreamSuperHashTable
31{
32public:
33
34    BitStreamDivHashTable() {};
35    ~BitStreamDivHashTable() {};
36
37    // Returns 0 upon failure
38    // Symbol L in [1,16]
39    // Use this method to do _first_ symbol lookup: _before_ checking if the last
40    // character is a delimiter
41    inline unsigned int Lookup_Name(char * name, const int hashvalue);
42
43    // Symbol L in [1,16]
44    // Use this method to do _second_ symbol lookup: _after_ checking if the last
45    // character is a delimiter
46    inline unsigned int Lookup_Name_Odd(char * name, const int hashvalue);
47
48    // Symbol length > 16
49    unsigned int Lookup_Name_17(char * name, const int hashvalue, int length);
50
51    // Use this method for identity and div2 grouping, L <= 16
52    void Insert_Name(const char * name, const int hashvalue, const unsigned int gid);
53
54    // Use this method for arbitrary length.
55    void Insert_Name(const char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth);
56
57    // Use this method for identity and div2 grouping, L <= 16
58    inline void Insert_Name_Odd_Symbol(const char * name, const int hashvalue, const unsigned int gid);
59
60protected:
61    // Use this for L in [1,16]
62    inline unsigned int getBucket(const char* name, const int hashvalue, unsigned int tableSize);
63
64    // Use this for L > 16
65    inline unsigned int getBucket(const int hashvalue, unsigned int tableSize, unsigned int length);
66
67private:
68    void expandHashTable();
69    BitStreamIdentityHashTable<L-1> m_oddSymbolTable;
70};
71
72// L in [1,16]
73template <int L>
74        inline unsigned int BitStreamDivHashTable<L>::Lookup_Name(char * name, const int hashvalue)
75{
76    unsigned int bucket = getBucket(name, hashvalue, m_tableSize);
77
78    // Look up the value in the chain
79    for(CHAIN* chain = m_table[bucket]; chain != NULL; chain = chain->next) {
80#if DEBUG_BHT
81        printf ("Check symbol: %s\n", chain->key);
82#endif
83        if( div_equal_compare <L> ((unsigned char*)chain->key, (unsigned char*)name) )
84        {
85#if DEBUG_BHT
86            printf ("Found GID: %i\n", chain->GID);
87#endif
88            return chain->GID;
89        }
90    }
91
92#if DEBUG_BHT
93    printf ("Not Found GID: %i\n", 0);
94#endif
95    return 0;
96}
97
98// L in [1,16]
99template <int L>
100        inline unsigned int BitStreamDivHashTable<L>::Lookup_Name_Odd(char * name, const int hashvalue)
101{
102    return m_oddSymbolTable.Lookup_Name(name, hashvalue);
103}
104
105//Use this method for L in [1,16], name has odd length
106template <int L>
107        void BitStreamDivHashTable<L>::Insert_Name_Odd_Symbol(const char * name, const int hashvalue, const unsigned int gid)
108{
109    m_oddSymbolTable.Insert_Name(name, hashvalue, gid);
110}
111
112#include "bitstream_hash_table_impl.h"
113
114#endif // BITSTREAM_DIV_HASH_TABLE_H
Note: See TracBrowser for help on using the repository browser.