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.
7 * You may obtain a copy of the License at
9 * http://www.apache.org/licenses/LICENSE-2.0
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
19 * Copyright (C) 2017 ScyllaDB
24 // A fixed capacity double-ended queue container that can be efficiently
25 // extended (and shrunk) from both ends. Implementation is a single
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.
31 #include <type_traits>
41 /// A fixed-capacity container (like boost::static_vector) that can insert
42 /// and remove at both ends (like std::deque). Does not allocate.
44 /// Does not perform overflow checking when size exceeds capacity.
46 /// \tparam T type of objects stored in the container; must be noexcept move enabled
47 /// \tparam Capacity maximum number of objects that can be stored in the container; must be a power of 2
48 template <typename T, size_t Capacity>
49 class circular_buffer_fixed_capacity {
54 maybe_storage() noexcept {}
57 maybe_storage _storage[Capacity];
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; }
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");
67 using size_type = size_t;
70 using const_reference = const T&;
71 using const_pointer = const T*;
72 using difference_type = ssize_t;
74 template <typename ValueType>
76 using holder = std::conditional_t<std::is_const<ValueType>::value, const maybe_storage, maybe_storage>;
80 cbiterator(holder* start, size_t idx) noexcept : _start(start), _idx(idx) {}
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&;
89 ValueType& operator*() const { return _start[mask(_idx)].data; }
90 ValueType* operator->() const { return &operator*(); }
92 cbiterator& operator++() {
97 cbiterator operator++(int) {
103 cbiterator& operator--() {
108 cbiterator operator--(int) {
113 cbiterator operator+(difference_type n) const {
114 return cbiterator{_start, _idx + n};
116 friend cbiterator operator+(difference_type n, cbiterator i) {
119 cbiterator operator-(difference_type n) const {
120 return cbiterator{_start, _idx - n};
122 cbiterator& operator+=(difference_type n) {
126 cbiterator& operator-=(difference_type n) {
130 bool operator==(const cbiterator& rhs) const {
131 return _idx == rhs._idx;
133 bool operator!=(const cbiterator& rhs) const {
134 return _idx != rhs._idx;
136 bool operator<(const cbiterator& rhs) const {
137 return ssize_t(_idx - rhs._idx) < 0;
139 bool operator>(const cbiterator& rhs) const {
140 return ssize_t(_idx - rhs._idx) > 0;
142 bool operator<=(const cbiterator& rhs) const {
143 return ssize_t(_idx - rhs._idx) <= 0;
145 bool operator>=(const cbiterator& rhs) const {
146 return ssize_t(_idx - rhs._idx) >= 0;
148 difference_type operator-(const cbiterator& rhs) const {
149 return _idx - rhs._idx;
151 friend class circular_buffer_fixed_capacity;
154 using iterator = cbiterator<T>;
155 using const_iterator = cbiterator<const T>;
157 circular_buffer_fixed_capacity() = default;
158 circular_buffer_fixed_capacity(circular_buffer_fixed_capacity&& x) noexcept;
159 ~circular_buffer_fixed_capacity();
160 circular_buffer_fixed_capacity& operator=(circular_buffer_fixed_capacity&& x) noexcept;
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);
175 size_t capacity() const;
176 T& operator[](size_t idx);
179 return iterator(_storage, _begin);
181 const_iterator begin() const {
182 return const_iterator(_storage, _begin);
185 return iterator(_storage, _end);
187 const_iterator end() const {
188 return const_iterator(_storage, _end);
190 const_iterator cbegin() const {
191 return const_iterator(_storage, _begin);
193 const_iterator cend() const {
194 return const_iterator(_storage, _end);
196 iterator erase(iterator first, iterator last);
199 template <typename T, size_t Capacity>
202 circular_buffer_fixed_capacity<T, Capacity>::empty() const {
203 return _begin == _end;
206 template <typename T, size_t Capacity>
209 circular_buffer_fixed_capacity<T, Capacity>::size() const {
210 return _end - _begin;
213 template <typename T, size_t Capacity>
216 circular_buffer_fixed_capacity<T, Capacity>::capacity() const {
220 template <typename T, size_t Capacity>
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
226 for (auto& obj : x) {
227 new (&*dest++) T(std::move(obj));
231 template <typename T, size_t Capacity>
233 circular_buffer_fixed_capacity<T, Capacity>&
234 circular_buffer_fixed_capacity<T, Capacity>::operator=(circular_buffer_fixed_capacity&& x) noexcept {
236 this->~circular_buffer_fixed_capacity();
237 new (this) circular_buffer_fixed_capacity(std::move(x));
242 template <typename T, size_t Capacity>
244 circular_buffer_fixed_capacity<T, Capacity>::~circular_buffer_fixed_capacity() {
248 template <typename T, size_t Capacity>
251 circular_buffer_fixed_capacity<T, Capacity>::push_front(const T& data) {
252 new (obj(_begin - 1)) T(data);
256 template <typename T, size_t Capacity>
259 circular_buffer_fixed_capacity<T, Capacity>::push_front(T&& data) {
260 new (obj(_begin - 1)) T(std::move(data));
264 template <typename T, size_t Capacity>
265 template <typename... Args>
268 circular_buffer_fixed_capacity<T, Capacity>::emplace_front(Args&&... args) {
269 auto p = new (obj(_begin - 1)) T(std::forward<Args>(args)...);
274 template <typename T, size_t Capacity>
277 circular_buffer_fixed_capacity<T, Capacity>::push_back(const T& data) {
278 new (obj(_end)) T(data);
282 template <typename T, size_t Capacity>
285 circular_buffer_fixed_capacity<T, Capacity>::push_back(T&& data) {
286 new (obj(_end)) T(std::move(data));
290 template <typename T, size_t Capacity>
291 template <typename... Args>
294 circular_buffer_fixed_capacity<T, Capacity>::emplace_back(Args&&... args) {
295 auto p = new (obj(_end)) T(std::forward<Args>(args)...);
300 template <typename T, size_t Capacity>
303 circular_buffer_fixed_capacity<T, Capacity>::front() {
307 template <typename T, size_t Capacity>
310 circular_buffer_fixed_capacity<T, Capacity>::back() {
311 return *obj(_end - 1);
314 template <typename T, size_t Capacity>
317 circular_buffer_fixed_capacity<T, Capacity>::pop_front() {
322 template <typename T, size_t Capacity>
325 circular_buffer_fixed_capacity<T, Capacity>::pop_back() {
330 template <typename T, size_t Capacity>
333 circular_buffer_fixed_capacity<T, Capacity>::operator[](size_t idx) {
334 return *obj(_begin + idx);
337 template <typename T, size_t Capacity>
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");
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);
350 while (i < new_start) {
353 _begin = new_start.idx;
356 auto new_end = std::move(last, end(), first);
367 template <typename T, size_t Capacity>
370 circular_buffer_fixed_capacity<T, Capacity>::clear() {
371 for (auto& obj : *this) {