Branch data Line data Source code
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 : 3 : std::list<CoinsCachePair> CreatePairs(CoinsCachePair& sentinel)
16 : : {
17 : 3 : std::list<CoinsCachePair> nodes;
18 [ + + ]: 15 : for (auto i{0}; i < NUM_NODES; ++i) {
19 [ + - ]: 12 : nodes.emplace_back();
20 : :
21 : 12 : auto node{std::prev(nodes.end())};
22 : 12 : node->second.AddFlags(CCoinsCacheEntry::DIRTY, *node, sentinel);
23 : :
24 [ + - + - ]: 12 : BOOST_CHECK_EQUAL(node->second.GetFlags(), CCoinsCacheEntry::DIRTY);
25 [ + - + - ]: 12 : BOOST_CHECK_EQUAL(node->second.Next(), &sentinel);
26 [ + - + - ]: 12 : BOOST_CHECK_EQUAL(sentinel.second.Prev(), &(*node));
27 : :
28 [ + + ]: 12 : if (i > 0) {
29 [ + - + - ]: 9 : BOOST_CHECK_EQUAL(std::prev(node)->second.Next(), &(*node));
30 [ + - + - ]: 9 : BOOST_CHECK_EQUAL(node->second.Prev(), &(*std::prev(node)));
31 : : }
32 : : }
33 : 3 : return nodes;
34 : 0 : }
35 : :
36 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(linked_list_iteration)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
37 : : {
38 : 1 : CoinsCachePair sentinel;
39 : 1 : sentinel.second.SelfRef(sentinel);
40 [ + - ]: 1 : auto nodes{CreatePairs(sentinel)};
41 : :
42 : : // Check iterating through pairs is identical to iterating through a list
43 : 1 : auto node{sentinel.second.Next()};
44 [ + + ]: 5 : for (const auto& expected : nodes) {
45 [ + - + - ]: 4 : BOOST_CHECK_EQUAL(&expected, node);
46 : 4 : node = node->second.Next();
47 : : }
48 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(node, &sentinel);
49 : :
50 : : // Check iterating through pairs is identical to iterating through a list
51 : : // Clear the flags during iteration
52 : 1 : node = sentinel.second.Next();
53 [ + + ]: 5 : for (const auto& expected : nodes) {
54 [ + - + - ]: 4 : BOOST_CHECK_EQUAL(&expected, node);
55 : 4 : auto next = node->second.Next();
56 [ + - ]: 4 : node->second.ClearFlags();
57 : 4 : node = next;
58 : : }
59 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(node, &sentinel);
60 : : // Check that sentinel's next and prev are itself
61 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Next(), &sentinel);
62 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Prev(), &sentinel);
63 : :
64 : : // Delete the nodes from the list to make sure there are no dangling pointers
65 [ + + ]: 5 : for (auto it{nodes.begin()}; it != nodes.end(); it = nodes.erase(it)) {
66 [ + - + - ]: 4 : BOOST_CHECK_EQUAL(it->second.GetFlags(), 0);
67 : : }
68 : 1 : }
69 : :
70 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(linked_list_iterate_erase)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
71 : : {
72 : 1 : CoinsCachePair sentinel;
73 : 1 : sentinel.second.SelfRef(sentinel);
74 [ + - ]: 1 : 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 flags
78 : : // The flags will be cleared by the CCoinsCacheEntry's destructor
79 : 1 : auto node{sentinel.second.Next()};
80 [ + + ]: 5 : for (auto expected{nodes.begin()}; expected != nodes.end(); expected = nodes.erase(expected)) {
81 [ + - + - ]: 4 : BOOST_CHECK_EQUAL(&(*expected), node);
82 : 4 : node = node->second.Next();
83 : : }
84 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(node, &sentinel);
85 : :
86 : : // Check that sentinel's next and prev are itself
87 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Next(), &sentinel);
88 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Prev(), &sentinel);
89 : 1 : }
90 : :
91 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(linked_list_random_deletion)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
92 : : {
93 : 1 : CoinsCachePair sentinel;
94 : 1 : sentinel.second.SelfRef(sentinel);
95 [ + - ]: 1 : auto nodes{CreatePairs(sentinel)};
96 : :
97 : : // Create linked list sentinel->n1->n2->n3->n4->sentinel
98 : 1 : auto n1{nodes.begin()};
99 : 1 : auto n2{std::next(n1)};
100 : 1 : auto n3{std::next(n2)};
101 : 1 : auto n4{std::next(n3)};
102 : :
103 : : // Delete n2
104 : : // sentinel->n1->n3->n4->sentinel
105 : 1 : nodes.erase(n2);
106 : : // Check that n1 now points to n3, and n3 still points to n4
107 : : // Also check that flags were not altered
108 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1->second.GetFlags(), CCoinsCacheEntry::DIRTY);
109 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1->second.Next(), &(*n3));
110 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n3->second.GetFlags(), CCoinsCacheEntry::DIRTY);
111 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n3->second.Next(), &(*n4));
112 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n3->second.Prev(), &(*n1));
113 : :
114 : : // Delete n1
115 : : // sentinel->n3->n4->sentinel
116 : 1 : nodes.erase(n1);
117 : : // Check that sentinel now points to n3, and n3 still points to n4
118 : : // Also check that flags were not altered
119 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n3->second.GetFlags(), CCoinsCacheEntry::DIRTY);
120 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Next(), &(*n3));
121 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n3->second.Next(), &(*n4));
122 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n3->second.Prev(), &sentinel);
123 : :
124 : : // Delete n4
125 : : // sentinel->n3->sentinel
126 : 1 : nodes.erase(n4);
127 : : // Check that sentinel still points to n3, and n3 points to sentinel
128 : : // Also check that flags were not altered
129 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n3->second.GetFlags(), CCoinsCacheEntry::DIRTY);
130 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Next(), &(*n3));
131 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n3->second.Next(), &sentinel);
132 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Prev(), &(*n3));
133 : :
134 : : // Delete n3
135 : : // sentinel->sentinel
136 : 1 : nodes.erase(n3);
137 : : // Check that sentinel's next and prev are itself
138 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Next(), &sentinel);
139 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Prev(), &sentinel);
140 : 1 : }
141 : :
142 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(linked_list_add_flags)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
143 : : {
144 : 1 : CoinsCachePair sentinel;
145 : 1 : sentinel.second.SelfRef(sentinel);
146 : 1 : CoinsCachePair n1;
147 : 1 : CoinsCachePair n2;
148 : :
149 : : // Check that adding 0 flag has no effect
150 : 1 : n1.second.AddFlags(0, n1, sentinel);
151 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.GetFlags(), 0);
152 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Next(), &sentinel);
153 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Prev(), &sentinel);
154 : :
155 : : // Check that adding DIRTY flag inserts it into linked list and sets flags
156 : 1 : n1.second.AddFlags(CCoinsCacheEntry::DIRTY, n1, sentinel);
157 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.GetFlags(), CCoinsCacheEntry::DIRTY);
158 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.Next(), &sentinel);
159 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.Prev(), &sentinel);
160 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Next(), &n1);
161 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n1);
162 : :
163 : : // Check that adding FRESH flag on new node inserts it after n1
164 : 1 : n2.second.AddFlags(CCoinsCacheEntry::FRESH, n2, sentinel);
165 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.GetFlags(), CCoinsCacheEntry::FRESH);
166 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Next(), &sentinel);
167 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Prev(), &n1);
168 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.Next(), &n2);
169 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n2);
170 : :
171 : : // Check that adding 0 flag has no effect, and doesn't change position
172 : 1 : n1.second.AddFlags(0, n1, sentinel);
173 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.GetFlags(), CCoinsCacheEntry::DIRTY);
174 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.Next(), &n2);
175 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.Prev(), &sentinel);
176 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Next(), &n1);
177 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Prev(), &n1);
178 : :
179 : : // Check that we can add extra flags, but they don't change our position
180 : 1 : n1.second.AddFlags(CCoinsCacheEntry::FRESH, n1, sentinel);
181 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.GetFlags(), CCoinsCacheEntry::DIRTY | CCoinsCacheEntry::FRESH);
182 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.Next(), &n2);
183 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.Prev(), &sentinel);
184 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Next(), &n1);
185 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Prev(), &n1);
186 : :
187 : : // Check that we can clear flags then re-add them
188 [ + - ]: 1 : n1.second.ClearFlags();
189 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.GetFlags(), 0);
190 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Next(), &n2);
191 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n2);
192 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Next(), &sentinel);
193 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Prev(), &sentinel);
194 : :
195 : : // Check that calling `ClearFlags` with 0 flags has no effect
196 [ - + ]: 1 : n1.second.ClearFlags();
197 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.GetFlags(), 0);
198 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Next(), &n2);
199 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n2);
200 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Next(), &sentinel);
201 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Prev(), &sentinel);
202 : :
203 : : // Adding 0 still has no effect
204 : 1 : n1.second.AddFlags(0, n1, sentinel);
205 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Next(), &n2);
206 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n2);
207 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Next(), &sentinel);
208 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Prev(), &sentinel);
209 : :
210 : : // But adding DIRTY re-inserts it after n2
211 : 1 : n1.second.AddFlags(CCoinsCacheEntry::DIRTY, n1, sentinel);
212 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.GetFlags(), CCoinsCacheEntry::DIRTY);
213 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Next(), &n1);
214 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.Prev(), &n2);
215 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.Next(), &sentinel);
216 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n1);
217 : 1 : }
218 : :
219 : : BOOST_AUTO_TEST_SUITE_END()
|
