Swiftdiff options
| author | Tobias Markmann <tm@ayena.de> | 2017-02-17 17:15:41 (GMT) |
|---|---|---|
| committer | Tobias Markmann <tm@ayena.de> | 2017-02-22 10:54:22 (GMT) |
| commit | eea861301be0bf3e3f5db6cfc3cada38d133fef2 (patch) | |
| tree | 3c2aa07ce3724a73ce2124832bee6b8c7884c9df /Swiften/Base | |
| parent | 80801aaeba2d29e3a375a01d782cf081e778dfaf (diff) | |
| download | swift-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/Base')
| -rw-r--r-- | Swiften/Base/LRUCache.h | 79 | ||||
| -rw-r--r-- | Swiften/Base/LogSerializers.cpp | 10 | ||||
| -rw-r--r-- | Swiften/Base/LogSerializers.h | 5 | ||||
| -rw-r--r-- | Swiften/Base/UnitTest/LRUCacheTest.cpp | 117 |
4 files changed, 211 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")); +} |