diff options
author | Felipe de Azevedo Piovezan <fpiovezan@apple.com> | 2023-05-09 14:58:29 -0400 |
---|---|---|
committer | Felipe de Azevedo Piovezan <fpiovezan@apple.com> | 2023-05-10 06:18:27 -0400 |
commit | 25495c9b4c05cb52bacdbc91ba7ee7da7b9a857c (patch) | |
tree | 99784994dd51116091d1af32bb8e35ce355c0d25 /lldb | |
parent | 48bbc64a8ff5e3777a76a02cffd94b3786b93203 (diff) | |
download | llvm-25495c9b4c05cb52bacdbc91ba7ee7da7b9a857c.tar.gz |
[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
Diffstat (limited to 'lldb')
-rw-r--r-- | lldb/source/Utility/Broadcaster.cpp | 59 |
1 files changed, 25 insertions, 34 deletions
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<std::recursive_mutex> 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(); } |