Page MenuHomePhabricator
Differential D11473 Diff 33538 src/test/radix_tests.cpp

Changeset View

Standalone View

View Options

src/test/radix_tests.cpp

Show First 20 Lines • Show All 57 Lines • ▼ Show 20 Linesstruct TestElementUint256 : TestElement<Uint256KeyWrapper> {
static uint256 SignedMin() { return ArithToUint256(signedMin); } static uint256 SignedMin() { return ArithToUint256(signedMin); }
static uint256 SignedMax() { return ArithToUint256(signedMax); } static uint256 SignedMax() { return ArithToUint256(signedMax); }
static uint256 MinusOne() { return ArithToUint256(minusOne); } static uint256 MinusOne() { return ArithToUint256(minusOne); }
static uint256 MinusTwo() { return ArithToUint256(minusTwo); } static uint256 MinusTwo() { return ArithToUint256(minusTwo); }
}; };
template <typename E> void testInsert() { template <typename E> void testInsert() {
RadixTree<E> mytree; Uint256RadixKey<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));
Show All 39 LinesBOOST_AUTO_TEST_CASE(insert_test) {
testInsert<TestElementInt<uint32_t>>(); testInsert<TestElementInt<uint32_t>>();
testInsert<TestElementInt<int64_t>>(); testInsert<TestElementInt<int64_t>>();
testInsert<TestElementInt<uint64_t>>(); testInsert<TestElementInt<uint64_t>>();
testInsert<TestElementUint256>(); testInsert<TestElementUint256>();
} }
template <typename E> void testGet() { template <typename E> void testGet() {
RadixTree<E> mytree; Uint256RadixKey<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 keyZero = zero->getId();
auto keyOne = one->getId(); auto keyOne = one->getId();
▲ Show 20 Lines • Show All 57 Lines • ▼ Show 20 LinesBOOST_AUTO_TEST_CASE(get_test) {
testGet<TestElementInt<uint32_t>>(); testGet<TestElementInt<uint32_t>>();
testGet<TestElementInt<int64_t>>(); testGet<TestElementInt<int64_t>>();
testGet<TestElementInt<uint64_t>>(); testGet<TestElementInt<uint64_t>>();
testGet<TestElementUint256>(); testGet<TestElementUint256>();
} }
template <typename E> void testRemove() { template <typename E> void testRemove() {
RadixTree<E> mytree; Uint256RadixKey<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 keyZero = zero->getId();
auto keyOne = one->getId(); auto keyOne = one->getId();
▲ Show 20 Lines • Show All 72 Lines • ▼ Show 20 LinesBOOST_AUTO_TEST_CASE(remove_test) {
testRemove<TestElementInt<int64_t>>(); testRemove<TestElementInt<int64_t>>();
testRemove<TestElementInt<uint64_t>>(); testRemove<TestElementInt<uint64_t>>();
testRemove<TestElementUint256>(); testRemove<TestElementUint256>();
} }
BOOST_AUTO_TEST_CASE(const_element_test) { BOOST_AUTO_TEST_CASE(const_element_test) {
using C = const TestElementInt<uint64_t>; using C = const TestElementInt<uint64_t>;
RadixTree<C> mytree; Uint256RadixKey<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)));
BOOST_CHECK(!mytree.insert(RCUPtr<C>::make(1))); BOOST_CHECK(!mytree.insert(RCUPtr<C>::make(1)));
Show All 16 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<TestElementInt<uint64_t>> &mytree, void CheckConstTree(const Uint256RadixKey<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 = TestElementInt<uint64_t>; using E = TestElementInt<uint64_t>;
RadixTree<E> mytree; Uint256RadixKey<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 = TestElementInt<uint32_t>; using E = TestElementInt<uint32_t>;
RadixTree<E> mytree; Uint256RadixKey<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)));
RadixTree<E> copyTree = mytree; Uint256RadixKey<E> copyTree = mytree;
// The copy tree is identical. // The copy tree is identical.
BOOST_CHECK(copyTree.get(0)); BOOST_CHECK(copyTree.get(0));
BOOST_CHECK(copyTree.get(1)); BOOST_CHECK(copyTree.get(1));
BOOST_CHECK(copyTree.get(2)); BOOST_CHECK(copyTree.get(2));
BOOST_CHECK(copyTree.get(3)); BOOST_CHECK(copyTree.get(3));
BOOST_CHECK(mytree.insert(RCUPtr<E>::make(90))); BOOST_CHECK(mytree.insert(RCUPtr<E>::make(90)));
Show All 27 LinesBOOST_AUTO_TEST_CASE(test_cow) {
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 = TestElementInt<uint32_t>; using E = TestElementInt<uint32_t>;
RadixTree<E> mytree; Uint256RadixKey<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)));
RadixTree<E> movedTree = std::move(mytree); Uint256RadixKey<E> movedTree = std::move(mytree);
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));
BOOST_CHECK(movedTree.remove(0)); BOOST_CHECK(movedTree.remove(0));
BOOST_CHECK(movedTree.remove(1)); BOOST_CHECK(movedTree.remove(1));
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 = TestElementInt<uint32_t>; using E = TestElementInt<uint32_t>;
RadixTree<E> mytree; Uint256RadixKey<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;
for (int j = 0; j < ELEMENTS; j++) { for (int j = 0; j < ELEMENTS; j++) {
uint32_t v = lcg.next(); uint32_t v = lcg.next();
▲ Show 20 Lines • Show All 41 Lines • ▼ Show 20 LinesBOOST_AUTO_TEST_CASE(insert_stress_test) {
// Cleanup after ourselves. // Cleanup after ourselves.
RCULock::synchronize(); RCULock::synchronize();
} }
BOOST_AUTO_TEST_CASE(tree_traversal) { BOOST_AUTO_TEST_CASE(tree_traversal) {
using E = TestElement<uint32_t>; using E = TestElement<uint32_t>;
RadixTree<E> mytree; Uint256RadixKey<E> mytree;
// Build a vector of elements in ascending key order // Build a vector of elements in ascending key order
std::vector<RCUPtr<E>> elements; std::vector<RCUPtr<E>> elements;
elements.reserve(ELEMENTS); elements.reserve(ELEMENTS);
for (uint32_t i = 0; i < ELEMENTS; i++) { for (uint32_t i = 0; i < ELEMENTS; i++) {
auto ptr = RCUPtr<E>::make(i); auto ptr = RCUPtr<E>::make(i);
elements.push_back(std::move(ptr)); elements.push_back(std::move(ptr));
} }
▲ Show 20 Lines • Show All 107 Lines • Show Last 20 Lines