24 #ifndef SEASTAR_MODULE
27 #include <type_traits>
28 #include <seastar/util/modules.hh>
90 template <
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];
109 chunk* _front_chunk =
nullptr;
110 chunk* _back_chunk =
nullptr;
123 chunk* _free_chunks =
nullptr;
124 size_t _nfree_chunks = 0;
126 using value_type = T;
127 using size_type = size_t;
128 using reference = T&;
130 using const_reference =
const T&;
131 using const_pointer =
const T*;
134 template <
bool IsConst>
135 class basic_iterator {
139 using iterator_category = std::forward_iterator_tag;
140 using difference_type = std::ptrdiff_t;
141 using value_type = std::conditional_t<IsConst, const T, T>;
142 using pointer = value_type*;
143 using reference = value_type&;
146 using chunk_t = std::conditional_t<IsConst, const chunk, chunk>;
147 chunk_t* _chunk =
nullptr;
148 size_t _item_index = 0;
151 inline explicit basic_iterator(chunk_t* c) noexcept;
152 inline basic_iterator(chunk_t* c,
size_t item_index) noexcept;
155 basic_iterator() noexcept =
default;
156 template<
bool OtherIsConst, std::enable_if_t<IsConst && !OtherIsConst,
int> = 0>
157 inline basic_iterator(
const basic_iterator<OtherIsConst>& o) noexcept
158 : basic_iterator{o._chunk, o._item_index} {}
159 inline bool operator==(
const basic_iterator& o)
const noexcept;
160 inline bool operator!=(
const basic_iterator& o)
const noexcept;
161 inline pointer operator->()
const noexcept;
162 inline reference operator*()
const noexcept;
163 inline basic_iterator operator++(
int) noexcept;
164 basic_iterator& operator++() noexcept;
168 using iterator = basic_iterator<false>;
169 using const_iterator = basic_iterator<true>;
178 inline void push_back(
const T& data);
179 inline void push_back(T&& data);
181 const T& back()
const noexcept;
182 template <
typename... A>
183 inline void emplace_back(A&&... args);
184 inline T& front()
const noexcept;
185 inline void pop_front() noexcept;
186 inline bool empty()
const noexcept;
187 inline size_t size()
const noexcept;
188 void clear() noexcept;
195 void reserve(
size_t n);
198 void shrink_to_fit() noexcept;
199 inline iterator begin() noexcept;
200 inline iterator end() noexcept;
201 inline const_iterator begin()
const noexcept;
202 inline const_iterator end()
const noexcept;
203 inline const_iterator cbegin()
const noexcept;
204 inline const_iterator cend()
const noexcept;
206 void back_chunk_new();
207 void front_chunk_delete() noexcept;
208 inline void ensure_room_back();
209 void undo_room_back() noexcept;
210 static inline size_t mask(
size_t idx) noexcept;
214 template <
typename T,
size_t items_per_chunk>
215 template <
bool IsConst>
220 template <
typename T,
size_t items_per_chunk>
221 template <
bool IsConst>
223 chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::basic_iterator(chunk_t* c,
size_t item_index) noexcept : _chunk(c), _item_index(item_index) {
226 template <
typename T,
size_t items_per_chunk>
227 template <
bool IsConst>
229 chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator==(
const basic_iterator& o)
const noexcept {
230 return _chunk == o._chunk && _item_index == o._item_index;
233 template <
typename T,
size_t items_per_chunk>
234 template <
bool IsConst>
236 chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator!=(
const basic_iterator& o)
const noexcept {
237 return !(*
this == o);
240 template <
typename T,
size_t items_per_chunk>
241 template <
bool IsConst>
242 inline typename chunked_fifo<T, items_per_chunk>::template basic_iterator<IsConst>::pointer
243 chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator->() const noexcept {
244 return &_chunk->items[chunked_fifo::mask(_item_index)].data;
247 template <
typename T,
size_t items_per_chunk>
248 template <
bool IsConst>
249 inline typename chunked_fifo<T, items_per_chunk>::template basic_iterator<IsConst>::reference
250 chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator*() const noexcept {
251 return _chunk->items[chunked_fifo::mask(_item_index)].data;
254 template <
typename T,
size_t items_per_chunk>
255 template <
bool IsConst>
256 inline typename chunked_fifo<T, items_per_chunk>::template basic_iterator<IsConst>
257 chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator++(
int) noexcept {
263 template <
typename T,
size_t items_per_chunk>
264 template <
bool IsConst>
265 typename chunked_fifo<T, items_per_chunk>::template basic_iterator<IsConst>&
266 chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator++() noexcept {
268 if (_item_index == _chunk->end) {
269 _chunk = _chunk->next;
270 _item_index = _chunk ? _chunk->begin : 0;
275 template <
typename T,
size_t items_per_chunk>
277 chunked_fifo<T, items_per_chunk>::chunked_fifo(chunked_fifo&& x) noexcept
278 : _front_chunk(x._front_chunk)
279 , _back_chunk(x._back_chunk)
280 , _nchunks(x._nchunks)
281 , _free_chunks(x._free_chunks)
282 , _nfree_chunks(x._nfree_chunks) {
283 x._front_chunk =
nullptr;
284 x._back_chunk =
nullptr;
286 x._free_chunks =
nullptr;
290 template <
typename T,
size_t items_per_chunk>
292 chunked_fifo<T, items_per_chunk>&
293 chunked_fifo<T, items_per_chunk>::operator=(chunked_fifo&& x) noexcept {
295 this->~chunked_fifo();
296 new (
this) chunked_fifo(std::move(x));
301 template <
typename T,
size_t items_per_chunk>
303 chunked_fifo<T, items_per_chunk>::mask(
size_t idx) noexcept {
304 return idx & (items_per_chunk - 1);
307 template <
typename T,
size_t items_per_chunk>
309 chunked_fifo<T, items_per_chunk>::empty() const noexcept {
310 return _front_chunk ==
nullptr;
313 template <
typename T,
size_t items_per_chunk>
315 chunked_fifo<T, items_per_chunk>::size() const noexcept{
316 if (_front_chunk ==
nullptr) {
318 }
else if (_back_chunk == _front_chunk) {
320 return _front_chunk->end - _front_chunk->begin;
322 return _front_chunk->end - _front_chunk->begin
323 +_back_chunk->end - _back_chunk->begin
324 + (_nchunks - 2) * items_per_chunk;
328 template <
typename T,
size_t items_per_chunk>
329 void chunked_fifo<T, items_per_chunk>::clear() noexcept {
343 for (
auto i = _front_chunk->begin; i != _front_chunk->end; ++i) {
344 _front_chunk->items[mask(i)].data.~T();
346 chunk *p = _front_chunk->next;
350 while (p != _back_chunk) {
352 chunk *nextp = p->next;
353 for (
auto i = 0; i != items_per_chunk; ++i) {
356 p->items[i].data.~T();
362 for (
auto i = _back_chunk->begin; i != _back_chunk->end; ++i) {
363 _back_chunk->items[mask(i)].data.~T();
367 _front_chunk =
nullptr;
368 _back_chunk =
nullptr;
373 template <
typename T,
size_t items_per_chunk>
void
374 chunked_fifo<T, items_per_chunk>::shrink_to_fit() noexcept {
375 while (_free_chunks) {
376 auto next = _free_chunks->next;
383 template <
typename T,
size_t items_per_chunk>
384 chunked_fifo<T, items_per_chunk>::~chunked_fifo() {
389 template <
typename T,
size_t items_per_chunk>
391 chunked_fifo<T, items_per_chunk>::back_chunk_new() {
392 chunk *old = _back_chunk;
394 _back_chunk = _free_chunks;
395 _free_chunks = _free_chunks->next;
398 _back_chunk =
new chunk;
400 _back_chunk->next =
nullptr;
401 _back_chunk->begin = 0;
402 _back_chunk->end = 0;
404 old->next = _back_chunk;
406 if (_front_chunk ==
nullptr) {
407 _front_chunk = _back_chunk;
413 template <
typename T,
size_t items_per_chunk>
415 chunked_fifo<T, items_per_chunk>::ensure_room_back() {
417 if (_back_chunk ==
nullptr ||
418 (_back_chunk->end - _back_chunk->begin) == items_per_chunk) {
423 template <
typename T,
size_t items_per_chunk>
425 chunked_fifo<T, items_per_chunk>::undo_room_back() noexcept {
430 if (_back_chunk->begin == _back_chunk->end) {
434 _back_chunk =
nullptr;
435 _front_chunk =
nullptr;
440 chunk *old = _back_chunk;
441 _back_chunk = _front_chunk;
442 while (_back_chunk->next != old) {
443 _back_chunk = _back_chunk->next;
445 _back_chunk->next =
nullptr;
451 template <
typename T,
size_t items_per_chunk>
452 template <
typename... Args>
454 chunked_fifo<T, items_per_chunk>::emplace_back(Args&&... args) {
456 auto p = &_back_chunk->items[mask(_back_chunk->end)].data;
458 new(p) T(std::forward<Args>(args)...);
466 template <
typename T,
size_t items_per_chunk>
468 chunked_fifo<T, items_per_chunk>::push_back(
const T& data) {
470 auto p = &_back_chunk->items[mask(_back_chunk->end)].data;
480 template <
typename T,
size_t items_per_chunk>
482 chunked_fifo<T, items_per_chunk>::push_back(T&& data) {
484 auto p = &_back_chunk->items[mask(_back_chunk->end)].data;
486 new(p) T(std::move(data));
494 template <
typename T,
size_t items_per_chunk>
497 chunked_fifo<T, items_per_chunk>::back() noexcept {
498 return _back_chunk->items[mask(_back_chunk->end - 1)].data;
501 template <
typename T,
size_t items_per_chunk>
504 chunked_fifo<T, items_per_chunk>::back() const noexcept {
505 return _back_chunk->items[mask(_back_chunk->end - 1)].data;
508 template <
typename T,
size_t items_per_chunk>
510 chunked_fifo<T, items_per_chunk>::front() const noexcept {
511 return _front_chunk->items[mask(_front_chunk->begin)].data;
514 template <
typename T,
size_t items_per_chunk>
516 chunked_fifo<T, items_per_chunk>::front_chunk_delete() noexcept {
517 chunk *next = _front_chunk->next;
529 static constexpr
int save_free_chunks = 1;
530 if (_nfree_chunks < save_free_chunks) {
531 _front_chunk->next = _free_chunks;
532 _free_chunks = _front_chunk;
538 if (_back_chunk == _front_chunk) {
539 _back_chunk =
nullptr;
545 template <
typename T,
size_t items_per_chunk>
547 chunked_fifo<T, items_per_chunk>::pop_front() noexcept {
551 if (++_front_chunk->begin == _front_chunk->end) {
552 front_chunk_delete();
556 template <
typename T,
size_t items_per_chunk>
557 void chunked_fifo<T, items_per_chunk>::reserve(
size_t n) {
563 size_t need = n - size();
567 size_t back_chunk_n = items_per_chunk - (_back_chunk->end - _back_chunk->begin);
568 need -= std::min(back_chunk_n, need);
570 size_t needed_chunks = (need + items_per_chunk - 1) / items_per_chunk;
573 if (needed_chunks <= _nfree_chunks) {
576 needed_chunks -= _nfree_chunks;
577 while (needed_chunks--) {
578 chunk *c =
new chunk;
579 c->next = _free_chunks;
585 template <
typename T,
size_t items_per_chunk>
586 inline typename chunked_fifo<T, items_per_chunk>::iterator
587 chunked_fifo<T, items_per_chunk>::begin() noexcept {
588 return iterator(_front_chunk);
591 template <
typename T,
size_t items_per_chunk>
592 inline typename chunked_fifo<T, items_per_chunk>::iterator
593 chunked_fifo<T, items_per_chunk>::end() noexcept {
594 return iterator(
nullptr);
597 template <
typename T,
size_t items_per_chunk>
598 inline typename chunked_fifo<T, items_per_chunk>::const_iterator
599 chunked_fifo<T, items_per_chunk>::begin() const noexcept {
600 return const_iterator(_front_chunk);
603 template <
typename T,
size_t items_per_chunk>
604 inline typename chunked_fifo<T, items_per_chunk>::const_iterator
605 chunked_fifo<T, items_per_chunk>::end() const noexcept {
606 return const_iterator(
nullptr);
609 template <
typename T,
size_t items_per_chunk>
610 inline typename chunked_fifo<T, items_per_chunk>::const_iterator
611 chunked_fifo<T, items_per_chunk>::cbegin() const noexcept {
612 return const_iterator(_front_chunk);
615 template <
typename T,
size_t items_per_chunk>
616 inline typename chunked_fifo<T, items_per_chunk>::const_iterator
617 chunked_fifo<T, items_per_chunk>::cend() const noexcept {
618 return const_iterator(
nullptr);
Definition: chunked_fifo.hh:91
Seastar API namespace.
Definition: abort_on_ebadf.hh:26