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/LRUCache.h | |
| 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/LRUCache.h')
| -rw-r--r-- | Swiften/Base/LRUCache.h | 79 |
1 files changed, 79 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; +}; + +} |