Changeset 2092


Ignore:
Timestamp:
May 9, 2012, 4:10:39 PM (7 years ago)
Author:
ksherdy
Message:

Refactored id,div2,log2. All tests pass.

Location:
trunk/symbol_table
Files:
1 added
11 edited

Legend:

Unmodified
Added
Removed
  • trunk/symbol_table/Makefile

    r2081 r2092  
    4343        python $(PABLO_COMPILER) $(MARKER_PABLO_SRC) -t $(MAIN_OUTFILE) -l $(MARKER_PREFIX) -o $(MAIN_OUTFILE) $(PABLO_ADD_DEBUG)
    4444
    45 logbase2: markers hash log2_group src/main.cpp
     45logbase2: markers hash logbase2_group src/main.cpp
    4646        python $(PABLO_COMPILER) $(MARKER_PABLO_SRC) -t $(MAIN_OUTFILE) -l $(MARKER_PREFIX) -o $(MAIN_OUTFILE) $(PABLO_ADD_DEBUG)
    4747
     
    6060        python $(PABLO_COMPILER) $(DIV2_GROUP_STRMS) -t $(MAIN_TEMPLATE) -l $(GROUP_PREFIX) -o $(MAIN_OUTFILE) $(PABLO_ADD_DEBUG)
    6161
    62 log2_group: log2_group_strms.py group_strms_template.hpp main_template.cpp
     62logbase2_group: log2_group_strms.py group_strms_template.hpp main_template.cpp
    6363        python $(PABLO_COMPILER) $(LOG2_GROUP_STRMS) -t $(GROUP_TEMPLATE) -l $(GROUP_PREFIX) -o $(GROUP_OUTFILE) $(PABLO_ADD_DEBUG)
    6464        python $(PABLO_COMPILER) $(LOG2_GROUP_STRMS) -t $(MAIN_TEMPLATE) -l $(GROUP_PREFIX) -o $(MAIN_OUTFILE) $(PABLO_ADD_DEBUG)
  • trunk/symbol_table/main_template.cpp

    r2062 r2092  
    134134    ///////////////////////////////////////////////////////////////////////////
    135135    while (chars_avail >= SEGMENT_SIZE) {
    136                                 uint32_t blk;
    137                                 for(blk=0;blk<SEGMENT_BLOCKS;blk++) {
    138                                 s2p_do_block((BytePack *) &raw_buffer[blk*BLOCK_SIZE], basis_bits[blk]);    // transpose
    139                                 markers_do_block(basis_bits[blk], markers[blk]);                            // gen symbol spans, mark starts & follows
    140                                 hash_strms_do_block(basis_bits[blk], hash[blk]);                            // gen hash bit streams
    141                                 identity_group_do_block(markers[blk], groups[blk]);                         // sort marker bit stream (identity)
    142       }
    143 
    144       for(int blk=0;blk<SEGMENT_BLOCKS;blk++) { // write contiguous bit streams
    145                                 h0[blk] = hash[blk].h0;
    146                                 h1[blk] = hash[blk].h1;
    147                                 starts[blk] = groups[blk].starts;
    148                                 ends_gte_17[blk] = groups[blk].ends_gte_17;
    149       }
    150 
    151       PERF_SEC_START(parser_timer);
    152       st.resolve(raw_buffer, groups, starts, ends_gte_17, h0, h1, SEGMENT_BLOCKS, gids);
    153       PERF_SEC_END(parser_timer, SEGMENT_SIZE);
    154 
    155       // copy loopback bytes
    156       memmove(lookback,&raw_buffer[SEGMENT_SIZE-LOOKBACK_SIZE],LOOKBACK_SIZE);
    157       // copy loopback bits
    158       memmove(lookback_h0,&((uint8_t *)h0)[(SEGMENT_SIZE-LOOKBACK_SIZE)/8],LOOKBACK_SIZE/8);
    159       memmove(lookback_h1,&((uint8_t *)h1)[(SEGMENT_SIZE-LOOKBACK_SIZE)/8],LOOKBACK_SIZE/8);
    160 
    161       memmove(lookback_starts,&((uint8_t *)starts)[(SEGMENT_SIZE-LOOKBACK_SIZE)/8],LOOKBACK_SIZE/8);
    162       memmove(lookback_ends_gte_17,&((uint8_t *)ends_gte_17)[(SEGMENT_SIZE-LOOKBACK_SIZE)/8],LOOKBACK_SIZE/8);
    163 
    164       //lookback_h0[0] = h0[SEGMENT_BLOCKS-1];
    165       //lookback_h1[0] = h1[SEGMENT_BLOCKS-1];
    166       is.read ((char *)(raw_buffer), SEGMENT_SIZE);
    167       chars_avail = is.gcount();
    168 
    169       // test
    170       uint32_t blk_offset;
    171       for(int blk=0;blk<SEGMENT_BLOCKS;blk++) {
    172                                 blk_offset = blk * BLOCKSIZE;
    173                                 gid_type gid;
    174                                 ForwardScanner<BitBlock, scanword_t> fscanner(&(groups[blk].starts));
    175 
    176                                 fscanner.scan_to_next();
    177                                 while(!fscanner.is_done()) {
    178                                         gid = gids.at[fscanner.get_pos() + blk_offset];
    179                                         cout << string((char *)st.get_raw_data(gid), st.get_lgth(gid)) << ",";
    180                                         fscanner.scan_to_next();
    181                                 }
    182       }
    183     }
     136        uint32_t blk;
     137        for(blk=0;blk<SEGMENT_BLOCKS;blk++) {
     138        s2p_do_block((BytePack *) &raw_buffer[blk*BLOCK_SIZE], basis_bits[blk]);    // transpose
     139        markers_do_block(basis_bits[blk], markers[blk]);                            // gen symbol spans, mark starts & follows
     140        hash_strms_do_block(basis_bits[blk], hash[blk]);                            // gen hash bit streams
     141        identity_group_do_block(markers[blk], groups[blk]);                         // sort marker bit stream (identity)
     142    }
     143
     144    for(int blk=0;blk<SEGMENT_BLOCKS;blk++) {   // write contiguous bit streams
     145        h0[blk] = hash[blk].h0;
     146        h1[blk] = hash[blk].h1;
     147        starts[blk] = groups[blk].starts;
     148        ends_gte_17[blk] = groups[blk].ends_gte_17;
     149    }
     150
     151    PERF_SEC_START(parser_timer);
     152    st.resolve(raw_buffer, groups, starts, ends_gte_17, h0, h1, SEGMENT_BLOCKS, gids);
     153    PERF_SEC_END(parser_timer, SEGMENT_SIZE);
     154
     155    // copy loopback bytes
     156    memmove(lookback,&raw_buffer[SEGMENT_SIZE-LOOKBACK_SIZE],LOOKBACK_SIZE);
     157    // copy loopback bits
     158    memmove(lookback_h0,&((uint8_t *)h0)[(SEGMENT_SIZE-LOOKBACK_SIZE)/8],LOOKBACK_SIZE/8);
     159    memmove(lookback_h1,&((uint8_t *)h1)[(SEGMENT_SIZE-LOOKBACK_SIZE)/8],LOOKBACK_SIZE/8);
     160
     161    memmove(lookback_starts,&((uint8_t *)starts)[(SEGMENT_SIZE-LOOKBACK_SIZE)/8],LOOKBACK_SIZE/8);
     162    memmove(lookback_ends_gte_17,&((uint8_t *)ends_gte_17)[(SEGMENT_SIZE-LOOKBACK_SIZE)/8],LOOKBACK_SIZE/8);
     163
     164    //lookback_h0[0] = h0[SEGMENT_BLOCKS-1];
     165    //lookback_h1[0] = h1[SEGMENT_BLOCKS-1];
     166    is.read ((char *)(raw_buffer), SEGMENT_SIZE);
     167    chars_avail = is.gcount();
     168
     169    // test
     170    #ifdef IDENTITY_TEST
     171    uint32_t blk_offset;
     172    for(int blk=0;blk<SEGMENT_BLOCKS;blk++) {
     173        blk_offset = blk * BLOCKSIZE;
     174        gid_type gid;
     175        ForwardScanner<BitBlock, scanword_t> fscanner(&(groups[blk].starts));
     176
     177        fscanner.scan_to_next();
     178        while(!fscanner.is_done()) {
     179            gid = gids.at[fscanner.get_pos() + blk_offset];
     180            cout << string((char *)st.get_raw_data(gid), st.get_lgth(gid)) << ",";
     181            fscanner.scan_to_next();
     182        }
     183    }
     184    #endif
     185    }
     186
    184187    /* Resolve Partial Segments */
    185188    uint32_t remaining = chars_avail;
     
    190193    uint32_t blk = 0;
    191194    while (remaining >= BLOCK_SIZE) {
    192                         s2p_do_block((BytePack *) &raw_buffer[blk*BLOCK_SIZE], basis_bits[blk]);
    193                         markers_do_block(basis_bits[blk], markers[blk]);
    194                         hash_strms_do_block(basis_bits[blk], hash[blk]);
    195                         identity_group_do_block(markers[blk], groups[blk]);
    196                         blk++;
    197                         remaining -= BLOCK_SIZE;
     195        s2p_do_block((BytePack *) &raw_buffer[blk*BLOCK_SIZE], basis_bits[blk]);
     196        markers_do_block(basis_bits[blk], markers[blk]);
     197        hash_strms_do_block(basis_bits[blk], hash[blk]);
     198        identity_group_do_block(markers[blk], groups[blk]);
     199        blk++;
     200        remaining -= BLOCK_SIZE;
    198201    }
    199202
     
    202205    ///////////////////////////////////////////////////////////////////////////
    203206    if (remaining > 0 || @marker_strms_any_carry || @group_strms_any_carry /*|| hash_strms_any_carry*/) {
    204                         BitBlock EOF_mask = bitblock::srl(simd<1>::constant<1>(), convert(BLOCK_SIZE-remaining));
    205                         s2p_do_final_block((BytePack *) &raw_buffer[blk*BLOCK_SIZE], basis_bits[blk], EOF_mask);
    206                         markers_do_final_block(basis_bits[blk], markers[blk], EOF_mask);
    207                         hash_strms_do_final_block(basis_bits[blk], hash[blk], EOF_mask);
    208                         identity_group_do_final_block(markers[blk], groups[blk], EOF_mask);
    209                         blk++;
     207        BitBlock EOF_mask = bitblock::srl(simd<1>::constant<1>(), convert(BLOCK_SIZE-remaining));
     208        s2p_do_final_block((BytePack *) &raw_buffer[blk*BLOCK_SIZE], basis_bits[blk], EOF_mask);
     209        markers_do_final_block(basis_bits[blk], markers[blk], EOF_mask);
     210        hash_strms_do_final_block(basis_bits[blk], hash[blk], EOF_mask);
     211        identity_group_do_final_block(markers[blk], groups[blk], EOF_mask);
     212        blk++;
    210213    }
    211214
    212215    uint32_t segment_blocks = blk;
    213216    for(int blk=0;blk<segment_blocks;blk++) { // write contiguous hash bit streams
    214                         h0[blk] = hash[blk].h0;
    215                         h1[blk] = hash[blk].h1;
    216                         starts[blk] = groups[blk].starts;
    217                         ends_gte_17[blk] = groups[blk].ends_gte_17;
     217        h0[blk] = hash[blk].h0;
     218        h1[blk] = hash[blk].h1;
     219        starts[blk] = groups[blk].starts;
     220        ends_gte_17[blk] = groups[blk].ends_gte_17;
    218221    }
    219222
     
    222225    //PERF_SEC_END(parser_timer, chars_avail+1);
    223226
     227    #ifdef IDENTITY_TEST
    224228    uint32_t blk_offset;
    225229    for(int blk=0;blk<segment_blocks;blk++) {
    226                         blk_offset = blk * BLOCKSIZE;
    227                         gid_type gid;
    228                         ForwardScanner<BitBlock, scanword_t> fscanner(&(groups[blk].starts));
    229 
    230                         fscanner.scan_to_next();
    231                         while(!fscanner.is_done()) {
    232                                 gid = gids.at[fscanner.get_pos() + blk_offset];
    233                                 cout << string((char *)st.get_raw_data(gid), st.get_lgth(gid)) << ",";
    234                                 fscanner.scan_to_next();
    235                         }
    236 
    237     }
     230        blk_offset = blk * BLOCKSIZE;
     231        gid_type gid;
     232        ForwardScanner<BitBlock, scanword_t> fscanner(&(groups[blk].starts));
     233
     234        fscanner.scan_to_next();
     235        while(!fscanner.is_done()) {
     236                gid = gids.at[fscanner.get_pos() + blk_offset];
     237                cout << string((char *)st.get_raw_data(gid), st.get_lgth(gid)) << ",";
     238                fscanner.scan_to_next();
     239        }
     240    }
     241    #endif
     242
     243    #ifdef GID_TEST
     244        cout << st.get_max_gid() << endl;
     245    #endif
    238246
    239247    PERF_SEC_DUMP(parser_timer);
  • trunk/symbol_table/src/Makefile

    r2090 r2092  
    1919
    2020id: basis_bits.hpp buffer.hpp byte_pool.hpp hash_strms.hpp  hash_table.hpp ../lib/hash.hpp  group_strms.hpp  symbol_table.hpp  main.cpp  marker_strms.hpp symbol_table.hpp transpose.hpp
    21         $(CC) -o main main.cpp $(AFLAGS) -DID_STRATEGY #-DID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG -DHASH_TABLE_HPP_DEBUG # -DBUFFER_PROFILING
     21        $(CC) -o main main.cpp $(AFLAGS) -DID_STRATEGY -DGID_TEST #-DIDENTITY_TEST  #-DID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG -DHASH_TABLE_HPP_DEBUG # -DBUFFER_PROFILING
    2222
    2323div2: basis_bits.hpp buffer.hpp byte_pool.hpp hash_strms.hpp  hash_table.hpp ../lib/hash.hpp  group_strms.hpp  symbol_table.hpp  main.cpp  marker_strms.hpp symbol_table.hpp transpose.hpp
    24         $(CC) -o main main.cpp $(AFLAGS) -DDIV2_STRATEGY #-DID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG -DHASH_TABLE_HPP_DEBUG # -DBUFFER_PROFILING
     24        $(CC) -o main main.cpp $(AFLAGS) -DDIV2_STRATEGY -DGID_TEST #-DIDENTITY_TEST #-DHASH_TABLE_HPP_DEBUG #-DID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG -DBUFFER_PROFILING
    2525
    2626logbase2: basis_bits.hpp buffer.hpp byte_pool.hpp hash_strms.hpp  hash_table.hpp ../lib/hash.hpp  group_strms.hpp  symbol_table.hpp  main.cpp  marker_strms.hpp symbol_table.hpp transpose.hpp
    27         $(CC) -o main main.cpp $(AFLAGS) -DLOG2_STRATEGY #-DID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG -DHASH_TABLE_HPP_DEBUG # -DBUFFER_PROFILING
     27        $(CC) -o main main.cpp $(AFLAGS) -DLOG2_STRATEGY  -DIDENTITY_TEST #-DGID_TEST  #-DID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG  #-DHASH_TABLE_HPP_DEBUG # -DBUFFER_PROFILING
    2828
    29 test: main
    30         python $(TEST_SCRIPT) $(TEST_PRGM) $(TEST_SRC_DIR)
     29diff_test: main
     30        python $(TEST_SCRIPT) $(TEST_PRGM) -d
     31        diff -rq --exclude=".svn" $(TEST_SRC_DIR) $(TEST_DST_DIR) || exit 0
    3132
    32 diff:
    33         diff -rq --exclude=".svn" $(TEST_SRC_DIR) $(TEST_DST_DIR)  || exit 0
     33gid_test:
     34        python $(TEST_SCRIPT) $(TEST_PRGM) -g
    3435
    3536clean:
  • trunk/symbol_table/src/compare_strategy.hpp

    r2056 r2092  
    22#define COMPARE_STRATEGY_HPP
    33
    4 /* Compare Strategy */
    5 class compare_strategy {
     4#include "types.hpp"
     5
     6///////////////////////////////////////////////////////////////////////////////
     7// Compare Strategy Interface
     8///////////////////////////////////////////////////////////////////////////////
     9class icompare_strategy {
    610public:
    711    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0);
    812protected:
    9     compare_strategy() {}
     13    icompare_strategy() {}
    1014};
    1115
    12 ///* Length and Type specific comparison */
    13 //template<uint32_t LGTH, class TYPE>
    14 //class identity_strategy_t: public compare_strategy {
    15 //public:
    16 //    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
    17 //      return overlap_compare<LGTH, TYPE>(x,y);
    18 //    }
    19 //};
    20 
    21 /* Length specific comparison */
    22 template<uint32_t LGTH>
    23 class compare_strategy_t: public compare_strategy {
    24 public:
    25     static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
    26         return overlap_compare<LGTH, BitBlock>(x,y);
    27     }
    28 };
    29 
    30 /* Default */
    31 template<> class compare_strategy_t<0>: public compare_strategy {
     16///////////////////////////////////////////////////////////////////////////////
     17// Length specialized comparison
     18///////////////////////////////////////////////////////////////////////////////
     19template<uint32_t LGTH, int GROUP_STRATEGY>
     20class compare_strategy_t {
    3221public:
    3322    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
     
    3625};
    3726
    38 template<> class compare_strategy_t<1>: public compare_strategy {
     27///////////////////////////////////////////////////////////////////////////////
     28// Identity - Default Case - Length 0 specialized for length > 16.
     29///////////////////////////////////////////////////////////////////////////////
     30template<int GROUP_STRATEGY> class compare_strategy_t<0,GROUP_STRATEGY> {
     31public:
     32    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth) {
     33        //return mem_compare(x,y,lgth); // TODO review
     34        return overlap_compare<bitblock128_t>(x,y,lgth);
     35    }
     36};
     37
     38template<int GROUP_STRATEGY> class compare_strategy_t<1,GROUP_STRATEGY> {
    3939public:
    4040    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
     
    4343};
    4444
    45 template<> class compare_strategy_t<2>: public compare_strategy {
     45template<int GROUP_STRATEGY> class compare_strategy_t<2,GROUP_STRATEGY> {
    4646public:
    4747    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
     
    5050};
    5151
    52 template<> class compare_strategy_t<3>: public compare_strategy {
     52template<int GROUP_STRATEGY> class compare_strategy_t<3,GROUP_STRATEGY> {
    5353public:
    5454    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
     
    5757};
    5858
    59 template<> class compare_strategy_t<4>: public compare_strategy {
     59template<int GROUP_STRATEGY> class compare_strategy_t<4,GROUP_STRATEGY> {
    6060public:
    6161    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
     
    6464};
    6565
    66 template<> class compare_strategy_t<5>: public compare_strategy {
     66template<int GROUP_STRATEGY> class compare_strategy_t<5,GROUP_STRATEGY> {
    6767public:
    6868    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
     
    7171};
    7272
    73 template<> class compare_strategy_t<6>: public compare_strategy {
     73template<int GROUP_STRATEGY> class compare_strategy_t<6,GROUP_STRATEGY> {
    7474public:
    7575    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
     
    7878};
    7979
    80 template<> class compare_strategy_t<7>: public compare_strategy {
     80template<int GROUP_STRATEGY> class compare_strategy_t<7,GROUP_STRATEGY> {
    8181public:
    8282    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
     
    8585};
    8686
    87 template<> class compare_strategy_t<8>: public compare_strategy {
     87template<int GROUP_STRATEGY> class compare_strategy_t<8,GROUP_STRATEGY> {
    8888public:
    8989    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
     
    9292};
    9393
    94 template<> class compare_strategy_t<9>: public compare_strategy {
     94template<int GROUP_STRATEGY> class compare_strategy_t<9,GROUP_STRATEGY> {
    9595public:
    9696    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
     
    9999};
    100100
    101 template<> class compare_strategy_t<10>: public compare_strategy {
     101template<int GROUP_STRATEGY> class compare_strategy_t<10,GROUP_STRATEGY> {
    102102public:
    103103    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
     
    106106};
    107107
    108 template<> class compare_strategy_t<11>: public compare_strategy {
     108template<int GROUP_STRATEGY> class compare_strategy_t<11,GROUP_STRATEGY> {
    109109public:
    110110    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
     
    113113};
    114114
    115 template<> class compare_strategy_t<12>: public compare_strategy {
     115template<int GROUP_STRATEGY> class compare_strategy_t<12,GROUP_STRATEGY> {
    116116public:
    117117    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
     
    120120};
    121121
    122 template<> class compare_strategy_t<13>: public compare_strategy {
     122template<int GROUP_STRATEGY> class compare_strategy_t<13,GROUP_STRATEGY> {
    123123public:
    124124    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
     
    127127};
    128128
    129 template<> class compare_strategy_t<14>: public compare_strategy {
     129template<int GROUP_STRATEGY> class compare_strategy_t<14,GROUP_STRATEGY> {
    130130public:
    131131    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
     
    134134};
    135135
    136 template<> class compare_strategy_t<15>: public compare_strategy {
     136template<int GROUP_STRATEGY> class compare_strategy_t<15,GROUP_STRATEGY> {
    137137public:
    138138    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
     
    141141};
    142142
    143 template<> class compare_strategy_t<16>: public compare_strategy {
     143template<int GROUP_STRATEGY> class compare_strategy_t<16,GROUP_STRATEGY> {
    144144public:
    145145    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
    146         return overlap_compare<16, BitBlock>(x,y);
     146        return overlap_compare<16, bitblock128_t>(x,y);
    147147    }
    148148};
    149149
    150 ///* Default */
    151 //class identity_strategy_d: public compare_strategy {
    152 //public:
    153 //    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
    154 //      return mem_compare(x,y,lgth);
    155 //    }
    156 //};
     150template<> class compare_strategy_t<1,logbase2> {
     151public:
     152    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth) {
     153        //return mem_compare(x,y,lgth); // TODO review
     154        return overlap_compare<uint8_t>(x,y,lgth);
     155    }
     156};
    157157
     158template<> class compare_strategy_t<2,logbase2> {
     159public:
     160    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth) {
     161        //return mem_compare(x,y,lgth); // TODO review
     162        return overlap_compare<uint8_t>(x,y,lgth);
     163    }
     164};
     165
     166template<> class compare_strategy_t<4,logbase2> {
     167public:
     168    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth) {
     169        //return mem_compare(x,y,lgth); // TODO review
     170        return overlap_compare<uint16_t>(x,y,lgth);
     171    }
     172};
     173
     174template<> class compare_strategy_t<8,logbase2> {
     175public:
     176    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth) {
     177        //return mem_compare(x,y,lgth); // TODO review
     178        return overlap_compare<uint32_t>(x,y,lgth);
     179    }
     180};
     181
     182template<> class compare_strategy_t<16,logbase2> {
     183public:
     184    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth) {
     185        //return mem_compare(x,y,lgth); // TODO review
     186        return overlap_compare<uint64_t>(x,y,lgth);
     187    }
     188};
    158189
    159190#endif // COMPARE_STRATEGY_HPP
  • trunk/symbol_table/src/gid.hpp

    r2033 r2092  
    2828    }
    2929
    30     IDISA_ALWAYS_INLINE size_t max() { return values.size(); }
     30    IDISA_ALWAYS_INLINE size_t max() const { return values.size(); }
    3131
    3232    IDISA_ALWAYS_INLINE uint8_t * get_raw_bytes(size_t idx) const {
  • trunk/symbol_table/src/hash_strategy.hpp

    r2078 r2092  
    22#define HASH_STRATEGY_HPP
    33
    4 #define MAX_HASH_BITS 17 // maximum length specific hash_strategy
     4#include "types.hpp"
    55
    6 enum group_strategy { id, div2, logbase2 };
     6#define MAX_HASH_BITS 17 // Maximum length specific hash_strategy
    77
    8 /* Hash Strategy */
    9 class hash_strategy {
     8
     9///////////////////////////////////////////////////////////////////////////////
     10// Hash Strategy Interface
     11///////////////////////////////////////////////////////////////////////////////
     12class ihash_strategy {
    1013public:
    1114    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits);
    1215    static IDISA_ALWAYS_INLINE uint32_t max_hashsize();
    1316protected:
    14     hash_strategy() {}
     17    ihash_strategy() {}
    1518};
    1619
    17 /* Hash functions specialized on symbol length. */
    18 template<uint32_t LGTH, int GROUP_STRATEGY>
    19 class hash_strategy_t: public hash_strategy {
     20///////////////////////////////////////////////////////////////////////////////
     21// Hash Strategy templated on LGTH, GROUP, SCALE FACTOR (BIT vs. BYTE)
     22///////////////////////////////////////////////////////////////////////////////
     23template<uint32_t LGTH, int GROUP_STRATEGY, int SCALE_FACTOR>
     24class hash_strategy_t: public ihash_strategy {
    2025public:
    2126    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits);
     
    2429
    2530///////////////////////////////////////////////////////////////////////////////
    26 // Bit Space Hash
     31// Identity - Default Case - Length 0 specialized for length > 16.
    2732///////////////////////////////////////////////////////////////////////////////
    28 template<> class hash_strategy_t<0,id> {
     33template<int SCALE_FACTOR> class hash_strategy_t<0,id,SCALE_FACTOR> {
    2934public:
    3035    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    31         return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits); // expect h0 as hash bit stream
     36        return bit_compress_hash(h0, h1, idx*SCALE_FACTOR, slice_bits, hash_bits); // expect h0 as hash bit stream
    3237    }
    3338    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return MAX_HASH_BITS; }
     
    3540
    3641///////////////////////////////////////////////////////////////////////////////
    37 // Byte Space Hash - Identity
     42// Identity - Length 1 specialized.
    3843///////////////////////////////////////////////////////////////////////////////
    39 template<> class hash_strategy_t<1,id> {
     44template<int SCALE_FACTOR> class hash_strategy_t<1,id,SCALE_FACTOR> {
    4045public:
    4146    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
     
    4550};
    4651
    47 template<> class hash_strategy_t<2,id> {
     52template<uint32_t LGTH, int SCALE_FACTOR> class hash_strategy_t<LGTH,id,SCALE_FACTOR> {
    4853public:
    4954    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    50         return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
     55        return bit_compress_hash(h0, h1, idx*SCALE_FACTOR, slice_bits, hash_bits);
    5156    }
    52     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(2); }
    53 };
    54 
    55 template<> class hash_strategy_t<3,id> {
    56 public:
    57     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    58         return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
    59     }
    60     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(3); }
    61 };
    62 
    63 template<> class hash_strategy_t<4,id>: public hash_strategy {
    64 public:
    65     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    66         return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
    67     };
    68     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(4); }
    69 };
    70 
    71 template<> class hash_strategy_t<5,id>: public hash_strategy {
    72 public:
    73     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    74         return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
    75     };
    76     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(5); }
    77 };
    78 
    79 template<> class hash_strategy_t<6,id>: public hash_strategy {
    80 public:
    81     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    82         return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
    83     };
    84     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(6); }
    85 };
    86 
    87 template<> class hash_strategy_t<7,id>: public hash_strategy {
    88 public:
    89     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    90         return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
    91     };
    92     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(7); }
     57    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return LGTH*SCALE_FACTOR; }
    9358};
    9459
    9560///////////////////////////////////////////////////////////////////////////////
    96 // Bit Space Hash - Identity
     61// Bit Space / Byte Space - div2 == id WTE bit/byte boundardy.
    9762///////////////////////////////////////////////////////////////////////////////
    98 template<> class hash_strategy_t<8,id>: public hash_strategy {
    99 public:
    100     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    101         return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits);
     63template<uint32_t LGTH, int SCALE_FACTOR> class hash_strategy_t<LGTH,div2,SCALE_FACTOR>: public hash_strategy_t<LGTH,id,SCALE_FACTOR>{};
     64
     65template<int SCALE_FACTOR> class hash_strategy_t<7,div2,SCALE_FACTOR> {
     66    public:
     67        static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
     68        return bit_compress_hash(h0, h1, idx*SCALE_FACTOR, slice_bits, hash_bits);
     69        }
     70        static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 7*SCALE_FACTOR; }
    10271    };
    103     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 8; }
    104 };
    10572
    106 template<> class hash_strategy_t<9,id>: public hash_strategy {
    107 public:
    108     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    109         return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits);
    110     };
    111     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 9; }
    112 };
    113 
    114 template<> class hash_strategy_t<10,id>: public hash_strategy {
    115 public:
    116     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    117         return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits);
    118     };
    119     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 10; }
    120 };
    121 
    122 template<> class hash_strategy_t<11,id>: public hash_strategy {
    123 public:
    124     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    125         return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits);
    126     };
    127     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 11; }
    128 };
    129 
    130 template<> class hash_strategy_t<12,id>: public hash_strategy {
    131 public:
    132     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    133         return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits);
    134     };
    135     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 12; }
    136 };
    137 
    138 template<> class hash_strategy_t<13,id>: public hash_strategy {
    139 public:
    140     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    141         return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits);
    142     };
    143     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 13; }
    144 };
    145 
    146 template<> class hash_strategy_t<14,id>: public hash_strategy {
    147 public:
    148     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    149         return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits);
    150     };
    151     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 14; }
    152 };
    153 
    154 template<> class hash_strategy_t<15,id>: public hash_strategy {
    155 public:
    156     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    157         return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits);
    158     };
    159     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 15; }
    160 };
    161 
    162 template<> class hash_strategy_t<16,id>: public hash_strategy {
    163 public:
    164     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    165         return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits);
    166     };
    167     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 16; }
    168 };
    169 
    170 ///////////////////////////////////////////////////////////////////////////////
    171 // Bit Space / Byte Space - Div 2 - Equivalent to identity hash function.
    172 ///////////////////////////////////////////////////////////////////////////////
    173 template<uint32_t LGTH> class hash_strategy_t<LGTH,div2>: public hash_strategy_t<LGTH,id>{};
    174 
    175 ///////////////////////////////////////////////////////////////////////////////
    176 // Byte Space Hash - Log base 2
    177 ///////////////////////////////////////////////////////////////////////////////
    178 template<> class hash_strategy_t<1,logbase2> {
    179 public:
    180     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    181         return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
    182     }
    183     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(1); }
    184 };
    185 
    186 template<> class hash_strategy_t<2,logbase2> {
    187 public:
    188     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    189         return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
    190     }
    191     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(2); }
    192 };
    193 
    194 template<> class hash_strategy_t<4,logbase2> {
    195 public:
    196     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    197         return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
    198     }
    199     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(3); }
    200 };
    201 
    202 template<> class hash_strategy_t<8,logbase2> {
    203 public:
    204     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    205         return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
    206     }
    207     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(5); }
    208 };
    209 
    210 ///////////////////////////////////////////////////////////////////////////////
    211 // Bit Space Hash - Log base 2
    212 ///////////////////////////////////////////////////////////////////////////////
    213 template<> class hash_strategy_t<16,logbase2> {
    214 public:
    215     static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
    216         return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
    217     }
    218     static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 9; }
    219 };
     73/////////////////////////////////////////////////////////////////////////////////
     74// Log base 2
     75/////////////////////////////////////////////////////////////////////////////////
     76template<int SCALE_FACTOR> class hash_strategy_t<1,logbase2,SCALE_FACTOR> : public hash_strategy_t<1,id,SCALE_FACTOR>{};
     77template<int SCALE_FACTOR> class hash_strategy_t<2,logbase2,SCALE_FACTOR> : public hash_strategy_t<2,id,SCALE_FACTOR>{};
     78template<int SCALE_FACTOR> class hash_strategy_t<4,logbase2,SCALE_FACTOR> : public hash_strategy_t<3,id,SCALE_FACTOR>{};
     79template<int SCALE_FACTOR> class hash_strategy_t<8,logbase2,SCALE_FACTOR> : public hash_strategy_t<5,id,SCALE_FACTOR>{};
     80template<int SCALE_FACTOR> class hash_strategy_t<16,logbase2,SCALE_FACTOR> : public hash_strategy_t<9,id,SCALE_FACTOR>{};
    22081
    22182#endif // HASH_STRATEGY_HPP
  • trunk/symbol_table/src/hash_table.hpp

    r2080 r2092  
    4646} node;
    4747
    48 template<uint32_t LGTH, int GROUP_STRATEGY, class ALLOCATOR>
     48template<uint32_t LGTH, int GROUP_STRATEGY, int SCALE_FACTOR, class ALLOCATOR>
    4949class hash_table {
    5050
     
    6868            lookups++;
    6969        #endif
    70         return hash_strategy.hash(h0,h1,idx,this->hash_strategy.max_hashsize(),this->hash_size);
     70
     71        return hash_strategy.hash(h0,h1,idx,this->hash_strategy.max_hashsize(),this->hash_size);;
    7172    }
    7273
     
    275276    node ** table;
    276277    byte_pool<ALLOCATOR> raw_data_pool;
    277     compare_strategy_t<LGTH> compare_strategy;
    278     hash_strategy_t<LGTH,GROUP_STRATEGY> hash_strategy;
     278    compare_strategy_t<LGTH,GROUP_STRATEGY> compare_strategy;
     279    hash_strategy_t<LGTH,GROUP_STRATEGY,SCALE_FACTOR> hash_strategy;
    279280
    280281    ///////////////////////////////////////////////////////////////////////////
     
    353354// id - Identity Strategy
    354355///////////////////////////////////////////////////////////////////////////
    355 template<uint32_t LGTH, int GROUP_STRATEGY, class ALLOCATOR>
    356 class id_hash_table : public hash_table<LGTH, GROUP_STRATEGY, ALLOCATOR> {};
     356template<uint32_t LGTH, int GROUP_STRATEGY, int SCALE_FACTOR, class ALLOCATOR>
     357class id_hash_table : public hash_table<LGTH, GROUP_STRATEGY, SCALE_FACTOR, ALLOCATOR> {};
    357358
    358359///////////////////////////////////////////////////////////////////////////
     
    374375}
    375376
    376 template<uint32_t LGTH, int GROUP_STRATEGY, class ALLOCATOR>
    377 class div2_hash_table : public hash_table<LGTH, GROUP_STRATEGY, ALLOCATOR> {
     377template<uint32_t LGTH, int GROUP_STRATEGY, int SCALE_FACTOR, class ALLOCATOR>
     378class div2_hash_table : public hash_table<LGTH, GROUP_STRATEGY, SCALE_FACTOR, ALLOCATOR> {
    378379
    379380public:
     
    442443    }
    443444
    444     id_hash_table<LGTH-1, id, ALLOCATOR> hash_table_odd;
     445    id_hash_table<LGTH-1, div2, SCALE_FACTOR, ALLOCATOR> hash_table_odd;
    445446};
    446447
     
    448449// log2 - Log base 2 Strategy
    449450///////////////////////////////////////////////////////////////////////////
    450 template<uint32_t LGTH, int GROUP_STRATEGY, class ALLOCATOR>
    451 class logbase2_hash_table : public hash_table<LGTH, GROUP_STRATEGY, ALLOCATOR> {};
     451template<uint32_t LGTH, int GROUP_STRATEGY, int SCALE_FACTOR, class ALLOCATOR>
     452class logbase2_hash_table : public hash_table<LGTH, GROUP_STRATEGY, SCALE_FACTOR, ALLOCATOR> {};
    452453
    453454#endif // HASH_TABLE_HPP
  • trunk/symbol_table/src/symbol_table.hpp

    r2079 r2092  
    1414#define ID_SYMBOL_TABLE_TEMPLATE_HPP
    1515
     16
     17#include "types.hpp"
    1618#include "buffer.hpp"
    1719#include "gid.hpp"
     
    127129                        // Byte Space Hash (Fixed Length)
    128130                        ///////////////////////////////////////////////////////////////////////////////
    129                         #define BYTE_HASH_FIXED(GROUP_STRATEGY, LGTH) \
     131                        #define BYTE_HASH_FIXED(GROUP_STRATEGY, HASH_STRATEGY, LGTH) \
    130132                                if(bitblock::any(groups.ends_##LGTH)) { \
    131                                         do_block<GIDS, GROUP_STRATEGY##_hash_table <LGTH, GROUP_STRATEGY, ALLOCATOR> > \
     133                                        do_block<GIDS, GROUP_STRATEGY##_hash_table <LGTH, GROUP_STRATEGY, HASH_STRATEGY, ALLOCATOR> > \
    132134                                                (blk_offset, \
    133135                                                 hash_table_##LGTH, \
     
    141143                        // Byte Space Variable Lengths (groups contain variable lengths)
    142144                        ///////////////////////////////////////////////////////////////////////////////
    143                         #define BYTE_HASH_VARIABLE(GROUP_STRATEGY, LGTH) \
     145                        #define BYTE_HASH_VARIABLE(GROUP_STRATEGY, HASH_STRATEGY, LGTH) \
    144146                                if(bitblock::any(groups.ends_##LGTH)) { \
    145                                         do_block<GIDS, GROUP_STRATEGY##_hash_table <LGTH, GROUP_STRATEGY, ALLOCATOR> > \
     147                                        do_block<GIDS, GROUP_STRATEGY##_hash_table <LGTH, GROUP_STRATEGY, HASH_STRATEGY, ALLOCATOR> > \
    146148                                                (blk_offset, \
    147149                                                 hash_table_##LGTH, \
     
    157159                        // Bit Space Hash (Fixed Length)
    158160                        ///////////////////////////////////////////////////////////////////////////////
    159                         #define BIT_HASH_FIXED(GROUP_STRATEGY, LGTH) \
     161                        #define BIT_HASH_FIXED(GROUP_STRATEGY, HASH_STRATEGY, LGTH) \
    160162                                if(bitblock::any(groups.ends_##LGTH)) { \
    161                                         do_block<GIDS, GROUP_STRATEGY##_hash_table <LGTH, GROUP_STRATEGY, ALLOCATOR> > \
     163                                        do_block<GIDS, GROUP_STRATEGY##_hash_table <LGTH, GROUP_STRATEGY, HASH_STRATEGY, ALLOCATOR> > \
    162164                                                (blk_offset, \
    163165                                                 hash_table_##LGTH, \
     
    171173                        // Byte Space Variable Lengths (groups contain variable lengths)
    172174                        ///////////////////////////////////////////////////////////////////////////////
    173                         #define BIT_HASH_VARIABLE(GROUP_STRATEGY, LGTH) \
     175                        #define BIT_HASH_VARIABLE(GROUP_STRATEGY, HASH_STRATEGY, LGTH) \
    174176                                if(bitblock::any(groups.ends_##LGTH)) { \
    175                                         do_block<GIDS, GROUP_STRATEGY##_hash_table <LGTH, GROUP_STRATEGY, ALLOCATOR> > \
     177                                        do_block<GIDS, GROUP_STRATEGY##_hash_table <LGTH, GROUP_STRATEGY, HASH_STRATEGY, ALLOCATOR> > \
    176178                                                (blk_offset, \
    177179                                                 hash_table_##LGTH, \
     
    188190                        ///////////////////////////////////////////////////////////////////////////////
    189191                        #ifdef ID_STRATEGY
    190                             BYTE_HASH_FIXED(id,1);
    191                             BYTE_HASH_FIXED(id,2);
    192                             BYTE_HASH_FIXED(id,3);
    193                             BYTE_HASH_FIXED(id,4);
    194                             BYTE_HASH_FIXED(id,5);
    195                             BYTE_HASH_FIXED(id,6);
    196                             BYTE_HASH_FIXED(id,7);
    197                             BIT_HASH_FIXED(id,8);
    198                             BIT_HASH_FIXED(id,9);
    199                             BIT_HASH_FIXED(id,10);
    200                             BIT_HASH_FIXED(id,11);
    201                             BIT_HASH_FIXED(id,12);
    202                             BIT_HASH_FIXED(id,13);
    203                             BIT_HASH_FIXED(id,14);
    204                             BIT_HASH_FIXED(id,15);
    205                             BIT_HASH_FIXED(id,16);
     192                            BYTE_HASH_FIXED(id,byte,1);
     193                            BYTE_HASH_FIXED(id,byte,2);
     194                            BYTE_HASH_FIXED(id,byte,3);
     195                            BYTE_HASH_FIXED(id,byte,4);
     196                            BYTE_HASH_FIXED(id,byte,5);
     197                            BYTE_HASH_FIXED(id,byte,6);
     198                            BYTE_HASH_FIXED(id,byte,7);
     199                            BIT_HASH_FIXED(id,bit,8);
     200                            BIT_HASH_FIXED(id,bit,9);
     201                            BIT_HASH_FIXED(id,bit,10);
     202                            BIT_HASH_FIXED(id,bit,11);
     203                            BIT_HASH_FIXED(id,bit,12);
     204                            BIT_HASH_FIXED(id,bit,13);
     205                            BIT_HASH_FIXED(id,bit,14);
     206                            BIT_HASH_FIXED(id,bit,15);
     207                            BIT_HASH_FIXED(id,bit,16);
    206208                        #elif DIV2_STRATEGY
    207                             BYTE_HASH_FIXED(div2,2);
    208                             BYTE_HASH_FIXED(div2,4);
    209                             BYTE_HASH_FIXED(div2,6);
    210                             BIT_HASH_FIXED(div2,8);
    211                             BIT_HASH_FIXED(div2,10);
    212                             BIT_HASH_FIXED(div2,12);
    213                             BIT_HASH_FIXED(div2,14);
    214                             BIT_HASH_FIXED(div2,16);
     209                            BYTE_HASH_FIXED(div2,byte,2);
     210                            BYTE_HASH_FIXED(div2,byte,4);
     211                            BYTE_HASH_FIXED(div2,byte,6);
     212                            BIT_HASH_FIXED(div2,bit,8);
     213                            BIT_HASH_FIXED(div2,bit,10);
     214                            BIT_HASH_FIXED(div2,bit,12);
     215                            BIT_HASH_FIXED(div2,bit,14);
     216                            BIT_HASH_FIXED(div2,bit,16);
    215217                        #elif LOG2_STRATEGY
    216                             BYTE_HASH_VARIABLE(logbase2,1);
    217                             BYTE_HASH_VARIABLE(logbase2,2);
    218                             BYTE_HASH_VARIABLE(logbase2,4);
    219                             BIT_HASH_VARIABLE(logbase2,8);
    220                             BIT_HASH_VARIABLE(logbase2,16);
     218                            BYTE_HASH_VARIABLE(logbase2,byte,1);
     219                            BYTE_HASH_VARIABLE(logbase2,byte,2);
     220                            BYTE_HASH_VARIABLE(logbase2,byte,4);
     221                            BIT_HASH_VARIABLE(logbase2,bit,8);
     222                            BIT_HASH_VARIABLE(logbase2,bit,16);
    221223                        #endif
    222224
     
    227229
    228230                        if(bitblock::any(groups.ends_gte_17)) {
    229                             do_block<GIDS, id_hash_table<0, id, ALLOCATOR> >
     231                            do_block<GIDS, id_hash_table<0, id, bit, ALLOCATOR> >
    230232                                                (blk_offset,
    231233                                                 hash_table_gte_17,
     
    239241        IDISA_ALWAYS_INLINE uint8_t * get_raw_data(uint32_t idx) const { return gid_data.get_raw_bytes(idx); }
    240242        IDISA_ALWAYS_INLINE uint32_t get_lgth(uint32_t idx) const { return gid_data.get_bytes_lgth(idx); }
     243        IDISA_ALWAYS_INLINE gid_type get_max_gid() const { return gid_data.max(); }
    241244
    242245private:
     
    248251        ///////////////////////////////////////////////////////////////////////////////
    249252        #ifdef ID_STRATEGY
    250             id_hash_table<1, id, ALLOCATOR> hash_table_1;
    251             id_hash_table<2, id, ALLOCATOR> hash_table_2;
    252             id_hash_table<3, id, ALLOCATOR> hash_table_3;
    253             id_hash_table<4, id, ALLOCATOR> hash_table_4;
    254             id_hash_table<5, id, ALLOCATOR> hash_table_5;
    255             id_hash_table<6, id, ALLOCATOR> hash_table_6;
    256             id_hash_table<7, id, ALLOCATOR> hash_table_7;
    257             id_hash_table<8, id, ALLOCATOR> hash_table_8;
    258             id_hash_table<9, id, ALLOCATOR> hash_table_9;
    259             id_hash_table<10, id, ALLOCATOR> hash_table_10;
    260             id_hash_table<11, id, ALLOCATOR> hash_table_11;
    261             id_hash_table<12, id, ALLOCATOR> hash_table_12;
    262             id_hash_table<13, id, ALLOCATOR> hash_table_13;
    263             id_hash_table<14, id, ALLOCATOR> hash_table_14;
    264             id_hash_table<15, id, ALLOCATOR> hash_table_15;
    265             id_hash_table<16, id, ALLOCATOR> hash_table_16;
     253            id_hash_table<1, id, byte, ALLOCATOR> hash_table_1;
     254            id_hash_table<2, id, byte, ALLOCATOR> hash_table_2;
     255            id_hash_table<3, id, byte, ALLOCATOR> hash_table_3;
     256            id_hash_table<4, id, byte, ALLOCATOR> hash_table_4;
     257            id_hash_table<5, id, byte, ALLOCATOR> hash_table_5;
     258            id_hash_table<6, id, byte, ALLOCATOR> hash_table_6;
     259            id_hash_table<7, id, byte, ALLOCATOR> hash_table_7;
     260            id_hash_table<8, id, bit, ALLOCATOR> hash_table_8;
     261            id_hash_table<9, id, bit, ALLOCATOR> hash_table_9;
     262            id_hash_table<10, id, bit, ALLOCATOR> hash_table_10;
     263            id_hash_table<11, id, bit, ALLOCATOR> hash_table_11;
     264            id_hash_table<12, id, bit, ALLOCATOR> hash_table_12;
     265            id_hash_table<13, id, bit, ALLOCATOR> hash_table_13;
     266            id_hash_table<14, id, bit, ALLOCATOR> hash_table_14;
     267            id_hash_table<15, id, bit, ALLOCATOR> hash_table_15;
     268            id_hash_table<16, id, bit, ALLOCATOR> hash_table_16;
    266269        #elif DIV2_STRATEGY
    267             div2_hash_table<2, div2, ALLOCATOR> hash_table_2;
    268             div2_hash_table<4, div2, ALLOCATOR> hash_table_4;
    269             div2_hash_table<6, div2, ALLOCATOR> hash_table_6;
    270             div2_hash_table<8, div2, ALLOCATOR> hash_table_8;
    271             div2_hash_table<10, div2, ALLOCATOR> hash_table_10;
    272             div2_hash_table<12, div2, ALLOCATOR> hash_table_12;
    273             div2_hash_table<14, div2, ALLOCATOR> hash_table_14;
    274             div2_hash_table<16, div2, ALLOCATOR> hash_table_16;
     270            div2_hash_table<2, div2, byte, ALLOCATOR> hash_table_2;
     271            div2_hash_table<4, div2, byte, ALLOCATOR> hash_table_4;
     272            div2_hash_table<6, div2, byte, ALLOCATOR> hash_table_6;
     273            div2_hash_table<8, div2, bit, ALLOCATOR> hash_table_8;
     274            div2_hash_table<10, div2, bit, ALLOCATOR> hash_table_10;
     275            div2_hash_table<12, div2, bit, ALLOCATOR> hash_table_12;
     276            div2_hash_table<14, div2, bit, ALLOCATOR> hash_table_14;
     277            div2_hash_table<16, div2, bit, ALLOCATOR> hash_table_16;
    275278        #elif LOG2_STRATEGY
    276             logbase2_hash_table<1, logbase2, ALLOCATOR> hash_table_1;
    277             logbase2_hash_table<2, logbase2, ALLOCATOR> hash_table_2;
    278             logbase2_hash_table<4, logbase2, ALLOCATOR> hash_table_4;
    279             logbase2_hash_table<8, logbase2, ALLOCATOR> hash_table_8;
    280             logbase2_hash_table<16, logbase2, ALLOCATOR> hash_table_16;
     279            logbase2_hash_table<1, logbase2, byte, ALLOCATOR> hash_table_1;
     280            logbase2_hash_table<2, logbase2, byte, ALLOCATOR> hash_table_2;
     281            logbase2_hash_table<4, logbase2, byte, ALLOCATOR> hash_table_4;
     282            logbase2_hash_table<8, logbase2, bit, ALLOCATOR> hash_table_8;
     283            logbase2_hash_table<16, logbase2, bit, ALLOCATOR> hash_table_16;
    281284        #else
    282285            #error "Length group strategy not specified. #define {ID_STRATEGY,DIV2_STRATEGY,LOG2_STRATEGY}."
    283286        #endif
    284287
    285         id_hash_table<0, id, ALLOCATOR> hash_table_gte_17;
     288        id_hash_table<0, id, bit, ALLOCATOR> hash_table_gte_17;
    286289};
    287290
  • trunk/symbol_table/symbol_table.pro

    r2082 r2092  
    1212    test/pool_test.cpp \
    1313    test/hash_test.cpp \
    14     src/main.cpp \
    1514    libtest/byte_compare_template.cpp \
    1615    libtest/byte_compare_generator.cpp \
     
    8281    src/hash_strategy.hpp \
    8382    group_strms_template.hpp \
    84     src/group_strms.hpp
     83    src/group_strms.hpp \
     84    lib/bitblock128.hpp \
     85    lib/bitblock.hpp \
     86    src/types.hpp
  • trunk/symbol_table/test/run_tests.py

    r2090 r2092  
    55#
    66# Quick-and-dirty Python symbol table test script
    7 # to generates expected output files for diff test.
    8 #
    9 # 1. Use st_test_file_generator.py to generate 'st_test_UNIFORM_*' CSV symbol files.
    10 # 2. Execute test script.
    11 # 3. diff -r 'results' directory against input symbol files.
     7# to generates expected output files for diff and gid tests.
    128#
    139# Ken Herdy
     
    2016out_dir_path='../test/out'
    2117#----------------------------------------------------------------------------
     18
    2219import sys
    2320import os
     
    2623import fnmatch                 
    2724import string
    28 
    29 usage='Usage: python ' + __file__ + ' <program> <test root>'
     25import optparse
    3026
    3127def gid_testcase(program, input_file):
     
    3430    triples = prefix.split(')_(')
    3531
    36     sum = 0
     32    e = 0
    3733    for t in triples:
    38         print int(t.split('_')[2])
    39         sum = sum + int(t.split('_')[2])
     34        e = e + int(t.split('_')[2])
    4035
    4136    output = subprocess.Popen([program, input_file], stdout=subprocess.PIPE).communicate()[0]
     37    a = int(output)
     38
     39    print file_name
     40    print "Expected: %d" % e
     41    print "Actual: %d" % a
     42    print
     43    return e == a
    4244
    4345def diff_testcase(program, input_file, outfile_root):
    4446        (head, tail) = os.path.split(input_file)
    4547        outputdir = os.path.join(outfile_root, tail)
    46         print outputdir
    47        
    4848        (head, tail) = os.path.split(outputdir)
    4949        if os.path.exists(head)==False:         
     
    5353        out_f.close()
    5454
     55def gen_test_files(test_dir_path):
     56    test_files = []
     57    for dirname, dirnames, filenames in os.walk(test_dir_path):
     58            for filename in filenames:
     59                    if filename.endswith('.test') and not filename.endswith('.svn-base'):
     60                            test_files.append(os.path.relpath(os.path.join(dirname, filename)))
     61    return test_files
     62
     63#----------------------------------------------------------------------------
     64def get_option_parser():
     65        """Return an C{optparse.OptionParser} instance tied to this configuration."""
     66       
     67        parser = optparse.OptionParser(usage='python %prog [options] <program>',
     68                                        version='1.0',
     69                                        )
     70       
     71        # Option definitions
     72        parser.add_option('-d', '--diff',
     73                          dest='diff_test',
     74                          action='store_true',
     75                          default=False,
     76                          help='Diff test.',
     77                          )
     78
     79        parser.add_option('-g', '--gid',
     80                          dest='gid_test',
     81                          action='store_true',
     82                          default=False,
     83                          help='GID test.',
     84                          )
     85
     86        return parser
     87
     88#----------------------------------------------------------------------------
     89
    5590if __name__ == "__main__":
    5691
    57         if(len(sys.argv) < 2):
    58                 print usage
    59                 sys.exit()
     92        option_parser = get_option_parser()
     93        options, args = option_parser.parse_args(sys.argv[1:])
     94
     95        # Positional arguments
     96        if len(args) != 1:
     97            option_parser.print_usage()
     98            sys.exit()
    6099
    61100        program = os.path.join(program_dir_path,sys.argv[1])
     101        test_files = gen_test_files(test_dir_path)
    62102
    63         for dirname, dirnames, filenames in os.walk(test_dir_path):
    64                 for filename in filenames:
    65                         if filename.endswith('.test') and not filename.endswith('.svn-base'):
    66                                 relfile = os.path.relpath(os.path.join(dirname, filename))
    67                                 diff_testcase(program, relfile, out_dir_path)
    68                                 #gid_testcase(program, relfile)
     103        if options.diff_test:
     104            for test_file in test_files:
     105                    diff_testcase(program, test_file, out_dir_path)
    69106
     107        if options.gid_test:
     108            all_true = True
     109            for test_file in test_files:
     110                    result = gid_testcase(program, test_file)
     111                    all_true = all_true and result
     112
     113            if all_true:
     114                print "All pass."
    70115       
  • trunk/symbol_table/test/st_test_file_generator.py

    r2075 r2092  
    2424#    in the generated test file.
    2525
    26 usage = "python testFileGenerator.py [L,O,U] [L,O,U] [L,O,U] ... AvgGap MaxGap"
     26usage = "python testFileGenerator.py (L,O,U) (L,O,U) (L,O,U) ... AvgGap MaxGap"
    2727
    2828# parallel lists
     
    229229        base_filename = ""
    230230        for lst in symbol_specs:
    231             base_filename += "[" + str(lst[0]) + "_" + str(lst[1]) + "_" + str(lst[2]) + "]"
     231            base_filename += "(" + str(lst[0]) + "_" + str(lst[1]) + "_" + str(lst[2]) + ")"
    232232        base_filename += "_" + str(arguments[num_args-2]) + "_" + str(arguments[num_args-1])
    233233
Note: See TracChangeset for help on using the changeset viewer.