63 lines · cpp
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-exception6//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 else52 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 __sanitizer63