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 void lru_map_test::testReplaceKey()
 109 {
 110     o3tl::lru_map<int, int> lru(2);
 111
 112     // inserting new entry
 113     lru.insert(std::make_pair<int, int>(1, 100));
 114     CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
 115     CPPUNIT_ASSERT_EQUAL(100, lru.find(1)->second);
 116     CPPUNIT_ASSERT(bool(lru.find(2) == lru.end()));
 117     CPPUNIT_ASSERT(bool(lru.find(3) == lru.end()));
 118
 119     // inserting new entry
 120     lru.insert(std::make_pair<int, int>(2, 200));
 121     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
 122     CPPUNIT_ASSERT_EQUAL(100, lru.find(1)->second);
 123     CPPUNIT_ASSERT_EQUAL(200, lru.find(2)->second);
 124     CPPUNIT_ASSERT(bool(lru.find(3) == lru.end()));
 125
 126     // inserting new entry, lru entry is removed
 127     lru.insert(std::make_pair<int, int>(3, 300));
 128     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
 129     CPPUNIT_ASSERT(bool(lru.find(1) == lru.end()));
 130     CPPUNIT_ASSERT_EQUAL(200, lru.find(2)->second);
 131     CPPUNIT_ASSERT_EQUAL(300, lru.find(3)->second);
 132
 133     // inserting new entry, lru entry is removed
 134     std::pair<int, int> pair(4, 400);
 135     lru.insert(pair);
 136     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
 137     CPPUNIT_ASSERT(bool(lru.find(1) == lru.end()));
 138     CPPUNIT_ASSERT(bool(lru.find(2) == lru.end()));
 139     CPPUNIT_ASSERT_EQUAL(300, lru.find(3)->second);
 140     CPPUNIT_ASSERT_EQUAL(400, lru.find(4)->second);
 141 }
 142
 143 void lru_map_test::testLruRemoval()
 144 {
 145     o3tl::lru_map<int, int> lru(5);
 146     CPPUNIT_ASSERT_EQUAL(size_t(0), lru.size());
 147
 148     // fill up...
 149     lru.insert(std::make_pair<int, int>(1, 100));
 150     lru.insert(std::make_pair<int, int>(2, 200));
 151     lru.insert(std::make_pair<int, int>(3, 300));
 152     lru.insert(std::make_pair<int, int>(4, 400));
 153     lru.insert(std::make_pair<int, int>(5, 500));
 154     CPPUNIT_ASSERT_EQUAL(size_t(5), lru.size());
 155     CPPUNIT_ASSERT_EQUAL(100, lru.find(1)->second);
 156     CPPUNIT_ASSERT_EQUAL(200, lru.find(2)->second);
 157     CPPUNIT_ASSERT_EQUAL(300, lru.find(3)->second);
 158     CPPUNIT_ASSERT_EQUAL(400, lru.find(4)->second);
 159     CPPUNIT_ASSERT_EQUAL(500, lru.find(5)->second);
 160
 161     // add one more entry - lru entry should be removed
 162     lru.insert(std::make_pair<int, int>(6, 600));
 163
 164     CPPUNIT_ASSERT_EQUAL(size_t(5), lru.size());
 165     CPPUNIT_ASSERT_EQUAL(200, lru.find(2)->second);
 166     CPPUNIT_ASSERT_EQUAL(300, lru.find(3)->second);
 167     CPPUNIT_ASSERT_EQUAL(400, lru.find(4)->second);
 168     CPPUNIT_ASSERT_EQUAL(500, lru.find(5)->second);
 169     CPPUNIT_ASSERT_EQUAL(600, lru.find(6)->second);
 170
 171     // access the lru entry to put it at the back of the lru queue
 172     lru.find(2);
 173     // add new entry - lru entry should be removed
 174     lru.insert(std::make_pair<int, int>(7, 700));
 175
 176     CPPUNIT_ASSERT_EQUAL(size_t(5), lru.size());
 177     CPPUNIT_ASSERT_EQUAL(200, lru.find(2)->second);
 178     CPPUNIT_ASSERT_EQUAL(400, lru.find(4)->second);
 179     CPPUNIT_ASSERT_EQUAL(500, lru.find(5)->second);
 180     CPPUNIT_ASSERT_EQUAL(600, lru.find(6)->second);
 181     CPPUNIT_ASSERT_EQUAL(700, lru.find(7)->second);
 182 }
 183
 184 namespace
 185 {
 186 struct TestClassKey
 187 {
 188     int mA;
 189     int mB;
 190
 191     TestClassKey(int a, int b)
 192         : mA(a)
 193         , mB(b)
 194     {
 195     }
 196
 197     bool operator==(TestClassKey const& aOther) const { return mA == aOther.mA && mB == aOther.mB; }
 198 };
 199
 200 struct TestClassKeyHashFunction
 201 {
 202     std::size_t operator()(TestClassKey const& aKey) const
 203     {
 204         std::size_t seed = 0;
 205         boost::hash_combine(seed, aKey.mA);
 206         boost::hash_combine(seed, aKey.mB);
 207         return seed;
 208     }
 209 };
 210 }
 211
 212 void lru_map_test::testCustomHash()
 213 {
 214     // check lru_map with custom hash function
 215     o3tl::lru_map<TestClassKey, int, TestClassKeyHashFunction> lru(2);
 216     CPPUNIT_ASSERT_EQUAL(size_t(0), lru.size());
 217
 218     lru.insert(std::make_pair<TestClassKey, int>(TestClassKey(1, 1), 2));
 219     CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
 220
 221     lru.insert(std::make_pair<TestClassKey, int>(TestClassKey(1, 1), 7));
 222     CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
 223
 224     lru.insert(std::make_pair<TestClassKey, int>(TestClassKey(1, 2), 9));
 225     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
 226
 227     CPPUNIT_ASSERT(bool(lru.end() == lru.find(TestClassKey(0, 0)))); // non existent
 228     CPPUNIT_ASSERT_EQUAL(7, lru.find(TestClassKey(1, 1))->second);
 229     CPPUNIT_ASSERT_EQUAL(9, lru.find(TestClassKey(1, 2))->second);
 230
 231     lru.insert(std::make_pair<TestClassKey, int>(TestClassKey(2, 1), 13));
 232
 233     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
 234
 235     CPPUNIT_ASSERT(bool(lru.end() == lru.find(TestClassKey(1, 1))));
 236     CPPUNIT_ASSERT_EQUAL(9, lru.find(TestClassKey(1, 2))->second);
 237     CPPUNIT_ASSERT_EQUAL(13, lru.find(TestClassKey(2, 1))->second);
 238 }
 239
 240 void lru_map_test::testRemoveIf()
 241 {
 242     typedef o3tl::lru_map<int, int> IntMap;
 243     typedef IntMap::key_value_pair_t IntMapPair;
 244     struct limit_except : public std::exception
 245     {
 246     };
 247
 248     IntMap lru(6);
 249     int i = 0;
 250     for (; i < 8; i++)
 251         lru.insert({ i, i });
 252     CPPUNIT_ASSERT_EQUAL(size_t(6), lru.size());
 253     // now contains 7..2
 254
 255     // remove everything < 4 from the back
 256     try
 257     {
 258         lru.remove_if([](IntMapPair const& rPair) {
 259             if (rPair.first >= 4)
 260                 throw limit_except();
 261             return true;
 262         });
 263         CPPUNIT_ASSERT(false); // not reached
 264     }
 265     catch (limit_except&)
 266     {
 267         // contains 7..4
 268         CPPUNIT_ASSERT_EQUAL(size_t(4), lru.size());
 269     }
 270
 271     // remove all even numbers
 272     lru.remove_if([](IntMapPair const& rPair) { return (0 == rPair.first % 2); });
 273     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
 274     // contains 7, 5
 275
 276     lru.insert({ 5, 5 });
 277     // contains 5, 7
 278
 279     i = 5;
 280     for (auto& rPair : lru)
 281     {
 282         CPPUNIT_ASSERT_EQUAL(i, rPair.first);
 283         i += 2;
 284     }
 285
 286     // remove the first item
 287     lru.remove_if([](IntMapPair const& rPair) { return (rPair.first == 5); });
 288     CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
 289
 290     // remove the only item
 291     lru.remove_if([](IntMapPair const& rPair) { return (rPair.first == 7); });
 292     CPPUNIT_ASSERT_EQUAL(size_t(0), lru.size());
 293 }
 294
 295 void lru_map_test::testNoAutoCleanup()
 296 {
 297     o3tl::lru_map<int, int> lru(0);
 298     CPPUNIT_ASSERT_EQUAL(size_t(0), lru.size());
 299     lru.insert({ 0, 0 });
 300     lru.insert({ 1, 1 });
 301     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
 302     lru.insert({ 0, 0 });
 303     CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
 304
 305     int i = 0;
 306     for (auto& rPair : lru)
 307     {
 308         CPPUNIT_ASSERT_EQUAL(i, rPair.first);
 309         ++i;
 310     }
 311 }
 312
 313 CPPUNIT_TEST_SUITE_REGISTRATION(lru_map_test);
 314
 315 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */