| 49 | |
| 50 | template <bool INCLUSIVE_EQUALITY, bool COMPARE_ROW, HashTable::BucketType TYPE> |
| 51 | inline int64_t HashTable::Probe(Bucket* buckets, uint32_t* hash_array, |
| 52 | int64_t num_buckets, HashTableCtx* __restrict__ ht_ctx, uint32_t hash, bool* found, |
| 53 | BucketData* bd) { |
| 54 | DCHECK(ht_ctx != nullptr); |
| 55 | DCHECK(buckets != nullptr); |
| 56 | DCHECK_GT(num_buckets, 0); |
| 57 | *found = false; |
| 58 | ++ht_ctx->num_probes_; |
| 59 | int64_t bucket_idx = hash & (num_buckets - 1); |
| 60 | |
| 61 | // In case of linear probing it counts the total number of steps for statistics and |
| 62 | // for knowing when to exit the loop (e.g. by capping the total travel length). In case |
| 63 | // of quadratic probing it is also used for calculating the length of the next jump. |
| 64 | int64_t step = 0; |
| 65 | do { |
| 66 | Bucket* bucket = &buckets[bucket_idx]; |
| 67 | if (LIKELY(!bucket->IsFilled())) return bucket_idx; |
| 68 | if (hash == hash_array[bucket_idx]) { |
| 69 | if (COMPARE_ROW |
| 70 | && ht_ctx->Equals<INCLUSIVE_EQUALITY>( |
| 71 | GetRow<TYPE>(bucket, ht_ctx->scratch_row_, bd))) { |
| 72 | *found = true; |
| 73 | return bucket_idx; |
| 74 | } |
| 75 | // Row equality failed, or not performed. This is a hash collision. Continue |
| 76 | // searching. |
| 77 | ++ht_ctx->num_hash_collisions_; |
| 78 | } |
| 79 | // Move to the next bucket. |
| 80 | ++step; |
| 81 | if (quadratic_probing()) { |
| 82 | // The i-th probe location is idx = (hash + (step * (step + 1)) / 2) mod |
| 83 | // num_buckets. This gives num_buckets unique idxs (between 0 and N-1) when |
| 84 | // num_buckets is a power of 2. |
| 85 | bucket_idx = (bucket_idx + step) & (num_buckets - 1); |
| 86 | } else { |
| 87 | // Linear probing |
| 88 | bucket_idx = (bucket_idx + 1) & (num_buckets - 1); |
| 89 | } |
| 90 | } while (LIKELY(step < num_buckets)); |
| 91 | |
| 92 | ht_ctx->travel_length_ += step; |
| 93 | |
| 94 | DCHECK_EQ(num_filled_buckets_, num_buckets) |
| 95 | << "Probing of a non-full table " |
| 96 | << "failed: " << quadratic_probing() << " " << hash; |
| 97 | return Iterator::BUCKET_NOT_FOUND; |
| 98 | } |
| 99 | |
| 100 | inline HashTable::Bucket* HashTable::InsertInternal( |
| 101 | HashTableCtx* __restrict__ ht_ctx, Status* status) { |