Added more functionality to Range template classes in RangeMap.h and converted remaining DWARF areas that were using ranges over to this class. Also converted lldb_private::Block to use it.

llvm-svn: 141460

6 files changed, 140 insertions, 217 deletions

diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.cpp b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.cpp
index 8c269b9f2da..ab2f9c4f16e 100644
--- a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.cpp
+++ b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.cpp
@@ -113,7 +113,7 @@ DWARFDebugAranges::Dump (Log *log) const
     if (log == NULL)
         return;
     
-    const size_t num_entries = m_aranges.GetNumEntries();
+    const size_t num_entries = m_aranges.GetSize();
     for (size_t i=0; i<num_entries; ++i)
     {
         const RangeToDIE::Entry *entry = m_aranges.GetEntryAtIndex(i);
@@ -141,7 +141,7 @@ DWARFDebugAranges::Sort (bool minimize)
     size_t orig_arange_size = 0;
     if (log)
     {
-        orig_arange_size = m_aranges.GetNumEntries();
+        orig_arange_size = m_aranges.GetSize();
         log->Printf ("DWARFDebugAranges::Sort(minimize = %u) with %zu entries", minimize, orig_arange_size);
     }
 
@@ -152,7 +152,7 @@ DWARFDebugAranges::Sort (bool minimize)
     {
         if (minimize)
         {
-            const size_t new_arange_size = m_aranges.GetNumEntries();
+            const size_t new_arange_size = m_aranges.GetSize();
             const size_t delta = orig_arange_size - new_arange_size;
             log->Printf ("DWARFDebugAranges::Sort() %zu entries after minimizing (%zu entries combined for %zu bytes saved)", 
                          new_arange_size, delta, delta * sizeof(Range));
diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h
index 90dc4fc43c1..78e1dfddc3f 100644
--- a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h
+++ b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h
@@ -69,7 +69,7 @@ public:
     uint32_t
     GetNumRanges() const
     {
-        return m_aranges.GetNumEntries();
+        return m_aranges.GetSize();
     }
 
     dw_offset_t 
diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugInfoEntry.cpp b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugInfoEntry.cpp
index 152867a5467..bcce74c60c9 100644
--- a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugInfoEntry.cpp
+++ b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugInfoEntry.cpp
@@ -933,7 +933,7 @@ DWARFDebugInfoEntry::GetDIENamesAndRanges
                         // All DW_AT_ranges are relative to the base address of the
                         // compile unit. We add the compile unit base address to make
                         // sure all the addresses are properly fixed up.
-                        ranges.AddOffset(cu->GetBaseAddress());
+                        ranges.Slide(cu->GetBaseAddress());
                     }
                     break;
 
@@ -1024,26 +1024,25 @@ DWARFDebugInfoEntry::GetDIENamesAndRanges
         }
     }
 
-    size_t numRanges = ranges.Size();
-
-    if (numRanges == 0)
+    if (ranges.IsEmpty())
     {
         if (lo_pc != DW_INVALID_ADDRESS)
         {
-            if (hi_pc != DW_INVALID_ADDRESS)
-                ranges.AddRange(lo_pc, hi_pc);
+            if (hi_pc != DW_INVALID_ADDRESS && hi_pc > lo_pc)
+                ranges.Append(DWARFDebugRanges::Range (lo_pc, hi_pc - lo_pc));
             else
-                ranges.AddRange(lo_pc, lo_pc);
+                ranges.Append(DWARFDebugRanges::Range (lo_pc, 0));
         }
     }
     
     if (set_frame_base_loclist_addr)
     {
-        assert (ranges.LowestAddress(0) >= cu->GetBaseAddress());
-        frame_base->SetLocationListSlide(ranges.LowestAddress(0) - cu->GetBaseAddress());
+        dw_addr_t lowest_range_pc = ranges.GetMinRangeBase(0);
+        assert (lowest_range_pc >= cu->GetBaseAddress());
+        frame_base->SetLocationListSlide (lowest_range_pc - cu->GetBaseAddress());
     }
 
-    if (ranges.Size() == 0 || (name == NULL) || (mangled == NULL))
+    if (ranges.IsEmpty() || name == NULL || mangled == NULL)
     {
         std::vector<dw_offset_t>::const_iterator pos;
         std::vector<dw_offset_t>::const_iterator end = die_offsets.end();
@@ -1060,7 +1059,7 @@ DWARFDebugInfoEntry::GetDIENamesAndRanges
             }
         }
     }
-    return ranges.Size() > 0;
+    return !ranges.IsEmpty();
 }
 
 //----------------------------------------------------------------------
@@ -2038,8 +2037,8 @@ DWARFDebugInfoEntry::LookupAddress
                     // All DW_AT_ranges are relative to the base address of the
                     // compile unit. We add the compile unit base address to make
                     // sure all the addresses are properly fixed up.
-                    ranges.AddOffset(cu->GetBaseAddress());
-                    if (ranges.Lookup(address))
+                    ranges.Slide (cu->GetBaseAddress());
+                    if (ranges.FindEntryThatContains(address))
                     {
                         found_address = true;
                     //  puts("***MATCH***");
diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugRanges.cpp b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugRanges.cpp
index 3502d56a82e..f69b370b515 100644
--- a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugRanges.cpp
+++ b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugRanges.cpp
@@ -30,94 +30,62 @@ DWARFDebugRanges::Extract(SymbolFileDWARF* dwarf2Data)
     RangeList range_list;
     dw_offset_t offset = 0;
     dw_offset_t debug_ranges_offset = offset;
-    while (range_list.Extract(dwarf2Data, &offset))
+    while (Extract(dwarf2Data, &offset, range_list))
     {
         m_range_map[debug_ranges_offset] = range_list;
         debug_ranges_offset = offset;
     }
 }
 
-bool
-DWARFDebugRanges::RangeList::AddRange(dw_addr_t lo_addr, dw_addr_t hi_addr)
-{
-    if (lo_addr <= hi_addr)
-    {
-        Range range(lo_addr, hi_addr);
-        ranges.push_back(range);
-        return true;
-    }
-    return false;
-}
-
-const DWARFDebugRanges::Range*
-DWARFDebugRanges::RangeList::Lookup(dw_addr_t offset) const
-{
-    Range::const_iterator pos = ranges.begin();
-    Range::const_iterator end_pos = ranges.end();
-    for (pos = ranges.begin(); pos != end_pos; ++pos)
-    {
-        if (pos->begin_offset <= offset && offset < pos->end_offset)
-        {
-            return &(*pos);
-        }
-    }
-    return NULL;
-}
-
-size_t
-DWARFDebugRanges::RangeList::Size() const
-{
-    return ranges.size();
-}
-
-void
-DWARFDebugRanges::RangeList::AddOffset(dw_addr_t offset)
-{
-    if (!ranges.empty())
-    {
-        Range::iterator pos = ranges.begin();
-        Range::iterator end_pos = ranges.end();
-        for (pos = ranges.begin(); pos != end_pos; ++pos)
-        {
-            // assert for unsigned overflows
-            assert (~pos->begin_offset >= offset);
-            assert (~pos->end_offset >= offset);
-            pos->begin_offset += offset;
-            pos->end_offset += offset;
-        }
-    }
-}
-
-void
-DWARFDebugRanges::RangeList::SubtractOffset(dw_addr_t offset)
-{
-    if (!ranges.empty())
-    {
-        Range::iterator pos = ranges.begin();
-        Range::iterator end_pos = ranges.end();
-        for (pos = ranges.begin(); pos != end_pos; ++pos)
-        {
-            assert (pos->begin_offset >= offset);
-            assert (pos->end_offset >= offset);
-            pos->begin_offset -= offset;
-            pos->end_offset -= offset;
-        }
-    }
-}
-
-
-const DWARFDebugRanges::Range*
-DWARFDebugRanges::RangeList::RangeAtIndex(size_t i) const
-{
-    if (i < ranges.size())
-        return &ranges[i];
-    return NULL;
-}
+//void
+//DWARFDebugRanges::RangeList::AddOffset(dw_addr_t offset)
+//{
+//    if (!ranges.empty())
+//    {
+//        Range::iterator pos = ranges.begin();
+//        Range::iterator end_pos = ranges.end();
+//        for (pos = ranges.begin(); pos != end_pos; ++pos)
+//        {
+//            // assert for unsigned overflows
+//            assert (~pos->begin_offset >= offset);
+//            assert (~pos->end_offset >= offset);
+//            pos->begin_offset += offset;
+//            pos->end_offset += offset;
+//        }
+//    }
+//}
+//
+//void
+//DWARFDebugRanges::RangeList::SubtractOffset(dw_addr_t offset)
+//{
+//    if (!ranges.empty())
+//    {
+//        Range::iterator pos = ranges.begin();
+//        Range::iterator end_pos = ranges.end();
+//        for (pos = ranges.begin(); pos != end_pos; ++pos)
+//        {
+//            assert (pos->begin_offset >= offset);
+//            assert (pos->end_offset >= offset);
+//            pos->begin_offset -= offset;
+//            pos->end_offset -= offset;
+//        }
+//    }
+//}
+//
+//
+//const DWARFDebugRanges::Range*
+//DWARFDebugRanges::RangeList::RangeAtIndex(size_t i) const
+//{
+//    if (i < ranges.size())
+//        return &ranges[i];
+//    return NULL;
+//}
 
 bool
-DWARFDebugRanges::RangeList::Extract(SymbolFileDWARF* dwarf2Data, uint32_t* offset_ptr)
+DWARFDebugRanges::Extract(SymbolFileDWARF* dwarf2Data, uint32_t* offset_ptr, RangeList &range_list)
 {
-    Clear();
+    range_list.Clear();
+
     uint32_t range_offset = *offset_ptr;
     const DataExtractor& debug_ranges_data = dwarf2Data->get_debug_ranges_data();
     uint32_t addr_size = debug_ranges_data.GetAddressByteSize();
@@ -154,65 +122,65 @@ DWARFDebugRanges::RangeList::Extract(SymbolFileDWARF* dwarf2Data, uint32_t* offs
         }
 
         // Filter out empty ranges
-        if (begin != end)
-            ranges.push_back(Range(begin, end));
+        if (begin < end)
+            range_list.Append(Range(begin, end - begin));
     }
 
     // Make sure we consumed at least something
     return range_offset != *offset_ptr;
 }
 
-
-dw_addr_t
-DWARFDebugRanges::RangeList::LowestAddress(const dw_addr_t cu_base_addr) const
-{
-    dw_addr_t addr = DW_INVALID_ADDRESS;
-    dw_addr_t curr_base_addr = cu_base_addr;
-    if (!ranges.empty())
-    {
-        Range::const_iterator pos = ranges.begin();
-        Range::const_iterator end_pos = ranges.end();
-        for (pos = ranges.begin(); pos != end_pos; ++pos)
-        {
-            if (pos->begin_offset == DW_INVALID_ADDRESS)
-                curr_base_addr = pos->end_offset;
-            else if (curr_base_addr != DW_INVALID_ADDRESS)
-            {
-                dw_addr_t curr_addr = curr_base_addr + pos->begin_offset;
-                if (addr > curr_addr)
-                    addr = curr_addr;
-            }
-        }
-    }
-    return addr;
-}
-
-dw_addr_t
-DWARFDebugRanges::RangeList::HighestAddress(const dw_addr_t cu_base_addr) const
-{
-    dw_addr_t addr = 0;
-    dw_addr_t curr_base_addr = cu_base_addr;
-    if (!ranges.empty())
-    {
-        Range::const_iterator pos = ranges.begin();
-        Range::const_iterator end_pos = ranges.end();
-        for (pos = ranges.begin(); pos != end_pos; ++pos)
-        {
-            if (pos->begin_offset == DW_INVALID_ADDRESS)
-                curr_base_addr = pos->end_offset;
-            else if (curr_base_addr != DW_INVALID_ADDRESS)
-            {
-                dw_addr_t curr_addr = curr_base_addr + pos->end_offset;
-                if (addr < curr_addr)
-                    addr = curr_addr;
-            }
-        }
-    }
-    if (addr != 0)
-        return addr;
-    return DW_INVALID_ADDRESS;
-}
-
+//
+//dw_addr_t
+//DWARFDebugRanges::RangeList::LowestAddress(const dw_addr_t cu_base_addr) const
+//{
+//    dw_addr_t addr = DW_INVALID_ADDRESS;
+//    dw_addr_t curr_base_addr = cu_base_addr;
+//    if (!ranges.empty())
+//    {
+//        Range::const_iterator pos = ranges.begin();
+//        Range::const_iterator end_pos = ranges.end();
+//        for (pos = ranges.begin(); pos != end_pos; ++pos)
+//        {
+//            if (pos->begin_offset == DW_INVALID_ADDRESS)
+//                curr_base_addr = pos->end_offset;
+//            else if (curr_base_addr != DW_INVALID_ADDRESS)
+//            {
+//                dw_addr_t curr_addr = curr_base_addr + pos->begin_offset;
+//                if (addr > curr_addr)
+//                    addr = curr_addr;
+//            }
+//        }
+//    }
+//    return addr;
+//}
+//
+//dw_addr_t
+//DWARFDebugRanges::RangeList::HighestAddress(const dw_addr_t cu_base_addr) const
+//{
+//    dw_addr_t addr = 0;
+//    dw_addr_t curr_base_addr = cu_base_addr;
+//    if (!ranges.empty())
+//    {
+//        Range::const_iterator pos = ranges.begin();
+//        Range::const_iterator end_pos = ranges.end();
+//        for (pos = ranges.begin(); pos != end_pos; ++pos)
+//        {
+//            if (pos->begin_offset == DW_INVALID_ADDRESS)
+//                curr_base_addr = pos->end_offset;
+//            else if (curr_base_addr != DW_INVALID_ADDRESS)
+//            {
+//                dw_addr_t curr_addr = curr_base_addr + pos->end_offset;
+//                if (addr < curr_addr)
+//                    addr = curr_addr;
+//            }
+//        }
+//    }
+//    if (addr != 0)
+//        return addr;
+//    return DW_INVALID_ADDRESS;
+//}
+//
 
 void
 DWARFDebugRanges::Dump(Stream &s, const DataExtractor& debug_ranges_data, uint32_t* offset_ptr, dw_addr_t cu_base_addr)
diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugRanges.h b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugRanges.h
index 362b99dc766..9145cc12648 100644
--- a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugRanges.h
+++ b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugRanges.h
@@ -11,66 +11,17 @@
 #define SymbolFileDWARF_DWARFDebugRanges_h_
 
 #include "SymbolFileDWARF.h"
+
 #include <map>
 #include <vector>
 
+#include "lldb/Core/RangeMap.h"
 
 class DWARFDebugRanges
 {
 public:
-
-    //------------------------------------------------------------------
-    // Address range
-    //------------------------------------------------------------------
-    struct Range
-    {
-        Range(dw_addr_t begin = DW_INVALID_ADDRESS, dw_addr_t end = DW_INVALID_ADDRESS) :
-            begin_offset(begin),
-            end_offset(end)
-        {
-        }
-
-        void Clear()
-        {
-            begin_offset = DW_INVALID_ADDRESS;
-            end_offset = DW_INVALID_ADDRESS;
-        }
-
-        dw_addr_t   begin_offset;
-        dw_addr_t   end_offset;
-
-        typedef std::vector<Range>          collection;
-        typedef collection::iterator        iterator;
-        typedef collection::const_iterator  const_iterator;
-
-    };
-
-    //------------------------------------------------------------------
-    // Collection of ranges
-    //------------------------------------------------------------------
-    struct RangeList
-    {
-            RangeList() :
-                ranges()
-            {
-            }
-
-        bool Extract(SymbolFileDWARF* dwarf2Data, uint32_t* offset_ptr);
-        bool AddRange(dw_addr_t lo_addr, dw_addr_t hi_addr);
-        void Clear()
-            {
-                ranges.clear();
-            }
-
-        dw_addr_t LowestAddress(const dw_addr_t base_addr) const;
-        dw_addr_t HighestAddress(const dw_addr_t base_addr) const;
-        void AddOffset(dw_addr_t offset);
-        void SubtractOffset(dw_addr_t offset);
-        size_t Size() const;
-        const Range* RangeAtIndex(size_t i) const;
-        const Range* Lookup(dw_addr_t offset) const;
-        Range::collection   ranges;
-    };
+    typedef lldb_private::RangeArray<dw_addr_t, dw_addr_t> RangeList;
+    typedef RangeList::Entry Range;
 
     DWARFDebugRanges();
     ~DWARFDebugRanges();
@@ -79,6 +30,12 @@ public:
     bool FindRanges(dw_offset_t debug_ranges_offset, DWARFDebugRanges::RangeList& range_list) const;
 
 protected:
+
+    bool
+    Extract (SymbolFileDWARF* dwarf2Data, 
+             uint32_t* offset_ptr, 
+             RangeList &range_list);
+
     typedef std::map<dw_offset_t, RangeList>    range_map;
     typedef range_map::iterator                 range_map_iterator;
     typedef range_map::const_iterator           range_map_const_iterator;
diff --git a/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp b/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp
index 5204d070ff5..bcbb448807e 100644
--- a/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp
+++ b/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp
@@ -650,20 +650,19 @@ SymbolFileDWARF::ParseCompileUnitAtIndex(uint32_t cu_idx)
 }
 
 static void
-AddRangesToBlock
-(
-    Block& block,
-    DWARFDebugRanges::RangeList& ranges,
-    addr_t block_base_addr
-)
+AddRangesToBlock (Block& block,
+                  DWARFDebugRanges::RangeList& ranges,
+                  addr_t block_base_addr)
 {
-    ranges.SubtractOffset (block_base_addr);
-    size_t range_idx = 0;
-    const DWARFDebugRanges::Range *debug_range;
-    for (range_idx = 0; (debug_range = ranges.RangeAtIndex(range_idx)) != NULL; range_idx++)
+    const size_t num_ranges = ranges.GetSize();
+    for (size_t i = 0; i<num_ranges; ++i)
     {
-        block.AddRange(VMRange (debug_range->begin_offset, debug_range->end_offset));
+        const DWARFDebugRanges::Range &range = ranges.GetEntryRef (i);
+        const addr_t range_base = range.GetRangeBase();
+        assert (range_base >= block_base_addr);
+        block.AddRange(Block::Range (range_base - block_base_addr, range.GetByteSize()));;
     }
+    block.FinalizeRanges ();
 }
 
 
@@ -690,8 +689,8 @@ SymbolFileDWARF::ParseCompileUnitFunction (const SymbolContext& sc, DWARFCompile
     {
         // Union of all ranges in the function DIE (if the function is discontiguous)
         AddressRange func_range;
-        lldb::addr_t lowest_func_addr = func_ranges.LowestAddress(0);
-        lldb::addr_t highest_func_addr = func_ranges.HighestAddress(0);
+        lldb::addr_t lowest_func_addr = func_ranges.GetMinRangeBase (0);
+        lldb::addr_t highest_func_addr = func_ranges.GetMaxRangeEnd (0);
         if (lowest_func_addr != LLDB_INVALID_ADDRESS && lowest_func_addr <= highest_func_addr)
         {
             func_range.GetBaseAddress().ResolveAddressUsingFileSections (lowest_func_addr, m_obj_file->GetSectionList());
@@ -1054,7 +1053,7 @@ SymbolFileDWARF::ParseFunctionBlocks
                     if (tag == DW_TAG_subprogram)
                     {
                         assert (subprogram_low_pc == LLDB_INVALID_ADDRESS);
-                        subprogram_low_pc = ranges.LowestAddress(0);
+                        subprogram_low_pc = ranges.GetMinRangeBase(0);
                     }
                     else if (tag == DW_TAG_inlined_subroutine)
                     {
@@ -1068,7 +1067,7 @@ SymbolFileDWARF::ParseFunctionBlocks
                         // function the offset will be for that function.  
                         if (subprogram_low_pc == LLDB_INVALID_ADDRESS)
                         {
-                            subprogram_low_pc = ranges.LowestAddress(0);
+                            subprogram_low_pc = ranges.GetMinRangeBase(0);
                         }
                     }