coinscachepair_tests.cpp raw
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()
199