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_ */