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 
13 namespace __sanitizer {
14 
15 void 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({r.begin, 1, 0});
29     events.push_back({r.end, -1, 0});
30   }
31 
32   for (const Range &r : b) {
33     CHECK_LE(r.begin, r.end);
34     events.push_back({r.begin, 0, 1});
35     events.push_back({r.end, 0, -1});
36   }
37 
38   Sort(events.data(), events.size(),
39        [](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({start, e.val});
53       }
54       start = e.val;
55     }
56 
57     state1 += e.diff1;
58     state2 += e.diff2;
59   }
60 }
61 
62 }  // namespace __sanitizer
63