24#ifndef MEM_ROOT_DEQUE_H
25#define MEM_ROOT_DEQUE_H
37template <
class Element_type>
40 size_t base_number_elems =
41 1024 /
sizeof(Element_type);
46 for (
size_t block_size = 16; block_size < 1024; ++block_size) {
47 if (block_size >= base_number_elems) {
110template <
class Element_type>
133 for (
size_t block_idx = 0; block_idx <
num_blocks(); ++block_idx) {
137 new (&
get(idx)) Element_type(other.
get(idx));
141 if (
this != &other) {
143 for (
const Element_type &elem : other) {
157 other.m_blocks =
nullptr;
158 other.m_begin_idx = other.m_end_idx = other.m_capacity = 0;
159 other.invalidate_iterators();
162 if (
this != &other) {
202 new (&
get(
m_end_idx++)) Element_type(std::move(element));
272 const Element_type &
back()
const {
288 template <
class Iterator_element_type>
314 typename = std::enable_if_t<
315 std::is_const<Iterator_element_type>::value &&
317 std::remove_const_t<Iterator_element_type>>::value>>
402 return *(*
this + idx);
449 return std::make_reverse_iterator(
end());
452 return std::make_reverse_iterator(
begin());
455 return std::make_reverse_iterator(
end());
458 return std::make_reverse_iterator(
begin());
496 return erase(position, std::next(position));
513 return begin() + idx;
530 return begin() + idx;
533 template <
class ForwardIt>
536 for (ForwardIt it = first; it !=
last; ++it) {
541 return begin() + idx;
559 sizeof(Element_type)));
617 Element_type &
get(
size_t physical_idx)
const {
630template <
class Element_type>
632 if (m_blocks ==
nullptr) {
633 return add_initial_block();
635 Block *new_blocks = m_root->ArrayAlloc<
Block>(num_blocks() + 1);
636 if (new_blocks ==
nullptr) {
639 memcpy(new_blocks, m_blocks,
sizeof(
Block) * num_blocks());
640 if (new_blocks[num_blocks()].
init(m_root)) {
644 m_blocks = new_blocks;
645 m_capacity += block_elements;
649template <
class Element_type>
651 if (m_blocks ==
nullptr) {
652 if (add_initial_block()) {
655 if (m_begin_idx == 0) {
657 m_begin_idx = m_end_idx = 1;
661 Block *new_blocks = m_root->ArrayAlloc<
Block>(num_blocks() + 1);
662 memcpy(new_blocks + 1, m_blocks,
sizeof(
Block) * num_blocks());
663 if (new_blocks[0].
init(m_root)) {
667 m_blocks = new_blocks;
668 m_begin_idx += block_elements;
669 m_end_idx += block_elements;
670 m_capacity += block_elements;
static mysql_service_status_t init()
Component initialization.
Definition: audit_api_message_emit.cc:571
Definition: mem_root_deque.h:289
Iterator_element_type * operator->() const
Definition: mem_root_deque.h:346
bool operator>(const Iterator &other) const
Definition: mem_root_deque.h:413
Iterator operator+(difference_type offset) const
Definition: mem_root_deque.h:385
bool operator>=(const Iterator &other) const
Definition: mem_root_deque.h:419
bool operator==(const Iterator &other) const
Definition: mem_root_deque.h:337
Iterator operator--(int)
Definition: mem_root_deque.h:365
bool operator<(const Iterator &other) const
Definition: mem_root_deque.h:405
size_t m_generation
Definition: mem_root_deque.h:425
difference_type operator-(const Iterator &other) const
Definition: mem_root_deque.h:395
std::random_access_iterator_tag iterator_category
Definition: mem_root_deque.h:295
Iterator(const mem_root_deque *deque, size_t physical_idx)
Definition: mem_root_deque.h:300
bool operator<=(const Iterator &other) const
Definition: mem_root_deque.h:411
Iterator_element_type * pointer
Definition: mem_root_deque.h:293
Iterator_element_type & operator[](size_t idx) const
Definition: mem_root_deque.h:401
Iterator & operator--()
Definition: mem_root_deque.h:360
Iterator operator-(difference_type offset) const
Definition: mem_root_deque.h:390
void assert_not_invalidated() const
Definition: mem_root_deque.h:428
Iterator & operator++()
Definition: mem_root_deque.h:330
Iterator_element_type & operator*() const
Definition: mem_root_deque.h:326
Iterator & operator-=(difference_type diff)
Definition: mem_root_deque.h:379
Iterator_element_type & reference
Definition: mem_root_deque.h:294
Iterator operator++(int)
Definition: mem_root_deque.h:352
Iterator(const T &other)
For const_iterator: Implicit conversion from iterator.
Definition: mem_root_deque.h:318
Iterator & operator+=(difference_type diff)
Definition: mem_root_deque.h:373
const mem_root_deque * m_deque
Definition: mem_root_deque.h:422
ptrdiff_t difference_type
Definition: mem_root_deque.h:291
Iterator_element_type value_type
Definition: mem_root_deque.h:292
size_t m_physical_idx
Definition: mem_root_deque.h:423
bool operator!=(const Iterator &other) const
Definition: mem_root_deque.h:344
A (partial) implementation of std::deque allocating its blocks on a MEM_ROOT.
Definition: mem_root_deque.h:111
Element_type & operator[](size_t idx) const
Definition: mem_root_deque.h:171
reverse_iterator rbegin()
Definition: mem_root_deque.h:442
iterator insert(const_iterator pos, Element_type &&value)
Insert an element at a given position.
Definition: mem_root_deque.h:525
std::reverse_iterator< const_iterator > reverse_const_iterator
Definition: mem_root_deque.h:438
const Element_type * const_pointer
Definition: mem_root_deque.h:119
void invalidate_iterators()
Definition: mem_root_deque.h:589
iterator erase(const_iterator first, const_iterator last)
Erase all the elements in the specified range.
Definition: mem_root_deque.h:472
size_t size() const
Definition: mem_root_deque.h:461
iterator insert(const_iterator pos, ForwardIt first, ForwardIt last)
Definition: mem_root_deque.h:534
bool push_back(Element_type &&element)
Adds the given element to the end of the deque.
Definition: mem_root_deque.h:196
static constexpr size_t block_elements
Number of elements in each block.
Definition: mem_root_deque.h:546
reverse_const_iterator rbegin() const
Definition: mem_root_deque.h:454
size_t size_type
Used to conform to STL algorithm demands.
Definition: mem_root_deque.h:114
reverse_const_iterator rend() const
Definition: mem_root_deque.h:457
reverse_const_iterator crbegin() const
Definition: mem_root_deque.h:448
Element_type & front()
Returns the first element in the deque.
Definition: mem_root_deque.h:256
bool add_initial_block()
Adds the first block of elements.
Definition: mem_root_deque.h:595
bool add_block_back()
Definition: mem_root_deque.h:631
const_iterator cend()
Definition: mem_root_deque.h:445
size_t m_begin_idx
Physical index to the first valid element.
Definition: mem_root_deque.h:570
const Element_type & back() const
Definition: mem_root_deque.h:272
mem_root_deque(const mem_root_deque &other)
Definition: mem_root_deque.h:127
size_t m_end_idx
Physical index one past the last valid element.
Definition: mem_root_deque.h:574
Element_type value_type
Definition: mem_root_deque.h:116
bool push_back(const Element_type &element)
Adds the given element to the end of the deque.
Definition: mem_root_deque.h:179
void clear()
Removes all elements from the deque.
Definition: mem_root_deque.h:280
reverse_iterator rend()
Definition: mem_root_deque.h:443
ptrdiff_t difference_type
Definition: mem_root_deque.h:115
std::reverse_iterator< iterator > reverse_iterator
Definition: mem_root_deque.h:437
iterator erase(const_iterator position)
Removes a single element from the array.
Definition: mem_root_deque.h:495
const Element_type & front() const
Definition: mem_root_deque.h:261
const Element_type & const_reference
Definition: mem_root_deque.h:120
Block * m_blocks
Pointer to the first block.
Definition: mem_root_deque.h:567
mem_root_deque & operator=(mem_root_deque &&other)
Definition: mem_root_deque.h:161
const_iterator end() const
Definition: mem_root_deque.h:447
iterator insert(const_iterator pos, const Element_type &value)
Insert an element at a given position.
Definition: mem_root_deque.h:508
bool push_front(const Element_type &element)
Adds the given element to the beginning of the deque.
Definition: mem_root_deque.h:213
mem_root_deque(MEM_ROOT *mem_root)
Constructor. Leaves the array in an empty, valid state.
Definition: mem_root_deque.h:123
mem_root_deque & operator=(const mem_root_deque &other)
Definition: mem_root_deque.h:140
size_t m_capacity
Number of blocks, multiplied by block_elements.
Definition: mem_root_deque.h:578
Element_type & reference
Definition: mem_root_deque.h:118
Element_type & back()
Returns the last element in the deque.
Definition: mem_root_deque.h:267
Element_type * pointer
Definition: mem_root_deque.h:117
reverse_const_iterator crend() const
Definition: mem_root_deque.h:451
Element_type & get(size_t physical_idx) const
Gets a reference to the memory used to store an element with the given physical index,...
Definition: mem_root_deque.h:617
const_iterator begin() const
Definition: mem_root_deque.h:446
~mem_root_deque()
Definition: mem_root_deque.h:169
const_iterator cbegin()
Definition: mem_root_deque.h:444
void pop_front()
Removes the first element from the deque.
Definition: mem_root_deque.h:249
bool empty() const
Definition: mem_root_deque.h:462
bool push_front(Element_type &&element)
Adds the given element to the end of the deque.
Definition: mem_root_deque.h:229
size_t num_blocks() const
Definition: mem_root_deque.h:612
iterator begin()
Definition: mem_root_deque.h:440
size_t generation() const
Definition: mem_root_deque.h:623
MEM_ROOT * m_root
Pointer to the MEM_ROOT that we store our blocks and elements on.
Definition: mem_root_deque.h:581
void pop_back()
Removes the last element from the deque.
Definition: mem_root_deque.h:242
bool add_block_front()
Definition: mem_root_deque.h:650
iterator end()
Definition: mem_root_deque.h:441
size_t m_generation
Incremented each time we make an operation that would invalidate iterators.
Definition: mem_root_deque.h:588
mem_root_deque(mem_root_deque &&other)
Definition: mem_root_deque.h:151
static MEM_ROOT mem_root
Definition: client_plugin.cc:114
static Bigint * diff(Bigint *a, Bigint *b, Stack_alloc *alloc)
Definition: dtoa.cc:1081
static constexpr size_t FindElementsPerBlock()
Definition: mem_root_deque.h:38
This file follows Google coding style, except for the name MEM_ROOT (which is kept for historical rea...
void destroy_at(T *ptr)
Definition: my_alloc.h:462
uint16_t value_type
Definition: vt100.h:184
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:83
T * ArrayAlloc(size_t num, Args... args)
Allocate 'num' objects of type T, and initialize them to a default value that is created by passing t...
Definition: my_alloc.h:180
void * Alloc(size_t length)
Allocate memory.
Definition: my_alloc.h:145
Definition: mem_root_deque.h:552
Element_type * elements
Definition: mem_root_deque.h:553
bool init(MEM_ROOT *mem_root)
Definition: mem_root_deque.h:555