| 649 | } |
| 650 | |
| 651 | Status SwissTable::grow_double() { |
| 652 | // Before and after metadata |
| 653 | int num_group_id_bits_before = num_groupid_bits_from_log_blocks(log_blocks_); |
| 654 | int num_group_id_bits_after = num_groupid_bits_from_log_blocks(log_blocks_ + 1); |
| 655 | uint32_t group_id_mask_before = |
| 656 | group_id_mask_from_num_groupid_bits(num_group_id_bits_before); |
| 657 | int log_blocks_after = log_blocks_ + 1; |
| 658 | int bits_shift_for_block_and_stamp_after = |
| 659 | ComputeBitsShiftForBlockAndStamp(log_blocks_after); |
| 660 | int bits_shift_for_block_after = ComputeBitsShiftForBlock(log_blocks_after); |
| 661 | int block_size_before = num_block_bytes_from_num_groupid_bits(num_group_id_bits_before); |
| 662 | int block_size_after = num_block_bytes_from_num_groupid_bits(num_group_id_bits_after); |
| 663 | int64_t block_size_total_after = |
| 664 | num_bytes_total_blocks(block_size_after, log_blocks_after); |
| 665 | int64_t hashes_size_total_after = |
| 666 | (bits_hash_ / 8 * num_slots_from_log_blocks(log_blocks_after)) + padding_; |
| 667 | constexpr uint32_t stamp_mask = (1 << bits_stamp_) - 1; |
| 668 | |
| 669 | // Allocate new buffers |
| 670 | ARROW_ASSIGN_OR_RAISE(std::unique_ptr<Buffer> blocks_new, |
| 671 | AllocateBuffer(block_size_total_after, pool_)); |
| 672 | memset(blocks_new->mutable_data(), 0, block_size_total_after); |
| 673 | ARROW_ASSIGN_OR_RAISE(std::unique_ptr<Buffer> hashes_new_buffer, |
| 674 | AllocateBuffer(hashes_size_total_after, pool_)); |
| 675 | auto hashes_new = reinterpret_cast<uint32_t*>(hashes_new_buffer->mutable_data()); |
| 676 | |
| 677 | // First pass over all old blocks. |
| 678 | // Reinsert entries that were not in the overflow block |
| 679 | // (block other than selected by hash bits corresponding to the entry). |
| 680 | for (int i = 0; i < (1 << log_blocks_); ++i) { |
| 681 | // How many full slots in this block |
| 682 | const uint8_t* block_base = block_data(i, block_size_before); |
| 683 | uint8_t* double_block_base_new = |
| 684 | mutable_block_data(blocks_new->mutable_data(), 2 * i, block_size_after); |
| 685 | uint64_t block = *reinterpret_cast<const uint64_t*>(block_base); |
| 686 | |
| 687 | uint32_t full_slots = std::countl_zero(block & kHighBitOfEachByte) >> 3; |
| 688 | uint32_t full_slots_new[2]; |
| 689 | full_slots_new[0] = full_slots_new[1] = 0; |
| 690 | util::SafeStore(double_block_base_new, kHighBitOfEachByte); |
| 691 | util::SafeStore(double_block_base_new + block_size_after, kHighBitOfEachByte); |
| 692 | |
| 693 | for (uint32_t j = 0; j < full_slots; ++j) { |
| 694 | uint32_t slot_id = global_slot_id(i, j); |
| 695 | uint32_t hash = hashes()[slot_id]; |
| 696 | uint32_t block_id_new = block_id_from_hash(hash, log_blocks_after); |
| 697 | bool is_overflow_entry = ((block_id_new >> 1) != static_cast<uint64_t>(i)); |
| 698 | if (is_overflow_entry) { |
| 699 | continue; |
| 700 | } |
| 701 | |
| 702 | uint32_t ihalf = block_id_new & 1; |
| 703 | uint8_t stamp_new = (hash >> bits_shift_for_block_and_stamp_after) & stamp_mask; |
| 704 | uint32_t group_id = |
| 705 | extract_group_id(block_base, j, num_group_id_bits_before, group_id_mask_before); |
| 706 | uint32_t slot_id_new = global_slot_id(i * 2 + ihalf, full_slots_new[ihalf]); |
| 707 | hashes_new[slot_id_new] = hash; |
| 708 | uint8_t* block_base_new = double_block_base_new + ihalf * block_size_after; |
nothing calls this directly
no test coverage detected