1#include <Storages/MergeTree/ActiveDataPartSet.h>
2#include <algorithm>
3
4
5namespace DB
6{
7
8ActiveDataPartSet::ActiveDataPartSet(MergeTreeDataFormatVersion format_version_, const Strings & names)
9 : format_version(format_version_)
10{
11 for (const auto & name : names)
12 add(name);
13}
14
15
16bool ActiveDataPartSet::add(const String & name, Strings * out_replaced_parts)
17{
18 auto part_info = MergeTreePartInfo::fromPartName(name, format_version);
19
20 if (getContainingPartImpl(part_info) != part_info_to_name.end())
21 return false;
22
23 /// Parts contained in `part` are located contiguously in `part_info_to_name`, overlapping with the place where the part itself would be inserted.
24 auto it = part_info_to_name.lower_bound(part_info);
25
26 if (out_replaced_parts)
27 out_replaced_parts->clear();
28
29 /// Let's go left.
30 while (it != part_info_to_name.begin())
31 {
32 --it;
33 if (!part_info.contains(it->first))
34 {
35 ++it;
36 break;
37 }
38
39 if (out_replaced_parts)
40 out_replaced_parts->push_back(it->second);
41 part_info_to_name.erase(it++);
42 }
43
44 if (out_replaced_parts)
45 std::reverse(out_replaced_parts->begin(), out_replaced_parts->end());
46
47 /// Let's go to the right.
48 while (it != part_info_to_name.end() && part_info.contains(it->first))
49 {
50 if (out_replaced_parts)
51 out_replaced_parts->push_back(it->second);
52 part_info_to_name.erase(it++);
53 }
54
55 part_info_to_name.emplace(part_info, name);
56 return true;
57}
58
59
60String ActiveDataPartSet::getContainingPart(const MergeTreePartInfo & part_info) const
61{
62 auto it = getContainingPartImpl(part_info);
63 if (it != part_info_to_name.end())
64 return it->second;
65 return {};
66}
67
68
69String ActiveDataPartSet::getContainingPart(const String & name) const
70{
71 auto it = getContainingPartImpl(MergeTreePartInfo::fromPartName(name, format_version));
72 if (it != part_info_to_name.end())
73 return it->second;
74 return {};
75}
76
77
78std::map<MergeTreePartInfo, String>::const_iterator
79ActiveDataPartSet::getContainingPartImpl(const MergeTreePartInfo & part_info) const
80{
81 /// A part can only be covered/overlapped by the previous or next one in `part_info_to_name`.
82 auto it = part_info_to_name.lower_bound(part_info);
83
84 if (it != part_info_to_name.end())
85 {
86 if (it->first.contains(part_info))
87 return it;
88 }
89
90 if (it != part_info_to_name.begin())
91 {
92 --it;
93 if (it->first.contains(part_info))
94 return it;
95 }
96
97 return part_info_to_name.end();
98}
99
100Strings ActiveDataPartSet::getPartsCoveredBy(const MergeTreePartInfo & part_info) const
101{
102 auto it_middle = part_info_to_name.lower_bound(part_info);
103 auto begin = it_middle;
104 while (begin != part_info_to_name.begin())
105 {
106 auto prev = std::prev(begin);
107 if (!part_info.contains(prev->first))
108 {
109 if (prev->first.contains(part_info))
110 return {};
111
112 break;
113 }
114
115 begin = prev;
116 }
117
118 auto end = it_middle;
119 while (end != part_info_to_name.end())
120 {
121 if (!part_info.contains(end->first))
122 {
123 if (end->first.contains(part_info))
124 return {};
125 break;
126 }
127
128 ++end;
129 }
130
131 Strings covered;
132 for (auto it = begin; it != end; ++it)
133 covered.push_back(it->second);
134
135 return covered;
136}
137
138Strings ActiveDataPartSet::getParts() const
139{
140 Strings res;
141 res.reserve(part_info_to_name.size());
142 for (const auto & kv : part_info_to_name)
143 res.push_back(kv.second);
144
145 return res;
146}
147
148size_t ActiveDataPartSet::size() const
149{
150 return part_info_to_name.size();
151}
152
153}
154