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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
//===- HashMappedTrieIndexGenerator.h ---------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_LIB_CAS_HASHMAPPEDTRIEINDEXGENERATOR_H
#define LLVM_LIB_CAS_HASHMAPPEDTRIEINDEXGENERATOR_H
#include "llvm/ADT/ArrayRef.h"
namespace llvm {
namespace cas {
struct IndexGenerator {
size_t NumRootBits;
size_t NumSubtrieBits;
ArrayRef<uint8_t> Bytes;
std::optional<size_t> StartBit = std::nullopt;
size_t getNumBits() const {
assert(StartBit);
size_t TotalNumBits = Bytes.size() * 8;
assert(*StartBit <= TotalNumBits);
return std::min(*StartBit ? NumSubtrieBits : NumRootBits,
TotalNumBits - *StartBit);
}
size_t next() {
size_t Index;
if (!StartBit) {
StartBit = 0;
Index = getIndex(Bytes, *StartBit, NumRootBits);
} else {
*StartBit += *StartBit ? NumSubtrieBits : NumRootBits;
assert((*StartBit - NumRootBits) % NumSubtrieBits == 0);
Index = getIndex(Bytes, *StartBit, NumSubtrieBits);
}
return Index;
}
size_t hint(unsigned Index, unsigned Bit) {
assert(Index >= 0);
assert(Bit < Bytes.size() * 8);
assert(Bit == 0 || (Bit - NumRootBits) % NumSubtrieBits == 0);
StartBit = Bit;
return Index;
}
size_t getCollidingBits(ArrayRef<uint8_t> CollidingBits) const {
assert(StartBit);
return getIndex(CollidingBits, *StartBit, NumSubtrieBits);
}
static size_t getIndex(ArrayRef<uint8_t> Bytes, size_t StartBit,
size_t NumBits) {
assert(StartBit < Bytes.size() * 8);
Bytes = Bytes.drop_front(StartBit / 8u);
StartBit %= 8u;
size_t Index = 0;
for (uint8_t Byte : Bytes) {
size_t ByteStart = 0, ByteEnd = 8;
if (StartBit) {
ByteStart = StartBit;
Byte &= (1u << (8 - StartBit)) - 1u;
StartBit = 0;
}
size_t CurrentNumBits = ByteEnd - ByteStart;
if (CurrentNumBits > NumBits) {
Byte >>= CurrentNumBits - NumBits;
CurrentNumBits = NumBits;
}
Index <<= CurrentNumBits;
Index |= Byte & ((1u << CurrentNumBits) - 1u);
assert(NumBits >= CurrentNumBits);
NumBits -= CurrentNumBits;
if (!NumBits)
break;
}
return Index;
}
};
} // namespace cas
} // namespace llvm
#endif // LLVM_LIB_CAS_HASHMAPPEDTRIEINDEXGENERATOR_H
|
