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({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