Skip to content
rachel/workerd
File

Blob: src/workerd/util/ring-buffer-test.c++

11.4 KB
1// Copyright (c) 2017-2022 Cloudflare, Inc.
2// Licensed under the Apache 2.0 license found in the LICENSE file or at:
3//     https://opensource.org/licenses/Apache-2.0
4 
5#include "ring-buffer.h"
6 
7#include <kj/test.h>
8 
9namespace workerd {
10namespace {
11 
12using kj::uint;
13 
14KJ_TEST("RingBuffer basic operations") {
15  RingBuffer<int> buffer;
16 
17  KJ_EXPECT(buffer.empty());
18  KJ_EXPECT(buffer.size() == 0);
19 
20  buffer.push_back(1);
21  KJ_EXPECT(!buffer.empty());
22  KJ_EXPECT(buffer.size() == 1);
23  KJ_EXPECT(buffer.front() == 1);
24  KJ_EXPECT(buffer.back() == 1);
25 
26  buffer.push_back(2);
27  KJ_EXPECT(buffer.size() == 2);
28  KJ_EXPECT(buffer.front() == 1);
29  KJ_EXPECT(buffer.back() == 2);
30 
31  buffer.push_back(3);
32  KJ_EXPECT(buffer.size() == 3);
33  KJ_EXPECT(buffer.front() == 1);
34  KJ_EXPECT(buffer.back() == 3);
35 
36  buffer.pop_front();
37  KJ_EXPECT(buffer.size() == 2);
38  KJ_EXPECT(buffer.front() == 2);
39  KJ_EXPECT(buffer.back() == 3);
40 
41  buffer.pop_front();
42  KJ_EXPECT(buffer.size() == 1);
43  KJ_EXPECT(buffer.front() == 3);
44  KJ_EXPECT(buffer.back() == 3);
45 
46  buffer.pop_front();
47  KJ_EXPECT(buffer.empty());
48  KJ_EXPECT(buffer.size() == 0);
49}
50 
51KJ_TEST("RingBuffer push_back with move semantics") {
52  RingBuffer<kj::String> buffer;
53 
54  auto str1 = kj::heapString("hello");
55  auto str2 = kj::heapString("world");
56 
57  buffer.push_back(kj::mv(str1));
58  buffer.push_back(kj::mv(str2));
59 
60  KJ_EXPECT(buffer.size() == 2);
61  KJ_EXPECT(buffer.front() == "hello");
62  KJ_EXPECT(buffer.back() == "world");
63}
64 
65KJ_TEST("RingBuffer push_back with copy") {
66  RingBuffer<int> buffer;
67 
68  int value = 42;
69  buffer.push_back(value);
70  KJ_EXPECT(buffer.size() == 1);
71  KJ_EXPECT(buffer.front() == 42);
72  KJ_EXPECT(value == 42);  // Original value unchanged
73}
74 
75KJ_TEST("RingBuffer emplace_back") {
76  struct TestStruct {
77    int a = 0;
78    TestStruct() = default;
79    TestStruct(int a): a(a) {}
80    TestStruct(const TestStruct&) = default;
81    TestStruct& operator=(const TestStruct&) = default;
82  };
83 
84  RingBuffer<TestStruct> buffer;
85 
86  auto& ref = buffer.emplace_back(10);
87  KJ_EXPECT(buffer.size() == 1);
88  KJ_EXPECT(ref.a == 10);
89  KJ_EXPECT(buffer.front().a == 10);
90}
91 
92KJ_TEST("RingBuffer clear") {
93  RingBuffer<int> buffer;
94 
95  for (int i = 0; i < 10; i++) {
96    buffer.push_back(i);
97  }
98  KJ_EXPECT(buffer.size() == 10);
99 
100  buffer.clear();
101  KJ_EXPECT(buffer.empty());
102  KJ_EXPECT(buffer.size() == 0);
103 
104  // Should be able to use after clear
105  buffer.push_back(1);
106  KJ_EXPECT(buffer.size() == 1);
107  KJ_EXPECT(buffer.front() == 1);
108}
109 
110KJ_TEST("RingBuffer iterator basic") {
111  RingBuffer<int> buffer;
112 
113  for (int i = 0; i < 5; i++) {
114    buffer.push_back(i);
115  }
116 
117  int expected = 0;
118  // Using verbose syntax to test iterator
119  // NOLINTNEXTLINE(modernize-loop-convert)
120  for (auto it = buffer.begin(); it != buffer.end(); ++it) {
121    KJ_EXPECT(*it == expected++);
122  }
123  KJ_EXPECT(expected == 5);
124}
125 
126KJ_TEST("RingBuffer iterator range-based for loop") {
127  RingBuffer<int> buffer;
128 
129  for (int i = 1; i <= 5; i++) {
130    buffer.push_back(i * 10);
131  }
132 
133  int expected = 10;
134  for (auto& value: buffer) {
135    KJ_EXPECT(value == expected);
136    expected += 10;
137  }
138  KJ_EXPECT(expected == 60);
139}
140 
141KJ_TEST("RingBuffer iterator modification") {
142  RingBuffer<int> buffer;
143 
144  for (int i = 0; i < 5; i++) {
145    buffer.push_back(i);
146  }
147 
148  // Modify through iterator
149  for (auto& value: buffer) {
150    value *= 2;
151  }
152 
153  int expected = 0;
154  for (const auto& value: buffer) {
155    KJ_EXPECT(value == expected * 2);
156    expected++;
157  }
158}
159 
160KJ_TEST("RingBuffer const_iterator") {
161  RingBuffer<int> buffer;
162 
163  for (int i = 0; i < 5; i++) {
164    buffer.push_back(i);
165  }
166 
167  const auto& constBuffer = buffer;
168 
169  int expected = 0;
170  // Using verbose syntax to test iterator
171  // NOLINTNEXTLINE(modernize-loop-convert)
172  for (auto it = constBuffer.begin(); it != constBuffer.end(); ++it) {
173    KJ_EXPECT(*it == expected++);
174  }
175}
176 
177KJ_TEST("RingBuffer iterator decrement") {
178  RingBuffer<int> buffer;
179 
180  for (int i = 0; i < 5; i++) {
181    buffer.push_back(i);
182  }
183 
184  auto it = buffer.end();
185  --it;
186  KJ_EXPECT(*it == 4);
187  --it;
188  KJ_EXPECT(*it == 3);
189 
190  it--;
191  KJ_EXPECT(*it == 2);
192}
193 
194KJ_TEST("RingBuffer iterator equality") {
195  RingBuffer<int> buffer;
196  buffer.push_back(1);
197  buffer.push_back(2);
198 
199  auto it1 = buffer.begin();
200  auto it2 = buffer.begin();
201  KJ_EXPECT(it1 == it2);
202 
203  ++it2;
204  KJ_EXPECT(it1 != it2);
205 
206  auto end1 = buffer.end();
207  auto end2 = buffer.end();
208  KJ_EXPECT(end1 == end2);
209}
210 
211KJ_TEST("RingBuffer iterator arrow operator") {
212  struct Point {
213    int x;
214    int y;
215  };
216 
217  RingBuffer<Point> buffer;
218  buffer.push_back(Point{1, 2});
219  buffer.push_back(Point{3, 4});
220 
221  auto it = buffer.begin();
222  KJ_EXPECT(it->x == 1);
223  KJ_EXPECT(it->y == 2);
224 
225  ++it;
226  KJ_EXPECT(it->x == 3);
227  KJ_EXPECT(it->y == 4);
228}
229 
230KJ_TEST("RingBuffer growth when capacity exceeded") {
231  RingBuffer<int, 4> buffer;  // Small initial capacity
232 
233  // Fill beyond initial capacity
234  for (int i = 0; i < 10; i++) {
235    buffer.push_back(i);
236  }
237 
238  KJ_EXPECT(buffer.size() == 10);
239 
240  // Verify all elements are intact
241  int expected = 0;
242  for (const auto& value: buffer) {
243    KJ_EXPECT(value == expected++);
244  }
245  KJ_EXPECT(expected == 10);
246}
247 
248KJ_TEST("RingBuffer growth maintains order across wrap-around") {
249  RingBuffer<int, 4> buffer;
250 
251  // Create wrap-around scenario: fill, then pop, then fill again
252  buffer.push_back(1);
253  buffer.push_back(2);
254  buffer.push_back(3);
255  buffer.push_back(4);
256 
257  buffer.pop_front();  // Remove 1
258  buffer.pop_front();  // Remove 2
259 
260  // Now head is at index 2, tail wraps around
261  buffer.push_back(5);
262  buffer.push_back(6);
263  buffer.push_back(7);  // This should trigger growth
264 
265  KJ_EXPECT(buffer.size() == 5);
266 
267  // Verify order is maintained: 3, 4, 5, 6, 7
268  int expected = 3;
269  for (const auto& value: buffer) {
270    KJ_EXPECT(value == expected++);
271  }
272  KJ_EXPECT(expected == 8);
273}
274 
275KJ_TEST("RingBuffer with non-trivial types") {
276  struct ComplexType {
277    kj::String str;
278    kj::Vector<int> vec;
279 
280    ComplexType(kj::String s): str(kj::mv(s)) {
281      vec.add(1);
282      vec.add(2);
283    }
284 
285    ComplexType(ComplexType&& other) = default;
286    ComplexType& operator=(ComplexType&& other) = default;
287 
288    KJ_DISALLOW_COPY(ComplexType);
289  };
290 
291  RingBuffer<kj::Own<ComplexType>> buffer;
292 
293  buffer.push_back(kj::heap<ComplexType>(kj::str("first")));
294  buffer.push_back(kj::heap<ComplexType>(kj::str("second")));
295  buffer.push_back(kj::heap<ComplexType>(kj::str("third")));
296 
297  KJ_EXPECT(buffer.size() == 3);
298  KJ_EXPECT(buffer.front()->str == "first");
299  KJ_EXPECT(buffer.back()->str == "third");
300 
301  buffer.pop_front();
302  KJ_EXPECT(buffer.front()->str == "second");
303}
304 
305KJ_TEST("RingBuffer destructor calls element destructors") {
306  struct DestructionDetector {
307    DestructionDetector(uint& count): count(count) {}
308    ~DestructionDetector() noexcept(false) {
309      ++count;
310    }
311    KJ_DISALLOW_COPY_AND_MOVE(DestructionDetector);
312    uint& count;
313  };
314 
315  uint destructionCount = 0;
316 
317  {
318    RingBuffer<kj::Own<DestructionDetector>> buffer;
319    buffer.push_back(kj::heap<DestructionDetector>(destructionCount));
320    buffer.push_back(kj::heap<DestructionDetector>(destructionCount));
321    buffer.push_back(kj::heap<DestructionDetector>(destructionCount));
322 
323    KJ_EXPECT(destructionCount == 0);
324  }  // Buffer goes out of scope
325 
326  KJ_EXPECT(destructionCount == 3);
327}
328 
329KJ_TEST("RingBuffer pop_front calls element destructor") {
330  struct DestructionDetector {
331    DestructionDetector(uint& count): count(count) {}
332    ~DestructionDetector() noexcept(false) {
333      ++count;
334    }
335    KJ_DISALLOW_COPY_AND_MOVE(DestructionDetector);
336    uint& count;
337  };
338 
339  uint destructionCount = 0;
340 
341  RingBuffer<kj::Own<DestructionDetector>> buffer;
342  buffer.push_back(kj::heap<DestructionDetector>(destructionCount));
343  buffer.push_back(kj::heap<DestructionDetector>(destructionCount));
344 
345  KJ_EXPECT(destructionCount == 0);
346 
347  buffer.pop_front();
348  KJ_EXPECT(destructionCount == 1);
349 
350  buffer.pop_front();
351  KJ_EXPECT(destructionCount == 2);
352}
353 
354KJ_TEST("RingBuffer clear calls all element destructors") {
355  struct DestructionDetector {
356    DestructionDetector(uint& count): count(count) {}
357    ~DestructionDetector() noexcept(false) {
358      ++count;
359    }
360    KJ_DISALLOW_COPY_AND_MOVE(DestructionDetector);
361    uint& count;
362  };
363 
364  uint destructionCount = 0;
365 
366  RingBuffer<kj::Own<DestructionDetector>> buffer;
367  for (int i = 0; i < 5; i++) {
368    buffer.push_back(kj::heap<DestructionDetector>(destructionCount));
369  }
370 
371  KJ_EXPECT(destructionCount == 0);
372 
373  buffer.clear();
374  KJ_EXPECT(destructionCount == 5);
375  KJ_EXPECT(buffer.empty());
376}
377 
378KJ_TEST("RingBuffer stress test - many operations") {
379  RingBuffer<int, 4> buffer;
380 
381  // Perform many mixed operations
382  for (int i = 0; i < 100; i++) {
383    buffer.push_back(i);
384  }
385 
386  for (int i = 0; i < 50; i++) {
387    buffer.pop_front();
388  }
389 
390  for (int i = 100; i < 150; i++) {
391    buffer.push_back(i);
392  }
393 
394  KJ_EXPECT(buffer.size() == 100);
395 
396  // Verify contents
397  int expected = 50;
398  for (const auto& value: buffer) {
399    KJ_EXPECT(value == expected++);
400  }
401}
402 
403KJ_TEST("RingBuffer empty buffer iterators") {
404  RingBuffer<int> buffer;
405 
406  KJ_EXPECT(buffer.begin() == buffer.end());
407  KJ_EXPECT(buffer.cbegin() == buffer.cend());
408 
409  // Range-based for should not execute
410  for ([[maybe_unused]] auto& value: buffer) {
411    KJ_FAIL_EXPECT("Should not iterate over empty buffer");
412  }
413}
414 
415KJ_TEST("RingBuffer single element") {
416  RingBuffer<int> buffer;
417  buffer.push_back(42);
418 
419  KJ_EXPECT(buffer.front() == 42);
420  KJ_EXPECT(buffer.back() == 42);
421  KJ_EXPECT(buffer.size() == 1);
422 
423  int count = 0;
424  for (const auto& value: buffer) {
425    KJ_EXPECT(value == 42);
426    count++;
427  }
428  KJ_EXPECT(count == 1);
429}
430 
431KJ_TEST("RingBuffer alternating push/pop maintains correctness") {
432  RingBuffer<int, 4> buffer;
433 
434  for (int round = 0; round < 10; round++) {
435    buffer.push_back(round * 2);
436    buffer.push_back(round * 2 + 1);
437 
438    KJ_EXPECT(buffer.front() == round * 2);
439    buffer.pop_front();
440 
441    KJ_EXPECT(buffer.front() == round * 2 + 1);
442    buffer.pop_front();
443 
444    KJ_EXPECT(buffer.empty());
445  }
446}
447 
448KJ_TEST("RingBuffer with custom initial capacity") {
449  RingBuffer<int, 128> largeBuffer;
450  RingBuffer<int, 2> tinyBuffer;
451 
452  // Both should work correctly regardless of initial capacity
453  for (int i = 0; i < 10; i++) {
454    largeBuffer.push_back(i);
455    tinyBuffer.push_back(i);
456  }
457 
458  KJ_EXPECT(largeBuffer.size() == 10);
459  KJ_EXPECT(tinyBuffer.size() == 10);
460 
461  int expected = 0;
462  for (const auto& value: largeBuffer) {
463    KJ_EXPECT(value == expected++);
464  }
465 
466  expected = 0;
467  for (const auto& value: tinyBuffer) {
468    KJ_EXPECT(value == expected++);
469  }
470}
471 
472KJ_TEST("RingBuffer front and back with wrap-around") {
473  RingBuffer<int, 4> buffer;
474 
475  buffer.push_back(1);
476  buffer.push_back(2);
477  buffer.push_back(3);
478  buffer.push_back(4);
479 
480  // Create wrap-around
481  buffer.pop_front();
482  buffer.pop_front();
483  buffer.push_back(5);
484  buffer.push_back(6);
485 
486  KJ_EXPECT(buffer.size() == 4);
487  KJ_EXPECT(buffer.front() == 3);
488  KJ_EXPECT(buffer.back() == 6);
489}
490 
491KJ_TEST("RingBuffer emplace_back returns reference") {
492  RingBuffer<int> buffer;
493 
494  auto& ref1 = buffer.emplace_back(10);
495  ref1 = 20;
496 
497  KJ_EXPECT(buffer.front() == 20);
498 
499  buffer.emplace_back(30);
500  buffer.emplace_back(40);
501 
502  auto& ref2 = buffer.emplace_back(50);
503  ref2 = 60;
504 
505  KJ_EXPECT(buffer.back() == 60);
506}
507 
508KJ_TEST("RingBuffer iterator conversion from mutable to const") {
509  RingBuffer<int> buffer;
510  buffer.push_back(1);
511  buffer.push_back(2);
512 
513  auto it = buffer.begin();
514  RingBuffer<int>::const_iterator cit = it;  // Conversion
515 
516  KJ_EXPECT(*cit == 1);
517  ++cit;
518  KJ_EXPECT(*cit == 2);
519}
520 
521}  // namespace
522}  // namespace workerd