Home | History | Annotate | Line # | Download | only in sanitizer_common 
      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