Swift
summaryrefslogtreecommitdiffstats
path: root/Swiften
diff options
context:
space:
mode:
authorTobias Markmann <tm@ayena.de>2017-02-17 17:15:41 (GMT)
committerTobias Markmann <tm@ayena.de>2017-02-22 10:54:22 (GMT)
commiteea861301be0bf3e3f5db6cfc3cada38d133fef2 (patch)
tree3c2aa07ce3724a73ce2124832bee6b8c7884c9df /Swiften
parent80801aaeba2d29e3a375a01d782cf081e778dfaf (diff)
downloadswift-eea861301be0bf3e3f5db6cfc3cada38d133fef2.zip
swift-eea861301be0bf3e3f5db6cfc3cada38d133fef2.tar.bz2
Add LRUCache utility class to Swiften
This implements a simple lookup cache with least recently used replacement strategy. This also adds Boost.MultiIndex from version 1.56 to 3rdParty. Test-Information: Added some unit tests for LRUCache, which pass on macOS 10.12.3 with clang-5.0 Change-Id: I0567945b1197d3fe786bf9d82fdb5e755743b975
Diffstat (limited to 'Swiften')
-rw-r--r--Swiften/Base/LRUCache.h79
-rw-r--r--Swiften/Base/LogSerializers.cpp10
-rw-r--r--Swiften/Base/LogSerializers.h5
-rw-r--r--Swiften/Base/UnitTest/LRUCacheTest.cpp117
-rw-r--r--Swiften/SConscript1
5 files changed, 212 insertions, 0 deletions
diff --git a/Swiften/Base/LRUCache.h b/Swiften/Base/LRUCache.h
new file mode 100644
index 0000000..e4e652f
--- /dev/null
+++ b/Swiften/Base/LRUCache.h
@@ -0,0 +1,79 @@
+/*
+ * Copyright (c) 2017 Isode Limited.
+ * All rights reserved.
+ * See the COPYING file for more information.
+ */
+
+#pragma once
+
+#include <functional>
+#include <utility>
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+#include <boost/optional.hpp>
+
+namespace Swift {
+
+
+/**
+ * The \ref LRUCache templaged class implements a lookup cache which removes
+ * the least recently used cached item from the cache, if the cache size hits
+ * the \ref MAX_SIZE limit.
+ *
+ * An example use is a cache for entity capabilities hash to DiscoInfo.
+ */
+template <typename KEY_TYPE, typename VALUE_TYPE, size_t MAX_SIZE>
+class LRUCache {
+public:
+ using cacheMissFunction = std::function<boost::optional<VALUE_TYPE>(const KEY_TYPE& )>;
+
+public:
+ /**
+ * Inserts the key/value pair in the front of the cache. If the \ref key
+ * already exists in the cache, it is moved to the front instead. If
+ * afterwards, the cahe size exceeds the \ref MAX_SIZE limit, the least
+ * recently item is removed from the cache.
+ */
+ void insert(const KEY_TYPE& key, VALUE_TYPE value) {
+ auto pushResult = cache.push_front(entry_t(key, value));
+ if (!pushResult.second) {
+ cache.relocate(cache.begin(), pushResult.first);
+ }
+ else if (cache.size() > MAX_SIZE) {
+ cache.pop_back();
+ }
+ }
+
+ /**
+ * Looks up a cache entry based on the provided \ref key and moves it back
+ * to the front of the cache. If there is no cache entry for the provided
+ * \ref key, an uninitialized \ref boost::optional is returned.
+ * If the optional \ref missFunction is provided, it is called on a cache miss.
+ * If the \ref missFunction returns an initialized \ref boost::optional, the
+ * value is inserted in the cache.
+ */
+ boost::optional<VALUE_TYPE> get(const KEY_TYPE& key, cacheMissFunction missFunction = cacheMissFunction()) {
+ boost::optional<VALUE_TYPE> cachedValue;
+ auto cacheItemIterator = boost::multi_index::get<1>(cache).find(key);
+ if (cacheItemIterator != boost::multi_index::get<1>(cache).end()) {
+ cachedValue = cacheItemIterator->second;
+ cache.relocate(cache.begin(), cache.iterator_to(*cacheItemIterator));
+ }
+ else if (missFunction && (cachedValue = missFunction(key))) {
+ insert(key, cachedValue.get());
+ }
+ return cachedValue;
+ }
+
+private:
+ using entry_t = std::pair<KEY_TYPE, VALUE_TYPE>;
+
+private:
+ boost::multi_index_container< entry_t, boost::multi_index::indexed_by< boost::multi_index::sequenced<>, boost::multi_index::hashed_unique<
+ BOOST_MULTI_INDEX_MEMBER(entry_t, KEY_TYPE, first)> > > cache;
+};
+
+}
diff --git a/Swiften/Base/LogSerializers.cpp b/Swiften/Base/LogSerializers.cpp
index ccc8437..5ac1e15 100644
--- a/Swiften/Base/LogSerializers.cpp
+++ b/Swiften/Base/LogSerializers.cpp
@@ -66,3 +66,13 @@ std::ostream& operator<<(std::ostream& stream, const Presence& presence) {
}
};
+
+::std::ostream& operator<<(::std::ostream& os, const boost::optional<std::string>& optStr) {
+ if (optStr.is_initialized()) {
+ return os << "boost::optional<std::string>(\"" << optStr.get() << "\")";
+ }
+ else {
+ return os << "boost::optional<std::string>()";
+ }
+}
+
diff --git a/Swiften/Base/LogSerializers.h b/Swiften/Base/LogSerializers.h
index 3d60426..be992bb 100644
--- a/Swiften/Base/LogSerializers.h
+++ b/Swiften/Base/LogSerializers.h
@@ -11,6 +11,8 @@
#include <string>
#include <vector>
+#include <boost/optional.hpp>
+
namespace Swift {
class Presence;
@@ -45,3 +47,6 @@ std::ostream& operator<<(std::ostream& stream, const std::vector<T>& vec) {
std::ostream& operator<<(std::ostream& stream, const Presence& presence);
};
+
+::std::ostream& operator<<(::std::ostream& os, const boost::optional<std::string>& optStr);
+
diff --git a/Swiften/Base/UnitTest/LRUCacheTest.cpp b/Swiften/Base/UnitTest/LRUCacheTest.cpp
new file mode 100644
index 0000000..7d54c5c
--- /dev/null
+++ b/Swiften/Base/UnitTest/LRUCacheTest.cpp
@@ -0,0 +1,117 @@
+/*
+ * Copyright (c) 2017 Isode Limited.
+ * All rights reserved.
+ * See the COPYING file for more information.
+ */
+
+#include <string>
+
+#include <boost/optional.hpp>
+
+#include <Swiften/Base/LogSerializers.h>
+#include <Swiften/Base/LRUCache.h>
+
+#include <gtest/gtest.h> // This has to go after Swiften/Base/LogSerializers.h.
+
+using namespace Swift;
+namespace b = boost;
+
+TEST(LRUCacheTest, testCacheLimit) {
+ LRUCache<std::string, std::string, 3> testling;
+
+ testling.insert("A", "AA");
+ testling.insert("B", "BB");
+ testling.insert("C", "CC");
+
+ ASSERT_EQ(b::optional<std::string>("AA"), testling.get("A"));
+ ASSERT_EQ(b::optional<std::string>("BB"), testling.get("B"));
+ ASSERT_EQ(b::optional<std::string>("CC"), testling.get("C"));
+ ASSERT_EQ(b::optional<std::string>(), testling.get("D"));
+
+ testling.insert("D", "DD");
+
+ ASSERT_EQ(b::optional<std::string>(), testling.get("A"));
+ ASSERT_EQ(b::optional<std::string>("BB"), testling.get("B"));
+ ASSERT_EQ(b::optional<std::string>("CC"), testling.get("C"));
+ ASSERT_EQ(b::optional<std::string>("DD"), testling.get("D"));
+}
+
+TEST(LRUCacheTest, testMoveRecentToFrontOnGet) {
+ LRUCache<std::string, std::string, 3> testling;
+
+ testling.insert("A", "AA");
+ testling.insert("B", "BB");
+ testling.insert("C", "CC");
+
+ ASSERT_EQ(b::optional<std::string>("AA"), testling.get("A"));
+ ASSERT_EQ(b::optional<std::string>("BB"), testling.get("B"));
+ ASSERT_EQ(b::optional<std::string>("CC"), testling.get("C"));
+ ASSERT_EQ(b::optional<std::string>(), testling.get("D"));
+ ASSERT_EQ(b::optional<std::string>("AA"), testling.get("A"));
+
+ testling.insert("D", "DD");
+
+ ASSERT_EQ(b::optional<std::string>("AA"), testling.get("A"));
+ ASSERT_EQ(b::optional<std::string>(), testling.get("B"));
+ ASSERT_EQ(b::optional<std::string>("CC"), testling.get("C"));
+ ASSERT_EQ(b::optional<std::string>("DD"), testling.get("D"));
+}
+
+TEST(LRUCacheTest, testMoveRecentToFrontOnReinsert) {
+ LRUCache<std::string, std::string, 3> testling;
+
+ testling.insert("A", "AA");
+ testling.insert("B", "BB");
+ testling.insert("C", "CC");
+
+ ASSERT_EQ(b::optional<std::string>("AA"), testling.get("A"));
+ ASSERT_EQ(b::optional<std::string>("BB"), testling.get("B"));
+ ASSERT_EQ(b::optional<std::string>("CC"), testling.get("C"));
+ ASSERT_EQ(b::optional<std::string>(), testling.get("D"));
+
+ testling.insert("B", "BB");
+
+ ASSERT_EQ(b::optional<std::string>("AA"), testling.get("A"));
+ ASSERT_EQ(b::optional<std::string>("BB"), testling.get("B"));
+ ASSERT_EQ(b::optional<std::string>("CC"), testling.get("C"));
+ ASSERT_EQ(b::optional<std::string>(), testling.get("D"));
+
+ testling.insert("D", "DD");
+
+ ASSERT_EQ(b::optional<std::string>(), testling.get("A"));
+ ASSERT_EQ(b::optional<std::string>("BB"), testling.get("B"));
+ ASSERT_EQ(b::optional<std::string>("CC"), testling.get("C"));
+ ASSERT_EQ(b::optional<std::string>("DD"), testling.get("D"));
+}
+
+TEST(LRUCacheTest, testCacheReturnsValuesPreviouslyInserted) {
+ LRUCache<std::string, std::string, 3> testling;
+
+ testling.insert("A", "AA");
+ testling.insert("B", "BB");
+ testling.insert("C", "CC");
+
+ ASSERT_EQ(b::optional<std::string>("AA"), testling.get("A"));
+ ASSERT_EQ(b::optional<std::string>("BB"), testling.get("B"));
+ ASSERT_EQ(b::optional<std::string>("CC"), testling.get("C"));
+}
+
+TEST(LRUCacheTest, testCacheMissFunctionIsUsedOnCacheMiss) {
+ LRUCache<std::string, std::string, 3> testling;
+
+ testling.insert("A", "AA");
+ testling.insert("B", "BB");
+
+ ASSERT_EQ(b::optional<std::string>("AA"), testling.get("A"));
+ ASSERT_EQ(b::optional<std::string>("BB"), testling.get("B"));
+
+ ASSERT_EQ(b::optional<std::string>("CC"), testling.get("C", [](const std::string&) {
+ return boost::optional<std::string>(std::string("CC"));
+ }));
+ ASSERT_EQ(b::optional<std::string>("CC"), testling.get("C"));
+
+ ASSERT_EQ(b::optional<std::string>(), testling.get("D", [](const std::string&) {
+ return boost::optional<std::string>();
+ }));
+ ASSERT_EQ(b::optional<std::string>(), testling.get("D"));
+}
diff --git a/Swiften/SConscript b/Swiften/SConscript
index a8fb88a..1103362 100644
--- a/Swiften/SConscript
+++ b/Swiften/SConscript
@@ -368,6 +368,7 @@ if env["SCONS_STAGE"] == "build" :
File("Avatars/UnitTest/CombinedAvatarProviderTest.cpp"),
File("Avatars/UnitTest/AvatarManagerImplTest.cpp"),
File("Base/UnitTest/IDGeneratorTest.cpp"),
+ File("Base/UnitTest/LRUCacheTest.cpp"),
File("Base/UnitTest/SimpleIDGeneratorTest.cpp"),
File("Base/UnitTest/StringTest.cpp"),
File("Base/UnitTest/DateTimeTest.cpp"),