Differential D2336 Diff 6891 src/test/radix_tests.cpp

Changeset View

Standalone View

src/test/radix_tests.cpp

	Show First 20 Lines • Show All 155 Lines • ▼ Show 20 Lines

	BOOST_AUTO_TEST_CASE(get_test) {			BOOST_AUTO_TEST_CASE(get_test) {
	testGet<int32_t>();			testGet<int32_t>();
	testGet<uint32_t>();			testGet<uint32_t>();
	testGet<int64_t>();			testGet<int64_t>();
	testGet<uint64_t>();			testGet<uint64_t>();
	}			}

				template <typename K> void testRemove() {
				typedef TestElement<K> E;
				RadixTree<E> mytree;

				E zero(0);
				E one(1);
				E two(2);
				E three(3);

				// Removing an element that isn't in the tree returns false.
				BOOST_CHECK(!mytree.remove(1));

				// Insert an element into the tree and check you can remove it.
				BOOST_CHECK(mytree.insert(&one));
				BOOST_CHECK(mytree.remove(1));
				BOOST_CHECK_EQUAL(mytree.get(1), NULLPTR(E));

				// Insert several elements and remove them.
				BOOST_CHECK(mytree.insert(&zero));
				BOOST_CHECK(mytree.insert(&one));
				BOOST_CHECK(mytree.insert(&two));
				BOOST_CHECK(mytree.insert(&three));

				BOOST_CHECK(mytree.remove(0));
				BOOST_CHECK(mytree.remove(1));
				BOOST_CHECK(mytree.remove(2));
				BOOST_CHECK(mytree.remove(3));

				BOOST_CHECK_EQUAL(mytree.get(0), NULLPTR(E));
				BOOST_CHECK_EQUAL(mytree.get(1), NULLPTR(E));
				BOOST_CHECK_EQUAL(mytree.get(2), NULLPTR(E));
				BOOST_CHECK_EQUAL(mytree.get(3), NULLPTR(E));

				// Once the elements are removed, removing them again returns false.
				BOOST_CHECK(!mytree.remove(0));
				BOOST_CHECK(!mytree.remove(1));
				BOOST_CHECK(!mytree.remove(2));
				BOOST_CHECK(!mytree.remove(3));

				// Check extreme values.
				typedef typename std::make_signed<K>::type SK;
				K maxsk = std::numeric_limits<SK>::max();
				K minsk = std::numeric_limits<SK>::min();
				typedef typename std::make_unsigned<K>::type UK;
				K maxuk = std::numeric_limits<UK>::max();

				E maxsigned(maxsk);
				E minsigned(minsk);
				E minusone(maxuk);
				E minustwo(maxuk - 1);

				// Insert them all.
				BOOST_CHECK(mytree.insert(&zero));
				BOOST_CHECK(mytree.insert(&one));
				BOOST_CHECK(mytree.insert(&two));
				BOOST_CHECK(mytree.insert(&three));
				BOOST_CHECK(mytree.insert(&maxsigned));
				BOOST_CHECK(mytree.insert(&minsigned));
				BOOST_CHECK(mytree.insert(&minusone));
				BOOST_CHECK(mytree.insert(&minustwo));

				// Delete them all
				BOOST_CHECK(mytree.remove(0));
				BOOST_CHECK(mytree.remove(1));
				BOOST_CHECK(mytree.remove(2));
				BOOST_CHECK(mytree.remove(3));
				BOOST_CHECK(mytree.remove(maxsk));
				BOOST_CHECK(mytree.remove(minsk));
				BOOST_CHECK(mytree.remove(maxuk));
				BOOST_CHECK(mytree.remove(maxuk - 1));

				BOOST_CHECK_EQUAL(mytree.get(0), NULLPTR(E));
				BOOST_CHECK_EQUAL(mytree.get(1), NULLPTR(E));
				BOOST_CHECK_EQUAL(mytree.get(2), NULLPTR(E));
				BOOST_CHECK_EQUAL(mytree.get(3), NULLPTR(E));
				BOOST_CHECK_EQUAL(mytree.get(maxsk), NULLPTR(E));
				BOOST_CHECK_EQUAL(mytree.get(minsk), NULLPTR(E));
				BOOST_CHECK_EQUAL(mytree.get(maxuk), NULLPTR(E));
				BOOST_CHECK_EQUAL(mytree.get(maxuk - 1), NULLPTR(E));
				}

				BOOST_AUTO_TEST_CASE(remove_test) {
				testRemove<int32_t>();
				testRemove<uint32_t>();
				testRemove<int64_t>();
				testRemove<uint64_t>();
				}

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

	static uint64_t next(uint64_t x) {			static uint64_t next(uint64_t x) {
	// Simple linear congruential generator by Donald Knuth.			// Simple linear congruential generator by Donald Knuth.
	return x * 6364136223846793005 + 1442695040888963407;			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;			uint64_t rand = 0;
	for (int j = 0; j < ELEMENTS; j++) {			for (int j = 0; j < ELEMENTS; j++) {
	rand = next(rand);			rand = next(rand);
	uint32_t v(rand >> 32);			uint32_t v(rand >> 32);

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

	std::unique_ptr<E> ptr = MakeUnique<E>(v);			std::unique_ptr<E> ptr = MakeUnique<E>(v);
	if (mytree.insert(ptr.get())) {			if (mytree.insert(ptr.get())) {
	success++;			success++;
	ptr.release();
	std::this_thread::yield();			std::this_thread::yield();
	}			}

	// Regardless if we inserted or someone else did, the element			if (mytree.remove(v)) {
	// should now be in the tree. For some reason, boost is spewing			success--;
	// an inordinate amount of log when performing checks in other			RCULock::synchronize();
	// threads than the main one, so we'll use asserts.			}
	assert(mytree.get(v)->getId() == v);
				if (mytree.insert(ptr.get())) {
				success++;
				ptr.release();
				std::this_thread::yield();
				}
	}			}
	}));			}));
	}			}

	// 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();
	}			}
	Show All 16 Lines