From Andrew Lindesay <apl@xxxxxxxxxxxxxx>:
Andrew Lindesay has uploaded this change for review. (
https://review.haiku-os.org/c/haiku/+/3367 ;)
Change subject: HaikuDepot: LRU Cache for Icons
......................................................................
HaikuDepot: LRU Cache for Icons
Only keep a fixed number of icons in memory at once.
Completes To #15370
---
M src/apps/haikudepot/model/PackageIconTarRepository.cpp
M src/apps/haikudepot/model/PackageIconTarRepository.h
A src/apps/haikudepot/util/LruHashMap.h
M src/tests/apps/haikudepot/HaikuDepotTestAddon.cpp
M src/tests/apps/haikudepot/Jamfile
A src/tests/apps/haikudepot/LruHashMapTest.cpp
A src/tests/apps/haikudepot/LruHashMapTest.h
7 files changed, 384 insertions(+), 3 deletions(-)
git pull ssh://git.haiku-os.org:22/haiku refs/changes/67/3367/1
diff --git a/src/apps/haikudepot/model/PackageIconTarRepository.cpp
b/src/apps/haikudepot/model/PackageIconTarRepository.cpp
index 3f872c8..fa69d6d 100644
--- a/src/apps/haikudepot/model/PackageIconTarRepository.cpp
+++ b/src/apps/haikudepot/model/PackageIconTarRepository.cpp
@@ -2,6 +2,8 @@
* Copyright 2020, Andrew Lindesay <apl@xxxxxxxxxxxxxx>.
* All rights reserved. Distributed under the terms of the MIT License.
*/
+
+
#include "PackageIconTarRepository.h"
#include <Autolock.h>
@@ -13,6 +15,9 @@
#include "TarArchiveService.h"
+#define LIMIT_ICON_CACHE 50
+
+
BitmapRef
PackageIconTarRepository::sDefaultIcon(new(std::nothrow) SharedBitmap(
"application/x-vnd.haiku-package"), true);
@@ -123,7 +128,8 @@
PackageIconTarRepository::PackageIconTarRepository()
:
- fTarIo(NULL)
+ fTarIo(NULL),
+ fIconCache(LIMIT_ICON_CACHE)
{
}
diff --git a/src/apps/haikudepot/model/PackageIconTarRepository.h
b/src/apps/haikudepot/model/PackageIconTarRepository.h
index 1ae509e..4a53abb 100644
--- a/src/apps/haikudepot/model/PackageIconTarRepository.h
+++ b/src/apps/haikudepot/model/PackageIconTarRepository.h
@@ -5,6 +5,7 @@
#ifndef PACKAGE_ICON_TAR_REPOSITORY_H
#define PACKAGE_ICON_TAR_REPOSITORY_H
+
#include <DataIO.h>
#include <HashMap.h>
#include <HashString.h>
@@ -12,8 +13,9 @@
#include <Path.h>
#include <Referenceable.h>
-#include "PackageIconRepository.h"
#include "IconTarPtr.h"
+#include "LruHashMap.h"
+#include "PackageIconRepository.h"
typedef BReference<IconTarPtr> IconTarPtrRef;
@@ -54,7 +56,7 @@
private:
BLocker fLock;
BPositionIO* fTarIo;
- HashMap<HashString, BitmapRef>
+ LruHashMap<HashString, BitmapRef>
fIconCache;
HashMap<HashString, IconTarPtrRef>
fIconTarPtrs;
diff --git a/src/apps/haikudepot/util/LruHashMap.h
b/src/apps/haikudepot/util/LruHashMap.h
new file mode 100644
index 0000000..5e05b51
--- /dev/null
+++ b/src/apps/haikudepot/util/LruHashMap.h
@@ -0,0 +1,210 @@
+/*
+ * Copyright 2020, Andrew Lindesay <apl@xxxxxxxxxxxxxx>.
+ * All rights reserved. Distributed under the terms of the MIT License.
+ */
+#ifndef LRU_HASH_MAP_H
+#define LRU_HASH_MAP_H
+
+
+#include <HashMap.h>
+
+#include "Logger.h"
+
+
+namespace BPrivate {
+
+
+template<typename Key, typename Value>
+class LruOrderingNode {
+private:
+ typedef LruOrderingNode<Key, Value> LruNode;
+
+public:
+ LruOrderingNode()
+ :
+ fKey(),
+ fValue(),
+ fOlder(NULL),
+ fNewer(NULL)
+ {
+ }
+
+ LruOrderingNode(const Key& key, const Value& value)
+ :
+ fKey(key),
+ fValue(value),
+ fOlder(NULL),
+ fNewer(NULL)
+ {
+ }
+
+ Key fKey;
+ Value fValue;
+ LruNode* fOlder;
+ LruNode* fNewer;
+};
+
+
+/*! \brief This is a hash map that maintains a limited number of entries.
Once
+ this number of entries has been exceeded then it will start to discard
+ entries. The first entries to be discarded are the ones that are the
least
+ recently used; hence the prefix "LRU".
+*/
+
+template<typename Key, typename Value>
+class LruHashMap {
+public:
+ typedef LruOrderingNode<Key, Value> LruNode;
+
+ LruHashMap(int32 limit)
+ :
+ fNewestNode(NULL),
+ fOldestNode(NULL),
+ fLimit(limit)
+ {
+ if (fLimit < 0)
+ fLimit = 0;
+ }
+
+ ~LruHashMap()
+ {
+ Clear();
+ }
+
+ status_t InitCheck() const
+ {
+ return fMap.InitCheck();
+ }
+
+ status_t Put(const Key& key, const Value& value)
+ {
+ LruNode* node = fMap.Get(key);
+
+ if (node != NULL) {
+ if (node->fValue != value) {
+ node->fValue = value;
+ _DisconnectNodeAndMakeNewest(node);
+ }
+ } else {
+ node = new(std::nothrow) LruNode(key, value);
+ if (node == NULL)
+ HDFATAL("memory exhausted adding to an lru hash
map");
+ status_t result = fMap.Put(key, node);
+ if (result != B_OK)
+ HDFATAL("failed adding to an lru hash map");
+ _SetNewestNode(node);
+ _PurgeExcess();
+ }
+
+ return B_OK;
+ }
+
+ Value Remove(const Key& key)
+ {
+ LruNode* node = fMap.Get(key);
+ if (node != NULL) {
+ _DisconnectNode(node);
+ Value result = node->fValue;
+ fMap.Remove(key);
+ delete node;
+ return result;
+ }
+ return Value();
+ }
+
+ void Clear()
+ {
+ fMap.Clear();
+ LruNode* node = fNewestNode;
+ while (node != NULL) {
+ LruNode *next = node->fOlder;
+ delete node;
+ node = next;
+ }
+ }
+
+ Value Get(const Key& key)
+ {
+ LruNode* node = fMap.Get(key);
+ if (node != NULL) {
+ _DisconnectNodeAndMakeNewest(node);
+ return node->fValue;
+ }
+ return Value();
+ }
+
+ bool ContainsKey(const Key& key) const
+ {
+ return fMap.ContainsKey(key);
+ }
+
+ int32 Size() const
+ {
+ return fMap.Size();
+ }
+
+private:
+
+ void _DisconnectNodeAndMakeNewest(LruNode* node) {
+ if (node != fNewestNode) {
+ _DisconnectNode(node);
+ node->fOlder = NULL;
+ node->fNewer = NULL;
+ _SetNewestNode(node);
+ }
+ }
+
+ void _DisconnectNode(LruNode* node)
+ {
+ LruNode *older = node->fOlder;
+ LruNode *newer = node->fNewer;
+ if (newer != NULL)
+ newer->fOlder = older;
+ if (older != NULL)
+ older->fNewer = newer;
+ if (fNewestNode == node)
+ fNewestNode = older;
+ if (fOldestNode == node)
+ fOldestNode = newer;
+ }
+
+ void _SetNewestNode(LruNode* node)
+ {
+ if (node != fNewestNode) {
+ node->fOlder = fNewestNode;
+ node->fNewer = NULL;
+ if (fNewestNode != NULL)
+ fNewestNode->fNewer = node;
+ fNewestNode = node;
+ if (fOldestNode == NULL)
+ fOldestNode = node;
+ }
+ }
+
+ void _PurgeOldestNode()
+ {
+ if (NULL == fOldestNode)
+ HDFATAL("attempt to purge oldest node when there is
none to purge");
+ Remove(fOldestNode->fKey);
+ }
+
+ void _PurgeExcess()
+ {
+ while(Size() > fLimit)
+ _PurgeOldestNode();
+ }
+
+protected:
+ HashMap<Key, LruNode*> fMap;
+ LruNode* fNewestNode;
+ LruNode* fOldestNode;
+
+private:
+ int32 fLimit;
+};
+
+}; // namespace BPrivate
+
+using BPrivate::LruHashMap;
+
+#endif // LRU_HASH_MAP_H
diff --git a/src/tests/apps/haikudepot/HaikuDepotTestAddon.cpp
b/src/tests/apps/haikudepot/HaikuDepotTestAddon.cpp
index 8ed7271..32bfcbb 100644
--- a/src/tests/apps/haikudepot/HaikuDepotTestAddon.cpp
+++ b/src/tests/apps/haikudepot/HaikuDepotTestAddon.cpp
@@ -3,6 +3,7 @@
* Distributed under the terms of the MIT License.
*/
+
#include <TestSuite.h>
#include <TestSuiteAddon.h>
@@ -13,6 +14,8 @@
#include "StorageUtilsTest.h"
#include "TarArchiveServiceTest.h"
#include "ListTest.h"
+#include "LruHashMapTest.h"
+
BTestSuite*
getTestSuite()
@@ -24,6 +27,7 @@
ValidationFailureTest::AddTests(*suite);
ValidationUtilsTest::AddTests(*suite);
ListTest::AddTests(*suite);
+ LruHashMapTest::AddTests(*suite);
StorageUtilsTest::AddTests(*suite);
TarArchiveServiceTest::AddTests(*suite);
diff --git a/src/tests/apps/haikudepot/Jamfile
b/src/tests/apps/haikudepot/Jamfile
index 4f695f1..7efa91f 100644
--- a/src/tests/apps/haikudepot/Jamfile
+++ b/src/tests/apps/haikudepot/Jamfile
@@ -44,6 +44,8 @@
Logger.cpp
+ LruHashMapTest.cpp
+
StandardMetaData.cpp
StandardMetaDataJsonEventListener.cpp
StandardMetaDataJsonEventListenerTest.cpp
diff --git a/src/tests/apps/haikudepot/LruHashMapTest.cpp
b/src/tests/apps/haikudepot/LruHashMapTest.cpp
new file mode 100644
index 0000000..6df8b17
--- /dev/null
+++ b/src/tests/apps/haikudepot/LruHashMapTest.cpp
@@ -0,0 +1,131 @@
+/*
+ * Copyright 2020, Andrew Lindesay <apl@xxxxxxxxxxxxxx>.
+ * All rights reserved. Distributed under the terms of the MIT License.
+ */
+
+
+#include "LruHashMapTest.h"
+
+#include <stdio.h>
+
+#include <HashString.h>
+
+#include <cppunit/TestCaller.h>
+#include <cppunit/TestSuite.h>
+
+#include "LruHashMap.h"
+
+
+LruHashMapTest::LruHashMapTest()
+{
+}
+
+
+LruHashMapTest::~LruHashMapTest()
+{
+}
+
+
+/*! This tests the insertion of various letters into the map and the subsequent
+ search for those values later using a binary search.
+*/
+
+void
+LruHashMapTest::TestAddWithOverflow()
+{
+ LruHashMap<HashString, BString> map(5);
+
+ BString tmpKey;
+ BString tmpValue;
+
+// ----------------------
+ for(char c = 'a'; c <= 'z'; c++) {
+ tmpKey.SetToFormat("%c", c);
+ tmpValue.SetToFormat("%c%c", c, c);
+ map.Put(HashString(tmpKey), tmpValue);
+ }
+// ----------------------
+
+ CPPUNIT_ASSERT_EQUAL(5, map.Size());
+ // oldest entries have been removed.
+ CPPUNIT_ASSERT_EQUAL(BString(""), map.Get(HashString("a")));
+ CPPUNIT_ASSERT_EQUAL(BString(""), map.Get(HashString("u")));
+ // latter entries have been removed.
+ CPPUNIT_ASSERT_EQUAL(BString("zz"), map.Get(HashString("z")));
+ CPPUNIT_ASSERT_EQUAL(BString("yy"), map.Get(HashString("y")));
+ CPPUNIT_ASSERT_EQUAL(BString("xx"), map.Get(HashString("x")));
+ CPPUNIT_ASSERT_EQUAL(BString("ww"), map.Get(HashString("w")));
+ CPPUNIT_ASSERT_EQUAL(BString("vv"), map.Get(HashString("v")));
+}
+
+
+/*! This tests the insertion of various letters into the list, but during the
+ inserts, there are some get operations which will effect which are
+ considered to be the oldest entries.
+*/
+
+void
+LruHashMapTest::TestAddWithOverflowWithGets()
+{
+ LruHashMap<HashString, BString> map(3);
+
+// ----------------------
+ map.Put(HashString("Red"), "Rot");
+ map.Put(HashString("Yellow"), "Gelb");
+ map.Get(HashString("Red"));
+ map.Put(HashString("Green"), "Gruen");
+ map.Put(HashString("Purple"), "Lila");
+// ----------------------
+
+ CPPUNIT_ASSERT_EQUAL(3, map.Size());
+ CPPUNIT_ASSERT_EQUAL(BString(""), map.Get(HashString("Yellow")));
+ CPPUNIT_ASSERT_EQUAL(BString("Rot"), map.Get(HashString("Red")));
+ CPPUNIT_ASSERT_EQUAL(BString("Gruen"), map.Get(HashString("Green")));
+ CPPUNIT_ASSERT_EQUAL(BString("Lila"), map.Get(HashString("Purple")));
+}
+
+
+void
+LruHashMapTest::TestRemove()
+{
+ LruHashMap<HashString, BString> map(3);
+
+ // control value
+ map.Put(HashString("Town"), "Tirau");
+ map.Put(HashString("Lake"), "Taupo");
+
+// ----------------------
+ BString resultOcean = map.Remove(HashString("Ocean"));
+ BString resultLake = map.Remove(HashString("Lake"));
+// ----------------------
+
+ CPPUNIT_ASSERT_EQUAL(1, map.Size());
+ CPPUNIT_ASSERT_EQUAL(BString(""), resultOcean);
+ CPPUNIT_ASSERT_EQUAL(BString("Taupo"), resultLake);
+ CPPUNIT_ASSERT_EQUAL(BString("Tirau"), map.Get(HashString("Town")));
+ CPPUNIT_ASSERT_EQUAL(BString(""), map.Get(HashString("Lake")));
+ CPPUNIT_ASSERT_EQUAL(BString(""), map.Get(HashString("Ocean")));
+}
+
+
+/*static*/ void
+LruHashMapTest::AddTests(BTestSuite& parent)
+{
+ CppUnit::TestSuite& suite = *new CppUnit::TestSuite(
+ "LruHashMapTest");
+
+ suite.addTest(
+ new CppUnit::TestCaller<LruHashMapTest>(
+ "LruHashMapTest::TestAddWithOverflow",
+ &LruHashMapTest::TestAddWithOverflow));
+ suite.addTest(
+ new CppUnit::TestCaller<LruHashMapTest>(
+ "LruHashMapTest::TestAddWithOverflowWithGets",
+ &LruHashMapTest::TestAddWithOverflowWithGets));
+ suite.addTest(
+ new CppUnit::TestCaller<LruHashMapTest>(
+ "LruHashMapTest::TestRemove",
+ &LruHashMapTest::TestRemove));
+
+ parent.addTest("LruHashMapTest", &suite);
+}
diff --git a/src/tests/apps/haikudepot/LruHashMapTest.h
b/src/tests/apps/haikudepot/LruHashMapTest.h
new file mode 100644
index 0000000..087b8fd
--- /dev/null
+++ b/src/tests/apps/haikudepot/LruHashMapTest.h
@@ -0,0 +1,26 @@
+/*
+ * Copyright 2020, Andrew Lindesay <apl@xxxxxxxxxxxxxx>
+ * Distributed under the terms of the MIT License.
+ */
+#ifndef LRU_HASH_MAP_TEST_H
+#define LRU_HASH_MAP_TEST_H
+
+
+#include <TestCase.h>
+#include <TestSuite.h>
+
+
+class LruHashMapTest : public CppUnit::TestCase {
+public:
+
LruHashMapTest();
+ virtual ~LruHashMapTest();
+
+ void TestAddWithOverflow();
+ void
TestAddWithOverflowWithGets();
+ void TestRemove();
+
+ static void AddTests(BTestSuite& suite);
+};
+
+
+#endif // LRU_HASH_MAP_TEST_H
--
To view, visit https://review.haiku-os.org/c/haiku/+/3367
To unsubscribe, or for help writing mail filters, visit
https://review.haiku-os.org/settings
Gerrit-Project: haiku
Gerrit-Branch: master
Gerrit-Change-Id: I23e3a4fa7559894034f45afb3b536910ea037078
Gerrit-Change-Number: 3367
Gerrit-PatchSet: 1
Gerrit-Owner: Andrew Lindesay <apl@xxxxxxxxxxxxxx>
Gerrit-MessageType: newchange
