Page MenuHomePhabricator
Differential D11405 Diff 33377 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(std::move(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)) {}
// Required by radix.h
static size_t IndexFromKey(const K &k, uint32_t depth, int mask) {
return (k >> depth) & mask;
}
// Test only
static K ToKey(K k) { return k; }
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<uint256> {
TestElementUint256(uint256 keyIn)
: TestElement<uint256>(std::move(keyIn)) {}
// Required by radix.h
static size_t IndexFromKey(const uint256 &k, uint32_t depth, int mask) {
auto index = UintToArith256(k) >> depth;
return index.GetLow64() & mask;
}
// Test only
static uint256 ToKey(const uint256 &k) { return k; }
static uint256 ToKey(uint64_t k) { return ArithToUint256(k); }
static uint256 SignedMin() {
return uint256S(
"8000000000000000000000000000000000000000000000000000000000000000");
}
static uint256 SignedMax() {
return uint256S(
"7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
}
static uint256 MinusOne() {
return uint256S(
"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
}
static uint256 MinusTwo() {
return uint256S(
"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE");
}
};
template <typename E> void testInsert() {
RadixTree<E> mytree; RadixTree<E> mytree;
auto zero = RCUPtr<E>::make(0); auto keyZero = E::ToKey(0);
auto one = RCUPtr<E>::make(1); auto keyOne = E::ToKey(1);
auto two = RCUPtr<E>::make(2); auto keyTwo = E::ToKey(2);
auto three = RCUPtr<E>::make(3); auto keyThree = E::ToKey(3);
auto zero = RCUPtr<E>::make(keyZero);
auto one = RCUPtr<E>::make(keyOne);
auto two = RCUPtr<E>::make(keyTwo);
auto three = RCUPtr<E>::make(keyThree);
// 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 keyZero = E::ToKey(0);
auto one = RCUPtr<E>::make(1); auto keyOne = E::ToKey(1);
auto two = RCUPtr<E>::make(2); auto keyTwo = E::ToKey(2);
auto three = RCUPtr<E>::make(3); auto keyThree = E::ToKey(3);
auto zero = RCUPtr<E>::make(keyZero);
auto one = RCUPtr<E>::make(keyOne);
auto two = RCUPtr<E>::make(keyTwo);
auto three = RCUPtr<E>::make(keyThree);
// 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 keyZero = E::ToKey(0);
auto one = RCUPtr<E>::make(1); auto keyOne = E::ToKey(1);
auto two = RCUPtr<E>::make(2); auto keyTwo = E::ToKey(2);
auto three = RCUPtr<E>::make(3); auto keyThree = E::ToKey(3);
auto zero = RCUPtr<E>::make(keyZero);
auto one = RCUPtr<E>::make(keyOne);
auto two = RCUPtr<E>::make(keyTwo);
auto three = RCUPtr<E>::make(keyThree);
// 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 49 Lines • Show Last 20 Lines