Changeset 2054 for trunk


Ignore:
Timestamp:
Apr 27, 2012, 2:56:29 AM (7 years ago)
Author:
ksherdy
Message:

Added div2 support wte length greater than or equal to 17.

Location:
trunk/symbol_table
Files:
7 edited
1 moved

Legend:

Unmodified
Added
Removed
  • trunk/symbol_table/Makefile

    r1966 r2054  
    2626HASH_OUTFILE=src/hash_strms.hpp
    2727
    28 IDENTITY_PREFIX=@id_group_strms_
    29 IDENTITY_PABLO_SRC=id_group_strms.py
    30 IDENTITY_TEMPLATE=id_group_strms_template.hpp
    31 IDENTITY_OUTFILE=src/id_group_strms.hpp
     28ID_GROUP_STRMS = id_group_strms.py
     29DIV2_GROUP_STRMS = div2_group_strms.py
     30
     31GROUP_PREFIX=@group_strms_
     32#GROUP_PABLO_SRC= $(ID_GROUP_STRMS)
     33GROUP_PABLO_SRC= $(DIV2_GROUP_STRMS)
     34GROUP_TEMPLATE=group_strms_template.hpp
     35GROUP_OUTFILE=src/group_strms.hpp
    3236
    3337MAIN_TEMPLATE=main_template.cpp
    3438MAIN_OUTFILE=src/main.cpp
    3539
    36 all: marker_strms.py marker_strms_template.hpp hash_strms.py hash_strms_template.hpp id_group_strms.py id_group_strms_template.hpp main_template.cpp
     40all: 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
    3741        python $(PABLO_COMPILER) $(MARKER_PABLO_SRC) -t $(MARKER_TEMPLATE) -l$(MARKER_PREFIX) -o $(MARKER_OUTFILE) $(PABLO_ADD_DEBUG)
    3842        python $(PABLO_COMPILER) $(HASH_PABLO_SRC) -t $(HASH_TEMPLATE) -l$(HASH_PREFIX) -o $(HASH_OUTFILE) $(PABLO_ADD_DEBUG)
    39         python $(PABLO_COMPILER) $(IDENTITY_PABLO_SRC) -t $(IDENTITY_TEMPLATE) -l$(IDENTITY_PREFIX) -o $(IDENTITY_OUTFILE) $(PABLO_ADD_DEBUG)
     43        python $(PABLO_COMPILER) $(GROUP_PABLO_SRC) -t $(GROUP_TEMPLATE) -l$(GROUP_PREFIX) -o $(GROUP_OUTFILE) $(PABLO_ADD_DEBUG)
    4044        python $(PABLO_COMPILER) $(MARKER_PABLO_SRC) -t $(MAIN_TEMPLATE) -l$(MARKER_PREFIX) -o $(MAIN_OUTFILE) $(PABLO_ADD_DEBUG) # @marker_strms_any_carry
    4145
    4246clean:
    43         rm -f $(MARKER_OUTFILE) $(HASH_OUTFILE) $(IDENTITY_OUTFILE) $(MAIN_OUTFILE)
     47        rm -f $(MARKER_OUTFILE) $(HASH_OUTFILE) $(GROUP_OUTFILE) $(MAIN_OUTFILE)
    4448
    4549       
  • trunk/symbol_table/div2_group_strms.py

    r2043 r2054  
    55        starts = 0
    66        ends = 0
    7         ends_1_2 = 0
    8         ends_3_4 = 0
    9         ends_5_6 = 0
    10         ends_7_8 = 0
    11         ends_9_10 = 0
    12         ends_11_12 = 0
    13         ends_13_14 = 0
    14         ends_15_16 = 0
     7        ends_2 = 0
     8        ends_4 = 0
     9        ends_6 = 0
     10        ends_8 = 0
     11        ends_10 = 0
     12        ends_12 = 0
     13        ends_14 = 0
     14        ends_16 = 0
    1515        ends_gte_17 = 0
    1616
     
    2323        # Group symbols of length 1 and length 2
    2424        cursor = pablo.Advance(pablo.Advance(cursor))
    25         groups.ends_1_2 = cursor & shift_or_ends
    26         temp = temp &~ groups.ends_1_2
     25        groups.ends_2 = cursor & shift_or_ends
     26        temp = temp &~ groups.ends_2
    2727
    2828        # Group symbols of length 3 and length 4
    29         cursor = pablo.Advance(pablo.Advance(cursor &~ shift_or_ends))
    30         groups.ends_3_4 = cursor & shift_or_ends
    31         temp = temp &~ groups.ends_3_4
     29        cursor = pablo.Advance(pablo.Advance(cursor &~ shift_or_ends))
     30        groups.ends_4 = cursor & shift_or_ends
     31        temp = temp &~ groups.ends_4
    3232
    3333        # Group symbols of length 5 and length 6
    34         cursor = pablo.Advance(pablo.Advance(cursor &~ shift_or_ends))
    35         groups.ends_5_6 = cursor & shift_or_ends
    36         temp = temp &~ groups.ends_5_6
     34        cursor = pablo.Advance(pablo.Advance(cursor &~ shift_or_ends))
     35        groups.ends_6 = cursor & shift_or_ends
     36        temp = temp &~ groups.ends_6
    3737
    3838        # Group symbols of length 7 and length 8
    39         cursor = pablo.Advance(pablo.Advance(cursor &~ shift_or_ends))
    40         groups.ends_7_8 = cursor & shift_or_ends
    41         temp = temp &~ groups.ends_7_8
     39        cursor = pablo.Advance(pablo.Advance(cursor &~ shift_or_ends))
     40        groups.ends_8 = cursor & shift_or_ends
     41        temp = temp &~ groups.ends_8
    4242
    4343        # Group symbols of length 9 and length 10
    44         cursor = pablo.Advance(pablo.Advance(cursor &~ shift_or_ends))
    45         groups.ends_9_10 = cursor & shift_or_ends
    46         temp = temp &~ groups.ends_9_10
     44        cursor = pablo.Advance(pablo.Advance(cursor &~ shift_or_ends))
     45        groups.ends_10 = cursor & shift_or_ends
     46        temp = temp &~ groups.ends_10
    4747
    4848        # Group symbols of length 11 and length 12
    49         cursor = pablo.Advance(pablo.Advance(cursor &~ shift_or_ends))
    50         groups.ends_11_12 = cursor & shift_or_ends
    51         temp = temp &~ groups.ends_11_12
     49        cursor = pablo.Advance(pablo.Advance(cursor &~ shift_or_ends))
     50        groups.ends_12 = cursor & shift_or_ends
     51        temp = temp &~ groups.ends_12
    5252
    5353        # Group symbols of length 13 and length 14
    54         cursor = pablo.Advance(pablo.Advance(cursor &~ shift_or_ends))
    55         groups.ends_13_14 = cursor & shift_or_ends
    56         temp = temp &~ groups.ends_13_14
     54        cursor = pablo.Advance(pablo.Advance(cursor &~ shift_or_ends))
     55        groups.ends_14 = cursor & shift_or_ends
     56        temp = temp &~ groups.ends_14
    5757
    5858        # Group symbols of length 15 and length 16
    59         cursor = pablo.Advance(pablo.Advance(cursor &~ shift_or_ends))
    60         groups.ends_15_16 = cursor & shift_or_ends
    61         temp = temp &~ groups.ends_15_16
     59        cursor = pablo.Advance(pablo.Advance(cursor &~ shift_or_ends))
     60        groups.ends_16 = cursor & shift_or_ends
     61        temp = temp &~ groups.ends_16
    6262
    6363        # Group symbols of length greater than equal to 17
  • trunk/symbol_table/group_strms_template.hpp

    r2048 r2054  
    1 #ifndef ID_GROUP_STRMS_TEMPLATE_HPP
    2 #define ID_GROUP_STRMS_TEMPLATE_HPP
     1#ifndef GROUP_STRMS_TEMPLATE_HPP
     2#define GROUP_STRMS_TEMPLATE_HPP
    33
    44#include "../lib/bitblock.hpp"
     
    66
    77// GENERATED
    8 @id_group_strms_global
     8@group_strms_global
    99// GENERATED
    10 @id_group_strms_stream_stmts
     10@group_strms_stream_stmts
    1111
    1212static IDISA_ALWAYS_INLINE void identity_group_do_block(Markers & markers, Groups & groups) {
     
    1414        groups.ends = markers.ends;
    1515        // GENERATED
    16         @id_group_strms_block_stmts
     16        @group_strms_block_stmts
    1717}
    1818
     
    2121        groups.ends = markers.ends;
    2222        // GENERATED
    23         @id_group_strms_final_block_stmts
     23        @group_strms_final_block_stmts
    2424}
    2525
  • trunk/symbol_table/main_template.cpp

    r2053 r2054  
    3939#include "marker_strms.hpp"     // GENERATED HEADER
    4040#include "hash_strms.hpp"       // GENERATED HEADER
    41 #include "id_group_strms.hpp"   // GENERATED HEADER
     41#include "group_strms.hpp"      // GENERATED HEADER
    4242#include "symbol_table.hpp"
    4343#include <string>
  • trunk/symbol_table/src/Makefile

    r2052 r2054  
    1515TEST_ROOT=../test
    1616
    17 all: basis_bits.hpp buffer.hpp byte_pool.hpp  hash_strms.hpp  hash_table.hpp  id_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
     17all: 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
    1919
    2020test: main
  • trunk/symbol_table/src/hash_table.hpp

    r2053 r2054  
    5151public:
    5252
     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:
     115
    53116    hash_table(const uint32_t table_size=1024, const uint32_t resize_chain_lgth=2) {
    54117        #ifdef HASH_TABLE_HPP_DEBUG
     
    65128    }
    66129
    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 gid_type lookup_or_insert(uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
    93 //                                                uint8_t * h0, uint8_t * h1, const uint32_t hash_bit_lgth,
    94 //                                                      GIDFactory & gid_factory, GIDData & gid_data);
    95 
     130    ///////////////////////////////////////////////////////////////////////////
     131    // Helpers
     132    ///////////////////////////////////////////////////////////////////////////
     133    uint32_t log2msb(uint32_t v) {
     134        uint32_t r = 0;
     135        while (v >>= 1) {r++;}
     136        return r;
     137    }
     138
     139    void init(const uint32_t size, const uint32_t chain_lgth) {
     140
     141        hash_size = MIN((log2msb(size)), hash_strategy.max_hashsize());
     142        table_size = pow(2.0, (double)hash_size);
     143        table = (node**) calloc(table_size, sizeof(node*));
     144
     145        if ((table) == NULL) {
     146                cerr << "Out of Memory" << endl;
     147                abort();
     148        }
     149        resize_chain_lgth = chain_lgth;
     150    }
     151
     152    void destroy_table(node ** table, const uint32_t table_size) {
     153        node * crt = NULL;
     154        node * next = NULL;
     155
     156        for(int i=0;i<table_size;i++) {
     157            crt = table[i];
     158            while(crt != NULL) {
     159                next = crt->next;
     160                free((node  *)crt);
     161                crt = next;
     162            }
     163        }
     164
     165        free((node **) table);
     166        table = NULL;
     167    }
     168
     169    uint32_t chain_lgth(const node * chain) {
     170        uint32_t lgth = 0;
     171        node * crt = (node *)chain;
     172        while(NULL != crt) {
     173            lgth++;
     174            crt = crt->next;
     175        }
     176
     177        return lgth;
     178    }
     179
     180    bool expansion_test(const node * chain) {
     181
     182        if ((chain_lgth(chain) > resize_chain_lgth)
     183                &&  (hash_size < hash_strategy.max_hashsize())
     184                &&  (table_size < MAX_TABLE_SIZE))
     185        {
     186            return true;
     187        }
     188
     189        return false;
     190    }
     191
     192    void expand() { // naive expansion
     193
     194        node ** prev_table = this->table;
     195        uint32_t prev_size = this->table_size;
     196
     197        init(table_size*2, resize_chain_lgth);
     198
     199        uint64_t bucket;
     200        node * crt;
     201
     202        for(int i=0;i<prev_size;i++) {
     203            crt = prev_table[i];
     204
     205            while(crt != NULL) {
     206
     207
     208                bucket = this->get_bucket(crt->h0,
     209                                          crt->h1,
     210                                          0);
     211                this->insert(bucket,
     212                             crt->raw_bytes,
     213                             crt->raw_bytes_lgth,
     214                             crt->h0,
     215                             crt->h1,
     216                             crt->gid);
     217
     218                crt = crt->next;
     219            }
     220        }
     221
     222        destroy_table(prev_table,prev_size);
     223        crt = NULL;
     224
     225        for(int i=0;i<table_size;i++) {
     226            if(expansion_test(table[i])) {
     227                expand();
     228            }
     229        }
     230    }
     231
     232    ///////////////////////////////////////////////////////////////////////////
     233    // Members
     234    ///////////////////////////////////////////////////////////////////////////
     235    uint32_t table_size;            // power of 2
     236    uint32_t hash_size;             // maximum number of bits hashed on
     237    uint32_t resize_chain_lgth;     // maximum chain length
     238
     239    node ** table;
     240    byte_pool<ALLOCATOR> raw_data_pool;
     241    compare_strategy_t<LGTH> compare_strategy;
     242    hash_strategy_t<LGTH> hash_strategy;
     243
     244    ///////////////////////////////////////////////////////////////////////////
     245    // Debug / Diagnostics
     246    ///////////////////////////////////////////////////////////////////////////
    96247    void print_table() const {
    97248
     
    120271    }
    121272
     273    void print_table_distribution() const {
     274
     275        for(int i=0;i<table_size;i++) {
     276
     277            node * head = table[i];
     278            node * crt = head;
     279
     280            if(head != NULL) { cout << "table[" << i << "]"; }
     281
     282            while(crt != NULL) {
     283                cout << "X";
     284                crt = crt->next;
     285            }
     286
     287            if(head != NULL) { cout << endl; }
     288        }
     289    }
     290
     291    ///////////////////////////////////////////////////////////////////////////
     292    // Debug Members
     293    ///////////////////////////////////////////////////////////////////////////
     294    #ifdef HASH_TABLE_HPP_DEBUG
     295        uint32_t lookups;
     296        uint32_t elements;
     297        uint32_t collisions;
     298        uint32_t table_expansions;
     299    #endif
    122300
    123301    void print_diagnostics() const {
     
    134312        #endif
    135313    }
    136 
    137 
    138     void print_table_distribution() const {
    139 
    140         for(int i=0;i<table_size;i++) {
    141 
    142             node * head = table[i];
    143             node * crt = head;
    144 
    145             if(head != NULL) { cout << "table[" << i << "]"; }
    146 
    147             while(crt != NULL) {
    148                 cout << "X";
    149                 crt = crt->next;
    150             }
    151 
    152             if(head != NULL) { cout << endl; }
    153         }
    154     }
    155 
    156 protected:
    157     // ----- Members -----
    158     uint32_t table_size;            // power of 2
    159     uint32_t hash_size;             // maximum number of bits hashed on
    160     uint32_t resize_chain_lgth;     // maximum chain length
    161 
    162     node ** table;
    163     // uint32_t elements;
    164     byte_pool<ALLOCATOR> raw_data_pool;
    165     compare_strategy_t<LGTH> compare_strategy;
    166     hash_strategy_t<LGTH> hash_strategy;
    167 
    168     // ----- Diagnostics -----
    169     #ifdef HASH_TABLE_HPP_DEBUG
    170         uint32_t lookups;
    171         uint32_t elements;
    172         uint32_t collisions;
    173         uint32_t table_expansions;
    174     #endif
    175 
    176     // ----- Helpers -----
    177     uint32_t log2msb(uint32_t v) {
    178         uint32_t r = 0;
    179         while (v >>= 1) {r++;}
    180         return r;
    181     }
    182 
    183     void init(const uint32_t size, const uint32_t chain_lgth) {
    184 
    185         hash_size = MIN((log2msb(size)), hash_strategy.max_hashsize());
    186         table_size = pow(2.0, (double)hash_size);
    187         table = (node**) calloc(table_size, sizeof(node*));
    188 
    189         if ((table) == NULL) {
    190                 cerr << "Out of Memory" << endl;
    191                 abort();
    192         }
    193         resize_chain_lgth = chain_lgth;
    194     }
    195 
    196     void destroy_table(node ** table, const uint32_t table_size) {
    197         node * crt = NULL;
    198         node * next = NULL;
    199 
    200         for(int i=0;i<table_size;i++) {
    201             crt = table[i];
    202             while(crt != NULL) {
    203                 next = crt->next;
    204                 free((node  *)crt);
    205                 crt = next;
    206             }
    207         }
    208 
    209         free((node **) table);
    210         table = NULL;
    211     }
    212 
    213     uint32_t chain_lgth(const node * chain) {
    214         uint32_t lgth = 0;
    215         node * crt = (node *)chain;
    216         while(NULL != crt) {
    217             lgth++;
    218             crt = crt->next;
    219         }
    220 
    221         return lgth;
    222     }
    223 
    224     bool expansion_test(const node * chain) {
    225 
    226         if ((chain_lgth(chain) > resize_chain_lgth)
    227                 &&  (hash_size < hash_strategy.max_hashsize())
    228                 &&  (table_size < MAX_TABLE_SIZE))
    229         {
    230             return true;
    231         }
    232 
    233         return false;
    234     }
    235 
    236     void expand() { // naive expansion
    237 
    238         node ** prev_table = this->table;
    239         uint32_t prev_size = this->table_size;
    240 
    241         init(table_size*2, resize_chain_lgth);
    242 
    243         uint64_t bucket;
    244         node * crt;
    245 
    246         for(int i=0;i<prev_size;i++) {
    247             crt = prev_table[i];
    248 
    249             while(crt != NULL) {
    250 
    251 
    252                 bucket = this->get_bucket(crt->h0,
    253                                           crt->h1,
    254                                           0);
    255                 this->insert(bucket,
    256                              crt->raw_bytes,
    257                              crt->raw_bytes_lgth,
    258                              crt->h0,
    259                              crt->h1,
    260                              crt->gid);
    261 
    262                 crt = crt->next;
    263             }
    264         }
    265 
    266         destroy_table(prev_table,prev_size);
    267         crt = NULL;
    268 
    269         for(int i=0;i<table_size;i++) {
    270             if(expansion_test(table[i])) {
    271                 expand();
    272             }
    273         }
    274     }
    275314};
    276315
     
    279318
    280319public:
     320
     321    IDISA_ALWAYS_INLINE gid_type lookup(uint64_t bucket, uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
     322                                        uint8_t * h0, uint8_t * h1, gid_type & gid) {
     323
     324        node * crt = this->table[bucket];
     325        node * prev = crt;
     326
     327        while(NULL != crt) {
     328            if(this->compare_strategy.compare(&raw_bytes[idx], crt->raw_bytes, raw_byte_lgth)) {
     329                                gid = crt->gid;
     330                                return true;
     331            }
     332            prev = crt;
     333            crt = crt->next;
     334            #ifdef HASH_TABLE_HPP_DEBUG
     335                collisions++;
     336            #endif
     337        }
     338
     339        return false;
     340    }
    281341
    282342    IDISA_ALWAYS_INLINE gid_type lookup_or_insert(uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
     
    284344                                                  GIDFactory & gid_factory, GIDData & gid_data) {
    285345
    286         /* lookup */ // returns gid
     346        gid_type gid;
    287347        uint64_t bucket = this->get_bucket(h0,h1,idx);
     348
     349        if(lookup(bucket, raw_bytes, idx, raw_byte_lgth, h0, h1, gid)) {
     350            return gid;
     351        }
     352
     353        this->pool_and_insert(bucket, raw_bytes, idx, raw_byte_lgth, h0, h1, gid_factory, gid_data, gid);
     354        return gid;
     355
     356    }
     357
     358};
     359
     360template<uint32_t LGTH, class ALLOCATOR>
     361class div2_hash_table : public hash_table<LGTH, ALLOCATOR> {
     362
     363public:
     364
     365    IDISA_ALWAYS_INLINE gid_type lookup(uint64_t bucket, uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
     366                                        uint8_t * h0, uint8_t * h1, gid_type & gid) {
    288367
    289368        node * crt = this->table[bucket];
     
    292371        while(NULL != crt) {
    293372            if(this->compare_strategy.compare(&raw_bytes[idx], crt->raw_bytes, raw_byte_lgth)) {
    294                                 return crt->gid;
     373                                gid = crt->gid;
     374                                return true;
    295375            }
    296376            prev = crt;
    297377            crt = crt->next;
    298378            #ifdef HASH_TABLE_HPP_DEBUG
    299                                 collisions++;
     379                collisions++;
    300380            #endif
    301381        }
    302382
    303         gid_type gid = gid_factory.next();
    304         uint64_t x0 = bit_slice(h0, idx, 1); // get pointer to bit position, TODO opt for bit/byte variants
    305         uint64_t x1 = bit_slice(h1, idx, 1);
    306         uint8_t * data_pool_raw_bytes = this->raw_data_pool.insert(&raw_bytes[idx],raw_byte_lgth); // persist
    307 
    308         /* insert */
    309         insert( bucket,
    310                 data_pool_raw_bytes,
    311                 raw_byte_lgth,
    312                 this->raw_data_pool.insert((uint8_t *)&x0, bits2bytes(this->hash_strategy.max_hashsize())), // TODO opt for bit/byte variants
    313                 this->raw_data_pool.insert((uint8_t *)&x1, bits2bytes(this->hash_strategy.max_hashsize())),
    314                 gid);
    315 
    316         if(this->expansion_test(this->table[bucket])) {
    317 
    318             #ifdef HASH_TABLE_HPP_DEBUG
    319                 this->table_expansions++;
    320             #endif
    321 
    322             this->expand();
    323         }
    324 
    325         #ifdef HASH_TABLE_HPP_DEBUG
    326             elements++;
    327         #endif
    328 
    329         gid_data.add_data(data_pool_raw_bytes,raw_byte_lgth);
    330 
    331         return gid;
    332     }
    333 
    334 };
    335 
    336 template<uint32_t LGTH, class ALLOCATOR>
    337 class div2_hash_table : public hash_table<LGTH, ALLOCATOR> {
    338 
    339 public:
    340 
    341 
    342 
    343 
     383        return false;
     384    }
     385
     386    IDISA_ALWAYS_INLINE gid_type lookup_or_insert(uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
     387                                                  uint8_t * h0, uint8_t * h1,
     388                                                  GIDFactory & gid_factory, GIDData & gid_data) {
     389
     390        gid_type gid;
     391        uint64_t bucket = this->get_bucket(h0,h1,idx);
     392        uint32_t lgth = raw_byte_lgth;
     393
     394        uint32_t index_of_last = idx + lgth - 1;
     395
     396        ///////////////////////////////////////////////////////////////////////////
     397        // Even
     398        ///////////////////////////////////////////////////////////////////////////
     399/*      if (!div2_hash_table::is_delimeter(raw_bytes, index_of_last)) {
     400
     401            if(lookup(bucket, raw_bytes, idx, lgth, h0, h1, gid)) {
     402                return gid;
     403            }
     404
     405            this->pool_and_insert(bucket, raw_bytes, idx, lgth, h0, h1, gid_factory, gid_data, gid);
     406            return gid;
     407
     408        } else*/ {
     409
     410        ///////////////////////////////////////////////////////////////////////////
     411        // Odd
     412        ///////////////////////////////////////////////////////////////////////////
     413            ///lgth--;
     414
     415            if(this->hash_table_odd.lookup(bucket, raw_bytes, idx, lgth-1, h0, h1, gid)) {
     416                return gid;
     417            }
     418
     419            hash_table_odd.pool_and_insert(bucket, raw_bytes, idx, lgth-1, h0, h1, gid_factory, gid_data, gid);
     420            return gid;
     421        }
     422
     423    }
     424
     425protected:
     426
     427    // TODO - Compile in delimeter set.
     428    static IDISA_ALWAYS_INLINE bool is_delimeter(uint8_t * raw_bytes, const uint32_t idx) {
     429        bool has_delim = *(raw_bytes + idx) == ',';
     430        return has_delim;
     431    }
     432
     433    id_hash_table<LGTH-1, ALLOCATOR> hash_table_odd;
    344434};
    345435
  • trunk/symbol_table/src/symbol_table.hpp

    r2053 r2054  
    9999//      hash_table_gte_17.print_table();
    100100#ifdef HASH_TABLE_HPP_DEBUG
    101         hash_table_1.print_diagnostics();
    102         hash_table_2.print_diagnostics();
    103         hash_table_3.print_diagnostics();
    104         hash_table_4.print_diagnostics();
    105         hash_table_5.print_diagnostics();
    106         hash_table_6.print_diagnostics();
    107         hash_table_7.print_diagnostics();
    108         hash_table_8.print_diagnostics();
    109         hash_table_9.print_diagnostics();
    110         hash_table_10.print_diagnostics();
    111         hash_table_11.print_diagnostics();
    112         hash_table_12.print_diagnostics();
    113         hash_table_13.print_diagnostics();
    114         hash_table_14.print_diagnostics();
    115         hash_table_15.print_diagnostics();
    116         hash_table_16.print_diagnostics();
    117         hash_table_gte_17.print_diagnostics();
     101//      hash_table_1.print_diagnostics();
     102//      hash_table_2.print_diagnostics();
     103//      hash_table_3.print_diagnostics();
     104//      hash_table_4.print_diagnostics();
     105//      hash_table_5.print_diagnostics();
     106//      hash_table_6.print_diagnostics();
     107//      hash_table_7.print_diagnostics();
     108//      hash_table_8.print_diagnostics();
     109//      hash_table_9.print_diagnostics();
     110//      hash_table_10.print_diagnostics();
     111//      hash_table_11.print_diagnostics();
     112//      hash_table_12.print_diagnostics();
     113//      hash_table_13.print_diagnostics();
     114//      hash_table_14.print_diagnostics();
     115//      hash_table_15.print_diagnostics();
     116//      hash_table_16.print_diagnostics();
     117//      hash_table_gte_17.print_diagnostics();
    118118#endif
    119119        }
     
    137137                        // Byte Space Hash
    138138                        ///////////////////////////////////////////////////////////////////////////////
    139                         #define BYTE_HASH(LGTH) \
     139                        #define BYTE_HASH(GROUP, LGTH) \
    140140                                if(bitblock::any(groups.ends_##LGTH)) { \
    141                                         do_block<SYMBOL, id_hash_table <LGTH, ALLOCATOR> > \
     141                                        do_block<SYMBOL, GROUP##_hash_table <LGTH, ALLOCATOR> > \
    142142                                                (blk_offset, \
    143143                                                 hash_table_##LGTH, \
     
    148148                                }
    149149
    150                                                 BYTE_HASH(1);
    151                                                 BYTE_HASH(2);
    152                                                 BYTE_HASH(3);
    153                                                 BYTE_HASH(4);
    154                                                 BYTE_HASH(5);
    155                                                 BYTE_HASH(6);
    156                                                 BYTE_HASH(7);
     150                                //BYTE_HASH(id,1);
     151                                BYTE_HASH(div2,2);
     152//                              //BYTE_HASH(id,3);
     153                                BYTE_HASH(div2,4);
     154                                //BYTE_HASH(id,5);
     155                                BYTE_HASH(div2,6);
     156                                //BYTE_HASH(id,7);
     157
    157158                        #undef BYTE_HASH
    158159
     
    160161                        // Bit Space Hash
    161162                        ///////////////////////////////////////////////////////////////////////////////
    162                         #define BIT_HASH(LGTH) \
     163                        #define BIT_HASH(GROUP, LGTH) \
    163164                                if(bitblock::any(groups.ends_##LGTH)) { \
    164                                         do_block<SYMBOL, id_hash_table <LGTH, ALLOCATOR> > \
     165                                        do_block<SYMBOL, GROUP##_hash_table <LGTH, ALLOCATOR> > \
    165166                                                (blk_offset, \
    166167                                                 hash_table_##LGTH, \
     
    171172                                }
    172173
    173                         BIT_HASH(8);
    174                         BIT_HASH(9);
    175                         BIT_HASH(10);
    176                         BIT_HASH(11);
    177                         BIT_HASH(12);
    178                         BIT_HASH(13);
    179                         BIT_HASH(14);
    180                         BIT_HASH(15);
    181                         BIT_HASH(16);
     174                                BIT_HASH(div2,8);
     175//                              //BIT_HASH(9);
     176                                BIT_HASH(div2,10);
     177//                              //BIT_HASH(11);
     178                                BIT_HASH(div2,12);
     179//                              //BIT_HASH(13);
     180                                BIT_HASH(div2,14);
     181//                              //BIT_HASH(15);
     182                                BIT_HASH(div2,16);
    182183
    183184                        #undef BIT_HASH
    184185
    185186                        if(bitblock::any(groups.ends_gte_17)) {
     187
     188                                print_register("17", groups.ends_gte_17);
     189
    186190                                do_block<SYMBOL, id_hash_table<0, ALLOCATOR> >
    187191                                                (blk_offset,
     
    205209        // Byte Space Hash
    206210        ///////////////////////////////////////////////////////////////////////////////
    207         id_hash_table<1, ALLOCATOR> hash_table_1;
    208         id_hash_table<2, ALLOCATOR> hash_table_2;
    209         id_hash_table<3, ALLOCATOR> hash_table_3;
    210         id_hash_table<4, ALLOCATOR> hash_table_4;
    211         id_hash_table<5, ALLOCATOR> hash_table_5;
    212         id_hash_table<6, ALLOCATOR> hash_table_6;
    213         id_hash_table<7, ALLOCATOR> hash_table_7;
    214 //      ///////////////////////////////////////////////////////////////////////////////
    215 //      // Bit Space Hash
    216 //      ///////////////////////////////////////////////////////////////////////////////
    217         id_hash_table<8, ALLOCATOR> hash_table_8;
    218         id_hash_table<9, ALLOCATOR> hash_table_9;
    219         id_hash_table<10, ALLOCATOR> hash_table_10;
    220         id_hash_table<11, ALLOCATOR> hash_table_11;
    221         id_hash_table<12, ALLOCATOR> hash_table_12;
    222         id_hash_table<13, ALLOCATOR> hash_table_13;
    223         id_hash_table<14, ALLOCATOR> hash_table_14;
    224         id_hash_table<15, ALLOCATOR> hash_table_15;
    225         id_hash_table<16, ALLOCATOR> hash_table_16;
     211//      div2_hash_table<2, ALLOCATOR> hash_table_1_2;
     212
     213//      id_hash_table<1, ALLOCATOR> hash_table_1;
     214//      id_hash_table<2, ALLOCATOR> hash_table_2;
     215//      id_hash_table<3, ALLOCATOR> hash_table_3;
     216//      id_hash_table<4, ALLOCATOR> hash_table_4;
     217//      id_hash_table<5, ALLOCATOR> hash_table_5;
     218//      id_hash_table<6, ALLOCATOR> hash_table_6;
     219//      id_hash_table<7, ALLOCATOR> hash_table_7;
     220
     221        div2_hash_table<2, ALLOCATOR> hash_table_2;
     222        div2_hash_table<4, ALLOCATOR> hash_table_4;
     223        div2_hash_table<6, ALLOCATOR> hash_table_6;
     224
     225        ///////////////////////////////////////////////////////////////////////////////
     226        // Bit Space Hash
     227        ///////////////////////////////////////////////////////////////////////////////
     228//      id_hash_table<8, ALLOCATOR> hash_table_8;
     229//      id_hash_table<9, ALLOCATOR> hash_table_9;
     230//      id_hash_table<10, ALLOCATOR> hash_table_10;
     231//      id_hash_table<11, ALLOCATOR> hash_table_11;
     232//      id_hash_table<12, ALLOCATOR> hash_table_12;
     233//      id_hash_table<13, ALLOCATOR> hash_table_13;
     234//      id_hash_table<14, ALLOCATOR> hash_table_14;
     235//      id_hash_table<15, ALLOCATOR> hash_table_15;
     236//      id_hash_table<16, ALLOCATOR> hash_table_16;
     237//      id_hash_table<0, ALLOCATOR> hash_table_gte_17;
     238
     239        div2_hash_table<8, ALLOCATOR> hash_table_8;
     240//      id_hash_table<9, ALLOCATOR> hash_table_9;
     241        div2_hash_table<10, ALLOCATOR> hash_table_10;
     242//      id_hash_table<11, ALLOCATOR> hash_table_11;
     243        div2_hash_table<12, ALLOCATOR> hash_table_12;
     244//      id_hash_table<13, ALLOCATOR> hash_table_13;
     245        div2_hash_table<14, ALLOCATOR> hash_table_14;
     246//      id_hash_table<15, ALLOCATOR> hash_table_15;
     247        div2_hash_table<16, ALLOCATOR> hash_table_16;
    226248        id_hash_table<0, ALLOCATOR> hash_table_gte_17;
    227249};
     
    275297
    276298                        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
    277                                 print_symbol_debug(gid, buffer_base, spos, epos, lgth);
     299                                print_symbol_debug(gid, buffer_base, spos, epos, gid_data.get_bytes_lgth(gid));
    278300                        #endif
    279301
    280302                        rscanner.scan_to_next();
    281                 epos = rscanner.get_pos();
     303                        epos = rscanner.get_pos();
    282304                }
    283305        }
     
    328350                        if(!starts_rscanner.is_done()) { // found start
    329351                                        lgth = epos + (BLOCK_SIZE - starts_rscanner.get_pos()) + (BLOCK_SIZE * (blk_count-1));
    330                                         // spos = (BLOCK_SIZE - (-1 * spos)) & (BLOCK_SIZE - 1);
    331 
    332                                         // buffer_base -= (BLOCK_SIZE * blk_count);
    333                                         //spos = epos - lgth;
    334352                                        spos = starts_rscanner.get_pos();
    335 
    336353                                        buffer_base -= (BLOCK_SIZE * blk_count);
    337354                                        h0_base -= (h_block_size * blk_count);
  • trunk/symbol_table/symbol_table.pro

    r2053 r2054  
    5454    marker_strms.hpp \
    5555    markers.hpp \
    56     id_group_strms_template.hpp \
    5756    id_group_strms.hpp \
    5857    hash_strms_template.hpp \
     
    6362    src/transpose.hpp \
    6463    src/marker_strms.hpp \
    65     src/id_group_strms.hpp \
    6664    src/hash_table.hpp \
    6765    src/hash_strms.hpp \
     
    7876    src/symbol_table.hpp \
    7977    src/compare_strategy.hpp \
    80     src/hash_strategy.hpp
     78    src/hash_strategy.hpp \
     79    group_strms_template.hpp \
     80    src/group_strms.hpp
Note: See TracChangeset for help on using the changeset viewer.