From 8e7260067be13075e7d8b78d3dceec50dc7ddab4 Mon Sep 17 00:00:00 2001 From: Brian Potchik Date: Thu, 14 Nov 2024 10:47:04 -0500 Subject: Fix indentation for easier diffs. --- genericrange.h | 332 ++++++++++++++++++++++++++++----------------------------- 1 file changed, 166 insertions(+), 166 deletions(-) diff --git a/genericrange.h b/genericrange.h index f21441bd..c46aa064 100644 --- a/genericrange.h +++ b/genericrange.h @@ -29,215 +29,215 @@ namespace BinaryNinjaCore using namespace std; #endif -template -class GenericRange -{ - uint64_t m_start; - uint64_t m_end; - vector m_items; - -public: - GenericRange(uint64_t s) : m_start(s), m_end(0) { } - GenericRange(uint64_t s, uint64_t e, const T& item) : m_start(s), m_end(e), m_items{item} {} - GenericRange(uint64_t s, uint64_t e, const vector& items) : m_start(s), m_end(e), m_items{items} {} - - bool operator<(const GenericRange& other) const + template + class GenericRange { - if (m_start != other.m_start) - return m_start < other.m_start; - return m_end < other.m_end; - } - - uint64_t GetStart() const { return m_start; } - uint64_t GetEnd() const { return m_end; } - const vector& GetItems() const { return m_items; } - vector& GetMutableItems() { return m_items; } + uint64_t m_start; + uint64_t m_end; + vector m_items; - bool overlaps(const GenericRange& other) const { return !(other.m_start > m_end || m_start > other.m_end); } + public: + GenericRange(uint64_t s) : m_start(s), m_end(0) { } + GenericRange(uint64_t s, uint64_t e, const T& item) : m_start(s), m_end(e), m_items{item} {} + GenericRange(uint64_t s, uint64_t e, const vector& items) : m_start(s), m_end(e), m_items{items} {} - vector split(const GenericRange& nextInterval) const - { - vector result; - if (overlaps(nextInterval)) + bool operator<(const GenericRange& other) const { - // Find overlap start and end - uint64_t intersectionStart = std::max(m_start, nextInterval.m_start); - uint64_t intersectionEnd = std::min(m_end, nextInterval.m_end); - - // Add part of this section to before the intersecting region if it starts earlier - if (m_start < intersectionStart) - result.push_back({m_start, intersectionStart - 1, m_items}); - - // Add the intersecting range, plus both sets of items - GenericRange intersection(intersectionStart, intersectionEnd, m_items); - intersection.m_items.insert(intersection.m_items.end(), nextInterval.m_items.begin(), nextInterval.m_items.end()); - result.push_back(intersection); - - // If the an interval's end is after the intersection (only up to one will be) add it after - if (nextInterval.m_end > intersectionEnd) - result.push_back({intersectionEnd + 1, nextInterval.m_end, nextInterval.m_items}); - else if (m_end > intersectionEnd) - result.push_back({intersectionEnd + 1, m_end, m_items}); + if (m_start != other.m_start) + return m_start < other.m_start; + return m_end < other.m_end; } - return result; - } -}; + uint64_t GetStart() const { return m_start; } + uint64_t GetEnd() const { return m_end; } + const vector& GetItems() const { return m_items; } + vector& GetMutableItems() { return m_items; } -// A map of ranges to items. The ranges are flattened and sorted, and the map is used to quickly find the items. Range values are inclusive. -template -class GenericRangeMap -{ - vector> m_sourceRanges; - vector> m_flattenedRanges; - map> m_rangeMap; + bool overlaps(const GenericRange& other) const { return !(other.m_start > m_end || m_start > other.m_end); } - void populateRangeMap() - { - uint64_t nextStart = 0; - for (const auto& i : m_flattenedRanges) + vector split(const GenericRange& nextInterval) const { - if (i.GetStart() > nextStart) - m_rangeMap.emplace(nextStart, GenericRange(nextStart, i.GetStart() - 1, vector())); + vector result; + if (overlaps(nextInterval)) + { + // Find overlap start and end + uint64_t intersectionStart = std::max(m_start, nextInterval.m_start); + uint64_t intersectionEnd = std::min(m_end, nextInterval.m_end); + + // Add part of this section to before the intersecting region if it starts earlier + if (m_start < intersectionStart) + result.push_back({m_start, intersectionStart - 1, m_items}); + + // Add the intersecting range, plus both sets of items + GenericRange intersection(intersectionStart, intersectionEnd, m_items); + intersection.m_items.insert(intersection.m_items.end(), nextInterval.m_items.begin(), nextInterval.m_items.end()); + result.push_back(intersection); + + // If the an interval's end is after the intersection (only up to one will be) add it after + if (nextInterval.m_end > intersectionEnd) + result.push_back({intersectionEnd + 1, nextInterval.m_end, nextInterval.m_items}); + else if (m_end > intersectionEnd) + result.push_back({intersectionEnd + 1, m_end, m_items}); + } - m_rangeMap.emplace(i.GetStart(), GenericRange(i.GetStart(), i.GetEnd(), i.GetItems())); - nextStart = i.GetEnd(); - if (nextStart != std::numeric_limits::max()) - nextStart++; + return result; } + }; - if (nextStart != std::numeric_limits::max()) - m_rangeMap.emplace(nextStart, GenericRange(nextStart, std::numeric_limits::max(), vector())); - } - -public: - static void flatten(vector>& intervals) + // A map of ranges to items. The ranges are flattened and sorted, and the map is used to quickly find the items. Range values are inclusive. + template + class GenericRangeMap { - // Make a flat list of intervals, with each interval having all elements found in it - // TODO: using a vector isn't ideal, since each modification not at front or back is O(n) - std::sort(intervals.begin(), intervals.end()); - auto itr = intervals.begin(); - while (itr != intervals.end()) + vector> m_sourceRanges; + vector> m_flattenedRanges; + map> m_rangeMap; + + void populateRangeMap() { - auto currentRange = *itr; - auto nextRange = std::next(itr); - if (nextRange == intervals.end()) // This is the last interval - break; + uint64_t nextStart = 0; + for (const auto& i : m_flattenedRanges) + { + if (i.GetStart() > nextStart) + m_rangeMap.emplace(nextStart, GenericRange(nextStart, i.GetStart() - 1, vector())); + + m_rangeMap.emplace(i.GetStart(), GenericRange(i.GetStart(), i.GetEnd(), i.GetItems())); + nextStart = i.GetEnd(); + if (nextStart != std::numeric_limits::max()) + nextStart++; + } + + if (nextStart != std::numeric_limits::max()) + m_rangeMap.emplace(nextStart, GenericRange(nextStart, std::numeric_limits::max(), vector())); + } - if (auto splitRanges = currentRange.split(*nextRange); splitRanges.size()) + public: + static void flatten(vector>& intervals) + { + // Make a flat list of intervals, with each interval having all elements found in it + // TODO: using a vector isn't ideal, since each modification not at front or back is O(n) + std::sort(intervals.begin(), intervals.end()); + auto itr = intervals.begin(); + while (itr != intervals.end()) { - itr = intervals.erase(itr, std::next(nextRange)); // Remove the two source ranges that were split - size_t resetIndex = intervals.size() + splitRanges.size() - 1; // This is where the iterator will be moved to after inserting new ranges - for (const auto& range : splitRanges) + auto currentRange = *itr; + auto nextRange = std::next(itr); + if (nextRange == intervals.end()) // This is the last interval + break; + + if (auto splitRanges = currentRange.split(*nextRange); splitRanges.size()) { - // For each split range, insert it in its sorted position - auto rangeInsertItr = std::upper_bound(intervals.begin(), intervals.end(), range); - size_t rangeInsertIndex = rangeInsertItr - intervals.begin(); - intervals.insert(rangeInsertItr, range); - // Move the reset index to before the lowest inserted range's index; everything before is still sorted - resetIndex = std::min(resetIndex, rangeInsertIndex == 0 ? 0 : rangeInsertIndex - 1); + itr = intervals.erase(itr, std::next(nextRange)); // Remove the two source ranges that were split + size_t resetIndex = intervals.size() + splitRanges.size() - 1; // This is where the iterator will be moved to after inserting new ranges + for (const auto& range : splitRanges) + { + // For each split range, insert it in its sorted position + auto rangeInsertItr = std::upper_bound(intervals.begin(), intervals.end(), range); + size_t rangeInsertIndex = rangeInsertItr - intervals.begin(); + intervals.insert(rangeInsertItr, range); + // Move the reset index to before the lowest inserted range's index; everything before is still sorted + resetIndex = std::min(resetIndex, rangeInsertIndex == 0 ? 0 : rangeInsertIndex - 1); + } + itr = intervals.begin() + resetIndex; } - itr = intervals.begin() + resetIndex; + else + ++itr; } - else - ++itr; } - } - GenericRangeMap() - { - populateRangeMap(); - } - - GenericRangeMap(const vector>& ranges) - { - m_sourceRanges = ranges; - m_flattenedRanges = ranges; - flatten(m_flattenedRanges); - populateRangeMap(); - } - - GenericRangeMap(const vector>& ranges, std::function&)> orderingStrategy) - { - m_sourceRanges = ranges; - m_flattenedRanges = ranges; - flatten(m_flattenedRanges); - if (orderingStrategy) + GenericRangeMap() { - for (auto& i : m_flattenedRanges) - orderingStrategy(i.GetMutableItems()); + populateRangeMap(); } - populateRangeMap(); - } - - const vector>& GetSourceRanges() const { return m_sourceRanges; } - const vector>& GetRanges() const { return m_flattenedRanges; } - const vector& GetItemsAt(uint64_t addr) const - { - if (auto itr = m_rangeMap.upper_bound(addr); itr != m_rangeMap.begin()) + GenericRangeMap(const vector>& ranges) { - --itr; - return itr->second.GetItems(); + m_sourceRanges = ranges; + m_flattenedRanges = ranges; + flatten(m_flattenedRanges); + populateRangeMap(); } - throw std::out_of_range("GenericRangeMap::GetItemsAt - Address not found in any range!"); - } - - const GenericRange& GetGenericRangeAt(uint64_t addr) const - { - if (auto itr = m_rangeMap.upper_bound(addr); itr != m_rangeMap.begin()) + GenericRangeMap(const vector>& ranges, std::function&)> orderingStrategy) { - --itr; - return itr->second; + m_sourceRanges = ranges; + m_flattenedRanges = ranges; + flatten(m_flattenedRanges); + if (orderingStrategy) + { + for (auto& i : m_flattenedRanges) + orderingStrategy(i.GetMutableItems()); + } + populateRangeMap(); } - throw std::out_of_range("GenericRangeMap::GetGenericRangeAt - Address not found in any range!"); - } + const vector>& GetSourceRanges() const { return m_sourceRanges; } + const vector>& GetRanges() const { return m_flattenedRanges; } - GenericRange& GetMutableGenericRangeAt(uint64_t addr) - { - if (auto itr = m_rangeMap.upper_bound(addr); itr != m_rangeMap.begin()) + const vector& GetItemsAt(uint64_t addr) const { - --itr; - return itr->second; + if (auto itr = m_rangeMap.upper_bound(addr); itr != m_rangeMap.begin()) + { + --itr; + return itr->second.GetItems(); + } + + throw std::out_of_range("GenericRangeMap::GetItemsAt - Address not found in any range!"); } - throw std::out_of_range("GenericRangeMap::GetMutableGenericRangeAt - Address not found in any range!"); - } + const GenericRange& GetGenericRangeAt(uint64_t addr) const + { + if (auto itr = m_rangeMap.upper_bound(addr); itr != m_rangeMap.begin()) + { + --itr; + return itr->second; + } - std::optional> GetNextValidRange(uint64_t addr, std::function&)> predicate) const - { - auto itr = m_rangeMap.upper_bound(addr); - if (itr != m_rangeMap.begin()) - --itr; + throw std::out_of_range("GenericRangeMap::GetGenericRangeAt - Address not found in any range!"); + } - while (itr != m_rangeMap.end()) + GenericRange& GetMutableGenericRangeAt(uint64_t addr) { - if (predicate(itr->second)) - return std::make_pair(itr->second.GetStart(), itr->second.GetEnd()); - ++itr; + if (auto itr = m_rangeMap.upper_bound(addr); itr != m_rangeMap.begin()) + { + --itr; + return itr->second; + } + + throw std::out_of_range("GenericRangeMap::GetMutableGenericRangeAt - Address not found in any range!"); } - return std::nullopt; - } + std::optional> GetNextValidRange(uint64_t addr, std::function&)> predicate) const + { + auto itr = m_rangeMap.upper_bound(addr); + if (itr != m_rangeMap.begin()) + --itr; - std::optional> GetPreviousValidRange(uint64_t addr, std::function&)> predicate) const - { - auto itr = m_rangeMap.upper_bound(addr); - if (itr != m_rangeMap.begin()) - --itr; + while (itr != m_rangeMap.end()) + { + if (predicate(itr->second)) + return std::make_pair(itr->second.GetStart(), itr->second.GetEnd()); + ++itr; + } - while (itr != m_rangeMap.begin()) - { - if (predicate(itr->second)) - return std::make_pair(itr->second.GetStart(), itr->second.GetEnd()); - --itr; + return std::nullopt; } - return std::nullopt; - } -}; + std::optional> GetPreviousValidRange(uint64_t addr, std::function&)> predicate) const + { + auto itr = m_rangeMap.upper_bound(addr); + if (itr != m_rangeMap.begin()) + --itr; + + while (itr != m_rangeMap.begin()) + { + if (predicate(itr->second)) + return std::make_pair(itr->second.GetStart(), itr->second.GetEnd()); + --itr; + } + + return std::nullopt; + } + }; #ifdef BINARYNINJACORE_LIBRARY } -- cgit v1.3.1