From 1215b9deff48c071f1ca8916f8307cb329bf495e Mon Sep 17 00:00:00 2001 From: Tomaž Vajngerl Date: Fri, 24 Jul 2015 13:39:22 +0900 Subject: 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 Reviewed-by: Miklos Vajna --- include/o3tl/lru_map.hxx | 141 ++++++++++++++++++++++++ o3tl/CppunitTest_o3tl_tests.mk | 1 + o3tl/qa/test-lru_map.cxx | 239 +++++++++++++++++++++++++++++++++++++++++ 3 files changed, 381 insertions(+) create mode 100644 include/o3tl/lru_map.hxx create mode 100644 o3tl/qa/test-lru_map.cxx diff --git a/include/o3tl/lru_map.hxx b/include/o3tl/lru_map.hxx new file mode 100644 index 000000000000..6d3b72521fc4 --- /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 +#include + +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> +class lru_map SAL_FINAL +{ +private: + typedef typename std::pair key_value_pair_t; + typedef std::list list_t; + typedef typename list_t::iterator list_iterator_t; + typedef typename list_t::const_iterator list_const_iterator_t; + + typedef std::unordered_map 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 66f2951bf4f6..c8f8f6b4e335 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 000000000000..d9428e381bb5 --- /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 +#include "cppunit/TestAssert.h" +#include "cppunit/TestFixture.h" +#include "cppunit/extensions/HelperMacros.h" + +#include + +#include + +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 lru(10); + lru.insert(std::make_pair(1, 1)); + + std::pair 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::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 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(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(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(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(1, 6)); + // inserting new entry, lru removed + lru.insert(std::make_pair(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 lru(2); + + // inserting new entry + lru.insert(std::make_pair(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(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(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 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 lru(5); + CPPUNIT_ASSERT_EQUAL(size_t(0), lru.size()); + + // fill up.. + lru.insert(std::make_pair(1, 100)); + lru.insert(std::make_pair(2, 200)); + lru.insert(std::make_pair(3, 300)); + lru.insert(std::make_pair(4, 400)); + lru.insert(std::make_pair(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(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(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 lru(2); + CPPUNIT_ASSERT_EQUAL(size_t(0), lru.size()); + + lru.insert(std::make_pair(TestClassKey(1,1), 2)); + CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size()); + + lru.insert(std::make_pair(TestClassKey(1,1), 7)); + CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size()); + + lru.insert(std::make_pair(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(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: */ -- cgit