Differential D2481 Diff 7118 src/test/radix_tests.cpp

Changeset View

Standalone View

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 "test/lcg.h"
#include <test/test_bitcoin.h>		#include <test/test_bitcoin.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)
▲ Show 20 Lines • Show All 298 Lines • ▼ Show 20 Lines	BOOST_AUTO_TEST_CASE(const_tree_test) {
BOOST_CHECK(mytree.remove(3));		BOOST_CHECK(mytree.remove(3));

CheckConstTree(mytree, false);		CheckConstTree(mytree, false);
}		}

#define THREADS 128		#define THREADS 128
#define ELEMENTS 65536		#define ELEMENTS 65536

static uint64_t next(uint64_t x) {
// Simple linear congruential generator by Donald Knuth.
return x * 6364136223846793005 + 1442695040888963407;
}

BOOST_AUTO_TEST_CASE(insert_stress_test) {		BOOST_AUTO_TEST_CASE(insert_stress_test) {
typedef TestElement<uint32_t> E;		typedef TestElement<uint32_t> E;

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([&] {
uint64_t rand = 0;		MMIXLinearCongruentialGenerator lcg;
for (int j = 0; j < ELEMENTS; j++) {		for (int j = 0; j < ELEMENTS; j++) {
rand = next(rand);		uint32_t v = lcg.next();
uint32_t v(rand >> 32);

if (mytree.remove(v)) {		if (mytree.remove(v)) {
success--;		success--;
std::this_thread::yield();		std::this_thread::yield();
}		}

auto ptr = RCUPtr<E>::make(v);		auto ptr = RCUPtr<E>::make(v);
if (mytree.insert(ptr)) {		if (mytree.insert(ptr)) {
Show All 17 Lines	BOOST_AUTO_TEST_CASE(insert_stress_test) {
// Wait for all the threads to finish.		// Wait for all the threads to finish.
for (std::thread &t : threads) {		for (std::thread &t : threads) {
t.join();		t.join();
}		}

BOOST_CHECK_EQUAL(success.load(), ELEMENTS);		BOOST_CHECK_EQUAL(success.load(), ELEMENTS);

// All the elements have been inserted into the tree.		// All the elements have been inserted into the tree.
uint64_t rand = 0;		MMIXLinearCongruentialGenerator lcg;
for (int i = 0; i < ELEMENTS; i++) {		for (int i = 0; i < ELEMENTS; i++) {
rand = next(rand);		uint32_t v = lcg.next();
uint32_t v(rand >> 32);
BOOST_CHECK_EQUAL(mytree.get(v)->getId(), v);		BOOST_CHECK_EQUAL(mytree.get(v)->getId(), v);
auto ptr = RCUPtr<E>::make(v);		auto ptr = RCUPtr<E>::make(v);
BOOST_CHECK(!mytree.insert(ptr));		BOOST_CHECK(!mytree.insert(ptr));
BOOST_CHECK(mytree.get(v) != ptr);		BOOST_CHECK(mytree.get(v) != ptr);
}		}

// Cleanup after ourselves.		// Cleanup after ourselves.
RCULock::synchronize();		RCULock::synchronize();
}		}

BOOST_AUTO_TEST_SUITE_END()		BOOST_AUTO_TEST_SUITE_END()