blob: 250c783f57e9bebebdaa8d067a5a53a2b44e5062 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
#include "generic_btree_bucket_database.h"
namespace storage::bucketdb {
using document::BucketId;
// TODO getMinDiffBits is hoisted from lockablemap.cpp, could probably be rewritten in terms of xor and MSB bit scan instr
/*
* 63 -------- ... -> 0
* a: 1101111111 ... 0010
* b: 1101110010 ... 0011
* a ^ b: 0000001101 ... 0001
* ^- diff bit = 57
*
* 63 - vespalib::Optimized::msbIdx(a ^ b) ==> 6
*
* what if a == b? special case? not a problem if we can prove this never happens.
*/
// TODO dedupe and unify common code
uint8_t
getMinDiffBits(uint16_t minBits, const BucketId& a, const BucketId& b) {
for (uint32_t i = minBits; i <= std::min(a.getUsedBits(), b.getUsedBits()); i++) {
BucketId a1(i, a.getRawId());
BucketId b1(i, b.getRawId());
if (b1.getId() != a1.getId()) {
return i;
}
}
return minBits;
}
uint8_t next_parent_bit_seek_level(uint8_t minBits, const BucketId& a, const BucketId& b) {
const uint8_t min_used = std::min(a.getUsedBits(), b.getUsedBits());
assert(min_used >= minBits); // Always monotonically descending towards leaves
for (uint32_t i = minBits; i <= min_used; i++) {
BucketId a1(i, a.getRawId());
BucketId b1(i, b.getRawId());
if (b1.getId() != a1.getId()) {
return i;
}
}
// The bit prefix is equal, which means that one node is a parent of the other. In this
// case we have to force the seek to continue from the next level in the tree.
return std::max(min_used, minBits) + 1;
}
}
|
