1//===- AddressRanges.cpp ----------------------------------------*- C++ -*-===//
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 "llvm/ADT/AddressRanges.h"
10#include "llvm/ADT/STLExtras.h"
11#include <inttypes.h>
12
13using namespace llvm;
14
15AddressRanges::Collection::const_iterator
16AddressRanges::insert(AddressRange Range) {
17  if (Range.size() == 0)
18    return Ranges.end();
19
20  auto It = llvm::upper_bound(Ranges, Range);
21  auto It2 = It;
22  while (It2 != Ranges.end() && It2->start() <= Range.end())
23    ++It2;
24  if (It != It2) {
25    Range = {Range.start(), std::max(Range.end(), std::prev(It2)->end())};
26    It = Ranges.erase(It, It2);
27  }
28  if (It != Ranges.begin() && Range.start() <= std::prev(It)->end()) {
29    --It;
30    *It = {It->start(), std::max(It->end(), Range.end())};
31    return It;
32  }
33
34  return Ranges.insert(It, Range);
35}
36
37AddressRanges::Collection::const_iterator
38AddressRanges::find(uint64_t Addr) const {
39  auto It = std::partition_point(
40      Ranges.begin(), Ranges.end(),
41      [=](const AddressRange &R) { return R.start() <= Addr; });
42
43  if (It == Ranges.begin())
44    return Ranges.end();
45
46  --It;
47  if (Addr >= It->end())
48    return Ranges.end();
49
50  return It;
51}
52
53AddressRanges::Collection::const_iterator
54AddressRanges::find(AddressRange Range) const {
55  if (Range.size() == 0)
56    return Ranges.end();
57
58  auto It = std::partition_point(
59      Ranges.begin(), Ranges.end(),
60      [=](const AddressRange &R) { return R.start() <= Range.start(); });
61
62  if (It == Ranges.begin())
63    return Ranges.end();
64
65  --It;
66  if (Range.end() > It->end())
67    return Ranges.end();
68
69  return It;
70}
71