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