From 25495c9b4c05cb52bacdbc91ba7ee7da7b9a857c Mon Sep 17 00:00:00 2001 From: Felipe de Azevedo Piovezan Date: Tue, 9 May 2023 14:58:29 -0400 Subject: [lldb][NFCI] Remove n^2 loops and simplify iterator usage The code inside Broadcaster makes usage of iterators using olden C++ coding style. Hidden in this old style is a couple of N^2 loops: we iterate over a map (sequentially), removing the first element that matches some predicate. The search is _always_ done from the start of the map, which implies that, if the map has N elements and if all matches happen on the second half of the map, then we visit the first N/2 elements exactly N/2 * N/2 times. Ideally some of the code here would benefit from `std::map`s own "erase_if", but this is only available with C++20: https://en.cppreference.com/w/cpp/container/map/erase_if We spent quite some time trying to make these loops more elegant, but it is surprisingly tricky to do so. Differential Revision: https://reviews.llvm.org/D150219 --- lldb/source/Utility/Broadcaster.cpp | 59 ++++++++++++++++--------------------- 1 file changed, 25 insertions(+), 34 deletions(-) (limited to 'lldb') diff --git a/lldb/source/Utility/Broadcaster.cpp b/lldb/source/Utility/Broadcaster.cpp index 66c78978571f..58e393863b5a 100644 --- a/lldb/source/Utility/Broadcaster.cpp +++ b/lldb/source/Utility/Broadcaster.cpp @@ -377,13 +377,10 @@ bool BroadcasterManager::UnregisterListenerForEvents( // Go through the map and delete the exact matches, and build a list of // matches that weren't exact to re-add: - while (true) { - collection::iterator iter, end_iter = m_event_map.end(); - iter = find_if(m_event_map.begin(), end_iter, - listener_matches_and_shared_bits); - if (iter == end_iter) { + for (auto iter = m_event_map.begin(), end = m_event_map.end();;) { + iter = find_if(iter, end, listener_matches_and_shared_bits); + if (iter == end) break; - } uint32_t iter_event_bits = (*iter).first.GetEventBits(); removed_some = true; @@ -392,12 +389,12 @@ bool BroadcasterManager::UnregisterListenerForEvents( to_be_readded.emplace_back(event_spec.GetBroadcasterClass(), new_event_bits); } - m_event_map.erase(iter); + iter = m_event_map.erase(iter); } // Okay now add back the bits that weren't completely removed: - for (size_t i = 0; i < to_be_readded.size(); i++) { - m_event_map.insert(event_listener_key(to_be_readded[i], listener_sp)); + for (const auto &event : to_be_readded) { + m_event_map.insert(event_listener_key(event, listener_sp)); } return removed_some; @@ -412,9 +409,8 @@ ListenerSP BroadcasterManager::GetListenerForEventSpec( return input.first.IsContainedIn(event_spec); }; - collection::const_iterator iter, end_iter = m_event_map.end(); - iter = find_if(m_event_map.begin(), end_iter, event_spec_matches); - if (iter != end_iter) + auto iter = llvm::find_if(m_event_map, event_spec_matches); + if (iter != m_event_map.end()) return (*iter).second; return nullptr; @@ -427,24 +423,21 @@ void BroadcasterManager::RemoveListener(Listener *listener) { return input.get() == listener; }; - listener_collection::iterator iter = m_listeners.begin(), - end_iter = m_listeners.end(); - - iter = std::find_if(iter, end_iter, listeners_predicate); - if (iter != end_iter) + if (auto iter = llvm::find_if(m_listeners, listeners_predicate); + iter != m_listeners.end()) m_listeners.erase(iter); - while (true) { - auto events_predicate = - [&listener](const event_listener_key &input) -> bool { - return input.second.get() == listener; - }; - collection::iterator iter, end_iter = m_event_map.end(); - iter = find_if(m_event_map.begin(), end_iter, events_predicate); - if (iter == end_iter) + auto events_predicate = [listener](const event_listener_key &input) -> bool { + return input.second.get() == listener; + }; + + // TODO: use 'std::map::erase_if' when moving to c++20. + for (auto iter = m_event_map.begin(), end = m_event_map.end();;) { + iter = find_if(iter, end, events_predicate); + if (iter == end) break; - m_event_map.erase(iter); + iter = m_event_map.erase(iter); } } @@ -459,13 +452,13 @@ void BroadcasterManager::RemoveListener(const lldb::ListenerSP &listener_sp) { if (m_listeners.erase(listener_sp) == 0) return; - while (true) { - collection::iterator iter, end_iter = m_event_map.end(); - iter = find_if(m_event_map.begin(), end_iter, listener_matches); + // TODO: use 'std::map::erase_if' when moving to c++20. + for (auto iter = m_event_map.begin(), end_iter = m_event_map.end();;) { + iter = find_if(iter, end_iter, listener_matches); if (iter == end_iter) break; - m_event_map.erase(iter); + iter = m_event_map.erase(iter); } } @@ -490,11 +483,9 @@ void BroadcasterManager::SignUpListenersForBroadcaster( void BroadcasterManager::Clear() { std::lock_guard guard(m_manager_mutex); - listener_collection::iterator end_iter = m_listeners.end(); - for (listener_collection::iterator iter = m_listeners.begin(); - iter != end_iter; iter++) - (*iter)->BroadcasterManagerWillDestruct(this->shared_from_this()); + for (auto &listener : m_listeners) + listener->BroadcasterManagerWillDestruct(this->shared_from_this()); m_listeners.clear(); m_event_map.clear(); } -- cgit v1.2.1