MySQL 8.3.0
Source Code Documentation
temptable::Storage Class Reference

Storage container. More...

#include <storage.h>

Classes

class  Iterator
 Iterator over a Storage object. More...
 

Public Types

typedef void Element
 Type used for elements. More...
 
typedef void Page
 Type used for pages. More...
 

Public Member Functions

 Storage (Allocator< uint8_t > *allocator)
 Constructor. More...
 
 Storage (const Storage &)=delete
 Copy constructing is disabled, too expensive and not necessary. More...
 
Storageoperator= (const Storage &)=delete
 Copy assignment is disabled, too expensive and not necessary. More...
 
 Storage (Storage &&other)
 Move constructor. More...
 
Storageoperator= (Storage &&rhs)
 Move assignment. More...
 
 ~Storage ()
 Destructor. More...
 
Iterator begin () const
 Get an iterator, positioned on the first element. More...
 
Iterator end () const
 Get an iterator, positioned after the last element. More...
 
void element_size (size_t element_size)
 Set the element size. More...
 
size_t element_size () const
 Get the element size. More...
 
size_t size () const
 Get the number of elements in the storage. More...
 
Elementback ()
 Get the last element. More...
 
Elementallocate_back ()
 Allocate space for one more element at the end and return a pointer to it. More...
 
void deallocate_back ()
 Destroy the last element. More...
 
Iterator erase (const Iterator &position)
 Delete the element pointed to by position. More...
 
void clear ()
 Delete all elements in the storage. More...
 
size_t number_of_elements_per_page () const
 A simple getter. More...
 

Private Member Functions

size_t page_size () const
 Calculate the size of a page. More...
 
uint8_t * element_meta (Element *element) const
 Get a pointer to element's meta byte(s). More...
 
bool element_first_on_page (Element *element) const
 Check if element is the first on its page. More...
 
void element_first_on_page (bool first_on_page, Element *element)
 Set element's first-on-page flag. More...
 
bool element_last_on_page (Element *element) const
 Check if element is the last on its page. More...
 
void element_last_on_page (bool last_on_page, Element *element)
 Set element's last-on-page flag. More...
 
bool element_deleted (Element *element) const
 Check if element is deleted. More...
 
void element_deleted (bool deleted, Element *element)
 Set element's deleted flag. More...
 
Page ** element_prev_page_ptr (Element *first) const
 Get the previous page. More...
 
Page ** element_next_page_ptr (Element *last) const
 Get the next page. More...
 
Elementprev_element (Element *element) const
 Get the previous element of a given element on the same page. More...
 
Elementnext_element (Element *element) const
 Get the next element of a given element on the same page. More...
 
Elementfirst_possible_element_on_page (Page *page) const
 Get the first element of a page. More...
 
Elementlast_possible_element_on_page (Page *page) const
 Get the last possible element of a page (not the last occupied). More...
 
Page ** page_prev_page_ptr (Page *page) const
 Get a pointer inside a page to the place denoting the previous page. More...
 
Page ** page_next_page_ptr (Page *page) const
 Get a pointer inside a page to the place denoting the next page. More...
 

Private Attributes

Allocator< uint8_t > * m_allocator
 Allocator to use for allocating new pages. More...
 
size_t m_element_size
 Element size in bytes. More...
 
size_t m_bytes_used_per_element
 Number of bytes used per element. More...
 
size_t m_number_of_elements_per_page
 Maximum number of elements a page can store. More...
 
size_t m_number_of_elements
 Number of elements in the container. More...
 
Pagem_first_page
 First page of the storage. More...
 
Pagem_last_page
 Last page of the storage. More...
 
Elementm_last_element
 Last used element in the last page of the storage. More...
 

Static Private Attributes

static constexpr size_t ALIGN_TO = alignof(void *)
 Align elements to this number of bytes. More...
 
static constexpr uint8_t ELEMENT_FIRST_ON_PAGE = 0x1
 Flag that denotes an element is the first element on a page. More...
 
static constexpr uint8_t ELEMENT_LAST_ON_PAGE = 0x2
 Flag that denotes an element is the last element on a page. More...
 
static constexpr uint8_t ELEMENT_DELETED = 0x4
 Flag that denotes an element is deleted. More...
 
static constexpr size_t META_BYTES_PER_ELEMENT = 1
 Extra bytes per element for element metadata. More...
 
static constexpr size_t META_BYTES_PER_PAGE = 2 * sizeof(Page *)
 Extra bytes per page for page metadata. More...
 

Detailed Description

Storage container.

This mimics std::vector and std::deque with the difference that the size of the objects that are being stored in it can be determined at runtime. Elements are stored next to each other in a pre-allocated pages of fixed size STORAGE_PAGE_SIZE.

Member Typedef Documentation

◆ Element

Type used for elements.

We treat elements as black boxes.

◆ Page

Type used for pages.

Constructor & Destructor Documentation

◆ Storage() [1/3]

temptable::Storage::Storage ( Allocator< uint8_t > *  allocator)
inlineexplicit

Constructor.

Parameters
[in,out]allocatorAllocator to use for allocating pages.

◆ Storage() [2/3]

temptable::Storage::Storage ( const Storage )
delete

Copy constructing is disabled, too expensive and not necessary.

◆ Storage() [3/3]

temptable::Storage::Storage ( Storage &&  other)
inline

Move constructor.

Parameters
[in,out]otherObject whose state to grasp, after this call the state of `other` is undefined.

◆ ~Storage()

temptable::Storage::~Storage ( )
inline

Destructor.

Member Function Documentation

◆ allocate_back()

Storage::Element * temptable::Storage::allocate_back ( )
inline

Allocate space for one more element at the end and return a pointer to it.

This will increase size() by one.

Returns
pointer to the newly created (uninitialized) element

◆ back()

Storage::Element * temptable::Storage::back ( )
inline

Get the last element.

Returns
a pointer to the last element

◆ begin()

Storage::Iterator temptable::Storage::begin ( void  ) const
inline

Get an iterator, positioned on the first element.

Returns
iterator

◆ clear()

void temptable::Storage::clear ( )
inline

Delete all elements in the storage.

After this size() will be zero.

◆ deallocate_back()

void temptable::Storage::deallocate_back ( )
inline

Destroy the last element.

This will decrease size() by one.

◆ element_deleted() [1/2]

void temptable::Storage::element_deleted ( bool  deleted,
Element element 
)
inlineprivate

Set element's deleted flag.

Parameters
[in]deletedFlag to set, true if deleted.
[in,out]elementElement to modify.

◆ element_deleted() [2/2]

bool temptable::Storage::element_deleted ( Element element) const
inlineprivate

Check if element is deleted.

Returns
true if deleted
Parameters
[in]elementElement to check.

◆ element_first_on_page() [1/2]

void temptable::Storage::element_first_on_page ( bool  first_on_page,
Element element 
)
inlineprivate

Set element's first-on-page flag.

Parameters
[in]first_on_pageFlag to set, true if first on page.
[in,out]elementElement to modify.

◆ element_first_on_page() [2/2]

bool temptable::Storage::element_first_on_page ( Element element) const
inlineprivate

Check if element is the first on its page.

If the element is the first, then the previous page pointer is stored right before that element (and its meta bytes).

Returns
true if first
Parameters
[in]elementElement to check.

◆ element_last_on_page() [1/2]

void temptable::Storage::element_last_on_page ( bool  last_on_page,
Element element 
)
inlineprivate

Set element's last-on-page flag.

Parameters
[in]last_on_pageFlag to set, true if last on page.
[in,out]elementElement to modify.

◆ element_last_on_page() [2/2]

bool temptable::Storage::element_last_on_page ( Element element) const
inlineprivate

Check if element is the last on its page.

If the element is the last, then the next page pointer is stored right after that element.

Returns
true if last
Parameters
[in]elementElement to check.

◆ element_meta()

uint8_t * temptable::Storage::element_meta ( Element element) const
inlineprivate

Get a pointer to element's meta byte(s).

Returns
pointer to meta byte(s)
Parameters
[in]elementElement whose meta byte(s) to get a pointer to.

◆ element_next_page_ptr()

Storage::Page ** temptable::Storage::element_next_page_ptr ( Element last) const
inlineprivate

Get the next page.

Undefined if !element_last_on_page().

Returns
next page or nullptr if this is the last page
Parameters
[in]lastThe last element on a page.

◆ element_prev_page_ptr()

Storage::Page ** temptable::Storage::element_prev_page_ptr ( Element first) const
inlineprivate

Get the previous page.

Undefined if !element_first_on_page().

Returns
previous page or nullptr if this is the first page
Parameters
[in]firstThe first element on a page.

◆ element_size() [1/2]

size_t temptable::Storage::element_size ( ) const
inline

Get the element size.

Returns
element size in bytes.

◆ element_size() [2/2]

void temptable::Storage::element_size ( size_t  element_size)
inline

Set the element size.

Only allowed if the storage is empty.

Parameters
[in]element_sizeNew element size to set, in bytes.

◆ end()

Storage::Iterator temptable::Storage::end ( void  ) const
inline

Get an iterator, positioned after the last element.

Returns
iterator

◆ erase()

Storage::Iterator temptable::Storage::erase ( const Iterator position)
inline

Delete the element pointed to by position.

Subsequent or previous iterators are not invalidated. The memory occupied by the deleted element is not returned to the underlying allocator.

Returns
an iterator to the next element (or end() if position points to the last element before this call)
Parameters
[in]positionDelete element at this position.

◆ first_possible_element_on_page()

Storage::Element * temptable::Storage::first_possible_element_on_page ( Page page) const
inlineprivate

Get the first element of a page.

Returns
pointer to first element, may be delete-marked
Parameters
[in]pagePage whose first element to fetch.

◆ last_possible_element_on_page()

Storage::Element * temptable::Storage::last_possible_element_on_page ( Page page) const
inlineprivate

Get the last possible element of a page (not the last occupied).

Returns
pointer where the last element would reside if the page is full, may be delete-marked.
Parameters
[in]pagePage whose last element to fetch.

◆ next_element()

Storage::Element * temptable::Storage::next_element ( Element element) const
inlineprivate

Get the next element of a given element on the same page.

Undefined if this is the last element on the page.

Returns
pointer to next element, may be delete-marked
Parameters
[in]elementElement whose sibling in the page to fetch.

◆ number_of_elements_per_page()

size_t temptable::Storage::number_of_elements_per_page ( ) const
inline

A simple getter.

◆ operator=() [1/2]

Storage & temptable::Storage::operator= ( const Storage )
delete

Copy assignment is disabled, too expensive and not necessary.

◆ operator=() [2/2]

Storage & temptable::Storage::operator= ( Storage &&  rhs)
inline

Move assignment.

Parameters
[in,out]rhsObject whose state to grasp, after this call the state of `rhs` is undefined.

◆ page_next_page_ptr()

Storage::Page ** temptable::Storage::page_next_page_ptr ( Page page) const
inlineprivate

Get a pointer inside a page to the place denoting the next page.

Returns
pointer to the pointer to the next page
Parameters
[in]pagePage whose next to fetch.

◆ page_prev_page_ptr()

Storage::Page ** temptable::Storage::page_prev_page_ptr ( Page page) const
inlineprivate

Get a pointer inside a page to the place denoting the previous page.

Returns
pointer to the pointer to the previous page
Parameters
[in]pagePage whose previous to fetch.

◆ page_size()

size_t temptable::Storage::page_size ( ) const
inlineprivate

Calculate the size of a page.

This is usually a little bit less than STORAGE_PAGE_SIZE. For example if STORAGE_PAGE_SIZE == 100 and our element size is 10 and we need 4 extra bytes per page, then the calculated page size will be 94: 9 elements (10 bytes each) and the extra 4 bytes.

Returns
page size in bytes

◆ prev_element()

Storage::Element * temptable::Storage::prev_element ( Element element) const
inlineprivate

Get the previous element of a given element on the same page.

Undefined if this is the first element on the page.

Returns
pointer to previous element, may be delete-marked
Parameters
[in]elementElement whose sibling in the page to fetch.

◆ size()

size_t temptable::Storage::size ( ) const
inline

Get the number of elements in the storage.

Returns
number of elements.

Member Data Documentation

◆ ALIGN_TO

constexpr size_t temptable::Storage::ALIGN_TO = alignof(void *)
staticconstexprprivate

Align elements to this number of bytes.

◆ ELEMENT_DELETED

constexpr uint8_t temptable::Storage::ELEMENT_DELETED = 0x4
staticconstexprprivate

Flag that denotes an element is deleted.

Deleted elements are skipped during iteration.

◆ ELEMENT_FIRST_ON_PAGE

constexpr uint8_t temptable::Storage::ELEMENT_FIRST_ON_PAGE = 0x1
staticconstexprprivate

Flag that denotes an element is the first element on a page.

◆ ELEMENT_LAST_ON_PAGE

constexpr uint8_t temptable::Storage::ELEMENT_LAST_ON_PAGE = 0x2
staticconstexprprivate

Flag that denotes an element is the last element on a page.

◆ m_allocator

Allocator<uint8_t>* temptable::Storage::m_allocator
private

Allocator to use for allocating new pages.

◆ m_bytes_used_per_element

size_t temptable::Storage::m_bytes_used_per_element
private

Number of bytes used per element.

This accounts for element size, alignment and our element meta bytes.

◆ m_element_size

size_t temptable::Storage::m_element_size
private

Element size in bytes.

◆ m_first_page

Page* temptable::Storage::m_first_page
private

First page of the storage.

◆ m_last_element

Element* temptable::Storage::m_last_element
private

Last used element in the last page of the storage.

The last page may not be fully occupied, so this may point somewhere in the middle of it.

◆ m_last_page

Page* temptable::Storage::m_last_page
private

Last page of the storage.

◆ m_number_of_elements

size_t temptable::Storage::m_number_of_elements
private

Number of elements in the container.

Not counting deleted ones.

◆ m_number_of_elements_per_page

size_t temptable::Storage::m_number_of_elements_per_page
private

Maximum number of elements a page can store.

◆ META_BYTES_PER_ELEMENT

constexpr size_t temptable::Storage::META_BYTES_PER_ELEMENT = 1
staticconstexprprivate

Extra bytes per element for element metadata.

It must store all ELEMENT_* bits.

◆ META_BYTES_PER_PAGE

constexpr size_t temptable::Storage::META_BYTES_PER_PAGE = 2 * sizeof(Page *)
staticconstexprprivate

Extra bytes per page for page metadata.

This stores the previous and next page pointers.


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