src/test/mruset_tests.cpp

   1 // Copyright (c) 2012-2013 The Bitcoin Core developers
   2 // Distributed under the MIT software license, see the accompanying
   3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   4
   5 #include "mruset.h"
   6
   7 #include "random.h"
   8 #include "util.h"
   9 #include "test/test_bitcoin.h"
  10
  11 #include <set>
  12
  13 #include <boost/test/unit_test.hpp>
  14
  15 #define NUM_TESTS 16
  16 #define MAX_SIZE 100
  17
  18 using namespace std;
  19
  20 BOOST_FIXTURE_TEST_SUITE(mruset_tests, BasicTestingSetup)
  21
  22 BOOST_AUTO_TEST_CASE(mruset_test)
  23 {
  24     // The mruset being tested.
  25     mruset<int> mru(5000);
  26
  27     // Run the test 10 times.
  28     for (int test = 0; test < 10; test++) {
  29         // Reset mru.
  30         mru.clear();
  31
  32         // A deque + set to simulate the mruset.
  33         std::deque<int> rep;
  34         std::set<int> all;
  35
  36         // Insert 10000 random integers below 15000.
  37         for (int j=0; j<10000; j++) {
  38             int add = GetRandInt(15000);
  39             mru.insert(add);
  40
  41             // Add the number to rep/all as well.
  42             if (all.count(add) == 0) {
  43                all.insert(add);
  44                rep.push_back(add);
  45                if (all.size() == 5001) {
  46                    all.erase(rep.front());
  47                    rep.pop_front();
  48                }
  49             }
  50
  51             // Do a full comparison between mru and the simulated mru every 1000 and every 5001 elements.
  52             if (j % 1000 == 0 || j % 5001 == 0) {
  53                 mruset<int> mru2 = mru; // Also try making a copy
  54
  55                 // Check that all elements that should be in there, are in there.
  56                 BOOST_FOREACH(int x, rep) {
  57                     BOOST_CHECK(mru.count(x));
  58                     BOOST_CHECK(mru2.count(x));
  59                 }
  60
  61                 // Check that all elements that are in there, should be in there.
  62                 BOOST_FOREACH(int x, mru) {
  63                     BOOST_CHECK(all.count(x));
  64                 }
  65
  66                 // Check that all elements that are in there, should be in there.
  67                 BOOST_FOREACH(int x, mru2) {
  68                     BOOST_CHECK(all.count(x));
  69                 }
  70
  71                 for (int t = 0; t < 10; t++) {
  72                     int r = GetRandInt(15000);
  73                     BOOST_CHECK(all.count(r) == mru.count(r));
  74                     BOOST_CHECK(all.count(r) == mru2.count(r));
  75                 }
  76             }
  77         }
  78     }
  79 }
  80
  81 BOOST_AUTO_TEST_CASE(mrumap_test)
  82 {
  83     // The mrumap being tested.
  84     mrumap<int, char> mru(5000);
  85
  86     // Run the test 10 times.
  87     for (int test = 0; test < 10; test++) {
  88         // Reset mru.
  89         mru.clear(5000);
  90
  91         // A deque + set to simulate the mruset.
  92         std::deque<int> rep;
  93         std::map<int, char> all;
  94
  95         // Insert 10000 random integers below 15000.
  96         for (int j=0; j<10000; j++) {
  97             int add = GetRandInt(15000);
  98             char val = (char)GetRandInt(256);
  99             mru.insert(add, val);
 100
 101             // Add the number to rep/all as well.
 102             if (all.count(add) == 0) {
 103                all.insert(std::make_pair<int, char>(add, val));
 104                rep.push_back(add);
 105                if (all.size() == 5001) {
 106                    all.erase(rep.front());
 107                    rep.pop_front();
 108                }
 109             }
 110
 111             if (GetRandInt(5) == 0) {
 112                 // With 20% chance: remove an item
 113                 int pos = GetRandInt(rep.size());
 114                 std::deque<int>::iterator it = rep.begin();
 115                 while (pos--) { it++; }
 116                 int delval = *it;
 117                 mru.erase(delval);
 118                 all.erase(delval);
 119                 rep.erase(it);
 120             }
 121
 122             // Do a full comparison between mru and the simulated mru every 1000 and every 5001 elements.
 123             if (j % 1000 == 0 || j % 5001 == 0) {
 124                 // Check that all elements that should be in there, are in there.
 125                 BOOST_FOREACH(int x, rep) {
 126                     BOOST_CHECK(mru.count(x));
 127                     BOOST_CHECK(mru.find(x)->second == all[x]);
 128                 }
 129
 130                 // Check that all elements that are in there, should be in there.
 131                 for (mrumap<int, char>::iterator it = mru.begin(); it != mru.end(); it++) {
 132                     BOOST_CHECK(all.count(it->first));
 133                     BOOST_CHECK(all[it->first] == it->second);
 134                 }
 135
 136                 for (int t = 0; t < 10; t++) {
 137                     int r = GetRandInt(15000);
 138                     BOOST_CHECK(all.count(r) == mru.count(r));
 139                 }
 140             }
 141         }
 142     }
 143 }
 144
 145 BOOST_AUTO_TEST_SUITE_END()