[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

163–164

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?

163–164

separate commit?

163–164

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

[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?

110–113

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

117–118

ditto

163–164

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

163–164

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

163–164

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!

106

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

include/lldb/Breakpoint/BreakpointList.h

public:
   lldb::break_id_t Add(lldb::BreakpointSP &bp_sp, bool notify);
 
   //------------------------------------------------------------------
   /// Standard "Dump" method.  At present it does nothing.
   //------------------------------------------------------------------
   void Dump(Stream *s) const;
 
   //------------------------------------------------------------------
-  /// Returns a shared pointer to the breakpoint with id \a breakID.
-  ///
-  /// @param[in] breakID
-  ///   The breakpoint ID to seek for.
-  ///
-  /// @result
-  ///   A shared pointer to the breakpoint.  May contain a NULL pointer if the
-  ///   breakpoint doesn't exist.
-  //------------------------------------------------------------------
-  lldb::BreakpointSP FindBreakpointByID(lldb::break_id_t breakID);
-
-  //------------------------------------------------------------------
   /// Returns a shared pointer to the breakpoint with id \a breakID.  Const
   /// version.
   ///
   /// @param[in] breakID
   ///   The breakpoint ID to seek for.
   ///
   /// @result
   ///   A shared pointer to the breakpoint.  May contain a NULL pointer if the
   ///   breakpoint doesn't exist.
   //------------------------------------------------------------------
-  const lldb::BreakpointSP FindBreakpointByID(lldb::break_id_t breakID) const;
+  lldb::BreakpointSP FindBreakpointByID(lldb::break_id_t breakID) const;
 
   //------------------------------------------------------------------
   /// Returns a shared pointer to the breakpoint with index \a i.
   ///
   /// @param[in] i
   ///   The breakpoint index to seek for.
   ///
   /// @result
   ///   A shared pointer to the breakpoint.  May contain a NULL pointer if the
   ///   breakpoint doesn't exist.
   //------------------------------------------------------------------
-  lldb::BreakpointSP GetBreakpointAtIndex(size_t i);
-
-  //------------------------------------------------------------------
-  /// Returns a shared pointer to the breakpoint with index \a i, const
-  /// version
-  ///
-  /// @param[in] i
-  ///   The breakpoint index to seek for.
-  ///
-  /// @result
-  ///   A shared pointer to the breakpoint.  May contain a NULL pointer if the
-  ///   breakpoint doesn't exist.
-  //------------------------------------------------------------------
-  const lldb::BreakpointSP GetBreakpointAtIndex(size_t i) const;
+  lldb::BreakpointSP GetBreakpointAtIndex(size_t i) const;
 
   //------------------------------------------------------------------
   /// Find all the breakpoints with a given name
   ///
   /// @param[in] name
   ///   The breakpoint name for which to search.
   ///
   /// @result
public:
   /// Sets the passed in Locker to hold the Breakpoint List mutex.
   ///
   /// @param[in] locker
   ///   The locker object that is set.
   //------------------------------------------------------------------
   void GetListMutex(std::unique_lock<std::recursive_mutex> &lock);
 
 protected:
-  typedef std::list<lldb::BreakpointSP> bp_collection;
+  typedef std::vector<lldb::BreakpointSP> bp_collection;
 
   bp_collection::iterator GetBreakpointIDIterator(lldb::break_id_t breakID);
 
   bp_collection::const_iterator
   GetBreakpointIDConstIterator(lldb::break_id_t breakID) const;
 
   std::recursive_mutex &GetMutex() const { return m_mutex; }
 
   mutable std::recursive_mutex m_mutex;
-  bp_collection m_breakpoints; // The breakpoint list, currently a list.
+  bp_collection m_breakpoints;
   lldb::break_id_t m_next_break_id;
   bool m_is_internal;
 
 public:
   typedef LockingAdaptedIterable<bp_collection, lldb::BreakpointSP,
                                  list_adapter, std::recursive_mutex>
       BreakpointIterable;
   BreakpointIterable Breakpoints() {

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(const BreakpointSP &bp, BreakpointEventType event) {
+  Target &target = bp->GetTarget();
+  if (target.EventTypeHasListeners(Target::eBroadcastBitBreakpointChanged))
+    target.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;
-  }
+
+  auto it = std::find_if(
+      m_breakpoints.begin(), m_breakpoints.end(),
+      [&](const BreakpointSP &bp) { return bp->GetID() == break_id; });
+
+  if (it == m_breakpoints.end())
     return false;
+
+  if (notify)
+    NotifyChange(*it, eBreakpointEventTypeRemoved);
+
+  m_breakpoints.erase(it);
+
+  return true;
 }
 
 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);
 }
 
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));
-      }
-    }
-  }
-  pos = m_breakpoints.begin();
-  while ( pos != end) {
-    auto bp = *pos;
-    if (bp->AllowDelete()) {
-      bp->ClearAllBreakpointSites();
-      pos = m_breakpoints.erase(pos);
-    } else
-      pos++;
-  }
+  for (const auto &bp_sp : m_breakpoints) {
+    if (bp_sp->AllowDelete())
+      bp_sp->ClearAllBreakpointSites();
+    if (notify)
+      NotifyChange(bp_sp, eBreakpointEventTypeRemoved);
   }
 
-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();
-  }
+  m_breakpoints.erase(
+      std::remove_if(m_breakpoints.begin(), m_breakpoints.end(),
+                     [&](const BreakpointSP &bp) { return bp->AllowDelete(); }),
+      m_breakpoints.end());
 
-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
+  return std::find_if(
+      m_breakpoints.begin(), m_breakpoints.end(),
+      [&](const BreakpointSP &bp) { return bp->GetID() == break_id; });
 }
 
 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);
-  if (pos != m_breakpoints.end())
-    stop_sp = *pos;
-
-  return stop_sp;
+  return std::find_if(
+      m_breakpoints.begin(), m_breakpoints.end(),
+      [&](const BreakpointSP &bp) { return bp->GetID() == break_id; });
 }
 
-const BreakpointSP
-BreakpointList::FindBreakpointByID(break_id_t break_id) const {
+BreakpointSP BreakpointList::FindBreakpointByID(break_id_t break_id) const {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
-  BreakpointSP stop_sp;
-  bp_collection::const_iterator pos = GetBreakpointIDConstIterator(break_id);
-  if (pos != m_breakpoints.end())
-    stop_sp = *pos;
 
-  return stop_sp;
+  auto it = GetBreakpointIDConstIterator(break_id);
+  if (it != m_breakpoints.end())
+    return *it;
+  return {};
 }
 
 bool BreakpointList::FindBreakpointsByName(const char *name,
                                            BreakpointList &matching_bps) {
   Status error;
   if (!name)
     return false;
 
   if (!BreakpointID::StringIsBreakpointName(llvm::StringRef(name), error))
     return false;
 
   for (BreakpointSP bkpt_sp : Breakpoints()) {
     if (bkpt_sp->MatchesName(name)) {
       matching_bps.Add(bkpt_sp, false);
     }
   }
+
   return true;
 }
 
 void BreakpointList::Dump(Stream *s) const {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
   s->Printf("%p: ", static_cast<const void *>(this));
   s->Indent();
   s->Printf("BreakpointList with %u Breakpoints:\n",
             (uint32_t)m_breakpoints.size());
   s->IndentMore();
   for (const auto &bp_sp : m_breakpoints)
     bp_sp->Dump(s);
   s->IndentLess();
 }
 
-BreakpointSP BreakpointList::GetBreakpointAtIndex(size_t i) {
+BreakpointSP BreakpointList::GetBreakpointAtIndex(size_t i) const {
   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) {
-    if (curr_i == i)
-      stop_sp = *pos;
-  }
-  return stop_sp;
-}
-
-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) {
-    if (curr_i == i)
-      stop_sp = *pos;
-  }
-  return stop_sp;
+  if (i < m_breakpoints.size())
+    return m_breakpoints[i];
+  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);
 }