MySQL  8.0.24
Source Code Documentation
mem_root_deque< Element_type > Class Template Reference

A (partial) implementation of std::deque allocating its blocks on a MEM_ROOT. More...

#include <mem_root_deque.h>

Classes

struct  Block
 
class  Iterator
 

Public Types

using size_type = size_t
 Used to conform to STL algorithm demands. More...
 
using difference_type = ptrdiff_t
 
using value_type = Element_type
 
using pointer = Element_type *
 
using reference = Element_type &
 
using const_pointer = const Element_type *
 
using const_reference = const Element_type &
 
using iterator = Iterator< Element_type >
 
using const_iterator = Iterator< const Element_type >
 
using reverse_iterator = std::reverse_iterator< iterator >
 
using reverse_const_iterator = std::reverse_iterator< const_iterator >
 

Public Member Functions

 mem_root_deque (MEM_ROOT *mem_root)
 Constructor. Leaves the array in an empty, valid state. More...
 
 mem_root_deque (const mem_root_deque &other)
 
mem_root_dequeoperator= (const mem_root_deque &other)
 
 mem_root_deque (mem_root_deque &&other)
 
mem_root_dequeoperator= (mem_root_deque &&other)
 
 ~mem_root_deque ()
 
Element_type & operator[] (size_t idx) const
 
bool push_back (const Element_type &element)
 Adds the given element to the end of the deque. More...
 
bool push_back (Element_type &&element)
 Adds the given element to the end of the deque. More...
 
bool push_front (const Element_type &element)
 Adds the given element to the beginning of the deque. More...
 
bool push_front (Element_type &&element)
 Adds the given element to the end of the deque. More...
 
void pop_back ()
 Removes the last element from the deque. More...
 
void pop_front ()
 Removes the first element from the deque. More...
 
Element_type & front ()
 Returns the first element in the deque. More...
 
const Element_type & front () const
 
Element_type & back ()
 Returns the last element in the deque. More...
 
const Element_type & back () const
 
void clear ()
 Removes all elements from the deque. More...
 
iterator begin ()
 
iterator end ()
 
reverse_iterator rbegin ()
 
reverse_iterator rend ()
 
const_iterator cbegin ()
 
const_iterator cend ()
 
const_iterator begin () const
 
const_iterator end () const
 
reverse_const_iterator crbegin () const
 
reverse_const_iterator crend () const
 
reverse_const_iterator rbegin () const
 
reverse_const_iterator rend () const
 
size_t size () const
 
bool empty () const
 
iterator erase (const_iterator first, const_iterator last)
 Erase all the elements in the specified range. More...
 
iterator erase (const_iterator position)
 Removes a single element from the array. More...
 
iterator insert (const_iterator pos, const Element_type &value)
 Insert an element at a given position. More...
 
iterator insert (const_iterator pos, Element_type &&value)
 Insert an element at a given position. More...
 
template<class ForwardIt >
iterator insert (const_iterator pos, ForwardIt first, ForwardIt last)
 

Private Member Functions

void invalidate_iterators ()
 
bool add_initial_block ()
 Adds the first block of elements. More...
 
bool add_block_back ()
 
bool add_block_front ()
 
size_t num_blocks () const
 
Element_type & get (size_t physical_idx) const
 Gets a reference to the memory used to store an element with the given physical index, starting from zero. More...
 
size_t generation () const
 

Private Attributes

Blockm_blocks = nullptr
 Pointer to the first block. More...
 
size_t m_begin_idx = 0
 Physical index to the first valid element. More...
 
size_t m_end_idx = 0
 Physical index one past the last valid element. More...
 
size_t m_capacity = 0
 Number of blocks, multiplied by block_elements. More...
 
MEM_ROOTm_root
 Pointer to the MEM_ROOT that we store our blocks and elements on. More...
 
size_t m_generation = 0
 Incremented each time we make an operation that would invalidate iterators. More...
 

Static Private Attributes

static constexpr size_t block_elements = FindElementsPerBlock<Element_type>()
 Number of elements in each block. More...
 

Detailed Description

template<class Element_type>
class mem_root_deque< Element_type >

A (partial) implementation of std::deque allocating its blocks on a MEM_ROOT.

This class works pretty much like an std::deque with a Mem_root_allocator, and used to be a forwarder to it. However, libstdc++ has a very complicated implementation of std::deque, leading to code blowup (e.g., operator[] is 23 instructions on x86-64, including two branches), and we cannot easily use libc++ on all platforms. This version is instead:

  • Optimized for small, straight-through machine code (few and simple instructions, few branches).
  • Optimized for few elements; in particular, zero elements is an important special case, much more so than 10,000.

It gives mostly the same guarantees as std::deque; elements can be inserted efficiently on both front and back [1]. {push,pop}_{front,back} guarantees reference stability except for to removed elements (obviously), and invalidates iterators. (Iterators are forcefully invalidated using asserts.) erase() does the same. Note that unlike std::deque, insert() at begin() will invalidate references. Some functionality, like several constructors, resize(), shrink_to_fit(), swap(), etc. is missing.

The implementation is the same as classic std::deque: Elements are held in blocks of about 1 kB each. Once an element is in a block, it never moves (giving the aforementioned pointer stability). The blocks are held in an array, which can be reallocated when more blocks are needed. The implementation keeps track of the used items in terms of “physical indexes”; element 0 starts at the first byte of the first block, element 1 starts immediately after 0, and so on. So you can have something like (assuming very small blocks of only 4 elements each for the sake of drawing):

   block 0   block 1   block 2
   ↓         ↓         ↓
  [x x 2 3] [4 5 6 7] [8 9 x x]
       ↑                   ↑
       begin_idx = 2       end_idx = 10

end_idx counts as is customary one-past-the-end, so in this case, the elements [2,9) would be valid, and e.g. (*this)[4] would give physical index 6, which points to the third element (index 2) in the middle block (block 1). Inserting a new element at the front is as easy as putting it in physical index 1 and adjusting begin_idx to the left. This means a lookup by index requires some shifting, masking and a double indirect load.

Iterators keep track of which deque they belong to, and what physical index they point to. (So lookup by iterator also requires a double indirect load, but the alternative would be caching the block pointer and having an extra branch when advancing the iterator.) Inserting a new block at the beginning would move around all the physical indexes (which is why iterators get invalidated; we could probably get around this by having an “offset to first block”, but it's likely not worth it.)

[1] Actually, it's O(n), since there's no exponential growth of the blocks array. But the blocks are reallocated very rarely, so it is generally efficient nevertheless.

Member Typedef Documentation

◆ const_iterator

template<class Element_type >
using mem_root_deque< Element_type >::const_iterator = Iterator<const Element_type>

◆ const_pointer

template<class Element_type >
using mem_root_deque< Element_type >::const_pointer = const Element_type *

◆ const_reference

template<class Element_type >
using mem_root_deque< Element_type >::const_reference = const Element_type &

◆ difference_type

template<class Element_type >
using mem_root_deque< Element_type >::difference_type = ptrdiff_t

◆ iterator

template<class Element_type >
using mem_root_deque< Element_type >::iterator = Iterator<Element_type>

◆ pointer

template<class Element_type >
using mem_root_deque< Element_type >::pointer = Element_type *

◆ reference

template<class Element_type >
using mem_root_deque< Element_type >::reference = Element_type &

◆ reverse_const_iterator

template<class Element_type >
using mem_root_deque< Element_type >::reverse_const_iterator = std::reverse_iterator<const_iterator>

◆ reverse_iterator

template<class Element_type >
using mem_root_deque< Element_type >::reverse_iterator = std::reverse_iterator<iterator>

◆ size_type

template<class Element_type >
using mem_root_deque< Element_type >::size_type = size_t

Used to conform to STL algorithm demands.

◆ value_type

template<class Element_type >
using mem_root_deque< Element_type >::value_type = Element_type

Constructor & Destructor Documentation

◆ mem_root_deque() [1/3]

template<class Element_type >
mem_root_deque< Element_type >::mem_root_deque ( MEM_ROOT mem_root)
inlineexplicit

Constructor. Leaves the array in an empty, valid state.

◆ mem_root_deque() [2/3]

template<class Element_type >
mem_root_deque< Element_type >::mem_root_deque ( const mem_root_deque< Element_type > &  other)
inline

◆ mem_root_deque() [3/3]

template<class Element_type >
mem_root_deque< Element_type >::mem_root_deque ( mem_root_deque< Element_type > &&  other)
inline

◆ ~mem_root_deque()

template<class Element_type >
mem_root_deque< Element_type >::~mem_root_deque ( )
inline

Member Function Documentation

◆ add_block_back()

template<class Element_type >
bool mem_root_deque< Element_type >::add_block_back
private

◆ add_block_front()

template<class Element_type >
bool mem_root_deque< Element_type >::add_block_front
private

◆ add_initial_block()

template<class Element_type >
bool mem_root_deque< Element_type >::add_initial_block ( )
inlineprivate

Adds the first block of elements.

◆ back() [1/2]

template<class Element_type >
Element_type& mem_root_deque< Element_type >::back ( )
inline

Returns the last element in the deque.

◆ back() [2/2]

template<class Element_type >
const Element_type& mem_root_deque< Element_type >::back ( ) const
inline

◆ begin() [1/2]

template<class Element_type >
iterator mem_root_deque< Element_type >::begin ( )
inline

◆ begin() [2/2]

template<class Element_type >
const_iterator mem_root_deque< Element_type >::begin ( ) const
inline

◆ cbegin()

template<class Element_type >
const_iterator mem_root_deque< Element_type >::cbegin ( )
inline

◆ cend()

template<class Element_type >
const_iterator mem_root_deque< Element_type >::cend ( )
inline

◆ clear()

template<class Element_type >
void mem_root_deque< Element_type >::clear ( )
inline

Removes all elements from the deque.

Destructors are called, but since the elements themselves are allocated on the MEM_ROOT, their memory cannot be freed.

◆ crbegin()

template<class Element_type >
reverse_const_iterator mem_root_deque< Element_type >::crbegin ( ) const
inline

◆ crend()

template<class Element_type >
reverse_const_iterator mem_root_deque< Element_type >::crend ( ) const
inline

◆ empty()

template<class Element_type >
bool mem_root_deque< Element_type >::empty ( ) const
inline

◆ end() [1/2]

template<class Element_type >
iterator mem_root_deque< Element_type >::end ( )
inline

◆ end() [2/2]

template<class Element_type >
const_iterator mem_root_deque< Element_type >::end ( ) const
inline

◆ erase() [1/2]

template<class Element_type >
iterator mem_root_deque< Element_type >::erase ( const_iterator  first,
const_iterator  last 
)
inline

Erase all the elements in the specified range.

Parameters
firstiterator that points to the first element to remove
lastiterator that points to the element after the last one to remove
Returns
an iterator to the first element after the removed range

◆ erase() [2/2]

template<class Element_type >
iterator mem_root_deque< Element_type >::erase ( const_iterator  position)
inline

Removes a single element from the array.

Parameters
positioniterator that points to the element to remove
Returns
an iterator to the first element after the removed range

◆ front() [1/2]

template<class Element_type >
Element_type& mem_root_deque< Element_type >::front ( )
inline

Returns the first element in the deque.

◆ front() [2/2]

template<class Element_type >
const Element_type& mem_root_deque< Element_type >::front ( ) const
inline

◆ generation()

template<class Element_type >
size_t mem_root_deque< Element_type >::generation ( ) const
inlineprivate

◆ get()

template<class Element_type >
Element_type& mem_root_deque< Element_type >::get ( size_t  physical_idx) const
inlineprivate

Gets a reference to the memory used to store an element with the given physical index, starting from zero.

Note that block_elements is always a power of two, so the division and modulus operations are cheap.

◆ insert() [1/3]

template<class Element_type >
iterator mem_root_deque< Element_type >::insert ( const_iterator  pos,
const Element_type &  value 
)
inline

Insert an element at a given position.

The element is a copy of the given one.

Parameters
posthe new element is inserted before the element at this position
valuethe value of the new element
Returns
an iterator that points to the inserted element

◆ insert() [2/3]

template<class Element_type >
iterator mem_root_deque< Element_type >::insert ( const_iterator  pos,
Element_type &&  value 
)
inline

Insert an element at a given position.

The element is moved into place.

Parameters
posthe new element is inserted before the element at this position
valuethe value of the new element
Returns
an iterator that points to the inserted element

◆ insert() [3/3]

template<class Element_type >
template<class ForwardIt >
iterator mem_root_deque< Element_type >::insert ( const_iterator  pos,
ForwardIt  first,
ForwardIt  last 
)
inline

◆ invalidate_iterators()

template<class Element_type >
void mem_root_deque< Element_type >::invalidate_iterators ( )
inlineprivate

◆ num_blocks()

template<class Element_type >
size_t mem_root_deque< Element_type >::num_blocks ( ) const
inlineprivate

◆ operator=() [1/2]

template<class Element_type >
mem_root_deque& mem_root_deque< Element_type >::operator= ( const mem_root_deque< Element_type > &  other)
inline

◆ operator=() [2/2]

template<class Element_type >
mem_root_deque& mem_root_deque< Element_type >::operator= ( mem_root_deque< Element_type > &&  other)
inline

◆ operator[]()

template<class Element_type >
Element_type& mem_root_deque< Element_type >::operator[] ( size_t  idx) const
inline

◆ pop_back()

template<class Element_type >
void mem_root_deque< Element_type >::pop_back ( )
inline

Removes the last element from the deque.

◆ pop_front()

template<class Element_type >
void mem_root_deque< Element_type >::pop_front ( )
inline

Removes the first element from the deque.

◆ push_back() [1/2]

template<class Element_type >
bool mem_root_deque< Element_type >::push_back ( const Element_type &  element)
inline

Adds the given element to the end of the deque.

The element is a copy of the given one.

Returns
true on OOM (no change is done if so)

◆ push_back() [2/2]

template<class Element_type >
bool mem_root_deque< Element_type >::push_back ( Element_type &&  element)
inline

Adds the given element to the end of the deque.

The element is moved into place.

Returns
true on OOM (no change is done if so)

◆ push_front() [1/2]

template<class Element_type >
bool mem_root_deque< Element_type >::push_front ( const Element_type &  element)
inline

Adds the given element to the beginning of the deque.

The element is a copy of the given one.

Returns
true on OOM (no change is done if so)

◆ push_front() [2/2]

template<class Element_type >
bool mem_root_deque< Element_type >::push_front ( Element_type &&  element)
inline

Adds the given element to the end of the deque.

The element is moved into place.

◆ rbegin() [1/2]

template<class Element_type >
reverse_iterator mem_root_deque< Element_type >::rbegin ( )
inline

◆ rbegin() [2/2]

template<class Element_type >
reverse_const_iterator mem_root_deque< Element_type >::rbegin ( ) const
inline

◆ rend() [1/2]

template<class Element_type >
reverse_iterator mem_root_deque< Element_type >::rend ( )
inline

◆ rend() [2/2]

template<class Element_type >
reverse_const_iterator mem_root_deque< Element_type >::rend ( ) const
inline

◆ size()

template<class Element_type >
size_t mem_root_deque< Element_type >::size ( ) const
inline

Member Data Documentation

◆ block_elements

template<class Element_type >
constexpr size_t mem_root_deque< Element_type >::block_elements = FindElementsPerBlock<Element_type>()
staticconstexprprivate

Number of elements in each block.

◆ m_begin_idx

template<class Element_type >
size_t mem_root_deque< Element_type >::m_begin_idx = 0
private

Physical index to the first valid element.

◆ m_blocks

template<class Element_type >
Block* mem_root_deque< Element_type >::m_blocks = nullptr
private

Pointer to the first block.

Can be nullptr if there are no elements (this makes the constructor cheaper). Stored on the MEM_ROOT, and needs no destruction, so just a raw pointer.

◆ m_capacity

template<class Element_type >
size_t mem_root_deque< Element_type >::m_capacity = 0
private

Number of blocks, multiplied by block_elements.

(Storing this instead of the number of blocks itself makes testing in push_back cheaper.)

◆ m_end_idx

template<class Element_type >
size_t mem_root_deque< Element_type >::m_end_idx = 0
private

Physical index one past the last valid element.

If begin == end, the array is empty (and then it doesn't matter what the values are).

◆ m_generation

template<class Element_type >
size_t mem_root_deque< Element_type >::m_generation = 0
private

Incremented each time we make an operation that would invalidate iterators.

Asserts use this value in debug mode to be able to verify that they have not been invalidated. (In optimized mode, using an invalidated iterator incurs undefined behavior.)

◆ m_root

template<class Element_type >
MEM_ROOT* mem_root_deque< Element_type >::m_root
private

Pointer to the MEM_ROOT that we store our blocks and elements on.


The documentation for this class was generated from the following file: