diff options
author | Wladimir J. van der Laan <laanwj@gmail.com> | 2015-08-19 15:44:18 +0200 |
---|---|---|
committer | Wladimir J. van der Laan <laanwj@gmail.com> | 2015-08-19 15:45:14 +0200 |
commit | e08a7d9d40b982a6ded3008398c542103f81209a (patch) | |
tree | 1a8d2b18dd987139fb2d07a21ca56614e0b54f8b | |
parent | 0f0f323c9a58437b33ba4fa9a67e1edf5fc6cc88 (diff) | |
parent | 7bd57bb1d79710a60459dfdefdc5c96ec3762eb9 (diff) | |
download | bitcoin-e08a7d9d40b982a6ded3008398c542103f81209a.tar.xz |
Merge pull request #6561
7bd57bb Add limitedmap test (Casey Rodarmor)
8b06894 Disallow unlimited limited maps (Casey Rodarmor)
fd2d862 Make limited map actually respect max size (Casey Rodarmor)
-rw-r--r-- | src/Makefile.test.include | 1 | ||||
-rw-r--r-- | src/limitedmap.h | 19 | ||||
-rw-r--r-- | src/test/limitedmap_tests.cpp | 101 |
3 files changed, 113 insertions, 8 deletions
diff --git a/src/Makefile.test.include b/src/Makefile.test.include index 8289198959..fc4e047c35 100644 --- a/src/Makefile.test.include +++ b/src/Makefile.test.include @@ -52,6 +52,7 @@ BITCOIN_TESTS =\ test/getarg_tests.cpp \ test/hash_tests.cpp \ test/key_tests.cpp \ + test/limitedmap_tests.cpp \ test/main_tests.cpp \ test/mempool_tests.cpp \ test/miner_tests.cpp \ diff --git a/src/limitedmap.h b/src/limitedmap.h index e8ea549653..5456dfc7c4 100644 --- a/src/limitedmap.h +++ b/src/limitedmap.h @@ -27,7 +27,11 @@ protected: size_type nMaxSize; public: - limitedmap(size_type nMaxSizeIn = 0) { nMaxSize = nMaxSizeIn; } + limitedmap(size_type nMaxSizeIn) + { + assert(nMaxSizeIn > 0); + nMaxSize = nMaxSizeIn; + } const_iterator begin() const { return map.begin(); } const_iterator end() const { return map.end(); } size_type size() const { return map.size(); } @@ -38,13 +42,12 @@ public: { std::pair<iterator, bool> ret = map.insert(x); if (ret.second) { - if (nMaxSize && map.size() == nMaxSize) { + if (map.size() > nMaxSize) { map.erase(rmap.begin()->second); rmap.erase(rmap.begin()); } rmap.insert(make_pair(x.second, ret.first)); } - return; } void erase(const key_type& k) { @@ -81,11 +84,11 @@ public: size_type max_size() const { return nMaxSize; } size_type max_size(size_type s) { - if (s) - while (map.size() > s) { - map.erase(rmap.begin()->second); - rmap.erase(rmap.begin()); - } + assert(s > 0); + while (map.size() > s) { + map.erase(rmap.begin()->second); + rmap.erase(rmap.begin()); + } nMaxSize = s; return nMaxSize; } diff --git a/src/test/limitedmap_tests.cpp b/src/test/limitedmap_tests.cpp new file mode 100644 index 0000000000..faaddffad8 --- /dev/null +++ b/src/test/limitedmap_tests.cpp @@ -0,0 +1,101 @@ +// Copyright (c) 2012-2015 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include "limitedmap.h" + +#include "test/test_bitcoin.h" + +#include <boost/test/unit_test.hpp> + +BOOST_FIXTURE_TEST_SUITE(limitedmap_tests, BasicTestingSetup) + +BOOST_AUTO_TEST_CASE(limitedmap_test) +{ + // create a limitedmap capped at 10 items + limitedmap<int, int> map(10); + + // check that the max size is 10 + BOOST_CHECK(map.max_size() == 10); + + // check that it's empty + BOOST_CHECK(map.size() == 0); + + // insert (-1, -1) + map.insert(std::pair<int, int>(-1, -1)); + + // make sure that the size is updated + BOOST_CHECK(map.size() == 1); + + // make sure that the new items is in the map + BOOST_CHECK(map.count(-1) == 1); + + // insert 10 new items + for (int i = 0; i < 10; i++) { + map.insert(std::pair<int, int>(i, i + 1)); + } + + // make sure that the map now contains 10 items... + BOOST_CHECK(map.size() == 10); + + // ...and that the first item has been discarded + BOOST_CHECK(map.count(-1) == 0); + + // iterate over the map, both with an index and an iterator + limitedmap<int, int>::const_iterator it = map.begin(); + for (int i = 0; i < 10; i++) { + // make sure the item is present + BOOST_CHECK(map.count(i) == 1); + + // use the iterator to check for the expected key adn value + BOOST_CHECK(it->first == i); + BOOST_CHECK(it->second == i + 1); + + // use find to check for the value + BOOST_CHECK(map.find(i)->second == i + 1); + + // update and recheck + map.update(it, i + 2); + BOOST_CHECK(map.find(i)->second == i + 2); + + it++; + } + + // check that we've exhausted the iterator + BOOST_CHECK(it == map.end()); + + // resize the map to 5 items + map.max_size(5); + + // check that the max size and size are now 5 + BOOST_CHECK(map.max_size() == 5); + BOOST_CHECK(map.size() == 5); + + // check that items less than 5 have been discarded + // and items greater than 5 are retained + for (int i = 0; i < 10; i++) { + if (i < 5) { + BOOST_CHECK(map.count(i) == 0); + } else { + BOOST_CHECK(map.count(i) == 1); + } + } + + // erase some items not in the map + for (int i = 100; i < 1000; i += 100) { + map.erase(i); + } + + // check that the size is unaffected + BOOST_CHECK(map.size() == 5); + + // erase the remaining elements + for (int i = 5; i < 10; i++) { + map.erase(i); + } + + // check that the map is now empty + BOOST_CHECK(map.empty()); +} + +BOOST_AUTO_TEST_SUITE_END() |