Logo Search packages:      
Sourcecode: maqview version File versions  Download package

template<class keytype_t>
bool __lh3_hash_base_class< keytype_t >::resize ( hashint_t  new_capacity ) [inline, inherited]

resize the hash table and perform rehashing

Reimplemented in hash_map_misc< keytype_t, valtype_t >, and hash_map_char< valtype_t >.

Definition at line 345 of file stdhash.hh.

Referenced by __lh3_hash_base_class< char * >::rehash().

                                                 {
            __lh3_flag_t *new_flags;
            if (!resize_aux1(&new_capacity, &new_flags)) return false;
            for (hashint_t j = 0; j != n_capacity; ++j) {
                  if (__lh3_isboth(flags, j) == 0) {
                        keytype_t key = keys[j]; // take out the key
                        __lh3_set_isdel_true(flags, j); // mark "deleted"
                        while (1) {
                              hashint_t inc, k, i;
                              k = __lh3_hash_fun(key);
                              i = k % new_capacity; // calculate the new position
                              inc = 1 + k % (new_capacity - 1);
                              while (!__lh3_isempty(new_flags, i)) {
                                    if (i + inc >= new_capacity) i = i + inc - new_capacity;
                                    else i += inc;
                              }
                              __lh3_set_isempty_false(new_flags, i);
                              if (i < this->n_capacity && __lh3_isboth(flags, i) == 0) { // something is here
                                    { keytype_t tmp = keys[i]; keys[i] = key; key = tmp; } // take it out
                                    __lh3_set_isdel_true(flags, i);
                              } else { // put key and quit the loop
                                    keys[i] = key;
                                    break;
                              }
                        }
                  }
            }
            resize_aux2(new_capacity, new_flags);
            return true;
      }

Here is the caller graph for this function:


Generated by  Doxygen 1.6.0   Back to index