Seastar
High performance C++ framework for concurrent servers
circular_buffer.hh
1/*
2 * This file is open source software, licensed to you under the terms
3 * of the Apache License, Version 2.0 (the "License"). See the NOTICE file
4 * distributed with this work for additional information regarding copyright
5 * ownership. You may not use this file except in compliance with the License.
6 *
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing,
12 * software distributed under the License is distributed on an
13 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14 * KIND, either express or implied. See the License for the
15 * specific language governing permissions and limitations
16 * under the License.
17 */
18/*
19 * Copyright (C) 2014 Cloudius Systems, Ltd.
20 */
21
22#pragma once
23
24#include <seastar/core/transfer.hh>
25#include <seastar/core/bitops.hh>
26#include <seastar/util/modules.hh>
27#ifndef SEASTAR_MODULE
28#include <concepts>
29#include <memory>
30#include <algorithm>
31#endif
32
33namespace seastar {
34
61SEASTAR_MODULE_EXPORT
62template <typename T, typename Alloc = std::allocator<T>>
64 struct impl : Alloc {
65 T* storage = nullptr;
66 // begin, end interpreted (mod capacity)
67 size_t begin = 0;
68 size_t end = 0;
69 size_t capacity = 0;
70
71 impl(Alloc a) noexcept : Alloc(std::move(a)) { }
72 void reset() {
73 storage = {};
74 begin = 0;
75 end = 0;
76 capacity = 0;
77 }
78 };
79 static_assert(!std::is_default_constructible_v<Alloc>
80 || std::is_nothrow_default_constructible_v<Alloc>);
81 static_assert(std::is_nothrow_move_constructible_v<Alloc>);
82 impl _impl;
83public:
84 using value_type = T;
85 using size_type = size_t;
86 using reference = T&;
87 using pointer = T*;
88 using const_reference = const T&;
89 using const_pointer = const T*;
90public:
91 circular_buffer() noexcept requires std::default_initializable<Alloc> : circular_buffer(Alloc()) {}
92 circular_buffer(Alloc alloc) noexcept;
93 circular_buffer(circular_buffer&& X) noexcept;
94 circular_buffer(const circular_buffer& X) = delete;
96 circular_buffer& operator=(const circular_buffer&) = delete;
97 circular_buffer& operator=(circular_buffer&& b) noexcept;
98 void push_front(const T& data);
99 void push_front(T&& data);
100 template <typename... A>
101 void emplace_front(A&&... args);
102 void push_back(const T& data);
103 void push_back(T&& data);
104 template <typename... A>
105 void emplace_back(A&&... args);
106 T& front() noexcept;
107 const T& front() const noexcept;
108 T& back() noexcept;
109 const T& back() const noexcept;
110 void pop_front() noexcept;
111 void pop_back() noexcept;
112 bool empty() const noexcept;
113 size_t size() const noexcept;
114 size_t capacity() const noexcept;
115 void reserve(size_t);
116 void clear() noexcept;
117 T& operator[](size_t idx) noexcept;
118 const T& operator[](size_t idx) const noexcept;
119 template <typename Func>
120 void for_each(Func func);
121 // access an element, may return wrong or destroyed element
122 // only useful if you do not rely on data accuracy (e.g. prefetch)
123 T& access_element_unsafe(size_t idx) noexcept;
124private:
125 void expand();
126 void expand(size_t);
127 void maybe_expand(size_t nr = 1);
128 size_t mask(size_t idx) const;
129
130 template<typename CB, typename ValueType>
131 struct cbiterator {
132 using iterator_category = std::random_access_iterator_tag;
133 using value_type = ValueType;
134 using difference_type = std::ptrdiff_t;
135 using pointer = ValueType*;
136 using reference = ValueType&;
137
138 ValueType& operator*() const noexcept { return cb->_impl.storage[cb->mask(idx)]; }
139 ValueType* operator->() const noexcept { return &cb->_impl.storage[cb->mask(idx)]; }
140 // prefix
141 cbiterator<CB, ValueType>& operator++() noexcept {
142 idx++;
143 return *this;
144 }
145 // postfix
146 cbiterator<CB, ValueType> operator++(int) noexcept {
147 auto v = *this;
148 idx++;
149 return v;
150 }
151 // prefix
152 cbiterator<CB, ValueType>& operator--() noexcept {
153 idx--;
154 return *this;
155 }
156 // postfix
157 cbiterator<CB, ValueType> operator--(int) noexcept {
158 auto v = *this;
159 idx--;
160 return v;
161 }
162 cbiterator<CB, ValueType> operator+(difference_type n) const noexcept {
163 return cbiterator<CB, ValueType>(cb, idx + n);
164 }
165 cbiterator<CB, ValueType> operator-(difference_type n) const noexcept {
166 return cbiterator<CB, ValueType>(cb, idx - n);
167 }
168 cbiterator<CB, ValueType>& operator+=(difference_type n) noexcept {
169 idx += n;
170 return *this;
171 }
172 cbiterator<CB, ValueType>& operator-=(difference_type n) noexcept {
173 idx -= n;
174 return *this;
175 }
176 bool operator==(const cbiterator<CB, ValueType>& rhs) const noexcept {
177 return idx == rhs.idx;
178 }
179 bool operator!=(const cbiterator<CB, ValueType>& rhs) const noexcept {
180 return idx != rhs.idx;
181 }
182 bool operator<(const cbiterator<CB, ValueType>& rhs) const noexcept {
183 return *this - rhs < 0;
184 }
185 bool operator>(const cbiterator<CB, ValueType>& rhs) const noexcept {
186 return *this - rhs > 0;
187 }
188 bool operator>=(const cbiterator<CB, ValueType>& rhs) const noexcept {
189 return *this - rhs >= 0;
190 }
191 bool operator<=(const cbiterator<CB, ValueType>& rhs) const noexcept {
192 return *this - rhs <= 0;
193 }
194 difference_type operator-(const cbiterator<CB, ValueType>& rhs) const noexcept {
195 return idx - rhs.idx;
196 }
197 cbiterator() = default;
198 private:
199 CB* cb{nullptr};
200 size_t idx{0};
201 cbiterator(CB* b, size_t i) noexcept : cb(b), idx(i) {}
202 friend class circular_buffer;
203 };
204 friend class iterator;
205
206public:
207 typedef cbiterator<circular_buffer, T> iterator;
208 typedef cbiterator<const circular_buffer, const T> const_iterator;
209
210 iterator begin() noexcept {
211 return iterator(this, _impl.begin);
212 }
213 const_iterator begin() const noexcept {
214 return const_iterator(this, _impl.begin);
215 }
216 iterator end() noexcept {
217 return iterator(this, _impl.end);
218 }
219 const_iterator end() const noexcept {
220 return const_iterator(this, _impl.end);
221 }
222 const_iterator cbegin() const noexcept {
223 return const_iterator(this, _impl.begin);
224 }
225 const_iterator cend() const noexcept {
226 return const_iterator(this, _impl.end);
227 }
228 iterator erase(iterator first, iterator last) noexcept;
229};
230
231template <typename T, typename Alloc>
232inline
233size_t
234circular_buffer<T, Alloc>::mask(size_t idx) const {
235 return idx & (_impl.capacity - 1);
236}
237
238template <typename T, typename Alloc>
239inline
240bool
241circular_buffer<T, Alloc>::empty() const noexcept {
242 return _impl.begin == _impl.end;
243}
244
245template <typename T, typename Alloc>
246inline
247size_t
248circular_buffer<T, Alloc>::size() const noexcept {
249 return _impl.end - _impl.begin;
250}
251
252template <typename T, typename Alloc>
253inline
254size_t
255circular_buffer<T, Alloc>::capacity() const noexcept {
256 return _impl.capacity;
257}
258
259template <typename T, typename Alloc>
260inline
261void
262circular_buffer<T, Alloc>::reserve(size_t size) {
263 if (capacity() < size) {
264 // Make sure that the new capacity is a power of two.
265 expand(size_t(1) << log2ceil(size));
266 }
267}
268
269template <typename T, typename Alloc>
270inline
271void
272circular_buffer<T, Alloc>::clear() noexcept {
273 erase(begin(), end());
274}
275
276template <typename T, typename Alloc>
277inline
278circular_buffer<T, Alloc>::circular_buffer(Alloc alloc) noexcept
279 : _impl(std::move(alloc)) {
280}
281
282template <typename T, typename Alloc>
283inline
284circular_buffer<T, Alloc>::circular_buffer(circular_buffer&& x) noexcept
285 : _impl(std::move(x._impl)) {
286 x._impl.reset();
287}
288
289template <typename T, typename Alloc>
290inline
291circular_buffer<T, Alloc>& circular_buffer<T, Alloc>::operator=(circular_buffer&& x) noexcept {
292 if (this != &x) {
293 this->~circular_buffer();
294 new (this) circular_buffer(std::move(x));
295 }
296 return *this;
297}
298
299template <typename T, typename Alloc>
300template <typename Func>
301inline
302void
303circular_buffer<T, Alloc>::for_each(Func func) {
304 auto s = _impl.storage;
305 auto m = _impl.capacity - 1;
306 for (auto i = _impl.begin; i != _impl.end; ++i) {
307 func(s[i & m]);
308 }
309}
310
311template <typename T, typename Alloc>
312inline
313circular_buffer<T, Alloc>::~circular_buffer() {
314 for_each([this] (T& obj) {
315 std::allocator_traits<Alloc>::destroy(_impl, &obj);
316 });
317 _impl.deallocate(_impl.storage, _impl.capacity);
318}
319
320template <typename T, typename Alloc>
321void
322circular_buffer<T, Alloc>::expand() {
323 expand(std::max<size_t>(_impl.capacity * 2, 1));
324}
325
326template <typename T, typename Alloc>
327void
328circular_buffer<T, Alloc>::expand(size_t new_cap) {
329 auto new_storage = _impl.allocate(new_cap);
330 auto p = new_storage;
331 try {
332 for_each([this, &p] (T& obj) {
333 transfer_pass1(_impl, &obj, p);
334 p++;
335 });
336 } catch (...) {
337 while (p != new_storage) {
338 std::allocator_traits<Alloc>::destroy(_impl, --p);
339 }
340 _impl.deallocate(new_storage, new_cap);
341 throw;
342 }
343 p = new_storage;
344 for_each([this, &p] (T& obj) {
345 transfer_pass2(_impl, &obj, p++);
346 });
347 std::swap(_impl.storage, new_storage);
348 std::swap(_impl.capacity, new_cap);
349 _impl.begin = 0;
350 _impl.end = p - _impl.storage;
351 _impl.deallocate(new_storage, new_cap);
352}
353
354template <typename T, typename Alloc>
355inline
356void
357circular_buffer<T, Alloc>::maybe_expand(size_t nr) {
358 if (_impl.end - _impl.begin + nr > _impl.capacity) {
359 expand();
360 }
361}
362
363template <typename T, typename Alloc>
364inline
365void
366circular_buffer<T, Alloc>::push_front(const T& data) {
367 maybe_expand();
368 auto p = &_impl.storage[mask(_impl.begin - 1)];
369 std::allocator_traits<Alloc>::construct(_impl, p, data);
370 --_impl.begin;
371}
372
373template <typename T, typename Alloc>
374inline
375void
376circular_buffer<T, Alloc>::push_front(T&& data) {
377 maybe_expand();
378 auto p = &_impl.storage[mask(_impl.begin - 1)];
379 std::allocator_traits<Alloc>::construct(_impl, p, std::move(data));
380 --_impl.begin;
381}
382
383template <typename T, typename Alloc>
384template <typename... Args>
385inline
386void
387circular_buffer<T, Alloc>::emplace_front(Args&&... args) {
388 maybe_expand();
389 auto p = &_impl.storage[mask(_impl.begin - 1)];
390 std::allocator_traits<Alloc>::construct(_impl, p, std::forward<Args>(args)...);
391 --_impl.begin;
392}
393
394template <typename T, typename Alloc>
395inline
396void
397circular_buffer<T, Alloc>::push_back(const T& data) {
398 maybe_expand();
399 auto p = &_impl.storage[mask(_impl.end)];
400 std::allocator_traits<Alloc>::construct(_impl, p, data);
401 ++_impl.end;
402}
403
404template <typename T, typename Alloc>
405inline
406void
407circular_buffer<T, Alloc>::push_back(T&& data) {
408 maybe_expand();
409 auto p = &_impl.storage[mask(_impl.end)];
410 std::allocator_traits<Alloc>::construct(_impl, p, std::move(data));
411 ++_impl.end;
412}
413
414template <typename T, typename Alloc>
415template <typename... Args>
416inline
417void
418circular_buffer<T, Alloc>::emplace_back(Args&&... args) {
419 maybe_expand();
420 auto p = &_impl.storage[mask(_impl.end)];
421 std::allocator_traits<Alloc>::construct(_impl, p, std::forward<Args>(args)...);
422 ++_impl.end;
423}
424
425template <typename T, typename Alloc>
426inline
427T&
428circular_buffer<T, Alloc>::front() noexcept {
429 return _impl.storage[mask(_impl.begin)];
430}
431
432template <typename T, typename Alloc>
433inline
434const T&
435circular_buffer<T, Alloc>::front() const noexcept {
436 return _impl.storage[mask(_impl.begin)];
437}
438
439template <typename T, typename Alloc>
440inline
441T&
442circular_buffer<T, Alloc>::back() noexcept {
443 return _impl.storage[mask(_impl.end - 1)];
444}
445
446template <typename T, typename Alloc>
447inline
448const T&
449circular_buffer<T, Alloc>::back() const noexcept {
450 return _impl.storage[mask(_impl.end - 1)];
451}
452
453template <typename T, typename Alloc>
454inline
455void
456circular_buffer<T, Alloc>::pop_front() noexcept {
457 std::allocator_traits<Alloc>::destroy(_impl, &front());
458 ++_impl.begin;
459}
460
461template <typename T, typename Alloc>
462inline
463void
464circular_buffer<T, Alloc>::pop_back() noexcept {
465 std::allocator_traits<Alloc>::destroy(_impl, &back());
466 --_impl.end;
467}
468
469template <typename T, typename Alloc>
470inline
471T&
472circular_buffer<T, Alloc>::operator[](size_t idx) noexcept {
473 return _impl.storage[mask(_impl.begin + idx)];
474}
475
476template <typename T, typename Alloc>
477inline
478const T&
479circular_buffer<T, Alloc>::operator[](size_t idx) const noexcept {
480 return _impl.storage[mask(_impl.begin + idx)];
481}
482
483template <typename T, typename Alloc>
484inline
485T&
486circular_buffer<T, Alloc>::access_element_unsafe(size_t idx) noexcept {
487 return _impl.storage[mask(_impl.begin + idx)];
488}
489
490template <typename T, typename Alloc>
491inline
492typename circular_buffer<T, Alloc>::iterator
493circular_buffer<T, Alloc>::erase(iterator first, iterator last) noexcept {
494 static_assert(std::is_nothrow_move_assignable_v<T>, "erase() assumes move assignment does not throw");
495 if (first == last) {
496 return last;
497 }
498 // Move to the left or right depending on which would result in least amount of moves.
499 // This also guarantees that iterators will be stable when removing from either front or back.
500 if (std::distance(begin(), first) < std::distance(last, end())) {
501 auto new_start = std::move_backward(begin(), first, last);
502 for (auto i = begin(); i < new_start; ++i) {
503 std::allocator_traits<Alloc>::destroy(_impl, &*i);
504 }
505 _impl.begin = new_start.idx;
506 return last;
507 } else {
508 auto new_end = std::move(last, end(), first);
509 for (auto i = new_end, e = end(); i < e; ++i) {
510 std::allocator_traits<Alloc>::destroy(_impl, &*i);
511 }
512 _impl.end = new_end.idx;
513 return first;
514 }
515}
516
517}
Definition: circular_buffer.hh:63
holds the implementation parts of the metrics layer, do not use directly.
Seastar API namespace.
Definition: abort_on_ebadf.hh:26