RangeMap.h: merge RangeDataArray and RangeDataVector

[labath]

Summary

The main difference between the classes was supposed to be the fact that
one is backed by llvm::SmallVector, and the other by std::vector.
However, over the years, they have accumulated various other differences
too.

This essentially removes the std::vector version, as that is pretty much
identical to llvm::SmallVector<T, 0>, and combines their interfaces. It
does not attempt to do a more significant refactoring, even though there
is still a lot of duplication in this file, as it is hard to tell which
quirk of some API is depended on by somebody (and, a previous, more
ambitious attempt at this in D16769 has failed).

I also add some tests, including one which demonstrates one of the
quirks/bugs of the API I have noticed in the process.

[davide]

unittests/Core/RangeMapTest.cpp

52–54

I think this is a bug in the implementation.

[davide]

LG

[labath]

unittests/Core/RangeMapTest.cpp

52–54

I agree. I think this can be fixed if we change the while loop in FindEntryThatContains to loop until the current range start address goes below the lookup address. If that's the behavior we want from this function, that is.

[tberghammer]

LGTM

include/lldb/Core/RangeMap.h

636

Would it make sense to have a default value of 0 for N so people don't have to specify it explicitly?

source/Plugins/Process/elf-core/ProcessElfCore.h

140

Should this be 1 to keep the previous semantics?

[labath]

include/lldb/Core/RangeMap.h

636

I don't have an clear opinion on that. On one hand, 0 seems like a perfectly reasonable default, but on the other SmallVector doesn't have a default either. Everyone typedefs these anyway, so it doesn't really matter.

source/Plugins/Process/elf-core/ProcessElfCore.h

140

If we wanted to be strict then yes, but it seemed weird to have different sizes for the two VMRange maps, when both of them will (hopefully) hold the same number of entries. My guess is that the author here meant "the smallest number possible" and didn't realize that 0 is valid too (or maybe it wasn't valid at that time).

[clayborg]

include/lldb/Core/RangeMap.h

636

Can we default N to be zero?

template <typename B, typename S, typename T, unsigned N=0>

Then remove the zero parameter from many of the changes in this patch?

include/lldb/Symbol/DWARFCallFrameInfo.h

117

We can remove the last zero parameter if we default its value in the template definition

include/lldb/Symbol/LineTable.h

233

We can remove the last zero parameter if we default its value in the template definition

include/lldb/Symbol/Symtab.h

150

We can remove the last zero parameter if we default its value in the template definition

source/Plugins/Process/elf-core/ProcessElfCore.h

139–140

We can remove the last zero parameter if we default its value in the template definition

142

We can remove the last zero parameter if we default its value in the template definition

source/Plugins/Process/mach-core/ProcessMachCore.h

133–134

We can remove the last zero parameter if we default its value in the template definition

136

Ditto

source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h

22

Should this default to zero instead of 1? Not many DWARFDebugAranges will have just a single address.

source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h

443

We can remove the last zero parameter if we default its value in the template definition

source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h

159

We can remove the last zero parameter if we default its value in the template definition

302

We can remove the last zero parameter if we default its value in the template definition

[labath]

Set N=0 default parameter, and remove the size specification from all usages
(including the one in DWARFDebugArranges, where N was 1).

include/lldb/Core/RangeMap.h

struct RangeData : public Range<B, S> {
   }
 
   bool operator!=(const RangeData &rhs) const {
     return this->GetRangeBase() != rhs.GetRangeBase() ||
            this->GetByteSize() != rhs.GetByteSize() || this->data != rhs.data;
   }
 };
 
-template <typename B, typename S, typename T, unsigned N> class RangeDataArray {
+template <typename B, typename S, typename T, unsigned N>
+class RangeDataVector {
 public:
   typedef RangeData<B, S, T> Entry;
   typedef llvm::SmallVector<Entry, N> Collection;
 
-  RangeDataArray() = default;
-
-  ~RangeDataArray() = default;
-
-  void Append(const Entry &entry) { m_entries.push_back(entry); }
-
-  void Sort() {
-    if (m_entries.size() > 1)
-      std::stable_sort(m_entries.begin(), m_entries.end());
-  }
-
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-  bool IsSorted() const {
-    typename Collection::const_iterator pos, end, prev;
-    // First we determine if we can combine any of the Entry objects so we
-    // don't end up allocating and making a new collection for no reason
-    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() {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-    assert(IsSorted());
-#endif
-    typename Collection::iterator pos;
-    typename Collection::iterator end;
-    typename Collection::iterator prev;
-    bool can_combine = false;
-    // First we determine if we can combine any of the Entry objects so we
-    // don't end up allocating and making a new collection for no reason
-    for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
-         prev = pos++) {
-      if (prev != end && prev->data == pos->data) {
-        can_combine = true;
-        break;
-      }
-    }
-
-    // We we can combine at least one entry, then we make a new collection and
-    // populate it accordingly, and then swap it into place.
-    if (can_combine) {
-      Collection minimal_ranges;
-      for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
-           pos != end; prev = pos++) {
-        if (prev != end && prev->data == pos->data)
-          minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd());
-        else
-          minimal_ranges.push_back(*pos);
-      }
-      // Use the swap technique in case our new vector is much smaller. We must
-      // swap when using the STL because std::vector objects never release or
-      // reduce the memory once it has been allocated/reserved.
-      m_entries.swap(minimal_ranges);
-    }
-  }
-
-  void Clear() { m_entries.clear(); }
-
-  bool IsEmpty() const { return m_entries.empty(); }
-
-  size_t GetSize() const { return m_entries.size(); }
-
-  const Entry *GetEntryAtIndex(size_t i) const {
-    return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
-  }
-
-  // Clients must ensure that "i" is a valid index prior to calling this
-  // function
-  const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
-
-  static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
-    return lhs.GetRangeBase() < rhs.GetRangeBase();
-  }
-
-  uint32_t FindEntryIndexThatContains(B addr) const {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-    assert(IsSorted());
-#endif
-    if (!m_entries.empty()) {
-      Entry entry(addr, 1);
-      typename Collection::const_iterator begin = m_entries.begin();
-      typename Collection::const_iterator end = m_entries.end();
-      typename Collection::const_iterator pos =
-          std::lower_bound(begin, end, entry, BaseLessThan);
-
-      if (pos != end && pos->Contains(addr)) {
-        return std::distance(begin, pos);
-      } else if (pos != begin) {
-        --pos;
-        if (pos->Contains(addr))
-          return std::distance(begin, pos);
-      }
-    }
-    return UINT32_MAX;
-  }
-
-  Entry *FindEntryThatContains(B addr) {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-    assert(IsSorted());
-#endif
-    if (!m_entries.empty()) {
-      Entry entry;
-      entry.SetRangeBase(addr);
-      entry.SetByteSize(1);
-      typename Collection::iterator begin = m_entries.begin();
-      typename Collection::iterator end = m_entries.end();
-      typename Collection::iterator pos =
-          std::lower_bound(begin, end, entry, BaseLessThan);
-
-      if (pos != end && pos->Contains(addr)) {
-        return &(*pos);
-      } else if (pos != begin) {
-        --pos;
-        if (pos->Contains(addr)) {
-          return &(*pos);
-        }
-      }
-    }
-    return nullptr;
-  }
-
-  const Entry *FindEntryThatContains(B addr) const {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-    assert(IsSorted());
-#endif
-    if (!m_entries.empty()) {
-      Entry entry;
-      entry.SetRangeBase(addr);
-      entry.SetByteSize(1);
-      typename Collection::const_iterator begin = m_entries.begin();
-      typename Collection::const_iterator end = m_entries.end();
-      typename Collection::const_iterator pos =
-          std::lower_bound(begin, end, entry, BaseLessThan);
-
-      if (pos != end && pos->Contains(addr)) {
-        return &(*pos);
-      } else if (pos != begin) {
-        --pos;
-        if (pos->Contains(addr)) {
-          return &(*pos);
-        }
-      }
-    }
-    return nullptr;
-  }
-
-  const Entry *FindEntryThatContains(const Entry &range) const {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-    assert(IsSorted());
-#endif
-    if (!m_entries.empty()) {
-      typename Collection::const_iterator begin = m_entries.begin();
-      typename Collection::const_iterator end = m_entries.end();
-      typename Collection::const_iterator pos =
-          std::lower_bound(begin, end, range, BaseLessThan);
-
-      if (pos != end && pos->Contains(range)) {
-        return &(*pos);
-      } else if (pos != begin) {
-        --pos;
-        if (pos->Contains(range)) {
-          return &(*pos);
-        }
-      }
-    }
-    return nullptr;
-  }
-
-  Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
-
-  const Entry *Back() const {
-    return (m_entries.empty() ? nullptr : &m_entries.back());
-  }
-
-protected:
-  Collection m_entries;
-};
-
-// Same as RangeDataArray, but uses std::vector as to not require static
-// storage of N items in the class itself
-template <typename B, typename S, typename T> class RangeDataVector {
-public:
-  typedef RangeData<B, S, T> Entry;
-  typedef std::vector<Entry> Collection;
-
   RangeDataVector() = default;
 
   ~RangeDataVector() = default;
 
   void Append(const Entry &entry) { m_entries.push_back(entry); }
 
   void Sort() {
     if (m_entries.size() > 1)
if (can_combine) {
       }
       // Use the swap technique in case our new vector is much smaller. We must
       // swap when using the STL because std::vector objects never release or
       // reduce the memory once it has been allocated/reserved.
       m_entries.swap(minimal_ranges);
     }
   }
 
-  // Calculate the byte size of ranges with zero byte sizes by finding the next
-  // entry with a base address > the current base address
-  void CalculateSizesOfZeroByteSizeRanges(S full_size = 0) {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-    assert(IsSorted());
-#endif
-    typename Collection::iterator pos;
-    typename Collection::iterator end;
-    typename Collection::iterator next;
-    for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) {
-      if (pos->GetByteSize() == 0) {
-        // Watch out for multiple entries with same address and make sure we
-        // find an entry that is greater than the current base address before
-        // we use that for the size
-        auto curr_base = pos->GetRangeBase();
-        for (next = pos + 1; next != end; ++next) {
-          auto next_base = next->GetRangeBase();
-          if (next_base > curr_base) {
-            pos->SetByteSize(next_base - curr_base);
-            break;
-          }
-        }
-        if (next == end && full_size > curr_base)
-          pos->SetByteSize(full_size - curr_base);
-      }
-    }
-  }
-
   void Clear() { m_entries.clear(); }
 
-  void Reserve(typename Collection::size_type size) { m_entries.resize(size); }
-
   bool IsEmpty() const { return m_entries.empty(); }
 
   size_t GetSize() const { return m_entries.size(); }
 
   const Entry *GetEntryAtIndex(size_t i) const {
     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
   }
 
   Entry *GetMutableEntryAtIndex(size_t i) {
     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
   }
 
   // Clients must ensure that "i" is a valid index prior to calling this
   // function
   const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
 
   static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
     return lhs.GetRangeBase() < rhs.GetRangeBase();
   }
 
   uint32_t FindEntryIndexThatContains(B addr) const {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-    assert(IsSorted());
-#endif
-    if (!m_entries.empty()) {
-      Entry entry(addr, 1);
-      typename Collection::const_iterator begin = m_entries.begin();
-      typename Collection::const_iterator end = m_entries.end();
-      typename Collection::const_iterator pos =
-          std::lower_bound(begin, end, entry, BaseLessThan);
-
-      while (pos != begin && pos[-1].Contains(addr))
-        --pos;
-
-      if (pos != end && pos->Contains(addr))
-        return std::distance(begin, pos);
-    }
+    const Entry *entry = FindEntryThatContains(addr);
+    if (entry)
+      return std::distance(m_entries.begin(), entry);
     return UINT32_MAX;
   }
 
   uint32_t FindEntryIndexesThatContain(B addr,
                                        std::vector<uint32_t> &indexes) const {
 #ifdef ASSERT_RANGEMAP_ARE_SORTED
     assert(IsSorted());
 #endif
 
     if (!m_entries.empty()) {
       for (const auto &entry : m_entries) {
         if (entry.Contains(addr))
           indexes.push_back(entry.data);
       }
     }
     return indexes.size();
   }
 
   Entry *FindEntryThatContains(B addr) {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-    assert(IsSorted());
-#endif
-    if (!m_entries.empty()) {
-      Entry entry;
-      entry.SetRangeBase(addr);
-      entry.SetByteSize(1);
-      typename Collection::iterator begin = m_entries.begin();
-      typename Collection::iterator end = m_entries.end();
-      typename Collection::iterator pos =
-          std::lower_bound(begin, end, entry, BaseLessThan);
-
-      while (pos != begin && pos[-1].Contains(addr))
-        --pos;
-
-      if (pos != end && pos->Contains(addr))
-        return &(*pos);
-    }
-    return nullptr;
+    return const_cast<Entry *>(
+        static_cast<const RangeDataVector *>(this)->FindEntryThatContains(
+            addr));
   }
 
   const Entry *FindEntryThatContains(B addr) const {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-    assert(IsSorted());
-#endif
-    if (!m_entries.empty()) {
-      Entry entry;
-      entry.SetRangeBase(addr);
-      entry.SetByteSize(1);
-      typename Collection::const_iterator begin = m_entries.begin();
-      typename Collection::const_iterator end = m_entries.end();
-      typename Collection::const_iterator pos =
-          std::lower_bound(begin, end, entry, BaseLessThan);
-
-      while (pos != begin && pos[-1].Contains(addr))
-        --pos;
-
-      if (pos != end && pos->Contains(addr))
-        return &(*pos);
-    }
-    return nullptr;
+    return FindEntryThatContains(entry);
   }
 
   const Entry *FindEntryThatContains(const Entry &range) const {
 #ifdef ASSERT_RANGEMAP_ARE_SORTED
     assert(IsSorted());
 #endif
     if (!m_entries.empty()) {
       typename Collection::const_iterator begin = m_entries.begin();

include/lldb/Symbol/DWARFCallFrameInfo.h

private:
 
   typedef std::shared_ptr<CIE> CIESP;
 
   typedef std::map<dw_offset_t, CIESP> cie_map_t;
 
   // Start address (file address), size, offset of FDE location used for
   // finding an FDE for a given File address; the start address field is an
   // offset into an individual Module.
-  typedef RangeDataVector<lldb::addr_t, uint32_t, dw_offset_t> FDEEntryMap;
+  typedef RangeDataVector<lldb::addr_t, uint32_t, dw_offset_t, 0> FDEEntryMap;
 
   bool IsEHFrame() const;
 
   bool GetFDEEntryByFileAddress(lldb::addr_t file_offset,
                                 FDEEntryMap::Entry &fde_entry);
 
   void GetFDEIndex();
 

include/lldb/Symbol/LineTable.h

public:
   /// @param[out] file_range_map
   ///     A collection of file ranges that maps to new file ranges
   ///     that will be used when linking the line table.
   ///
   /// @return
   ///     A new line table if at least one line table entry was able
   ///     to be mapped.
   //------------------------------------------------------------------
-  typedef RangeDataVector<lldb::addr_t, lldb::addr_t, lldb::addr_t>
+  typedef RangeDataVector<lldb::addr_t, lldb::addr_t, lldb::addr_t, 0>
       FileRangeMap;
 
   LineTable *LinkLineTable(const FileRangeMap &file_range_map);
 
 protected:
   struct Entry {
     Entry()
         : file_addr(LLDB_INVALID_ADDRESS), line(0), column(0), file_idx(0),

include/lldb/Symbol/Symtab.h

void AppendSymbolNamesToMap(const IndexCollection &indexes,
                               NameToIndexMap &name_to_index_map) const;
 
   ObjectFile *GetObjectFile() { return m_objfile; }
 
 protected:
   typedef std::vector<Symbol> collection;
   typedef collection::iterator iterator;
   typedef collection::const_iterator const_iterator;
-  typedef RangeDataVector<lldb::addr_t, lldb::addr_t, uint32_t>
+  typedef RangeDataVector<lldb::addr_t, lldb::addr_t, uint32_t, 0>
       FileRangeToIndexMap;
   void InitNameIndexes();
   void InitAddressIndexes();
 
   ObjectFile *m_objfile;
   collection m_symbols;
   FileRangeToIndexMap m_file_addr_to_index;
   UniqueCStringMap<uint32_t> m_name_to_index;

source/Plugins/Process/elf-core/ProcessElfCore.h

struct NT_FILE_Entry {
     lldb::addr_t file_ofs;
     lldb_private::ConstString path;
   };
 
   //------------------------------------------------------------------
   // For ProcessElfCore only
   //------------------------------------------------------------------
   typedef lldb_private::Range<lldb::addr_t, lldb::addr_t> FileRange;
-  typedef lldb_private::RangeDataArray<lldb::addr_t, lldb::addr_t, FileRange, 1>
+  typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, FileRange,
+                                        0>
       VMRangeToFileOffset;
-  typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, uint32_t>
+  typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, uint32_t, 0>
       VMRangeToPermissions;
 
   lldb::ModuleSP m_core_module_sp;
   lldb_private::FileSpec m_core_file;
   std::string m_dyld_plugin_name;
   DISALLOW_COPY_AND_ASSIGN(ProcessElfCore);
 
   // True if m_thread_contexts contains valid entries

source/Plugins/Process/mach-core/ProcessMachCore.h

CorefilePreference GetCorefilePreference() {
     // process dyld in one of its pages.
     return eKernelCorefile;
   }
 
   //------------------------------------------------------------------
   // For ProcessMachCore only
   //------------------------------------------------------------------
   typedef lldb_private::Range<lldb::addr_t, lldb::addr_t> FileRange;
-  typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, FileRange>
+  typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, FileRange,
+                                        0>
       VMRangeToFileOffset;
-  typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, uint32_t>
+  typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, uint32_t, 0>
       VMRangeToPermissions;
 
   VMRangeToFileOffset m_core_aranges;
   VMRangeToPermissions m_core_range_infos;
   lldb::ModuleSP m_core_module_sp;
   lldb_private::FileSpec m_core_file;
   lldb::addr_t m_dyld_addr;
   lldb::addr_t m_mach_kernel_addr;
   lldb_private::ConstString m_dyld_plugin_name;
 
   DISALLOW_COPY_AND_ASSIGN(ProcessMachCore);
 };
 
 #endif // liblldb_ProcessMachCore_h_

source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h

 #include <list>
 
 #include "lldb/Core/RangeMap.h"
 
 class SymbolFileDWARF;
 
 class DWARFDebugAranges {
 protected:
-  typedef lldb_private::RangeDataArray<dw_addr_t, uint32_t, dw_offset_t, 1>
+  typedef lldb_private::RangeDataVector<dw_addr_t, uint32_t, dw_offset_t, 1>
       RangeToDIE;
 
 public:
   typedef RangeToDIE::Entry Range;
   typedef std::vector<RangeToDIE::Entry> RangeColl;
 
   DWARFDebugAranges();
 

source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h

protected:
 
   typedef std::set<lldb_private::Type *> TypeSet;
 
   void GetTypes(const DWARFDIE &die, dw_offset_t min_die_offset,
                 dw_offset_t max_die_offset, uint32_t type_mask,
                 TypeSet &type_set);
 
   typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t,
-                                        lldb_private::Variable *>
+                                        lldb_private::Variable *, 0>
       GlobalVariableMap;
 
   GlobalVariableMap &GetGlobalAranges();
 
   void UpdateExternalModuleListIfNeeded();
 
   virtual DIEToTypePtr &GetDIEToType() { return m_die_to_type; }
 

source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h

struct OSOInfo {
     lldb::ModuleSP module_sp;
 
     OSOInfo() : module_sp() {}
   };
 
   typedef std::shared_ptr<OSOInfo> OSOInfoSP;
 
   typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t,
-                                        lldb::addr_t>
+                                        lldb::addr_t, 0>
       FileRangeMap;
 
   //------------------------------------------------------------------
   // Class specific types
   //------------------------------------------------------------------
   struct CompileUnitInfo {
     lldb_private::FileSpec so_file;
     lldb_private::ConstString oso_path;
void SetOSOFileAddress(lldb::addr_t oso_file_addr) {
       m_oso_file_addr = oso_file_addr;
     }
 
   protected:
     uint32_t m_exe_sym_idx;
     lldb::addr_t m_oso_file_addr;
   };
 
-  typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, OSOEntry>
+  typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, OSOEntry, 0>
       DebugMap;
 
   //------------------------------------------------------------------
   // Member Variables
   //------------------------------------------------------------------
   std::bitset<kNumFlags> m_flags;
   std::vector<CompileUnitInfo> m_compile_unit_infos;
   std::vector<uint32_t> m_func_indexes; // Sorted by address

unittests/Core/CMakeLists.txt

 add_lldb_unittest(LLDBCoreTests
   MangledTest.cpp
+  RangeMapTest.cpp
   RangeTest.cpp
   RichManglingContextTest.cpp
   StreamCallbackTest.cpp
 
   LINK_LIBS
     lldbCore
     lldbHost
     lldbSymbol

unittests/Core/RangeMapTest.cpp

+//===-- RangeTest.cpp ----------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "lldb/Core/RangeMap.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+using namespace lldb_private;
+
+using RangeDataVectorT = RangeDataVector<uint32_t, uint32_t, uint32_t, 0>;
+using EntryT = RangeDataVectorT::Entry;
+
+static testing::Matcher<const EntryT *> EntryIs(uint32_t ID) {
+  return testing::Pointee(testing::Field(&EntryT::data, ID));
+}
+
+TEST(RangeDataVector, FindEntryThatContains) {
+  RangeDataVectorT Map;
+  uint32_t NextID = 0;
+  Map.Append(EntryT(0, 10, NextID++));
+  Map.Append(EntryT(10, 10, NextID++));
+  Map.Append(EntryT(20, 10, NextID++));
+  Map.Sort();
+
+  EXPECT_THAT(Map.FindEntryThatContains(0), EntryIs(0));
+  EXPECT_THAT(Map.FindEntryThatContains(9), EntryIs(0));
+  EXPECT_THAT(Map.FindEntryThatContains(10), EntryIs(1));
+  EXPECT_THAT(Map.FindEntryThatContains(19), EntryIs(1));
+  EXPECT_THAT(Map.FindEntryThatContains(20), EntryIs(2));
+  EXPECT_THAT(Map.FindEntryThatContains(29), EntryIs(2));
+  EXPECT_THAT(Map.FindEntryThatContains(30), nullptr);
+}
+
+TEST(RangeDataVector, FindEntryThatContains_Overlap) {
+  RangeDataVectorT Map;
+  uint32_t NextID = 0;
+  Map.Append(EntryT(0, 40, NextID++));
+  Map.Append(EntryT(10, 20, NextID++));
+  Map.Append(EntryT(20, 10, NextID++));
+  Map.Sort();
+
+  // With overlapping intervals, the intention seems to be to return the first
+  // interval which contains the address.
+  EXPECT_THAT(Map.FindEntryThatContains(25), EntryIs(0));
+
+  // However, this does not always succeed.
+  // TODO: This should probably return the range (0, 40) as well.
+  EXPECT_THAT(Map.FindEntryThatContains(35), nullptr);
+}