//===-- sanitizer_common_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_common_range.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