Changeset 2069 for trunk/symbol_table


Ignore:
Timestamp:
May 5, 2012, 4:32:26 PM (7 years ago)
Author:
ksherdy
Message:

Refactored build process. Added log2 support.

Location:
trunk/symbol_table
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • trunk/symbol_table/Makefile

    r2068 r2069  
    3131
    3232GROUP_PREFIX=@group_strms_
    33 #GROUP_PABLO_SRC= $(ID_GROUP_STRMS)
    34 GROUP_PABLO_SRC= $(DIV2_GROUP_STRMS)
    35 #GROUP_PABLO_SRC= $(LOG2_GROUP_STRMS)
    3633GROUP_TEMPLATE=group_strms_template.hpp
    3734GROUP_OUTFILE=src/group_strms.hpp
     
    4037MAIN_OUTFILE=src/main.cpp
    4138
    42 all: marker_strms.py marker_strms_template.hpp hash_strms.py hash_strms_template.hpp id_group_strms.py group_strms_template.hpp main_template.cpp
    43         python $(PABLO_COMPILER) $(MARKER_PABLO_SRC) -t $(MARKER_TEMPLATE) -l$(MARKER_PREFIX) -o $(MARKER_OUTFILE) $(PABLO_ADD_DEBUG)
    44         python $(PABLO_COMPILER) $(HASH_PABLO_SRC) -t $(HASH_TEMPLATE) -l$(HASH_PREFIX) -o $(HASH_OUTFILE) $(PABLO_ADD_DEBUG)
    45         python $(PABLO_COMPILER) $(GROUP_PABLO_SRC) -t $(GROUP_TEMPLATE) -l$(GROUP_PREFIX) -o $(GROUP_OUTFILE) $(PABLO_ADD_DEBUG)
    46         python $(PABLO_COMPILER) $(MARKER_PABLO_SRC) -t $(MAIN_TEMPLATE) -l$(MARKER_PREFIX) -o $(MAIN_OUTFILE) $(PABLO_ADD_DEBUG) # @marker_strms_any_carry
    47         python $(PABLO_COMPILER) $(GROUP_PABLO_SRC) -t $(MAIN_OUTFILE) -l$(GROUP_PREFIX) -o $(MAIN_OUTFILE) $(PABLO_ADD_DEBUG) # @marker_strms_any_carry
     39id: markers hash id_group src/main.cpp
     40        python $(PABLO_COMPILER) $(MARKER_PABLO_SRC) -t $(MAIN_OUTFILE) -l $(MARKER_PREFIX) -o $(MAIN_OUTFILE) $(PABLO_ADD_DEBUG)
     41
     42div2: markers hash div2_group src/main.cpp
     43        python $(PABLO_COMPILER) $(MARKER_PABLO_SRC) -t $(MAIN_OUTFILE) -l $(MARKER_PREFIX) -o $(MAIN_OUTFILE) $(PABLO_ADD_DEBUG)
     44
     45log2: markers hash log2_group src/main.cpp
     46        python $(PABLO_COMPILER) $(MARKER_PABLO_SRC) -t $(MAIN_OUTFILE) -l $(MARKER_PREFIX) -o $(MAIN_OUTFILE) $(PABLO_ADD_DEBUG)
     47
     48markers: marker_strms.py marker_strms_template.hpp
     49        python $(PABLO_COMPILER) $(MARKER_PABLO_SRC) -t $(MARKER_TEMPLATE) -l $(MARKER_PREFIX) -o $(MARKER_OUTFILE) $(PABLO_ADD_DEBUG)
     50
     51hash: hash_strms.py hash_strms_template.hpp
     52        python $(PABLO_COMPILER) $(HASH_PABLO_SRC) -t $(HASH_TEMPLATE) -l $(HASH_PREFIX) -o $(HASH_OUTFILE) $(PABLO_ADD_DEBUG)
     53
     54id_group: id_group_strms.py group_strms_template.hpp main_template.cpp
     55        python $(PABLO_COMPILER) $(ID_GROUP_STRMS) -t $(GROUP_TEMPLATE) -l $(GROUP_PREFIX) -o $(GROUP_OUTFILE) $(PABLO_ADD_DEBUG)
     56        python $(PABLO_COMPILER) $(ID_GROUP_STRMS) -t $(MAIN_TEMPLATE) -l $(GROUP_PREFIX) -o $(MAIN_OUTFILE) $(PABLO_ADD_DEBUG)
     57
     58div2_group: div2_group_strms.py group_strms_template.hpp main_template.cpp
     59        python $(PABLO_COMPILER) $(DIV2_GROUP_STRMS) -t $(GROUP_TEMPLATE) -l $(GROUP_PREFIX) -o $(GROUP_OUTFILE) $(PABLO_ADD_DEBUG)
     60        python $(PABLO_COMPILER) $(DIV2_GROUP_STRMS) -t $(MAIN_TEMPLATE) -l $(GROUP_PREFIX) -o $(MAIN_OUTFILE) $(PABLO_ADD_DEBUG)
     61
     62log2_group: log2_group_strms.py group_strms_template.hpp main_template.cpp
     63        python $(PABLO_COMPILER) $(LOG2_GROUP_STRMS) -t $(GROUP_TEMPLATE) -l $(GROUP_PREFIX) -o $(GROUP_OUTFILE) $(PABLO_ADD_DEBUG)
     64        python $(PABLO_COMPILER) $(LOG2_GROUP_STRMS) -t $(MAIN_TEMPLATE) -l $(GROUP_PREFIX) -o $(MAIN_OUTFILE) $(PABLO_ADD_DEBUG)
     65
    4866clean:
    4967        rm -f $(MARKER_OUTFILE) $(HASH_OUTFILE) $(GROUP_OUTFILE) $(MAIN_OUTFILE)
    5068
    51        
     69
  • trunk/symbol_table/src/Makefile

    r2055 r2069  
    1313endif
    1414
    15 TEST_ROOT=../test
     15TEST_SCRIPT = ../test/run_tests.py
     16TEST_PRGM = main
     17TEST_SRC_DIR = ../test/uniform
     18TEST_DST_DIR = ../test/uniform_rslts
    1619
    17 all: basis_bits.hpp buffer.hpp byte_pool.hpp  hash_strms.hpp  hash_table.hpp  group_strms.hpp  symbol_table.hpp  main.cpp  Makefile  marker_strms.hpp  symbol_table.hpp  transpose.hpp
    18         $(CC) -o main main.cpp $(AFLAGS) #-DID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG #-DHASH_TABLE_HPP_DEBUG # -DBUFFER_PROFILING
     20id: 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
     22
     23div2: 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
     25
     26log2: 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
    1928
    2029test: main
    21         python $(TEST_ROOT)/run_tests.py main $(TEST_ROOT)/uniform
     30        python $(TEST_SCRIPT) $(TEST_PRGM) $(TEST_SRC_DIR)
    2231
    2332diff:
    24         diff -rq --exclude=".svn" $(TEST_ROOT)/uniform $(TEST_ROOT)/uniform_rslts || exit 0
     33        diff -rq --exclude=".svn" $(TEST_SRC_DIR) $(TEST_DST_DIR) || exit 0
    2534
    2635clean:
    27         rm -Rf main $(TEST_ROOT)/uniform_rslts
     36        rm -Rf main $(TEST_DST_DIR)
    2837
  • trunk/symbol_table/src/hash_strategy.hpp

    r2053 r2069  
    3434
    3535///////////////////////////////////////////////////////////////////////////////
    36 // Byte Space Hash
     36// Byte Space Hash - Identity
    3737///////////////////////////////////////////////////////////////////////////////
    3838template<> class hash_strategy_t<1> {
     
    9393
    9494///////////////////////////////////////////////////////////////////////////////
    95 // Bit Space Hash
     95// Bit Space Hash - Identity
    9696///////////////////////////////////////////////////////////////////////////////
    9797template<> class hash_strategy_t<8>: public hash_strategy {
     
    167167};
    168168
    169 ///* Default */
    170 //class hash_strategy_d: public hash_strategy {
    171 //public:
    172 //    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) {
    173 //      return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits); // expect h0 as hash bit stream
    174 //    }
    175 //    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return MAX_HASH_BITS; }
    176 //};
     169
     170///////////////////////////////////////////////////////////////////////////////
     171// Log base 2
     172///////////////////////////////////////////////////////////////////////////////
     173template<uint32_t LGTH>
     174class log_hash_strategy_t: public hash_strategy {
     175public:
     176    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);
     177    static IDISA_ALWAYS_INLINE uint32_t max_hashsize();
     178};
     179
     180///////////////////////////////////////////////////////////////////////////////
     181// Byte Space Hash - Log 2
     182///////////////////////////////////////////////////////////////////////////////
     183template<> class log_hash_strategy_t<1> {
     184public:
     185    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) {
     186        return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
     187    }
     188    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(1); }
     189};
     190
     191template<> class log_hash_strategy_t<2> {
     192public:
     193    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) {
     194        return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
     195    }
     196    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(2); }
     197};
     198
     199template<> class log_hash_strategy_t<4> {
     200public:
     201    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) {
     202        return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
     203    }
     204    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(3); }
     205};
     206
     207template<> class log_hash_strategy_t<8> {
     208public:
     209    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) {
     210        return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
     211    }
     212    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(5); }
     213};
     214
     215///////////////////////////////////////////////////////////////////////////////
     216// Bit Space Hash - Log 2
     217///////////////////////////////////////////////////////////////////////////////
     218template<> class log_hash_strategy_t<16> {
     219public:
     220    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) {
     221        return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
     222    }
     223    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 9; }
     224};
    177225
    178226#endif // HASH_STRATEGY_HPP
  • trunk/symbol_table/src/hash_table.hpp

    r2067 r2069  
    4646} node;
    4747
    48 template<uint32_t LGTH, class ALLOCATOR>
     48template<uint32_t LGTH, class COMPARE_STRATEGY, class HASH_STRATEGY, class ALLOCATOR>
    4949class hash_table {
    5050
    5151public:
    52 
    53     IDISA_ALWAYS_INLINE uint64_t get_bucket(const uint8_t * h0, const uint8_t * h1, const uint32_t idx) {
    54                         #ifdef HASH_TABLE_HPP_DEBUG
    55                                         lookups++;
    56                         #endif
    57                         return hash_strategy.hash(h0,h1,idx,this->hash_strategy.max_hashsize(),this->hash_size);
    58     }
    59 
    60     IDISA_ALWAYS_INLINE void insert(const uint64_t bucket, uint8_t * raw_bytes, uint32_t raw_byte_lgth, uint8_t * h0, uint8_t * h1, gid_type gid) {
    61 
    62         node * next = (node *) malloc(sizeof(node));
    63         if (next == NULL) {
    64             cerr << "Out of Memory" << endl;
    65             abort();
    66         }
    67 
    68         next->raw_bytes = raw_bytes;
    69         next->raw_bytes_lgth = raw_byte_lgth;
    70         next->h0 = h0;
    71         next->h1 = h1;
    72         next->gid = gid;
    73 
    74         next->next = table[bucket];
    75         table[bucket] = next;
    76     }
    77 
    78     IDISA_ALWAYS_INLINE void pool_and_insert(uint64_t bucket, uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
    79                                                   uint8_t * h0, uint8_t * h1,
    80                                                   GIDFactory & gid_factory, GIDData & gid_data, gid_type & gid) {
    81 
    82         /* persistant data */
    83         gid = gid_factory.next();
    84 
    85         uint64_t x0 = *((uint64_t *)(h0 + (idx/8))) >> (idx & (8-1));
    86         uint8_t * data_pool_x0 = this->raw_data_pool.insert((uint8_t *)&x0, bits2bytes(this->hash_strategy.max_hashsize()));
    87 
    88         uint64_t x1 = *((uint64_t *)(h1 + (idx/8))) >> (idx & (8-1));
    89         uint8_t * data_pool_x1 = this->raw_data_pool.insert((uint8_t *)&x1, bits2bytes(this->hash_strategy.max_hashsize()));
    90 
    91         uint8_t * data_pool_raw_bytes = this->raw_data_pool.insert(&raw_bytes[idx],raw_byte_lgth);
    92 
    93         /* insert */
    94         insert( bucket,
    95                 data_pool_raw_bytes,
    96                 raw_byte_lgth,
    97                 data_pool_x0,
    98                 data_pool_x1,
    99                 gid);
    100 
    101         if(this->expansion_test(this->table[bucket])) {
    102             #ifdef HASH_TABLE_HPP_DEBUG
    103                 this->table_expansions++;
    104             #endif
    105             this->expand();
    106         }
    107 
    108         #ifdef HASH_TABLE_HPP_DEBUG
    109             elements++;
    110         #endif
    111         gid_data.add_data(data_pool_raw_bytes,raw_byte_lgth);
    112     }
    113 
    114     protected:
    11552
    11653    hash_table(const uint32_t table_size=1024, const uint32_t resize_chain_lgth=2) {
     
    12865    }
    12966
     67    IDISA_ALWAYS_INLINE uint64_t get_bucket(const uint8_t * h0, const uint8_t * h1, const uint32_t idx) {
     68        #ifdef HASH_TABLE_HPP_DEBUG
     69            lookups++;
     70        #endif
     71        return hash_strategy.hash(h0,h1,idx,this->hash_strategy.max_hashsize(),this->hash_size);
     72    }
     73
     74    IDISA_ALWAYS_INLINE void insert(const uint64_t bucket, uint8_t * raw_bytes, uint32_t raw_byte_lgth, uint8_t * h0, uint8_t * h1, gid_type gid) {
     75
     76        node * next = (node *) malloc(sizeof(node));
     77        if (next == NULL) {
     78            cerr << "Out of Memory" << endl;
     79            abort();
     80        }
     81
     82        next->raw_bytes = raw_bytes;
     83        next->raw_bytes_lgth = raw_byte_lgth;
     84        next->h0 = h0;
     85        next->h1 = h1;
     86        next->gid = gid;
     87
     88        next->next = table[bucket];
     89        table[bucket] = next;
     90    }
     91
     92    IDISA_ALWAYS_INLINE void pool_and_insert(uint64_t bucket, uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
     93                                                  uint8_t * h0, uint8_t * h1,
     94                                                  GIDFactory & gid_factory, GIDData & gid_data, gid_type & gid) {
     95
     96        /* persistant data */
     97        gid = gid_factory.next();
     98
     99        uint64_t x0 = *((uint64_t *)(h0 + (idx/8))) >> (idx & (8-1));
     100        uint8_t * data_pool_x0 = this->raw_data_pool.insert((uint8_t *)&x0, bits2bytes(this->hash_strategy.max_hashsize()));
     101
     102        uint64_t x1 = *((uint64_t *)(h1 + (idx/8))) >> (idx & (8-1));
     103        uint8_t * data_pool_x1 = this->raw_data_pool.insert((uint8_t *)&x1, bits2bytes(this->hash_strategy.max_hashsize()));
     104
     105        uint8_t * data_pool_raw_bytes = this->raw_data_pool.insert(&raw_bytes[idx],raw_byte_lgth);
     106
     107        /* insert */
     108        insert( bucket,
     109                data_pool_raw_bytes,
     110                raw_byte_lgth,
     111                data_pool_x0,
     112                data_pool_x1,
     113                gid);
     114
     115        if(this->expansion_test(this->table[bucket])) {
     116            #ifdef HASH_TABLE_HPP_DEBUG
     117                this->table_expansions++;
     118            #endif
     119            this->expand();
     120        }
     121
     122        #ifdef HASH_TABLE_HPP_DEBUG
     123            elements++;
     124        #endif
     125        gid_data.add_data(data_pool_raw_bytes,raw_byte_lgth);
     126    }
     127
     128    IDISA_ALWAYS_INLINE gid_type lookup(uint64_t bucket, uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
     129                                        uint8_t * h0, uint8_t * h1, gid_type & gid) {
     130
     131        node * crt = this->table[bucket];
     132        node * prev = crt;
     133
     134        while(NULL != crt) {
     135            if(this->compare_strategy.compare(&raw_bytes[idx], crt->raw_bytes, raw_byte_lgth)) {
     136                                gid = crt->gid;
     137                                return true;
     138            }
     139            prev = crt;
     140            crt = crt->next;
     141            #ifdef HASH_TABLE_HPP_DEBUG
     142                this->collisions++;
     143            #endif
     144        }
     145
     146        return false;
     147    }
     148
     149    IDISA_ALWAYS_INLINE gid_type lookup_or_insert(uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
     150                                                  uint8_t * h0, uint8_t * h1,
     151                                                  GIDFactory & gid_factory, GIDData & gid_data) {
     152
     153        gid_type gid;
     154        uint64_t bucket = this->get_bucket(h0,h1,idx);
     155
     156        if(lookup(bucket, raw_bytes, idx, raw_byte_lgth, h0, h1, gid)) {
     157            return gid;
     158        }
     159
     160        this->pool_and_insert(bucket, raw_bytes, idx, raw_byte_lgth, h0, h1, gid_factory, gid_data, gid);
     161        return gid;
     162
     163    }
     164
    130165    ///////////////////////////////////////////////////////////////////////////
    131166    // Helpers
    132167    ///////////////////////////////////////////////////////////////////////////
     168    protected:
     169
    133170    uint32_t log2msb(uint32_t v) {
    134171        uint32_t r = 0;
     
    239276    node ** table;
    240277    byte_pool<ALLOCATOR> raw_data_pool;
    241     compare_strategy_t<LGTH> compare_strategy;
    242     hash_strategy_t<LGTH> hash_strategy;
     278    COMPARE_STRATEGY compare_strategy;
     279    HASH_STRATEGY hash_strategy;
    243280
    244281    ///////////////////////////////////////////////////////////////////////////
     
    317354// id - Identity Strategy
    318355///////////////////////////////////////////////////////////////////////////
    319 template<uint32_t LGTH, class ALLOCATOR>
    320 class id_hash_table : public hash_table<LGTH, ALLOCATOR> {
    321 
    322 public:
    323 
    324     IDISA_ALWAYS_INLINE gid_type lookup(uint64_t bucket, uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
    325                                         uint8_t * h0, uint8_t * h1, gid_type & gid) {
    326 
    327         node * crt = this->table[bucket];
    328         node * prev = crt;
    329 
    330         while(NULL != crt) {
    331             if(this->compare_strategy.compare(&raw_bytes[idx], crt->raw_bytes, raw_byte_lgth)) {
    332                                 gid = crt->gid;
    333                                 return true;
    334             }
    335             prev = crt;
    336             crt = crt->next;
    337             #ifdef HASH_TABLE_HPP_DEBUG
    338                 collisions++;
    339             #endif
    340         }
    341 
    342         return false;
    343     }
    344 
    345     IDISA_ALWAYS_INLINE gid_type lookup_or_insert(uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
    346                                                   uint8_t * h0, uint8_t * h1,
    347                                                   GIDFactory & gid_factory, GIDData & gid_data) {
    348 
    349         gid_type gid;
    350         uint64_t bucket = this->get_bucket(h0,h1,idx);
    351 
    352         if(lookup(bucket, raw_bytes, idx, raw_byte_lgth, h0, h1, gid)) {
    353             return gid;
    354         }
    355 
    356         this->pool_and_insert(bucket, raw_bytes, idx, raw_byte_lgth, h0, h1, gid_factory, gid_data, gid);
    357         return gid;
    358 
    359     }
    360 
    361 };
    362 
     356template<uint32_t LGTH, class COMPARE_STRATEGY, class HASH_STRATEGY, class ALLOCATOR>
     357class id_hash_table : public hash_table<LGTH, COMPARE_STRATEGY, HASH_STRATEGY, ALLOCATOR> {};
    363358
    364359///////////////////////////////////////////////////////////////////////////
     
    381376
    382377
    383 template<uint32_t LGTH, class ALLOCATOR>
    384 class div2_hash_table : public hash_table<LGTH, ALLOCATOR> {
     378template<uint32_t LGTH, class COMPARE_STRATEGY, class HASH_STRATEGY, class ALLOCATOR>
     379class div2_hash_table : public hash_table<LGTH, COMPARE_STRATEGY, HASH_STRATEGY, ALLOCATOR> {
    385380
    386381public:
     
    400395            crt = crt->next;
    401396            #ifdef HASH_TABLE_HPP_DEBUG
    402                 collisions++;
     397                this->collisions++;
    403398            #endif
    404399        }
     
    446441    }
    447442
    448     id_hash_table<LGTH-1, ALLOCATOR> hash_table_odd;
     443    id_hash_table<LGTH-1, COMPARE_STRATEGY, HASH_STRATEGY, ALLOCATOR> hash_table_odd;
    449444};
    450445
     
    452447// log2 - Log base 2 Strategy
    453448///////////////////////////////////////////////////////////////////////////
    454 template<uint32_t LGTH, class ALLOCATOR>
    455 class log2_hash_table : public hash_table<LGTH, ALLOCATOR> {
    456 
    457 public:
    458 
    459     IDISA_ALWAYS_INLINE gid_type lookup_or_insert(uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
    460                                                   uint8_t * h0, uint8_t * h1,
    461                                                   GIDFactory & gid_factory, GIDData & gid_data) {
    462 
    463         gid_type gid;
    464         uint64_t bucket = this->get_bucket(h0,h1,idx);
    465 
    466 
    467         return gid;
    468     }
    469 };
     449template<uint32_t LGTH, class COMPARE_STRATEGY, class HASH_STRATEGY, class ALLOCATOR>
     450class log2_hash_table : public hash_table<LGTH, COMPARE_STRATEGY, HASH_STRATEGY, ALLOCATOR> {};
    470451
    471452#endif // HASH_TABLE_HPP
  • trunk/symbol_table/src/symbol_table.hpp

    r2068 r2069  
    121121
    122122        // Groups & groups
    123         IDISA_ALWAYS_INLINE
    124         void resolve(uint32_t blk_offset, uint8_t buffer [], Groups & groups,  BitBlock starts[],
     123        IDISA_ALWAYS_INLINE void resolve(uint32_t blk_offset, uint8_t buffer [], Groups & groups,  BitBlock starts[],
    125124                                 BitBlock * h0, BitBlock * h1, GIDS & gids) {
    126125
     
    128127                        // Byte Space Hash (Fixed Length)
    129128                        ///////////////////////////////////////////////////////////////////////////////
    130                         #define BYTE_HASH_FIXED(GROUP, LGTH) \
     129                        #define BYTE_HASH_FIXED(GROUP_STRATEGY, LGTH, CMP_STRATEGY, HASH_STRATEGY) \
    131130                                if(bitblock::any(groups.ends_##LGTH)) { \
    132                                         do_block<GIDS, GROUP##_hash_table <LGTH, ALLOCATOR> > \
     131                                        do_block<GIDS, GROUP_STRATEGY##_hash_table <LGTH, CMP_STRATEGY, HASH_STRATEGY, ALLOCATOR> > \
    133132                                                (blk_offset, \
    134133                                                 hash_table_##LGTH, \
     
    139138                                }
    140139
    141 //                              //BYTE_HASH_FIXED(id,1);
    142                                 BYTE_HASH_FIXED(div2,2);
    143 //                              //BYTE_HASH_FIXED(id,3);
    144                                 BYTE_HASH_FIXED(div2,4);
    145 //                              //BYTE_HASH_FIXED(id,5);
    146                                 BYTE_HASH_FIXED(div2,6);
    147 //                              //BYTE_HASH_FIXED(id,7);
    148 
    149                         #undef BYTE_HASH_FIXED
    150 
    151140                        /////////////////////////////////////////////////////////////////////////////
    152141                        // Byte Space Variable Lengths (groups contain variable lengths)
    153142                        ///////////////////////////////////////////////////////////////////////////////
    154                         #define BYTE_HASH_VARIABLE(GROUP, LGTH) \
     143                        #define BYTE_HASH_VARIABLE(GROUP_STRATEGY, LGTH, CMP_STRATEGY, HASH_STRATEGY) \
    155144                                if(bitblock::any(groups.ends_##LGTH)) { \
    156                                         do_block<GIDS, GROUP##_hash_table <LGTH, ALLOCATOR> > \
     145                                        do_block<GIDS, GROUP_STRATEGY##_hash_table <LGTH, CMP_STRATEGY, HASH_STRATEGY, ALLOCATOR> > \
    157146                                                (blk_offset, \
    158147                                                 hash_table_##LGTH, \
     
    164153                                }
    165154
    166                                 //BYTE_HASH_VARIABLE(log2,1);
    167                                 //BYTE_HASH_VARIABLE(log2,2);
    168                                 //BYTE_HASH_VARIABLE(log2,4);
    169 
    170                         #undef BYTE_HASH_VARIABLE
    171155
    172156                        ///////////////////////////////////////////////////////////////////////////////
    173157                        // Bit Space Hash (Fixed Length)
    174158                        ///////////////////////////////////////////////////////////////////////////////
    175                         #define BIT_HASH_FIXED(GROUP, LGTH) \
     159                        #define BIT_HASH_FIXED(GROUP_STRATEGY, LGTH, CMP_STRATEGY, HASH_STRATEGY) \
    176160                                if(bitblock::any(groups.ends_##LGTH)) { \
    177                                         do_block<GIDS, GROUP##_hash_table <LGTH, ALLOCATOR> > \
     161                                        do_block<GIDS, GROUP_STRATEGY##_hash_table <LGTH, CMP_STRATEGY, HASH_STRATEGY, ALLOCATOR> > \
    178162                                                (blk_offset, \
    179163                                                 hash_table_##LGTH, \
     
    184168                                }
    185169
    186                                 BIT_HASH_FIXED(div2,8);
    187 //                              //BIT_HASH_FIXED(9);
    188                                 BIT_HASH_FIXED(div2,10);
    189 //                              //BIT_HASH_FIXED(11);
    190                                 BIT_HASH_FIXED(div2,12);
    191 //                              //BIT_HASH_FIXED(13);
    192                                 BIT_HASH_FIXED(div2,14);
    193 //                              //BIT_HASH_FIXED(15);
    194                                 BIT_HASH_FIXED(div2,16);
    195 
     170                        /////////////////////////////////////////////////////////////////////////////
     171                        // Byte Space Variable Lengths (groups contain variable lengths)
     172                        ///////////////////////////////////////////////////////////////////////////////
     173                        #define BIT_HASH_VARIABLE(GROUP_STRATEGY, LGTH, CMP_STRATEGY, HASH_STRATEGY) \
     174                                if(bitblock::any(groups.ends_##LGTH)) { \
     175                                        do_block<GIDS, GROUP_STRATEGY##_hash_table <LGTH, CMP_STRATEGY, HASH_STRATEGY, ALLOCATOR> > \
     176                                                (blk_offset, \
     177                                                 hash_table_##LGTH, \
     178                                                 starts, \
     179                                                 &groups.ends_##LGTH, \
     180                                                 buffer, \
     181                                                 (uint8_t *)h0, (uint8_t *)h1, (BLOCK_SIZE / 8), /* h0, h1, hash block size (bits) */ \
     182                                                 gids, this->gid_factory, this->gid_data); \
     183                                }
     184
     185                        ///////////////////////////////////////////////////////////////////////////////
     186                        // WARNING: BYTE_HASH max 8 bytes under the shift XOR hash approach of hash.hpp
     187                        //     ---> (id,7),(div2,6),(log2,4)
     188                        ///////////////////////////////////////////////////////////////////////////////
     189                        #ifdef ID_STRATEGY
     190                            BYTE_HASH_FIXED(id,1,compare_strategy_t<1>,hash_strategy_t<1>);
     191                            BYTE_HASH_FIXED(id,2,compare_strategy_t<2>,hash_strategy_t<2>);
     192                            BYTE_HASH_FIXED(id,3,compare_strategy_t<3>,hash_strategy_t<3>);
     193                            BYTE_HASH_FIXED(id,4,compare_strategy_t<4>,hash_strategy_t<4>);
     194                            BYTE_HASH_FIXED(id,5,compare_strategy_t<5>,hash_strategy_t<5>);
     195                            BYTE_HASH_FIXED(id,6,compare_strategy_t<6>,hash_strategy_t<6>);
     196                            BYTE_HASH_FIXED(id,7,compare_strategy_t<7>,hash_strategy_t<7>);
     197                            BIT_HASH_FIXED(id,8,compare_strategy_t<8>,hash_strategy_t<8>);
     198                            BIT_HASH_FIXED(id,9,compare_strategy_t<9>,hash_strategy_t<9>);
     199                            BIT_HASH_FIXED(id,10,compare_strategy_t<10>,hash_strategy_t<10>);
     200                            BIT_HASH_FIXED(id,11,compare_strategy_t<11>,hash_strategy_t<11>);
     201                            BIT_HASH_FIXED(id,12,compare_strategy_t<12>,hash_strategy_t<12>);
     202                            BIT_HASH_FIXED(id,13,compare_strategy_t<13>,hash_strategy_t<13>);
     203                            BIT_HASH_FIXED(id,14,compare_strategy_t<14>,hash_strategy_t<14>);
     204                            BIT_HASH_FIXED(id,15,compare_strategy_t<15>,hash_strategy_t<15>);
     205                            BIT_HASH_FIXED(id,16,compare_strategy_t<16>,hash_strategy_t<16>);
     206                        #elif DIV2_STRATEGY
     207                            BYTE_HASH_FIXED(div2,2,compare_strategy_t<2>,hash_strategy_t<2>);
     208                            BYTE_HASH_FIXED(div2,4,compare_strategy_t<4>,hash_strategy_t<4>);
     209                            BYTE_HASH_FIXED(div2,6,compare_strategy_t<6>,hash_strategy_t<6>);
     210                            BIT_HASH_FIXED(div2,8,compare_strategy_t<8>,hash_strategy_t<8>);
     211                            BIT_HASH_FIXED(div2,10,compare_strategy_t<10>,hash_strategy_t<10>);
     212                            BIT_HASH_FIXED(div2,12,compare_strategy_t<12>,hash_strategy_t<12>);
     213                            BIT_HASH_FIXED(div2,14,compare_strategy_t<14>,hash_strategy_t<14>);
     214                            BIT_HASH_FIXED(div2,16,compare_strategy_t<16>,hash_strategy_t<16>);
     215                        #elif LOG2_STRATEGY
     216                            BYTE_HASH_VARIABLE(log2,1,compare_strategy_t<0>,log_hash_strategy_t<1>);
     217                            BYTE_HASH_VARIABLE(log2,2,compare_strategy_t<0>,log_hash_strategy_t<2>);
     218                            BYTE_HASH_VARIABLE(log2,4,compare_strategy_t<0>,log_hash_strategy_t<4>);
     219                            BIT_HASH_VARIABLE(log2,8,compare_strategy_t<0>,log_hash_strategy_t<8>);
     220                            BIT_HASH_VARIABLE(log2,16,compare_strategy_t<0>,log_hash_strategy_t<16>);
     221                        #endif
     222
     223                        #undef BYTE_HASH_FIXED
     224                        #undef BYTE_HASH_VARIABLE
    196225                        #undef BIT_HASH_FIXED
     226                        #undef BIT_HASH_VARIABLE
    197227
    198228                        if(bitblock::any(groups.ends_gte_17)) {
    199 
    200                             do_block<GIDS, id_hash_table<0, ALLOCATOR> >
     229                            do_block<GIDS, id_hash_table<0, compare_strategy_t<0>, hash_strategy_t<0>, ALLOCATOR> >
    201230                                                (blk_offset,
    202231                                                 hash_table_gte_17,
     
    219248        // Byte Space Hash
    220249        ///////////////////////////////////////////////////////////////////////////////
    221 //      div2_hash_table<2, ALLOCATOR> hash_table_1_2;
    222 
    223 //      id_hash_table<1, ALLOCATOR> hash_table_1;
    224 //      id_hash_table<2, ALLOCATOR> hash_table_2;
    225 //      id_hash_table<3, ALLOCATOR> hash_table_3;
    226 //      id_hash_table<4, ALLOCATOR> hash_table_4;
    227 //      id_hash_table<5, ALLOCATOR> hash_table_5;
    228 //      id_hash_table<6, ALLOCATOR> hash_table_6;
    229 //      id_hash_table<7, ALLOCATOR> hash_table_7;
    230 
    231         div2_hash_table<2, ALLOCATOR> hash_table_2;
    232         div2_hash_table<4, ALLOCATOR> hash_table_4;
    233         div2_hash_table<6, ALLOCATOR> hash_table_6;
    234 
    235 //      log2_hash_table<1, ALLOCATOR> hash_table_1;
    236 //      log2_hash_table<2, ALLOCATOR> hash_table_2;
    237 //      log2_hash_table<4, ALLOCATOR> hash_table_4;
    238 
    239         ///////////////////////////////////////////////////////////////////////////////
    240         // Bit Space Hash
    241         ///////////////////////////////////////////////////////////////////////////////
    242 //      id_hash_table<8, ALLOCATOR> hash_table_8;
    243 //      id_hash_table<9, ALLOCATOR> hash_table_9;
    244 //      id_hash_table<10, ALLOCATOR> hash_table_10;
    245 //      id_hash_table<11, ALLOCATOR> hash_table_11;
    246 //      id_hash_table<12, ALLOCATOR> hash_table_12;
    247 //      id_hash_table<13, ALLOCATOR> hash_table_13;
    248 //      id_hash_table<14, ALLOCATOR> hash_table_14;
    249 //      id_hash_table<15, ALLOCATOR> hash_table_15;
    250 //      id_hash_table<16, ALLOCATOR> hash_table_16;
    251 //      id_hash_table<0, ALLOCATOR> hash_table_gte_17;
    252 
    253         div2_hash_table<8, ALLOCATOR> hash_table_8;
    254         div2_hash_table<10, ALLOCATOR> hash_table_10;
    255         div2_hash_table<12, ALLOCATOR> hash_table_12;
    256         div2_hash_table<14, ALLOCATOR> hash_table_14;
    257         div2_hash_table<16, ALLOCATOR> hash_table_16;
    258         id_hash_table<0, ALLOCATOR> hash_table_gte_17;
     250        #ifdef ID_STRATEGY
     251            id_hash_table<1, compare_strategy_t<1>, hash_strategy_t<1>, ALLOCATOR> hash_table_1;
     252            id_hash_table<2, compare_strategy_t<2>, hash_strategy_t<2>, ALLOCATOR> hash_table_2;
     253            id_hash_table<3, compare_strategy_t<3>, hash_strategy_t<3>, ALLOCATOR> hash_table_3;
     254            id_hash_table<4, compare_strategy_t<4>, hash_strategy_t<4>, ALLOCATOR> hash_table_4;
     255            id_hash_table<5, compare_strategy_t<5>, hash_strategy_t<5>, ALLOCATOR> hash_table_5;
     256            id_hash_table<6, compare_strategy_t<6>, hash_strategy_t<6>, ALLOCATOR> hash_table_6;
     257            id_hash_table<7, compare_strategy_t<7>, hash_strategy_t<7>, ALLOCATOR> hash_table_7;
     258            id_hash_table<8, compare_strategy_t<8>, hash_strategy_t<8>, ALLOCATOR> hash_table_8;
     259            id_hash_table<9, compare_strategy_t<9>, hash_strategy_t<9>, ALLOCATOR> hash_table_9;
     260            id_hash_table<10, compare_strategy_t<10>, hash_strategy_t<10>, ALLOCATOR> hash_table_10;
     261            id_hash_table<11, compare_strategy_t<11>, hash_strategy_t<11>, ALLOCATOR> hash_table_11;
     262            id_hash_table<12, compare_strategy_t<12>, hash_strategy_t<12>, ALLOCATOR> hash_table_12;
     263            id_hash_table<13, compare_strategy_t<13>, hash_strategy_t<13>, ALLOCATOR> hash_table_13;
     264            id_hash_table<14, compare_strategy_t<14>, hash_strategy_t<14>, ALLOCATOR> hash_table_14;
     265            id_hash_table<15, compare_strategy_t<15>, hash_strategy_t<15>, ALLOCATOR> hash_table_15;
     266            id_hash_table<16, compare_strategy_t<16>, hash_strategy_t<16>, ALLOCATOR> hash_table_16;
     267        #elif DIV2_STRATEGY
     268            div2_hash_table<2, compare_strategy_t<2>, hash_strategy_t<2>, ALLOCATOR> hash_table_2;
     269            div2_hash_table<4, compare_strategy_t<4>, hash_strategy_t<4>, ALLOCATOR> hash_table_4;
     270            div2_hash_table<6, compare_strategy_t<6>, hash_strategy_t<6>, ALLOCATOR> hash_table_6;
     271            div2_hash_table<8, compare_strategy_t<8>, hash_strategy_t<8>, ALLOCATOR> hash_table_8;
     272            div2_hash_table<10, compare_strategy_t<10>, hash_strategy_t<10>, ALLOCATOR> hash_table_10;
     273            div2_hash_table<12, compare_strategy_t<12>, hash_strategy_t<12>, ALLOCATOR> hash_table_12;
     274            div2_hash_table<14, compare_strategy_t<14>, hash_strategy_t<14>, ALLOCATOR> hash_table_14;
     275            div2_hash_table<16, compare_strategy_t<16>, hash_strategy_t<16>, ALLOCATOR> hash_table_16;
     276        #elif LOG2_STRATEGY
     277            log2_hash_table<1, compare_strategy_t<0>, log_hash_strategy_t<1>, ALLOCATOR> hash_table_1;
     278            log2_hash_table<2, compare_strategy_t<0>, log_hash_strategy_t<2>, ALLOCATOR> hash_table_2;
     279            log2_hash_table<4, compare_strategy_t<0>, log_hash_strategy_t<4>, ALLOCATOR> hash_table_4;
     280            log2_hash_table<8, compare_strategy_t<0>, log_hash_strategy_t<8>, ALLOCATOR> hash_table_8;
     281            log2_hash_table<16, compare_strategy_t<0>, log_hash_strategy_t<16>, ALLOCATOR> hash_table_16;
     282        #else
     283            #error "Length group strategy not specified. #define {ID_STRATEGY,DIV2_STRATEGY,LOG2_STRATEGY}."
     284        #endif
     285
     286        id_hash_table<0, compare_strategy_t<0>, hash_strategy_t<0>, ALLOCATOR> hash_table_gte_17;
    259287};
    260288
  • trunk/symbol_table/test/st_test_file_generator.py

    r1973 r2069  
    77# 1. Output Test File
    88#
    9 #    st_test_UNIFORM_(L_O_U)_(L_O_U)_(L_O_U)_Ag_Mg, where for each (L_O_U),
     9#    L_O_U_L_O_U_L_O_U_Ag_Mg.test, where for each (L_O_U),
    1010
    1111#    * UNIFORM denotes that equal counts of symbols of each length L are generated
     
    2121# 2. Meta Results File
    2222#
    23 #    st_meta_test_UNIFORM_(L_O_U)_(L_O_U)_(L_O_U)_Ag_Mg
     23#    L_O_U_L_O_U_L_O_U_Ag_Mg.meta
    2424#
    2525#    This file contains start position, length and gap distance for each symbol contains in the generated test file, as
     
    4343    testFileHandle = 0   
    4444    def __init__(self,base_filename):   
    45         self.testFileHandle = open("st_test_UNIFORM_"+base_filename, 'w')
     45        self.testFileHandle = open(base_filename+".test", 'w')
    4646       
    4747    def appendUniqueSymbolAndGap(self, symbol_string, gap):   
     
    6161            unique_sym_pos.append([])
    6262
    63         self.logFileHandle = open ("st_meta_test_UNIFORM_"+base_filename, 'w')
     63        self.logFileHandle = open (base_filename+".meta", 'w')
    6464        self.logFileHandle.write("Average Gap Distance: " + str(avg_gap) + "\nMaximum Gap Distance: " + str(max_gap))
    6565
     
    228228        base_filename = ""
    229229        for lst in symbol_specs:
    230             base_filename += "(" + str(lst[0]) + "_" + str(lst[1]) + "_" + str(lst[2]) + ")_"
    231         base_filename += str(arguments[num_args-2]) + "_" + str(arguments[num_args-1])
     230            base_filename += str(lst[0]) + "_" + str(lst[1]) + "_" + str(lst[2])
     231        base_filename += "___" + str(arguments[num_args-2]) + "_" + str(arguments[num_args-1])
    232232
    233233        # calculate total symbol count
Note: See TracChangeset for help on using the changeset viewer.