blob: 503ccaf03ffe64f3acaebf481a8941e35a47f6fa (
plain) (
blame)
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
|
#include "range_set.h"
#include <util/generic/algorithm.h>
namespace {
bool ShouldJoin(const TIpAddressRange& lhs, const TIpAddressRange& rhs) {
return lhs.Overlaps(rhs) || lhs.IsConsecutive(rhs);
}
}
bool TIpRangeSet::TRangeLess::operator()(const TIpAddressRange& lhs, const TIpAddressRange& rhs) const {
return *lhs.Begin() < *rhs.Begin();
}
TIpRangeSet::TIpRangeSet() = default;
TIpRangeSet::~TIpRangeSet() = default;
void TIpRangeSet::Add(TIpAddressRange r) {
Y_ENSURE(IsEmpty() || r.Type() == Type(), "Mixing IPv4 and IPv6 ranges is disallowed");
auto lowerIt = Ranges_.lower_bound(r);
// still may overlap the last interval in our tree
if (IsEmpty()) {
Ranges_.insert(r);
return;
} else if (lowerIt == Ranges_.end()) {
if (auto it = Ranges_.rbegin(); ShouldJoin(*it, r)) {
auto unitedRange = it->Union(r);
Ranges_.erase(--it.base());
Ranges_.insert(unitedRange);
} else {
Ranges_.insert(r);
}
return;
}
TIpAddressRange unitedRange{r};
auto joined = lowerIt;
if (lowerIt != Ranges_.begin()) {
if (ShouldJoin(unitedRange, *(--joined))) {
unitedRange = unitedRange.Union(*joined);
} else {
++joined;
}
}
auto it = lowerIt;
for (; it != Ranges_.end() && ShouldJoin(*it, unitedRange); ++it) {
unitedRange = unitedRange.Union(*it);
}
Ranges_.erase(joined, it);
Ranges_.insert(unitedRange);
}
TIpAddressRange::TIpType TIpRangeSet::Type() const {
return IsEmpty()
? TIpAddressRange::TIpType::LAST
: Ranges_.begin()->Type();
}
bool TIpRangeSet::IsEmpty() const {
return Ranges_.empty();
}
TIpRangeSet::TIterator TIpRangeSet::Find(TIpv6Address addr) const {
if (IsEmpty() || addr.Type() != Type()) {
return End();
}
auto lowerIt = Ranges_.lower_bound(TIpAddressRange(addr, addr));
if (lowerIt == Ranges_.begin()) {
return lowerIt->Contains(addr)
? lowerIt
: End();
} else if (lowerIt == Ranges_.end()) {
auto rbegin = Ranges_.crbegin();
return rbegin->Contains(addr)
? (++rbegin).base()
: End();
} else if (lowerIt->Contains(addr)) {
return lowerIt;
}
--lowerIt;
return lowerIt->Contains(addr)
? lowerIt
: End();
}
bool TIpRangeSet::Contains(TIpv6Address addr) const {
return Find(addr) != End();
}
|
