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 | |
18 | namespace llvm { |
19 | |
20 | /// A class that represents an address range. The range is specified using |
21 | /// a start and an end address: [Start, End). |
22 | class AddressRange { |
23 | public: |
24 | AddressRange() {} |
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 | |
47 | private: |
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 | |
58 | template <typename T> class AddressRangesBase { |
59 | protected: |
60 | using Collection = SmallVector<T>; |
61 | Collection Ranges; |
62 | |
63 | public: |
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<T> &RHS) const { |
92 | return Ranges == RHS.Ranges; |
93 | } |
94 | |
95 | protected: |
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 = |
101 | std::partition_point(Ranges.begin(), Ranges.end(), [=](const T &R) { |
102 | return AddressRange(R).start() <= Start; |
103 | }); |
104 | |
105 | if (It == Ranges.begin()) |
106 | return Ranges.end(); |
107 | |
108 | --It; |
109 | if (End > AddressRange(*It).end()) |
110 | return Ranges.end(); |
111 | |
112 | return It; |
113 | } |
114 | }; |
115 | |
116 | /// The AddressRanges class helps normalize address range collections. |
117 | /// This class keeps a sorted vector of AddressRange objects and can perform |
118 | /// insertions and searches efficiently. Intersecting([100,200), [150,300)) |
119 | /// and adjacent([100,200), [200,300)) address ranges are combined during |
120 | /// insertion. |
121 | class AddressRanges : public AddressRangesBase<AddressRange> { |
122 | public: |
123 | Collection::const_iterator insert(AddressRange Range) { |
124 | if (Range.empty()) |
125 | return Ranges.end(); |
126 | |
127 | auto It = llvm::upper_bound(Range&: Ranges, Value&: Range); |
128 | auto It2 = It; |
129 | while (It2 != Ranges.end() && It2->start() <= Range.end()) |
130 | ++It2; |
131 | if (It != It2) { |
132 | Range = {Range.start(), std::max(a: Range.end(), b: std::prev(x: It2)->end())}; |
133 | It = Ranges.erase(CS: It, CE: It2); |
134 | } |
135 | if (It != Ranges.begin() && Range.start() <= std::prev(x: It)->end()) { |
136 | --It; |
137 | *It = {It->start(), std::max(a: It->end(), b: Range.end())}; |
138 | return It; |
139 | } |
140 | |
141 | return Ranges.insert(I: It, Elt: Range); |
142 | } |
143 | }; |
144 | |
145 | class AddressRangeValuePair { |
146 | public: |
147 | operator AddressRange() const { return Range; } |
148 | |
149 | AddressRange Range; |
150 | int64_t Value = 0; |
151 | }; |
152 | |
153 | inline bool operator==(const AddressRangeValuePair &LHS, |
154 | const AddressRangeValuePair &RHS) { |
155 | return LHS.Range == RHS.Range && LHS.Value == RHS.Value; |
156 | } |
157 | |
158 | /// AddressRangesMap class maps values to the address ranges. |
159 | /// It keeps normalized address ranges and corresponding values. |
160 | /// This class keeps a sorted vector of AddressRangeValuePair objects |
161 | /// and can perform insertions and searches efficiently. |
162 | /// Intersecting([100,200), [150,300)) ranges splitted into non-conflicting |
163 | /// parts([100,200), [200,300)). Adjacent([100,200), [200,300)) address |
164 | /// ranges are not combined during insertion. |
165 | class AddressRangesMap : public AddressRangesBase<AddressRangeValuePair> { |
166 | public: |
167 | void insert(AddressRange Range, int64_t Value) { |
168 | if (Range.empty()) |
169 | return; |
170 | |
171 | // Search for range which is less than or equal incoming Range. |
172 | auto It = std::partition_point(first: Ranges.begin(), last: Ranges.end(), |
173 | pred: [=](const AddressRangeValuePair &R) { |
174 | return R.Range.start() <= Range.start(); |
175 | }); |
176 | |
177 | if (It != Ranges.begin()) |
178 | It--; |
179 | |
180 | while (!Range.empty()) { |
181 | // Inserted range does not overlap with any range. |
182 | // Store it into the Ranges collection. |
183 | if (It == Ranges.end() || Range.end() <= It->Range.start()) { |
184 | Ranges.insert(I: It, Elt: {.Range: Range, .Value: Value}); |
185 | return; |
186 | } |
187 | |
188 | // Inserted range partially overlaps with current range. |
189 | // Store not overlapped part of inserted range. |
190 | if (Range.start() < It->Range.start()) { |
191 | It = Ranges.insert(I: It, Elt: {.Range: {Range.start(), It->Range.start()}, .Value: Value}); |
192 | It++; |
193 | Range = {It->Range.start(), Range.end()}; |
194 | continue; |
195 | } |
196 | |
197 | // Inserted range fully overlaps with current range. |
198 | if (Range.end() <= It->Range.end()) |
199 | return; |
200 | |
201 | // Inserted range partially overlaps with current range. |
202 | // Remove overlapped part from the inserted range. |
203 | if (Range.start() < It->Range.end()) |
204 | Range = {It->Range.end(), Range.end()}; |
205 | |
206 | It++; |
207 | } |
208 | } |
209 | }; |
210 | |
211 | } // namespace llvm |
212 | |
213 | #endif // LLVM_ADT_ADDRESSRANGES_H |
214 | |