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

Method search_block

cpp/src/arrow/compute/key_map_internal.cc:49–95  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

47//
48template <bool use_start_slot>
49inline void SwissTable::search_block(uint64_t block, int stamp, int start_slot,
50 int* out_slot, int* out_match_found) const {
51 // Filled slot bytes have the highest bit set to 0 and empty slots are equal to 0x80.
52 uint64_t block_high_bits = block & kHighBitOfEachByte;
53
54 // Replicate 7-bit stamp to all non-empty slots, leaving zeroes for empty slots.
55 uint64_t stamp_pattern = stamp * ((block_high_bits ^ kHighBitOfEachByte) >> 7);
56
57 // If we xor this pattern with block status bytes we get in individual bytes:
58 // a) 0x00, for filled slots matching the stamp,
59 // b) 0x00 < x < 0x80, for filled slots not matching the stamp,
60 // c) 0x80, for empty slots.
61 uint64_t block_xor_pattern = block ^ stamp_pattern;
62
63 // If we then add 0x7f to every byte, we get:
64 // a) 0x7F
65 // b) 0x80 <= x < 0xFF
66 // c) 0xFF
67 uint64_t match_base = block_xor_pattern + ~kHighBitOfEachByte;
68
69 // The highest bit now tells us if we have a match (0) or not (1).
70 // We will negate the bits so that match is represented by a set bit.
71 uint64_t matches = ~match_base;
72
73 // Clear 7 non-relevant bits in each byte.
74 // Also clear bytes that correspond to slots that we were supposed to
75 // skip due to provided start slot index.
76 // Note: the highest byte corresponds to the first slot.
77 if (use_start_slot) {
78 matches &= kHighBitOfEachByte >> (8 * start_slot);
79 } else {
80 matches &= kHighBitOfEachByte;
81 }
82
83 // In case when there are no matches in slots and the block is full (no empty slots),
84 // pretend that there is a match in the last slot.
85 //
86 matches |= (~block_high_bits & 0x80);
87
88 // We get 0 if there are no matches
89 *out_match_found = (matches == 0 ? 0 : 1);
90
91 // Now if we or with the highest bits of the block and scan zero bits in reverse, we get
92 // 8x slot index that we were looking for. This formula works in all three cases a), b)
93 // and c).
94 *out_slot = static_cast<int>(std::countl_zero(matches | block_high_bits) >> 3);
95}
96
97template <typename T, bool use_selection>
98void SwissTable::extract_group_ids_imp(const int num_keys, const uint16_t* selection,

Callers

nothing calls this directly

Calls

no outgoing calls

Tested by

no test coverage detected