From e5ecd73e063311e4a6145baaa3e358628b1caed4 Mon Sep 17 00:00:00 2001
From: Dan Goodliffe <dan@randomdan.homeip.net>
Date: Mon, 31 Aug 2015 01:04:43 +0100
Subject: Migrate cache from libmisc and add covering tests, some minor
 renaming and refactoring

---
 libadhocutil/cache.h                 |  83 +++++++++++++++++++++++
 libadhocutil/cache.impl.h            | 127 +++++++++++++++++++++++++++++++++++
 libadhocutil/unittests/Jamfile.jam   |  12 ++++
 libadhocutil/unittests/testCache.cpp |  79 ++++++++++++++++++++++
 4 files changed, 301 insertions(+)
 create mode 100644 libadhocutil/cache.h
 create mode 100644 libadhocutil/cache.impl.h
 create mode 100644 libadhocutil/unittests/testCache.cpp

diff --git a/libadhocutil/cache.h b/libadhocutil/cache.h
new file mode 100644
index 0000000..8cd7903
--- /dev/null
+++ b/libadhocutil/cache.h
@@ -0,0 +1,83 @@
+#ifndef NETFS_FUSE_CACHE_H
+#define NETFS_FUSE_CACHE_H
+
+#include <time.h>
+#include <boost/shared_ptr.hpp>
+#include <boost/function.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/thread/shared_mutex.hpp>
+#include <boost/variant.hpp>
+
+template <typename T, typename K>
+class Cacheable {
+	public:
+		Cacheable(const K & k, time_t validUntil);
+
+		const K key;
+		const time_t validUntil;
+
+		virtual const T & item() const = 0;
+};
+
+template <typename T, typename K>
+class ObjectCacheable : public Cacheable<T, K> {
+	public:
+		ObjectCacheable(const T & t, const K & k, time_t validUtil);
+
+		virtual const T & item() const override;
+
+	private:
+		const T value;
+};
+
+template <typename T, typename K>
+class CallCacheable : public Cacheable<T, K> {
+	public:
+		CallCacheable(const T & t, const K & k, time_t validUtil);
+		CallCacheable(const boost::function<T()> & t, const K & k, time_t validUtil);
+
+		virtual const T & item() const override;
+
+	private:
+		mutable boost::variant<T, boost::function<T()>> value;
+		mutable boost::shared_mutex lock;
+};
+
+struct byValidity {};
+struct byKey {};
+template <typename T, typename K>
+class Cache {
+	public:
+		typedef K Key;
+		typedef T Value;
+		typedef Cacheable<T, K> Item;
+		typedef boost::shared_ptr<Item> Element;
+
+		Cache();
+
+		void add(const K & k, const T & t, time_t validUntil);
+		void add(const K & k, const boost::function<T()> & tf, time_t validUntil);
+		Element getItem(const K & k) const;
+		const T * get(const K & k) const;
+		size_t size() const;
+
+	private:
+		void prune() const;
+		mutable time_t lastPruneTime;
+
+		mutable boost::shared_mutex lock;
+
+		typedef boost::multi_index::multi_index_container<Element,
+						boost::multi_index::indexed_by<
+						boost::multi_index::ordered_unique<
+							boost::multi_index::tag<byKey>, BOOST_MULTI_INDEX_MEMBER(Item, const K, key)>,
+						boost::multi_index::ordered_non_unique<
+							boost::multi_index::tag<byValidity>,  BOOST_MULTI_INDEX_MEMBER(Item, const time_t, validUntil)>
+							> > Cached;
+		mutable Cached cached;
+};
+
+#endif
+
diff --git a/libadhocutil/cache.impl.h b/libadhocutil/cache.impl.h
new file mode 100644
index 0000000..43fcd1a
--- /dev/null
+++ b/libadhocutil/cache.impl.h
@@ -0,0 +1,127 @@
+#include "cache.h"
+#include <boost/lambda/lambda.hpp>
+#include "lockHelpers.h"
+
+template<typename T, typename K>
+Cacheable<T, K>::Cacheable(const K & k, time_t vu) :
+	key(k),
+	validUntil(vu)
+{
+}
+
+template<typename T, typename K>
+ObjectCacheable<T, K>::ObjectCacheable(const T & t, const K & k, time_t vu) :
+	Cacheable<T, K>(k, vu),
+	value(t)
+{
+}
+
+template<typename T, typename K>
+const T &
+ObjectCacheable<T, K>::item() const
+{
+	return value;
+}
+
+template<typename T, typename K>
+CallCacheable<T, K>::CallCacheable(const T & t, const K & k, time_t vu) :
+	Cacheable<T, K>(k, vu),
+	value(t)
+{
+}
+
+template<typename T, typename K>
+CallCacheable<T, K>::CallCacheable(const boost::function<T()> & t, const K & k, time_t vu) :
+	Cacheable<T, K>(k, vu),
+	value(t)
+{
+}
+
+template<typename T, typename K>
+const T &
+CallCacheable<T, K>::item() const
+{
+	Lock(lock);
+	const T * t = boost::get<T>(&value);
+	if (t) {
+		return *t;
+	}
+	const boost::function<T()> & f = boost::get<boost::function<T()>>(value);
+	value = f();
+	return boost::get<T>(value);
+}
+
+
+template<typename T, typename K>
+Cache<T, K>::Cache() :
+	lastPruneTime(time(NULL))
+{
+}
+
+template<typename T, typename K>
+void
+Cache<T, K>::add(const K & k, const T & t, time_t validUntil)
+{
+	Lock(lock);
+	cached.insert(Element(new ObjectCacheable<T, K>(t, k, validUntil)));
+}
+
+template<typename T, typename K>
+void
+Cache<T, K>::add(const K & k, const boost::function<T()> & tf, time_t validUntil)
+{
+	Lock(lock);
+	cached.insert(Element(new CallCacheable<T, K>(tf, k, validUntil)));
+}
+
+template<typename T, typename K>
+typename Cache<T, K>::Element
+Cache<T, K>::getItem(const K & k) const
+{
+	{
+		SharedLock(lock);
+		auto & collection = cached.template get<byKey>();
+		auto i = collection.find(k);
+		if (i == collection.end()) {
+			return Element();
+		}
+		if ((*i)->validUntil > time(NULL)) {
+			return (*i);
+		}
+	}
+	prune();
+	return Element();
+}
+
+template<typename T, typename K>
+const T *
+Cache<T, K>::get(const K & k) const
+{
+	auto i = getItem(k);
+	if (i) {
+		return &i->item();
+	}
+	return nullptr;
+}
+
+template<typename T, typename K>
+size_t
+Cache<T, K>::size() const
+{
+	return cached.size();
+}
+
+template<typename T, typename K>
+void
+Cache<T, K>::prune() const
+{
+	auto now = time(NULL);
+	if (lastPruneTime < now) {
+		Lock(lock);
+		auto & collection = cached.template get<byValidity>();
+		auto range = collection.range(boost::multi_index::unbounded, boost::lambda::_1 < now);
+		collection.erase(range.first, range.second);
+		lastPruneTime = now;
+	}
+}
+
diff --git a/libadhocutil/unittests/Jamfile.jam b/libadhocutil/unittests/Jamfile.jam
index 7b2720e..8275cbb 100644
--- a/libadhocutil/unittests/Jamfile.jam
+++ b/libadhocutil/unittests/Jamfile.jam
@@ -107,3 +107,15 @@ run
 	testNvpParse
 	;
 
+run
+	testCache.cpp
+	: : :
+	<define>BOOST_TEST_DYN_LINK
+	<library>..//adhocutil
+	<library>boost_utf
+	<library>boost_system
+	<library>boost_thread
+	:
+	testCache
+	;
+
diff --git a/libadhocutil/unittests/testCache.cpp b/libadhocutil/unittests/testCache.cpp
new file mode 100644
index 0000000..da6df69
--- /dev/null
+++ b/libadhocutil/unittests/testCache.cpp
@@ -0,0 +1,79 @@
+#define BOOST_TEST_MODULE Cache
+#include <boost/test/unit_test.hpp>
+
+#include <boost/bind.hpp>
+#include "cache.h"
+#include "cache.impl.h"
+
+typedef Cache<int, std::string> TestCache;
+template class Cache<int, std::string>;
+template class Cacheable<int, std::string>;
+template class ObjectCacheable<int, std::string>;
+template class CallCacheable<int, std::string>;
+
+namespace std {
+	std::ostream & operator<<(std::ostream & s, const std::nullptr_t &)
+	{
+		return s << "(nil)";	
+	}
+}
+
+BOOST_AUTO_TEST_CASE( miss )
+{
+	TestCache tc;
+	BOOST_REQUIRE_EQUAL(0, tc.size());
+	tc.add("key", 3, time(NULL) + 5);
+	BOOST_REQUIRE_EQUAL(1, tc.size());
+	BOOST_REQUIRE_EQUAL(nullptr, tc.get("anything"));
+	BOOST_REQUIRE_EQUAL(nullptr, tc.getItem("anything"));
+	BOOST_REQUIRE_EQUAL(1, tc.size());
+}
+
+BOOST_AUTO_TEST_CASE( hit )
+{
+	TestCache tc;
+	auto vu = time(NULL) + 5;
+	tc.add("key", 3, vu);
+	BOOST_REQUIRE_EQUAL(1, tc.size());
+	BOOST_REQUIRE_EQUAL(3, *tc.get("key"));
+	BOOST_REQUIRE_EQUAL(3, tc.getItem("key")->item());
+	BOOST_REQUIRE_EQUAL(vu, tc.getItem("key")->validUntil);
+	BOOST_REQUIRE_EQUAL("key", tc.getItem("key")->key);
+	BOOST_REQUIRE_EQUAL(1, tc.size());
+}
+
+BOOST_AUTO_TEST_CASE( expired )
+{
+	TestCache tc;
+	tc.add("miss", 3, time(NULL) - 5);
+	tc.add("hit", 3, time(NULL) + 5);
+	// We only prune once a second... so size() should stay at 1
+	BOOST_REQUIRE_EQUAL(2, tc.size());
+	BOOST_REQUIRE_EQUAL(nullptr, tc.get("miss"));
+	BOOST_REQUIRE_EQUAL(nullptr, tc.getItem("miss"));
+	BOOST_REQUIRE(tc.get("hit"));
+	BOOST_REQUIRE(tc.getItem("hit"));
+	BOOST_REQUIRE_EQUAL(2, tc.size());
+	sleep(1);
+	// Should prune now...
+	BOOST_REQUIRE_EQUAL(2, tc.size());
+	BOOST_REQUIRE(tc.get("hit"));
+	BOOST_REQUIRE_EQUAL(2, tc.size());
+	BOOST_REQUIRE_EQUAL(nullptr, tc.get("miss"));
+	BOOST_REQUIRE_EQUAL(1, tc.size());
+}
+
+BOOST_AUTO_TEST_CASE( callcache )
+{
+	TestCache tc;
+	int callCount = 0;
+	auto vu = time(NULL) + 5;
+	BOOST_REQUIRE_EQUAL(nullptr, tc.get("key"));
+	tc.add("key", [&callCount]{ callCount++; return 3; }, vu);
+	BOOST_REQUIRE_EQUAL(0, callCount);
+	BOOST_REQUIRE_EQUAL(3, *tc.get("key"));
+	BOOST_REQUIRE_EQUAL(1, callCount);
+	BOOST_REQUIRE_EQUAL(3, *tc.get("key"));
+	BOOST_REQUIRE_EQUAL(1, callCount);
+}
+
-- 
cgit v1.2.3