1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
3 * This file is open source software, licensed to you under the terms
4 * of the Apache License, Version 2.0 (the "License"). See the NOTICE file
5 * distributed with this work for additional information regarding copyright
6 * ownership. You may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
10 * http://www.apache.org/licenses/LICENSE-2.0
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
20 * Copyright (C) 2014 Cloudius Systems, Ltd.
23 #ifndef CEPH_CIRCULAR_BUFFER_HH_
24 #define CEPH_CIRCULAR_BUFFER_HH_
26 // A growable double-ended queue container that can be efficiently
27 // extended (and shrunk) from both ends. Implementation is a single
30 // Similar to libstdc++'s std::deque, except that it uses a single level
31 // store, and so is more efficient for simple stored items.
32 // Similar to boost::circular_buffer_space_optimized, except it uses
33 // uninitialized storage for unoccupied elements (and thus move/copy
34 // constructors instead of move/copy assignments, which are less efficient).
41 template <typename T, typename Alloc = std::allocator<T>>
42 class circular_buffer {
45 // begin, end interpreted (mod capacity)
53 using size_type = size_t;
56 using const_reference = const T&;
57 using const_pointer = const T*;
59 circular_buffer() = default;
60 circular_buffer(circular_buffer&& X);
61 circular_buffer(const circular_buffer& X) = delete;
63 circular_buffer& operator=(const circular_buffer&) = delete;
64 circular_buffer& operator=(circular_buffer&&) = delete;
65 void push_front(const T& data);
66 void push_front(T&& data);
67 template <typename... A>
68 void emplace_front(A&&... args);
69 void push_back(const T& data);
70 void push_back(T&& data);
71 template <typename... A>
72 void emplace_back(A&&... args);
79 size_t capacity() const;
80 T& operator[](size_t idx);
81 template <typename Func>
82 void for_each(Func func);
83 // access an element, may return wrong or destroyed element
84 // only useful if you do not rely on data accuracy (e.g. prefetch)
85 T& access_element_unsafe(size_t idx);
88 void maybe_expand(size_t nr = 1);
89 size_t mask(size_t idx) const;
91 template<typename CB, typename ValueType>
92 struct cbiterator : std::iterator<std::random_access_iterator_tag, ValueType> {
93 typedef std::iterator<std::random_access_iterator_tag, ValueType> super_t;
95 ValueType& operator*() const { return cb->_impl.storage[cb->mask(idx)]; }
96 ValueType* operator->() const { return &cb->_impl.storage[cb->mask(idx)]; }
98 cbiterator<CB, ValueType>& operator++() {
103 cbiterator<CB, ValueType> operator++(int unused) {
109 cbiterator<CB, ValueType>& operator--() {
114 cbiterator<CB, ValueType> operator--(int unused) {
119 cbiterator<CB, ValueType> operator+(typename super_t::difference_type n) const {
120 return cbiterator<CB, ValueType>(cb, idx + n);
122 cbiterator<CB, ValueType> operator-(typename super_t::difference_type n) const {
123 return cbiterator<CB, ValueType>(cb, idx - n);
125 cbiterator<CB, ValueType>& operator+=(typename super_t::difference_type n) {
129 cbiterator<CB, ValueType>& operator-=(typename super_t::difference_type n) {
133 bool operator==(const cbiterator<CB, ValueType>& rhs) const {
134 return idx == rhs.idx;
136 bool operator!=(const cbiterator<CB, ValueType>& rhs) const {
137 return idx != rhs.idx;
139 bool operator<(const cbiterator<CB, ValueType>& rhs) const {
140 return idx < rhs.idx;
142 bool operator>(const cbiterator<CB, ValueType>& rhs) const {
143 return idx > rhs.idx;
145 bool operator>=(const cbiterator<CB, ValueType>& rhs) const {
146 return idx >= rhs.idx;
148 bool operator<=(const cbiterator<CB, ValueType>& rhs) const {
149 return idx <= rhs.idx;
151 typename super_t::difference_type operator-(const cbiterator<CB, ValueType>& rhs) const {
152 return idx - rhs.idx;
157 cbiterator<CB, ValueType>(CB* b, size_t i) : cb(b), idx(i) {}
158 friend class circular_buffer;
160 friend class iterator;
163 typedef cbiterator<circular_buffer, T> iterator;
164 typedef cbiterator<const circular_buffer, const T> const_iterator;
167 return iterator(this, _impl.begin);
169 const_iterator begin() const {
170 return const_iterator(this, _impl.begin);
173 return iterator(this, _impl.end);
175 const_iterator end() const {
176 return const_iterator(this, _impl.end);
178 const_iterator cbegin() const {
179 return const_iterator(this, _impl.begin);
181 const_iterator cend() const {
182 return const_iterator(this, _impl.end);
186 template <typename T, typename Alloc>
187 inline size_t circular_buffer<T, Alloc>::mask(size_t idx) const {
188 return idx & (_impl.capacity - 1);
191 template <typename T, typename Alloc>
192 inline bool circular_buffer<T, Alloc>::empty() const {
193 return _impl.begin == _impl.end;
196 template <typename T, typename Alloc>
197 inline size_t circular_buffer<T, Alloc>::size() const {
198 return _impl.end - _impl.begin;
201 template <typename T, typename Alloc>
202 inline size_t circular_buffer<T, Alloc>::capacity() const {
203 return _impl.capacity;
206 template <typename T, typename Alloc>
207 inline circular_buffer<T, Alloc>::circular_buffer(circular_buffer&& x)
208 : _impl(std::move(x._impl)) {
212 template <typename T, typename Alloc>
213 template <typename Func>
214 inline void circular_buffer<T, Alloc>::for_each(Func func) {
215 auto s = _impl.storage;
216 auto m = _impl.capacity - 1;
217 for (auto i = _impl.begin; i != _impl.end; ++i) {
222 template <typename T, typename Alloc>
223 inline circular_buffer<T, Alloc>::~circular_buffer() {
224 for_each([this] (T& obj) {
227 _impl.deallocate(_impl.storage, _impl.capacity);
230 template <typename T, typename Alloc>
231 void circular_buffer<T, Alloc>::expand() {
232 auto new_cap = std::max<size_t>(_impl.capacity * 2, 1);
233 auto new_storage = _impl.allocate(new_cap);
234 auto p = new_storage;
236 for_each([this, &p] (T& obj) {
237 transfer_pass1(_impl, &obj, p);
241 while (p != new_storage) {
244 _impl.deallocate(new_storage, new_cap);
248 for_each([this, &p] (T& obj) {
249 transfer_pass2(_impl, &obj, p++);
251 std::swap(_impl.storage, new_storage);
252 std::swap(_impl.capacity, new_cap);
254 _impl.end = p - _impl.storage;
255 _impl.deallocate(new_storage, new_cap);
258 template <typename T, typename Alloc>
259 inline void circular_buffer<T, Alloc>::maybe_expand(size_t nr) {
260 if (_impl.end - _impl.begin + nr > _impl.capacity) {
265 template <typename T, typename Alloc>
266 inline void circular_buffer<T, Alloc>::push_front(const T& data) {
268 auto p = &_impl.storage[mask(_impl.begin - 1)];
269 _impl.construct(p, data);
273 template <typename T, typename Alloc>
274 inline void circular_buffer<T, Alloc>::push_front(T&& data) {
276 auto p = &_impl.storage[mask(_impl.begin - 1)];
277 _impl.construct(p, std::move(data));
281 template <typename T, typename Alloc>
282 template <typename... Args>
283 inline void circular_buffer<T, Alloc>::emplace_front(Args&&... args) {
285 auto p = &_impl.storage[mask(_impl.begin - 1)];
286 _impl.construct(p, std::forward<Args>(args)...);
290 template <typename T, typename Alloc>
291 inline void circular_buffer<T, Alloc>::push_back(const T& data) {
293 auto p = &_impl.storage[mask(_impl.end)];
294 _impl.construct(p, data);
298 template <typename T, typename Alloc>
299 inline void circular_buffer<T, Alloc>::push_back(T&& data) {
301 auto p = &_impl.storage[mask(_impl.end)];
302 _impl.construct(p, std::move(data));
306 template <typename T, typename Alloc>
307 template <typename... Args>
308 inline void circular_buffer<T, Alloc>::emplace_back(Args&&... args) {
310 auto p = &_impl.storage[mask(_impl.end)];
311 _impl.construct(p, std::forward<Args>(args)...);
315 template <typename T, typename Alloc>
316 inline T& circular_buffer<T, Alloc>::front() {
317 return _impl.storage[mask(_impl.begin)];
320 template <typename T, typename Alloc>
321 inline T& circular_buffer<T, Alloc>::back() {
322 return _impl.storage[mask(_impl.end - 1)];
325 template <typename T, typename Alloc>
326 inline void circular_buffer<T, Alloc>::pop_front() {
327 _impl.destroy(&front());
331 template <typename T, typename Alloc>
332 inline void circular_buffer<T, Alloc>::pop_back() {
333 _impl.destroy(&back());
337 template <typename T, typename Alloc>
338 inline T& circular_buffer<T, Alloc>::operator[](size_t idx) {
339 return _impl.storage[mask(_impl.begin + idx)];
342 template <typename T, typename Alloc>
343 inline T& circular_buffer<T, Alloc>::access_element_unsafe(size_t idx) {
344 return _impl.storage[mask(_impl.begin + idx)];
347 #endif /* CEPH_CIRCULAR_BUFFER_HH_ */