1//===- AddressRanges.h ------------------------------------------*- 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#ifndef LLVM_ADT_ADDRESSRANGES_H
10#define LLVM_ADT_ADDRESSRANGES_H
11
12#include "llvm/ADT/STLExtras.h"
13#include "llvm/ADT/SmallVector.h"
14#include <cassert>
15#include <optional>
16#include <stdint.h>
17
18namespace llvm {
19
20/// A class that represents an address range. The range is specified using
21/// a start and an end address: [Start, End).
22class AddressRange {
23public:
24 AddressRange() = default;
25 AddressRange(uint64_t S, uint64_t E) : Start(S), End(E) {
26 assert(Start <= End);
27 }
28 uint64_t start() const { return Start; }
29 uint64_t end() const { return End; }
30 uint64_t size() const { return End - Start; }
31 uint64_t empty() const { return size() == 0; }
32 bool contains(uint64_t Addr) const { return Start <= Addr && Addr < End; }
33 bool contains(const AddressRange &R) const {
34 return Start <= R.Start && R.End <= End;
35 }
36 bool intersects(const AddressRange &R) const {
37 return Start < R.End && R.Start < End;
38 }
39 bool operator==(const AddressRange &R) const {
40 return Start == R.Start && End == R.End;
41 }
42 bool operator!=(const AddressRange &R) const { return !(*this == R); }
43 bool operator<(const AddressRange &R) const {
44 return std::make_pair(x: Start, y: End) < std::make_pair(x: R.Start, y: R.End);
45 }
46
47private:
48 uint64_t Start = 0;
49 uint64_t End = 0;
50};
51
52/// The AddressRangesBase class presents the base functionality for the
53/// normalized address ranges collection. This class keeps a sorted vector
54/// of AddressRange-like objects and can perform searches efficiently.
55/// The address ranges are always sorted and never contain any invalid,
56/// empty or intersected address ranges.
57
58template <typename T> class AddressRangesBase {
59protected:
60 using Collection = SmallVector<T>;
61 Collection Ranges;
62
63public:
64 void clear() { Ranges.clear(); }
65 bool empty() const { return Ranges.empty(); }
66 bool contains(uint64_t Addr) const {
67 return find(Start: Addr, End: Addr + 1) != Ranges.end();
68 }
69 bool contains(AddressRange Range) const {
70 return find(Start: Range.start(), End: Range.end()) != Ranges.end();
71 }
72 void reserve(size_t Capacity) { Ranges.reserve(Capacity); }
73 size_t size() const { return Ranges.size(); }
74
75 std::optional<T> getRangeThatContains(uint64_t Addr) const {
76 typename Collection::const_iterator It = find(Start: Addr, End: Addr + 1);
77 if (It == Ranges.end())
78 return std::nullopt;
79
80 return *It;
81 }
82
83 typename Collection::const_iterator begin() const { return Ranges.begin(); }
84 typename Collection::const_iterator end() const { return Ranges.end(); }
85
86 const T &operator[](size_t I) const {
87 assert(I < Ranges.size());
88 return Ranges[I];
89 }
90
91 bool operator==(const AddressRangesBase &RHS) const {
92 return Ranges == RHS.Ranges;
93 }
94
95protected:
96 typename Collection::const_iterator find(uint64_t Start, uint64_t End) const {
97 if (Start >= End)
98 return Ranges.end();
99
100 auto It = llvm::partition_point(
101 Ranges, [=](const T &R) { return AddressRange(R).start() <= Start; });
102
103 if (It == Ranges.begin())
104 return Ranges.end();
105
106 --It;
107 if (End > AddressRange(*It).end())
108 return Ranges.end();
109
110 return It;
111 }
112};
113
114/// The AddressRanges class helps normalize address range collections.
115/// This class keeps a sorted vector of AddressRange objects and can perform
116/// insertions and searches efficiently. Intersecting([100,200), [150,300))
117/// and adjacent([100,200), [200,300)) address ranges are combined during
118/// insertion.
119class AddressRanges : public AddressRangesBase<AddressRange> {
120public:
121 Collection::const_iterator insert(AddressRange Range) {
122 if (Range.empty())
123 return Ranges.end();
124
125 auto It = upper_bound(Range&: Ranges, Value&: Range);
126 auto It2 = It;
127 while (It2 != Ranges.end() && It2->start() <= Range.end())
128 ++It2;
129 if (It != It2) {
130 Range = {Range.start(), std::max(a: Range.end(), b: std::prev(x: It2)->end())};
131 It = Ranges.erase(CS: It, CE: It2);
132 }
133 if (It != Ranges.begin() && Range.start() <= std::prev(x: It)->end()) {
134 --It;
135 *It = {It->start(), std::max(a: It->end(), b: Range.end())};
136 return It;
137 }
138
139 return Ranges.insert(I: It, Elt: Range);
140 }
141};
142
143class AddressRangeValuePair {
144public:
145 explicit operator AddressRange() const { return Range; }
146
147 AddressRange Range;
148 int64_t Value = 0;
149};
150
151inline bool operator==(const AddressRangeValuePair &LHS,
152 const AddressRangeValuePair &RHS) {
153 return LHS.Range == RHS.Range && LHS.Value == RHS.Value;
154}
155
156/// AddressRangesMap class maps values to the address ranges.
157/// It keeps normalized address ranges and corresponding values.
158/// This class keeps a sorted vector of AddressRangeValuePair objects
159/// and can perform insertions and searches efficiently.
160/// Intersecting([100,200), [150,300)) ranges splitted into non-conflicting
161/// parts([100,200), [200,300)). Adjacent([100,200), [200,300)) address
162/// ranges are not combined during insertion.
163class AddressRangesMap : public AddressRangesBase<AddressRangeValuePair> {
164public:
165 void insert(AddressRange Range, int64_t Value) {
166 if (Range.empty())
167 return;
168
169 // Search for range which is less than or equal incoming Range.
170 auto It =
171 llvm::partition_point(Range&: Ranges, P: [=](const AddressRangeValuePair &R) {
172 return R.Range.start() <= Range.start();
173 });
174
175 if (It != Ranges.begin())
176 It--;
177
178 while (!Range.empty()) {
179 // Inserted range does not overlap with any range.
180 // Store it into the Ranges collection.
181 if (It == Ranges.end() || Range.end() <= It->Range.start()) {
182 Ranges.insert(I: It, Elt: {.Range: Range, .Value: Value});
183 return;
184 }
185
186 // Inserted range partially overlaps with current range.
187 // Store not overlapped part of inserted range.
188 if (Range.start() < It->Range.start()) {
189 It = Ranges.insert(I: It, Elt: {.Range: {Range.start(), It->Range.start()}, .Value: Value});
190 It++;
191 Range = {It->Range.start(), Range.end()};
192 continue;
193 }
194
195 // Inserted range fully overlaps with current range.
196 if (Range.end() <= It->Range.end())
197 return;
198
199 // Inserted range partially overlaps with current range.
200 // Remove overlapped part from the inserted range.
201 if (Range.start() < It->Range.end())
202 Range = {It->Range.end(), Range.end()};
203
204 It++;
205 }
206 }
207};
208
209} // namespace llvm
210
211#endif // LLVM_ADT_ADDRESSRANGES_H
212