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() {} 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(Start, End) < std::make_pair(R.Start, 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(Addr, Addr + 1) != Ranges.end(); 68 } 69 bool contains(AddressRange Range) const { 70 return find(Range.start(), 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(Addr, 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 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 = 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. 121class AddressRanges : public AddressRangesBase<AddressRange> { 122public: 123 Collection::const_iterator insert(AddressRange Range) { 124 if (Range.empty()) 125 return Ranges.end(); 126 127 auto It = llvm::upper_bound(Ranges, 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(Range.end(), std::prev(It2)->end())}; 133 It = Ranges.erase(It, It2); 134 } 135 if (It != Ranges.begin() && Range.start() <= std::prev(It)->end()) { 136 --It; 137 *It = {It->start(), std::max(It->end(), Range.end())}; 138 return It; 139 } 140 141 return Ranges.insert(It, Range); 142 } 143}; 144 145class AddressRangeValuePair { 146public: 147 operator AddressRange() const { return Range; } 148 149 AddressRange Range; 150 int64_t Value = 0; 151}; 152 153inline 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. 165class AddressRangesMap : public AddressRangesBase<AddressRangeValuePair> { 166public: 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(Ranges.begin(), Ranges.end(), 173 [=](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(It, {Range, 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(It, {{Range.start(), It->Range.start()}, 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