| 580 | |
| 581 | template <bool ignoreNullKeys> |
| 582 | void HashTable<ignoreNullKeys>::groupProbe(HashLookup& lookup) { |
| 583 | incrementProbes(lookup.rows.size()); |
| 584 | |
| 585 | if (hashMode_ == HashMode::kArray) { |
| 586 | arrayGroupProbe(lookup); |
| 587 | return; |
| 588 | } |
| 589 | // Do size-based rehash before mixing hashes from normalized keys |
| 590 | // because the size of the table affects the mixing. |
| 591 | checkSize(lookup.rows.size(), false); |
| 592 | if (hashMode_ == HashMode::kNormalizedKey) { |
| 593 | populateNormalizedKeys(lookup, sizeBits_); |
| 594 | groupNormalizedKeyProbe(lookup); |
| 595 | return; |
| 596 | } |
| 597 | ProbeState state1; |
| 598 | ProbeState state2; |
| 599 | ProbeState state3; |
| 600 | ProbeState state4; |
| 601 | int32_t probeIndex = 0; |
| 602 | int32_t numProbes = lookup.rows.size(); |
| 603 | auto rows = lookup.rows.data(); |
| 604 | for (; probeIndex + 4 <= numProbes; probeIndex += 4) { |
| 605 | int32_t row = rows[probeIndex]; |
| 606 | state1.preProbe(*this, lookup.hashes[row], row); |
| 607 | row = rows[probeIndex + 1]; |
| 608 | state2.preProbe(*this, lookup.hashes[row], row); |
| 609 | row = rows[probeIndex + 2]; |
| 610 | state3.preProbe(*this, lookup.hashes[row], row); |
| 611 | row = rows[probeIndex + 3]; |
| 612 | state4.preProbe(*this, lookup.hashes[row], row); |
| 613 | |
| 614 | state1.firstProbe<ProbeState::Operation::kInsert>(*this, 0); |
| 615 | state2.firstProbe<ProbeState::Operation::kInsert>(*this, 0); |
| 616 | state3.firstProbe<ProbeState::Operation::kInsert>(*this, 0); |
| 617 | state4.firstProbe<ProbeState::Operation::kInsert>(*this, 0); |
| 618 | |
| 619 | fullProbe<false>(lookup, state1, false); |
| 620 | fullProbe<false>(lookup, state2, true); |
| 621 | fullProbe<false>(lookup, state3, true); |
| 622 | fullProbe<false>(lookup, state4, true); |
| 623 | } |
| 624 | for (; probeIndex < numProbes; ++probeIndex) { |
| 625 | int32_t row = rows[probeIndex]; |
| 626 | state1.preProbe(*this, lookup.hashes[row], row); |
| 627 | state1.firstProbe(*this, 0); |
| 628 | fullProbe<false>(lookup, state1, false); |
| 629 | } |
| 630 | } |
| 631 | |
| 632 | template <bool ignoreNullKeys> |
| 633 | void HashTable<ignoreNullKeys>::groupNormalizedKeyProbe(HashLookup& lookup) { |