[BreakpointList] Simplify/modernize BreakpointList (NFC)

[JDevlieghere]

Summary

I was looking at the code in BreakpointList.cpp and found it deserved a quick cleanup.

• Extract duplicate code
• Use range-based for loop
• Use early return in loops

[JDevlieghere]

I wonder if we should use a vector instead of a list here too. For small data sets a std::vector usually outperforms a std::list. I *think* the data-locality would outweigh the cost of copying the shared pointers.

[vsk]

Looks like a nice/reasonable cleanup, thanks!

Based on the coverage report (https://teemperor.de/lldb-coverage/coverage/Users/vsk/src/llvm.org-lldbsan/llvm/tools/lldb/source/Breakpoint/BreakpointList.cpp.html#L217) and benchmarks (https://teemperor.de/lldb-bench/static.html) GetBreakpointAtIndex doesn't looks that hot, so I'm not sure it's worth changing / accidentally regressing.

source/Breakpoint/BreakpointList.cpp

196

Just call the non-const overload and const_cast?

[aprantl]

source/Breakpoint/BreakpointList.cpp

18

perhaps:

• factor out bp->GetTarget()?
• pass a BerakpointSP & or Breakpoint & to avoid shared pointer traffic?

189

is the whole point of this loop to do something like m_breakpoints[i]?
why not std::next(..., i) ?

200

separate commit?

[clayborg]

Second vote from me to switch to a std::vector since we have a function get breakpoint at index. Other than that, looks good.

[clayborg]

source/Breakpoint/BreakpointList.cpp

22

If we don't pass a "BreakpointSP& sp", then use std::move?

123–125

If m_breakpoints is a std::vector, we can keep it sorted and use std::lower_bound for faster lookups

130

ditto

188

If we use std::vector this will be O(1)

196

If we use std::vector this will be O(1)

[JDevlieghere]

• Use std::vector
• Code review feedback
• Remove code duplication when returning a const by value.

[JDevlieghere]

source/Breakpoint/BreakpointList.cpp

200

I'm happy to split it up but since I'm touching so much already might as well merge it into a single change.

[aprantl]

source/Breakpoint/BreakpointList.cpp

49

very nice!

122

also nice!

[clayborg]

If we keep the list sorted we might be able to improve finding breakpoints by ID, but that can be done if we need to. BreakpointList::Add would need to insert it sorted, then we can get better than O(n) performance on FindBreakpointByID and Remove (anything that was using find_if when it is searching for a breakpoint by ID).

[JDevlieghere]

In D56425#1350234, @clayborg wrote:

If we keep the list sorted we might be able to improve finding breakpoints by ID, but that can be done if we need to. BreakpointList::Add would need to insert it sorted, then we can get better than O(n) performance on FindBreakpointByID and Remove (anything that was using find_if when it is searching for a breakpoint by ID).

I'll do this as a follow-up.

[JDevlieghere]

In D56425#1350236, @JDevlieghere wrote:

In D56425#1350234, @clayborg wrote:

If we keep the list sorted we might be able to improve finding breakpoints by ID, but that can be done if we need to. BreakpointList::Add would need to insert it sorted, then we can get better than O(n) performance on FindBreakpointByID and Remove (anything that was using find_if when it is searching for a breakpoint by ID).

I'll do this as a follow-up.

On second thought, maybe it's not such a good idea after all. Internal breakpoints are negative so if we keep the vector sorted we'd always insert them at the front of the vector. We could change strategies based on whether the list is internal or not, but that seems overkill, especially given the code is not that hot as Vedant pointed out.

[clayborg]

In D56425#1350253, @JDevlieghere wrote:

In D56425#1350236, @JDevlieghere wrote:

In D56425#1350234, @clayborg wrote:

If we keep the list sorted we might be able to improve finding breakpoints by ID, but that can be done if we need to. BreakpointList::Add would need to insert it sorted, then we can get better than O(n) performance on FindBreakpointByID and Remove (anything that was using find_if when it is searching for a breakpoint by ID).

I'll do this as a follow-up.

On second thought, maybe it's not such a good idea after all. Internal breakpoints are negative so if we keep the vector sorted we'd always insert them at the front of the vector. We could change strategies based on whether the list is internal or not, but that seems overkill, especially given the code is not that hot as Vedant pointed out.

No worries. This is why I mentioned "if we need to". Fine to wait until we need to do this for some reason that proves to be an efficiency issue

source/Breakpoint/BreakpointList.cpp

 //===-- BreakpointList.cpp --------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "lldb/Breakpoint/BreakpointList.h"
 
 #include "lldb/Target/Target.h"
 
 using namespace lldb;
 using namespace lldb_private;
 
+static void NotifyChange(BreakpointSP bp, BreakpointEventType event) {
+  if (bp->GetTarget().EventTypeHasListeners(
+          Target::eBroadcastBitBreakpointChanged))
+    bp->GetTarget().BroadcastEvent(
+        Target::eBroadcastBitBreakpointChanged,
+        new Breakpoint::BreakpointEventData(event, bp));
+}
+
 BreakpointList::BreakpointList(bool is_internal)
     : m_mutex(), m_breakpoints(), m_next_break_id(0),
       m_is_internal(is_internal) {}
 
 BreakpointList::~BreakpointList() {}
 
 break_id_t BreakpointList::Add(BreakpointSP &bp_sp, bool notify) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
   // Internal breakpoint IDs are negative, normal ones are positive
   bp_sp->SetID(m_is_internal ? --m_next_break_id : ++m_next_break_id);
 
   m_breakpoints.push_back(bp_sp);
-  if (notify) {
-    if (bp_sp->GetTarget().EventTypeHasListeners(
-            Target::eBroadcastBitBreakpointChanged))
-      bp_sp->GetTarget().BroadcastEvent(Target::eBroadcastBitBreakpointChanged,
-                                        new Breakpoint::BreakpointEventData(
-                                            eBreakpointEventTypeAdded, bp_sp));
-  }
+  if (notify)
+    NotifyChange(bp_sp, eBreakpointEventTypeAdded);
   return bp_sp->GetID();
 }
 
 bool BreakpointList::Remove(break_id_t break_id, bool notify) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
+
   bp_collection::iterator pos = GetBreakpointIDIterator(break_id); // Predicate
-  if (pos != m_breakpoints.end()) {
-    BreakpointSP bp_sp(*pos);
-    m_breakpoints.erase(pos);
-    if (notify) {
-      if (bp_sp->GetTarget().EventTypeHasListeners(
-              Target::eBroadcastBitBreakpointChanged))
-        bp_sp->GetTarget().BroadcastEvent(
-            Target::eBroadcastBitBreakpointChanged,
-            new Breakpoint::BreakpointEventData(eBreakpointEventTypeRemoved,
-                                                bp_sp));
-    }
-    return true;
-  }
-  return false;
-}
+  if (pos == m_breakpoints.end())
+    return false;
+
+  if (notify)
+    NotifyChange(bp_sp, eBreakpointEventTypeRemoved);
 
 void BreakpointList::RemoveInvalidLocations(const ArchSpec &arch) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
   for (const auto &bp_sp : m_breakpoints)
     bp_sp->RemoveInvalidLocations(arch);
 }
 
 void BreakpointList::SetEnabledAll(bool enabled) {
if (bp_sp->AllowDisable())
       bp_sp->SetEnabled(enabled);
 }
 
 void BreakpointList::RemoveAll(bool notify) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
   ClearAllBreakpointSites();
 
   if (notify) {
-    bp_collection::iterator pos, end = m_breakpoints.end();
-    for (pos = m_breakpoints.begin(); pos != end; ++pos) {
-      if ((*pos)->GetTarget().EventTypeHasListeners(
-              Target::eBroadcastBitBreakpointChanged)) {
-        (*pos)->GetTarget().BroadcastEvent(
-            Target::eBroadcastBitBreakpointChanged,
-            new Breakpoint::BreakpointEventData(eBreakpointEventTypeRemoved,
-                                                *pos));
-      }
-    }
+    for (const auto &bp_sp : m_breakpoints)
+      NotifyChange(bp_sp, eBreakpointEventTypeRemoved);
   }
-  m_breakpoints.erase(m_breakpoints.begin(), m_breakpoints.end());
+
+  m_breakpoints.clear();
 }
 
 void BreakpointList::RemoveAllowed(bool notify) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 
   bp_collection::iterator pos, end = m_breakpoints.end();
   if (notify) {
-    for (pos = m_breakpoints.begin(); pos != end; ++pos) {
-      if(!(*pos)->AllowDelete())
-        continue;
-      if ((*pos)->GetTarget().EventTypeHasListeners(
-              Target::eBroadcastBitBreakpointChanged)) {
-        (*pos)->GetTarget().BroadcastEvent(
-            Target::eBroadcastBitBreakpointChanged,
-            new Breakpoint::BreakpointEventData(eBreakpointEventTypeRemoved,
-                                                *pos));
-      }
+    for (const auto &bp_sp : m_breakpoints) {
+      if (bp_sp->AllowDelete())
+        NotifyChange(bp_sp, eBreakpointEventTypeRemoved);
     }
   }
+
   pos = m_breakpoints.begin();
   while ( pos != end) {
     auto bp = *pos;
     if (bp->AllowDelete()) {
       bp->ClearAllBreakpointSites();
       pos = m_breakpoints.erase(pos);
     } else
       pos++;
   }
 }
 
 class BreakpointIDMatches {
 public:
   BreakpointIDMatches(break_id_t break_id) : m_break_id(break_id) {}
 
   bool operator()(const BreakpointSP &bp) const {
     return m_break_id == bp->GetID();
   }
 
 private:
   const break_id_t m_break_id;
 };
 
 BreakpointList::bp_collection::iterator
 BreakpointList::GetBreakpointIDIterator(break_id_t break_id) {
   return std::find_if(m_breakpoints.begin(),
                       m_breakpoints.end(),            // Search full range
                       BreakpointIDMatches(break_id)); // Predicate
 }
 
 BreakpointList::bp_collection::const_iterator
 BreakpointList::GetBreakpointIDConstIterator(break_id_t break_id) const {
   return std::find_if(m_breakpoints.begin(),
                       m_breakpoints.end(),            // Search full range
                       BreakpointIDMatches(break_id)); // Predicate
 }
 
 BreakpointSP BreakpointList::FindBreakpointByID(break_id_t break_id) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
   BreakpointSP stop_sp;
   bp_collection::iterator pos = GetBreakpointIDIterator(break_id);
void BreakpointList::Dump(Stream *s) const {
   s->IndentMore();
   for (const auto &bp_sp : m_breakpoints)
     bp_sp->Dump(s);
   s->IndentLess();
 }
 
 BreakpointSP BreakpointList::GetBreakpointAtIndex(size_t i) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
-  BreakpointSP stop_sp;
-  bp_collection::iterator end = m_breakpoints.end();
-  bp_collection::iterator pos;
   size_t curr_i = 0;
-  for (pos = m_breakpoints.begin(), curr_i = 0; pos != end; ++pos, ++curr_i) {
+  for (const auto &bp_sp : m_breakpoints) {
     if (curr_i == i)
-      stop_sp = *pos;
+      return bp_sp;
+    curr_i++;
   }
-  return stop_sp;
+  return {};
 }
 
 const BreakpointSP BreakpointList::GetBreakpointAtIndex(size_t i) const {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
   BreakpointSP stop_sp;
-  bp_collection::const_iterator end = m_breakpoints.end();
-  bp_collection::const_iterator pos;
   size_t curr_i = 0;
-  for (pos = m_breakpoints.begin(), curr_i = 0; pos != end; ++pos, ++curr_i) {
+  for (const auto &bp_sp : m_breakpoints) {
     if (curr_i == i)
-      stop_sp = *pos;
+      return bp_sp;
+    curr_i++;
   }
-  return stop_sp;
+  return {};
 }
 
 void BreakpointList::UpdateBreakpoints(ModuleList &module_list, bool added,
                                        bool delete_locations) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
   for (const auto &bp_sp : m_breakpoints)
     bp_sp->ModulesChanged(module_list, added, delete_locations);
 }