MCPcopy Create free account
hub / github.com/apache/arrow / Fold

Method Fold

cpp/src/parquet/bloom_filter.cc:428–460  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

426}
427
428void BlockSplitBloomFilter::Fold(uint32_t num_folds) {
429 DCHECK_GT(num_folds, 0);
430
431 const uint32_t num_blocks = NumBlocks();
432 // A fold group is a consecutive run of blocks ORed into one output block.
433 // Keeping the group size as (1 << num_folds) preserves a power-of-two bitset
434 // size. Folding by this power-of-two group size keeps the old-to-new bucket
435 // remapping aligned with bucket lookup and avoids false negatives.
436 const uint32_t group_size = UINT32_C(1) << num_folds;
437 DCHECK_LE(group_size, num_blocks);
438
439 const uint32_t new_num_blocks = num_blocks / group_size;
440 auto* bitset32 = reinterpret_cast<uint32_t*>(data_->mutable_data());
441
442 for (uint32_t dst_block = 0; dst_block < new_num_blocks; ++dst_block) {
443 uint32_t* dst = bitset32 + dst_block * kBitsSetPerBlock;
444
445 const uint32_t src_block = dst_block * group_size;
446 const uint32_t* src = bitset32 + src_block * kBitsSetPerBlock;
447 if (dst != src) {
448 std::copy_n(src, kBitsSetPerBlock, dst);
449 }
450
451 for (uint32_t fold_block = 1; fold_block < group_size; ++fold_block) {
452 src = bitset32 + (src_block + fold_block) * kBitsSetPerBlock;
453 for (int word = 0; word < kBitsSetPerBlock; ++word) {
454 dst[word] |= src[word];
455 }
456 }
457 }
458
459 num_bytes_ = new_num_blocks * kBytesPerFilterBlock;
460}
461
462bool BlockSplitBloomFilter::FindHash(uint64_t hash) const {
463 const uint32_t bucket_index = static_cast<uint32_t>(((hash >> 32) * NumBlocks()) >> 32);

Callers

nothing calls this directly

Calls 2

NumBlocksFunction · 0.85
mutable_dataMethod · 0.45

Tested by

no test coverage detected