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() && !node->second.IsFresh());
- + + - +
- ]
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 state 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.SetClean();
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 [ + - + - : 8 : BOOST_CHECK(!it->second.IsDirty() && !it->second.IsFresh());
- + + - ]
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 state
78 : : // The state 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 state was not altered
108 [ + - + - : 2 : BOOST_CHECK(n1->second.IsDirty() && !n1->second.IsFresh());
- + + - +
- ]
109 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1->second.Next(), &(*n3));
110 [ + - + - : 2 : BOOST_CHECK(n3->second.IsDirty() && !n3->second.IsFresh());
- + + - +
- ]
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 state was not altered
119 [ + - + - : 2 : BOOST_CHECK(n3->second.IsDirty() && !n3->second.IsFresh());
- + + - +
- ]
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 state was not altered
129 [ + - + - : 2 : BOOST_CHECK(n3->second.IsDirty() && !n3->second.IsFresh());
- + + - +
- ]
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_set_state)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
143 : : {
144 : 1 : CoinsCachePair sentinel;
145 : 1 : sentinel.second.SelfRef(sentinel);
146 : 1 : CoinsCachePair n1;
147 : 1 : CoinsCachePair n2;
148 : :
149 : : // Check that setting DIRTY inserts it into linked list and sets state
150 [ + - ]: 1 : CCoinsCacheEntry::SetDirty(n1, sentinel);
151 [ + - + - : 2 : BOOST_CHECK(n1.second.IsDirty() && !n1.second.IsFresh());
- + + - +
- ]
152 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.Next(), &sentinel);
153 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.Prev(), &sentinel);
154 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Next(), &n1);
155 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n1);
156 : :
157 : : // Check that setting FRESH on new node inserts it after n1
158 [ + - ]: 1 : CCoinsCacheEntry::SetFresh(n2, sentinel);
159 [ + - + - : 2 : BOOST_CHECK(n2.second.IsFresh() && !n2.second.IsDirty());
- + + - +
- ]
160 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Next(), &sentinel);
161 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Prev(), &n1);
162 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.Next(), &n2);
163 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n2);
164 : :
165 : : // Check that we can set extra state, but they don't change our position
166 [ - + ]: 1 : CCoinsCacheEntry::SetFresh(n1, sentinel);
167 [ + - + - : 2 : BOOST_CHECK(n1.second.IsDirty() && n1.second.IsFresh());
- + + - +
- ]
168 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.Next(), &n2);
169 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.Prev(), &sentinel);
170 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Next(), &n1);
171 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Prev(), &n1);
172 : :
173 : : // Check that we can clear state then re-set it
174 [ + - ]: 1 : n1.second.SetClean();
175 [ + - + - : 2 : BOOST_CHECK(!n1.second.IsDirty() && !n1.second.IsFresh());
- + + - +
- ]
176 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Next(), &n2);
177 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n2);
178 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Next(), &sentinel);
179 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Prev(), &sentinel);
180 : :
181 : : // Calling `SetClean` a second time has no effect
182 [ - + ]: 1 : n1.second.SetClean();
183 [ + - + - : 2 : BOOST_CHECK(!n1.second.IsDirty() && !n1.second.IsFresh());
- + + - +
- ]
184 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Next(), &n2);
185 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n2);
186 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Next(), &sentinel);
187 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Prev(), &sentinel);
188 : :
189 : : // Adding DIRTY re-inserts it after n2
190 [ + - ]: 1 : CCoinsCacheEntry::SetDirty(n1, sentinel);
191 [ + - + - : 2 : BOOST_CHECK(n1.second.IsDirty() && !n1.second.IsFresh());
- + + - +
- ]
192 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n2.second.Next(), &n1);
193 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.Prev(), &n2);
194 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(n1.second.Next(), &sentinel);
195 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n1);
196 : 1 : }
197 : :
198 : : BOOST_AUTO_TEST_SUITE_END()
|
