1//===-- sanitizer_range.cpp -----------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "sanitizer_range.h"
10
11#include "sanitizer_common/sanitizer_array_ref.h"
12
13namespace __sanitizer {
14
15void Intersect(ArrayRef<Range> a, ArrayRef<Range> b,
16 InternalMmapVectorNoCtor<Range> &output) {
17 output.clear();
18
19 struct Event {
20 uptr val;
21 s8 diff1;
22 s8 diff2;
23 };
24
25 InternalMmapVector<Event> events;
26 for (const Range &r : a) {
27 CHECK_LE(r.begin, r.end);
28 events.push_back(element: {.val: r.begin, .diff1: 1, .diff2: 0});
29 events.push_back(element: {.val: r.end, .diff1: -1, .diff2: 0});
30 }
31
32 for (const Range &r : b) {
33 CHECK_LE(r.begin, r.end);
34 events.push_back(element: {.val: r.begin, .diff1: 0, .diff2: 1});
35 events.push_back(element: {.val: r.end, .diff1: 0, .diff2: -1});
36 }
37
38 Sort(v: events.data(), size: events.size(),
39 comp: [](const Event &lh, const Event &rh) { return lh.val < rh.val; });
40
41 uptr start = 0;
42 sptr state1 = 0;
43 sptr state2 = 0;
44 for (const auto &e : events) {
45 if (e.val != start) {
46 DCHECK_GE(state1, 0);
47 DCHECK_GE(state2, 0);
48 if (state1 && state2) {
49 if (!output.empty() && start == output.back().end)
50 output.back().end = e.val;
51 else
52 output.push_back(element: {.begin: start, .end: e.val});
53 }
54 start = e.val;
55 }
56
57 state1 += e.diff1;
58 state2 += e.diff2;
59 }
60}
61
62} // namespace __sanitizer
63