1#include "duckdb/storage/table/segment_tree.hpp"
2#include "duckdb/common/exception.hpp"
3#include "duckdb/common/string_util.hpp"
4using namespace duckdb;
5using namespace std;
6
7SegmentBase *SegmentTree::GetRootSegment() {
8 return root_node.get();
9}
10
11SegmentBase *SegmentTree::GetLastSegment() {
12 return nodes.back().node;
13}
14
15SegmentBase *SegmentTree::GetSegment(idx_t row_number) {
16 lock_guard<mutex> tree_lock(node_lock);
17 return nodes[GetSegmentIndex(row_number)].node;
18}
19
20idx_t SegmentTree::GetSegmentIndex(idx_t row_number) {
21 idx_t lower = 0;
22 idx_t upper = nodes.size() - 1;
23 // binary search to find the node
24 while (lower <= upper) {
25 idx_t index = (lower + upper) / 2;
26 auto &entry = nodes[index];
27 if (row_number < entry.row_start) {
28 upper = index - 1;
29 } else if (row_number >= entry.row_start + entry.node->count) {
30 lower = index + 1;
31 } else {
32 return index;
33 }
34 }
35 throw Exception("Could not find node in column segment tree!");
36}
37
38void SegmentTree::AppendSegment(unique_ptr<SegmentBase> segment) {
39 // add the node to the list of nodes
40 SegmentNode node;
41 node.row_start = segment->start;
42 node.node = segment.get();
43 nodes.push_back(node);
44
45 if (nodes.size() > 1) {
46 // add the node as the next pointer of the last node
47 nodes[nodes.size() - 2].node->next = move(segment);
48 } else {
49 root_node = move(segment);
50 }
51}
52