28#include <seastar/util/modules.hh>
90template <
typename T,
size_t items_per_chunk = 128>
92 static_assert((items_per_chunk & (items_per_chunk - 1)) == 0,
93 "chunked_fifo chunk size must be power of two");
95 maybe_item()
noexcept {}
100 maybe_item items[items_per_chunk];
107 size_t size()
const {
114 chunk* _front_chunk =
nullptr;
115 chunk* _back_chunk =
nullptr;
128 chunk* _free_chunks =
nullptr;
129 size_t _nfree_chunks = 0;
131 using value_type = T;
132 using size_type = size_t;
133 using reference = T&;
135 using const_reference =
const T&;
136 using const_pointer =
const T*;
139 template <
bool IsConst>
140 class basic_iterator {
144 using iterator_category = std::forward_iterator_tag;
145 using difference_type = std::ptrdiff_t;
146 using value_type = std::conditional_t<IsConst, const T, T>;
147 using pointer = value_type*;
148 using reference = value_type&;
151 using chunk_t = std::conditional_t<IsConst, const chunk, chunk>;
152 chunk_t* _chunk =
nullptr;
153 size_t _item_index = 0;
156 inline explicit basic_iterator(chunk_t* c)
noexcept;
157 inline basic_iterator(chunk_t* c,
size_t item_index)
noexcept;
160 basic_iterator()
noexcept =
default;
161 template<
bool OtherIsConst, std::enable_if_t<IsConst && !OtherIsConst,
int> = 0>
162 inline basic_iterator(
const basic_iterator<OtherIsConst>& o) noexcept
163 : basic_iterator{o._chunk, o._item_index} {}
164 inline bool operator==(
const basic_iterator& o)
const noexcept;
165 inline bool operator!=(
const basic_iterator& o)
const noexcept;
166 inline pointer operator->()
const noexcept;
167 inline reference operator*()
const noexcept;
168 inline basic_iterator operator++(
int)
noexcept;
169 basic_iterator& operator++()
noexcept;
173 using iterator = basic_iterator<false>;
174 using const_iterator = basic_iterator<true>;
183 inline void push_back(
const T& data);
184 inline void push_back(T&& data);
186 const T& back()
const noexcept;
187 template <
typename... A>
188 inline void emplace_back(A&&... args);
189 inline T& front()
const noexcept;
190 inline void pop_front()
noexcept;
191 inline bool empty()
const noexcept;
192 inline size_t size()
const noexcept;
196 void pop_front_n(
size_t n)
noexcept;
197 void clear()
noexcept;
204 void reserve(
size_t n);
207 void shrink_to_fit()
noexcept;
208 inline iterator begin()
noexcept;
209 inline iterator end()
noexcept;
210 inline const_iterator begin()
const noexcept;
211 inline const_iterator end()
const noexcept;
212 inline const_iterator cbegin()
const noexcept;
213 inline const_iterator cend()
const noexcept;
215 void back_chunk_new();
216 void front_chunk_delete()
noexcept;
217 inline void ensure_room_back();
218 void undo_room_back()
noexcept;
219 static inline size_t mask(
size_t idx)
noexcept;
223template <
typename T,
size_t items_per_chunk>
224template <
bool IsConst>
229template <
typename T,
size_t items_per_chunk>
230template <
bool IsConst>
232chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::basic_iterator(chunk_t* c,
size_t item_index) noexcept : _chunk(c), _item_index(item_index) {
235template <
typename T,
size_t items_per_chunk>
236template <
bool IsConst>
238chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator==(
const basic_iterator& o)
const noexcept {
239 return _chunk == o._chunk && _item_index == o._item_index;
242template <
typename T,
size_t items_per_chunk>
243template <
bool IsConst>
245chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator!=(
const basic_iterator& o)
const noexcept {
246 return !(*
this == o);
249template <
typename T,
size_t items_per_chunk>
250template <
bool IsConst>
251inline typename chunked_fifo<T, items_per_chunk>::template basic_iterator<IsConst>::pointer
252chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator->() const noexcept {
253 return &_chunk->items[chunked_fifo::mask(_item_index)].data;
256template <
typename T,
size_t items_per_chunk>
257template <
bool IsConst>
258inline typename chunked_fifo<T, items_per_chunk>::template basic_iterator<IsConst>::reference
259chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator*() const noexcept {
260 return _chunk->items[chunked_fifo::mask(_item_index)].data;
263template <
typename T,
size_t items_per_chunk>
264template <
bool IsConst>
265inline typename chunked_fifo<T, items_per_chunk>::template basic_iterator<IsConst>
266chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator++(
int)
noexcept {
272template <
typename T,
size_t items_per_chunk>
273template <
bool IsConst>
274typename chunked_fifo<T, items_per_chunk>::template basic_iterator<IsConst>&
275chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator++() noexcept {
277 if (_item_index == _chunk->end) {
278 _chunk = _chunk->next;
279 _item_index = _chunk ? _chunk->begin : 0;
284template <
typename T,
size_t items_per_chunk>
286chunked_fifo<T, items_per_chunk>::chunked_fifo(chunked_fifo&& x) noexcept
287 : _front_chunk(x._front_chunk)
288 , _back_chunk(x._back_chunk)
289 , _nchunks(x._nchunks)
290 , _free_chunks(x._free_chunks)
291 , _nfree_chunks(x._nfree_chunks) {
292 x._front_chunk =
nullptr;
293 x._back_chunk =
nullptr;
295 x._free_chunks =
nullptr;
299template <
typename T,
size_t items_per_chunk>
301chunked_fifo<T, items_per_chunk>&
302chunked_fifo<T, items_per_chunk>::operator=(chunked_fifo&& x)
noexcept {
304 this->~chunked_fifo();
305 new (
this) chunked_fifo(std::move(x));
310template <
typename T,
size_t items_per_chunk>
312chunked_fifo<T, items_per_chunk>::mask(
size_t idx)
noexcept {
313 return idx & (items_per_chunk - 1);
316template <
typename T,
size_t items_per_chunk>
318chunked_fifo<T, items_per_chunk>::empty() const noexcept {
319 return _front_chunk ==
nullptr;
322template <
typename T,
size_t items_per_chunk>
324chunked_fifo<T, items_per_chunk>::size() const noexcept{
325 if (_front_chunk ==
nullptr) {
327 }
else if (_back_chunk == _front_chunk) {
329 return _front_chunk->end - _front_chunk->begin;
331 return _front_chunk->end - _front_chunk->begin
332 +_back_chunk->end - _back_chunk->begin
333 + (_nchunks - 2) * items_per_chunk;
337template <
typename T,
size_t items_per_chunk>
338void chunked_fifo<T, items_per_chunk>::clear() noexcept {
342template <
typename T,
size_t items_per_chunk>
343void chunked_fifo<T, items_per_chunk>::pop_front_n(
size_t n)
noexcept {
345 assert(_front_chunk &&
"pop_front_n n too large");
347 auto target = _front_chunk;
348 unsigned delete_count = std::min(target->size(), n);
350 for (
auto i = target->begin, e = i + delete_count; i != e; i++) {
351 target->items[mask(i)].data.~T();
354 target->begin += delete_count;
357 if (target->size() == 0) {
358 front_chunk_delete();
365template <
typename T,
size_t items_per_chunk>
void
366chunked_fifo<T, items_per_chunk>::shrink_to_fit() noexcept {
367 while (_free_chunks) {
368 auto next = _free_chunks->next;
375template <
typename T,
size_t items_per_chunk>
376chunked_fifo<T, items_per_chunk>::~chunked_fifo() {
381template <
typename T,
size_t items_per_chunk>
383chunked_fifo<T, items_per_chunk>::back_chunk_new() {
384 chunk *old = _back_chunk;
386 _back_chunk = _free_chunks;
387 _free_chunks = _free_chunks->next;
390 _back_chunk =
new chunk;
392 _back_chunk->next =
nullptr;
393 _back_chunk->begin = 0;
394 _back_chunk->end = 0;
396 old->next = _back_chunk;
398 if (_front_chunk ==
nullptr) {
399 _front_chunk = _back_chunk;
405template <
typename T,
size_t items_per_chunk>
407chunked_fifo<T, items_per_chunk>::ensure_room_back() {
409 if (_back_chunk ==
nullptr ||
410 (_back_chunk->end - _back_chunk->begin) == items_per_chunk) {
415template <
typename T,
size_t items_per_chunk>
417chunked_fifo<T, items_per_chunk>::undo_room_back() noexcept {
422 if (_back_chunk->begin == _back_chunk->end) {
426 _back_chunk =
nullptr;
427 _front_chunk =
nullptr;
432 chunk *old = _back_chunk;
433 _back_chunk = _front_chunk;
434 while (_back_chunk->next != old) {
435 _back_chunk = _back_chunk->next;
437 _back_chunk->next =
nullptr;
443template <
typename T,
size_t items_per_chunk>
444template <
typename... Args>
446chunked_fifo<T, items_per_chunk>::emplace_back(Args&&... args) {
448 auto p = &_back_chunk->items[mask(_back_chunk->end)].data;
450 new(p) T(std::forward<Args>(args)...);
458template <
typename T,
size_t items_per_chunk>
460chunked_fifo<T, items_per_chunk>::push_back(
const T& data) {
462 auto p = &_back_chunk->items[mask(_back_chunk->end)].data;
472template <
typename T,
size_t items_per_chunk>
474chunked_fifo<T, items_per_chunk>::push_back(T&& data) {
476 auto p = &_back_chunk->items[mask(_back_chunk->end)].data;
478 new(p) T(std::move(data));
486template <
typename T,
size_t items_per_chunk>
489chunked_fifo<T, items_per_chunk>::back() noexcept {
490 return _back_chunk->items[mask(_back_chunk->end - 1)].data;
493template <
typename T,
size_t items_per_chunk>
496chunked_fifo<T, items_per_chunk>::back() const noexcept {
497 return _back_chunk->items[mask(_back_chunk->end - 1)].data;
500template <
typename T,
size_t items_per_chunk>
502chunked_fifo<T, items_per_chunk>::front() const noexcept {
503 return _front_chunk->items[mask(_front_chunk->begin)].data;
506template <
typename T,
size_t items_per_chunk>
508chunked_fifo<T, items_per_chunk>::front_chunk_delete() noexcept {
509 chunk *next = _front_chunk->next;
521 static constexpr int save_free_chunks = 1;
522 if (_nfree_chunks < save_free_chunks) {
523 _front_chunk->next = _free_chunks;
524 _free_chunks = _front_chunk;
530 if (_back_chunk == _front_chunk) {
531 _back_chunk =
nullptr;
537template <
typename T,
size_t items_per_chunk>
539chunked_fifo<T, items_per_chunk>::pop_front() noexcept {
543 if (++_front_chunk->begin == _front_chunk->end) {
544 front_chunk_delete();
548template <
typename T,
size_t items_per_chunk>
549void chunked_fifo<T, items_per_chunk>::reserve(
size_t n) {
555 size_t need = n - size();
559 size_t back_chunk_n = items_per_chunk - (_back_chunk->end - _back_chunk->begin);
560 need -= std::min(back_chunk_n, need);
562 size_t needed_chunks = (need + items_per_chunk - 1) / items_per_chunk;
565 if (needed_chunks <= _nfree_chunks) {
568 needed_chunks -= _nfree_chunks;
569 while (needed_chunks--) {
570 chunk *c =
new chunk;
571 c->next = _free_chunks;
577template <
typename T,
size_t items_per_chunk>
578inline typename chunked_fifo<T, items_per_chunk>::iterator
579chunked_fifo<T, items_per_chunk>::begin() noexcept {
580 return iterator(_front_chunk);
583template <
typename T,
size_t items_per_chunk>
584inline typename chunked_fifo<T, items_per_chunk>::iterator
585chunked_fifo<T, items_per_chunk>::end() noexcept {
586 return iterator(
nullptr);
589template <
typename T,
size_t items_per_chunk>
590inline typename chunked_fifo<T, items_per_chunk>::const_iterator
591chunked_fifo<T, items_per_chunk>::begin() const noexcept {
592 return const_iterator(_front_chunk);
595template <
typename T,
size_t items_per_chunk>
596inline typename chunked_fifo<T, items_per_chunk>::const_iterator
597chunked_fifo<T, items_per_chunk>::end() const noexcept {
598 return const_iterator(
nullptr);
601template <
typename T,
size_t items_per_chunk>
602inline typename chunked_fifo<T, items_per_chunk>::const_iterator
603chunked_fifo<T, items_per_chunk>::cbegin() const noexcept {
604 return const_iterator(_front_chunk);
607template <
typename T,
size_t items_per_chunk>
608inline typename chunked_fifo<T, items_per_chunk>::const_iterator
609chunked_fifo<T, items_per_chunk>::cend() const noexcept {
610 return const_iterator(
nullptr);
Definition: chunked_fifo.hh:91
Seastar API namespace.
Definition: abort_on_ebadf.hh:26