| 341 | |
| 342 | template <typename Value, typename Key, typename GetKey, typename Hash, typename Equals, typename Allocator> |
| 343 | auto FlatHashTable<Value, Key, GetKey, Hash, Equals, Allocator>::insert(Value value) -> pair<iterator, bool> { |
| 344 | if (m_buckets.empty() || m_filledCount + 1 > (m_buckets.size() - 1) * MaxFillLevel) |
| 345 | checkCapacity(1); |
| 346 | |
| 347 | size_t hash = m_hash(m_getKey(value)) | FilledHashBit; |
| 348 | size_t targetBucket = hashBucket(hash); |
| 349 | size_t currentBucket = targetBucket; |
| 350 | size_t insertedBucket = NPos; |
| 351 | |
| 352 | while (true) { |
| 353 | auto& target = m_buckets[currentBucket]; |
| 354 | if (auto entryValue = target.valuePtr()) { |
| 355 | if (target.hash == hash && m_equals(m_getKey(*entryValue), m_getKey(value))) |
| 356 | return make_pair(iterator{m_buckets.data() + currentBucket}, false); |
| 357 | |
| 358 | size_t entryTargetBucket = hashBucket(target.hash); |
| 359 | size_t entryError = bucketError(currentBucket, entryTargetBucket); |
| 360 | size_t addError = bucketError(currentBucket, targetBucket); |
| 361 | if (addError > entryError) { |
| 362 | if (insertedBucket == NPos) |
| 363 | insertedBucket = currentBucket; |
| 364 | |
| 365 | swap(value, *entryValue); |
| 366 | swap(hash, target.hash); |
| 367 | targetBucket = entryTargetBucket; |
| 368 | } |
| 369 | currentBucket = hashBucket(currentBucket + 1); |
| 370 | |
| 371 | } else { |
| 372 | target.setFilled(hash, std::move(value)); |
| 373 | ++m_filledCount; |
| 374 | if (insertedBucket == NPos) |
| 375 | insertedBucket = currentBucket; |
| 376 | |
| 377 | return make_pair(iterator{m_buckets.data() + insertedBucket}, true); |
| 378 | } |
| 379 | } |
| 380 | } |
| 381 | |
| 382 | template <typename Value, typename Key, typename GetKey, typename Hash, typename Equals, typename Allocator> |
| 383 | auto FlatHashTable<Value, Key, GetKey, Hash, Equals, Allocator>::erase(const_iterator pos) -> iterator { |