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 bool contains(uint64_t Addr) const { return Start <= Addr && Addr < End; } 32 bool intersects(const AddressRange &R) const { 33 return Start < R.End && R.Start < End; 34 } 35 bool operator==(const AddressRange &R) const { 36 return Start == R.Start && End == R.End; 37 } 38 bool operator!=(const AddressRange &R) const { return !(*this == R); } 39 bool operator<(const AddressRange &R) const { 40 return std::make_pair(Start, End) < std::make_pair(R.Start, R.End); 41 } 42 43 private: 44 uint64_t Start = 0; 45 uint64_t End = 0; 46 }; 47 48 /// The AddressRanges class helps normalize address range collections. 49 /// This class keeps a sorted vector of AddressRange objects and can perform 50 /// insertions and searches efficiently. The address ranges are always sorted 51 /// and never contain any invalid or empty address ranges. 52 /// Intersecting([100,200), [150,300)) and adjacent([100,200), [200,300)) 53 /// address ranges are combined during insertion. 54 class AddressRanges { 55 protected: 56 using Collection = SmallVector<AddressRange>; 57 Collection Ranges; 58 59 public: 60 void clear() { Ranges.clear(); } 61 bool empty() const { return Ranges.empty(); } 62 bool contains(uint64_t Addr) const { return find(Addr) != Ranges.end(); } 63 bool contains(AddressRange Range) const { 64 return find(Range) != Ranges.end(); 65 } 66 std::optional<AddressRange> getRangeThatContains(uint64_t Addr) const { 67 Collection::const_iterator It = find(Addr); 68 if (It == Ranges.end()) 69 return std::nullopt; 70 71 return *It; 72 } 73 Collection::const_iterator insert(AddressRange Range); 74 void reserve(size_t Capacity) { Ranges.reserve(Capacity); } 75 size_t size() const { return Ranges.size(); } 76 bool operator==(const AddressRanges &RHS) const { 77 return Ranges == RHS.Ranges; 78 } 79 const AddressRange &operator[](size_t i) const { 80 assert(i < Ranges.size()); 81 return Ranges[i]; 82 } 83 Collection::const_iterator begin() const { return Ranges.begin(); } 84 Collection::const_iterator end() const { return Ranges.end(); } 85 86 protected: 87 Collection::const_iterator find(uint64_t Addr) const; 88 Collection::const_iterator find(AddressRange Range) const; 89 }; 90 91 /// AddressRangesMap class maps values to the address ranges. 92 /// It keeps address ranges and corresponding values. If ranges 93 /// are combined during insertion, then combined range keeps 94 /// newly inserted value. 95 template <typename T> class AddressRangesMap : protected AddressRanges { 96 public: 97 void clear() { 98 Ranges.clear(); 99 Values.clear(); 100 } 101 bool empty() const { return AddressRanges::empty(); } 102 bool contains(uint64_t Addr) const { return AddressRanges::contains(Addr); } 103 bool contains(AddressRange Range) const { 104 return AddressRanges::contains(Range); 105 } 106 void insert(AddressRange Range, T Value) { 107 size_t InputSize = Ranges.size(); 108 Collection::const_iterator RangesIt = AddressRanges::insert(Range); 109 if (RangesIt == Ranges.end()) 110 return; 111 112 // make Values match to Ranges. 113 size_t Idx = RangesIt - Ranges.begin(); 114 typename ValuesCollection::iterator ValuesIt = Values.begin() + Idx; 115 if (InputSize < Ranges.size()) 116 Values.insert(ValuesIt, T()); 117 else if (InputSize > Ranges.size()) 118 Values.erase(ValuesIt, ValuesIt + InputSize - Ranges.size()); 119 assert(Ranges.size() == Values.size()); 120 121 // set value to the inserted or combined range. 122 Values[Idx] = Value; 123 } 124 size_t size() const { 125 assert(Ranges.size() == Values.size()); 126 return AddressRanges::size(); 127 } 128 std::optional<std::pair<AddressRange, T>> 129 getRangeValueThatContains(uint64_t Addr) const { 130 Collection::const_iterator It = find(Addr); 131 if (It == Ranges.end()) 132 return std::nullopt; 133 134 return std::make_pair(*It, Values[It - Ranges.begin()]); 135 } 136 std::pair<AddressRange, T> operator[](size_t Idx) const { 137 return std::make_pair(Ranges[Idx], Values[Idx]); 138 } 139 140 protected: 141 using ValuesCollection = SmallVector<T>; 142 ValuesCollection Values; 143 }; 144 145 } // namespace llvm 146 147 #endif // LLVM_ADT_ADDRESSRANGES_H 148