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
#pragma once
6
 
7
#include <kj/array.h>
8
#include <kj/common.h>
9
#include <kj/debug.h>
10
 
11
#include <iterator>
12
 
13
namespace workerd {
14
 
15
// A simple ring buffer with amortized O(1) push/pop at both ends and O(1) random access.
16
// The initial capacity can be specified as a template parameter (default 16). The buffer
17
// will grow as needed. The type T must be Moveable and/or Copyable.
18
//
19
// The purpose of this class is to provide a more memory-efficient alternative to std::list
20
// for use in places where we need a double-ended queue with stable iterators and references
21
// but avoids the memory overhead of std::list's per-node allocations and has better cache
22
// locality than std::list. The trade-off is that iterators and references may be
23
// invalidated when the buffer grows, which is not the case with std::list. However,
24
// in our use cases, we do not rely on iterator/reference stability across growth
25
// operations, so this fine.
26
template <typename T, size_t InitialCapacity = 16>
27
class RingBuffer final {
28
 public:
29
  RingBuffer(): storage(kj::heapArray<kj::byte>(sizeof(T) * InitialCapacity)) {}
30
 
31
  ~RingBuffer() {
32
    clear();
33
  }
34
 
35
  RingBuffer(RingBuffer&& other) noexcept
36
      : storage(kj::mv(other.storage)),
37
        head(other.head),
38
        tail(other.tail),
39
        count(other.count),
40
        generation(other.generation) {
41
    other.head = 0;
42
    other.tail = 0;
43
    other.count = 0;
44
    other.generation = 0;
45
  }
46
 
47
  RingBuffer& operator=(RingBuffer&& other) noexcept {
48
    if (this != &other) {
49
      clear();
50
 
51
      storage = kj::mv(other.storage);
52
      head = other.head;
53
      tail = other.tail;
54
      count = other.count;
55
      generation = other.generation;
56
 
57
      other.head = 0;
58
      other.tail = 0;
59
      other.count = 0;
60
      other.generation = 0;
61
    }
62
    return *this;
63
  }
64
 
65
  KJ_DISALLOW_COPY(RingBuffer);
66
 
67
  bool empty() const {
68
    return count == 0;
69
  }
70
  size_t size() const {
71
    return count;
72
  }
73
 
74
  class iterator;
75
  class const_iterator;
76
 
77
  class iterator {
78
   public:
79
    using iterator_category = std::bidirectional_iterator_tag;
80
    using value_type = T;
81
    using difference_type = std::ptrdiff_t;
82
    using pointer = T*;
83
    using reference = T&;
84
 
85
    iterator(): buffer(nullptr), index(0) {}
86
 
87
    reference operator*() const {
88
      KJ_DREQUIRE(buffer != nullptr);
89
      size_t physicalIndex = (buffer->head + index) % buffer->capacity();
90
      return buffer->slot(physicalIndex);
91
    }
92
 
93
    pointer operator->() const {
94
      KJ_DREQUIRE(buffer != nullptr);
95
      size_t physicalIndex = (buffer->head + index) % buffer->capacity();
96
      return &buffer->slot(physicalIndex);
97
    }
98
 
99
    iterator& operator++() {
100
      KJ_DREQUIRE(buffer != nullptr);
101
      ++index;
102
      return *this;
103
    }
104
 
105
    iterator operator++(int) {
106
      iterator tmp = *this;
107
      ++(*this);
108
      return tmp;
109
    }
110
 
111
    iterator& operator--() {
112
      KJ_DREQUIRE(buffer != nullptr);
113
      --index;
114
      return *this;
115
    }
116
 
117
    iterator operator--(int) {
118
      iterator tmp = *this;
119
      --(*this);
120
      return tmp;
121
    }
122
 
123
    bool operator==(const iterator& other) const {
124
      return buffer == other.buffer && index == other.index;
125
    }
126
 
127
    bool operator!=(const iterator& other) const {
128
      return !(*this == other);
129
    }
130
 
131
   private:
132
    friend class RingBuffer;
133
    friend class const_iterator;
134
 
135
    iterator(RingBuffer* buf, size_t idx): buffer(buf), index(idx) {}
136
 
137
    RingBuffer* buffer;
138
    size_t index;  // Logical index (0 to count-1)
139
  };
140
 
141
  class const_iterator {
142
   public:
143
    using iterator_category = std::bidirectional_iterator_tag;
144
    using value_type = T;
145
    using difference_type = std::ptrdiff_t;
146
    using pointer = const T*;
147
    using reference = const T&;
148
 
149
    const_iterator(): buffer(nullptr), index(0) {}
150
 
151
    const_iterator(const iterator& it): buffer(it.buffer), index(it.index) {}
152
 
153
    reference operator*() const {
154
      KJ_DREQUIRE(buffer != nullptr);
155
      size_t physicalIndex = (buffer->head + index) % buffer->capacity();
156
      return buffer->slot(physicalIndex);
157
    }
158
 
159
    pointer operator->() const {
160
      KJ_DREQUIRE(buffer != nullptr);
161
      size_t physicalIndex = (buffer->head + index) % buffer->capacity();
162
      return &buffer->slot(physicalIndex);
163
    }
164
 
165
    const_iterator& operator++() {
166
      KJ_DREQUIRE(buffer != nullptr);
167
      ++index;
168
      return *this;
169
    }
170
 
171
    const_iterator operator++(int) {
172
      const_iterator tmp = *this;
173
      ++(*this);
174
      return tmp;
175
    }
176
 
177
    const_iterator& operator--() {
178
      KJ_DREQUIRE(buffer != nullptr);
179
      --index;
180
      return *this;
181
    }
182
 
183
    const_iterator operator--(int) {
184
      const_iterator tmp = *this;
185
      --(*this);
186
      return tmp;
187
    }
188
 
189
    bool operator==(const const_iterator& other) const {
190
      return buffer == other.buffer && index == other.index;
191
    }
192
 
193
    bool operator!=(const const_iterator& other) const {
194
      return !(*this == other);
195
    }
196
 
197
   private:
198
    friend class RingBuffer;
199
 
200
    const_iterator(const RingBuffer* buf, size_t idx): buffer(buf), index(idx) {}
201
 
202
    const RingBuffer* buffer;
203
    size_t index;
204
  };
205
 
206
  iterator begin() {
207
    return iterator(this, 0);
208
  }
209
 
210
  iterator end() {
211
    return iterator(this, count);
212
  }
213
 
214
  const_iterator begin() const {
215
    return const_iterator(this, 0);
216
  }
217
 
218
  const_iterator end() const {
219
    return const_iterator(this, count);
220
  }
221
 
222
  const_iterator cbegin() const {
223
    return const_iterator(this, 0);
224
  }
225
 
226
  const_iterator cend() const {
227
    return const_iterator(this, count);
228
  }
229
 
230
  void push_back(T&& item) {
231
    if (count == capacity()) {
232
      grow();
233
    }
234
    // Use placement new - the slot is uninitialized raw memory
235
    new (&slot(tail)) T(kj::mv(item));
236
    tail = (tail + 1) % capacity();
237
    count++;
238
  }
239
 
240
  void push_back(const T& item) {
241
    if (count == capacity()) {
242
      grow();
243
    }
244
    // Use placement new - the slot is uninitialized raw memory
245
    new (&slot(tail)) T(item);
246
    tail = (tail + 1) % capacity();
247
    count++;
248
  }
249
 
250
  template <typename... Args>
251
  T& emplace_back(Args&&... args) {
252
    if (count == capacity()) {
253
      grow();
254
    }
255
    // Use placement new to construct in place at the tail position
256
    T* ptr = new (&slot(tail)) T(kj::fwd<Args>(args)...);
257
    tail = (tail + 1) % capacity();
258
    count++;
259
    return *ptr;
260
  }
261
 
262
  void pop_front() {
263
    KJ_DREQUIRE(count > 0);
264
    slot(head).~T();
265
    head = (head + 1) % capacity();
266
    count--;
267
    generation++;
268
  }
269
 
270
  // Returns a generation counter that is incremented each time pop_front() is called.
271
  // This can be used to detect if the front of the queue has changed during async operations,
272
  // since RingBuffer may relocate elements when it grows and pointer/reference comparisons
273
  // are not reliable.
274
  uint64_t currentGeneration() const {
275
    return generation;
276
  }
277
 
278
  T& front() {
279
    KJ_DREQUIRE(count > 0);
280
    return slot(head);
281
  }
282
 
283
  T& back() {
284
    KJ_DREQUIRE(count > 0);
285
    size_t backIdx = (tail == 0) ? capacity() - 1 : tail - 1;
286
    KJ_REQUIRE(backIdx < capacity());
287
    return slot(backIdx);
288
  }
289
 
290
  void clear() {
291
    while (count > 0) {
292
      slot(head).~T();
293
      head = (head + 1) % capacity();
294
      count--;
295
    }
296
    // Reset to initial state
297
    head = 0;
298
    tail = 0;
299
  }
300
 
301
 private:
302
  kj::Array<kj::byte> storage;
303
  size_t head = 0;
304
  size_t tail = 0;
305
  size_t count = 0;
306
  uint64_t generation = 0;  // Incremented on each pop_front()
307
 
308
  size_t capacity() const {
309
    return storage.size() / sizeof(T);
310
  }
311
 
312
  T& slot(size_t index) {
313
    return reinterpret_cast<T*>(storage.begin())[index];
314
  }
315
 
316
  const T& slot(size_t index) const {
317
    return reinterpret_cast<const T*>(storage.begin())[index];
318
  }
319
 
320
  void grow() {
321
    size_t oldCapacity = capacity();
322
    size_t newCapacity = oldCapacity * 2;
323
    auto newStorage = kj::heapArray<kj::byte>(sizeof(T) * newCapacity);
324
    T* newSlots = reinterpret_cast<T*>(newStorage.begin());
325
 
326
    // Move-construct elements to new storage using placement new
327
    for (size_t i = 0; i < count; i++) {
328
      new (&newSlots[i]) T(kj::mv(slot((head + i) % oldCapacity)));
329
      slot((head + i) % oldCapacity).~T();
330
    }
331
 
332
    storage = kj::mv(newStorage);
333
    head = 0;
334
    tail = count;
335
  }
336
};
337
 
338
}  // namespace workerd