Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  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.