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