jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2022, Lucas Chollet <lucas.chollet@free.fr>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <LibTest/TestCase.h>
8
9#include <AK/CircularBuffer.h>
10
11namespace {
12
13CircularBuffer create_circular_buffer(size_t size)
14{
15 auto buffer_or_error = CircularBuffer::create_empty(size);
16 EXPECT(!buffer_or_error.is_error());
17
18 return buffer_or_error.release_value();
19}
20
21void safe_write(CircularBuffer& buffer, u8 i)
22{
23 Bytes b { &i, 1 };
24 auto written_bytes = buffer.write(b);
25 EXPECT_EQ(written_bytes, 1ul);
26};
27
28void safe_read(CircularBuffer& buffer, u8 supposed_result)
29{
30 u8 read_value {};
31 Bytes b { &read_value, 1 };
32 b = buffer.read(b);
33 EXPECT_EQ(b.size(), 1ul);
34 EXPECT_EQ(*b.data(), supposed_result);
35};
36
37void safe_discard(CircularBuffer& buffer, size_t size)
38{
39 auto result = buffer.discard(size);
40 EXPECT(!result.is_error());
41};
42
43}
44
45TEST_CASE(simple_write_read)
46{
47 auto buffer = create_circular_buffer(1);
48
49 safe_write(buffer, 42);
50 safe_read(buffer, 42);
51}
52
53TEST_CASE(writing_above_limits)
54{
55 auto buffer = create_circular_buffer(1);
56
57 safe_write(buffer, 1);
58
59 u8 value = 42;
60 Bytes b { &value, 1 };
61 auto written_bytes = buffer.write(b);
62 EXPECT_EQ(written_bytes, 0ul);
63}
64
65TEST_CASE(usage_with_wrapping_around)
66{
67 constexpr size_t capacity = 3;
68 auto buffer = create_circular_buffer(capacity);
69
70 for (unsigned i {}; i < capacity; ++i)
71 safe_write(buffer, i + 8);
72
73 EXPECT_EQ(buffer.used_space(), capacity);
74 EXPECT_EQ(buffer.empty_space(), 0ul);
75
76 safe_read(buffer, 0 + 8);
77 safe_read(buffer, 1 + 8);
78
79 EXPECT_EQ(buffer.used_space(), capacity - 2);
80
81 safe_write(buffer, 5);
82 safe_write(buffer, 6);
83
84 EXPECT_EQ(buffer.used_space(), capacity);
85
86 safe_read(buffer, 10);
87 safe_read(buffer, 5);
88 safe_read(buffer, 6);
89
90 EXPECT_EQ(buffer.used_space(), 0ul);
91}
92
93TEST_CASE(full_read_aligned)
94{
95 constexpr size_t capacity = 3;
96 auto buffer = create_circular_buffer(capacity);
97
98 for (unsigned i {}; i < capacity; ++i)
99 safe_write(buffer, i);
100
101 EXPECT_EQ(buffer.used_space(), capacity);
102 EXPECT_EQ(buffer.empty_space(), 0ul);
103
104 u8 const source[] = { 0, 1, 2 };
105
106 u8 result[] = { 0, 0, 0 };
107 auto const bytes_or_error = buffer.read({ result, 3 });
108 EXPECT_EQ(bytes_or_error.size(), 3ul);
109
110 EXPECT_EQ(memcmp(source, result, 3), 0);
111}
112
113TEST_CASE(full_read_non_aligned)
114{
115 constexpr size_t capacity = 3;
116 auto buffer = create_circular_buffer(capacity);
117
118 for (unsigned i {}; i < capacity; ++i)
119 safe_write(buffer, i + 5);
120
121 safe_read(buffer, 5);
122
123 safe_write(buffer, 42);
124
125 EXPECT_EQ(buffer.used_space(), capacity);
126 EXPECT_EQ(buffer.empty_space(), 0ul);
127
128 u8 result[] = { 0, 0, 0 };
129 auto const bytes = buffer.read({ result, 3 });
130 EXPECT_EQ(bytes.size(), 3ul);
131
132 u8 const source[] = { 6, 7, 42 };
133 EXPECT_EQ(memcmp(source, result, 3), 0);
134}
135
136TEST_CASE(full_write_aligned)
137{
138 constexpr size_t capacity = 3;
139 auto buffer = create_circular_buffer(capacity);
140
141 u8 const source[] = { 12, 13, 14 };
142
143 auto written_bytes = buffer.write({ source, 3 });
144 EXPECT_EQ(written_bytes, 3ul);
145
146 EXPECT_EQ(buffer.used_space(), capacity);
147 EXPECT_EQ(buffer.empty_space(), 0ul);
148
149 for (unsigned i {}; i < capacity; ++i)
150 safe_read(buffer, i + 12);
151
152 EXPECT_EQ(buffer.used_space(), 0ul);
153}
154
155TEST_CASE(full_write_non_aligned)
156{
157 constexpr size_t capacity = 3;
158 auto buffer = create_circular_buffer(capacity);
159
160 safe_write(buffer, 10);
161 safe_read(buffer, 10);
162
163 u8 const source[] = { 12, 13, 14 };
164
165 auto written_bytes = buffer.write({ source, 3 });
166 EXPECT_EQ(written_bytes, 3ul);
167
168 EXPECT_EQ(buffer.used_space(), capacity);
169 EXPECT_EQ(buffer.empty_space(), 0ul);
170
171 for (unsigned i {}; i < capacity; ++i)
172 safe_read(buffer, i + 12);
173
174 EXPECT_EQ(buffer.used_space(), 0ul);
175}
176
177TEST_CASE(create_from_bytebuffer)
178{
179 u8 const source[] = { 2, 4, 6 };
180 auto byte_buffer_or_error = ByteBuffer::copy(source, AK::array_size(source));
181 EXPECT(!byte_buffer_or_error.is_error());
182 auto byte_buffer = byte_buffer_or_error.release_value();
183
184 auto circular_buffer_or_error = CircularBuffer::create_initialized(move(byte_buffer));
185 EXPECT(!circular_buffer_or_error.is_error());
186 auto circular_buffer = circular_buffer_or_error.release_value();
187 EXPECT_EQ(circular_buffer.used_space(), circular_buffer.capacity());
188 EXPECT_EQ(circular_buffer.used_space(), 3ul);
189
190 safe_read(circular_buffer, 2);
191 safe_read(circular_buffer, 4);
192 safe_read(circular_buffer, 6);
193}
194
195TEST_CASE(discard)
196{
197 constexpr size_t capacity = 3;
198 auto buffer = create_circular_buffer(capacity);
199
200 safe_write(buffer, 11);
201 safe_write(buffer, 12);
202
203 safe_discard(buffer, 1);
204
205 safe_read(buffer, 12);
206
207 EXPECT_EQ(buffer.used_space(), 0ul);
208 EXPECT_EQ(buffer.empty_space(), capacity);
209}
210
211TEST_CASE(discard_on_edge)
212{
213 constexpr size_t capacity = 3;
214 auto buffer = create_circular_buffer(capacity);
215
216 safe_write(buffer, 11);
217 safe_write(buffer, 12);
218 safe_write(buffer, 13);
219
220 safe_discard(buffer, 2);
221
222 safe_write(buffer, 14);
223 safe_write(buffer, 15);
224
225 safe_discard(buffer, 2);
226
227 safe_read(buffer, 15);
228
229 EXPECT_EQ(buffer.used_space(), 0ul);
230 EXPECT_EQ(buffer.empty_space(), capacity);
231}
232
233TEST_CASE(discard_too_much)
234{
235 constexpr size_t capacity = 3;
236 auto buffer = create_circular_buffer(capacity);
237
238 safe_write(buffer, 11);
239 safe_write(buffer, 12);
240
241 safe_discard(buffer, 2);
242
243 auto result = buffer.discard(2);
244 EXPECT(result.is_error());
245}
246
247TEST_CASE(offset_of)
248{
249 auto const source = "Well Hello Friends!"sv;
250 auto byte_buffer_or_error = ByteBuffer::copy(source.bytes());
251 EXPECT(!byte_buffer_or_error.is_error());
252 auto byte_buffer = byte_buffer_or_error.release_value();
253
254 auto circular_buffer_or_error = CircularBuffer::create_initialized(byte_buffer);
255 EXPECT(!circular_buffer_or_error.is_error());
256 auto circular_buffer = circular_buffer_or_error.release_value();
257
258 auto result = circular_buffer.offset_of("Well"sv);
259 EXPECT(result.has_value());
260 EXPECT_EQ(result.value(), 0ul);
261
262 result = circular_buffer.offset_of("Hello"sv);
263 EXPECT(result.has_value());
264 EXPECT_EQ(result.value(), 5ul);
265
266 safe_discard(circular_buffer, 5);
267
268 auto written_bytes = circular_buffer.write(byte_buffer.span().trim(5));
269 EXPECT_EQ(written_bytes, 5ul);
270
271 result = circular_buffer.offset_of("!Well"sv);
272 EXPECT(result.has_value());
273 EXPECT_EQ(result.value(), 13ul);
274
275 result = circular_buffer.offset_of("!Well"sv, {}, 12);
276 EXPECT(!result.has_value());
277
278 result = circular_buffer.offset_of("e"sv, 2);
279 EXPECT(result.has_value());
280 EXPECT_EQ(result.value(), 9ul);
281}
282
283TEST_CASE(offset_of_with_until_and_after)
284{
285 auto const source = "Well Hello Friends!"sv;
286 auto byte_buffer_or_error = ByteBuffer::copy(source.bytes());
287 EXPECT(!byte_buffer_or_error.is_error());
288 auto byte_buffer = byte_buffer_or_error.release_value();
289
290 auto circular_buffer_or_error = CircularBuffer::create_initialized(byte_buffer);
291 EXPECT(!circular_buffer_or_error.is_error());
292 auto circular_buffer = circular_buffer_or_error.release_value();
293
294 auto result = circular_buffer.offset_of("Well Hello Friends!"sv, 0, 19);
295 EXPECT_EQ(result.value_or(42), 0ul);
296
297 result = circular_buffer.offset_of(" Hello"sv, 4, 10);
298 EXPECT_EQ(result.value_or(42), 4ul);
299
300 result = circular_buffer.offset_of("el"sv, 3, 10);
301 EXPECT_EQ(result.value_or(42), 6ul);
302
303 safe_discard(circular_buffer, 5);
304 auto written_bytes = circular_buffer.write(byte_buffer.span().trim(5));
305 EXPECT_EQ(written_bytes, 5ul);
306
307 result = circular_buffer.offset_of("Hello Friends!Well "sv, 0, 19);
308 EXPECT_EQ(result.value_or(42), 0ul);
309
310 result = circular_buffer.offset_of("o Frie"sv, 4, 10);
311 EXPECT_EQ(result.value_or(42), 4ul);
312
313 result = circular_buffer.offset_of("el"sv, 3, 17);
314 EXPECT_EQ(result.value_or(42), 15ul);
315}
316
317TEST_CASE(offset_of_with_until_and_after_wrapping_around)
318{
319 auto const source = "Well Hello Friends!"sv;
320 auto byte_buffer_or_error = ByteBuffer::copy(source.bytes());
321 EXPECT(!byte_buffer_or_error.is_error());
322 auto byte_buffer = byte_buffer_or_error.release_value();
323
324 auto circular_buffer_or_error = CircularBuffer::create_empty(19);
325 EXPECT(!circular_buffer_or_error.is_error());
326 auto circular_buffer = circular_buffer_or_error.release_value();
327
328 auto written_bytes = circular_buffer.write(byte_buffer.span().trim(5));
329 EXPECT_EQ(written_bytes, 5ul);
330
331 auto result = circular_buffer.offset_of("Well "sv, 0, 5);
332 EXPECT_EQ(result.value_or(42), 0ul);
333
334 written_bytes = circular_buffer.write(byte_buffer.span().slice(5));
335 EXPECT_EQ(written_bytes, 14ul);
336
337 result = circular_buffer.offset_of("Hello Friends!"sv, 5, 19);
338 EXPECT_EQ(result.value_or(42), 5ul);
339
340 safe_discard(circular_buffer, 5);
341
342 result = circular_buffer.offset_of("Hello Friends!"sv, 0, 14);
343 EXPECT_EQ(result.value_or(42), 0ul);
344
345 written_bytes = circular_buffer.write(byte_buffer.span().trim(5));
346 EXPECT_EQ(written_bytes, 5ul);
347
348 result = circular_buffer.offset_of("Well "sv, 14, 19);
349 EXPECT_EQ(result.value_or(42), 14ul);
350}