Fixed the BreakpointLocationList to be able to do O(1) lookups on breakpoint
locations by ID. It used to be, worst case, O(N).
git-svn-id: https://llvm.org/svn/llvm-project/llvdb/trunk@124914 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/source/Breakpoint/Breakpoint.cpp b/source/Breakpoint/Breakpoint.cpp
index 346c774..7f40458 100644
--- a/source/Breakpoint/Breakpoint.cpp
+++ b/source/Breakpoint/Breakpoint.cpp
@@ -81,33 +81,33 @@
}
BreakpointLocationSP
-Breakpoint::AddLocation (Address &addr, bool *new_location)
+Breakpoint::AddLocation (const Address &addr, bool *new_location)
{
- BreakpointLocationSP bp_loc_sp (m_locations.FindByAddress(addr));
- if (bp_loc_sp)
- {
- if (new_location)
- *new_location = false;
- return bp_loc_sp;
- }
-
- bp_loc_sp.reset (new BreakpointLocation (m_locations.GetNextID(), *this, addr));
- m_locations.Add (bp_loc_sp);
- bp_loc_sp->ResolveBreakpointSite();
-
if (new_location)
- *new_location = true;
+ *new_location = false;
+ BreakpointLocationSP bp_loc_sp (m_locations.FindByAddress(addr));
+ if (!bp_loc_sp)
+ {
+ bp_loc_sp = m_locations.Create (*this, addr);
+ if (bp_loc_sp)
+ {
+ bp_loc_sp->ResolveBreakpointSite();
+
+ if (new_location)
+ *new_location = true;
+ }
+ }
return bp_loc_sp;
}
BreakpointLocationSP
-Breakpoint::FindLocationByAddress (Address &addr)
+Breakpoint::FindLocationByAddress (const Address &addr)
{
return m_locations.FindByAddress(addr);
}
break_id_t
-Breakpoint::FindLocationIDByAddress (Address &addr)
+Breakpoint::FindLocationIDByAddress (const Address &addr)
{
return m_locations.FindIDByAddress(addr);
}
@@ -127,7 +127,6 @@
BreakpointLocationSP
Breakpoint::GetLocationSP (BreakpointLocation *bp_loc_ptr)
{
- assert (bp_loc_ptr->GetBreakpoint().GetID() == GetID());
return m_locations.FindByID(bp_loc_ptr->GetID());
}
@@ -280,24 +279,25 @@
// 3) If we don't see this module in our breakpoint location list, call ResolveInModules.
ModuleList new_modules; // We'll stuff the "unseen" modules in this list, and then resolve
- // them after the locations pass. Have to do it this way because
- // resolving breakpoints will add new locations potentially.
+ // them after the locations pass. Have to do it this way because
+ // resolving breakpoints will add new locations potentially.
+
+ const size_t num_locs = m_locations.GetSize();
for (size_t i = 0; i < module_list.GetSize(); i++)
{
bool seen = false;
ModuleSP module_sp (module_list.GetModuleAtIndex (i));
- Module *module = module_sp.get();
if (!m_filter_sp->ModulePasses (module_sp))
continue;
- for (size_t loc_idx = 0; loc_idx < m_locations.GetSize(); loc_idx++)
+ for (size_t loc_idx = 0; loc_idx < num_locs; loc_idx++)
{
BreakpointLocationSP break_loc = m_locations.GetByIndex(loc_idx);
if (!break_loc->IsEnabled())
continue;
const Section *section = break_loc->GetAddress().GetSection();
- if (section == NULL || section->GetModule() == module)
+ if (section == NULL || section->GetModule() == module_sp.get())
{
if (!seen)
seen = true;
diff --git a/source/Breakpoint/BreakpointLocation.cpp b/source/Breakpoint/BreakpointLocation.cpp
index 4532114..388da6b 100644
--- a/source/Breakpoint/BreakpointLocation.cpp
+++ b/source/Breakpoint/BreakpointLocation.cpp
@@ -32,7 +32,7 @@
(
break_id_t loc_id,
Breakpoint &owner,
- Address &addr,
+ const Address &addr,
lldb::tid_t tid,
bool hardware
) :
diff --git a/source/Breakpoint/BreakpointLocationList.cpp b/source/Breakpoint/BreakpointLocationList.cpp
index 09f94ea..b4fcc58 100644
--- a/source/Breakpoint/BreakpointLocationList.cpp
+++ b/source/Breakpoint/BreakpointLocationList.cpp
@@ -23,8 +23,7 @@
BreakpointLocationList::BreakpointLocationList() :
m_locations(),
m_address_to_location (),
- m_mutex (Mutex::eMutexTypeRecursive),
- m_next_id (0)
+ m_mutex (Mutex::eMutexTypeRecursive)
{
}
@@ -32,17 +31,16 @@
{
}
-lldb::break_id_t
-BreakpointLocationList::Add (BreakpointLocationSP &bp_loc_sp)
+BreakpointLocationSP
+BreakpointLocationList::Create (Breakpoint &bp, const Address &addr)
{
- if (bp_loc_sp)
- {
- Mutex::Locker locker (m_mutex);
- m_locations.push_back (bp_loc_sp);
- m_address_to_location[bp_loc_sp->GetAddress()] = bp_loc_sp;
- return bp_loc_sp->GetID();
- }
- return LLDB_INVALID_BREAK_ID;
+ Mutex::Locker locker (m_mutex);
+ // The location ID is just the size of the location list + 1
+ lldb::break_id_t bp_loc_id = m_locations.size() + 1;
+ BreakpointLocationSP bp_loc_sp (new BreakpointLocation (bp_loc_id, bp, addr));
+ m_locations.push_back (bp_loc_sp);
+ m_address_to_location[addr] = bp_loc_sp;
+ return bp_loc_sp;
}
bool
@@ -62,7 +60,7 @@
}
lldb::break_id_t
-BreakpointLocationList::FindIDByAddress (Address &addr)
+BreakpointLocationList::FindIDByAddress (const Address &addr)
{
BreakpointLocationSP bp_loc_sp = FindByAddress (addr);
if (bp_loc_sp)
@@ -72,95 +70,19 @@
return LLDB_INVALID_BREAK_ID;
}
-bool
-BreakpointLocationList::Remove (lldb::break_id_t break_id)
-{
- Mutex::Locker locker (m_mutex);
- collection::iterator pos = GetIDIterator(break_id); // Predicate
- if (pos != m_locations.end())
- {
- m_address_to_location.erase ((*pos)->GetAddress());
- m_locations.erase(pos);
- return true;
- }
- return false;
-}
-
-
-class BreakpointLocationIDMatches
-{
-public:
- BreakpointLocationIDMatches (lldb::break_id_t break_id) :
- m_break_id(break_id)
- {
- }
-
- bool operator() (const BreakpointLocationSP &bp_loc_sp) const
- {
- return m_break_id == bp_loc_sp->GetID();
- }
-
-private:
- const lldb::break_id_t m_break_id;
-};
-
-class BreakpointLocationAddressMatches
-{
-public:
- BreakpointLocationAddressMatches (Address& addr) :
- m_addr(addr)
- {
- }
-
- bool operator() (const BreakpointLocationSP& bp_loc_sp) const
- {
- return Address::CompareFileAddress(m_addr, bp_loc_sp->GetAddress()) == 0;
- }
-
-private:
- const Address &m_addr;
-};
-
-BreakpointLocationList::collection::iterator
-BreakpointLocationList::GetIDIterator (lldb::break_id_t break_id)
-{
- Mutex::Locker locker (m_mutex);
- return std::find_if (m_locations.begin(),
- m_locations.end(),
- BreakpointLocationIDMatches(break_id));
-}
-
-BreakpointLocationList::collection::const_iterator
-BreakpointLocationList::GetIDConstIterator (lldb::break_id_t break_id) const
-{
- Mutex::Locker locker (m_mutex);
- return std::find_if (m_locations.begin(),
- m_locations.end(),
- BreakpointLocationIDMatches(break_id));
-}
-
BreakpointLocationSP
-BreakpointLocationList::FindByID (lldb::break_id_t break_id)
-{
- Mutex::Locker locker (m_mutex);
- BreakpointLocationSP stop_sp;
- collection::iterator pos = GetIDIterator(break_id);
- if (pos != m_locations.end())
- stop_sp = *pos;
-
- return stop_sp;
-}
-
-const BreakpointLocationSP
BreakpointLocationList::FindByID (lldb::break_id_t break_id) const
{
+ BreakpointLocationSP bp_loc_sp;
Mutex::Locker locker (m_mutex);
- BreakpointLocationSP stop_sp;
- collection::const_iterator pos = GetIDConstIterator(break_id);
- if (pos != m_locations.end())
- stop_sp = *pos;
-
- return stop_sp;
+ // We never remove a breakpoint locations, so the ID can be translated into
+ // the location index by subtracting 1
+ uint32_t idx = break_id - 1;
+ if (idx <= m_locations.size())
+ {
+ bp_loc_sp = m_locations[idx];
+ }
+ return bp_loc_sp;
}
size_t
@@ -193,18 +115,18 @@
}
const BreakpointLocationSP
-BreakpointLocationList::FindByAddress (Address &addr) const
+BreakpointLocationList::FindByAddress (const Address &addr) const
{
Mutex::Locker locker (m_mutex);
- BreakpointLocationSP stop_sp;
+ BreakpointLocationSP bp_loc_sp;
if (!m_locations.empty())
{
addr_map::const_iterator pos = m_address_to_location.find (addr);
if (pos != m_address_to_location.end())
- stop_sp = pos->second;
+ bp_loc_sp = pos->second;
}
- return stop_sp;
+ return bp_loc_sp;
}
void
@@ -226,22 +148,22 @@
BreakpointLocationList::GetByIndex (uint32_t i)
{
Mutex::Locker locker (m_mutex);
- BreakpointLocationSP stop_sp;
+ BreakpointLocationSP bp_loc_sp;
if (i < m_locations.size())
- stop_sp = m_locations[i];
+ bp_loc_sp = m_locations[i];
- return stop_sp;
+ return bp_loc_sp;
}
const BreakpointLocationSP
BreakpointLocationList::GetByIndex (uint32_t i) const
{
Mutex::Locker locker (m_mutex);
- BreakpointLocationSP stop_sp;
+ BreakpointLocationSP bp_loc_sp;
if (i < m_locations.size())
- stop_sp = m_locations[i];
+ bp_loc_sp = m_locations[i];
- return stop_sp;
+ return bp_loc_sp;
}
void
@@ -291,12 +213,6 @@
return resolve_count;
}
-break_id_t
-BreakpointLocationList::GetNextID()
-{
- return ++m_next_id;
-}
-
void
BreakpointLocationList::GetDescription (Stream *s, lldb::DescriptionLevel level)
{