o3tl/qa/test-lru_map.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  */
  10
  11 #include <sal/types.h>
  12 #include <cppunit/TestAssert.h>
  13 #include <cppunit/TestFixture.h>
  14 #include <cppunit/extensions/HelperMacros.h>
  15
  16 #include <o3tl/lru_map.hxx>
  17
  18 #include <boost/functional/hash.hpp>
  19
  20 using namespace ::o3tl;
  21
  22 class lru_map_test : public CppUnit::TestFixture
  23 {
  24 public:
  25     void testBaseUsage();
  26     void testReplaceKey();
  27     void testReplaceValue();
  28     void testLruRemoval();
  29     void testCustomHash();
  30     void testRemoveIf();
  31     void testNoAutoCleanup();
  32
  33     CPPUNIT_TEST_SUITE(lru_map_test);
  34     CPPUNIT_TEST(testBaseUsage);
  35     CPPUNIT_TEST(testReplaceKey);
  36     CPPUNIT_TEST(testReplaceValue);
  37     CPPUNIT_TEST(testLruRemoval);
  38     CPPUNIT_TEST(testCustomHash);
  39     CPPUNIT_TEST(testRemoveIf);
  40     CPPUNIT_TEST(testNoAutoCleanup);
  41     CPPUNIT_TEST_SUITE_END();
  42 };
  43
  44 void lru_map_test::testBaseUsage()
  45 {
  46     o3tl::lru_map<int, int> lru(10);
  47     lru.insert(std::make_pair<int, int>(1, 1));
  48
  49     std::pair<int, int> pair;
  50     for (int i = 2; i < 7; i++)
  51     {
  52         pair.first = pair.second = i;
  53         lru.insert(pair);
  54     }
  55
  56     CPPUNIT_ASSERT_EQUAL(size_t(6), lru.size());
  57
  58     o3tl::lru_map<int, int>::const_iterator it;
  59
  60     it = lru.find(2);
  61     CPPUNIT_ASSERT(it != lru.end());
  62     CPPUNIT_ASSERT_EQUAL(2, it->second);
  63
  64     it = lru.find(5);
  65     CPPUNIT_ASSERT(it != lru.end());
  66     CPPUNIT_ASSERT_EQUAL(5, it->second);
  67
  68     it = lru.find(0);
  69     CPPUNIT_ASSERT(bool(it == lru.end()));
  70 }
  71
  72 void lru_map_test::testReplaceValue()
  73 {
  74     o3tl::lru_map<int, int> lru(2);
  75     // check if map is empty
  76     CPPUNIT_ASSERT_EQUAL(size_t(0), lru.size());
  77
  78     // check if inserting entry with same key replaces the value
  79
  80     // inserting new entry
  81     lru.insert(std::make_pair<int, int>(1, 2));
  82     CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
  83     CPPUNIT_ASSERT_EQUAL(2, lru.find(1)->second);
  84
  85     // inserting new entry with key that already exists
  86     lru.insert(std::make_pair<int, int>(1, 4));
  87     CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
  88     CPPUNIT_ASSERT_EQUAL(4, lru.find(1)->second);
  89
  90     // inserting new entry
  91     lru.insert(std::make_pair<int, int>(2, 200));
  92     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
  93     CPPUNIT_ASSERT_EQUAL(4, lru.find(1)->second);
  94     CPPUNIT_ASSERT_EQUAL(200, lru.find(2)->second);
  95
  96     // check if insert with same key, moves the entry back of the lru queue
  97
  98     // inserting new entry with key that already exists
  99     lru.insert(std::make_pair<int, int>(1, 6));
 100     // inserting new entry, lru removed
 101     lru.insert(std::make_pair<int, int>(3, 300));
 102
 103     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
 104     CPPUNIT_ASSERT_EQUAL(6, lru.find(1)->second);
 105     CPPUNIT_ASSERT_EQUAL(300, lru.find(3)->second);
 106
 107 }
 108
 109 void lru_map_test::testReplaceKey()
 110 {
 111     o3tl::lru_map<int, int> lru(2);
 112
 113     // inserting new entry
 114     lru.insert(std::make_pair<int, int>(1, 100));
 115     CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
 116     CPPUNIT_ASSERT_EQUAL(100, lru.find(1)->second);
 117     CPPUNIT_ASSERT(bool(lru.find(2) == lru.end()));
 118     CPPUNIT_ASSERT(bool(lru.find(3) == lru.end()));
 119
 120     // inserting new entry
 121     lru.insert(std::make_pair<int, int>(2, 200));
 122     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
 123     CPPUNIT_ASSERT_EQUAL(100, lru.find(1)->second);
 124     CPPUNIT_ASSERT_EQUAL(200, lru.find(2)->second);
 125     CPPUNIT_ASSERT(bool(lru.find(3) == lru.end()));
 126
 127     // inserting new entry, lru entry is removed
 128     lru.insert(std::make_pair<int, int>(3, 300));
 129     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
 130     CPPUNIT_ASSERT(bool(lru.find(1) == lru.end()));
 131     CPPUNIT_ASSERT_EQUAL(200, lru.find(2)->second);
 132     CPPUNIT_ASSERT_EQUAL(300, lru.find(3)->second);
 133
 134     // inserting new entry, lru entry is removed
 135     std::pair<int, int> pair(4, 400);
 136     lru.insert(pair);
 137     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
 138     CPPUNIT_ASSERT(bool(lru.find(1) == lru.end()));
 139     CPPUNIT_ASSERT(bool(lru.find(2) == lru.end()));
 140     CPPUNIT_ASSERT_EQUAL(300, lru.find(3)->second);
 141     CPPUNIT_ASSERT_EQUAL(400, lru.find(4)->second);
 142 }
 143
 144 void lru_map_test::testLruRemoval()
 145 {
 146     o3tl::lru_map<int, int> lru(5);
 147     CPPUNIT_ASSERT_EQUAL(size_t(0), lru.size());
 148
 149     // fill up...
 150     lru.insert(std::make_pair<int, int>(1, 100));
 151     lru.insert(std::make_pair<int, int>(2, 200));
 152     lru.insert(std::make_pair<int, int>(3, 300));
 153     lru.insert(std::make_pair<int, int>(4, 400));
 154     lru.insert(std::make_pair<int, int>(5, 500));
 155     CPPUNIT_ASSERT_EQUAL(size_t(5), lru.size());
 156     CPPUNIT_ASSERT_EQUAL(100, lru.find(1)->second);
 157     CPPUNIT_ASSERT_EQUAL(200, lru.find(2)->second);
 158     CPPUNIT_ASSERT_EQUAL(300, lru.find(3)->second);
 159     CPPUNIT_ASSERT_EQUAL(400, lru.find(4)->second);
 160     CPPUNIT_ASSERT_EQUAL(500, lru.find(5)->second);
 161
 162     // add one more entry - lru entry should be removed
 163     lru.insert(std::make_pair<int, int>(6, 600));
 164
 165     CPPUNIT_ASSERT_EQUAL(size_t(5), lru.size());
 166     CPPUNIT_ASSERT_EQUAL(200, lru.find(2)->second);
 167     CPPUNIT_ASSERT_EQUAL(300, lru.find(3)->second);
 168     CPPUNIT_ASSERT_EQUAL(400, lru.find(4)->second);
 169     CPPUNIT_ASSERT_EQUAL(500, lru.find(5)->second);
 170     CPPUNIT_ASSERT_EQUAL(600, lru.find(6)->second);
 171
 172     // access the lru entry to put it at the back of the lru queue
 173     lru.find(2);
 174     // add new entry - lru entry should be removed
 175     lru.insert(std::make_pair<int, int>(7, 700));
 176
 177     CPPUNIT_ASSERT_EQUAL(size_t(5), lru.size());
 178     CPPUNIT_ASSERT_EQUAL(200, lru.find(2)->second);
 179     CPPUNIT_ASSERT_EQUAL(400, lru.find(4)->second);
 180     CPPUNIT_ASSERT_EQUAL(500, lru.find(5)->second);
 181     CPPUNIT_ASSERT_EQUAL(600, lru.find(6)->second);
 182     CPPUNIT_ASSERT_EQUAL(700, lru.find(7)->second);
 183 }
 184
 185 struct TestClassKey
 186 {
 187     int mA;
 188     int mB;
 189
 190     TestClassKey(int a, int b)
 191         : mA(a)
 192         , mB(b)
 193     {}
 194
 195     bool operator==(TestClassKey const& aOther) const
 196     {
 197         return mA == aOther.mA
 198             && mB == aOther.mB;
 199     }
 200 };
 201
 202 struct TestClassKeyHashFunction
 203 {
 204     std::size_t operator()(TestClassKey const& aKey) const
 205     {
 206         std::size_t seed = 0;
 207         boost::hash_combine(seed, aKey.mA);
 208         boost::hash_combine(seed, aKey.mB);
 209         return seed;
 210     }
 211 };
 212
 213 void lru_map_test::testCustomHash()
 214 {
 215     // check lru_map with custom hash function
 216     o3tl::lru_map<TestClassKey, int, TestClassKeyHashFunction> lru(2);
 217     CPPUNIT_ASSERT_EQUAL(size_t(0), lru.size());
 218
 219     lru.insert(std::make_pair<TestClassKey, int>(TestClassKey(1,1), 2));
 220     CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
 221
 222     lru.insert(std::make_pair<TestClassKey, int>(TestClassKey(1,1), 7));
 223     CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
 224
 225     lru.insert(std::make_pair<TestClassKey, int>(TestClassKey(1,2), 9));
 226     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
 227
 228     CPPUNIT_ASSERT(bool(lru.end() == lru.find(TestClassKey(0,0)))); // non existent
 229     CPPUNIT_ASSERT_EQUAL(7, lru.find(TestClassKey(1,1))->second);
 230     CPPUNIT_ASSERT_EQUAL(9, lru.find(TestClassKey(1,2))->second);
 231
 232     lru.insert(std::make_pair<TestClassKey, int>(TestClassKey(2,1), 13));
 233
 234     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
 235
 236     CPPUNIT_ASSERT(bool(lru.end() == lru.find(TestClassKey(1,1))));
 237     CPPUNIT_ASSERT_EQUAL(9,  lru.find(TestClassKey(1,2))->second);
 238     CPPUNIT_ASSERT_EQUAL(13, lru.find(TestClassKey(2,1))->second);
 239 }
 240
 241 void lru_map_test::testRemoveIf()
 242 {
 243     typedef o3tl::lru_map<int, int> IntMap;
 244     typedef IntMap::key_value_pair_t IntMapPair;
 245     struct limit_except : public std::exception {};
 246
 247     IntMap lru(6);
 248     int i = 0;
 249     for (; i < 8; i++)
 250         lru.insert({i, i});
 251     CPPUNIT_ASSERT_EQUAL(size_t(6), lru.size());
 252     // now contains 7..2
 253
 254     // remove everything < 4 from the back
 255     try
 256     {
 257         lru.remove_if([] (IntMapPair const& rPair) {
 258             if (rPair.first >= 4)
 259                 throw limit_except();
 260             return true;
 261         });
 262         CPPUNIT_ASSERT(false); // not reached
 263     }
 264     catch (limit_except&)
 265     {
 266         // contains 7..4
 267         CPPUNIT_ASSERT_EQUAL(size_t(4), lru.size());
 268     }
 269
 270     // remove all even numbers
 271     lru.remove_if([] (IntMapPair const& rPair) { return (0 == rPair.first % 2); });
 272     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
 273     // contains 7, 5
 274
 275     lru.insert({5, 5});
 276     // contains 5, 7
 277
 278     i = 5;
 279     for (auto &rPair : lru)
 280     {
 281         CPPUNIT_ASSERT_EQUAL(i, rPair.first);
 282         i += 2;
 283     }
 284
 285     // remove the first item
 286     lru.remove_if([] (IntMapPair const& rPair) { return (rPair.first == 5); });
 287     CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
 288
 289     // remove the only item
 290     lru.remove_if([] (IntMapPair const& rPair) { return (rPair.first == 7); });
 291     CPPUNIT_ASSERT_EQUAL(size_t(0), lru.size());
 292 }
 293
 294 void lru_map_test::testNoAutoCleanup()
 295 {
 296     o3tl::lru_map<int, int> lru(0);
 297     CPPUNIT_ASSERT_EQUAL(size_t(0), lru.size());
 298     lru.insert({0,0});
 299     lru.insert({1,1});
 300     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
 301     lru.insert({0,0});
 302     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
 303
 304     int i = 0;
 305     for (auto &rPair : lru)
 306     {
 307         CPPUNIT_ASSERT_EQUAL(i, rPair.first);
 308         ++i;
 309     }
 310 }
 311
 312 CPPUNIT_TEST_SUITE_REGISTRATION(lru_map_test);
 313
 314 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */