1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
#pragma once
#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif
//===- AddressRanges.h ------------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ADT_ADDRESSRANGES_H
#define LLVM_ADT_ADDRESSRANGES_H
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include <cassert>
#include <optional>
#include <stdint.h>
namespace llvm {
/// A class that represents an address range. The range is specified using
/// a start and an end address: [Start, End).
class AddressRange {
public:
AddressRange() {}
AddressRange(uint64_t S, uint64_t E) : Start(S), End(E) {
assert(Start <= End);
}
uint64_t start() const { return Start; }
uint64_t end() const { return End; }
uint64_t size() const { return End - Start; }
bool contains(uint64_t Addr) const { return Start <= Addr && Addr < End; }
bool intersects(const AddressRange &R) const {
return Start < R.End && R.Start < End;
}
bool operator==(const AddressRange &R) const {
return Start == R.Start && End == R.End;
}
bool operator!=(const AddressRange &R) const { return !(*this == R); }
bool operator<(const AddressRange &R) const {
return std::make_pair(Start, End) < std::make_pair(R.Start, R.End);
}
private:
uint64_t Start = 0;
uint64_t End = 0;
};
/// The AddressRanges class helps normalize address range collections.
/// This class keeps a sorted vector of AddressRange objects and can perform
/// insertions and searches efficiently. The address ranges are always sorted
/// and never contain any invalid or empty address ranges.
/// Intersecting([100,200), [150,300)) and adjacent([100,200), [200,300))
/// address ranges are combined during insertion.
class AddressRanges {
protected:
using Collection = SmallVector<AddressRange>;
Collection Ranges;
public:
void clear() { Ranges.clear(); }
bool empty() const { return Ranges.empty(); }
bool contains(uint64_t Addr) const { return find(Addr) != Ranges.end(); }
bool contains(AddressRange Range) const {
return find(Range) != Ranges.end();
}
std::optional<AddressRange> getRangeThatContains(uint64_t Addr) const {
Collection::const_iterator It = find(Addr);
if (It == Ranges.end())
return std::nullopt;
return *It;
}
Collection::const_iterator insert(AddressRange Range);
void reserve(size_t Capacity) { Ranges.reserve(Capacity); }
size_t size() const { return Ranges.size(); }
bool operator==(const AddressRanges &RHS) const {
return Ranges == RHS.Ranges;
}
const AddressRange &operator[](size_t i) const {
assert(i < Ranges.size());
return Ranges[i];
}
Collection::const_iterator begin() const { return Ranges.begin(); }
Collection::const_iterator end() const { return Ranges.end(); }
protected:
Collection::const_iterator find(uint64_t Addr) const;
Collection::const_iterator find(AddressRange Range) const;
};
/// AddressRangesMap class maps values to the address ranges.
/// It keeps address ranges and corresponding values. If ranges
/// are combined during insertion, then combined range keeps
/// newly inserted value.
template <typename T> class AddressRangesMap : protected AddressRanges {
public:
void clear() {
Ranges.clear();
Values.clear();
}
bool empty() const { return AddressRanges::empty(); }
bool contains(uint64_t Addr) const { return AddressRanges::contains(Addr); }
bool contains(AddressRange Range) const {
return AddressRanges::contains(Range);
}
void insert(AddressRange Range, T Value) {
size_t InputSize = Ranges.size();
Collection::const_iterator RangesIt = AddressRanges::insert(Range);
if (RangesIt == Ranges.end())
return;
// make Values match to Ranges.
size_t Idx = RangesIt - Ranges.begin();
typename ValuesCollection::iterator ValuesIt = Values.begin() + Idx;
if (InputSize < Ranges.size())
Values.insert(ValuesIt, T());
else if (InputSize > Ranges.size())
Values.erase(ValuesIt, ValuesIt + InputSize - Ranges.size());
assert(Ranges.size() == Values.size());
// set value to the inserted or combined range.
Values[Idx] = Value;
}
size_t size() const {
assert(Ranges.size() == Values.size());
return AddressRanges::size();
}
std::optional<std::pair<AddressRange, T>>
getRangeValueThatContains(uint64_t Addr) const {
Collection::const_iterator It = find(Addr);
if (It == Ranges.end())
return std::nullopt;
return std::make_pair(*It, Values[It - Ranges.begin()]);
}
std::pair<AddressRange, T> operator[](size_t Idx) const {
return std::make_pair(Ranges[Idx], Values[Idx]);
}
protected:
using ValuesCollection = SmallVector<T>;
ValuesCollection Values;
};
} // namespace llvm
#endif // LLVM_ADT_ADDRESSRANGES_H
#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif
|
