diff --git a/src/core/autotests/CMakeLists.txt b/src/core/autotests/CMakeLists.txt --- a/src/core/autotests/CMakeLists.txt +++ b/src/core/autotests/CMakeLists.txt @@ -94,3 +94,4 @@ add_ruqola_test(messagecachetest.cpp) add_ruqola_test(commandtest.cpp) add_ruqola_test(commandstest.cpp) +add_ruqola_test(lrucachetest.cpp) diff --git a/src/widgets/room/autotests/pixmapcachetest.h b/src/core/autotests/lrucachetest.h rename from src/widgets/room/autotests/pixmapcachetest.h rename to src/core/autotests/lrucachetest.h --- a/src/widgets/room/autotests/pixmapcachetest.h +++ b/src/core/autotests/lrucachetest.h @@ -18,20 +18,20 @@ Boston, MA 02110-1301, USA. */ -#ifndef PIXMAPCACHETEST_H -#define PIXMAPCACHETEST_H +#ifndef LRUCACHETEST_H +#define LRUCACHETEST_H #include -class PixmapCacheTest : public QObject +class LRUCacheTest : public QObject { Q_OBJECT public: - explicit PixmapCacheTest(QObject *parent = nullptr); - ~PixmapCacheTest() override = default; + explicit LRUCacheTest(QObject *parent = nullptr); + ~LRUCacheTest() override = default; private Q_SLOTS: - void shouldCacheLastFivePixmaps(); + void shouldCacheLastFiveEntries(); }; -#endif // PIXMAPCACHETEST_H +#endif // LRUCACHETEST_H diff --git a/src/core/autotests/lrucachetest.cpp b/src/core/autotests/lrucachetest.cpp new file mode 100644 --- /dev/null +++ b/src/core/autotests/lrucachetest.cpp @@ -0,0 +1,99 @@ +/* + Copyright (c) 2020 David Faure + Copyright (c) 2020 Milian Wolff + + This library is free software; you can redistribute it and/or modify + it under the terms of the GNU Library General Public License as published + by the Free Software Foundation; either version 2 of the License or + ( at your option ) version 3 or, at the discretion of KDE e.V. + ( which shall act as a proxy as in section 14 of the GPLv3 ), any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public License + along with this library; see the file COPYING.LIB. If not, write to + the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, + Boston, MA 02110-1301, USA. +*/ + +#include "lrucachetest.h" + +#include +#include +#include + +#include +#include + +QTEST_MAIN(LRUCacheTest) + +LRUCacheTest::LRUCacheTest(QObject *parent) + : QObject(parent) +{ + QStandardPaths::setTestModeEnabled(true); +} + +void LRUCacheTest::shouldCacheLastFiveEntries() +{ + auto makeString = [](const char *prefix, int i) -> QString + { + return QLatin1String(prefix) + QString::number(i); + }; + + using Cache = LRUCache; + Cache cache; + auto contents = [&cache]() -> QVector + { + QVector ret(cache.size()); + std::transform(cache.begin(), cache.end(), ret.begin(), [](const Cache::Entry &entry) { + return entry.value; + }); + return ret; + }; + + QCOMPARE(cache.size(), 0); + QCOMPARE(cache.begin(), cache.end()); + QCOMPARE(cache.find(QString()), cache.end()); + + QVector expected; + for (int i = 1; i < 7; ++i) { + const auto expectedSizeBefore = std::min(i - 1, 5); + const auto expectedSizeAfter = std::min(i, 5); + QCOMPARE(cache.size(), expectedSizeBefore); + const auto key = makeString("key", i); + const auto value = makeString("value", i); + QCOMPARE(cache.find(key), cache.end()); + cache.insert(key, value); + QCOMPARE(cache.size(), expectedSizeAfter); + QCOMPARE(std::distance(cache.begin(), cache.find(key)), 0); + QCOMPARE(cache.find(key)->value, value); + expected.prepend(value); + if (expected.size() == 6) + expected.removeLast(); + QCOMPARE(contents(), expected); + } + + for (int i = 0; i < 10; ++i) { + const auto key = makeString("key", i); + const auto value = makeString("value", i); + if (i <= 1 || i >= 7) { + QCOMPARE(cache.find(key), cache.end()); + } else { + QCOMPARE(std::distance(cache.begin(), cache.find(key)), 0); + QCOMPARE(cache.find(key)->value, value); + QCOMPARE(value, expected.last()); + expected.removeLast(); + expected.prepend(value); + } + QCOMPARE(contents(), expected); + } + + auto value = makeString("value", 4); + QCOMPARE(cache.find(makeString("key", 4))->value, value); + QVERIFY(expected.removeOne(value)); + expected.prepend(value); + QCOMPARE(contents(), expected); +} diff --git a/src/core/lrucache.h b/src/core/lrucache.h new file mode 100644 --- /dev/null +++ b/src/core/lrucache.h @@ -0,0 +1,91 @@ +/* + Copyright (c) 2020 Milian Wolff + + This library is free software; you can redistribute it and/or modify + it under the terms of the GNU Library General Public License as published + by the Free Software Foundation; either version 2 of the License or + ( at your option ) version 3 or, at the discretion of KDE e.V. + ( which shall act as a proxy as in section 14 of the GPLv3 ), any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public License + along with this library; see the file COPYING.LIB. If not, write to + the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, + Boston, MA 02110-1301, USA. +*/ + +#ifndef LRUCACHE_H +#define LRUCACHE_H + +#include +#include + +template +class LRUCache +{ +public: + struct Entry + { + Key key; + Value value; + bool operator==(const Key &rhs) const + { + return key == rhs; + } + }; + using Entries = std::array; + using value_type = typename Entries::value_type; + using size_type = typename Entries::size_type; + using difference_type = typename Entries::difference_type; + // only const access + using reference = typename Entries::const_reference; + using const_reference = typename Entries::const_reference; + using pointer = typename Entries::const_pointer; + using iterator = typename Entries::const_iterator; + using const_iterator = typename Entries::const_iterator; + + std::size_t size() const { return mNumEntries; } + + const_iterator begin() const { return mEntries.begin(); } + const_iterator end() const { return std::next(mEntries.begin(), mNumEntries); } + + const_iterator find(const Key &key) + { + // using non-const iterators here since we will re-insert when we find + const auto begin = mEntries.begin(); + const auto end = std::next(mEntries.begin(), mNumEntries); + auto it = std::find(begin, end, key); + if (it == begin || it == end) // not found or already the last recently used one + return it; + + // rotate to mark entry as last recently used one + std::rotate(begin, it, it + 1); + return mEntries.cbegin(); + } + + void insert(Key key, Value value) + { + if (mNumEntries < mEntries.size()) { + // open up a new slot + ++mNumEntries; + } + + // right shift to make space at the front + std::rotate(mEntries.begin(), + std::next(mEntries.begin(), mNumEntries - 1), + std::next(mEntries.begin(), mNumEntries)); + + // insert up front + mEntries.front() = {std::move(key), std::move(value)}; + } + +private: + Entries mEntries; + std::size_t mNumEntries = 0; +}; + +#endif diff --git a/src/widgets/room/autotests/CMakeLists.txt b/src/widgets/room/autotests/CMakeLists.txt --- a/src/widgets/room/autotests/CMakeLists.txt +++ b/src/widgets/room/autotests/CMakeLists.txt @@ -17,5 +17,4 @@ add_ruqolaroom_test(readonlylineeditwidgettest.cpp) add_ruqolaroom_test(usersinroomflowwidgettest.cpp) add_ruqolaroom_test(usersinroomlabeltest.cpp) -add_ruqolaroom_test(pixmapcachetest.cpp) add_ruqolaroom_test(channelactionpopupmenutest.cpp) diff --git a/src/widgets/room/autotests/pixmapcachetest.cpp b/src/widgets/room/autotests/pixmapcachetest.cpp deleted file mode 100644 --- a/src/widgets/room/autotests/pixmapcachetest.cpp +++ /dev/null @@ -1,48 +0,0 @@ -/* - Copyright (c) 2020 David Faure - - This library is free software; you can redistribute it and/or modify - it under the terms of the GNU Library General Public License as published - by the Free Software Foundation; either version 2 of the License or - ( at your option ) version 3 or, at the discretion of KDE e.V. - ( which shall act as a proxy as in section 14 of the GPLv3 ), any later version. - - This library is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - Library General Public License for more details. - - You should have received a copy of the GNU Library General Public License - along with this library; see the file COPYING.LIB. If not, write to - the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, - Boston, MA 02110-1301, USA. -*/ - -#include "pixmapcachetest.h" -#include "room/delegate/pixmapcache.h" - -#include -#include -#include - -QTEST_MAIN(PixmapCacheTest) - -PixmapCacheTest::PixmapCacheTest(QObject *parent) - : QObject(parent) -{ - QStandardPaths::setTestModeEnabled(true); -} - -void PixmapCacheTest::shouldCacheLastFivePixmaps() -{ - PixmapCache cache; - for (int i = 1; i < 7; ++i) { - const QString link = QStringLiteral("link") + QString::number(i); - const QPixmap pix(i * 10, i * 10); - cache.insertCachedPixmap(link, pix); - QCOMPARE(cache.findCachedPixmap(link).height(), i * 10); - QCOMPARE(cache.findCachedPixmap(QStringLiteral("link1")).height(), 10); // we keep using that one - } - QCOMPARE(cache.findCachedPixmap(QStringLiteral("link4")).height(), 40); - QVERIFY(cache.findCachedPixmap(QStringLiteral("link2")).isNull()); // oldest one got evicted -} diff --git a/src/widgets/room/delegate/pixmapcache.h b/src/widgets/room/delegate/pixmapcache.h --- a/src/widgets/room/delegate/pixmapcache.h +++ b/src/widgets/room/delegate/pixmapcache.h @@ -23,6 +23,7 @@ #include "libruqolawidgets_private_export.h" +#include #include #include @@ -34,14 +35,9 @@ private: friend class PixmapCacheTest; + LRUCache mCachedImages; QPixmap findCachedPixmap(const QString &link); void insertCachedPixmap(const QString &link, const QPixmap &pixmap); - - struct CachedImage { - QString link; - QPixmap pixmap; - }; - QVector mCachedImages; // most recent first }; #endif // PIXMAPCACHE_H diff --git a/src/widgets/room/delegate/pixmapcache.cpp b/src/widgets/room/delegate/pixmapcache.cpp --- a/src/widgets/room/delegate/pixmapcache.cpp +++ b/src/widgets/room/delegate/pixmapcache.cpp @@ -23,40 +23,15 @@ QPixmap PixmapCache::pixmapForLocalFile(const QString &path) { - QPixmap pixmap = findCachedPixmap(path); + auto it = mCachedImages.find(path); + if (it != mCachedImages.end()) { + return it->value; + } + auto pixmap = QPixmap(path); if (pixmap.isNull()) { - if (pixmap.load(path)) { - insertCachedPixmap(path, pixmap); - } else { - qCWarning(RUQOLAWIDGETS_LOG) << "Could not load" << path; - } + qCWarning(RUQOLAWIDGETS_LOG) << "Could not load" << path; + return pixmap; } + mCachedImages.insert(path, pixmap); return pixmap; } - -QPixmap PixmapCache::findCachedPixmap(const QString &link) -{ - auto matchesLink = [&](const CachedImage &cached) { - return cached.link == link; - }; - auto it = std::find_if(mCachedImages.begin(), mCachedImages.end(), matchesLink); - if (it == mCachedImages.end()) { - return QPixmap(); - } - QPixmap result = it->pixmap; // grab pixmap before 'it' gets invalidated - // Move it to the front - if (it != mCachedImages.begin()) { - const auto idx = std::distance(mCachedImages.begin(), it); - mCachedImages.move(idx, 0); - } - return result; -} - -void PixmapCache::insertCachedPixmap(const QString &link, const QPixmap &pixmap) -{ - mCachedImages.prepend(CachedImage{link, pixmap}); - static const int s_maxCacheSize = 5; - if (mCachedImages.size() > s_maxCacheSize) { - mCachedImages.resize(s_maxCacheSize); - } -}