[Libreoffice-commits] core.git: Branch 'libreoffice-5-0' - include/o3tl o3tl/CppunitTest_o3tl_tests.mk o3tl/qa
Tomaž Vajngerl
tomaz.vajngerl at collabora.co.uk
Fri Aug 7 02:34:16 PDT 2015
include/o3tl/lru_map.hxx | 141 ++++++++++++++++++++++++
o3tl/CppunitTest_o3tl_tests.mk | 1
o3tl/qa/test-lru_map.cxx | 239 +++++++++++++++++++++++++++++++++++++++++
3 files changed, 381 insertions(+)
New commits:
commit 1215b9deff48c071f1ca8916f8307cb329bf495e
Author: Tomaž Vajngerl <tomaz.vajngerl at collabora.co.uk>
Date: Fri Jul 24 13:39:22 2015 +0900
LRU map (cache) implementation to o3tl + tests
Change-Id: I6b1a39918e6c8c67712be2c8e9907266dcfefedb
(cherry picked from commit 80a92134806a876287818530eb61c6bb536a05f9)
Reviewed-on: https://gerrit.libreoffice.org/17555
Tested-by: Jenkins <ci at libreoffice.org>
Reviewed-by: Miklos Vajna <vmiklos at collabora.co.uk>
diff --git a/include/o3tl/lru_map.hxx b/include/o3tl/lru_map.hxx
new file mode 100644
index 0000000..6d3b725
--- /dev/null
+++ b/include/o3tl/lru_map.hxx
@@ -0,0 +1,141 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ */
+
+#ifndef INCLUDED_O3TL_LRU_MAP_HXX
+#define INCLUDED_O3TL_LRU_MAP_HXX
+
+#include <list>
+#include <unordered_map>
+
+namespace o3tl
+{
+
+/** LRU map
+ *
+ * Similar to unordered_map (it actually uses it) with additionaly functionality
+ * which removes the entries that have been "least recently used" when the size
+ * hits the specified capacity.
+ *
+ * It only implements the minimal methods needed and the implementation is NOT
+ * thread safe.
+ *
+ * The implementation is as simple as possible but it still uses O(1) complexity
+ * for most of the operations with a combination unordered map and linked list.
+ *
+ **/
+template<typename Key, typename Value, class KeyHash = std::hash<Key>>
+class lru_map SAL_FINAL
+{
+private:
+ typedef typename std::pair<Key, Value> key_value_pair_t;
+ typedef std::list<key_value_pair_t> list_t;
+ typedef typename list_t::iterator list_iterator_t;
+ typedef typename list_t::const_iterator list_const_iterator_t;
+
+ typedef std::unordered_map<Key, list_iterator_t, KeyHash> map_t;
+ typedef typename map_t::iterator map_iterator_t;
+ typedef typename map_t::const_iterator map_const_iterator_t;
+
+ list_t mLruList;
+ map_t mLruMap;
+ const size_t mMaxSize;
+
+ inline void checkLRU()
+ {
+ if (mLruMap.size() > mMaxSize)
+ {
+ // remove from map
+ mLruMap.erase(mLruList.back().first);
+ // remove from list
+ mLruList.pop_back();
+ }
+ }
+public:
+ typedef list_iterator_t iterator;
+ typedef list_const_iterator_t const_iterator;
+
+ lru_map(size_t nMaxSize)
+ : mMaxSize(nMaxSize)
+ {}
+
+ void insert(key_value_pair_t& rPair)
+ {
+ map_iterator_t iterator = mLruMap.find(rPair.first);
+
+ if (iterator == mLruMap.end()) // doesn't exist -> add to queue and map
+ {
+ // add to front of the list
+ mLruList.push_front(rPair);
+ // add the list position (iterator) to the map
+ mLruMap[rPair.first] = mLruList.begin();
+ checkLRU();
+ }
+ else // already exists -> replace value
+ {
+ // replace value
+ iterator->second->second = rPair.second;
+ // bring to front of the lru list
+ mLruList.splice(mLruList.begin(), mLruList, iterator->second);
+ }
+ }
+
+ void insert(key_value_pair_t&& rPair)
+ {
+ map_iterator_t iterator = mLruMap.find(rPair.first);
+
+ if (iterator == mLruMap.end()) // doesn't exist -> add to list and map
+ {
+ // add to front of the list
+ mLruList.push_front(std::move(rPair));
+ // add the list position (iterator) to the map
+ mLruMap[rPair.first] = mLruList.begin();
+ checkLRU();
+ }
+ else // already exists -> replace value
+ {
+ // replace value
+ iterator->second->second = std::move(rPair.second);
+ // push to back of the lru list
+ mLruList.splice(mLruList.begin(), mLruList, iterator->second);
+ }
+ }
+
+ const list_const_iterator_t find(const Key& key)
+ {
+ const map_iterator_t iterator = mLruMap.find(key);
+ if (iterator == mLruMap.cend()) // can't find entry for the key
+ {
+ // return empty iterator
+ return mLruList.cend();
+ }
+ else
+ {
+ // push to back of the lru list
+ mLruList.splice(mLruList.begin(), mLruList, iterator->second);
+ return iterator->second;
+ }
+ }
+
+ const list_const_iterator_t end() const
+ {
+ return mLruList.end();
+ }
+
+ size_t size() const
+ {
+ return mLruList.size();
+ }
+};
+
+}
+
+#endif /* INCLUDED_O3TL_LRU_MAP_HXX */
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/o3tl/CppunitTest_o3tl_tests.mk b/o3tl/CppunitTest_o3tl_tests.mk
index 66f2951..c8f8f6b 100644
--- a/o3tl/CppunitTest_o3tl_tests.mk
+++ b/o3tl/CppunitTest_o3tl_tests.mk
@@ -33,6 +33,7 @@ $(eval $(call gb_CppunitTest_add_exception_objects,o3tl_tests,\
o3tl/qa/test-vector_pool \
o3tl/qa/test-sorted_vector \
o3tl/qa/test-typed_flags \
+ o3tl/qa/test-lru_map \
))
# vim: set noet sw=4:
diff --git a/o3tl/qa/test-lru_map.cxx b/o3tl/qa/test-lru_map.cxx
new file mode 100644
index 0000000..d9428e3
--- /dev/null
+++ b/o3tl/qa/test-lru_map.cxx
@@ -0,0 +1,239 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ */
+
+#include <sal/types.h>
+#include "cppunit/TestAssert.h"
+#include "cppunit/TestFixture.h"
+#include "cppunit/extensions/HelperMacros.h"
+
+#include <o3tl/lru_map.hxx>
+
+#include <boost/functional/hash.hpp>
+
+using namespace ::o3tl;
+
+class lru_map_test : public CppUnit::TestFixture
+{
+public:
+ void testBaseUsage();
+ void testReplaceKey();
+ void testReplaceValue();
+ void testLruRemoval();
+ void testCustomHash();
+
+ CPPUNIT_TEST_SUITE(lru_map_test);
+ CPPUNIT_TEST(testBaseUsage);
+ CPPUNIT_TEST(testReplaceKey);
+ CPPUNIT_TEST(testReplaceValue);
+ CPPUNIT_TEST(testLruRemoval);
+ CPPUNIT_TEST(testCustomHash);
+ CPPUNIT_TEST_SUITE_END();
+};
+
+void lru_map_test::testBaseUsage()
+{
+ o3tl::lru_map<int, int> lru(10);
+ lru.insert(std::make_pair<int, int>(1, 1));
+
+ std::pair<int, int> pair;
+ for (int i = 2; i < 7; i++)
+ {
+ pair.first = pair.second = i;
+ lru.insert(pair);
+ }
+
+ CPPUNIT_ASSERT_EQUAL(size_t(6), lru.size());
+
+ o3tl::lru_map<int, int>::const_iterator it;
+
+ it = lru.find(2);
+ CPPUNIT_ASSERT(it != lru.end());
+ CPPUNIT_ASSERT_EQUAL(2, it->second);
+
+ it = lru.find(5);
+ CPPUNIT_ASSERT(it != lru.end());
+ CPPUNIT_ASSERT_EQUAL(5, it->second);
+
+ it = lru.find(0);
+ CPPUNIT_ASSERT(it == lru.end());
+}
+
+void lru_map_test::testReplaceValue()
+{
+ o3tl::lru_map<int, int> lru(2);
+ // check if map is empty
+ CPPUNIT_ASSERT_EQUAL(size_t(0), lru.size());
+
+ // check if inserting entry with with same key replaces the value
+
+ // inserting new entry
+ lru.insert(std::make_pair<int, int>(1, 2));
+ CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
+ CPPUNIT_ASSERT_EQUAL(2, lru.find(1)->second);
+
+ // inserting new entry with key that alreay exists
+ lru.insert(std::make_pair<int, int>(1, 4));
+ CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
+ CPPUNIT_ASSERT_EQUAL(4, lru.find(1)->second);
+
+ // inserting new entry
+ lru.insert(std::make_pair<int, int>(2, 200));
+ CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
+ CPPUNIT_ASSERT_EQUAL(4, lru.find(1)->second);
+ CPPUNIT_ASSERT_EQUAL(200, lru.find(2)->second);
+
+ // check if insert with same key, moves the entry back of the lru queu
+
+ // inserting new entry with key that alreay exists
+ lru.insert(std::make_pair<int, int>(1, 6));
+ // inserting new entry, lru removed
+ lru.insert(std::make_pair<int, int>(3, 300));
+
+ CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
+ CPPUNIT_ASSERT_EQUAL(6, lru.find(1)->second);
+ CPPUNIT_ASSERT_EQUAL(300, lru.find(3)->second);
+
+}
+
+void lru_map_test::testReplaceKey()
+{
+ o3tl::lru_map<int, int> lru(2);
+
+ // inserting new entry
+ lru.insert(std::make_pair<int, int>(1, 100));
+ CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
+ CPPUNIT_ASSERT_EQUAL(100, lru.find(1)->second);
+ CPPUNIT_ASSERT(lru.find(2) == lru.end());
+ CPPUNIT_ASSERT(lru.find(3) == lru.end());
+
+ // inserting new entry
+ lru.insert(std::make_pair<int, int>(2, 200));
+ CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
+ CPPUNIT_ASSERT_EQUAL(100, lru.find(1)->second);
+ CPPUNIT_ASSERT_EQUAL(200, lru.find(2)->second);
+ CPPUNIT_ASSERT(lru.find(3) == lru.end());
+
+ // inserting new entry, lru entry is removed
+ lru.insert(std::make_pair<int, int>(3, 300));
+ CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
+ CPPUNIT_ASSERT(lru.find(1) == lru.end());
+ CPPUNIT_ASSERT_EQUAL(200, lru.find(2)->second);
+ CPPUNIT_ASSERT_EQUAL(300, lru.find(3)->second);
+
+ // inserting new entry, lru entry is removed
+ std::pair<int, int> pair(4, 400);
+ lru.insert(pair);
+ CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
+ CPPUNIT_ASSERT(lru.find(1) == lru.end());
+ CPPUNIT_ASSERT(lru.find(2) == lru.end());
+ CPPUNIT_ASSERT_EQUAL(300, lru.find(3)->second);
+ CPPUNIT_ASSERT_EQUAL(400, lru.find(4)->second);
+}
+
+void lru_map_test::testLruRemoval()
+{
+ o3tl::lru_map<int, int> lru(5);
+ CPPUNIT_ASSERT_EQUAL(size_t(0), lru.size());
+
+ // fill up..
+ lru.insert(std::make_pair<int, int>(1, 100));
+ lru.insert(std::make_pair<int, int>(2, 200));
+ lru.insert(std::make_pair<int, int>(3, 300));
+ lru.insert(std::make_pair<int, int>(4, 400));
+ lru.insert(std::make_pair<int, int>(5, 500));
+ CPPUNIT_ASSERT_EQUAL(size_t(5), lru.size());
+ CPPUNIT_ASSERT_EQUAL(100, lru.find(1)->second);
+ CPPUNIT_ASSERT_EQUAL(200, lru.find(2)->second);
+ CPPUNIT_ASSERT_EQUAL(300, lru.find(3)->second);
+ CPPUNIT_ASSERT_EQUAL(400, lru.find(4)->second);
+ CPPUNIT_ASSERT_EQUAL(500, lru.find(5)->second);
+
+ // add one more entry - lru entry should be removed
+ lru.insert(std::make_pair<int, int>(6, 600));
+
+ CPPUNIT_ASSERT_EQUAL(size_t(5), lru.size());
+ CPPUNIT_ASSERT_EQUAL(200, lru.find(2)->second);
+ CPPUNIT_ASSERT_EQUAL(300, lru.find(3)->second);
+ CPPUNIT_ASSERT_EQUAL(400, lru.find(4)->second);
+ CPPUNIT_ASSERT_EQUAL(500, lru.find(5)->second);
+ CPPUNIT_ASSERT_EQUAL(600, lru.find(6)->second);
+
+ // access the lru entry to put it at the back of the lru queue
+ lru.find(2);
+ // add new entry - lru entry should be removed
+ lru.insert(std::make_pair<int, int>(7, 700));
+
+ CPPUNIT_ASSERT_EQUAL(size_t(5), lru.size());
+ CPPUNIT_ASSERT_EQUAL(200, lru.find(2)->second);
+ CPPUNIT_ASSERT_EQUAL(400, lru.find(4)->second);
+ CPPUNIT_ASSERT_EQUAL(500, lru.find(5)->second);
+ CPPUNIT_ASSERT_EQUAL(600, lru.find(6)->second);
+ CPPUNIT_ASSERT_EQUAL(700, lru.find(7)->second);
+}
+
+struct TestClassKey
+{
+ int mA;
+ int mB;
+
+ TestClassKey(int a, int b)
+ : mA(a)
+ , mB(b)
+ {}
+
+ bool operator==(TestClassKey const& aOther) const
+ {
+ return mA == aOther.mA
+ && mB == aOther.mB;
+ }
+};
+
+struct TestClassKeyHashFunction
+{
+ std::size_t operator()(TestClassKey const& aKey) const
+ {
+ std::size_t seed = 0;
+ boost::hash_combine(seed, aKey.mA);
+ boost::hash_combine(seed, aKey.mB);
+ return seed;
+ }
+};
+
+void lru_map_test::testCustomHash()
+{
+ // check lru_map with custom hash function
+ o3tl::lru_map<TestClassKey, int, TestClassKeyHashFunction> lru(2);
+ CPPUNIT_ASSERT_EQUAL(size_t(0), lru.size());
+
+ lru.insert(std::make_pair<TestClassKey, int>(TestClassKey(1,1), 2));
+ CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
+
+ lru.insert(std::make_pair<TestClassKey, int>(TestClassKey(1,1), 7));
+ CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
+
+ lru.insert(std::make_pair<TestClassKey, int>(TestClassKey(1,2), 9));
+ CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
+
+ CPPUNIT_ASSERT(lru.end() == lru.find(TestClassKey(0,0))); // non existent
+ CPPUNIT_ASSERT_EQUAL(7, lru.find(TestClassKey(1,1))->second);
+ CPPUNIT_ASSERT_EQUAL(9, lru.find(TestClassKey(1,2))->second);
+
+ lru.insert(std::make_pair<TestClassKey, int>(TestClassKey(2,1), 13));
+
+ CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
+
+ CPPUNIT_ASSERT(lru.end() == lru.find(TestClassKey(1,1)));
+ CPPUNIT_ASSERT_EQUAL(9, lru.find(TestClassKey(1,2))->second);
+ CPPUNIT_ASSERT_EQUAL(13, lru.find(TestClassKey(2,1))->second);
+}
+
+CPPUNIT_TEST_SUITE_REGISTRATION(lru_map_test);
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
More information about the Libreoffice-commits
mailing list