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
|
#pragma once
#include <torch/csrc/profiler/unwind/unwind_error.h>
#include <algorithm>
#include <memory>
#include <optional>
#include <vector>
namespace torch::unwind {
template <typename T>
struct RangeTable {
RangeTable() {
// guarentee that lower_bound[-1] is always valid
addresses_.push_back(0);
payloads_.emplace_back(std::nullopt);
}
void add(uint64_t address, std::optional<T> payload, bool sorted) {
if (addresses_.back() > address) {
UNWIND_CHECK(!sorted, "expected addresses to be sorted");
sorted_ = false;
}
addresses_.push_back(address);
payloads_.emplace_back(std::move(payload));
}
std::optional<T> find(uint64_t address) {
maybeSort();
auto it = std::upper_bound(addresses_.begin(), addresses_.end(), address);
return payloads_.at(it - addresses_.begin() - 1);
}
void dump() {
for (size_t i = 0; i < addresses_.size(); i++) {
fmt::print("{} {:x}: {}\n", i, addresses_[i], payloads_[i] ? "" : "END");
}
}
size_t size() const {
return addresses_.size();
}
uint64_t back() {
maybeSort();
return addresses_.back();
}
private:
void maybeSort() {
if (sorted_) {
return;
}
std::vector<uint64_t> indices;
indices.reserve(addresses_.size());
for (size_t i = 0; i < addresses_.size(); i++) {
indices.push_back(i);
}
std::sort(indices.begin(), indices.end(), [&](uint64_t a, uint64_t b) {
return addresses_[a] < addresses_[b] ||
(addresses_[a] == addresses_[b] &&
bool(payloads_[a]) < bool(payloads_[b]));
});
std::vector<uint64_t> addresses;
std::vector<std::optional<T>> payloads;
addresses.reserve(addresses_.size());
payloads.reserve(addresses_.size());
for (auto i : indices) {
addresses.push_back(addresses_[i]);
payloads.push_back(payloads_[i]);
}
addresses_ = std::move(addresses);
payloads_ = std::move(payloads);
sorted_ = true;
}
bool sorted_ = true;
std::vector<uint64_t> addresses_;
std::vector<std::optional<T>> payloads_;
};
} // namespace torch::unwind
|
