Seastar
High performance C++ framework for concurrent servers
circular_buffer_fixed_capacity.hh
Go to the documentation of this file.
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) 2017 ScyllaDB
20  */
21 
22 #pragma once
23 
24 // A fixed capacity double-ended queue container that can be efficiently
25 // extended (and shrunk) from both ends. Implementation is a single
26 // storage vector.
27 //
28 // Similar to libstdc++'s std::deque, except that it uses a single level
29 // store, and so is more efficient for simple stored items.
30 
31 #include <type_traits>
32 #include <cstddef>
33 #include <iterator>
34 #include <utility>
35 
36 
38 
39 namespace seastar {
40 
48 template <typename T, size_t Capacity>
50  size_t _begin = 0;
51  size_t _end = 0;
52  union maybe_storage {
53  T data;
54  maybe_storage() noexcept {}
55  ~maybe_storage() {}
56  };
57  maybe_storage _storage[Capacity];
58 private:
59  static size_t mask(size_t idx) { return idx % Capacity; }
60  T* obj(size_t idx) { return &_storage[mask(idx)].data; }
61  const T* obj(size_t idx) const { return &_storage[mask(idx)].data; }
62 public:
63  static_assert((Capacity & (Capacity - 1)) == 0, "capacity must be a power of two");
64  static_assert(std::is_nothrow_move_constructible<T>::value && std::is_nothrow_move_assignable<T>::value,
65  "circular_buffer_fixed_capacity only supports nothrow-move value types");
66  using value_type = T;
67  using size_type = size_t;
68  using reference = T&;
69  using pointer = T*;
70  using const_reference = const T&;
71  using const_pointer = const T*;
72  using difference_type = ssize_t;
73 public:
74  template <typename ValueType>
75  class cbiterator {
76  using holder = std::conditional_t<std::is_const<ValueType>::value, const maybe_storage, maybe_storage>;
77  holder* _start;
78  size_t _idx;
79  private:
80  cbiterator(holder* start, size_t idx) noexcept : _start(start), _idx(idx) {}
81  public:
82  using iterator_category = std::random_access_iterator_tag;
83  using value_type = ValueType;
84  using difference_type = ssize_t;
85  using pointer = ValueType*;
86  using reference = ValueType&;
87  public:
88  cbiterator();
89  ValueType& operator*() const { return _start[mask(_idx)].data; }
90  ValueType* operator->() const { return &operator*(); }
91  // prefix
92  cbiterator& operator++() {
93  ++_idx;
94  return *this;
95  }
96  // postfix
97  cbiterator operator++(int) {
98  auto v = *this;
99  ++_idx;
100  return v;
101  }
102  // prefix
103  cbiterator& operator--() {
104  --_idx;
105  return *this;
106  }
107  // postfix
108  cbiterator operator--(int) {
109  auto v = *this;
110  --_idx;
111  return v;
112  }
113  cbiterator operator+(difference_type n) const {
114  return cbiterator{_start, _idx + n};
115  }
116  friend cbiterator operator+(difference_type n, cbiterator i) {
117  return i + n;
118  }
119  cbiterator operator-(difference_type n) const {
120  return cbiterator{_start, _idx - n};
121  }
122  cbiterator& operator+=(difference_type n) {
123  _idx += n;
124  return *this;
125  }
126  cbiterator& operator-=(difference_type n) {
127  _idx -= n;
128  return *this;
129  }
130  bool operator==(const cbiterator& rhs) const {
131  return _idx == rhs._idx;
132  }
133  bool operator!=(const cbiterator& rhs) const {
134  return _idx != rhs._idx;
135  }
136  bool operator<(const cbiterator& rhs) const {
137  return ssize_t(_idx - rhs._idx) < 0;
138  }
139  bool operator>(const cbiterator& rhs) const {
140  return ssize_t(_idx - rhs._idx) > 0;
141  }
142  bool operator<=(const cbiterator& rhs) const {
143  return ssize_t(_idx - rhs._idx) <= 0;
144  }
145  bool operator>=(const cbiterator& rhs) const {
146  return ssize_t(_idx - rhs._idx) >= 0;
147  }
148  difference_type operator-(const cbiterator& rhs) const {
149  return _idx - rhs._idx;
150  }
151  friend class circular_buffer_fixed_capacity;
152  };
153 public:
154  using iterator = cbiterator<T>;
156 public:
157  circular_buffer_fixed_capacity() = default;
161  void push_front(const T& data);
162  void push_front(T&& data);
163  template <typename... A>
164  T& emplace_front(A&&... args);
165  void push_back(const T& data);
166  void push_back(T&& data);
167  template <typename... A>
168  T& emplace_back(A&&... args);
169  T& front();
170  T& back();
171  void pop_front();
172  void pop_back();
173  bool empty() const;
174  size_t size() const;
175  size_t capacity() const;
176  T& operator[](size_t idx);
177  void clear();
178  iterator begin() {
179  return iterator(_storage, _begin);
180  }
181  const_iterator begin() const {
182  return const_iterator(_storage, _begin);
183  }
184  iterator end() {
185  return iterator(_storage, _end);
186  }
187  const_iterator end() const {
188  return const_iterator(_storage, _end);
189  }
190  const_iterator cbegin() const {
191  return const_iterator(_storage, _begin);
192  }
193  const_iterator cend() const {
194  return const_iterator(_storage, _end);
195  }
196  iterator erase(iterator first, iterator last);
197 };
198 
199 template <typename T, size_t Capacity>
200 inline
201 bool
202 circular_buffer_fixed_capacity<T, Capacity>::empty() const {
203  return _begin == _end;
204 }
205 
206 template <typename T, size_t Capacity>
207 inline
208 size_t
209 circular_buffer_fixed_capacity<T, Capacity>::size() const {
210  return _end - _begin;
211 }
212 
213 template <typename T, size_t Capacity>
214 inline
215 size_t
216 circular_buffer_fixed_capacity<T, Capacity>::capacity() const {
217  return Capacity;
218 }
219 
220 template <typename T, size_t Capacity>
221 inline
222 circular_buffer_fixed_capacity<T, Capacity>::circular_buffer_fixed_capacity(circular_buffer_fixed_capacity&& x) noexcept
223  : _begin(x._begin), _end(x._end) {
224  // This is std::uninitialized_move, but that is c++17 only
225  auto dest = begin();
226  for (auto& obj : x) {
227  new (&*dest++) T(std::move(obj));
228  }
229 }
230 
231 template <typename T, size_t Capacity>
232 inline
233 circular_buffer_fixed_capacity<T, Capacity>&
234 circular_buffer_fixed_capacity<T, Capacity>::operator=(circular_buffer_fixed_capacity&& x) noexcept {
235  if (this != &x) {
236  this->~circular_buffer_fixed_capacity();
237  new (this) circular_buffer_fixed_capacity(std::move(x));
238  }
239  return *this;
240 }
241 
242 template <typename T, size_t Capacity>
243 inline
244 circular_buffer_fixed_capacity<T, Capacity>::~circular_buffer_fixed_capacity() {
245  clear();
246 }
247 
248 template <typename T, size_t Capacity>
249 inline
250 void
251 circular_buffer_fixed_capacity<T, Capacity>::push_front(const T& data) {
252  new (obj(_begin - 1)) T(data);
253  --_begin;
254 }
255 
256 template <typename T, size_t Capacity>
257 inline
258 void
259 circular_buffer_fixed_capacity<T, Capacity>::push_front(T&& data) {
260  new (obj(_begin - 1)) T(std::move(data));
261  --_begin;
262 }
263 
264 template <typename T, size_t Capacity>
265 template <typename... Args>
266 inline
267 T&
268 circular_buffer_fixed_capacity<T, Capacity>::emplace_front(Args&&... args) {
269  auto p = new (obj(_begin - 1)) T(std::forward<Args>(args)...);
270  --_begin;
271  return *p;
272 }
273 
274 template <typename T, size_t Capacity>
275 inline
276 void
277 circular_buffer_fixed_capacity<T, Capacity>::push_back(const T& data) {
278  new (obj(_end)) T(data);
279  ++_end;
280 }
281 
282 template <typename T, size_t Capacity>
283 inline
284 void
285 circular_buffer_fixed_capacity<T, Capacity>::push_back(T&& data) {
286  new (obj(_end)) T(std::move(data));
287  ++_end;
288 }
289 
290 template <typename T, size_t Capacity>
291 template <typename... Args>
292 inline
293 T&
294 circular_buffer_fixed_capacity<T, Capacity>::emplace_back(Args&&... args) {
295  auto p = new (obj(_end)) T(std::forward<Args>(args)...);
296  ++_end;
297  return *p;
298 }
299 
300 template <typename T, size_t Capacity>
301 inline
302 T&
303 circular_buffer_fixed_capacity<T, Capacity>::front() {
304  return *obj(_begin);
305 }
306 
307 template <typename T, size_t Capacity>
308 inline
309 T&
310 circular_buffer_fixed_capacity<T, Capacity>::back() {
311  return *obj(_end - 1);
312 }
313 
314 template <typename T, size_t Capacity>
315 inline
316 void
317 circular_buffer_fixed_capacity<T, Capacity>::pop_front() {
318  obj(_begin)->~T();
319  ++_begin;
320 }
321 
322 template <typename T, size_t Capacity>
323 inline
324 void
325 circular_buffer_fixed_capacity<T, Capacity>::pop_back() {
326  obj(_end - 1)->~T();
327  --_end;
328 }
329 
330 template <typename T, size_t Capacity>
331 inline
332 T&
333 circular_buffer_fixed_capacity<T, Capacity>::operator[](size_t idx) {
334  return *obj(_begin + idx);
335 }
336 
337 template <typename T, size_t Capacity>
338 inline
339 typename circular_buffer_fixed_capacity<T, Capacity>::iterator
340 circular_buffer_fixed_capacity<T, Capacity>::erase(iterator first, iterator last) {
341  static_assert(std::is_nothrow_move_assignable<T>::value, "erase() assumes move assignment does not throw");
342  if (first == last) {
343  return last;
344  }
345  // Move to the left or right depending on which would result in least amount of moves.
346  // This also guarantees that iterators will be stable when removing from either front or back.
347  if (std::distance(begin(), first) < std::distance(last, end())) {
348  auto new_start = std::move_backward(begin(), first, last);
349  auto i = begin();
350  while (i < new_start) {
351  *i++.~T();
352  }
353  _begin = new_start.idx;
354  return last;
355  } else {
356  auto new_end = std::move(last, end(), first);
357  auto i = new_end;
358  auto e = end();
359  while (i < e) {
360  *i++.~T();
361  }
362  _end = new_end.idx;
363  return first;
364  }
365 }
366 
367 template <typename T, size_t Capacity>
368 inline
369 void
370 circular_buffer_fixed_capacity<T, Capacity>::clear() {
371  for (auto& obj : *this) {
372  obj.~T();
373  }
374  _begin = _end = 0;
375 }
376 
377 }
378 
seastar
Seastar API namespace.
Definition: abort_on_ebadf.hh:24
seastar::circular_buffer_fixed_capacity
Definition: circular_buffer_fixed_capacity.hh:49
seastar::circular_buffer_fixed_capacity::cbiterator
Definition: circular_buffer_fixed_capacity.hh:75