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
|
//===-- sanitizer_range.cpp -----------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "sanitizer_range.h"
#include "sanitizer_common/sanitizer_array_ref.h"
namespace __sanitizer {
void Intersect(ArrayRef<Range> a, ArrayRef<Range> b,
InternalMmapVectorNoCtor<Range> &output) {
output.clear();
struct Event {
uptr val;
s8 diff1;
s8 diff2;
};
InternalMmapVector<Event> events;
for (const Range &r : a) {
CHECK_LE(r.begin, r.end);
events.push_back({r.begin, 1, 0});
events.push_back({r.end, -1, 0});
}
for (const Range &r : b) {
CHECK_LE(r.begin, r.end);
events.push_back({r.begin, 0, 1});
events.push_back({r.end, 0, -1});
}
Sort(events.data(), events.size(),
[](const Event &lh, const Event &rh) { return lh.val < rh.val; });
uptr start = 0;
sptr state1 = 0;
sptr state2 = 0;
for (const auto &e : events) {
if (e.val != start) {
DCHECK_GE(state1, 0);
DCHECK_GE(state2, 0);
if (state1 && state2) {
if (!output.empty() && start == output.back().end)
output.back().end = e.val;
else
output.push_back({start, e.val});
}
start = e.val;
}
state1 += e.diff1;
state2 += e.diff2;
}
}
} // namespace __sanitizer
|
