| 161 | } |
| 162 | |
| 163 | KeyValue* insert_nonexistent_norehash(Key key, Value value) { |
| 164 | assert(should_rehash() == false); |
| 165 | assert(size() < slots.size()); // requires empty slots |
| 166 | assert(cthis()->get_slot(key) == nullptr); |
| 167 | |
| 168 | std::size_t i = key_index(key); |
| 169 | std::size_t hash_offset = 0; |
| 170 | |
| 171 | // first, find an empty (unused) slot |
| 172 | while (slots[i].used) { |
| 173 | i = (i + 1) & mask(); |
| 174 | hash_offset++; |
| 175 | } |
| 176 | |
| 177 | // then, perform the actual insertion. |
| 178 | // this also marks the slot as used. |
| 179 | slots[i] = { std::move(key), std::move(value) }; |
| 180 | assert(slots[i].used); |
| 181 | |
| 182 | // unconditionally increment the size because |
| 183 | // we know that the key didn't exist before. |
| 184 | count++; |
| 185 | |
| 186 | // finally, update maximal length of probe sequences (minus one) |
| 187 | if (hash_offset > max_hash_offset) { |
| 188 | max_hash_offset = hash_offset; |
| 189 | } |
| 190 | |
| 191 | return &slots[i].kv; |
| 192 | } |
| 193 | |
| 194 | void rehash() { |
| 195 | // compute new size. Must be a power of two. |