Inside Bitcoin

1// Copyright (c) 2015-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 <prevector.h>
6#include <serialize.h>
7#include <streams.h>
8#include <test/util/random.h>
9#include <test/util/setup_common.h>
10
11#include <boost/test/unit_test.hpp>
12
13#include <ranges>
14#include <vector>
15
16BOOST_FIXTURE_TEST_SUITE(prevector_tests, BasicTestingSetup)
17
18template <unsigned int N, typename T>
19class prevector_tester
20{
21    typedef std::vector<T> realtype;
22    realtype real_vector;
23    realtype real_vector_alt;
24
25    typedef prevector<N, T> pretype;
26    pretype pre_vector;
27    pretype pre_vector_alt;
28
29    typedef typename pretype::size_type Size;
30    bool passed = true;
31    uint256 rand_seed;
32
33
34    template <typename A, typename B>
35    void local_check_equal(A a, B b)
36    {
37        local_check(a == b);
38    }
39    void local_check(bool b)
40    {
41        passed &= b;
42    }
43    void test()
44    {
45        const pretype& const_pre_vector = pre_vector;
46        local_check_equal(real_vector.size(), pre_vector.size());
47        local_check_equal(real_vector.empty(), pre_vector.empty());
48        for (Size s = 0; s < real_vector.size(); s++) {
49            local_check(real_vector[s] == pre_vector[s]);
50            local_check(&(pre_vector[s]) == &(pre_vector.begin()[s]));
51            local_check(&(pre_vector[s]) == &*(pre_vector.begin() + s));
52            local_check(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size()));
53        }
54        // local_check(realtype(pre_vector) == real_vector);
55        local_check(pretype(real_vector.begin(), real_vector.end()) == pre_vector);
56        local_check(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector);
57        size_t pos = 0;
58        for (const T& v : pre_vector) {
59            local_check(v == real_vector[pos++]);
60        }
61        for (const T& v : pre_vector | std::views::reverse) {
62            local_check(v == real_vector[--pos]);
63        }
64        for (const T& v : const_pre_vector) {
65            local_check(v == real_vector[pos++]);
66        }
67        for (const T& v : const_pre_vector | std::views::reverse) {
68            local_check(v == real_vector[--pos]);
69        }
70        DataStream ss1{};
71        DataStream ss2{};
72        ss1 << real_vector;
73        ss2 << pre_vector;
74        local_check_equal(ss1.size(), ss2.size());
75        for (Size s = 0; s < ss1.size(); s++) {
76            local_check_equal(ss1[s], ss2[s]);
77        }
78    }
79
80public:
81    void resize(Size s)
82    {
83        real_vector.resize(s);
84        local_check_equal(real_vector.size(), s);
85        pre_vector.resize(s);
86        local_check_equal(pre_vector.size(), s);
87        test();
88    }
89
90    void reserve(Size s)
91    {
92        real_vector.reserve(s);
93        local_check(real_vector.capacity() >= s);
94        pre_vector.reserve(s);
95        local_check(pre_vector.capacity() >= s);
96        test();
97    }
98
99    void insert(Size position, const T& value)
100    {
101        real_vector.insert(real_vector.begin() + position, value);
102        pre_vector.insert(pre_vector.begin() + position, value);
103        test();
104    }
105
106    void insert(Size position, Size count, const T& value)
107    {
108        real_vector.insert(real_vector.begin() + position, count, value);
109        pre_vector.insert(pre_vector.begin() + position, count, value);
110        test();
111    }
112
113    template <typename I>
114    void insert_range(Size position, I first, I last)
115    {
116        real_vector.insert(real_vector.begin() + position, first, last);
117        pre_vector.insert(pre_vector.begin() + position, first, last);
118        test();
119    }
120
121    void erase(Size position)
122    {
123        real_vector.erase(real_vector.begin() + position);
124        pre_vector.erase(pre_vector.begin() + position);
125        test();
126    }
127
128    void erase(Size first, Size last)
129    {
130        real_vector.erase(real_vector.begin() + first, real_vector.begin() + last);
131        pre_vector.erase(pre_vector.begin() + first, pre_vector.begin() + last);
132        test();
133    }
134
135    void update(Size pos, const T& value)
136    {
137        real_vector[pos] = value;
138        pre_vector[pos] = value;
139        test();
140    }
141
142    void push_back(const T& value)
143    {
144        real_vector.push_back(value);
145        pre_vector.push_back(value);
146        test();
147    }
148
149    void pop_back()
150    {
151        real_vector.pop_back();
152        pre_vector.pop_back();
153        test();
154    }
155
156    void clear()
157    {
158        real_vector.clear();
159        pre_vector.clear();
160    }
161
162    void assign(Size n, const T& value)
163    {
164        real_vector.assign(n, value);
165        pre_vector.assign(n, value);
166    }
167
168    Size size() const
169    {
170        return real_vector.size();
171    }
172
173    Size capacity() const
174    {
175        return pre_vector.capacity();
176    }
177
178    void shrink_to_fit()
179    {
180        pre_vector.shrink_to_fit();
181        test();
182    }
183
184    void swap() noexcept
185    {
186        real_vector.swap(real_vector_alt);
187        pre_vector.swap(pre_vector_alt);
188        test();
189    }
190
191    void move()
192    {
193        real_vector = std::move(real_vector_alt);
194        real_vector_alt.clear();
195        pre_vector = std::move(pre_vector_alt);
196        pre_vector_alt.clear();
197    }
198
199    void copy()
200    {
201        real_vector = real_vector_alt;
202        pre_vector = pre_vector_alt;
203    }
204
205    void resize_uninitialized(realtype values)
206    {
207        size_t r = values.size();
208        size_t s = real_vector.size() / 2;
209        if (real_vector.capacity() < s + r) {
210            real_vector.reserve(s + r);
211        }
212        real_vector.resize(s);
213        pre_vector.resize_uninitialized(s);
214        for (auto v : values) {
215            real_vector.push_back(v);
216        }
217        auto p = pre_vector.size();
218        pre_vector.resize_uninitialized(p + r);
219        for (auto v : values) {
220            pre_vector[p] = v;
221            ++p;
222        }
223        test();
224    }
225
226    ~prevector_tester()
227    {
228        BOOST_CHECK_MESSAGE(passed, "insecure_rand: " + rand_seed.ToString());
229    }
230
231    prevector_tester(FastRandomContext& rng)
232    {
233        rand_seed = rng.rand256();
234        rng.Reseed(rand_seed);
235    }
236};
237
238BOOST_AUTO_TEST_CASE(PrevectorTestInt)
239{
240    for (int j = 0; j < 64; j++) {
241        prevector_tester<8, int> test{m_rng};
242        for (int i = 0; i < 2048; i++) {
243            if (m_rng.randbits(2) == 0) {
244                test.insert(m_rng.randrange(test.size() + 1), int(m_rng.rand32()));
245            }
246            if (test.size() > 0 && m_rng.randbits(2) == 1) {
247                test.erase(m_rng.randrange(test.size()));
248            }
249            if (m_rng.randbits(3) == 2) {
250                int new_size = std::max(0, std::min(30, (int)test.size() + (int)m_rng.randrange(5) - 2));