This revision was automatically updated to reflect the committed changes. Closed by commit rL355509: Move RangeMap.h into Utility (authored by labath, committed by ). Herald added subscribers: llvm-commits, jdoerfert. Herald added a project: LLVM.
Changed prior to commit: https://reviews.llvm.org/D58970?vs=189328&id=189501#toc Repository: rL LLVM CHANGES SINCE LAST ACTION https://reviews.llvm.org/D58970/new/ https://reviews.llvm.org/D58970 Files: lldb/trunk/include/lldb/Core/RangeMap.h lldb/trunk/include/lldb/Core/dwarf.h lldb/trunk/include/lldb/Symbol/ArmUnwindInfo.h lldb/trunk/include/lldb/Symbol/Block.h lldb/trunk/include/lldb/Symbol/CompactUnwindInfo.h lldb/trunk/include/lldb/Symbol/DWARFCallFrameInfo.h lldb/trunk/include/lldb/Symbol/LineTable.h lldb/trunk/include/lldb/Symbol/Symtab.h lldb/trunk/include/lldb/Symbol/Variable.h lldb/trunk/include/lldb/Target/Memory.h lldb/trunk/include/lldb/Target/MemoryRegionInfo.h lldb/trunk/include/lldb/Utility/RangeMap.h lldb/trunk/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp lldb/trunk/source/Plugins/ObjectFile/JIT/ObjectFileJIT.cpp lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.h lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h lldb/trunk/source/Target/Memory.cpp lldb/trunk/unittests/Core/CMakeLists.txt lldb/trunk/unittests/Core/RangeMapTest.cpp lldb/trunk/unittests/Core/RangeTest.cpp lldb/trunk/unittests/Utility/CMakeLists.txt lldb/trunk/unittests/Utility/RangeMapTest.cpp lldb/trunk/unittests/Utility/RangeTest.cpp
Index: lldb/trunk/unittests/Utility/RangeMapTest.cpp =================================================================== --- lldb/trunk/unittests/Utility/RangeMapTest.cpp +++ lldb/trunk/unittests/Utility/RangeMapTest.cpp @@ -0,0 +1,54 @@ +//===-- RangeTest.cpp ----------------------------------------*- 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 +// +//===----------------------------------------------------------------------===// + +#include "lldb/Utility/RangeMap.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" + +using namespace lldb_private; + +using RangeDataVectorT = RangeDataVector<uint32_t, uint32_t, uint32_t>; +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); +} Index: lldb/trunk/unittests/Utility/CMakeLists.txt =================================================================== --- lldb/trunk/unittests/Utility/CMakeLists.txt +++ lldb/trunk/unittests/Utility/CMakeLists.txt @@ -19,6 +19,8 @@ NameMatchesTest.cpp PredicateTest.cpp ProcessInfoTest.cpp + RangeMapTest.cpp + RangeTest.cpp RegisterValueTest.cpp ReproducerTest.cpp ReproducerInstrumentationTest.cpp Index: lldb/trunk/unittests/Utility/RangeTest.cpp =================================================================== --- lldb/trunk/unittests/Utility/RangeTest.cpp +++ lldb/trunk/unittests/Utility/RangeTest.cpp @@ -0,0 +1,328 @@ +//===-- RangeTest.cpp ----------------------------------------*- 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 +// +//===----------------------------------------------------------------------===// + +#include "lldb/Utility/RangeMap.h" +#include <cstdint> +#include <type_traits> + +#include "gtest/gtest.h" + +using namespace lldb; +using namespace lldb_private; + +TEST(RangeTest, SizeTypes) { + Range<lldb::addr_t, uint32_t> r; + static_assert(std::is_same<lldb::addr_t, decltype(r.GetRangeBase())>::value, + "RangeBase type is not equal to the given one."); + static_assert(std::is_same<lldb::addr_t, decltype(r.GetRangeEnd())>::value, + "RangeEnd type is not equal to the given one."); + static_assert(std::is_same<uint32_t, decltype(r.GetByteSize())>::value, + "Size type is not equal to the given one."); +} + +typedef Range<lldb::addr_t, uint32_t> RangeT; + +TEST(RangeTest, DefaultConstructor) { + RangeT r; + EXPECT_FALSE(r.IsValid()); + EXPECT_EQ(0U, r.GetByteSize()); + EXPECT_EQ(0U, r.GetRangeBase()); + EXPECT_EQ(0U, r.GetRangeEnd()); +} + +TEST(RangeTest, Constructor) { + RangeT r(3, 5); + EXPECT_TRUE(r.IsValid()); + EXPECT_EQ(5U, r.GetByteSize()); + EXPECT_EQ(3U, r.GetRangeBase()); + EXPECT_EQ(8U, r.GetRangeEnd()); +} + +TEST(RangeTest, Copy) { + RangeT orig(3, 5); + RangeT r = orig; + EXPECT_TRUE(r.IsValid()); + EXPECT_EQ(5U, r.GetByteSize()); + EXPECT_EQ(3U, r.GetRangeBase()); + EXPECT_EQ(8U, r.GetRangeEnd()); +} + +TEST(RangeTest, Clear) { + RangeT r(3, 5); + r.Clear(); + EXPECT_TRUE(r == RangeT()); +} + +TEST(RangeTest, ClearWithStarAddress) { + RangeT r(3, 5); + r.Clear(4); + EXPECT_TRUE(r == RangeT(4, 0)); +} + +TEST(RangeTest, SetRangeBase) { + RangeT r(3, 5); + r.SetRangeBase(6); + EXPECT_EQ(6U, r.GetRangeBase()); + EXPECT_EQ(11U, r.GetRangeEnd()); + EXPECT_EQ(5U, r.GetByteSize()); +} + +TEST(RangeTest, Slide) { + RangeT r(3, 5); + r.Slide(1); + EXPECT_EQ(4U, r.GetRangeBase()); + EXPECT_EQ(9U, r.GetRangeEnd()); + EXPECT_EQ(5U, r.GetByteSize()); + + r.Slide(2); + EXPECT_EQ(6U, r.GetRangeBase()); + EXPECT_EQ(11U, r.GetRangeEnd()); + EXPECT_EQ(5U, r.GetByteSize()); +} + +TEST(RangeTest, SlideZero) { + RangeT r(3, 5); + r.Slide(0); + EXPECT_EQ(3U, r.GetRangeBase()); + EXPECT_EQ(8U, r.GetRangeEnd()); + EXPECT_EQ(5U, r.GetByteSize()); +} + +TEST(RangeTest, ContainsAddr) { + RangeT r(3, 5); + EXPECT_FALSE(r.Contains(0)); + EXPECT_FALSE(r.Contains(1)); + EXPECT_FALSE(r.Contains(2)); + EXPECT_TRUE(r.Contains(3)); + EXPECT_TRUE(r.Contains(4)); + EXPECT_TRUE(r.Contains(5)); + EXPECT_TRUE(r.Contains(6)); + EXPECT_TRUE(r.Contains(7)); + EXPECT_FALSE(r.Contains(8)); + EXPECT_FALSE(r.Contains(9)); + EXPECT_FALSE(r.Contains(10)); +} + +TEST(RangeTest, ContainsAddrInvalid) { + RangeT r; + EXPECT_FALSE(r.Contains(0)); + EXPECT_FALSE(r.Contains(1)); + EXPECT_FALSE(r.Contains(2)); + EXPECT_FALSE(r.Contains(3)); + EXPECT_FALSE(r.Contains(4)); +} + +TEST(RangeTest, ContainsEndInclusive) { + RangeT r(3, 5); + EXPECT_FALSE(r.ContainsEndInclusive(0)); + EXPECT_FALSE(r.ContainsEndInclusive(1)); + EXPECT_FALSE(r.ContainsEndInclusive(2)); + EXPECT_TRUE(r.ContainsEndInclusive(3)); + EXPECT_TRUE(r.ContainsEndInclusive(4)); + EXPECT_TRUE(r.ContainsEndInclusive(5)); + EXPECT_TRUE(r.ContainsEndInclusive(6)); + EXPECT_TRUE(r.ContainsEndInclusive(7)); + EXPECT_TRUE(r.ContainsEndInclusive(8)); + EXPECT_FALSE(r.ContainsEndInclusive(9)); + EXPECT_FALSE(r.ContainsEndInclusive(10)); +} + +TEST(RangeTest, ContainsEndInclusiveInvalid) { + RangeT r; + // FIXME: This is probably not intended. + EXPECT_TRUE(r.ContainsEndInclusive(0)); + + EXPECT_FALSE(r.ContainsEndInclusive(1)); + EXPECT_FALSE(r.ContainsEndInclusive(2)); +} + +TEST(RangeTest, ContainsRange) { + RangeT r(3, 5); + + // Range always contains itself. + EXPECT_TRUE(r.Contains(r)); + // Invalid range. + EXPECT_FALSE(r.Contains(RangeT())); + // Range starts and ends before. + EXPECT_FALSE(r.Contains(RangeT(0, 3))); + // Range starts before but contains beginning. + EXPECT_FALSE(r.Contains(RangeT(0, 4))); + // Range starts before but contains beginning and more. + EXPECT_FALSE(r.Contains(RangeT(0, 5))); + // Range starts before and contains the other. + EXPECT_FALSE(r.Contains(RangeT(0, 9))); + // Range is fully inside. + EXPECT_TRUE(r.Contains(RangeT(4, 3))); + // Range has same start, but not as large. + EXPECT_TRUE(r.Contains(RangeT(3, 4))); + // Range has same end, but starts earlier. + EXPECT_TRUE(r.Contains(RangeT(4, 4))); + // Range starts inside, but stops after the end of r. + EXPECT_FALSE(r.Contains(RangeT(4, 5))); + // Range starts directly after r. + EXPECT_FALSE(r.Contains(RangeT(8, 2))); + // Range starts directly after r. + EXPECT_FALSE(r.Contains(RangeT(9, 2))); + + // Invalid range with different start. + // FIXME: The first two probably not intended. + EXPECT_TRUE(r.Contains(RangeT(3, 0))); + EXPECT_TRUE(r.Contains(RangeT(4, 0))); + EXPECT_FALSE(r.Contains(RangeT(8, 0))); +} + +TEST(RangeTest, ContainsRangeStartingFromZero) { + RangeT r(0, 3); + EXPECT_TRUE(r.Contains(r)); + + // FIXME: This is probably not intended. + EXPECT_TRUE(r.Contains(RangeT())); +} + +TEST(RangeTest, Union) { + RangeT r(3, 5); + + // Ranges that we can't merge because it's not adjoin/intersecting. + EXPECT_FALSE(r.Union(RangeT(9, 1))); + // Check that we didn't modify our range. + EXPECT_EQ(r, RangeT(3, 5)); + + // Another range we can't merge, but before r. + EXPECT_FALSE(r.Union(RangeT(1, 1))); + EXPECT_EQ(r, RangeT(3, 5)); + + // Merge an adjoin range after. + EXPECT_TRUE(r.Union(RangeT(8, 2))); + EXPECT_EQ(r, RangeT(3, 7)); + + // Merge an adjoin range before. + EXPECT_TRUE(r.Union(RangeT(1, 2))); + EXPECT_EQ(r, RangeT(1, 9)); + + // Merge an intersecting range after. + EXPECT_TRUE(r.Union(RangeT(8, 3))); + EXPECT_EQ(r, RangeT(1, 10)); + + // Merge an intersecting range before. + EXPECT_TRUE(r.Union(RangeT(0, 1))); + EXPECT_EQ(r, RangeT(0, 11)); + + // Merge a few ranges inside that shouldn't do anything. + EXPECT_TRUE(r.Union(RangeT(0, 3))); + EXPECT_EQ(r, RangeT(0, 11)); + EXPECT_TRUE(r.Union(RangeT(5, 1))); + EXPECT_EQ(r, RangeT(0, 11)); + EXPECT_TRUE(r.Union(RangeT(9, 2))); + EXPECT_EQ(r, RangeT(0, 11)); +} + +TEST(RangeTest, DoesAdjoinOrIntersect) { + RangeT r(3, 4); + + EXPECT_FALSE(r.DoesAdjoinOrIntersect(RangeT(1, 1))); + EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(1, 2))); + EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(2, 2))); + EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(4, 2))); + EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(6, 2))); + EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(7, 2))); + EXPECT_FALSE(r.DoesAdjoinOrIntersect(RangeT(8, 2))); +} + +TEST(RangeTest, DoesIntersect) { + RangeT r(3, 4); + + EXPECT_FALSE(r.DoesIntersect(RangeT(1, 1))); + EXPECT_FALSE(r.DoesIntersect(RangeT(1, 2))); + EXPECT_TRUE(r.DoesIntersect(RangeT(2, 2))); + EXPECT_TRUE(r.DoesIntersect(RangeT(4, 2))); + EXPECT_TRUE(r.DoesIntersect(RangeT(6, 2))); + EXPECT_FALSE(r.DoesIntersect(RangeT(7, 2))); + EXPECT_FALSE(r.DoesIntersect(RangeT(8, 2))); +} + +TEST(RangeTest, LessThan) { + RangeT r(10, 20); + + // Equal range. + EXPECT_FALSE(r < RangeT(10, 20)); + EXPECT_FALSE(RangeT(10, 20) < r); + + auto expect_ordered_less_than = [](RangeT r1, RangeT r2) { + EXPECT_TRUE(r1 < r2); + EXPECT_FALSE(r2 < r1); + }; + + // Same start, but bigger size. + expect_ordered_less_than(r, RangeT(10, 21)); + + // Start before and ends before. + expect_ordered_less_than(RangeT(9, 20), r); + + // Start before and equal size. + expect_ordered_less_than(RangeT(9, 21), r); + + // Start before and bigger size. + expect_ordered_less_than(RangeT(9, 22), r); + + // Start after and ends before. + expect_ordered_less_than(r, RangeT(11, 18)); + + // Start after and equal size. + expect_ordered_less_than(r, RangeT(11, 19)); + + // Start after and bigger size. + expect_ordered_less_than(r, RangeT(11, 20)); +} + +TEST(RangeTest, Equal) { + RangeT r(10, 20); + + // Equal range. + EXPECT_TRUE(r == RangeT(10, 20)); + + // Same start, different size. + EXPECT_FALSE(r == RangeT(10, 21)); + + // Different start, same size. + EXPECT_FALSE(r == RangeT(9, 20)); + + // Different start, different size. + EXPECT_FALSE(r == RangeT(9, 21)); + EXPECT_FALSE(r == RangeT(11, 19)); +} + +TEST(RangeTest, NotEqual) { + RangeT r(10, 20); + + EXPECT_FALSE(r != RangeT(10, 20)); + + EXPECT_TRUE(r != RangeT(10, 21)); + EXPECT_TRUE(r != RangeT(9, 20)); + EXPECT_TRUE(r != RangeT(9, 21)); +} + +// Comparison tests for invalid ranges (size == 0). + +TEST(RangeTest, LessThanInvalid) { + EXPECT_TRUE(RangeT() < RangeT(1, 0)); + EXPECT_TRUE(RangeT() < RangeT(2, 0)); + EXPECT_TRUE(RangeT(1, 0) < RangeT(2, 0)); +} + +TEST(RangeTest, EqualInvalid) { + RangeT r; + EXPECT_TRUE(r == RangeT()); + // Another invalid range, but with a different start. + EXPECT_FALSE(r == RangeT(3, 0)); +} + +TEST(RangeTest, NotEqualInvalid) { + RangeT r; + EXPECT_FALSE(r != RangeT()); + EXPECT_FALSE(r == RangeT(3, 0)); +} Index: lldb/trunk/unittests/Core/CMakeLists.txt =================================================================== --- lldb/trunk/unittests/Core/CMakeLists.txt +++ lldb/trunk/unittests/Core/CMakeLists.txt @@ -1,7 +1,5 @@ add_lldb_unittest(LLDBCoreTests MangledTest.cpp - RangeMapTest.cpp - RangeTest.cpp RichManglingContextTest.cpp StreamCallbackTest.cpp Index: lldb/trunk/source/Target/Memory.cpp =================================================================== --- lldb/trunk/source/Target/Memory.cpp +++ lldb/trunk/source/Target/Memory.cpp @@ -7,11 +7,10 @@ //===----------------------------------------------------------------------===// #include "lldb/Target/Memory.h" - -#include "lldb/Core/RangeMap.h" #include "lldb/Target/Process.h" #include "lldb/Utility/DataBufferHeap.h" #include "lldb/Utility/Log.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/State.h" #include <cinttypes> Index: lldb/trunk/source/Plugins/ObjectFile/JIT/ObjectFileJIT.cpp =================================================================== --- lldb/trunk/source/Plugins/ObjectFile/JIT/ObjectFileJIT.cpp +++ lldb/trunk/source/Plugins/ObjectFile/JIT/ObjectFileJIT.cpp @@ -14,7 +14,6 @@ #include "lldb/Core/Module.h" #include "lldb/Core/ModuleSpec.h" #include "lldb/Core/PluginManager.h" -#include "lldb/Core/RangeMap.h" #include "lldb/Core/Section.h" #include "lldb/Core/StreamFile.h" #include "lldb/Host/Host.h" @@ -28,6 +27,7 @@ #include "lldb/Utility/DataBufferHeap.h" #include "lldb/Utility/FileSpec.h" #include "lldb/Utility/Log.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/StreamString.h" #include "lldb/Utility/Timer.h" #include "lldb/Utility/UUID.h" Index: lldb/trunk/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp =================================================================== --- lldb/trunk/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp +++ lldb/trunk/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp @@ -16,7 +16,6 @@ #include "lldb/Core/Module.h" #include "lldb/Core/ModuleSpec.h" #include "lldb/Core/PluginManager.h" -#include "lldb/Core/RangeMap.h" #include "lldb/Core/Section.h" #include "lldb/Host/FileSystem.h" #include "lldb/Symbol/DWARFCallFrameInfo.h" @@ -26,6 +25,7 @@ #include "lldb/Utility/ArchSpec.h" #include "lldb/Utility/DataBufferHeap.h" #include "lldb/Utility/Log.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/Status.h" #include "lldb/Utility/Stream.h" #include "lldb/Utility/Timer.h" Index: lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.h =================================================================== --- lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.h +++ lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.h @@ -11,10 +11,10 @@ #include "lldb/Core/Address.h" #include "lldb/Core/FileSpecList.h" -#include "lldb/Core/RangeMap.h" #include "lldb/Host/SafeMachO.h" #include "lldb/Symbol/ObjectFile.h" #include "lldb/Utility/FileSpec.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/UUID.h" //---------------------------------------------------------------------- Index: lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp =================================================================== --- lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp +++ lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp @@ -17,7 +17,6 @@ #include "lldb/Core/Module.h" #include "lldb/Core/ModuleSpec.h" #include "lldb/Core/PluginManager.h" -#include "lldb/Core/RangeMap.h" #include "lldb/Core/Section.h" #include "lldb/Core/StreamFile.h" #include "lldb/Host/Host.h" @@ -35,6 +34,7 @@ #include "lldb/Utility/DataBuffer.h" #include "lldb/Utility/FileSpec.h" #include "lldb/Utility/Log.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/RegisterValue.h" #include "lldb/Utility/Status.h" #include "lldb/Utility/StreamString.h" Index: lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp =================================================================== --- lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp +++ lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp @@ -12,9 +12,9 @@ #include "lldb/Core/Module.h" #include "lldb/Core/ModuleList.h" #include "lldb/Core/PluginManager.h" -#include "lldb/Core/RangeMap.h" #include "lldb/Core/Section.h" #include "lldb/Host/FileSystem.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/RegularExpression.h" #include "lldb/Utility/Timer.h" Index: lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h =================================================================== --- lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h +++ lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h @@ -10,10 +10,9 @@ #define SymbolFileDWARF_DWARFDebugAranges_h_ #include "DWARFDebugArangeSet.h" +#include "lldb/Utility/RangeMap.h" #include <list> -#include "lldb/Core/RangeMap.h" - class SymbolFileDWARF; class DWARFDebugAranges { Index: lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h =================================================================== --- lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h +++ lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h @@ -19,9 +19,6 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/Support/Threading.h" -#include "lldb/Utility/Flags.h" - -#include "lldb/Core/RangeMap.h" #include "lldb/Core/UniqueCStringMap.h" #include "lldb/Core/dwarf.h" #include "lldb/Expression/DWARFExpression.h" @@ -29,6 +26,8 @@ #include "lldb/Symbol/SymbolContext.h" #include "lldb/Symbol/SymbolFile.h" #include "lldb/Utility/ConstString.h" +#include "lldb/Utility/Flags.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/lldb-private.h" #include "DWARFDataExtractor.h" Index: lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h =================================================================== --- lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h +++ lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h @@ -9,14 +9,13 @@ #ifndef SymbolFileDWARF_SymbolFileDWARFDebugMap_h_ #define SymbolFileDWARF_SymbolFileDWARFDebugMap_h_ +#include "lldb/Symbol/SymbolFile.h" +#include "lldb/Utility/RangeMap.h" +#include "llvm/Support/Chrono.h" #include <bitset> #include <map> #include <vector> -#include "lldb/Core/RangeMap.h" -#include "lldb/Symbol/SymbolFile.h" -#include "llvm/Support/Chrono.h" - #include "UniqueDWARFASTType.h" class SymbolFileDWARF; Index: lldb/trunk/include/lldb/Symbol/CompactUnwindInfo.h =================================================================== --- lldb/trunk/include/lldb/Symbol/CompactUnwindInfo.h +++ lldb/trunk/include/lldb/Symbol/CompactUnwindInfo.h @@ -9,14 +9,13 @@ #ifndef liblldb_CompactUnwindInfo_h_ #define liblldb_CompactUnwindInfo_h_ -#include <mutex> -#include <vector> - -#include "lldb/Core/RangeMap.h" #include "lldb/Symbol/ObjectFile.h" #include "lldb/Symbol/UnwindPlan.h" #include "lldb/Utility/DataExtractor.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/lldb-private.h" +#include <mutex> +#include <vector> namespace lldb_private { Index: lldb/trunk/include/lldb/Symbol/DWARFCallFrameInfo.h =================================================================== --- lldb/trunk/include/lldb/Symbol/DWARFCallFrameInfo.h +++ lldb/trunk/include/lldb/Symbol/DWARFCallFrameInfo.h @@ -13,12 +13,11 @@ #include <mutex> #include "lldb/Core/AddressRange.h" -#include "lldb/Utility/Flags.h" - -#include "lldb/Core/RangeMap.h" #include "lldb/Core/dwarf.h" #include "lldb/Symbol/ObjectFile.h" #include "lldb/Symbol/UnwindPlan.h" +#include "lldb/Utility/Flags.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/VMRange.h" #include "lldb/lldb-private.h" Index: lldb/trunk/include/lldb/Symbol/LineTable.h =================================================================== --- lldb/trunk/include/lldb/Symbol/LineTable.h +++ lldb/trunk/include/lldb/Symbol/LineTable.h @@ -9,13 +9,12 @@ #ifndef liblldb_LineTable_h_ #define liblldb_LineTable_h_ -#include <vector> - #include "lldb/Core/ModuleChild.h" -#include "lldb/Core/RangeMap.h" #include "lldb/Core/Section.h" #include "lldb/Symbol/LineEntry.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/lldb-private.h" +#include <vector> namespace lldb_private { Index: lldb/trunk/include/lldb/Symbol/Symtab.h =================================================================== --- lldb/trunk/include/lldb/Symbol/Symtab.h +++ lldb/trunk/include/lldb/Symbol/Symtab.h @@ -9,13 +9,12 @@ #ifndef liblldb_Symtab_h_ #define liblldb_Symtab_h_ -#include <mutex> -#include <vector> - -#include "lldb/Core/RangeMap.h" #include "lldb/Core/UniqueCStringMap.h" #include "lldb/Symbol/Symbol.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/lldb-private.h" +#include <mutex> +#include <vector> namespace lldb_private { Index: lldb/trunk/include/lldb/Symbol/Block.h =================================================================== --- lldb/trunk/include/lldb/Symbol/Block.h +++ lldb/trunk/include/lldb/Symbol/Block.h @@ -9,17 +9,16 @@ #ifndef liblldb_Block_h_ #define liblldb_Block_h_ -#include <vector> - #include "lldb/Core/AddressRange.h" -#include "lldb/Core/RangeMap.h" #include "lldb/Symbol/CompilerType.h" #include "lldb/Symbol/LineEntry.h" #include "lldb/Symbol/SymbolContext.h" #include "lldb/Symbol/SymbolContextScope.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/Stream.h" #include "lldb/Utility/UserID.h" #include "lldb/lldb-private.h" +#include <vector> namespace lldb_private { Index: lldb/trunk/include/lldb/Symbol/Variable.h =================================================================== --- lldb/trunk/include/lldb/Symbol/Variable.h +++ lldb/trunk/include/lldb/Symbol/Variable.h @@ -9,17 +9,16 @@ #ifndef liblldb_Variable_h_ #define liblldb_Variable_h_ -#include <memory> -#include <vector> - #include "lldb/Core/Mangled.h" -#include "lldb/Core/RangeMap.h" #include "lldb/Expression/DWARFExpression.h" #include "lldb/Symbol/Declaration.h" #include "lldb/Utility/CompletionRequest.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/UserID.h" #include "lldb/lldb-enumerations.h" #include "lldb/lldb-private.h" +#include <memory> +#include <vector> namespace lldb_private { Index: lldb/trunk/include/lldb/Symbol/ArmUnwindInfo.h =================================================================== --- lldb/trunk/include/lldb/Symbol/ArmUnwindInfo.h +++ lldb/trunk/include/lldb/Symbol/ArmUnwindInfo.h @@ -9,12 +9,11 @@ #ifndef liblldb_ArmUnwindInfo_h_ #define liblldb_ArmUnwindInfo_h_ -#include <vector> - -#include "lldb/Core/RangeMap.h" #include "lldb/Symbol/ObjectFile.h" #include "lldb/Utility/DataExtractor.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/lldb-private.h" +#include <vector> /* * Unwind information reader and parser for the ARM exception handling ABI Index: lldb/trunk/include/lldb/Utility/RangeMap.h =================================================================== --- lldb/trunk/include/lldb/Utility/RangeMap.h +++ lldb/trunk/include/lldb/Utility/RangeMap.h @@ -0,0 +1,947 @@ +//===-- 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 { + typedef B BaseType; + typedef S SizeType; + + BaseType base; + SizeType size; + + Range() : base(0), size(0) {} + + Range(BaseType b, SizeType s) : base(b), size(s) {} + + void Clear(BaseType b = 0) { + base = b; + size = 0; + } + + // Set the start value for the range, and keep the same size + BaseType GetRangeBase() const { return base; } + + void SetRangeBase(BaseType b) { base = b; } + + void Slide(BaseType slide) { base += slide; } + + bool Union(const Range &rhs) { + if (DoesAdjoinOrIntersect(rhs)) { + auto new_end = std::max<BaseType>(GetRangeEnd(), rhs.GetRangeEnd()); + base = std::min<BaseType>(base, rhs.base); + size = new_end - base; + return true; + } + return false; + } + + BaseType GetRangeEnd() const { return base + size; } + + void SetRangeEnd(BaseType end) { + if (end > base) + size = end - base; + else + size = 0; + } + + SizeType GetByteSize() const { return size; } + + void SetByteSize(SizeType s) { size = s; } + + bool IsValid() const { return size > 0; } + + bool Contains(BaseType r) const { + return (GetRangeBase() <= r) && (r < GetRangeEnd()); + } + + bool ContainsEndInclusive(BaseType r) const { + return (GetRangeBase() <= r) && (r <= GetRangeEnd()); + } + + bool Contains(const Range &range) const { + return Contains(range.GetRangeBase()) && + ContainsEndInclusive(range.GetRangeEnd()); + } + + // Returns true if the two ranges adjoing or intersect + bool DoesAdjoinOrIntersect(const Range &rhs) const { + const BaseType lhs_base = this->GetRangeBase(); + const BaseType rhs_base = rhs.GetRangeBase(); + const BaseType lhs_end = this->GetRangeEnd(); + const BaseType rhs_end = rhs.GetRangeEnd(); + bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base); + return result; + } + + // Returns true if the two ranges intersect + bool DoesIntersect(const Range &rhs) const { + const BaseType lhs_base = this->GetRangeBase(); + const BaseType rhs_base = rhs.GetRangeBase(); + const BaseType lhs_end = this->GetRangeEnd(); + const BaseType rhs_end = rhs.GetRangeEnd(); + bool result = (lhs_base < rhs_end) && (lhs_end > rhs_base); + return result; + } + + bool operator<(const Range &rhs) const { + if (base == rhs.base) + return size < rhs.size; + return base < rhs.base; + } + + bool operator==(const Range &rhs) const { + return base == rhs.base && size == rhs.size; + } + + bool operator!=(const Range &rhs) const { + return base != rhs.base || size != rhs.size; + } +}; + +//---------------------------------------------------------------------- +// A range array class where you get to define the type of the ranges +// that the collection contains. +//---------------------------------------------------------------------- + +template <typename B, typename S, unsigned N> class RangeArray { +public: + typedef B BaseType; + typedef S SizeType; + typedef Range<B, S> Entry; + typedef llvm::SmallVector<Entry, N> Collection; + + RangeArray() = default; + + ~RangeArray() = default; + + void Append(const Entry &entry) { m_entries.push_back(entry); } + + void Append(B base, S size) { m_entries.emplace_back(base, size); } + + bool RemoveEntrtAtIndex(uint32_t idx) { + if (idx < m_entries.size()) { + m_entries.erase(m_entries.begin() + idx); + return true; + } + return false; + } + + 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; + 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 CombineConsecutiveRanges() { +#ifdef ASSERT_RANGEMAP_ARE_SORTED + assert(IsSorted()); +#endif + // Can't combine if ranges if we have zero or one range + if (m_entries.size() > 1) { + // The list should be sorted prior to calling this function + 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->DoesAdjoinOrIntersect(*pos)) { + 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->DoesAdjoinOrIntersect(*pos)) + minimal_ranges.back().SetRangeEnd( + std::max<BaseType>(prev->GetRangeEnd(), 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); + } + } + } + + BaseType GetMinRangeBase(BaseType fail_value) const { +#ifdef ASSERT_RANGEMAP_ARE_SORTED + assert(IsSorted()); +#endif + if (m_entries.empty()) + return fail_value; + // m_entries must be sorted, so if we aren't empty, we grab the first + // range's base + return m_entries.front().GetRangeBase(); + } + + BaseType GetMaxRangeEnd(BaseType fail_value) const { +#ifdef ASSERT_RANGEMAP_ARE_SORTED + assert(IsSorted()); +#endif + if (m_entries.empty()) + return fail_value; + // m_entries must be sorted, so if we aren't empty, we grab the last + // range's end + return m_entries.back().GetRangeEnd(); + } + + void Slide(BaseType slide) { + typename Collection::iterator pos, end; + for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) + pos->Slide(slide); + } + + 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]; } + + Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); } + + const Entry *Back() const { + return (m_entries.empty() ? nullptr : &m_entries.back()); + } + + 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; + } + + const Entry *FindEntryThatContains(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 &(*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; + } + +protected: + Collection m_entries; +}; + +template <typename B, typename S> class RangeVector { +public: + typedef B BaseType; + typedef S SizeType; + typedef Range<B, S> Entry; + typedef std::vector<Entry> Collection; + + RangeVector() = default; + + ~RangeVector() = default; + + void Append(const Entry &entry) { m_entries.push_back(entry); } + + void Append(B base, S size) { m_entries.emplace_back(base, size); } + + // Insert an item into a sorted list and optionally combine it with any + // adjacent blocks if requested. + void Insert(const Entry &entry, bool combine) { + if (m_entries.empty()) { + m_entries.push_back(entry); + return; + } + auto begin = m_entries.begin(); + auto end = m_entries.end(); + auto pos = std::lower_bound(begin, end, entry); + if (combine) { + if (pos != end && pos->Union(entry)) { + CombinePrevAndNext(pos); + return; + } + if (pos != begin) { + auto prev = pos - 1; + if (prev->Union(entry)) { + CombinePrevAndNext(prev); + return; + } + } + } + m_entries.insert(pos, entry); + } + + bool RemoveEntryAtIndex(uint32_t idx) { + if (idx < m_entries.size()) { + m_entries.erase(m_entries.begin() + idx); + return true; + } + return false; + } + + 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 CombineConsecutiveRanges() { +#ifdef ASSERT_RANGEMAP_ARE_SORTED + assert(IsSorted()); +#endif + // Can't combine if ranges if we have zero or one range + if (m_entries.size() > 1) { + // The list should be sorted prior to calling this function + 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->DoesAdjoinOrIntersect(*pos)) { + 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->DoesAdjoinOrIntersect(*pos)) + minimal_ranges.back().SetRangeEnd( + std::max<BaseType>(prev->GetRangeEnd(), 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); + } + } + } + + BaseType GetMinRangeBase(BaseType fail_value) const { +#ifdef ASSERT_RANGEMAP_ARE_SORTED + assert(IsSorted()); +#endif + if (m_entries.empty()) + return fail_value; + // m_entries must be sorted, so if we aren't empty, we grab the first + // range's base + return m_entries.front().GetRangeBase(); + } + + BaseType GetMaxRangeEnd(BaseType fail_value) const { +#ifdef ASSERT_RANGEMAP_ARE_SORTED + assert(IsSorted()); +#endif + if (m_entries.empty()) + return fail_value; + // m_entries must be sorted, so if we aren't empty, we grab the last + // range's end + return m_entries.back().GetRangeEnd(); + } + + void Slide(BaseType slide) { + typename Collection::iterator pos, end; + for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) + pos->Slide(slide); + } + + void Clear() { m_entries.clear(); } + + void Reserve(typename Collection::size_type size) { m_entries.reserve(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); + } + + // Clients must ensure that "i" is a valid index prior to calling this + // function + Entry &GetEntryRef(size_t i) { return m_entries[i]; } + const Entry &GetEntryRef(size_t i) const { return m_entries[i]; } + + Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); } + + const Entry *Back() const { + return (m_entries.empty() ? nullptr : &m_entries.back()); + } + + 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; + } + + const Entry *FindEntryThatContains(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 &(*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; + } + +protected: + void CombinePrevAndNext(typename Collection::iterator pos) { + // Check if the prev or next entries in case they need to be unioned with + // the entry pointed to by "pos". + if (pos != m_entries.begin()) { + auto prev = pos - 1; + if (prev->Union(*pos)) + m_entries.erase(pos); + pos = prev; + } + + auto end = m_entries.end(); + if (pos != end) { + auto next = pos + 1; + if (next != end) { + if (pos->Union(*next)) + m_entries.erase(next); + } + } + return; + } + + Collection m_entries; +}; + +//---------------------------------------------------------------------- +// 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> { + typedef T DataType; + + DataType data; + + RangeData() : Range<B, S>(), data() {} + + RangeData(B base, S size) : Range<B, S>(base, size), data() {} + + RangeData(B base, S size, DataType d) : Range<B, S>(base, size), data(d) {} + + bool operator<(const RangeData &rhs) const { + if (this->base == rhs.base) { + if (this->size == rhs.size) + return this->data < rhs.data; + else + return this->size < rhs.size; + } + return this->base < rhs.base; + } + + bool operator==(const RangeData &rhs) const { + return this->GetRangeBase() == rhs.GetRangeBase() && + this->GetByteSize() == rhs.GetByteSize() && this->data == rhs.data; + } + + 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 = 0> +class RangeDataVector { +public: + typedef RangeData<B, S, T> Entry; + typedef llvm::SmallVector<Entry, N> Collection; + + RangeDataVector() = default; + + ~RangeDataVector() = 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); + } + + 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 + Entry &GetEntryRef(size_t i) { return m_entries[i]; } + 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 { + 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) { + return const_cast<Entry *>( + static_cast<const RangeDataVector *>(this)->FindEntryThatContains( + addr)); + } + + const Entry *FindEntryThatContains(B addr) const { + return FindEntryThatContains(Entry(addr, 1)); + } + + 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); + + while (pos != begin && pos[-1].Contains(range)) + --pos; + + if (pos != end && pos->Contains(range)) + return &(*pos); + } + return nullptr; + } + + const Entry *FindEntryStartsAt(B addr) const { +#ifdef ASSERT_RANGEMAP_ARE_SORTED + assert(IsSorted()); +#endif + if (!m_entries.empty()) { + auto begin = m_entries.begin(), end = m_entries.end(); + auto pos = std::lower_bound(begin, end, Entry(addr, 1), BaseLessThan); + if (pos != end && pos->base == addr) + return &(*pos); + } + return nullptr; + } + + // 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 { +#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(m_entries.begin(), end, addr, + [](const Entry &lhs, B rhs_base) -> bool { + return lhs.GetRangeEnd() <= rhs_base; + }); + + while (pos != begin && pos[-1].Contains(addr)) + --pos; + + if (pos != end) + 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; +}; + +//---------------------------------------------------------------------- +// 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 { + typedef B BaseType; + typedef T DataType; + + BaseType addr; + DataType data; + + AddressData() : addr(), data() {} + + AddressData(B a, DataType d) : addr(a), data(d) {} + + bool operator<(const AddressData &rhs) const { + if (this->addr == rhs.addr) + return this->data < rhs.data; + return this->addr < rhs.addr; + } + + bool operator==(const AddressData &rhs) const { + return this->addr == rhs.addr && this->data == rhs.data; + } + + bool operator!=(const AddressData &rhs) const { + return this->addr != rhs.addr || this->data == rhs.data; + } +}; + +template <typename B, typename T, unsigned N> class AddressDataArray { +public: + typedef AddressData<B, T> Entry; + typedef llvm::SmallVector<Entry, N> Collection; + + AddressDataArray() = default; + + ~AddressDataArray() = 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 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.addr < rhs.addr; + } + + Entry *FindEntry(B addr, bool exact_match_only) { +#ifdef ASSERT_RANGEMAP_ARE_SORTED + assert(IsSorted()); +#endif + if (!m_entries.empty()) { + Entry entry; + entry.addr = addr; + 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].addr == addr) + --pos; + + if (pos != end) { + if (pos->addr == addr || !exact_match_only) + return &(*pos); + } + } + return nullptr; + } + + const Entry *FindNextEntry(const Entry *entry) { + if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end()) + return entry + 1; + 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; +}; + +} // namespace lldb_private + +#endif // LLDB_UTILITY_RANGEMAP_H Index: lldb/trunk/include/lldb/Core/dwarf.h =================================================================== --- lldb/trunk/include/lldb/Core/dwarf.h +++ lldb/trunk/include/lldb/Core/dwarf.h @@ -9,13 +9,12 @@ #ifndef DebugBase_dwarf_h_ #define DebugBase_dwarf_h_ +#include "lldb/Utility/RangeMap.h" #include <stdint.h> // Get the DWARF constant definitions from llvm #include "llvm/BinaryFormat/Dwarf.h" -#include "lldb/Core/RangeMap.h" - // and stuff them in our default namespace using namespace llvm::dwarf; Index: lldb/trunk/include/lldb/Target/MemoryRegionInfo.h =================================================================== --- lldb/trunk/include/lldb/Target/MemoryRegionInfo.h +++ lldb/trunk/include/lldb/Target/MemoryRegionInfo.h @@ -10,9 +10,9 @@ #ifndef lldb_MemoryRegionInfo_h #define lldb_MemoryRegionInfo_h -#include "lldb/Core/RangeMap.h" -#include "llvm/Support/FormatProviders.h" #include "lldb/Utility/ConstString.h" +#include "lldb/Utility/RangeMap.h" +#include "llvm/Support/FormatProviders.h" namespace lldb_private { class MemoryRegionInfo { Index: lldb/trunk/include/lldb/Target/Memory.h =================================================================== --- lldb/trunk/include/lldb/Target/Memory.h +++ lldb/trunk/include/lldb/Target/Memory.h @@ -9,14 +9,12 @@ #ifndef liblldb_Memory_h_ #define liblldb_Memory_h_ +#include "lldb/Utility/RangeMap.h" +#include "lldb/lldb-private.h" #include <map> #include <mutex> #include <vector> - -#include "lldb/Core/RangeMap.h" -#include "lldb/lldb-private.h" - namespace lldb_private { //---------------------------------------------------------------------- // A class to track memory that was read from a live process between Index: lldb/trunk/unittests/Core/RangeTest.cpp =================================================================== --- lldb/trunk/unittests/Core/RangeTest.cpp +++ lldb/trunk/unittests/Core/RangeTest.cpp @@ -1,329 +0,0 @@ -//===-- RangeTest.cpp ----------------------------------------*- 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 -// -//===----------------------------------------------------------------------===// - -#include "lldb/Core/RangeMap.h" - -#include <cstdint> -#include <type_traits> - -#include "gtest/gtest.h" - -using namespace lldb; -using namespace lldb_private; - -TEST(RangeTest, SizeTypes) { - Range<lldb::addr_t, uint32_t> r; - static_assert(std::is_same<lldb::addr_t, decltype(r.GetRangeBase())>::value, - "RangeBase type is not equal to the given one."); - static_assert(std::is_same<lldb::addr_t, decltype(r.GetRangeEnd())>::value, - "RangeEnd type is not equal to the given one."); - static_assert(std::is_same<uint32_t, decltype(r.GetByteSize())>::value, - "Size type is not equal to the given one."); -} - -typedef Range<lldb::addr_t, uint32_t> RangeT; - -TEST(RangeTest, DefaultConstructor) { - RangeT r; - EXPECT_FALSE(r.IsValid()); - EXPECT_EQ(0U, r.GetByteSize()); - EXPECT_EQ(0U, r.GetRangeBase()); - EXPECT_EQ(0U, r.GetRangeEnd()); -} - -TEST(RangeTest, Constructor) { - RangeT r(3, 5); - EXPECT_TRUE(r.IsValid()); - EXPECT_EQ(5U, r.GetByteSize()); - EXPECT_EQ(3U, r.GetRangeBase()); - EXPECT_EQ(8U, r.GetRangeEnd()); -} - -TEST(RangeTest, Copy) { - RangeT orig(3, 5); - RangeT r = orig; - EXPECT_TRUE(r.IsValid()); - EXPECT_EQ(5U, r.GetByteSize()); - EXPECT_EQ(3U, r.GetRangeBase()); - EXPECT_EQ(8U, r.GetRangeEnd()); -} - -TEST(RangeTest, Clear) { - RangeT r(3, 5); - r.Clear(); - EXPECT_TRUE(r == RangeT()); -} - -TEST(RangeTest, ClearWithStarAddress) { - RangeT r(3, 5); - r.Clear(4); - EXPECT_TRUE(r == RangeT(4, 0)); -} - -TEST(RangeTest, SetRangeBase) { - RangeT r(3, 5); - r.SetRangeBase(6); - EXPECT_EQ(6U, r.GetRangeBase()); - EXPECT_EQ(11U, r.GetRangeEnd()); - EXPECT_EQ(5U, r.GetByteSize()); -} - -TEST(RangeTest, Slide) { - RangeT r(3, 5); - r.Slide(1); - EXPECT_EQ(4U, r.GetRangeBase()); - EXPECT_EQ(9U, r.GetRangeEnd()); - EXPECT_EQ(5U, r.GetByteSize()); - - r.Slide(2); - EXPECT_EQ(6U, r.GetRangeBase()); - EXPECT_EQ(11U, r.GetRangeEnd()); - EXPECT_EQ(5U, r.GetByteSize()); -} - -TEST(RangeTest, SlideZero) { - RangeT r(3, 5); - r.Slide(0); - EXPECT_EQ(3U, r.GetRangeBase()); - EXPECT_EQ(8U, r.GetRangeEnd()); - EXPECT_EQ(5U, r.GetByteSize()); -} - -TEST(RangeTest, ContainsAddr) { - RangeT r(3, 5); - EXPECT_FALSE(r.Contains(0)); - EXPECT_FALSE(r.Contains(1)); - EXPECT_FALSE(r.Contains(2)); - EXPECT_TRUE(r.Contains(3)); - EXPECT_TRUE(r.Contains(4)); - EXPECT_TRUE(r.Contains(5)); - EXPECT_TRUE(r.Contains(6)); - EXPECT_TRUE(r.Contains(7)); - EXPECT_FALSE(r.Contains(8)); - EXPECT_FALSE(r.Contains(9)); - EXPECT_FALSE(r.Contains(10)); -} - -TEST(RangeTest, ContainsAddrInvalid) { - RangeT r; - EXPECT_FALSE(r.Contains(0)); - EXPECT_FALSE(r.Contains(1)); - EXPECT_FALSE(r.Contains(2)); - EXPECT_FALSE(r.Contains(3)); - EXPECT_FALSE(r.Contains(4)); -} - -TEST(RangeTest, ContainsEndInclusive) { - RangeT r(3, 5); - EXPECT_FALSE(r.ContainsEndInclusive(0)); - EXPECT_FALSE(r.ContainsEndInclusive(1)); - EXPECT_FALSE(r.ContainsEndInclusive(2)); - EXPECT_TRUE(r.ContainsEndInclusive(3)); - EXPECT_TRUE(r.ContainsEndInclusive(4)); - EXPECT_TRUE(r.ContainsEndInclusive(5)); - EXPECT_TRUE(r.ContainsEndInclusive(6)); - EXPECT_TRUE(r.ContainsEndInclusive(7)); - EXPECT_TRUE(r.ContainsEndInclusive(8)); - EXPECT_FALSE(r.ContainsEndInclusive(9)); - EXPECT_FALSE(r.ContainsEndInclusive(10)); -} - -TEST(RangeTest, ContainsEndInclusiveInvalid) { - RangeT r; - // FIXME: This is probably not intended. - EXPECT_TRUE(r.ContainsEndInclusive(0)); - - EXPECT_FALSE(r.ContainsEndInclusive(1)); - EXPECT_FALSE(r.ContainsEndInclusive(2)); -} - -TEST(RangeTest, ContainsRange) { - RangeT r(3, 5); - - // Range always contains itself. - EXPECT_TRUE(r.Contains(r)); - // Invalid range. - EXPECT_FALSE(r.Contains(RangeT())); - // Range starts and ends before. - EXPECT_FALSE(r.Contains(RangeT(0, 3))); - // Range starts before but contains beginning. - EXPECT_FALSE(r.Contains(RangeT(0, 4))); - // Range starts before but contains beginning and more. - EXPECT_FALSE(r.Contains(RangeT(0, 5))); - // Range starts before and contains the other. - EXPECT_FALSE(r.Contains(RangeT(0, 9))); - // Range is fully inside. - EXPECT_TRUE(r.Contains(RangeT(4, 3))); - // Range has same start, but not as large. - EXPECT_TRUE(r.Contains(RangeT(3, 4))); - // Range has same end, but starts earlier. - EXPECT_TRUE(r.Contains(RangeT(4, 4))); - // Range starts inside, but stops after the end of r. - EXPECT_FALSE(r.Contains(RangeT(4, 5))); - // Range starts directly after r. - EXPECT_FALSE(r.Contains(RangeT(8, 2))); - // Range starts directly after r. - EXPECT_FALSE(r.Contains(RangeT(9, 2))); - - // Invalid range with different start. - // FIXME: The first two probably not intended. - EXPECT_TRUE(r.Contains(RangeT(3, 0))); - EXPECT_TRUE(r.Contains(RangeT(4, 0))); - EXPECT_FALSE(r.Contains(RangeT(8, 0))); -} - -TEST(RangeTest, ContainsRangeStartingFromZero) { - RangeT r(0, 3); - EXPECT_TRUE(r.Contains(r)); - - // FIXME: This is probably not intended. - EXPECT_TRUE(r.Contains(RangeT())); -} - -TEST(RangeTest, Union) { - RangeT r(3, 5); - - // Ranges that we can't merge because it's not adjoin/intersecting. - EXPECT_FALSE(r.Union(RangeT(9, 1))); - // Check that we didn't modify our range. - EXPECT_EQ(r, RangeT(3, 5)); - - // Another range we can't merge, but before r. - EXPECT_FALSE(r.Union(RangeT(1, 1))); - EXPECT_EQ(r, RangeT(3, 5)); - - // Merge an adjoin range after. - EXPECT_TRUE(r.Union(RangeT(8, 2))); - EXPECT_EQ(r, RangeT(3, 7)); - - // Merge an adjoin range before. - EXPECT_TRUE(r.Union(RangeT(1, 2))); - EXPECT_EQ(r, RangeT(1, 9)); - - // Merge an intersecting range after. - EXPECT_TRUE(r.Union(RangeT(8, 3))); - EXPECT_EQ(r, RangeT(1, 10)); - - // Merge an intersecting range before. - EXPECT_TRUE(r.Union(RangeT(0, 1))); - EXPECT_EQ(r, RangeT(0, 11)); - - // Merge a few ranges inside that shouldn't do anything. - EXPECT_TRUE(r.Union(RangeT(0, 3))); - EXPECT_EQ(r, RangeT(0, 11)); - EXPECT_TRUE(r.Union(RangeT(5, 1))); - EXPECT_EQ(r, RangeT(0, 11)); - EXPECT_TRUE(r.Union(RangeT(9, 2))); - EXPECT_EQ(r, RangeT(0, 11)); -} - -TEST(RangeTest, DoesAdjoinOrIntersect) { - RangeT r(3, 4); - - EXPECT_FALSE(r.DoesAdjoinOrIntersect(RangeT(1, 1))); - EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(1, 2))); - EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(2, 2))); - EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(4, 2))); - EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(6, 2))); - EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(7, 2))); - EXPECT_FALSE(r.DoesAdjoinOrIntersect(RangeT(8, 2))); -} - -TEST(RangeTest, DoesIntersect) { - RangeT r(3, 4); - - EXPECT_FALSE(r.DoesIntersect(RangeT(1, 1))); - EXPECT_FALSE(r.DoesIntersect(RangeT(1, 2))); - EXPECT_TRUE(r.DoesIntersect(RangeT(2, 2))); - EXPECT_TRUE(r.DoesIntersect(RangeT(4, 2))); - EXPECT_TRUE(r.DoesIntersect(RangeT(6, 2))); - EXPECT_FALSE(r.DoesIntersect(RangeT(7, 2))); - EXPECT_FALSE(r.DoesIntersect(RangeT(8, 2))); -} - -TEST(RangeTest, LessThan) { - RangeT r(10, 20); - - // Equal range. - EXPECT_FALSE(r < RangeT(10, 20)); - EXPECT_FALSE(RangeT(10, 20) < r); - - auto expect_ordered_less_than = [](RangeT r1, RangeT r2) { - EXPECT_TRUE(r1 < r2); - EXPECT_FALSE(r2 < r1); - }; - - // Same start, but bigger size. - expect_ordered_less_than(r, RangeT(10, 21)); - - // Start before and ends before. - expect_ordered_less_than(RangeT(9, 20), r); - - // Start before and equal size. - expect_ordered_less_than(RangeT(9, 21), r); - - // Start before and bigger size. - expect_ordered_less_than(RangeT(9, 22), r); - - // Start after and ends before. - expect_ordered_less_than(r, RangeT(11, 18)); - - // Start after and equal size. - expect_ordered_less_than(r, RangeT(11, 19)); - - // Start after and bigger size. - expect_ordered_less_than(r, RangeT(11, 20)); -} - -TEST(RangeTest, Equal) { - RangeT r(10, 20); - - // Equal range. - EXPECT_TRUE(r == RangeT(10, 20)); - - // Same start, different size. - EXPECT_FALSE(r == RangeT(10, 21)); - - // Different start, same size. - EXPECT_FALSE(r == RangeT(9, 20)); - - // Different start, different size. - EXPECT_FALSE(r == RangeT(9, 21)); - EXPECT_FALSE(r == RangeT(11, 19)); -} - -TEST(RangeTest, NotEqual) { - RangeT r(10, 20); - - EXPECT_FALSE(r != RangeT(10, 20)); - - EXPECT_TRUE(r != RangeT(10, 21)); - EXPECT_TRUE(r != RangeT(9, 20)); - EXPECT_TRUE(r != RangeT(9, 21)); -} - -// Comparison tests for invalid ranges (size == 0). - -TEST(RangeTest, LessThanInvalid) { - EXPECT_TRUE(RangeT() < RangeT(1, 0)); - EXPECT_TRUE(RangeT() < RangeT(2, 0)); - EXPECT_TRUE(RangeT(1, 0) < RangeT(2, 0)); -} - -TEST(RangeTest, EqualInvalid) { - RangeT r; - EXPECT_TRUE(r == RangeT()); - // Another invalid range, but with a different start. - EXPECT_FALSE(r == RangeT(3, 0)); -} - -TEST(RangeTest, NotEqualInvalid) { - RangeT r; - EXPECT_FALSE(r != RangeT()); - EXPECT_FALSE(r == RangeT(3, 0)); -} Index: lldb/trunk/unittests/Core/RangeMapTest.cpp =================================================================== --- lldb/trunk/unittests/Core/RangeMapTest.cpp +++ lldb/trunk/unittests/Core/RangeMapTest.cpp @@ -1,54 +0,0 @@ -//===-- RangeTest.cpp ----------------------------------------*- 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 -// -//===----------------------------------------------------------------------===// - -#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>; -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); -} Index: lldb/trunk/include/lldb/Core/RangeMap.h =================================================================== --- lldb/trunk/include/lldb/Core/RangeMap.h +++ lldb/trunk/include/lldb/Core/RangeMap.h @@ -1,950 +0,0 @@ -//===-- 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 liblldb_RangeMap_h_ -#define liblldb_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 { - typedef B BaseType; - typedef S SizeType; - - BaseType base; - SizeType size; - - Range() : base(0), size(0) {} - - Range(BaseType b, SizeType s) : base(b), size(s) {} - - void Clear(BaseType b = 0) { - base = b; - size = 0; - } - - // Set the start value for the range, and keep the same size - BaseType GetRangeBase() const { return base; } - - void SetRangeBase(BaseType b) { base = b; } - - void Slide(BaseType slide) { base += slide; } - - bool Union(const Range &rhs) - { - if (DoesAdjoinOrIntersect(rhs)) - { - auto new_end = std::max<BaseType>(GetRangeEnd(), rhs.GetRangeEnd()); - base = std::min<BaseType>(base, rhs.base); - size = new_end - base; - return true; - } - return false; - } - - BaseType GetRangeEnd() const { return base + size; } - - void SetRangeEnd(BaseType end) { - if (end > base) - size = end - base; - else - size = 0; - } - - SizeType GetByteSize() const { return size; } - - void SetByteSize(SizeType s) { size = s; } - - bool IsValid() const { return size > 0; } - - bool Contains(BaseType r) const { - return (GetRangeBase() <= r) && (r < GetRangeEnd()); - } - - bool ContainsEndInclusive(BaseType r) const { - return (GetRangeBase() <= r) && (r <= GetRangeEnd()); - } - - bool Contains(const Range &range) const { - return Contains(range.GetRangeBase()) && - ContainsEndInclusive(range.GetRangeEnd()); - } - - // Returns true if the two ranges adjoing or intersect - bool DoesAdjoinOrIntersect(const Range &rhs) const { - const BaseType lhs_base = this->GetRangeBase(); - const BaseType rhs_base = rhs.GetRangeBase(); - const BaseType lhs_end = this->GetRangeEnd(); - const BaseType rhs_end = rhs.GetRangeEnd(); - bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base); - return result; - } - - // Returns true if the two ranges intersect - bool DoesIntersect(const Range &rhs) const { - const BaseType lhs_base = this->GetRangeBase(); - const BaseType rhs_base = rhs.GetRangeBase(); - const BaseType lhs_end = this->GetRangeEnd(); - const BaseType rhs_end = rhs.GetRangeEnd(); - bool result = (lhs_base < rhs_end) && (lhs_end > rhs_base); - return result; - } - - bool operator<(const Range &rhs) const { - if (base == rhs.base) - return size < rhs.size; - return base < rhs.base; - } - - bool operator==(const Range &rhs) const { - return base == rhs.base && size == rhs.size; - } - - bool operator!=(const Range &rhs) const { - return base != rhs.base || size != rhs.size; - } -}; - -//---------------------------------------------------------------------- -// A range array class where you get to define the type of the ranges -// that the collection contains. -//---------------------------------------------------------------------- - -template <typename B, typename S, unsigned N> class RangeArray { -public: - typedef B BaseType; - typedef S SizeType; - typedef Range<B, S> Entry; - typedef llvm::SmallVector<Entry, N> Collection; - - RangeArray() = default; - - ~RangeArray() = default; - - void Append(const Entry &entry) { m_entries.push_back(entry); } - - void Append(B base, S size) { m_entries.emplace_back(base, size); } - - bool RemoveEntrtAtIndex(uint32_t idx) { - if (idx < m_entries.size()) { - m_entries.erase(m_entries.begin() + idx); - return true; - } - return false; - } - - 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; - 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 CombineConsecutiveRanges() { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - // Can't combine if ranges if we have zero or one range - if (m_entries.size() > 1) { - // The list should be sorted prior to calling this function - 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->DoesAdjoinOrIntersect(*pos)) { - 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->DoesAdjoinOrIntersect(*pos)) - minimal_ranges.back().SetRangeEnd( - std::max<BaseType>(prev->GetRangeEnd(), 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); - } - } - } - - BaseType GetMinRangeBase(BaseType fail_value) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (m_entries.empty()) - return fail_value; - // m_entries must be sorted, so if we aren't empty, we grab the first - // range's base - return m_entries.front().GetRangeBase(); - } - - BaseType GetMaxRangeEnd(BaseType fail_value) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (m_entries.empty()) - return fail_value; - // m_entries must be sorted, so if we aren't empty, we grab the last - // range's end - return m_entries.back().GetRangeEnd(); - } - - void Slide(BaseType slide) { - typename Collection::iterator pos, end; - for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) - pos->Slide(slide); - } - - 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]; } - - Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); } - - const Entry *Back() const { - return (m_entries.empty() ? nullptr : &m_entries.back()); - } - - 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; - } - - const Entry *FindEntryThatContains(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 &(*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; - } - -protected: - Collection m_entries; -}; - -template <typename B, typename S> class RangeVector { -public: - typedef B BaseType; - typedef S SizeType; - typedef Range<B, S> Entry; - typedef std::vector<Entry> Collection; - - RangeVector() = default; - - ~RangeVector() = default; - - void Append(const Entry &entry) { m_entries.push_back(entry); } - - void Append(B base, S size) { m_entries.emplace_back(base, size); } - - // Insert an item into a sorted list and optionally combine it with any - // adjacent blocks if requested. - void Insert(const Entry &entry, bool combine) { - if (m_entries.empty()) { - m_entries.push_back(entry); - return; - } - auto begin = m_entries.begin(); - auto end = m_entries.end(); - auto pos = std::lower_bound(begin, end, entry); - if (combine) { - if (pos != end && pos->Union(entry)) { - CombinePrevAndNext(pos); - return; - } - if (pos != begin) { - auto prev = pos - 1; - if (prev->Union(entry)) { - CombinePrevAndNext(prev); - return; - } - } - } - m_entries.insert(pos, entry); - } - - bool RemoveEntryAtIndex(uint32_t idx) { - if (idx < m_entries.size()) { - m_entries.erase(m_entries.begin() + idx); - return true; - } - return false; - } - - 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 CombineConsecutiveRanges() { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - // Can't combine if ranges if we have zero or one range - if (m_entries.size() > 1) { - // The list should be sorted prior to calling this function - 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->DoesAdjoinOrIntersect(*pos)) { - 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->DoesAdjoinOrIntersect(*pos)) - minimal_ranges.back().SetRangeEnd( - std::max<BaseType>(prev->GetRangeEnd(), 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); - } - } - } - - BaseType GetMinRangeBase(BaseType fail_value) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (m_entries.empty()) - return fail_value; - // m_entries must be sorted, so if we aren't empty, we grab the first - // range's base - return m_entries.front().GetRangeBase(); - } - - BaseType GetMaxRangeEnd(BaseType fail_value) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (m_entries.empty()) - return fail_value; - // m_entries must be sorted, so if we aren't empty, we grab the last - // range's end - return m_entries.back().GetRangeEnd(); - } - - void Slide(BaseType slide) { - typename Collection::iterator pos, end; - for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) - pos->Slide(slide); - } - - void Clear() { m_entries.clear(); } - - void Reserve(typename Collection::size_type size) { m_entries.reserve(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); - } - - // Clients must ensure that "i" is a valid index prior to calling this - // function - Entry &GetEntryRef(size_t i) { return m_entries[i]; } - const Entry &GetEntryRef(size_t i) const { return m_entries[i]; } - - Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); } - - const Entry *Back() const { - return (m_entries.empty() ? nullptr : &m_entries.back()); - } - - 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; - } - - const Entry *FindEntryThatContains(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 &(*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; - } - -protected: - - void CombinePrevAndNext(typename Collection::iterator pos) { - // Check if the prev or next entries in case they need to be unioned with - // the entry pointed to by "pos". - if (pos != m_entries.begin()) { - auto prev = pos - 1; - if (prev->Union(*pos)) - m_entries.erase(pos); - pos = prev; - } - - auto end = m_entries.end(); - if (pos != end) { - auto next = pos + 1; - if (next != end) { - if (pos->Union(*next)) - m_entries.erase(next); - } - } - return; - } - - Collection m_entries; -}; - -//---------------------------------------------------------------------- -// 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> { - typedef T DataType; - - DataType data; - - RangeData() : Range<B, S>(), data() {} - - RangeData(B base, S size) : Range<B, S>(base, size), data() {} - - RangeData(B base, S size, DataType d) : Range<B, S>(base, size), data(d) {} - - bool operator<(const RangeData &rhs) const { - if (this->base == rhs.base) { - if (this->size == rhs.size) - return this->data < rhs.data; - else - return this->size < rhs.size; - } - return this->base < rhs.base; - } - - bool operator==(const RangeData &rhs) const { - return this->GetRangeBase() == rhs.GetRangeBase() && - this->GetByteSize() == rhs.GetByteSize() && this->data == rhs.data; - } - - 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 = 0> -class RangeDataVector { -public: - typedef RangeData<B, S, T> Entry; - typedef llvm::SmallVector<Entry, N> Collection; - - RangeDataVector() = default; - - ~RangeDataVector() = 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); - } - - 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 - Entry &GetEntryRef(size_t i) { return m_entries[i]; } - 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 { - 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) { - return const_cast<Entry *>( - static_cast<const RangeDataVector *>(this)->FindEntryThatContains( - addr)); - } - - const Entry *FindEntryThatContains(B addr) const { - return FindEntryThatContains(Entry(addr, 1)); - } - - 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); - - while (pos != begin && pos[-1].Contains(range)) - --pos; - - if (pos != end && pos->Contains(range)) - return &(*pos); - } - return nullptr; - } - - const Entry *FindEntryStartsAt(B addr) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (!m_entries.empty()) { - auto begin = m_entries.begin(), end = m_entries.end(); - auto pos = std::lower_bound(begin, end, Entry(addr, 1), BaseLessThan); - if (pos != end && pos->base == addr) - return &(*pos); - } - return nullptr; - } - - // 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 { -#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(m_entries.begin(), end, addr, - [](const Entry &lhs, B rhs_base) -> bool { - return lhs.GetRangeEnd() <= rhs_base; - }); - - while (pos != begin && pos[-1].Contains(addr)) - --pos; - - if (pos != end) - 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; -}; - -//---------------------------------------------------------------------- -// 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 { - typedef B BaseType; - typedef T DataType; - - BaseType addr; - DataType data; - - AddressData() : addr(), data() {} - - AddressData(B a, DataType d) : addr(a), data(d) {} - - bool operator<(const AddressData &rhs) const { - if (this->addr == rhs.addr) - return this->data < rhs.data; - return this->addr < rhs.addr; - } - - bool operator==(const AddressData &rhs) const { - return this->addr == rhs.addr && this->data == rhs.data; - } - - bool operator!=(const AddressData &rhs) const { - return this->addr != rhs.addr || this->data == rhs.data; - } -}; - -template <typename B, typename T, unsigned N> class AddressDataArray { -public: - typedef AddressData<B, T> Entry; - typedef llvm::SmallVector<Entry, N> Collection; - - AddressDataArray() = default; - - ~AddressDataArray() = 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 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.addr < rhs.addr; - } - - Entry *FindEntry(B addr, bool exact_match_only) { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (!m_entries.empty()) { - Entry entry; - entry.addr = addr; - 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].addr == addr) - --pos; - - if (pos != end) { - if (pos->addr == addr || !exact_match_only) - return &(*pos); - } - } - return nullptr; - } - - const Entry *FindNextEntry(const Entry *entry) { - if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end()) - return entry + 1; - 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; -}; - -} // namespace lldb_private - -#endif // liblldb_RangeMap_h_
_______________________________________________ lldb-commits mailing list lldb-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
