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