1 files changed, 62 insertions, 0 deletions
diff --git a/contrib/llvm-project/compiler-rt/lib/sanitizer_common/sanitizer_range.cpp b/contrib/llvm-project/compiler-rt/lib/sanitizer_common/sanitizer_range.cpp
new file mode 100644
index 000000000000..68d79f18ac8d
--- /dev/null
+++ b/contrib/llvm-project/compiler-rt/lib/sanitizer_common/sanitizer_range.cpp
@@ -0,0 +1,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