Ignore:
Timestamp:
Nov 2, 2011, 8:34:40 PM (8 years ago)
Author:
vla24
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/symtab/bitstream_id_hash_table.h

    r1518 r1653  
    1313#ifndef BITSTREAM_ID_HASH_TABLE_H
    1414#define BITSTREAM_ID_HASH_TABLE_H
    15 #define USE_IDENTITY_SORT
     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
    1620
    17 #include "bitstream_hash_table.h"
    18 #include "pbgs_utilities.h"
    19 
    20 class BitStreamIdentityHashTable : public BitStreamHashTable
     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
    2125{
    2226public:
     
    2428    //Returns 0 upon failure
    2529    // Symbol length [1,16]
    26     template <int L> inline unsigned int Lookup_Name(char * name, const int hashvalue);
     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();
    2750};
    2851
    2952template <int L>
    30         unsigned int BitStreamIdentityHashTable::Lookup_Name(char * name, const int hashvalue)
     53unsigned int BitStreamIdentityHashTable<L>::Lookup_Name(char * name, const int hashvalue)
    3154{
    32     unsigned int bucket = getBucket(hashvalue, g_tableSize);
     55    unsigned int bucket = getBucket(name, hashvalue, m_tableSize);
    3356
    3457    // Look up the value in the chain
    35     for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
     58    for(CHAIN* chain = m_table[bucket]; chain != NULL; chain = chain->next) {
    3659#if DEBUG_BHT
    3760        printf ("Check symbol: %s\n", chain->key);
     
    4063        {
    4164#if DEBUG_BHT
    42             printf ("Found GID: %i\n", chain->GID);
     65            printf ("%s%i Found GID: %i\n", __FUNCTION__, L, chain->GID);
    4366#endif
    4467            return chain->GID;
     
    4770
    4871#if DEBUG_BHT
    49     printf ("Not Found GID: %i\n", 0);
     72    printf ("%s%i Not Found GID: %i\n", __FUNCTION__, L, 0);
    5073#endif
    5174
    5275    return 0;
    5376}
     77
     78#include "bitstream_hash_table_impl.h"
    5479#endif // BITSTREAM_ID_HASH_TABLE_H
Note: See TracChangeset for help on using the changeset viewer.