diff --git a/src/radix.h b/src/radix.h --- a/src/radix.h +++ b/src/radix.h @@ -5,6 +5,7 @@ #ifndef BITCOIN_RADIX_H #define BITCOIN_RADIX_H +#include #include #include @@ -368,7 +369,7 @@ RadixNode &operator=(const RadixNode &) = delete; std::atomic *get(uint32_t level, const KeyType &key) { - return &children[(key >> (level * BITS)) & MASK]; + return &children[(key >> uint32_t(level * BITS)) & MASK]; } bool isShared() const { return refcount > 0; } @@ -386,4 +387,24 @@ "RadixNode alignment must be 2 or more."); }; +/** + * Facility for using an uint256 as a radix tree key. + */ +struct Uint256KeyWrapper { + arith_uint256 base; + + Uint256KeyWrapper(const uint256 &keyIn) : base(UintToArith256(keyIn)) {} + Uint256KeyWrapper(const base_uint<256> &keyIn) : base(keyIn) {} + + Uint256KeyWrapper operator>>(uint32_t shift) const { return base >> shift; } + Uint256KeyWrapper operator&(const Uint256KeyWrapper &mask) const { + return base & mask.base; + } + operator size_t() const { return size_t(base.GetLow64()); } +}; + +// The radix tree relies on sizeof to gather the bit length of the key +static_assert(sizeof(Uint256KeyWrapper) == 32, + "Uint256KeyWrapper key size should be 256 bits"); + #endif // BITCOIN_RADIX_H diff --git a/src/test/radix_tests.cpp b/src/test/radix_tests.cpp --- a/src/test/radix_tests.cpp +++ b/src/test/radix_tests.cpp @@ -4,6 +4,9 @@ #include +#include +#include + #include #include @@ -23,8 +26,43 @@ IMPLEMENT_RCU_REFCOUNT(uint32_t); }; -template void testInsert() { - using E = TestElement; +template struct TestElementInt : TestElement { + TestElementInt(K keyIn) : TestElement(std::move(keyIn)) {} + + static auto SignedMin() { + return std::numeric_limits::type>::min(); + } + static auto SignedMax() { + return std::numeric_limits::type>::max(); + } + static auto MinusOne() { + return std::numeric_limits::type>::max(); + } + static auto MinusTwo() { + return std::numeric_limits< + typename std::make_unsigned::type>::max() - + 1; + } +}; + +struct TestElementUint256 : TestElement { + TestElementUint256(const uint256 &keyIn) + : TestElement(Uint256KeyWrapper(keyIn)) {} + TestElementUint256(uint64_t keyIn) + : TestElement(Uint256KeyWrapper(keyIn)) {} + + static inline arith_uint256 signedMin = arith_uint256(1) << 255; + static inline arith_uint256 signedMax = ~signedMin; + static inline arith_uint256 minusOne = arith_uint256(0) - 1; + static inline arith_uint256 minusTwo = minusOne - 1; + + static uint256 SignedMin() { return ArithToUint256(signedMin); } + static uint256 SignedMax() { return ArithToUint256(signedMax); } + static uint256 MinusOne() { return ArithToUint256(minusOne); } + static uint256 MinusTwo() { return ArithToUint256(minusTwo); } +}; + +template void testInsert() { RadixTree mytree; auto zero = RCUPtr::make(0); @@ -49,12 +87,10 @@ BOOST_CHECK(!mytree.insert(three)); // Check extreme values. - using SK = typename std::make_signed::type; - auto maxsigned = RCUPtr::make(std::numeric_limits::max()); - auto minsigned = RCUPtr::make(std::numeric_limits::min()); - using UK = typename std::make_unsigned::type; - auto minusone = RCUPtr::make(std::numeric_limits::max()); - auto minustwo = RCUPtr::make(std::numeric_limits::max() - 1); + auto maxsigned = RCUPtr::make(E::SignedMax()); + auto minsigned = RCUPtr::make(E::SignedMin()); + auto minusone = RCUPtr::make(E::MinusOne()); + auto minustwo = RCUPtr::make(E::MinusTwo()); // Insert them into the tree. BOOST_CHECK(mytree.insert(maxsigned)); @@ -74,14 +110,15 @@ } BOOST_AUTO_TEST_CASE(insert_test) { - testInsert(); - testInsert(); - testInsert(); - testInsert(); + testInsert>(); + testInsert>(); + testInsert>(); + testInsert>(); + + testInsert(); } -template void testGet() { - using E = TestElement; +template void testGet() { RadixTree mytree; auto zero = RCUPtr::make(0); @@ -89,47 +126,45 @@ auto two = RCUPtr::make(2); auto three = RCUPtr::make(3); + auto keyZero = zero->getId(); + auto keyOne = one->getId(); + auto keyTwo = two->getId(); + auto keyThree = three->getId(); + // 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. 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. - BOOST_CHECK_EQUAL(mytree.get(0), NULLPTR(E)); + BOOST_CHECK_EQUAL(mytree.get(keyZero), NULLPTR(E)); BOOST_CHECK(mytree.insert(zero)); - BOOST_CHECK_EQUAL(mytree.get(0), zero); - BOOST_CHECK_EQUAL(mytree.get(1), one); + BOOST_CHECK_EQUAL(mytree.get(keyZero), zero); + BOOST_CHECK_EQUAL(mytree.get(keyOne), one); // More elements. - BOOST_CHECK_EQUAL(mytree.get(2), NULLPTR(E)); - BOOST_CHECK_EQUAL(mytree.get(3), NULLPTR(E)); + BOOST_CHECK_EQUAL(mytree.get(keyTwo), NULLPTR(E)); + BOOST_CHECK_EQUAL(mytree.get(keyThree), NULLPTR(E)); BOOST_CHECK(mytree.insert(two)); BOOST_CHECK(mytree.insert(three)); - BOOST_CHECK_EQUAL(mytree.get(0), zero); - BOOST_CHECK_EQUAL(mytree.get(1), one); - BOOST_CHECK_EQUAL(mytree.get(2), two); - BOOST_CHECK_EQUAL(mytree.get(3), three); + BOOST_CHECK_EQUAL(mytree.get(keyZero), zero); + BOOST_CHECK_EQUAL(mytree.get(keyOne), one); + BOOST_CHECK_EQUAL(mytree.get(keyTwo), two); + BOOST_CHECK_EQUAL(mytree.get(keyThree), three); - // Check extreme values. - using SK = typename std::make_signed::type; - K maxsk = std::numeric_limits::max(); - K minsk = std::numeric_limits::min(); - using UK = typename std::make_unsigned::type; - K maxuk = std::numeric_limits::max(); - - auto maxsigned = RCUPtr::make(maxsk); - auto minsigned = RCUPtr::make(minsk); - auto minusone = RCUPtr::make(maxuk); - auto minustwo = RCUPtr::make(maxuk - 1); + auto maxsigned = RCUPtr::make(E::SignedMax()); + auto minsigned = RCUPtr::make(E::SignedMin()); + auto minusone = RCUPtr::make(E::MinusOne()); + auto minustwo = RCUPtr::make(E::MinusTwo()); // Check that they are not in the tree. - 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_CHECK_EQUAL(mytree.get(E::SignedMax()), NULLPTR(E)); + BOOST_CHECK_EQUAL(mytree.get(E::SignedMin()), NULLPTR(E)); + BOOST_CHECK_EQUAL(mytree.get(E::MinusOne()), NULLPTR(E)); + BOOST_CHECK_EQUAL(mytree.get(E::MinusTwo()), NULLPTR(E)); // Insert into the tree. BOOST_CHECK(mytree.insert(maxsigned)); @@ -138,25 +173,26 @@ BOOST_CHECK(mytree.insert(minustwo)); // And now they all are in the tree. - BOOST_CHECK_EQUAL(mytree.get(0), zero); - BOOST_CHECK_EQUAL(mytree.get(1), one); - BOOST_CHECK_EQUAL(mytree.get(2), two); - BOOST_CHECK_EQUAL(mytree.get(3), three); - BOOST_CHECK_EQUAL(mytree.get(maxsk), maxsigned); - BOOST_CHECK_EQUAL(mytree.get(minsk), minsigned); - BOOST_CHECK_EQUAL(mytree.get(maxuk), minusone); - BOOST_CHECK_EQUAL(mytree.get(maxuk - 1), minustwo); + BOOST_CHECK_EQUAL(mytree.get(keyZero), zero); + BOOST_CHECK_EQUAL(mytree.get(keyOne), one); + BOOST_CHECK_EQUAL(mytree.get(keyTwo), two); + BOOST_CHECK_EQUAL(mytree.get(keyThree), three); + BOOST_CHECK_EQUAL(mytree.get(E::SignedMax()), maxsigned); + BOOST_CHECK_EQUAL(mytree.get(E::SignedMin()), minsigned); + BOOST_CHECK_EQUAL(mytree.get(E::MinusOne()), minusone); + BOOST_CHECK_EQUAL(mytree.get(E::MinusTwo()), minustwo); } BOOST_AUTO_TEST_CASE(get_test) { - testGet(); - testGet(); - testGet(); - testGet(); + testGet>(); + testGet>(); + testGet>(); + testGet>(); + + testGet(); } -template void testRemove() { - using E = TestElement; +template void testRemove() { RadixTree mytree; auto zero = RCUPtr::make(0); @@ -164,13 +200,18 @@ auto two = RCUPtr::make(2); auto three = RCUPtr::make(3); + auto keyZero = zero->getId(); + auto keyOne = one->getId(); + auto keyTwo = two->getId(); + auto keyThree = three->getId(); + // 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. BOOST_CHECK(mytree.insert(one)); - BOOST_CHECK(mytree.remove(1)); - BOOST_CHECK_EQUAL(mytree.get(1), NULLPTR(E)); + BOOST_CHECK(mytree.remove(keyOne)); + BOOST_CHECK_EQUAL(mytree.get(keyOne), NULLPTR(E)); // Insert several elements and remove them. BOOST_CHECK(mytree.insert(zero)); @@ -178,33 +219,27 @@ 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(mytree.remove(keyZero)); + BOOST_CHECK(mytree.remove(keyOne)); + BOOST_CHECK(mytree.remove(keyTwo)); + BOOST_CHECK(mytree.remove(keyThree)); - 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(keyZero), NULLPTR(E)); + BOOST_CHECK_EQUAL(mytree.get(keyOne), NULLPTR(E)); + BOOST_CHECK_EQUAL(mytree.get(keyTwo), NULLPTR(E)); + BOOST_CHECK_EQUAL(mytree.get(keyThree), 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)); + BOOST_CHECK(!mytree.remove(keyZero)); + BOOST_CHECK(!mytree.remove(keyOne)); + BOOST_CHECK(!mytree.remove(keyTwo)); + BOOST_CHECK(!mytree.remove(keyThree)); // Check extreme values. - using SK = typename std::make_signed::type; - K maxsk = std::numeric_limits::max(); - K minsk = std::numeric_limits::min(); - using UK = typename std::make_unsigned::type; - K maxuk = std::numeric_limits::max(); - - auto maxsigned = RCUPtr::make(maxsk); - auto minsigned = RCUPtr::make(minsk); - auto minusone = RCUPtr::make(maxuk); - auto minustwo = RCUPtr::make(maxuk - 1); + auto maxsigned = RCUPtr::make(E::SignedMax()); + auto minsigned = RCUPtr::make(E::SignedMin()); + auto minusone = RCUPtr::make(E::MinusOne()); + auto minustwo = RCUPtr::make(E::MinusTwo()); // Insert them all. BOOST_CHECK(mytree.insert(zero)); @@ -217,34 +252,36 @@ 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_CHECK(mytree.remove(keyZero)); + BOOST_CHECK(mytree.remove(keyOne)); + BOOST_CHECK(mytree.remove(keyTwo)); + BOOST_CHECK(mytree.remove(keyThree)); + BOOST_CHECK(mytree.remove(E::SignedMax())); + BOOST_CHECK(mytree.remove(E::SignedMin())); + BOOST_CHECK(mytree.remove(E::MinusOne())); + BOOST_CHECK(mytree.remove(E::MinusTwo())); + + BOOST_CHECK_EQUAL(mytree.get(keyZero), NULLPTR(E)); + BOOST_CHECK_EQUAL(mytree.get(keyOne), NULLPTR(E)); + BOOST_CHECK_EQUAL(mytree.get(keyTwo), NULLPTR(E)); + BOOST_CHECK_EQUAL(mytree.get(keyThree), NULLPTR(E)); + BOOST_CHECK_EQUAL(mytree.get(E::SignedMax()), NULLPTR(E)); + BOOST_CHECK_EQUAL(mytree.get(E::SignedMin()), NULLPTR(E)); + BOOST_CHECK_EQUAL(mytree.get(E::MinusOne()), NULLPTR(E)); + BOOST_CHECK_EQUAL(mytree.get(E::MinusTwo()), NULLPTR(E)); } BOOST_AUTO_TEST_CASE(remove_test) { - testRemove(); - testRemove(); - testRemove(); - testRemove(); + testRemove>(); + testRemove>(); + testRemove>(); + testRemove>(); + + testRemove(); } BOOST_AUTO_TEST_CASE(const_element_test) { - using C = const TestElement; + using C = const TestElementInt; RadixTree mytree; BOOST_CHECK(mytree.insert(RCUPtr::make(0))); @@ -278,7 +315,7 @@ BOOST_CHECK(!mytree.remove(3)); } -void CheckConstTree(const RadixTree> &mytree, +void CheckConstTree(const RadixTree> &mytree, bool expected) { BOOST_CHECK_EQUAL(!!mytree.get(0), expected); BOOST_CHECK_EQUAL(!!mytree.get(1), expected); @@ -287,7 +324,7 @@ } BOOST_AUTO_TEST_CASE(const_tree_test) { - using E = TestElement; + using E = TestElementInt; RadixTree mytree; CheckConstTree(mytree, false); @@ -308,7 +345,7 @@ } BOOST_AUTO_TEST_CASE(test_cow) { - using E = TestElement; + using E = TestElementInt; RadixTree mytree; @@ -359,7 +396,7 @@ } BOOST_AUTO_TEST_CASE(test_move) { - using E = TestElement; + using E = TestElementInt; RadixTree mytree; @@ -385,7 +422,7 @@ #define ELEMENTS 65536 BOOST_AUTO_TEST_CASE(insert_stress_test) { - using E = TestElement; + using E = TestElementInt; RadixTree mytree; std::atomic success{0}; @@ -475,4 +512,72 @@ BOOST_CHECK_EQUAL(count, ELEMENTS); } +BOOST_AUTO_TEST_CASE(uint256_key_wrapper) { + Uint256KeyWrapper key = uint256S( + "AA00000000000000000000000000000000000000000000000000000000000000"); + + auto checkEqual = [&](const Uint256KeyWrapper &val, + const uint256 &expected) { + BOOST_CHECK_EQUAL(ArithToUint256(val.base), expected); + }; + + auto checkOperands = [&](const Uint256KeyWrapper &val, + const uint256 &expected_uint256, + const size_t expected_size_t) { + checkEqual(val, expected_uint256); + + checkEqual(val & Uint256KeyWrapper(uint256::ZERO), uint256::ZERO); + checkEqual(val & val, expected_uint256); + checkEqual(val & TestElementUint256::MinusOne(), expected_uint256); + + BOOST_CHECK_EQUAL(size_t(val), expected_size_t); + }; + + // clang-format off + checkOperands(key >> 0u, uint256S("AA00000000000000000000000000000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 1u, uint256S("5500000000000000000000000000000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 2u, uint256S("2A80000000000000000000000000000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 3u, uint256S("1540000000000000000000000000000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 4u, uint256S("0AA0000000000000000000000000000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 8u, uint256S("00AA000000000000000000000000000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 16u, uint256S("0000AA0000000000000000000000000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 24u, uint256S("000000AA00000000000000000000000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 32u, uint256S("00000000AA000000000000000000000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 40u, uint256S("0000000000AA0000000000000000000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 48u, uint256S("000000000000AA00000000000000000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 56u, uint256S("00000000000000AA000000000000000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 64u, uint256S("0000000000000000AA0000000000000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 72u, uint256S("000000000000000000AA00000000000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 80u, uint256S("00000000000000000000AA000000000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 88u, uint256S("0000000000000000000000AA0000000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 96u, uint256S("000000000000000000000000AA00000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 104u, uint256S("00000000000000000000000000AA000000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 112u, uint256S("0000000000000000000000000000AA0000000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 120u, uint256S("000000000000000000000000000000AA00000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 128u, uint256S("00000000000000000000000000000000AA000000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 136u, uint256S("0000000000000000000000000000000000AA0000000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 144u, uint256S("000000000000000000000000000000000000AA00000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 152u, uint256S("00000000000000000000000000000000000000AA000000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 160u, uint256S("0000000000000000000000000000000000000000AA0000000000000000000000"), 0x0000000000000000); + checkOperands(key >> 168u, uint256S("000000000000000000000000000000000000000000AA00000000000000000000"), 0x0000000000000000); + checkOperands(key >> 176u, uint256S("00000000000000000000000000000000000000000000AA000000000000000000"), 0x0000000000000000); + checkOperands(key >> 184u, uint256S("0000000000000000000000000000000000000000000000AA0000000000000000"), 0x0000000000000000); + checkOperands(key >> 185u, uint256S("0000000000000000000000000000000000000000000000550000000000000000"), 0x0000000000000000); + checkOperands(key >> 186u, uint256S("00000000000000000000000000000000000000000000002A8000000000000000"), 0x8000000000000000); + checkOperands(key >> 192u, uint256S("000000000000000000000000000000000000000000000000AA00000000000000"), 0xAA00000000000000); + checkOperands(key >> 200u, uint256S("00000000000000000000000000000000000000000000000000AA000000000000"), 0x00AA000000000000); + checkOperands(key >> 208u, uint256S("0000000000000000000000000000000000000000000000000000AA0000000000"), 0x0000AA0000000000); + checkOperands(key >> 216u, uint256S("000000000000000000000000000000000000000000000000000000AA00000000"), 0x000000AA00000000); + checkOperands(key >> 224u, uint256S("00000000000000000000000000000000000000000000000000000000AA000000"), 0x00000000AA000000); + checkOperands(key >> 232u, uint256S("0000000000000000000000000000000000000000000000000000000000AA0000"), 0x0000000000AA0000); + checkOperands(key >> 240u, uint256S("000000000000000000000000000000000000000000000000000000000000AA00"), 0x000000000000AA00); + checkOperands(key >> 248u, uint256S("00000000000000000000000000000000000000000000000000000000000000AA"), 0x00000000000000AA); + checkOperands(key >> 252u, uint256S("000000000000000000000000000000000000000000000000000000000000000A"), 0x000000000000000A); + checkOperands(key >> 253u, uint256S("0000000000000000000000000000000000000000000000000000000000000005"), 0x0000000000000005); + checkOperands(key >> 254u, uint256S("0000000000000000000000000000000000000000000000000000000000000002"), 0x0000000000000002); + checkOperands(key >> 255u, uint256S("0000000000000000000000000000000000000000000000000000000000000001"), 0x0000000000000001); + checkOperands(key >> 256u, uint256S("0000000000000000000000000000000000000000000000000000000000000000"), 0x0000000000000000); + // clang-format on +} + BOOST_AUTO_TEST_SUITE_END()