| 166 | // below to use an rvalue constructor if available. |
| 167 | template <typename KeyType> |
| 168 | SearchResult FindOrInsert(KeyType&& k) { |
| 169 | size_t h = hash_(k); |
| 170 | const uint32 marker = Marker(h & 0xff); |
| 171 | size_t index = (h >> 8) & mask_; // Holds bucket num and index-in-bucket |
| 172 | uint32 num_probes = 1; // Needed for quadratic probing |
| 173 | Bucket* del = nullptr; // First encountered deletion for kInsert |
| 174 | uint32 di = 0; |
| 175 | while (true) { |
| 176 | uint32 bi = index & (kWidth - 1); |
| 177 | Bucket* b = &array_[index >> kBase]; |
| 178 | const uint32 x = b->marker[bi]; |
| 179 | if (x == marker && equal_(b->key(bi), k)) { |
| 180 | return {true, b, bi}; |
| 181 | } else if (!del && x == kDeleted) { |
| 182 | // Remember deleted index to use for insertion. |
| 183 | del = b; |
| 184 | di = bi; |
| 185 | } else if (x == kEmpty) { |
| 186 | if (del) { |
| 187 | // Store in the first deleted slot we encountered |
| 188 | b = del; |
| 189 | bi = di; |
| 190 | deleted_--; // not_empty_ does not change |
| 191 | } else { |
| 192 | not_empty_++; |
| 193 | } |
| 194 | b->marker[bi] = marker; |
| 195 | new (&b->key(bi)) Key(std::forward<KeyType>(k)); |
| 196 | return {false, b, bi}; |
| 197 | } |
| 198 | index = NextIndex(index, num_probes); |
| 199 | num_probes++; |
| 200 | } |
| 201 | } |
| 202 | |
| 203 | void Erase(Bucket* b, uint32 i) { |
| 204 | b->Destroy(i); |