Page MenuHomePhabricator
Differential D11405 Diff 33465 src/test/radix_tests.cpp

Changeset View

Standalone View

View Options

src/test/radix_tests.cpp

// Copyright (c) 2019 The Bitcoin developers // Copyright (c) 2019 The Bitcoin developers
// Distributed under the MIT software license, see the accompanying // Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php. // file COPYING or http://www.opensource.org/licenses/mit-license.php.
#include <radix.h> #include <radix.h>
#include <arith_uint256.h>
#include <uint256.h>
#include <test/lcg.h> #include <test/lcg.h>
#include <test/util/setup_common.h> #include <test/util/setup_common.h>
#include <boost/test/unit_test.hpp> #include <boost/test/unit_test.hpp>
#include <limits> #include <limits>
#include <type_traits> #include <type_traits>
BOOST_FIXTURE_TEST_SUITE(radix_tests, BasicTestingSetup) BOOST_FIXTURE_TEST_SUITE(radix_tests, BasicTestingSetup)
template <typename K> struct TestElement { template <typename K> struct TestElement {
K key; K key;
TestElement(K keyIn) : key(keyIn) {} TestElement(K keyIn) : key(keyIn) {}
const K &getId() const { return key; } const K &getId() const { return key; }
IMPLEMENT_RCU_REFCOUNT(uint32_t); IMPLEMENT_RCU_REFCOUNT(uint32_t);
}; };
template <typename K> void testInsert() { template <typename K> struct TestElementInt : TestElement<K> {
using E = TestElement<K>; TestElementInt(K keyIn) : TestElement<K>(std::move(keyIn)) {}
static auto SignedMin() {
return std::numeric_limits<typename std::make_signed<K>::type>::min();
}
static auto SignedMax() {
return std::numeric_limits<typename std::make_signed<K>::type>::max();
}
static auto MinusOne() {
return std::numeric_limits<typename std::make_unsigned<K>::type>::max();
}
static auto MinusTwo() {
return std::numeric_limits<
typename std::make_unsigned<K>::type>::max() -
1;
}
};
struct TestElementUint256 : TestElement<Uint256KeyWrapper> {
TestElementUint256(const uint256 &keyIn)
: TestElement<Uint256KeyWrapper>(Uint256KeyWrapper(keyIn)) {}
TestElementUint256(uint64_t keyIn)
: TestElement<Uint256KeyWrapper>(Uint256KeyWrapper(keyIn)) {}
static inline arith_uint256 signedMin = arith_uint256(1) << 255;
static inline arith_uint256 signedMax = ~signedMin;
static inline arith_uint256 minusOne = arith_uint256(0) - 1;
static inline arith_uint256 minusTwo = minusOne - 1;
static uint256 SignedMin() { return ArithToUint256(signedMin); }
static uint256 SignedMax() { return ArithToUint256(signedMax); }
static uint256 MinusOne() { return ArithToUint256(minusOne); }
static uint256 MinusTwo() { return ArithToUint256(minusTwo); }
};
template <typename E> void testInsert() {
RadixTree<E> mytree; RadixTree<E> mytree;
auto zero = RCUPtr<E>::make(0); auto zero = RCUPtr<E>::make(0);
auto one = RCUPtr<E>::make(1); auto one = RCUPtr<E>::make(1);
auto two = RCUPtr<E>::make(2); auto two = RCUPtr<E>::make(2);
auto three = RCUPtr<E>::make(3); auto three = RCUPtr<E>::make(3);
// Inserting a new element into the tree returns true. // Inserting a new element into the tree returns true.
BOOST_CHECK(mytree.insert(one)); BOOST_CHECK(mytree.insert(one));
// Inserting an element already in the tree returns false. // Inserting an element already in the tree returns false.
BOOST_CHECK(!mytree.insert(one)); BOOST_CHECK(!mytree.insert(one));
// Let's insert more elements and check behavior stays consistent. // Let's insert more elements and check behavior stays consistent.
BOOST_CHECK(mytree.insert(zero)); BOOST_CHECK(mytree.insert(zero));
BOOST_CHECK(!mytree.insert(one)); BOOST_CHECK(!mytree.insert(one));
BOOST_CHECK(mytree.insert(two)); BOOST_CHECK(mytree.insert(two));
BOOST_CHECK(mytree.insert(three)); BOOST_CHECK(mytree.insert(three));
BOOST_CHECK(!mytree.insert(zero)); BOOST_CHECK(!mytree.insert(zero));
BOOST_CHECK(!mytree.insert(one)); BOOST_CHECK(!mytree.insert(one));
BOOST_CHECK(!mytree.insert(two)); BOOST_CHECK(!mytree.insert(two));
BOOST_CHECK(!mytree.insert(three)); BOOST_CHECK(!mytree.insert(three));
// Check extreme values. // Check extreme values.
using SK = typename std::make_signed<K>::type; auto maxsigned = RCUPtr<E>::make(E::SignedMax());
auto maxsigned = RCUPtr<E>::make(std::numeric_limits<SK>::max()); auto minsigned = RCUPtr<E>::make(E::SignedMin());
auto minsigned = RCUPtr<E>::make(std::numeric_limits<SK>::min()); auto minusone = RCUPtr<E>::make(E::MinusOne());
using UK = typename std::make_unsigned<K>::type; auto minustwo = RCUPtr<E>::make(E::MinusTwo());
auto minusone = RCUPtr<E>::make(std::numeric_limits<UK>::max());
auto minustwo = RCUPtr<E>::make(std::numeric_limits<UK>::max() - 1);
// Insert them into the tree. // Insert them into the tree.
BOOST_CHECK(mytree.insert(maxsigned)); BOOST_CHECK(mytree.insert(maxsigned));
BOOST_CHECK(mytree.insert(minsigned)); BOOST_CHECK(mytree.insert(minsigned));
BOOST_CHECK(mytree.insert(minusone)); BOOST_CHECK(mytree.insert(minusone));
BOOST_CHECK(mytree.insert(minustwo)); BOOST_CHECK(mytree.insert(minustwo));
// All elements are now in the tree. // All elements are now in the tree.
BOOST_CHECK(!mytree.insert(zero)); BOOST_CHECK(!mytree.insert(zero));
BOOST_CHECK(!mytree.insert(one)); BOOST_CHECK(!mytree.insert(one));
BOOST_CHECK(!mytree.insert(two)); BOOST_CHECK(!mytree.insert(two));
BOOST_CHECK(!mytree.insert(three)); BOOST_CHECK(!mytree.insert(three));
BOOST_CHECK(!mytree.insert(maxsigned)); BOOST_CHECK(!mytree.insert(maxsigned));
BOOST_CHECK(!mytree.insert(minsigned)); BOOST_CHECK(!mytree.insert(minsigned));
BOOST_CHECK(!mytree.insert(minusone)); BOOST_CHECK(!mytree.insert(minusone));
BOOST_CHECK(!mytree.insert(minustwo)); BOOST_CHECK(!mytree.insert(minustwo));
} }
BOOST_AUTO_TEST_CASE(insert_test) { BOOST_AUTO_TEST_CASE(insert_test) {
testInsert<int32_t>(); testInsert<TestElementInt<int32_t>>();
testInsert<uint32_t>(); testInsert<TestElementInt<uint32_t>>();
testInsert<int64_t>(); testInsert<TestElementInt<int64_t>>();
testInsert<uint64_t>(); testInsert<TestElementInt<uint64_t>>();
testInsert<TestElementUint256>();
} }
template <typename K> void testGet() { template <typename E> void testGet() {
using E = TestElement<K>;
RadixTree<E> mytree; RadixTree<E> mytree;
auto zero = RCUPtr<E>::make(0); auto zero = RCUPtr<E>::make(0);
auto one = RCUPtr<E>::make(1); auto one = RCUPtr<E>::make(1);
auto two = RCUPtr<E>::make(2); auto two = RCUPtr<E>::make(2);
auto three = RCUPtr<E>::make(3); auto three = RCUPtr<E>::make(3);
auto keyZero = zero->getId();
auto keyOne = one->getId();
auto keyTwo = two->getId();
auto keyThree = three->getId();
// There are no elements in the tree so far. // There are no elements in the tree so far.
BOOST_CHECK_EQUAL(mytree.get(1), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(keyOne), NULLPTR(E));
// Insert an element into the tree and check it is there. // Insert an element into the tree and check it is there.
BOOST_CHECK(mytree.insert(one)); BOOST_CHECK(mytree.insert(one));
BOOST_CHECK_EQUAL(mytree.get(1), one); BOOST_CHECK_EQUAL(mytree.get(keyOne), one);
// Let's insert more elements and check they are recovered properly. // Let's insert more elements and check they are recovered properly.
BOOST_CHECK_EQUAL(mytree.get(0), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(keyZero), NULLPTR(E));
BOOST_CHECK(mytree.insert(zero)); BOOST_CHECK(mytree.insert(zero));
BOOST_CHECK_EQUAL(mytree.get(0), zero); BOOST_CHECK_EQUAL(mytree.get(keyZero), zero);
BOOST_CHECK_EQUAL(mytree.get(1), one); BOOST_CHECK_EQUAL(mytree.get(keyOne), one);
// More elements. // More elements.
BOOST_CHECK_EQUAL(mytree.get(2), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(keyTwo), NULLPTR(E));
BOOST_CHECK_EQUAL(mytree.get(3), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(keyThree), NULLPTR(E));
BOOST_CHECK(mytree.insert(two)); BOOST_CHECK(mytree.insert(two));
BOOST_CHECK(mytree.insert(three)); BOOST_CHECK(mytree.insert(three));
BOOST_CHECK_EQUAL(mytree.get(0), zero); BOOST_CHECK_EQUAL(mytree.get(keyZero), zero);
BOOST_CHECK_EQUAL(mytree.get(1), one); BOOST_CHECK_EQUAL(mytree.get(keyOne), one);
BOOST_CHECK_EQUAL(mytree.get(2), two); BOOST_CHECK_EQUAL(mytree.get(keyTwo), two);
BOOST_CHECK_EQUAL(mytree.get(3), three); BOOST_CHECK_EQUAL(mytree.get(keyThree), three);
// Check extreme values. auto maxsigned = RCUPtr<E>::make(E::SignedMax());
using SK = typename std::make_signed<K>::type; auto minsigned = RCUPtr<E>::make(E::SignedMin());
K maxsk = std::numeric_limits<SK>::max(); auto minusone = RCUPtr<E>::make(E::MinusOne());
K minsk = std::numeric_limits<SK>::min(); auto minustwo = RCUPtr<E>::make(E::MinusTwo());
using UK = typename std::make_unsigned<K>::type;
K maxuk = std::numeric_limits<UK>::max();
auto maxsigned = RCUPtr<E>::make(maxsk);
auto minsigned = RCUPtr<E>::make(minsk);
auto minusone = RCUPtr<E>::make(maxuk);
auto minustwo = RCUPtr<E>::make(maxuk - 1);
// Check that they are not in the tree. // Check that they are not in the tree.
BOOST_CHECK_EQUAL(mytree.get(maxsk), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(E::SignedMax()), NULLPTR(E));
BOOST_CHECK_EQUAL(mytree.get(minsk), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(E::SignedMin()), NULLPTR(E));
BOOST_CHECK_EQUAL(mytree.get(maxuk), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(E::MinusOne()), NULLPTR(E));
BOOST_CHECK_EQUAL(mytree.get(maxuk - 1), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(E::MinusTwo()), NULLPTR(E));
// Insert into the tree. // Insert into the tree.
BOOST_CHECK(mytree.insert(maxsigned)); BOOST_CHECK(mytree.insert(maxsigned));
BOOST_CHECK(mytree.insert(minsigned)); BOOST_CHECK(mytree.insert(minsigned));
BOOST_CHECK(mytree.insert(minusone)); BOOST_CHECK(mytree.insert(minusone));
BOOST_CHECK(mytree.insert(minustwo)); BOOST_CHECK(mytree.insert(minustwo));
// And now they all are in the tree. // And now they all are in the tree.
BOOST_CHECK_EQUAL(mytree.get(0), zero); BOOST_CHECK_EQUAL(mytree.get(keyZero), zero);
BOOST_CHECK_EQUAL(mytree.get(1), one); BOOST_CHECK_EQUAL(mytree.get(keyOne), one);
BOOST_CHECK_EQUAL(mytree.get(2), two); BOOST_CHECK_EQUAL(mytree.get(keyTwo), two);
BOOST_CHECK_EQUAL(mytree.get(3), three); BOOST_CHECK_EQUAL(mytree.get(keyThree), three);
BOOST_CHECK_EQUAL(mytree.get(maxsk), maxsigned); BOOST_CHECK_EQUAL(mytree.get(E::SignedMax()), maxsigned);
BOOST_CHECK_EQUAL(mytree.get(minsk), minsigned); BOOST_CHECK_EQUAL(mytree.get(E::SignedMin()), minsigned);
BOOST_CHECK_EQUAL(mytree.get(maxuk), minusone); BOOST_CHECK_EQUAL(mytree.get(E::MinusOne()), minusone);
BOOST_CHECK_EQUAL(mytree.get(maxuk - 1), minustwo); BOOST_CHECK_EQUAL(mytree.get(E::MinusTwo()), minustwo);
} }
BOOST_AUTO_TEST_CASE(get_test) { BOOST_AUTO_TEST_CASE(get_test) {
testGet<int32_t>(); testGet<TestElementInt<int32_t>>();
testGet<uint32_t>(); testGet<TestElementInt<uint32_t>>();
testGet<int64_t>(); testGet<TestElementInt<int64_t>>();
testGet<uint64_t>(); testGet<TestElementInt<uint64_t>>();
testGet<TestElementUint256>();
} }
template <typename K> void testRemove() { template <typename E> void testRemove() {
using E = TestElement<K>;
RadixTree<E> mytree; RadixTree<E> mytree;
auto zero = RCUPtr<E>::make(0); auto zero = RCUPtr<E>::make(0);
auto one = RCUPtr<E>::make(1); auto one = RCUPtr<E>::make(1);
auto two = RCUPtr<E>::make(2); auto two = RCUPtr<E>::make(2);
auto three = RCUPtr<E>::make(3); auto three = RCUPtr<E>::make(3);
auto keyZero = zero->getId();
auto keyOne = one->getId();
auto keyTwo = two->getId();
auto keyThree = three->getId();
// Removing an element that isn't in the tree returns false. // Removing an element that isn't in the tree returns false.
BOOST_CHECK(!mytree.remove(1)); BOOST_CHECK(!mytree.remove(keyOne));
// Insert an element into the tree and check you can remove it. // Insert an element into the tree and check you can remove it.
BOOST_CHECK(mytree.insert(one)); BOOST_CHECK(mytree.insert(one));
BOOST_CHECK(mytree.remove(1)); BOOST_CHECK(mytree.remove(keyOne));
BOOST_CHECK_EQUAL(mytree.get(1), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(keyOne), NULLPTR(E));
// Insert several elements and remove them. // Insert several elements and remove them.
BOOST_CHECK(mytree.insert(zero)); BOOST_CHECK(mytree.insert(zero));
BOOST_CHECK(mytree.insert(one)); BOOST_CHECK(mytree.insert(one));
BOOST_CHECK(mytree.insert(two)); BOOST_CHECK(mytree.insert(two));
BOOST_CHECK(mytree.insert(three)); BOOST_CHECK(mytree.insert(three));
BOOST_CHECK(mytree.remove(0)); BOOST_CHECK(mytree.remove(keyZero));
BOOST_CHECK(mytree.remove(1)); BOOST_CHECK(mytree.remove(keyOne));
BOOST_CHECK(mytree.remove(2)); BOOST_CHECK(mytree.remove(keyTwo));
BOOST_CHECK(mytree.remove(3)); BOOST_CHECK(mytree.remove(keyThree));
BOOST_CHECK_EQUAL(mytree.get(0), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(keyZero), NULLPTR(E));
BOOST_CHECK_EQUAL(mytree.get(1), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(keyOne), NULLPTR(E));
BOOST_CHECK_EQUAL(mytree.get(2), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(keyTwo), NULLPTR(E));
BOOST_CHECK_EQUAL(mytree.get(3), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(keyThree), NULLPTR(E));
// Once the elements are removed, removing them again returns false. // Once the elements are removed, removing them again returns false.
BOOST_CHECK(!mytree.remove(0)); BOOST_CHECK(!mytree.remove(keyZero));
BOOST_CHECK(!mytree.remove(1)); BOOST_CHECK(!mytree.remove(keyOne));
BOOST_CHECK(!mytree.remove(2)); BOOST_CHECK(!mytree.remove(keyTwo));
BOOST_CHECK(!mytree.remove(3)); BOOST_CHECK(!mytree.remove(keyThree));
// Check extreme values. // Check extreme values.
using SK = typename std::make_signed<K>::type; auto maxsigned = RCUPtr<E>::make(E::SignedMax());
K maxsk = std::numeric_limits<SK>::max(); auto minsigned = RCUPtr<E>::make(E::SignedMin());
K minsk = std::numeric_limits<SK>::min(); auto minusone = RCUPtr<E>::make(E::MinusOne());
using UK = typename std::make_unsigned<K>::type; auto minustwo = RCUPtr<E>::make(E::MinusTwo());
K maxuk = std::numeric_limits<UK>::max();
auto maxsigned = RCUPtr<E>::make(maxsk);
auto minsigned = RCUPtr<E>::make(minsk);
auto minusone = RCUPtr<E>::make(maxuk);
auto minustwo = RCUPtr<E>::make(maxuk - 1);
// Insert them all. // Insert them all.
BOOST_CHECK(mytree.insert(zero)); BOOST_CHECK(mytree.insert(zero));
BOOST_CHECK(mytree.insert(one)); BOOST_CHECK(mytree.insert(one));
BOOST_CHECK(mytree.insert(two)); BOOST_CHECK(mytree.insert(two));
BOOST_CHECK(mytree.insert(three)); BOOST_CHECK(mytree.insert(three));
BOOST_CHECK(mytree.insert(maxsigned)); BOOST_CHECK(mytree.insert(maxsigned));
BOOST_CHECK(mytree.insert(minsigned)); BOOST_CHECK(mytree.insert(minsigned));
BOOST_CHECK(mytree.insert(minusone)); BOOST_CHECK(mytree.insert(minusone));
BOOST_CHECK(mytree.insert(minustwo)); BOOST_CHECK(mytree.insert(minustwo));
// Delete them all // Delete them all
BOOST_CHECK(mytree.remove(0)); BOOST_CHECK(mytree.remove(keyZero));
BOOST_CHECK(mytree.remove(1)); BOOST_CHECK(mytree.remove(keyOne));
BOOST_CHECK(mytree.remove(2)); BOOST_CHECK(mytree.remove(keyTwo));
BOOST_CHECK(mytree.remove(3)); BOOST_CHECK(mytree.remove(keyThree));
BOOST_CHECK(mytree.remove(maxsk)); BOOST_CHECK(mytree.remove(E::SignedMax()));
BOOST_CHECK(mytree.remove(minsk)); BOOST_CHECK(mytree.remove(E::SignedMin()));
BOOST_CHECK(mytree.remove(maxuk)); BOOST_CHECK(mytree.remove(E::MinusOne()));
BOOST_CHECK(mytree.remove(maxuk - 1)); BOOST_CHECK(mytree.remove(E::MinusTwo()));
BOOST_CHECK_EQUAL(mytree.get(0), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(keyZero), NULLPTR(E));
BOOST_CHECK_EQUAL(mytree.get(1), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(keyOne), NULLPTR(E));
BOOST_CHECK_EQUAL(mytree.get(2), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(keyTwo), NULLPTR(E));
BOOST_CHECK_EQUAL(mytree.get(3), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(keyThree), NULLPTR(E));
BOOST_CHECK_EQUAL(mytree.get(maxsk), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(E::SignedMax()), NULLPTR(E));
BOOST_CHECK_EQUAL(mytree.get(minsk), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(E::SignedMin()), NULLPTR(E));
BOOST_CHECK_EQUAL(mytree.get(maxuk), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(E::MinusOne()), NULLPTR(E));
BOOST_CHECK_EQUAL(mytree.get(maxuk - 1), NULLPTR(E)); BOOST_CHECK_EQUAL(mytree.get(E::MinusTwo()), NULLPTR(E));
} }
BOOST_AUTO_TEST_CASE(remove_test) { BOOST_AUTO_TEST_CASE(remove_test) {
testRemove<int32_t>(); testRemove<TestElementInt<int32_t>>();
testRemove<uint32_t>(); testRemove<TestElementInt<uint32_t>>();
testRemove<int64_t>(); testRemove<TestElementInt<int64_t>>();
testRemove<uint64_t>(); testRemove<TestElementInt<uint64_t>>();
testRemove<TestElementUint256>();
} }
BOOST_AUTO_TEST_CASE(const_element_test) { BOOST_AUTO_TEST_CASE(const_element_test) {
using C = const TestElement<uint64_t>; using C = const TestElementInt<uint64_t>;
RadixTree<C> mytree; RadixTree<C> mytree;
BOOST_CHECK(mytree.insert(RCUPtr<C>::make(0))); BOOST_CHECK(mytree.insert(RCUPtr<C>::make(0)));
BOOST_CHECK(mytree.insert(RCUPtr<C>::make(1))); BOOST_CHECK(mytree.insert(RCUPtr<C>::make(1)));
BOOST_CHECK(mytree.insert(RCUPtr<C>::make(2))); BOOST_CHECK(mytree.insert(RCUPtr<C>::make(2)));
BOOST_CHECK(mytree.insert(RCUPtr<C>::make(3))); BOOST_CHECK(mytree.insert(RCUPtr<C>::make(3)));
BOOST_CHECK(!mytree.insert(RCUPtr<C>::make(0))); BOOST_CHECK(!mytree.insert(RCUPtr<C>::make(0)));
Show All 17 LinesBOOST_AUTO_TEST_CASE(const_element_test) {
BOOST_CHECK(!mytree.get(3)); BOOST_CHECK(!mytree.get(3));
BOOST_CHECK(!mytree.remove(0)); BOOST_CHECK(!mytree.remove(0));
BOOST_CHECK(!mytree.remove(1)); BOOST_CHECK(!mytree.remove(1));
BOOST_CHECK(!mytree.remove(2)); BOOST_CHECK(!mytree.remove(2));
BOOST_CHECK(!mytree.remove(3)); BOOST_CHECK(!mytree.remove(3));
} }
void CheckConstTree(const RadixTree<TestElement<uint64_t>> &mytree, void CheckConstTree(const RadixTree<TestElementInt<uint64_t>> &mytree,
bool expected) { bool expected) {
BOOST_CHECK_EQUAL(!!mytree.get(0), expected); BOOST_CHECK_EQUAL(!!mytree.get(0), expected);
BOOST_CHECK_EQUAL(!!mytree.get(1), expected); BOOST_CHECK_EQUAL(!!mytree.get(1), expected);
BOOST_CHECK_EQUAL(!!mytree.get(2), expected); BOOST_CHECK_EQUAL(!!mytree.get(2), expected);
BOOST_CHECK_EQUAL(!!mytree.get(3), expected); BOOST_CHECK_EQUAL(!!mytree.get(3), expected);
} }
BOOST_AUTO_TEST_CASE(const_tree_test) { BOOST_AUTO_TEST_CASE(const_tree_test) {
using E = TestElement<uint64_t>; using E = TestElementInt<uint64_t>;
RadixTree<E> mytree; RadixTree<E> mytree;
CheckConstTree(mytree, false); CheckConstTree(mytree, false);
BOOST_CHECK(mytree.insert(RCUPtr<E>::make(0))); BOOST_CHECK(mytree.insert(RCUPtr<E>::make(0)));
BOOST_CHECK(mytree.insert(RCUPtr<E>::make(1))); BOOST_CHECK(mytree.insert(RCUPtr<E>::make(1)));
BOOST_CHECK(mytree.insert(RCUPtr<E>::make(2))); BOOST_CHECK(mytree.insert(RCUPtr<E>::make(2)));
BOOST_CHECK(mytree.insert(RCUPtr<E>::make(3))); BOOST_CHECK(mytree.insert(RCUPtr<E>::make(3)));
CheckConstTree(mytree, true); CheckConstTree(mytree, true);
BOOST_CHECK(mytree.remove(0)); BOOST_CHECK(mytree.remove(0));
BOOST_CHECK(mytree.remove(1)); BOOST_CHECK(mytree.remove(1));
BOOST_CHECK(mytree.remove(2)); BOOST_CHECK(mytree.remove(2));
BOOST_CHECK(mytree.remove(3)); BOOST_CHECK(mytree.remove(3));
CheckConstTree(mytree, false); CheckConstTree(mytree, false);
} }
BOOST_AUTO_TEST_CASE(test_cow) { BOOST_AUTO_TEST_CASE(test_cow) {
using E = TestElement<uint32_t>; using E = TestElementInt<uint32_t>;
RadixTree<E> mytree; RadixTree<E> mytree;
BOOST_CHECK(mytree.insert(RCUPtr<E>::make(0))); BOOST_CHECK(mytree.insert(RCUPtr<E>::make(0)));
BOOST_CHECK(mytree.insert(RCUPtr<E>::make(1))); BOOST_CHECK(mytree.insert(RCUPtr<E>::make(1)));
BOOST_CHECK(mytree.insert(RCUPtr<E>::make(2))); BOOST_CHECK(mytree.insert(RCUPtr<E>::make(2)));
BOOST_CHECK(mytree.insert(RCUPtr<E>::make(3))); BOOST_CHECK(mytree.insert(RCUPtr<E>::make(3)));
Show All 34 LinesBOOST_AUTO_TEST_CASE(test_cow) {
BOOST_CHECK(copyTree.get(3)); BOOST_CHECK(copyTree.get(3));
BOOST_CHECK(copyTree.get(90)); BOOST_CHECK(copyTree.get(90));
BOOST_CHECK(copyTree.get(91)); BOOST_CHECK(copyTree.get(91));
BOOST_CHECK(copyTree.get(92)); BOOST_CHECK(copyTree.get(92));
BOOST_CHECK(copyTree.get(93)); BOOST_CHECK(copyTree.get(93));
} }
BOOST_AUTO_TEST_CASE(test_move) { BOOST_AUTO_TEST_CASE(test_move) {
using E = TestElement<uint32_t>; using E = TestElementInt<uint32_t>;
RadixTree<E> mytree; RadixTree<E> mytree;
BOOST_CHECK(mytree.insert(RCUPtr<E>::make(0))); BOOST_CHECK(mytree.insert(RCUPtr<E>::make(0)));
BOOST_CHECK(mytree.insert(RCUPtr<E>::make(1))); BOOST_CHECK(mytree.insert(RCUPtr<E>::make(1)));
BOOST_CHECK(mytree.insert(RCUPtr<E>::make(2))); BOOST_CHECK(mytree.insert(RCUPtr<E>::make(2)));
BOOST_CHECK(mytree.insert(RCUPtr<E>::make(3))); BOOST_CHECK(mytree.insert(RCUPtr<E>::make(3)));
Show All 9 LinesBOOST_AUTO_TEST_CASE(test_move) {
BOOST_CHECK(movedTree.remove(2)); BOOST_CHECK(movedTree.remove(2));
BOOST_CHECK(movedTree.remove(3)); BOOST_CHECK(movedTree.remove(3));
} }
#define THREADS 128 #define THREADS 128
#define ELEMENTS 65536 #define ELEMENTS 65536
BOOST_AUTO_TEST_CASE(insert_stress_test) { BOOST_AUTO_TEST_CASE(insert_stress_test) {
using E = TestElement<uint32_t>; using E = TestElementInt<uint32_t>;
RadixTree<E> mytree; RadixTree<E> mytree;
std::atomic<uint32_t> success{0}; std::atomic<uint32_t> success{0};
std::vector<std::thread> threads; std::vector<std::thread> threads;
for (int i = 0; i < THREADS; i++) { for (int i = 0; i < THREADS; i++) {
threads.push_back(std::thread([&] { threads.push_back(std::thread([&] {
MMIXLinearCongruentialGenerator lcg; MMIXLinearCongruentialGenerator lcg;
▲ Show 20 Lines • Show All 73 Lines • ▼ Show 20 Lines mytree.forEachLeaf([&](RCUPtr<E> ptr) {
BOOST_CHECK_EQUAL(ptr->getId(), count); BOOST_CHECK_EQUAL(ptr->getId(), count);
BOOST_CHECK_EQUAL(ptr, elements[count++]); BOOST_CHECK_EQUAL(ptr, elements[count++]);
}); });
// All the elements are parsed // All the elements are parsed
BOOST_CHECK_EQUAL(count, ELEMENTS); BOOST_CHECK_EQUAL(count, ELEMENTS);
} }
BOOST_AUTO_TEST_CASE(uint256_key_wrapper) {
Uint256KeyWrapper key = uint256S(
"AA00000000000000000000000000000000000000000000000000000000000000");
auto checkEqual = [&](const Uint256KeyWrapper &val,
const uint256 &expected) {
BOOST_CHECK_EQUAL(ArithToUint256(val.base), expected);
};
auto checkOperands = [&](const Uint256KeyWrapper &val,
const uint256 &expected_uint256,
const size_t expected_size_t) {
checkEqual(val, expected_uint256);
checkEqual(val & Uint256KeyWrapper(uint256::ZERO), uint256::ZERO);
checkEqual(val & val, expected_uint256);
checkEqual(val & TestElementUint256::MinusOne(), expected_uint256);
BOOST_CHECK_EQUAL(size_t(val), expected_size_t);
};
// clang-format off
checkOperands(key >> 0u, uint256S("AA00000000000000000000000000000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 1u, uint256S("5500000000000000000000000000000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 2u, uint256S("2A80000000000000000000000000000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 3u, uint256S("1540000000000000000000000000000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 4u, uint256S("0AA0000000000000000000000000000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 8u, uint256S("00AA000000000000000000000000000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 16u, uint256S("0000AA0000000000000000000000000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 24u, uint256S("000000AA00000000000000000000000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 32u, uint256S("00000000AA000000000000000000000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 40u, uint256S("0000000000AA0000000000000000000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 48u, uint256S("000000000000AA00000000000000000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 56u, uint256S("00000000000000AA000000000000000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 64u, uint256S("0000000000000000AA0000000000000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 72u, uint256S("000000000000000000AA00000000000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 80u, uint256S("00000000000000000000AA000000000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 88u, uint256S("0000000000000000000000AA0000000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 96u, uint256S("000000000000000000000000AA00000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 104u, uint256S("00000000000000000000000000AA000000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 112u, uint256S("0000000000000000000000000000AA0000000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 120u, uint256S("000000000000000000000000000000AA00000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 128u, uint256S("00000000000000000000000000000000AA000000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 136u, uint256S("0000000000000000000000000000000000AA0000000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 144u, uint256S("000000000000000000000000000000000000AA00000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 152u, uint256S("00000000000000000000000000000000000000AA000000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 160u, uint256S("0000000000000000000000000000000000000000AA0000000000000000000000"), 0x0000000000000000);
checkOperands(key >> 168u, uint256S("000000000000000000000000000000000000000000AA00000000000000000000"), 0x0000000000000000);
checkOperands(key >> 176u, uint256S("00000000000000000000000000000000000000000000AA000000000000000000"), 0x0000000000000000);
checkOperands(key >> 184u, uint256S("0000000000000000000000000000000000000000000000AA0000000000000000"), 0x0000000000000000);
checkOperands(key >> 185u, uint256S("0000000000000000000000000000000000000000000000550000000000000000"), 0x0000000000000000);
checkOperands(key >> 186u, uint256S("00000000000000000000000000000000000000000000002A8000000000000000"), 0x8000000000000000);
checkOperands(key >> 192u, uint256S("000000000000000000000000000000000000000000000000AA00000000000000"), 0xAA00000000000000);
checkOperands(key >> 200u, uint256S("00000000000000000000000000000000000000000000000000AA000000000000"), 0x00AA000000000000);
checkOperands(key >> 208u, uint256S("0000000000000000000000000000000000000000000000000000AA0000000000"), 0x0000AA0000000000);
checkOperands(key >> 216u, uint256S("000000000000000000000000000000000000000000000000000000AA00000000"), 0x000000AA00000000);
checkOperands(key >> 224u, uint256S("00000000000000000000000000000000000000000000000000000000AA000000"), 0x00000000AA000000);
checkOperands(key >> 232u, uint256S("0000000000000000000000000000000000000000000000000000000000AA0000"), 0x0000000000AA0000);
checkOperands(key >> 240u, uint256S("000000000000000000000000000000000000000000000000000000000000AA00"), 0x000000000000AA00);
checkOperands(key >> 248u, uint256S("00000000000000000000000000000000000000000000000000000000000000AA"), 0x00000000000000AA);
checkOperands(key >> 252u, uint256S("000000000000000000000000000000000000000000000000000000000000000A"), 0x000000000000000A);
checkOperands(key >> 253u, uint256S("0000000000000000000000000000000000000000000000000000000000000005"), 0x0000000000000005);
checkOperands(key >> 254u, uint256S("0000000000000000000000000000000000000000000000000000000000000002"), 0x0000000000000002);
checkOperands(key >> 255u, uint256S("0000000000000000000000000000000000000000000000000000000000000001"), 0x0000000000000001);
checkOperands(key >> 256u, uint256S("0000000000000000000000000000000000000000000000000000000000000000"), 0x0000000000000000);
// clang-format on
}
BOOST_AUTO_TEST_SUITE_END() BOOST_AUTO_TEST_SUITE_END()