llvm/lldb/include/lldb/Utility/RangeMap.h

//===-- RangeMap.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 LLDB_UTILITY_RANGEMAP_H
#define LLDB_UTILITY_RANGEMAP_H

#include <algorithm>
#include <vector>

#include "llvm/ADT/SmallVector.h"

#include "lldb/lldb-private.h"

// Uncomment to make sure all Range objects are sorted when needed
//#define ASSERT_RANGEMAP_ARE_SORTED

namespace lldb_private {

// Templatized classes for dealing with generic ranges and also collections of
// ranges, or collections of ranges that have associated data.

// A simple range class where you get to define the type of the range
// base "B", and the type used for the range byte size "S".
template <typename B, typename S> struct Range { … };

template <typename B, typename S, unsigned N = 0> class RangeVector { … };

// A simple range  with data class where you get to define the type of
// the range base "B", the type used for the range byte size "S", and the type
// for the associated data "T".
template <typename B, typename S, typename T>
struct RangeData : public Range<B, S> { … };

// We can treat the vector as a flattened Binary Search Tree, augmenting it
// with upper bounds (max of range endpoints) for every index allows us to
// query for range containment quicker.
template <typename B, typename S, typename T>
struct AugmentedRangeData : public RangeData<B, S, T> { … };

template <typename B, typename S, typename T, unsigned N = 0,
          class Compare = std::less<T>>
class RangeDataVector {
public:
  typedef lldb_private::Range<B, S> Range;
  typedef RangeData<B, S, T> Entry;
  typedef AugmentedRangeData<B, S, T> AugmentedEntry;
  typedef llvm::SmallVector<AugmentedEntry, N> Collection;

  RangeDataVector(Compare compare = Compare()) : … { … }

  ~RangeDataVector() = default;

  void Append(const Entry &entry) { … }

  /// Append a range with data to the vector
  /// \param B The base of the memory range
  /// \param S The size of the memory range
  /// \param T The data associated with the memory range
  void Append(B &&b, S &&s, T &&t) { … }

  bool Erase(uint32_t start, uint32_t end) { … }

  void Sort() { … }

#ifdef ASSERT_RANGEMAP_ARE_SORTED
  bool IsSorted() const {
    typename Collection::const_iterator pos, end, prev;
    for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
         prev = pos++) {
      if (prev != end && *pos < *prev)
        return false;
    }
    return true;
  }
#endif

  void CombineConsecutiveEntriesWithEqualData() { … }

  void Clear() { … }

  bool IsEmpty() const { … }

  size_t GetSize() const { … }

  const Entry *GetEntryAtIndex(size_t i) const { … }

  Entry *GetMutableEntryAtIndex(size_t i) { … }

  // Clients must ensure that "i" is a valid index prior to calling this
  // function
  Entry &GetEntryRef(size_t i) { … }
  const Entry &GetEntryRef(size_t i) const { … }

  static bool BaseLessThan(const Entry &lhs, const Entry &rhs) { … }

  uint32_t FindEntryIndexThatContains(B addr) const { … }

  uint32_t FindEntryIndexesThatContain(B addr, std::vector<uint32_t> &indexes) { … }

  Entry *FindEntryThatContains(B addr) { … }

  const Entry *FindEntryThatContains(B addr) const { … }

  const Entry *FindEntryThatContains(const Entry &range) const { … }

  const Entry *FindEntryStartsAt(B addr) const { … }

  // This method will return the entry that contains the given address, or the
  // entry following that address.  If you give it an address of 0 and the
  // first entry starts at address 0x100, you will get the entry at 0x100.
  //
  // For most uses, FindEntryThatContains is the correct one to use, this is a
  // less commonly needed behavior.  It was added for core file memory regions,
  // where we want to present a gap in the memory regions as a distinct region,
  // so we need to know the start address of the next memory section that
  // exists.
  const Entry *FindEntryThatContainsOrFollows(B addr) const { … }

  uint32_t FindEntryIndexThatContainsOrFollows(B addr) const { … }

  Entry *Back() { … }

  const Entry *Back() const { … }

  using const_iterator = typename Collection::const_iterator;
  const_iterator begin() const { … }
  const_iterator end() const { … }

protected:
  Collection m_entries;
  Compare m_compare;

private:
  // Compute extra information needed for search
  B ComputeUpperBounds(size_t lo, size_t hi) { … }

  // This is based on the augmented tree implementation found at
  // https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
  void FindEntryIndexesThatContain(B addr, size_t lo, size_t hi,
                                   std::vector<uint32_t> &indexes) { … }
};

// A simple range  with data class where you get to define the type of
// the range base "B", the type used for the range byte size "S", and the type
// for the associated data "T".
template <typename B, typename T> struct AddressData { … };

template <typename B, typename T, unsigned N> class AddressDataArray { … };

} // namespace lldb_private

#endif // LLDB_UTILITY_RANGEMAP_H