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
@@ -39,30 +39,40 @@ std::ostream& operator<<(std::ostream& stream, const Presence& presence) {
             break;
     }
 
     std::string showTypeString;
     switch (presence.getShow()) {
         case StatusShow::Online:
             showTypeString = "Online";
             break;
         case StatusShow::Away:
             showTypeString = "Away";
             break;
         case StatusShow::FFC:
             showTypeString = "FFC";
             break;
         case StatusShow::DND:
             showTypeString = "DND";
             break;
         case StatusShow::XA:
             showTypeString = "XA";
             break;
         case StatusShow::None:
             showTypeString = "None";
             break;
     }
 
     stream << "Presence(" << "from: " << presence.getFrom() << ", to: " << presence.getTo() << ", type: " << typeString << ", status: " << showTypeString << ", priority: " << presence.getPriority() << ", '" << presence.getStatus() << "'" <<  " )";
     return stream;
 }
 
 };
+
+::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
@@ -1,47 +1,52 @@
 /*
  * Copyright (c) 2016 Isode Limited.
  * All rights reserved.
  * See the COPYING file for more information.
  */
 
 #pragma once
 
 #include <memory>
 #include <ostream>
 #include <string>
 #include <vector>
 
+#include <boost/optional.hpp>
+
 namespace Swift {
 
 class Presence;
 
 template <typename T>
 std::ostream& operator<<(std::ostream& stream, const std::shared_ptr<T>& ptr) {
     if (ptr) {
         stream << *ptr;
     }
     else {
         stream << "nullptr";
     }
     return stream;
 }
 
 template <typename T>
 std::ostream& operator<<(std::ostream& stream, const std::vector<T>& vec) {
     stream << "[";
     if (!vec.empty()) {
         auto it = std::begin(vec);
         stream << *it;
 
         ++it;
         for (auto end = std::end(vec); it != end; ++it) {
             stream << ", " << *it;
         }
      }
     stream << "]";
     return stream;
 }
 
 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
@@ -341,60 +341,61 @@ if env["SCONS_STAGE"] == "build" :
             myenv.Append(LINKFLAGS = ["-Wl,-install_name,${SHLIBPREFIX}Swiften.${SWIFTEN_VERSION_MAJOR}${SHLIBSUFFIX}", "-Wl,-compatibility_version,${SWIFTEN_VERSION_MAJOR}.${SWIFTEN_VERSION_MINOR}", "-Wl,-current_version,${SWIFTEN_VERSION_MAJOR}.${SWIFTEN_VERSION_MINOR}"])
         elif myenv["PLATFORM"] == "win32" :
             res_env = myenv.Clone()
             res_env.Append(CPPDEFINES = [
                     ("SWIFTEN_LIBRARY_FILE", "\"\\\"${SWIFTEN_LIBRARY_FILE}\\\"\""),
                     ("SWIFTEN_COPYRIGHT_YEAR", "\"\\\"2010-%s\\\"\"" % str(time.localtime()[0])),
                     ("SWIFTEN_VERSION_MAJOR", "${SWIFTEN_VERSION_MAJOR}"),
                     ("SWIFTEN_VERSION_MINOR", "${SWIFTEN_VERSION_MINOR}"),
                     ("SWIFTEN_VERSION_PATCH", "${SWIFTEN_VERSION_PATCH}"),
                 ])
             res = res_env.RES("Swiften.rc")
             # For some reason, SCons isn't picking up the dependency correctly
             # Adding it explicitly until i figure out why
             res_env.Depends(res, "Version.h")
             sources += res
 
     swiften_lib = myenv.SwiftenLibrary(swiften_env["SWIFTEN_LIBRARY_FILE"], sources + swiften_env["SWIFTEN_OBJECTS"])
     def symlink(env, target, source) :
         if os.path.exists(str(target[0])) :
             os.unlink(str(target[0]))
         os.symlink(source[0].get_contents(), str(target[0]))
     for alias in myenv["SWIFTEN_LIBRARY_ALIASES"] :
         myenv.Command(myenv.File(alias), [myenv.Value(swiften_lib[0].name), swiften_lib[0]], symlink)
 
     env.Append(UNITTEST_SOURCES = [
             File("Avatars/UnitTest/VCardUpdateAvatarManagerTest.cpp"),
             File("Avatars/UnitTest/VCardAvatarManagerTest.cpp"),
             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"),
             File("Base/UnitTest/ByteArrayTest.cpp"),
             File("Base/UnitTest/URLTest.cpp"),
             File("Base/UnitTest/PathTest.cpp"),
             File("Chat/UnitTest/ChatStateNotifierTest.cpp"),
 #       File("Chat/UnitTest/ChatStateTrackerTest.cpp"),
             File("Client/UnitTest/ClientSessionTest.cpp"),
             File("Client/UnitTest/NickResolverTest.cpp"),
             File("Client/UnitTest/ClientBlockListManagerTest.cpp"),
             File("Client/UnitTest/BlockListImplTest.cpp"),
             File("Compress/UnitTest/ZLibCompressorTest.cpp"),
             File("Compress/UnitTest/ZLibDecompressorTest.cpp"),
             File("Component/UnitTest/ComponentHandshakeGeneratorTest.cpp"),
             File("Component/UnitTest/ComponentConnectorTest.cpp"),
             File("Component/UnitTest/ComponentSessionTest.cpp"),
             File("Disco/UnitTest/CapsInfoGeneratorTest.cpp"),
             File("Disco/UnitTest/CapsManagerTest.cpp"),
             File("Disco/UnitTest/DiscoInfoResponderTest.cpp"),
             File("Disco/UnitTest/EntityCapsManagerTest.cpp"),
             File("Disco/UnitTest/FeatureOracleTest.cpp"),
             File("Disco/UnitTest/JIDDiscoInfoResponderTest.cpp"),
             File("Elements/UnitTest/IQTest.cpp"),
             File("Elements/UnitTest/StanzaTest.cpp"),
             File("Elements/UnitTest/FormTest.cpp"),
             File("EventLoop/UnitTest/EventLoopTest.cpp"),
             File("EventLoop/UnitTest/SimpleEventLoopTest.cpp"),
 #           File("History/UnitTest/SQLiteHistoryManagerTest.cpp"),
             File("JID/UnitTest/JIDTest.cpp"),