| 97 | |
| 98 | |
| 99 | __hot StringTable::insertResult StringTable::insert(key_t key, value_t value, hash_t hash) { |
| 100 | assert_precondition(key); |
| 101 | assert_precondition(hash != hash_t::Empty); |
| 102 | |
| 103 | if (_usuallyFalse(_count > _capacity)) |
| 104 | grow(); |
| 105 | |
| 106 | ssize_t distance = 0; |
| 107 | auto maxDistance = _maxDistance; |
| 108 | hash_t curHash = hash; |
| 109 | entry_t curEntry = {key, value}; |
| 110 | entry_t *result = nullptr; |
| 111 | // Walk along the table looking for an empty space: |
| 112 | size_t i; |
| 113 | for (i = indexOfHash(hash); _hashes[i] != hash_t::Empty; i = wrap(i + 1)) { |
| 114 | assert(distance < _count); |
| 115 | if (_hashes[i] == hash && _entries[i].first == key) { |
| 116 | // Found the key in the table already: |
| 117 | if (!result) |
| 118 | return {&_entries[i], false}; // Return existing entry |
| 119 | else |
| 120 | break; |
| 121 | } |
| 122 | ssize_t itsDistance = wrap(i - indexOfHash(_hashes[i]) + _size); |
| 123 | if (itsDistance < distance) { |
| 124 | // Robin Hood hashing: Put new item where a less-distant existing item was: |
| 125 | std::swap(curHash, _hashes[i]); |
| 126 | std::swap(curEntry, _entries[i]); |
| 127 | maxDistance = std::max(distance, maxDistance); |
| 128 | distance = itsDistance; |
| 129 | if (!result) |
| 130 | result = &_entries[i]; |
| 131 | // Then continue, to find a new spot for the existing item we removed... |
| 132 | } |
| 133 | ++distance; |
| 134 | } |
| 135 | |
| 136 | // Now place the final item in the empty space: |
| 137 | _hashes[i] = curHash; |
| 138 | _entries[i] = std::move(curEntry); |
| 139 | _maxDistance = std::max(distance, maxDistance); |
| 140 | ++_count; |
| 141 | |
| 142 | if (!result) |
| 143 | result = &_entries[i]; |
| 144 | return {result, true}; // Return new entry |
| 145 | } |
| 146 | |
| 147 | |
| 148 | __hot void StringTable::insertOnly(key_t key, value_t value, hash_t hash) { |
no test coverage detected