Changeset 1742 for trunk/symtab


Ignore:
Timestamp:
Nov 28, 2011, 8:27:21 PM (7 years ago)
Author:
vla24
Message:

SymbolTable?: Fixed custom hashing function for parallel bitstream based grouping

Location:
trunk/symtab
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • trunk/symtab/bitstream_hash_table_impl.h

    r1653 r1742  
    1717//#ifndef BITSTREAM_HASH_TABLE_IMPL_H
    1818//#define BITSTREAM_HASH_TABLE_IMPL_H
     19
     20//#define XOR_HASHVALUE //Define this macro to xor bitstream hashvalue with the computed hashvalue for custom hash function
    1921
    2022#include <stdlib.h>
     
    239241    printf ("%s_%i | hashvalue: %i | ", __FUNCTION__, 1, hashvalue);
    240242#endif
     243#ifdef XOR_HASHVALUE
     244    return ( longHashFunction<uint8_t>((uint8_t*)name, (uint8_t*)name, BYTES_TO_BITS(1), BIT_SIZE(tableSize)) ^ ~hashvalue ) & TABLE_SIZE_MASK(tableSize);
     245#else
    241246    return longHashFunction<uint8_t>((uint8_t*)name, (uint8_t*)name, BYTES_TO_BITS(1), BIT_SIZE(tableSize)) & TABLE_SIZE_MASK(tableSize);
     247#endif
    242248}
    243249
     
    248254    printf ("%s_%i | hashvalue: %i | ", __FUNCTION__, 2, hashvalue);
    249255#endif
     256#ifdef XOR_HASHVALUE
     257    return ( longHashFunction<uint16_t>((uint16_t*)name, (uint16_t*)name, BYTES_TO_BITS(2), BIT_SIZE(tableSize)) ^ ~hashvalue ) & TABLE_SIZE_MASK(tableSize);
     258#else
    250259    return longHashFunction<uint16_t>((uint16_t*)name, (uint16_t*)name, BYTES_TO_BITS(2), BIT_SIZE(tableSize)) & TABLE_SIZE_MASK(tableSize);
     260#endif
    251261}
    252262
     
    257267    printf ("%s_%i | hashvalue: %i | ", __FUNCTION__, 3, hashvalue);
    258268#endif
     269#ifdef XOR_HASHVALUE
     270    return ( longHashFunction<uint32_t>((uint32_t*)name, (uint32_t*)name, BYTES_TO_BITS(3), BIT_SIZE(tableSize)) ^ ~hashvalue ) & TABLE_SIZE_MASK(tableSize);
     271#else
    259272    return longHashFunction<uint32_t>((uint32_t*)name, (uint32_t*)name, BYTES_TO_BITS(3), BIT_SIZE(tableSize)) & TABLE_SIZE_MASK(tableSize);
     273#endif
    260274}
    261275
     
    266280    printf ("%s_%i | hashvalue: %i | ", __FUNCTION__, 4, hashvalue);
    267281#endif
    268     return longHashFunction<uint16_t>((uint16_t*)name, (uint16_t*)(name+2), BYTES_TO_BITS(2), BIT_SIZE(tableSize)) & TABLE_SIZE_MASK(tableSize);
     282#ifdef XOR_HASHVALUE
     283    return ( longHashFunction<uint32_t>((uint32_t*)name, (uint32_t*)name, BYTES_TO_BITS(4), BIT_SIZE(tableSize)) ^ ~hashvalue ) & TABLE_SIZE_MASK(tableSize);
     284#else
     285    return longHashFunction<uint32_t>((uint32_t*)name, (uint32_t*)name, BYTES_TO_BITS(4), BIT_SIZE(tableSize)) & TABLE_SIZE_MASK(tableSize);
     286#endif
    269287}
    270288
     
    275293    printf ("%s_%i | hashvalue: %i | ", __FUNCTION__, 5, hashvalue);
    276294#endif
     295#ifdef XOR_HASHVALUE
     296    return ( longHashFunction<uint32_t>((uint32_t*)name, (uint32_t*)(name+2), BYTES_TO_BITS(3), BIT_SIZE(tableSize)) ^ ~hashvalue ) & TABLE_SIZE_MASK(tableSize);
     297#else
    277298    return longHashFunction<uint32_t>((uint32_t*)name, (uint32_t*)(name+2), BYTES_TO_BITS(3), BIT_SIZE(tableSize)) & TABLE_SIZE_MASK(tableSize);
     299#endif
    278300}
    279301
     
    284306    printf ("%s_%i | hashvalue: %i | ", __FUNCTION__, 6, hashvalue);
    285307#endif
     308#ifdef XOR_HASHVALUE
     309    return ( longHashFunction<uint32_t>((uint32_t*)name, (uint32_t*)(name+3), BYTES_TO_BITS(3), BIT_SIZE(tableSize)) ^ ~hashvalue ) & TABLE_SIZE_MASK(tableSize);
     310#else
    286311    return longHashFunction<uint32_t>((uint32_t*)name, (uint32_t*)(name+3), BYTES_TO_BITS(3), BIT_SIZE(tableSize)) & TABLE_SIZE_MASK(tableSize);
     312#endif
    287313}
    288314
     
    293319    printf ("%s_%i | hashvalue: %i | ", __FUNCTION__, 7, hashvalue);
    294320#endif
     321#ifdef XOR_HASHVALUE
     322    return ( longHashFunction<uint32_t>((uint32_t*)name, (uint32_t*)(name+3), BYTES_TO_BITS(4), BIT_SIZE(tableSize)) ^ ~hashvalue ) & TABLE_SIZE_MASK(tableSize);
     323#else
    295324    return longHashFunction<uint32_t>((uint32_t*)name, (uint32_t*)(name+3), BYTES_TO_BITS(4), BIT_SIZE(tableSize)) & TABLE_SIZE_MASK(tableSize);
     325#endif
    296326}
    297327
     
    302332    printf ("%s_%i | hashvalue: %i | ", __FUNCTION__, 8, hashvalue);
    303333#endif
     334#ifdef XOR_HASHVALUE
     335    return ( longHashFunction<uint32_t>((uint32_t*)name, (uint32_t*)(name+4), BYTES_TO_BITS(4), BIT_SIZE(tableSize)) ^ ~hashvalue ) & TABLE_SIZE_MASK(tableSize);
     336#else
    304337    return longHashFunction<uint32_t>((uint32_t*)name, (uint32_t*)(name+4), BYTES_TO_BITS(4), BIT_SIZE(tableSize)) & TABLE_SIZE_MASK(tableSize);
     338#endif
     339}
     340
     341template <>
     342    inline unsigned int BitStreamHashTableImpl<9>::getBucket(const char* name, const int hashvalue, unsigned int tableSize)
     343{
     344#if DEBUG_BHT
     345    printf ("%s_%i | hashvalue: %i | ", __FUNCTION__, 9, hashvalue);
     346#endif
     347#ifdef XOR_HASHVALUE
     348    return ( longHashFunction<uint64_t>((uint64_t*)name, (uint64_t*)(name+4), BYTES_TO_BITS(5), BIT_SIZE(tableSize)) ^ ~hashvalue ) & TABLE_SIZE_MASK(tableSize);
     349#else
     350    return longHashFunction<uint64_t>((uint64_t*)name, (uint64_t*)(name+4), BYTES_TO_BITS(5), BIT_SIZE(tableSize)) & TABLE_SIZE_MASK(tableSize);
     351#endif
     352}
     353
     354template <>
     355    inline unsigned int BitStreamHashTableImpl<10>::getBucket(const char* name, const int hashvalue, unsigned int tableSize)
     356{
     357#if DEBUG_BHT
     358    printf ("%s_%i | hashvalue: %i | ", __FUNCTION__, 10, hashvalue);
     359#endif
     360#ifdef XOR_HASHVALUE
     361    return ( longHashFunction<uint64_t>((uint64_t*)name, (uint64_t*)(name+5), BYTES_TO_BITS(5), BIT_SIZE(tableSize)) ^ ~hashvalue ) & TABLE_SIZE_MASK(tableSize);
     362#else
     363    return longHashFunction<uint64_t>((uint64_t*)name, (uint64_t*)(name+5), BYTES_TO_BITS(5), BIT_SIZE(tableSize)) & TABLE_SIZE_MASK(tableSize);
     364#endif
     365}
     366
     367template <>
     368    inline unsigned int BitStreamHashTableImpl<11>::getBucket(const char* name, const int hashvalue, unsigned int tableSize)
     369{
     370#if DEBUG_BHT
     371    printf ("%s_%i | hashvalue: %i | ", __FUNCTION__, 11, hashvalue);
     372#endif
     373#ifdef XOR_HASHVALUE
     374    return ( longHashFunction<uint64_t>((uint64_t*)name, (uint64_t*)(name+5), BYTES_TO_BITS(6), BIT_SIZE(tableSize)) ^ ~hashvalue ) & TABLE_SIZE_MASK(tableSize);
     375#else
     376    return longHashFunction<uint64_t>((uint64_t*)name, (uint64_t*)(name+5), BYTES_TO_BITS(6), BIT_SIZE(tableSize)) & TABLE_SIZE_MASK(tableSize);
     377#endif
     378}
     379
     380template <>
     381    inline unsigned int BitStreamHashTableImpl<12>::getBucket(const char* name, const int hashvalue, unsigned int tableSize)
     382{
     383#if DEBUG_BHT
     384    printf ("%s_%i | hashvalue: %i | ", __FUNCTION__, 12, hashvalue);
     385#endif
     386#ifdef XOR_HASHVALUE
     387    return ( longHashFunction<uint64_t>((uint64_t*)name, (uint64_t*)(name+6), BYTES_TO_BITS(6), BIT_SIZE(tableSize)) ^ ~hashvalue ) & TABLE_SIZE_MASK(tableSize);
     388#else
     389    return longHashFunction<uint64_t>((uint64_t*)name, (uint64_t*)(name+6), BYTES_TO_BITS(6), BIT_SIZE(tableSize)) & TABLE_SIZE_MASK(tableSize);
     390#endif
    305391}
    306392//#endif // BITSTREAM_HASH_TABLE_IMPL_H
  • trunk/symtab/bitstream_super_hash_table.h

    r1653 r1742  
    1111#define BIT_SIZE(x)             cfzl(x)
    1212#define BYTES_TO_BITS(x)        x << 3
    13 #define MAX_CHAIN               2
     13#define MAX_CHAIN               4
    1414
    1515#include <string.h>
     
    115115    {
    116116        int items = chainLength(m_table[bucket]);
    117         if (items >= 1)
     117        if (items >= 1)
    118118        {
    119             fprintf (stderr, "\tBucket: %i | #items: %i\n", bucket, items);
    120         }
     119            printf ("\tBucket: %i | #items: %i\n", bucket, items);
     120        }
     121        if (items > MAX_CHAIN)
     122        {
     123            printf ("\t\tSymbols: ");
     124            CHAIN* curr = m_table[bucket];
     125            while (curr != NULL)
     126            {
     127                printf ("%s ", curr->key);
     128                curr = curr->next;
     129            }
     130            printf ("\n");
     131        }
    121132    }
    122133}
  • trunk/symtab/ls_symbol_table.cxx

    r1649 r1742  
    530530}
    531531
     532vector<int> LSSymbolTable::get_flattened_gids()
     533{
     534    vector<int> gids;
     535    for (size_t i = 0; i < this->doc_idx_gids_->size(); i++) {
     536        int gid = this->doc_idx_gids_->get(i);
     537        gids.push_back(gid);
     538    }
     539    return gids;
     540}
     541
    532542#ifdef USE_FUNCTION_OBJECTS
    533543
  • trunk/symtab/ls_symbol_table.h

    r1229 r1742  
    4646#endif
    4747
     48
    4849#include "arrays/HeapArray.h"
    4950#include "arrays/HeapArray2D.h"
     
    5354#ifndef LSYMTAB_H_
    5455#define LSYMTAB_H_
     56
     57#include <vector>
     58using namespace std;
    5559
    5660class LSSymbolTable {
     
    9397        void display_flattened_symbol_values() const;
    9498       
    95         void display_flattened_gids() const;   
     99        void display_flattened_gids() const;
     100
     101        // Used for dictionary
     102        vector<int> get_flattened_gids();
    96103               
    97104private:
  • trunk/symtab/pbgs_div_symbol_table.h

    r1665 r1742  
    197197    for (int i = 1; i < TOTAL_GROUPS; i ++)
    198198    {
    199         fprintf (stderr, "Group #%i\n", i );
     199        printf ("Group #%i\n", i );
    200200        m_hashTable[i]->Print_Symbol_Table_Distribution();
    201201    }
  • trunk/symtab/pbgs_hash_functions.h

    r1653 r1742  
    22#define HASH_FUNCTIONS_H
    33
    4 //#define DEBUG_HASH_FUNCTION
    54#ifdef DEBUG_HASH_FUNCTION
    65#include <stdio.h>
  • trunk/symtab/pbgs_identity_symbol_table.h

    r1653 r1742  
    174174    for (int i = 1; i < TOTAL_GROUPS; i ++)
    175175    {
    176         fprintf (stderr, "Group #%i\n", i );
     176        printf ("Group #%i\n", i );
    177177        m_hashTable[i]->Print_Symbol_Table_Distribution();
    178178    }
Note: See TracChangeset for help on using the changeset viewer.