| 234 | } |
| 235 | |
| 236 | inline bool BloomFilter::MayContainKey(const BloomKeyProbe &probe) const { |
| 237 | uint32_t h = probe.initial_hash(); |
| 238 | |
| 239 | // Basic unrolling by 2s gives a small benefit here since the two bit positions |
| 240 | // can be calculated in parallel -- it's a 50% chance that the first will be |
| 241 | // set even if it's a bloom miss, in which case we can parallelize the load. |
| 242 | int rem_hashes = n_hashes_; |
| 243 | while (rem_hashes >= 2) { |
| 244 | uint32_t bitpos1 = PickBit(h, n_bits_); |
| 245 | h = probe.MixHash(h); |
| 246 | uint32_t bitpos2 = PickBit(h, n_bits_); |
| 247 | h = probe.MixHash(h); |
| 248 | |
| 249 | if (!BitmapTest(&bitmap_[0], bitpos1) || |
| 250 | !BitmapTest(&bitmap_[0], bitpos2)) { |
| 251 | return false; |
| 252 | } |
| 253 | |
| 254 | rem_hashes -= 2; |
| 255 | } |
| 256 | |
| 257 | while (rem_hashes) { |
| 258 | uint32_t bitpos = PickBit(h, n_bits_); |
| 259 | if (!BitmapTest(&bitmap_[0], bitpos)) { |
| 260 | return false; |
| 261 | } |
| 262 | h = probe.MixHash(h); |
| 263 | rem_hashes--; |
| 264 | } |
| 265 | return true; |
| 266 | } |
| 267 | |
| 268 | } // namespace kudu |