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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
#pragma once
#include "indexer/interval_index_iface.hpp"
#include "coding/endianness.hpp"
#include "base/assert.hpp"
#include "base/base.hpp"
#include "base/macros.hpp"
#include "std/cstring.hpp"
namespace old_101 {
class IntervalIndexBase : public IntervalIndexIFace
{
public:
#pragma pack(push, 1)
struct Header
{
uint8_t m_CellIdLeafBytes;
};
#pragma pack(pop)
class Index
{
public:
uint32_t GetBaseOffset() const { return UINT32_FROM_UINT16(m_BaseOffsetHi, m_BaseOffsetLo); }
void SetBaseOffset(uint32_t baseOffset)
{
m_BaseOffsetLo = UINT32_LO(baseOffset);
m_BaseOffsetHi = UINT32_HI(baseOffset);
}
private:
uint16_t m_BaseOffsetLo;
uint16_t m_BaseOffsetHi;
public:
uint16_t m_Count[256];
};
static_assert(sizeof(Index) == 2 * 258, "");
};
// TODO: IntervalIndex shouldn't do SwapIfBigEndian for ValueT.
template <typename ValueT, class ReaderT>
class IntervalIndex : public IntervalIndexBase
{
typedef IntervalIndexBase base_t;
public:
IntervalIndex(ReaderT const & reader, int cellIdBytes = 5)
: m_Reader(reader), m_CellIdBytes(cellIdBytes)
{
m_Reader.Read(0, &m_Header, sizeof(m_Header));
ReadIndex(sizeof(m_Header), m_Level0Index);
}
template <typename F>
void ForEach(F const & f, uint64_t beg, uint64_t end) const
{
ASSERT_LESS(beg, 1ULL << 8 * m_CellIdBytes, (beg, end));
ASSERT_LESS_OR_EQUAL(end, 1ULL << 8 * m_CellIdBytes, (beg, end));
// end is inclusive in ForEachImpl().
--end;
ForEachImpl(f, beg, end, m_Level0Index, m_CellIdBytes - 1);
}
virtual void DoForEach(FunctionT const & f, uint64_t beg, uint64_t end)
{
ForEach(f, beg, end);
}
private:
template <typename F>
void ForEachImpl(F const & f, uint64_t beg, uint64_t end, Index const & index, int level) const
{
uint32_t const beg0 = static_cast<uint32_t>(beg >> (8 * level));
uint32_t const end0 = static_cast<uint32_t>(end >> (8 * level));
uint32_t cumCount = 0;
for (uint32_t i = 0; i < beg0; ++i)
cumCount += index.m_Count[i];
for (uint32_t i = beg0; i <= end0; ++i)
{
ASSERT_LESS(i, 256, ());
if (index.m_Count[i] != 0)
{
uint64_t const levelBytesFF = (1ULL << 8 * level) - 1;
uint64_t const b1 = (i == beg0) ? (beg & levelBytesFF) : 0;
uint64_t const e1 = (i == end0) ? (end & levelBytesFF) : levelBytesFF;
if (level > m_Header.m_CellIdLeafBytes)
{
Index index1;
ReadIndex(index.GetBaseOffset() + (cumCount * sizeof(Index)), index1);
ForEachImpl(f, b1, e1, index1, level - 1);
}
else
{
// TODO: Use binary search here if count is very large.
uint32_t const step = sizeof(ValueT) + m_Header.m_CellIdLeafBytes;
uint32_t const count = index.m_Count[i];
uint32_t pos = index.GetBaseOffset() + (cumCount * step);
size_t const readSize = step * count;
vector<char> dataCache(readSize, 0);
char * pData = &dataCache[0];
m_Reader.Read(pos, pData, readSize);
for (uint32_t j = 0; j < count; ++j, pData += step)
// for (uint32_t j = 0; j < count; ++j, pos += step)
{
ValueT value;
uint32_t cellIdOnDisk = 0;
memcpy(&value, pData, sizeof(ValueT));
memcpy(&cellIdOnDisk, pData + sizeof(ValueT), m_Header.m_CellIdLeafBytes);
// m_Reader.Read(pos, &value, step);
uint32_t const cellId = SwapIfBigEndian(cellIdOnDisk);
if (b1 <= cellId && cellId <= e1)
f(SwapIfBigEndian(value));
}
}
cumCount += index.m_Count[i];
}
}
}
void ReadIndex(uint64_t pos, Index & index) const
{
m_Reader.Read(pos, &index, sizeof(Index));
if (IsBigEndian())
{
for (uint32_t i = 0; i < 256; ++i)
index.m_Count[i] = SwapIfBigEndian(index.m_Count[i]);
}
}
ReaderT m_Reader;
Header m_Header;
Index m_Level0Index;
int m_CellIdBytes;
};
}
|
