Do inserts and find group ids for a set of new keys (with possible duplicates within this set).
| 599 | // this set). |
| 600 | // |
| 601 | Status SwissTable::map_new_keys(uint32_t num_ids, uint16_t* ids, const uint32_t* hashes, |
| 602 | uint32_t* group_ids, util::TempVectorStack* temp_stack, |
| 603 | const EqualImpl& equal_impl, |
| 604 | const AppendImpl& append_impl, void* callback_ctx) { |
| 605 | if (num_ids == 0) { |
| 606 | return Status::OK(); |
| 607 | } |
| 608 | |
| 609 | uint16_t max_id = ids[0]; |
| 610 | for (uint32_t i = 1; i < num_ids; ++i) { |
| 611 | max_id = std::max(max_id, ids[i]); |
| 612 | } |
| 613 | |
| 614 | // Temporary buffers have limited size. |
| 615 | // Caller is responsible for splitting larger input arrays into smaller chunks. |
| 616 | ARROW_DCHECK(static_cast<int>(num_ids) <= (1 << log_minibatch_)); |
| 617 | ARROW_DCHECK(static_cast<int>(max_id + 1) <= (1 << log_minibatch_)); |
| 618 | |
| 619 | // Allocate temporary buffers for slot ids and initialize them |
| 620 | auto slot_ids_buf = util::TempVectorHolder<uint32_t>(temp_stack, max_id + 1); |
| 621 | uint32_t* slot_ids = slot_ids_buf.mutable_data(); |
| 622 | init_slot_ids_for_new_keys(num_ids, ids, hashes, slot_ids); |
| 623 | |
| 624 | do { |
| 625 | // A single round of slow-pass (robust) lookup or insert. |
| 626 | // A single round ends with either a single comparison verifying the match |
| 627 | // candidate or inserting a new key. A single round of slow-pass may return early |
| 628 | // if we reach the limit of the number of groups due to inserts of new keys. In |
| 629 | // that case we need to resize and recalculating starting global slot ids for new |
| 630 | // bigger hash table. |
| 631 | bool out_of_capacity; |
| 632 | RETURN_NOT_OK(map_new_keys_helper(hashes, &num_ids, ids, &out_of_capacity, group_ids, |
| 633 | slot_ids, temp_stack, equal_impl, append_impl, |
| 634 | callback_ctx)); |
| 635 | if (out_of_capacity) { |
| 636 | RETURN_NOT_OK(grow_double()); |
| 637 | // Reset start slot ids for still unprocessed input keys. |
| 638 | // |
| 639 | for (uint32_t i = 0; i < num_ids; ++i) { |
| 640 | // First slot in the new starting block |
| 641 | const int16_t id = ids[i]; |
| 642 | uint32_t block_id = block_id_from_hash(hashes[id], log_blocks_); |
| 643 | slot_ids[id] = global_slot_id(block_id, /*local_slot_id=*/0); |
| 644 | } |
| 645 | } |
| 646 | } while (num_ids > 0); |
| 647 | |
| 648 | return Status::OK(); |
| 649 | } |
| 650 | |
| 651 | Status SwissTable::grow_double() { |
| 652 | // Before and after metadata |
no test coverage detected