]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | /* | |
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. | |
7 | * | |
8 | * You may obtain a copy of the License at | |
9 | * | |
10 | * http://www.apache.org/licenses/LICENSE-2.0 | |
11 | * | |
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 | |
17 | * under the License. | |
18 | */ | |
19 | /* | |
20 | * Copyright (C) 2014 Cloudius Systems, Ltd. | |
21 | */ | |
22 | ||
23 | #ifndef CEPH_CIRCULAR_BUFFER_HH_ | |
24 | #define CEPH_CIRCULAR_BUFFER_HH_ | |
25 | ||
26 | // A growable double-ended queue container that can be efficiently | |
27 | // extended (and shrunk) from both ends. Implementation is a single | |
28 | // storage vector. | |
29 | // | |
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). | |
35 | ||
36 | #include <memory> | |
37 | #include <algorithm> | |
38 | ||
39 | #include "transfer.h" | |
40 | ||
41 | template <typename T, typename Alloc = std::allocator<T>> | |
42 | class circular_buffer { | |
43 | struct impl : Alloc { | |
44 | T* storage = nullptr; | |
45 | // begin, end interpreted (mod capacity) | |
46 | size_t begin = 0; | |
47 | size_t end = 0; | |
48 | size_t capacity = 0; | |
49 | }; | |
50 | impl _impl; | |
51 | public: | |
52 | using value_type = T; | |
53 | using size_type = size_t; | |
54 | using reference = T&; | |
55 | using pointer = T*; | |
56 | using const_reference = const T&; | |
57 | using const_pointer = const T*; | |
58 | public: | |
59 | circular_buffer() = default; | |
60 | circular_buffer(circular_buffer&& X); | |
61 | circular_buffer(const circular_buffer& X) = delete; | |
62 | ~circular_buffer(); | |
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); | |
73 | T& front(); | |
74 | T& back(); | |
75 | void pop_front(); | |
76 | void pop_back(); | |
77 | bool empty() const; | |
78 | size_t size() const; | |
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); | |
86 | private: | |
87 | void expand(); | |
88 | void maybe_expand(size_t nr = 1); | |
89 | size_t mask(size_t idx) const; | |
90 | ||
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; | |
94 | ||
95 | ValueType& operator*() const { return cb->_impl.storage[cb->mask(idx)]; } | |
96 | ValueType* operator->() const { return &cb->_impl.storage[cb->mask(idx)]; } | |
97 | // prefix | |
98 | cbiterator<CB, ValueType>& operator++() { | |
99 | idx++; | |
100 | return *this; | |
101 | } | |
102 | // postfix | |
103 | cbiterator<CB, ValueType> operator++(int unused) { | |
104 | auto v = *this; | |
105 | idx++; | |
106 | return v; | |
107 | } | |
108 | // prefix | |
109 | cbiterator<CB, ValueType>& operator--() { | |
110 | idx--; | |
111 | return *this; | |
112 | } | |
113 | // postfix | |
114 | cbiterator<CB, ValueType> operator--(int unused) { | |
115 | auto v = *this; | |
116 | idx--; | |
117 | return v; | |
118 | } | |
119 | cbiterator<CB, ValueType> operator+(typename super_t::difference_type n) const { | |
120 | return cbiterator<CB, ValueType>(cb, idx + n); | |
121 | } | |
122 | cbiterator<CB, ValueType> operator-(typename super_t::difference_type n) const { | |
123 | return cbiterator<CB, ValueType>(cb, idx - n); | |
124 | } | |
125 | cbiterator<CB, ValueType>& operator+=(typename super_t::difference_type n) { | |
126 | idx += n; | |
127 | return *this; | |
128 | } | |
129 | cbiterator<CB, ValueType>& operator-=(typename super_t::difference_type n) { | |
130 | idx -= n; | |
131 | return *this; | |
132 | } | |
133 | bool operator==(const cbiterator<CB, ValueType>& rhs) const { | |
134 | return idx == rhs.idx; | |
135 | } | |
136 | bool operator!=(const cbiterator<CB, ValueType>& rhs) const { | |
137 | return idx != rhs.idx; | |
138 | } | |
139 | bool operator<(const cbiterator<CB, ValueType>& rhs) const { | |
140 | return idx < rhs.idx; | |
141 | } | |
142 | bool operator>(const cbiterator<CB, ValueType>& rhs) const { | |
143 | return idx > rhs.idx; | |
144 | } | |
145 | bool operator>=(const cbiterator<CB, ValueType>& rhs) const { | |
146 | return idx >= rhs.idx; | |
147 | } | |
148 | bool operator<=(const cbiterator<CB, ValueType>& rhs) const { | |
149 | return idx <= rhs.idx; | |
150 | } | |
151 | typename super_t::difference_type operator-(const cbiterator<CB, ValueType>& rhs) const { | |
152 | return idx - rhs.idx; | |
153 | } | |
154 | private: | |
155 | CB* cb; | |
156 | size_t idx; | |
157 | cbiterator<CB, ValueType>(CB* b, size_t i) : cb(b), idx(i) {} | |
158 | friend class circular_buffer; | |
159 | }; | |
160 | friend class iterator; | |
161 | ||
162 | public: | |
163 | typedef cbiterator<circular_buffer, T> iterator; | |
164 | typedef cbiterator<const circular_buffer, const T> const_iterator; | |
165 | ||
166 | iterator begin() { | |
167 | return iterator(this, _impl.begin); | |
168 | } | |
169 | const_iterator begin() const { | |
170 | return const_iterator(this, _impl.begin); | |
171 | } | |
172 | iterator end() { | |
173 | return iterator(this, _impl.end); | |
174 | } | |
175 | const_iterator end() const { | |
176 | return const_iterator(this, _impl.end); | |
177 | } | |
178 | const_iterator cbegin() const { | |
179 | return const_iterator(this, _impl.begin); | |
180 | } | |
181 | const_iterator cend() const { | |
182 | return const_iterator(this, _impl.end); | |
183 | } | |
184 | }; | |
185 | ||
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); | |
189 | } | |
190 | ||
191 | template <typename T, typename Alloc> | |
192 | inline bool circular_buffer<T, Alloc>::empty() const { | |
193 | return _impl.begin == _impl.end; | |
194 | } | |
195 | ||
196 | template <typename T, typename Alloc> | |
197 | inline size_t circular_buffer<T, Alloc>::size() const { | |
198 | return _impl.end - _impl.begin; | |
199 | } | |
200 | ||
201 | template <typename T, typename Alloc> | |
202 | inline size_t circular_buffer<T, Alloc>::capacity() const { | |
203 | return _impl.capacity; | |
204 | } | |
205 | ||
206 | template <typename T, typename Alloc> | |
207 | inline circular_buffer<T, Alloc>::circular_buffer(circular_buffer&& x) | |
208 | : _impl(std::move(x._impl)) { | |
209 | x._impl = {}; | |
210 | } | |
211 | ||
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) { | |
218 | func(s[i & m]); | |
219 | } | |
220 | } | |
221 | ||
222 | template <typename T, typename Alloc> | |
223 | inline circular_buffer<T, Alloc>::~circular_buffer() { | |
224 | for_each([this] (T& obj) { | |
225 | _impl.destroy(&obj); | |
226 | }); | |
227 | _impl.deallocate(_impl.storage, _impl.capacity); | |
228 | } | |
229 | ||
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; | |
235 | try { | |
236 | for_each([this, &p] (T& obj) { | |
237 | transfer_pass1(_impl, &obj, p); | |
238 | p++; | |
239 | }); | |
240 | } catch (...) { | |
241 | while (p != new_storage) { | |
242 | _impl.destroy(--p); | |
243 | } | |
244 | _impl.deallocate(new_storage, new_cap); | |
245 | throw; | |
246 | } | |
247 | p = new_storage; | |
248 | for_each([this, &p] (T& obj) { | |
249 | transfer_pass2(_impl, &obj, p++); | |
250 | }); | |
251 | std::swap(_impl.storage, new_storage); | |
252 | std::swap(_impl.capacity, new_cap); | |
253 | _impl.begin = 0; | |
254 | _impl.end = p - _impl.storage; | |
255 | _impl.deallocate(new_storage, new_cap); | |
256 | } | |
257 | ||
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) { | |
261 | expand(); | |
262 | } | |
263 | } | |
264 | ||
265 | template <typename T, typename Alloc> | |
266 | inline void circular_buffer<T, Alloc>::push_front(const T& data) { | |
267 | maybe_expand(); | |
268 | auto p = &_impl.storage[mask(_impl.begin - 1)]; | |
269 | _impl.construct(p, data); | |
270 | --_impl.begin; | |
271 | } | |
272 | ||
273 | template <typename T, typename Alloc> | |
274 | inline void circular_buffer<T, Alloc>::push_front(T&& data) { | |
275 | maybe_expand(); | |
276 | auto p = &_impl.storage[mask(_impl.begin - 1)]; | |
277 | _impl.construct(p, std::move(data)); | |
278 | --_impl.begin; | |
279 | } | |
280 | ||
281 | template <typename T, typename Alloc> | |
282 | template <typename... Args> | |
283 | inline void circular_buffer<T, Alloc>::emplace_front(Args&&... args) { | |
284 | maybe_expand(); | |
285 | auto p = &_impl.storage[mask(_impl.begin - 1)]; | |
286 | _impl.construct(p, std::forward<Args>(args)...); | |
287 | --_impl.begin; | |
288 | } | |
289 | ||
290 | template <typename T, typename Alloc> | |
291 | inline void circular_buffer<T, Alloc>::push_back(const T& data) { | |
292 | maybe_expand(); | |
293 | auto p = &_impl.storage[mask(_impl.end)]; | |
294 | _impl.construct(p, data); | |
295 | ++_impl.end; | |
296 | } | |
297 | ||
298 | template <typename T, typename Alloc> | |
299 | inline void circular_buffer<T, Alloc>::push_back(T&& data) { | |
300 | maybe_expand(); | |
301 | auto p = &_impl.storage[mask(_impl.end)]; | |
302 | _impl.construct(p, std::move(data)); | |
303 | ++_impl.end; | |
304 | } | |
305 | ||
306 | template <typename T, typename Alloc> | |
307 | template <typename... Args> | |
308 | inline void circular_buffer<T, Alloc>::emplace_back(Args&&... args) { | |
309 | maybe_expand(); | |
310 | auto p = &_impl.storage[mask(_impl.end)]; | |
311 | _impl.construct(p, std::forward<Args>(args)...); | |
312 | ++_impl.end; | |
313 | } | |
314 | ||
315 | template <typename T, typename Alloc> | |
316 | inline T& circular_buffer<T, Alloc>::front() { | |
317 | return _impl.storage[mask(_impl.begin)]; | |
318 | } | |
319 | ||
320 | template <typename T, typename Alloc> | |
321 | inline T& circular_buffer<T, Alloc>::back() { | |
322 | return _impl.storage[mask(_impl.end - 1)]; | |
323 | } | |
324 | ||
325 | template <typename T, typename Alloc> | |
326 | inline void circular_buffer<T, Alloc>::pop_front() { | |
327 | _impl.destroy(&front()); | |
328 | ++_impl.begin; | |
329 | } | |
330 | ||
331 | template <typename T, typename Alloc> | |
332 | inline void circular_buffer<T, Alloc>::pop_back() { | |
333 | _impl.destroy(&back()); | |
334 | --_impl.end; | |
335 | } | |
336 | ||
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)]; | |
340 | } | |
341 | ||
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)]; | |
345 | } | |
346 | ||
347 | #endif /* CEPH_CIRCULAR_BUFFER_HH_ */ |