-
Notifications
You must be signed in to change notification settings - Fork 1.5k
/
segment_tree.cpp
51 lines (45 loc) · 1.33 KB
/
segment_tree.cpp
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
#include "duckdb/storage/table/segment_tree.hpp"
#include "duckdb/common/exception.hpp"
#include "duckdb/common/string_util.hpp"
using namespace duckdb;
using namespace std;
SegmentBase *SegmentTree::GetRootSegment() {
return root_node.get();
}
SegmentBase *SegmentTree::GetLastSegment() {
return nodes.back().node;
}
SegmentBase *SegmentTree::GetSegment(index_t row_number) {
lock_guard<mutex> tree_lock(node_lock);
return nodes[GetSegmentIndex(row_number)].node;
}
index_t SegmentTree::GetSegmentIndex(index_t row_number) {
index_t lower = 0;
index_t upper = nodes.size() - 1;
// binary search to find the node
while (lower <= upper) {
index_t index = (lower + upper) / 2;
auto &entry = nodes[index];
if (row_number < entry.row_start) {
upper = index - 1;
} else if (row_number >= entry.row_start + entry.node->count) {
lower = index + 1;
} else {
return index;
}
}
throw Exception("Could not find node in column segment tree!");
}
void SegmentTree::AppendSegment(unique_ptr<SegmentBase> segment) {
// add the node to the list of nodes
SegmentNode node;
node.row_start = segment->start;
node.node = segment.get();
nodes.push_back(node);
if (nodes.size() > 1) {
// add the node as the next pointer of the last node
nodes[nodes.size() - 2].node->next = move(segment);
} else {
root_node = move(segment);
}
}