]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
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) 2016 ScyllaDB Ltd. | |
20 | */ | |
21 | ||
22 | #pragma once | |
23 | ||
24 | #include <memory> | |
25 | #include <algorithm> | |
26 | ||
27 | namespace seastar { | |
28 | ||
29 | // An unbounded FIFO queue of objects of type T. | |
30 | // | |
31 | // It provides operations to push items in one end of the queue, and pop them | |
32 | // from the other end of the queue - both operations are guaranteed O(1) | |
33 | // (not just amortized O(1)). The size() operation is also O(1). | |
34 | // chunked_fifo also guarantees that the largest contiguous memory allocation | |
35 | // it does is O(1). The total memory used is, of course, O(N). | |
36 | // | |
37 | // How does chunked_fifo differ from std::list<>, circular_buffer<> and | |
38 | // std::deque()? | |
39 | // | |
40 | // std::list<> can also make all the above guarantees, but is inefficient - | |
41 | // both at run speed (every operation requires an allocation), and in memory | |
42 | // use. Much more efficient than std::list<> is our circular_buffer<>, which | |
43 | // allocates a contiguous array to hold the items and only reallocates it, | |
44 | // exponentially, when the queue grows. On one test of several different | |
45 | // push/pop scenarios, circular_buffer<> was between 5 and 20 times faster | |
46 | // than std::list, and also used considerably less memory. | |
47 | // The problem with circular_buffer<> is that gives up on the last guarantee | |
48 | // we made above: circular_buffer<> allocates all the items in one large | |
49 | // contiguous allocation - that might not be possible when the memory is | |
50 | // highly fragmented. | |
51 | // std::deque<> aims to solve the contiguous allocation problem by allocating | |
52 | // smaller chunks of the queue, and keeping a list of them in an array. This | |
53 | // array is necessary to allow for O(1) random access to any element, a | |
54 | // feature which we do not need; But this array is itself contiguous so | |
55 | // std::deque<> attempts larger contiguous allocations the larger the queue | |
56 | // gets: std::deque<>'s contiguous allocation is still O(N) and in fact | |
57 | // exactly 1/64 of the size of circular_buffer<>'s contiguous allocation. | |
58 | // So it's an improvement over circular_buffer<>, but not a full solution. | |
59 | // | |
60 | // chunked_fifo<> is such a solution: it also allocates the queue in fixed- | |
61 | // size chunks (just like std::deque) but holds them in a linked list, not | |
62 | // a contiguous array, so there are no large contiguous allocations. | |
63 | // | |
64 | // Unlike std::deque<> or circular_buffer<>, chunked_fifo only provides the | |
65 | // operations needed by std::queue, i.e.,: empty(), size(), front(), back(), | |
66 | // push_back() and pop_front(). For simplicity, we do *not* implement other | |
67 | // possible operations, like inserting or deleting elements from the "wrong" | |
68 | // side of the queue or from the middle, nor random-access to items in the | |
9f95a23c TL |
69 | // middle of the queue. However, chunked_fifo does allow iterating over all |
70 | // of the queue's elements without popping them, a feature which std::queue | |
71 | // is missing. | |
11fdf7f2 TL |
72 | // |
73 | // Another feature of chunked_fifo which std::deque is missing is the ability | |
74 | // to control the chunk size, as a template parameter. In std::deque the | |
75 | // chunk size is undocumented and fixed - in gcc, it is always 512 bytes. | |
76 | // chunked_fifo, on the other hand, makes the chunk size (in number of items | |
77 | // instead of bytes) a template parameter; In situations where the queue is | |
78 | // expected to become very long, using a larger chunk size might make sense | |
79 | // because it will result in fewer allocations. | |
80 | // | |
81 | // chunked_fifo uses uninitialized storage for unoccupied elements, and thus | |
82 | // uses move/copy constructors instead of move/copy assignments, which are | |
83 | // less efficient. | |
84 | ||
85 | template <typename T, size_t items_per_chunk = 128> | |
86 | class chunked_fifo { | |
87 | static_assert((items_per_chunk & (items_per_chunk - 1)) == 0, | |
88 | "chunked_fifo chunk size must be power of two"); | |
89 | union maybe_item { | |
90 | maybe_item() noexcept {} | |
91 | ~maybe_item() {} | |
92 | T data; | |
93 | }; | |
94 | struct chunk { | |
95 | maybe_item items[items_per_chunk]; | |
96 | struct chunk* next; | |
97 | // begin and end interpreted mod items_per_chunk | |
98 | unsigned begin; | |
99 | unsigned end; | |
100 | }; | |
101 | // We pop from the chunk at _front_chunk. This chunk is then linked to | |
102 | // the following chunks via the "next" link. _back_chunk points to the | |
103 | // last chunk in this list, and it is where we push. | |
104 | chunk* _front_chunk = nullptr; // where we pop | |
105 | chunk* _back_chunk = nullptr; // where we push | |
106 | // We want an O(1) size but don't want to maintain a size() counter | |
107 | // because this will slow down every push and pop operation just for | |
108 | // the rare size() call. Instead, we just keep a count of chunks (which | |
109 | // doesn't change on every push or pop), from which we can calculate | |
110 | // size() when needed, and still be O(1). | |
111 | // This assumes the invariant that all middle chunks (except the front | |
112 | // and back) are always full. | |
113 | size_t _nchunks = 0; | |
114 | // A list of freed chunks, to support reserve() and to improve | |
115 | // performance of repeated push and pop, especially on an empty queue. | |
116 | // It is a performance/memory tradeoff how many freed chunks to keep | |
117 | // here (see save_free_chunks constant below). | |
118 | chunk* _free_chunks = nullptr; | |
119 | size_t _nfree_chunks = 0; | |
120 | public: | |
121 | using value_type = T; | |
122 | using size_type = size_t; | |
123 | using reference = T&; | |
124 | using pointer = T*; | |
125 | using const_reference = const T&; | |
126 | using const_pointer = const T*; | |
9f95a23c TL |
127 | |
128 | private: | |
129 | template <typename U> | |
130 | class basic_iterator { | |
131 | friend class chunked_fifo; | |
132 | ||
133 | public: | |
134 | using iterator_category = std::forward_iterator_tag; | |
135 | using difference_type = std::ptrdiff_t; | |
136 | using value_type = U; | |
137 | using pointer = U*; | |
138 | using reference = U&; | |
139 | ||
140 | protected: | |
141 | chunk* _chunk = nullptr; | |
142 | size_t _item_index = 0; | |
143 | ||
144 | protected: | |
145 | inline explicit basic_iterator(chunk* c); | |
146 | inline basic_iterator(chunk* c, size_t item_index); | |
147 | ||
148 | public: | |
149 | inline bool operator==(const basic_iterator& o) const; | |
150 | inline bool operator!=(const basic_iterator& o) const; | |
151 | inline pointer operator->() const; | |
152 | inline reference operator*() const; | |
153 | inline basic_iterator operator++(int); | |
154 | basic_iterator& operator++(); | |
155 | }; | |
156 | ||
157 | public: | |
158 | class iterator : public basic_iterator<T> { | |
159 | using basic_iterator<T>::basic_iterator; | |
160 | public: | |
161 | iterator() = default; | |
162 | }; | |
163 | class const_iterator : public basic_iterator<const T> { | |
164 | using basic_iterator<T>::basic_iterator; | |
165 | public: | |
166 | const_iterator() = default; | |
167 | inline const_iterator(iterator o); | |
168 | }; | |
169 | ||
11fdf7f2 TL |
170 | public: |
171 | chunked_fifo() = default; | |
172 | chunked_fifo(chunked_fifo&& x) noexcept; | |
173 | chunked_fifo(const chunked_fifo& X) = delete; | |
174 | ~chunked_fifo(); | |
175 | chunked_fifo& operator=(const chunked_fifo&) = delete; | |
176 | chunked_fifo& operator=(chunked_fifo&&) noexcept; | |
177 | inline void push_back(const T& data); | |
178 | inline void push_back(T&& data); | |
179 | T& back(); | |
180 | const T& back() const; | |
181 | template <typename... A> | |
182 | inline void emplace_back(A&&... args); | |
183 | inline T& front() const noexcept; | |
184 | inline void pop_front() noexcept; | |
185 | inline bool empty() const noexcept; | |
186 | inline size_t size() const noexcept; | |
187 | void clear() noexcept; | |
188 | // reserve(n) ensures that at least (n - size()) further push() calls can | |
189 | // be served without needing new memory allocation. | |
190 | // Calling pop()s between these push()es is also allowed and does not | |
191 | // alter this guarantee. | |
192 | // Note that reserve() does not reduce the amount of memory already | |
193 | // reserved - use shrink_to_fit() for that. | |
194 | void reserve(size_t n); | |
195 | // shrink_to_fit() frees memory held, but unused, by the queue. Such | |
196 | // unused memory might exist after pops, or because of reserve(). | |
197 | void shrink_to_fit(); | |
9f95a23c TL |
198 | inline iterator begin(); |
199 | inline iterator end(); | |
200 | inline const_iterator begin() const; | |
201 | inline const_iterator end() const; | |
202 | inline const_iterator cbegin() const; | |
203 | inline const_iterator cend() const; | |
11fdf7f2 TL |
204 | private: |
205 | void back_chunk_new(); | |
206 | void front_chunk_delete() noexcept; | |
207 | inline void ensure_room_back(); | |
208 | void undo_room_back(); | |
9f95a23c | 209 | static inline size_t mask(size_t idx) noexcept; |
11fdf7f2 TL |
210 | |
211 | }; | |
212 | ||
9f95a23c TL |
213 | template <typename T, size_t items_per_chunk> |
214 | template <typename U> | |
215 | inline | |
216 | chunked_fifo<T, items_per_chunk>::basic_iterator<U>::basic_iterator(chunk* c) : _chunk(c), _item_index(_chunk ? _chunk->begin : 0) { | |
217 | } | |
218 | ||
219 | template <typename T, size_t items_per_chunk> | |
220 | template <typename U> | |
221 | inline | |
222 | chunked_fifo<T, items_per_chunk>::basic_iterator<U>::basic_iterator(chunk* c, size_t item_index) : _chunk(c), _item_index(item_index) { | |
223 | } | |
224 | ||
225 | template <typename T, size_t items_per_chunk> | |
226 | template <typename U> | |
227 | inline bool | |
228 | chunked_fifo<T, items_per_chunk>::basic_iterator<U>::operator==(const basic_iterator& o) const { | |
229 | return _chunk == o._chunk && _item_index == o._item_index; | |
230 | } | |
231 | ||
232 | template <typename T, size_t items_per_chunk> | |
233 | template <typename U> | |
234 | inline bool | |
235 | chunked_fifo<T, items_per_chunk>::basic_iterator<U>::operator!=(const basic_iterator& o) const { | |
236 | return !(*this == o); | |
237 | } | |
238 | ||
239 | template <typename T, size_t items_per_chunk> | |
240 | template <typename U> | |
241 | inline typename chunked_fifo<T, items_per_chunk>::template basic_iterator<U>::pointer | |
242 | chunked_fifo<T, items_per_chunk>::basic_iterator<U>::operator->() const { | |
243 | return &_chunk->items[chunked_fifo::mask(_item_index)].data; | |
244 | } | |
245 | ||
246 | template <typename T, size_t items_per_chunk> | |
247 | template <typename U> | |
248 | inline typename chunked_fifo<T, items_per_chunk>::template basic_iterator<U>::reference | |
249 | chunked_fifo<T, items_per_chunk>::basic_iterator<U>::operator*() const { | |
250 | return _chunk->items[chunked_fifo::mask(_item_index)].data; | |
251 | } | |
252 | ||
253 | template <typename T, size_t items_per_chunk> | |
254 | template <typename U> | |
255 | inline typename chunked_fifo<T, items_per_chunk>::template basic_iterator<U> | |
256 | chunked_fifo<T, items_per_chunk>::basic_iterator<U>::operator++(int) { | |
257 | auto it = *this; | |
258 | ++(*this); | |
259 | return it; | |
260 | } | |
261 | ||
262 | template <typename T, size_t items_per_chunk> | |
263 | template <typename U> | |
264 | typename chunked_fifo<T, items_per_chunk>::template basic_iterator<U>& | |
265 | chunked_fifo<T, items_per_chunk>::basic_iterator<U>::operator++() { | |
266 | ++_item_index; | |
267 | if (_item_index == _chunk->end) { | |
268 | _chunk = _chunk->next; | |
269 | _item_index = _chunk ? _chunk->begin : 0; | |
270 | } | |
271 | return *this; | |
272 | } | |
273 | ||
274 | template <typename T, size_t items_per_chunk> | |
275 | inline | |
276 | chunked_fifo<T, items_per_chunk>::const_iterator::const_iterator(chunked_fifo<T, items_per_chunk>::iterator o) | |
277 | : basic_iterator<const T>(o._chunk, o._item_index) { | |
278 | } | |
279 | ||
11fdf7f2 TL |
280 | template <typename T, size_t items_per_chunk> |
281 | inline | |
282 | chunked_fifo<T, items_per_chunk>::chunked_fifo(chunked_fifo&& x) noexcept | |
283 | : _front_chunk(x._front_chunk) | |
284 | , _back_chunk(x._back_chunk) | |
285 | , _nchunks(x._nchunks) | |
286 | , _free_chunks(x._free_chunks) | |
287 | , _nfree_chunks(x._nfree_chunks) { | |
288 | x._front_chunk = nullptr; | |
289 | x._back_chunk = nullptr; | |
290 | x._nchunks = 0; | |
291 | x._free_chunks = nullptr; | |
292 | x._nfree_chunks = 0; | |
293 | } | |
294 | ||
295 | template <typename T, size_t items_per_chunk> | |
296 | inline | |
297 | chunked_fifo<T, items_per_chunk>& | |
298 | chunked_fifo<T, items_per_chunk>::operator=(chunked_fifo&& x) noexcept { | |
299 | if (&x != this) { | |
300 | this->~chunked_fifo(); | |
301 | new (this) chunked_fifo(std::move(x)); | |
302 | } | |
303 | return *this; | |
304 | } | |
305 | ||
306 | template <typename T, size_t items_per_chunk> | |
307 | inline size_t | |
9f95a23c | 308 | chunked_fifo<T, items_per_chunk>::mask(size_t idx) noexcept { |
11fdf7f2 TL |
309 | return idx & (items_per_chunk - 1); |
310 | } | |
311 | ||
312 | template <typename T, size_t items_per_chunk> | |
313 | inline bool | |
314 | chunked_fifo<T, items_per_chunk>::empty() const noexcept { | |
315 | return _front_chunk == nullptr; | |
316 | } | |
317 | ||
318 | template <typename T, size_t items_per_chunk> | |
319 | inline size_t | |
320 | chunked_fifo<T, items_per_chunk>::size() const noexcept{ | |
321 | if (_front_chunk == nullptr) { | |
322 | return 0; | |
323 | } else if (_back_chunk == _front_chunk) { | |
324 | // Single chunk. | |
325 | return _front_chunk->end - _front_chunk->begin; | |
326 | } else { | |
327 | return _front_chunk->end - _front_chunk->begin | |
328 | +_back_chunk->end - _back_chunk->begin | |
329 | + (_nchunks - 2) * items_per_chunk; | |
330 | } | |
331 | } | |
332 | ||
333 | template <typename T, size_t items_per_chunk> | |
334 | void chunked_fifo<T, items_per_chunk>::clear() noexcept { | |
335 | #if 1 | |
336 | while (!empty()) { | |
337 | pop_front(); | |
338 | } | |
339 | #else | |
340 | // This is specialized code to free the contents of all the chunks and the | |
341 | // chunks themselves. but since destroying a very full queue is not an | |
342 | // important use case to optimize, the simple loop above is preferable. | |
343 | if (!_front_chunk) { | |
344 | // Empty, nothing to do | |
345 | return; | |
346 | } | |
347 | // Delete front chunk (partially filled) | |
348 | for (auto i = _front_chunk->begin; i != _front_chunk->end; ++i) { | |
349 | _front_chunk->items[mask(i)].data.~T(); | |
350 | } | |
351 | chunk *p = _front_chunk->next; | |
352 | delete _front_chunk; | |
353 | // Delete all the middle chunks (all completely filled) | |
354 | if (p) { | |
355 | while (p != _back_chunk) { | |
356 | // These are full chunks | |
357 | chunk *nextp = p->next; | |
358 | for (auto i = 0; i != items_per_chunk; ++i) { | |
359 | // Note we delete out of order (we don't start with p->begin). | |
360 | // That should be fine.. | |
361 | p->items[i].data.~T(); | |
362 | } | |
363 | delete p; | |
364 | p = nextp; | |
365 | } | |
366 | // Finally delete back chunk (partially filled) | |
367 | for (auto i = _back_chunk->begin; i != _back_chunk->end; ++i) { | |
368 | _back_chunk->items[mask(i)].data.~T(); | |
369 | } | |
370 | delete _back_chunk; | |
371 | } | |
372 | _front_chunk = nullptr; | |
373 | _back_chunk = nullptr; | |
374 | _nchunks = 0; | |
375 | #endif | |
376 | } | |
377 | ||
378 | template <typename T, size_t items_per_chunk> void | |
379 | chunked_fifo<T, items_per_chunk>::shrink_to_fit() { | |
380 | while (_free_chunks) { | |
381 | auto next = _free_chunks->next; | |
382 | delete _free_chunks; | |
383 | _free_chunks = next; | |
384 | } | |
385 | _nfree_chunks = 0; | |
386 | } | |
387 | ||
388 | template <typename T, size_t items_per_chunk> | |
389 | chunked_fifo<T, items_per_chunk>::~chunked_fifo() { | |
390 | clear(); | |
391 | shrink_to_fit(); | |
392 | } | |
393 | ||
394 | template <typename T, size_t items_per_chunk> | |
395 | void | |
396 | chunked_fifo<T, items_per_chunk>::back_chunk_new() { | |
397 | chunk *old = _back_chunk; | |
398 | if (_free_chunks) { | |
399 | _back_chunk = _free_chunks; | |
400 | _free_chunks = _free_chunks->next; | |
401 | --_nfree_chunks; | |
402 | } else { | |
403 | _back_chunk = new chunk; | |
404 | } | |
405 | _back_chunk->next = nullptr; | |
406 | _back_chunk->begin = 0; | |
407 | _back_chunk->end = 0; | |
408 | if (old) { | |
409 | old->next = _back_chunk; | |
410 | } | |
411 | if (_front_chunk == nullptr) { | |
412 | _front_chunk = _back_chunk; | |
413 | } | |
414 | _nchunks++; | |
415 | } | |
416 | ||
417 | ||
418 | template <typename T, size_t items_per_chunk> | |
419 | inline void | |
420 | chunked_fifo<T, items_per_chunk>::ensure_room_back() { | |
421 | // If we don't have a back chunk or it's full, we need to create a new one | |
422 | if (_back_chunk == nullptr || | |
423 | (_back_chunk->end - _back_chunk->begin) == items_per_chunk) { | |
424 | back_chunk_new(); | |
425 | } | |
426 | } | |
427 | ||
428 | template <typename T, size_t items_per_chunk> | |
429 | void | |
430 | chunked_fifo<T, items_per_chunk>::undo_room_back() { | |
431 | // If we failed creating a new item after ensure_room_back() created a | |
432 | // new empty chunk, we must remove it, or empty() will be incorrect | |
433 | // (either immediately, if the fifo was empty, or when all the items are | |
434 | // popped, if it already had items). | |
435 | if (_back_chunk->begin == _back_chunk->end) { | |
436 | delete _back_chunk; | |
437 | --_nchunks; | |
438 | if (_nchunks == 0) { | |
439 | _back_chunk = nullptr; | |
440 | _front_chunk = nullptr; | |
441 | } else { | |
442 | // Because we don't usually pop from the back, we don't have a "prev" | |
443 | // pointer so we need to find the previous chunk the hard and slow | |
444 | // way. B | |
445 | chunk *old = _back_chunk; | |
446 | _back_chunk = _front_chunk; | |
447 | while (_back_chunk->next != old) { | |
448 | _back_chunk = _back_chunk->next; | |
449 | } | |
450 | _back_chunk->next = nullptr; | |
451 | } | |
452 | } | |
453 | ||
454 | } | |
455 | ||
456 | template <typename T, size_t items_per_chunk> | |
457 | template <typename... Args> | |
458 | inline void | |
459 | chunked_fifo<T, items_per_chunk>::emplace_back(Args&&... args) { | |
460 | ensure_room_back(); | |
461 | auto p = &_back_chunk->items[mask(_back_chunk->end)].data; | |
462 | try { | |
463 | new(p) T(std::forward<Args>(args)...); | |
464 | } catch(...) { | |
465 | undo_room_back(); | |
466 | throw; | |
467 | } | |
468 | ++_back_chunk->end; | |
469 | } | |
470 | ||
471 | template <typename T, size_t items_per_chunk> | |
472 | inline void | |
473 | chunked_fifo<T, items_per_chunk>::push_back(const T& data) { | |
474 | ensure_room_back(); | |
475 | auto p = &_back_chunk->items[mask(_back_chunk->end)].data; | |
476 | try { | |
477 | new(p) T(data); | |
478 | } catch(...) { | |
479 | undo_room_back(); | |
480 | throw; | |
481 | } | |
482 | ++_back_chunk->end; | |
483 | } | |
484 | ||
485 | template <typename T, size_t items_per_chunk> | |
486 | inline void | |
487 | chunked_fifo<T, items_per_chunk>::push_back(T&& data) { | |
488 | ensure_room_back(); | |
489 | auto p = &_back_chunk->items[mask(_back_chunk->end)].data; | |
490 | try { | |
491 | new(p) T(std::move(data)); | |
492 | } catch(...) { | |
493 | undo_room_back(); | |
494 | throw; | |
495 | } | |
496 | ++_back_chunk->end; | |
497 | } | |
498 | ||
499 | template <typename T, size_t items_per_chunk> | |
500 | inline | |
501 | T& | |
502 | chunked_fifo<T, items_per_chunk>::back() { | |
503 | return _back_chunk->items[mask(_back_chunk->end - 1)].data; | |
504 | } | |
505 | ||
506 | template <typename T, size_t items_per_chunk> | |
507 | inline | |
508 | const T& | |
509 | chunked_fifo<T, items_per_chunk>::back() const { | |
510 | return _back_chunk->items[mask(_back_chunk->end - 1)].data; | |
511 | } | |
512 | ||
513 | template <typename T, size_t items_per_chunk> | |
514 | inline T& | |
515 | chunked_fifo<T, items_per_chunk>::front() const noexcept { | |
516 | return _front_chunk->items[mask(_front_chunk->begin)].data; | |
517 | } | |
518 | ||
519 | template <typename T, size_t items_per_chunk> | |
520 | inline void | |
521 | chunked_fifo<T, items_per_chunk>::front_chunk_delete() noexcept { | |
522 | chunk *next = _front_chunk->next; | |
523 | // Certain use cases may need to repeatedly allocate and free a chunk - | |
524 | // an obvious example is an empty queue to which we push, and then pop, | |
525 | // repeatedly. Another example is pushing and popping to a non-empty queue | |
526 | // we push and pop at different chunks so we need to free and allocate a | |
527 | // chunk every items_per_chunk operations. | |
528 | // The solution is to keep a list of freed chunks instead of freeing them | |
529 | // immediately. There is a performance/memory tradeoff of how many freed | |
530 | // chunks to save: If we save them all, the queue can never shrink from | |
531 | // its maximum memory use (this is how circular_buffer behaves). | |
532 | // The ad-hoc choice made here is to limit the number of saved chunks to 1, | |
533 | // but this could easily be made a configuration option. | |
534 | static constexpr int save_free_chunks = 1; | |
535 | if (_nfree_chunks < save_free_chunks) { | |
536 | _front_chunk->next = _free_chunks; | |
537 | _free_chunks = _front_chunk; | |
538 | ++_nfree_chunks; | |
539 | } else { | |
540 | delete _front_chunk; | |
541 | } | |
542 | // If we only had one chunk, _back_chunk is gone too. | |
543 | if (_back_chunk == _front_chunk) { | |
544 | _back_chunk = nullptr; | |
545 | } | |
546 | _front_chunk = next; | |
547 | --_nchunks; | |
548 | } | |
549 | ||
550 | template <typename T, size_t items_per_chunk> | |
551 | inline void | |
552 | chunked_fifo<T, items_per_chunk>::pop_front() noexcept { | |
553 | front().~T(); | |
554 | // If the front chunk has become empty, we need to free remove it and use | |
555 | // the next one. | |
556 | if (++_front_chunk->begin == _front_chunk->end) { | |
557 | front_chunk_delete(); | |
558 | } | |
559 | } | |
560 | ||
561 | template <typename T, size_t items_per_chunk> | |
562 | void chunked_fifo<T, items_per_chunk>::reserve(size_t n) { | |
563 | // reserve() guarantees that (n - size()) additional push()es will | |
564 | // succeed without reallocation: | |
565 | size_t need = n - size(); | |
566 | // If we already have a back chunk, it might have room for some pushes | |
567 | // before filling up, so decrease "need": | |
568 | if (_back_chunk) { | |
569 | need -= items_per_chunk - (_back_chunk->end - _back_chunk->begin); | |
570 | } | |
571 | size_t needed_chunks = (need + items_per_chunk - 1) / items_per_chunk; | |
572 | // If we already have some freed chunks saved, we need to allocate fewer | |
573 | // additional chunks, or none at all | |
574 | if (needed_chunks <= _nfree_chunks) { | |
575 | return; | |
576 | } | |
577 | needed_chunks -= _nfree_chunks; | |
578 | while (needed_chunks--) { | |
579 | chunk *c = new chunk; | |
580 | c->next = _free_chunks; | |
581 | _free_chunks = c; | |
582 | ++_nfree_chunks; | |
583 | } | |
584 | } | |
585 | ||
9f95a23c TL |
586 | template <typename T, size_t items_per_chunk> |
587 | inline typename chunked_fifo<T, items_per_chunk>::iterator | |
588 | chunked_fifo<T, items_per_chunk>::begin() { | |
589 | return iterator(_front_chunk); | |
590 | } | |
591 | ||
592 | template <typename T, size_t items_per_chunk> | |
593 | inline typename chunked_fifo<T, items_per_chunk>::iterator | |
594 | chunked_fifo<T, items_per_chunk>::end() { | |
595 | return iterator(nullptr); | |
596 | } | |
597 | ||
598 | template <typename T, size_t items_per_chunk> | |
599 | inline typename chunked_fifo<T, items_per_chunk>::const_iterator | |
600 | chunked_fifo<T, items_per_chunk>::begin() const { | |
601 | return const_iterator(_front_chunk); | |
602 | } | |
603 | ||
604 | template <typename T, size_t items_per_chunk> | |
605 | inline typename chunked_fifo<T, items_per_chunk>::const_iterator | |
606 | chunked_fifo<T, items_per_chunk>::end() const { | |
607 | return const_iterator(nullptr); | |
608 | } | |
609 | ||
610 | template <typename T, size_t items_per_chunk> | |
611 | inline typename chunked_fifo<T, items_per_chunk>::const_iterator | |
612 | chunked_fifo<T, items_per_chunk>::cbegin() const { | |
613 | return const_iterator(_front_chunk); | |
614 | } | |
615 | ||
616 | template <typename T, size_t items_per_chunk> | |
617 | inline typename chunked_fifo<T, items_per_chunk>::const_iterator | |
618 | chunked_fifo<T, items_per_chunk>::cend() const { | |
619 | return const_iterator(nullptr); | |
620 | } | |
621 | ||
11fdf7f2 | 622 | } |