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