Associates row `hash` with row `ptr`. Returns whether `hash` was already associated with `ptr` Handles any hash conflicts for `hash`.
(&mut self, hash: RowHash, ptr: RowPointer)
| 221 | /// |
| 222 | /// Handles any hash conflicts for `hash`. |
| 223 | pub fn insert(&mut self, hash: RowHash, ptr: RowPointer) -> bool { |
| 224 | let mut was_in_map = false; |
| 225 | |
| 226 | self.map |
| 227 | .entry(hash) |
| 228 | .and_modify(|v| match v.unpack() { |
| 229 | // Already in map; bail for idempotence. |
| 230 | MapSlotRef::Pointer(existing) if *existing == ptr => was_in_map = true, |
| 231 | // Stored inline => colliders list. |
| 232 | MapSlotRef::Pointer(existing) => { |
| 233 | let ptrs = [*existing, ptr].map(ensure_ptr); |
| 234 | let ci = match self.emptied_collider_slots.pop() { |
| 235 | // Allocate a new colliders slot. |
| 236 | None => { |
| 237 | let ci = ColliderSlotIndex::new(self.colliders.len()); |
| 238 | self.colliders.push(ptrs.into()); |
| 239 | ci |
| 240 | } |
| 241 | // Reuse an empty slot. |
| 242 | Some(ci) => { |
| 243 | self.colliders[ci.idx()].extend(ptrs); |
| 244 | ci |
| 245 | } |
| 246 | }; |
| 247 | *v = PtrOrCollider::collider(ci); |
| 248 | } |
| 249 | // Already using a list; add to it. |
| 250 | MapSlotRef::Collider(ci) => { |
| 251 | let ptr = ensure_ptr(ptr); |
| 252 | let colliders = &mut self.colliders[ci.idx()]; |
| 253 | if colliders.contains(&ptr) { |
| 254 | // Already in map; bail for idempotence. |
| 255 | // |
| 256 | // O(n) check, but that's OK, |
| 257 | // as we only regress perf in case we have > 5_000 |
| 258 | // collisions for this `hash`. |
| 259 | // |
| 260 | // Let `n` be the number of bits (`64`) |
| 261 | // and `k` be the number of hashes. |
| 262 | // The average number of collisions, `avg`, |
| 263 | // according to the birthday problem is: |
| 264 | // `avg = 2^(-n) * combinations(k, 2)`. |
| 265 | // (Caveat: our hash function is not truly random.) |
| 266 | // |
| 267 | // Solving for `avg = 5000`, we get `k ≈ 5 * 10^11`. |
| 268 | // That is, we need around half a trillion hashes before, |
| 269 | // on average, getting 5_000 collisions. |
| 270 | // So we can safely ignore this in terms of perf. |
| 271 | return was_in_map = true; |
| 272 | } |
| 273 | colliders.push(ptr); |
| 274 | } |
| 275 | }) |
| 276 | // 0 hashes so far. |
| 277 | .or_insert(PtrOrCollider::ptr(ptr)); |
| 278 | |
| 279 | was_in_map |
| 280 | } |