| 47 | // |
| 48 | template <bool use_start_slot> |
| 49 | inline 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 | |
| 97 | template <typename T, bool use_selection> |
| 98 | void SwissTable::extract_group_ids_imp(const int num_keys, const uint16_t* selection, |
nothing calls this directly
no outgoing calls
no test coverage detected