OXYGENHUB
◆ main openmsx / src / unittest / circular_buffer_test.cc
5.5 KiB · C++ · last changed chore(): initial commit 1 month ago source blame history raw
1 
#include "catch.hpp"
2 
#include "circular_buffer.hh"
3
4 
#include "xrange.hh"
5
6 
#include <array>
7 
#include <memory>
8 
#include <span>
9 
#include <vector>
10
11 
using namespace std;
12
13 
static void check_buf(
14 
	const circular_buffer<int>& buf,
15 
	size_t expectedCapacity, const vector<int>& expectedElements)
16 
{
17 
	auto expectedSize = expectedElements.size();
18 
	REQUIRE(buf.size() == expectedSize);
19 
	CHECK(buf.capacity() == expectedCapacity);
20 
	CHECK(buf.reserve() == expectedCapacity - expectedSize);
21 
	CHECK(buf.empty() == (expectedSize == 0));
22 
	CHECK(buf.full()  == (expectedCapacity == expectedSize));
23
24 
	auto iter_diff = buf.end() - buf.begin();
25 
	CHECK(ptrdiff_t(buf.size()) == iter_diff);
26
27 
	if (expectedSize != 0) {
28 
		CHECK(buf.front() == expectedElements.front());
29 
		CHECK(buf.back()  == expectedElements.back());
30 
	}
31
32 
	for (auto i : xrange(expectedSize)) {
33 
		CHECK(buf[i] == expectedElements[i]);
34 
	}
35
36 
	auto it1 = expectedElements.begin();
37 
	for (auto& i : buf) {
38 
		CHECK(i == *it1++);
39 
	}
40
41 
	auto rit = expectedElements.rbegin();
42 
	for (auto it = buf.rbegin(); it != buf.rend(); ++it) {
43 
		CHECK(*it == *rit++);
44 
	}
45 
}
46 
TEST_CASE("circular_buffer") {
47 
	circular_buffer<int> buf1;    check_buf(buf1, 0, {});
48 
	buf1.set_capacity(3);         check_buf(buf1, 3, {});
49 
	buf1.push_back(1);            check_buf(buf1, 3, {1});
50 
	buf1.push_back(2);            check_buf(buf1, 3, {1,2});
51 
	buf1.push_front(3);           check_buf(buf1, 3, {3,1,2});
52 
	buf1.pop_front();             check_buf(buf1, 3, {1,2});
53 
	buf1.pop_back();              check_buf(buf1, 3, {1});
54 
	buf1.clear();                 check_buf(buf1, 3, {});
55
56 
	circular_buffer<int> buf2(5); check_buf(buf2, 5, {});
57 
	buf1.push_back({4,5});        check_buf(buf1, 3, {4,5});
58 
	buf2.push_back({7,8,9});      check_buf(buf2, 5, {7,8,9});
59
60 
	swap(buf1, buf2);             check_buf(buf1, 5, {7,8,9});
61 
	                              check_buf(buf2, 3, {4,5});
62 
}
63
64 
static void check_buf(
65 
	const circular_buffer<unique_ptr<int>>& buf,
66 
	size_t expectedCapacity, const vector<int>& expectedElements)
67 
{
68 
	auto expectedSize = expectedElements.size();
69 
	REQUIRE(buf.size() == expectedSize);
70 
	CHECK(buf.capacity() == expectedCapacity);
71 
	CHECK(buf.reserve() == expectedCapacity - expectedSize);
72 
	CHECK(buf.empty() == (expectedSize == 0));
73 
	CHECK(buf.full()  == (expectedCapacity == expectedSize));
74
75 
	auto iter_diff = buf.end() - buf.begin();
76 
	CHECK(ptrdiff_t(buf.size()) == iter_diff);
77
78 
	if (expectedSize != 0) {
79 
		CHECK(*buf.front() == expectedElements.front());
80 
		CHECK(*buf.back()  == expectedElements.back());
81 
	}
82
83 
	for (auto i : xrange(expectedSize)) {
84 
		CHECK(*buf[i] == expectedElements[i]);
85 
	}
86
87 
	auto it1 = expectedElements.begin();
88 
	for (auto& i : buf) {
89 
		CHECK(*i == *it1++);
90 
	}
91
92 
	auto rit = expectedElements.rbegin();
93 
	for (auto it = buf.rbegin(); it != buf.rend(); ++it) {
94 
		CHECK(**it == *rit++);
95 
	}
96 
}
97 
TEST_CASE("circular_buffer, move-only") {
98 
	circular_buffer<unique_ptr<int>> buf1; check_buf(buf1, 0, {});
99 
	buf1.set_capacity(3);                  check_buf(buf1, 3, {});
100 
	buf1.push_back (make_unique<int>(1));  check_buf(buf1, 3, {1});
101 
	buf1.push_back (make_unique<int>(2));  check_buf(buf1, 3, {1,2});
102 
	buf1.push_front(make_unique<int>(3));  check_buf(buf1, 3, {3,1,2});
103 
	buf1.pop_front();                      check_buf(buf1, 3, {1,2});
104 
	buf1.pop_back();                       check_buf(buf1, 3, {1});
105 
	buf1.clear();                          check_buf(buf1, 3, {});
106
107 
	// doesn't work, see
108 
	//    http://stackoverflow.com/questions/8193102/initializer-list-and-move-semantics
109 
	//buf1.push_back({make_unique<int>(4),
110 
	//                make_unique<int>(5)}); check_buf(buf1, 3, {4,5});
111 
}
112
113 
static void check_queue(
114 
	const cb_queue<int>& q, int expectedCapacity,
115 
	const vector<int>& expectedElements)
116 
{
117 
	check_buf(q.getBuffer(), expectedCapacity, expectedElements);
118 
}
119 
TEST_CASE("cb_queue") {
120 
	cb_queue<int> q;           check_queue(q, 0, {});
121 
	q.push_back(1);            check_queue(q, 4, {1});
122 
	q.push_back(2);            check_queue(q, 4, {1,2});
123 
	CHECK(q.pop_front() == 1); check_queue(q, 4, {2});
124 
	q.push_back({4,5,6,7});    check_queue(q, 8, {2,4,5,6,7});
125 
	CHECK(q.pop_front() == 2); check_queue(q, 8, {4,5,6,7});
126 
	CHECK(q.pop_front() == 4); check_queue(q, 8, {5,6,7});
127 
	q.clear();                 check_queue(q, 8, {});
128 
}
129
130 
static void check_queue(
131 
	const cb_queue<unique_ptr<int>>& q, int expectedCapacity,
132 
	const vector<int>& expectedElements)
133 
{
134 
	check_buf(q.getBuffer(), expectedCapacity, expectedElements);
135 
}
136 
TEST_CASE("cb_queue, move-only") {
137 
	cb_queue<unique_ptr<int>> q;      check_queue(q, 0, {});
138 
	q.push_back(make_unique<int>(1)); check_queue(q, 4, {1});
139 
	q.push_back(make_unique<int>(2)); check_queue(q, 4, {1,2});
140 
	CHECK(*q.pop_front() == 1);       check_queue(q, 4, {2});
141 
	q.clear();                        check_queue(q, 4, {});
142 
}
143
144 
TEST_CASE("cb_queue, push_back_range") {
145 
	cb_queue<int> q;                           check_queue(q, 0, {});
146 
	const array<int, 4> a = {1, 2, 3, 4};
147 
	q.push_back_range(a);                      check_queue(q, 4, {1,2,3,4});
148 
	// One growth step for the whole range: size 4 + 6 => need 10 => capacity
149 
	// becomes exactly 10 (repeated push_back would have doubled to 16).
150 
	const array<int, 6> b = {5, 6, 7, 8, 9, 10};
151 
	q.push_back_range(b);                      check_queue(q, 10, {1,2,3,4,5,6,7,8,9,10});
152 
	// An empty range is a no-op.
153 
	q.push_back_range(span<const int>{});      check_queue(q, 10, {1,2,3,4,5,6,7,8,9,10});
154 
	CHECK(q.pop_front() == 1);                 check_queue(q, 10, {2,3,4,5,6,7,8,9,10});
155 
	// Wrap-around + growth: size 9 + 2 => need 11 => capacity 20.
156 
	const vector<int> c = {11, 12};
157 
	q.push_back_range(c);                      check_queue(q, 20, {2,3,4,5,6,7,8,9,10,11,12});
158 
}