diff options
author | Marc Mutz <marc.mutz@kdab.com> | 2019-07-11 21:52:01 +0200 |
---|---|---|
committer | Marc Mutz <marc.mutz@kdab.com> | 2019-07-15 13:09:37 +0200 |
commit | 2e5b8032a27f678b1f514c7402fe2a808e7fcdcc (patch) | |
tree | ae1817de684c61c7a2b9e3bf2a10d01497b63970 | |
parent | a7383b4b6dde54569e6fdfa0888e474a37416a51 (diff) |
Optimize QInotifyFileSystemWatcherEngine::getPathFromID()
The code basically wants to get the last element of equal_range(id).
The problem is that backwards iteration on QHash is very expensive,
because it's implemented as forward search with wrap-around at bucket
end.
So it was implementing its own equal_range with look-ahead. The
problem is that it compared each key in the equal_range twice: once in
the if, and once more in the following while iteration.
I expect to see this kind of algorithm more as we move away from the
fake bidirectionalism of QHash, so I decided to implement it in a
generic way. We can copy it somewhere else when we find more users.
Change-Id: I7951652107ab897f6a456035f02e0339835e078d
Reviewed-by: Volker Hilsheimer <volker.hilsheimer@qt.io>
Reviewed-by: Friedemann Kleint <Friedemann.Kleint@qt.io>
Reviewed-by: MÃ¥rten Nordheim <marten.nordheim@qt.io>
-rw-r--r-- | src/corelib/io/qfilesystemwatcher_inotify.cpp | 27 |
1 files changed, 19 insertions, 8 deletions
diff --git a/src/corelib/io/qfilesystemwatcher_inotify.cpp b/src/corelib/io/qfilesystemwatcher_inotify.cpp index 5fb5685f42..ca1f6cc359 100644 --- a/src/corelib/io/qfilesystemwatcher_inotify.cpp +++ b/src/corelib/io/qfilesystemwatcher_inotify.cpp @@ -422,16 +422,27 @@ void QInotifyFileSystemWatcherEngine::readFromInotify() } } -QString QInotifyFileSystemWatcherEngine::getPathFromID(int id) const +template <typename Hash, typename Key> +typename Hash::const_iterator +find_last_in_equal_range(const Hash &c, const Key &key) { - QHash<int, QString>::const_iterator i = idToPath.find(id); - while (i != idToPath.constEnd() && i.key() == id) { - if ((i + 1) == idToPath.constEnd() || (i + 1).key() != id) { - return i.value(); - } + // find c.equal_range(key).second - 1 without backwards iteration: + auto i = c.find(key); + const auto end = c.cend(); + if (i == end) + return end; + decltype(i) prev; + do { + prev = i; ++i; - } - return QString(); + } while (i != end && i.key() == key); + return prev; +} + +QString QInotifyFileSystemWatcherEngine::getPathFromID(int id) const +{ + auto i = find_last_in_equal_range(idToPath, id); + return i == idToPath.cend() ? QString() : i.value() ; } QT_END_NAMESPACE |