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.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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
Note: See TracChangeset for help on using the changeset viewer.