| 567 | } |
| 568 | |
| 569 | Status HashTable::ResizeBuckets( |
| 570 | int64_t num_buckets, HashTableCtx* __restrict__ ht_ctx, bool* got_memory) { |
| 571 | DCHECK_EQ((num_buckets & (num_buckets - 1)), 0) |
| 572 | << "num_buckets=" << num_buckets << " must be a power of 2"; |
| 573 | DCHECK_GT(num_buckets, num_filled_buckets_) |
| 574 | << "Cannot shrink the hash table to smaller number of buckets than the number of " |
| 575 | << "filled buckets."; |
| 576 | VLOG(2) << "Resizing hash table from " << num_buckets_ << " to " << num_buckets |
| 577 | << " buckets."; |
| 578 | if (max_num_buckets_ != -1 && num_buckets > max_num_buckets_) { |
| 579 | *got_memory = false; |
| 580 | return Status::OK(); |
| 581 | } |
| 582 | ++num_resizes_; |
| 583 | |
| 584 | // All memory that can grow proportional to the input should come from the block mgrs |
| 585 | // mem tracker. |
| 586 | // Note that while we copying over the contents of the old hash table, we need to have |
| 587 | // allocated both the old and the new hash table. Once we finish, we return the memory |
| 588 | // of the old hash table. |
| 589 | // int64_t old_size = num_buckets_ * sizeof(Bucket); |
| 590 | int64_t new_size = num_buckets * sizeof(Bucket); |
| 591 | int64_t new_hash_size = num_buckets * sizeof(uint32_t); |
| 592 | unique_ptr<Suballocation> new_allocation; |
| 593 | unique_ptr<Suballocation> new_hash_allocation; |
| 594 | RETURN_IF_ERROR(allocator_->Allocate(new_size, &new_allocation)); |
| 595 | Status hash_allocation_status = |
| 596 | allocator_->Allocate(new_hash_size, &new_hash_allocation); |
| 597 | if (!hash_allocation_status.ok()) { |
| 598 | if (new_allocation != NULL) allocator_->Free(move(new_allocation)); |
| 599 | return hash_allocation_status; |
| 600 | } |
| 601 | if (new_allocation == NULL || new_hash_allocation == NULL) { |
| 602 | if (new_allocation != NULL) allocator_->Free(move(new_allocation)); |
| 603 | if (new_hash_allocation != NULL) allocator_->Free(move(new_hash_allocation)); |
| 604 | *got_memory = false; |
| 605 | return Status::OK(); |
| 606 | } |
| 607 | Bucket* new_buckets = reinterpret_cast<Bucket*>(new_allocation->data()); |
| 608 | memset(new_buckets, 0, new_size); |
| 609 | uint32_t* new_hash_array = reinterpret_cast<uint32_t*>(new_hash_allocation->data()); |
| 610 | memset(new_hash_array, 0, new_hash_size); |
| 611 | |
| 612 | // Walk the old table and copy all the filled buckets to the new (resized) table. |
| 613 | // We do not have to do anything with the duplicate nodes. This operation is expected |
| 614 | // to succeed. |
| 615 | for (HashTable::Iterator iter = Begin(ht_ctx); !iter.AtEnd(); |
| 616 | NextFilledBucket(&iter.bucket_idx_, &iter.node_)) { |
| 617 | Bucket* bucket_to_copy = &buckets_[iter.bucket_idx_]; |
| 618 | uint32_t hash = hash_array_[iter.bucket_idx_]; |
| 619 | bool found = false; |
| 620 | BucketData bd; |
| 621 | int64_t bucket_idx = Probe<true, false, HashTable::BucketType::MATCH_UNSET>( |
| 622 | new_buckets, new_hash_array, num_buckets, ht_ctx, hash, &found, &bd); |
| 623 | DCHECK(!found); |
| 624 | DCHECK_NE(bucket_idx, Iterator::BUCKET_NOT_FOUND) << " Probe failed even though " |
| 625 | " there are free buckets. " << num_buckets << " " << num_filled_buckets_; |
| 626 | Bucket* dst_bucket = &new_buckets[bucket_idx]; |