libsanitizer/sanitizer_common/sanitizer_range.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-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