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