coinscachepair_tests.cpp
1 // Copyright (c) 2024-present The Bitcoin Core developers 2 // Distributed under the MIT software license, see the accompanying 3 // file COPYING or http://www.opensource.org/licenses/mit-license.php. 4 5 #include <coins.h> 6 7 #include <boost/test/unit_test.hpp> 8 9 #include <list> 10 11 BOOST_AUTO_TEST_SUITE(coinscachepair_tests) 12 13 static constexpr auto NUM_NODES{4}; 14 15 std::list<CoinsCachePair> CreatePairs(CoinsCachePair& sentinel) 16 { 17 std::list<CoinsCachePair> nodes; 18 for (auto i{0}; i < NUM_NODES; ++i) { 19 nodes.emplace_back(); 20 21 auto node{std::prev(nodes.end())}; 22 CCoinsCacheEntry::SetDirty(*node, sentinel); 23 24 BOOST_CHECK(node->second.IsDirty() && !node->second.IsFresh()); 25 BOOST_CHECK_EQUAL(node->second.Next(), &sentinel); 26 BOOST_CHECK_EQUAL(sentinel.second.Prev(), &(*node)); 27 28 if (i > 0) { 29 BOOST_CHECK_EQUAL(std::prev(node)->second.Next(), &(*node)); 30 BOOST_CHECK_EQUAL(node->second.Prev(), &(*std::prev(node))); 31 } 32 } 33 return nodes; 34 } 35 36 BOOST_AUTO_TEST_CASE(linked_list_iteration) 37 { 38 CoinsCachePair sentinel; 39 sentinel.second.SelfRef(sentinel); 40 auto nodes{CreatePairs(sentinel)}; 41 42 // Check iterating through pairs is identical to iterating through a list 43 auto node{sentinel.second.Next()}; 44 for (const auto& expected : nodes) { 45 BOOST_CHECK_EQUAL(&expected, node); 46 node = node->second.Next(); 47 } 48 BOOST_CHECK_EQUAL(node, &sentinel); 49 50 // Check iterating through pairs is identical to iterating through a list 51 // Clear the state during iteration 52 node = sentinel.second.Next(); 53 for (const auto& expected : nodes) { 54 BOOST_CHECK_EQUAL(&expected, node); 55 auto next = node->second.Next(); 56 node->second.SetClean(); 57 node = next; 58 } 59 BOOST_CHECK_EQUAL(node, &sentinel); 60 // Check that sentinel's next and prev are itself 61 BOOST_CHECK_EQUAL(sentinel.second.Next(), &sentinel); 62 BOOST_CHECK_EQUAL(sentinel.second.Prev(), &sentinel); 63 64 // Delete the nodes from the list to make sure there are no dangling pointers 65 for (auto it{nodes.begin()}; it != nodes.end(); it = nodes.erase(it)) { 66 BOOST_CHECK(!it->second.IsDirty() && !it->second.IsFresh()); 67 } 68 } 69 70 BOOST_AUTO_TEST_CASE(linked_list_iterate_erase) 71 { 72 CoinsCachePair sentinel; 73 sentinel.second.SelfRef(sentinel); 74 auto nodes{CreatePairs(sentinel)}; 75 76 // Check iterating through pairs is identical to iterating through a list 77 // Erase the nodes as we iterate through, but don't clear state 78 // The state will be cleared by the CCoinsCacheEntry's destructor 79 auto node{sentinel.second.Next()}; 80 for (auto expected{nodes.begin()}; expected != nodes.end(); expected = nodes.erase(expected)) { 81 BOOST_CHECK_EQUAL(&(*expected), node); 82 node = node->second.Next(); 83 } 84 BOOST_CHECK_EQUAL(node, &sentinel); 85 86 // Check that sentinel's next and prev are itself 87 BOOST_CHECK_EQUAL(sentinel.second.Next(), &sentinel); 88 BOOST_CHECK_EQUAL(sentinel.second.Prev(), &sentinel); 89 } 90 91 BOOST_AUTO_TEST_CASE(linked_list_random_deletion) 92 { 93 CoinsCachePair sentinel; 94 sentinel.second.SelfRef(sentinel); 95 auto nodes{CreatePairs(sentinel)}; 96 97 // Create linked list sentinel->n1->n2->n3->n4->sentinel 98 auto n1{nodes.begin()}; 99 auto n2{std::next(n1)}; 100 auto n3{std::next(n2)}; 101 auto n4{std::next(n3)}; 102 103 // Delete n2 104 // sentinel->n1->n3->n4->sentinel 105 nodes.erase(n2); 106 // Check that n1 now points to n3, and n3 still points to n4 107 // Also check that state was not altered 108 BOOST_CHECK(n1->second.IsDirty() && !n1->second.IsFresh()); 109 BOOST_CHECK_EQUAL(n1->second.Next(), &(*n3)); 110 BOOST_CHECK(n3->second.IsDirty() && !n3->second.IsFresh()); 111 BOOST_CHECK_EQUAL(n3->second.Next(), &(*n4)); 112 BOOST_CHECK_EQUAL(n3->second.Prev(), &(*n1)); 113 114 // Delete n1 115 // sentinel->n3->n4->sentinel 116 nodes.erase(n1); 117 // Check that sentinel now points to n3, and n3 still points to n4 118 // Also check that state was not altered 119 BOOST_CHECK(n3->second.IsDirty() && !n3->second.IsFresh()); 120 BOOST_CHECK_EQUAL(sentinel.second.Next(), &(*n3)); 121 BOOST_CHECK_EQUAL(n3->second.Next(), &(*n4)); 122 BOOST_CHECK_EQUAL(n3->second.Prev(), &sentinel); 123 124 // Delete n4 125 // sentinel->n3->sentinel 126 nodes.erase(n4); 127 // Check that sentinel still points to n3, and n3 points to sentinel 128 // Also check that state was not altered 129 BOOST_CHECK(n3->second.IsDirty() && !n3->second.IsFresh()); 130 BOOST_CHECK_EQUAL(sentinel.second.Next(), &(*n3)); 131 BOOST_CHECK_EQUAL(n3->second.Next(), &sentinel); 132 BOOST_CHECK_EQUAL(sentinel.second.Prev(), &(*n3)); 133 134 // Delete n3 135 // sentinel->sentinel 136 nodes.erase(n3); 137 // Check that sentinel's next and prev are itself 138 BOOST_CHECK_EQUAL(sentinel.second.Next(), &sentinel); 139 BOOST_CHECK_EQUAL(sentinel.second.Prev(), &sentinel); 140 } 141 142 BOOST_AUTO_TEST_CASE(linked_list_set_state) 143 { 144 CoinsCachePair sentinel; 145 sentinel.second.SelfRef(sentinel); 146 CoinsCachePair n1; 147 CoinsCachePair n2; 148 149 // Check that setting DIRTY inserts it into linked list and sets state 150 CCoinsCacheEntry::SetDirty(n1, sentinel); 151 BOOST_CHECK(n1.second.IsDirty() && !n1.second.IsFresh()); 152 BOOST_CHECK_EQUAL(n1.second.Next(), &sentinel); 153 BOOST_CHECK_EQUAL(n1.second.Prev(), &sentinel); 154 BOOST_CHECK_EQUAL(sentinel.second.Next(), &n1); 155 BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n1); 156 157 // Check that setting FRESH on new node inserts it after n1 158 CCoinsCacheEntry::SetFresh(n2, sentinel); 159 BOOST_CHECK(n2.second.IsFresh() && !n2.second.IsDirty()); 160 BOOST_CHECK_EQUAL(n2.second.Next(), &sentinel); 161 BOOST_CHECK_EQUAL(n2.second.Prev(), &n1); 162 BOOST_CHECK_EQUAL(n1.second.Next(), &n2); 163 BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n2); 164 165 // Check that we can set extra state, but they don't change our position 166 CCoinsCacheEntry::SetFresh(n1, sentinel); 167 BOOST_CHECK(n1.second.IsDirty() && n1.second.IsFresh()); 168 BOOST_CHECK_EQUAL(n1.second.Next(), &n2); 169 BOOST_CHECK_EQUAL(n1.second.Prev(), &sentinel); 170 BOOST_CHECK_EQUAL(sentinel.second.Next(), &n1); 171 BOOST_CHECK_EQUAL(n2.second.Prev(), &n1); 172 173 // Check that we can clear state then re-set it 174 n1.second.SetClean(); 175 BOOST_CHECK(!n1.second.IsDirty() && !n1.second.IsFresh()); 176 BOOST_CHECK_EQUAL(sentinel.second.Next(), &n2); 177 BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n2); 178 BOOST_CHECK_EQUAL(n2.second.Next(), &sentinel); 179 BOOST_CHECK_EQUAL(n2.second.Prev(), &sentinel); 180 181 // Calling `SetClean` a second time has no effect 182 n1.second.SetClean(); 183 BOOST_CHECK(!n1.second.IsDirty() && !n1.second.IsFresh()); 184 BOOST_CHECK_EQUAL(sentinel.second.Next(), &n2); 185 BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n2); 186 BOOST_CHECK_EQUAL(n2.second.Next(), &sentinel); 187 BOOST_CHECK_EQUAL(n2.second.Prev(), &sentinel); 188 189 // Adding DIRTY re-inserts it after n2 190 CCoinsCacheEntry::SetDirty(n1, sentinel); 191 BOOST_CHECK(n1.second.IsDirty() && !n1.second.IsFresh()); 192 BOOST_CHECK_EQUAL(n2.second.Next(), &n1); 193 BOOST_CHECK_EQUAL(n1.second.Prev(), &n2); 194 BOOST_CHECK_EQUAL(n1.second.Next(), &sentinel); 195 BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n1); 196 } 197 198 BOOST_AUTO_TEST_SUITE_END()