Changeset View
Changeset View
Standalone View
Standalone View
src/test/radix_tests.cpp
Show First 20 Lines • Show All 146 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); | |||||
// 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); | |||||
BOOST_CHECK_EQUAL(mytree.get(1), nullptr); | |||||
BOOST_CHECK_EQUAL(mytree.get(2), nullptr); | |||||
BOOST_CHECK_EQUAL(mytree.get(3), nullptr); | |||||
// 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); | |||||
BOOST_CHECK_EQUAL(mytree.get(1), nullptr); | |||||
BOOST_CHECK_EQUAL(mytree.get(2), nullptr); | |||||
BOOST_CHECK_EQUAL(mytree.get(3), nullptr); | |||||
BOOST_CHECK_EQUAL(mytree.get(maxsk), nullptr); | |||||
BOOST_CHECK_EQUAL(mytree.get(minsk), nullptr); | |||||
BOOST_CHECK_EQUAL(mytree.get(maxuk), nullptr); | |||||
BOOST_CHECK_EQUAL(mytree.get(maxuk - 1), nullptr); | |||||
jasonbcox: Needs a for loop that provides a set of cases where some random values, including min/max… | |||||
} | |||||
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; | ||||
} | } | ||||
▲ Show 20 Lines • Show All 49 Lines • Show Last 20 Lines |
Needs a for loop that provides a set of cases where some random values, including min/max values, are inserted and deleted in random order.
Additionally, the inserts and deletes should be logged logged so that in the event of a failure, debugging will be possible.