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...

Storage &	operator= (const Storage &)=delete
	Copy assignment is disabled, too expensive and not necessary. More...

	Storage (Storage &&other)
	Move constructor. More...

Storage &	operator= (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...

Element *	back ()
	Get the last element. More...

Element *	allocate_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...

Element *	prev_element (Element *element) const
	Get the previous element of a given element on the same page. More...

Element *	next_element (Element *element) const
	Get the next element of a given element on the same page. More...

Element *	first_possible_element_on_page (Page *page) const
	Get the first element of a page. More...

Element *	last_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...

Page *	m_first_page
	First page of the storage. More...

Page *	m_last_page
	Last page of the storage. More...

Element *	m_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

typedef void temptable::Storage::Element

Type used for elements.

We treat elements as black boxes.

◆ Page

typedef void temptable::Storage::Page

Type used for pages.

Constructor & Destructor Documentation

◆ Storage() [1/3]

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

inlineexplicit

Constructor.

Parameters

[in,out] allocator Allocator 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] other Object 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]	deleted	Flag to set, true if deleted.
[in,out]	element	Element 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] element Element 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_page	Flag to set, true if first on page.
[in,out]	element	Element 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] element Element 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_page	Flag to set, true if last on page.
[in,out]	element	Element 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] element Element 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] element Element 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] last The 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] first The 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_size New 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] position Delete 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] page Page 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] page Page 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] element Element 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] rhs Object 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] page Page 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] page Page 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] element Element 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:

storage/temptable/include/temptable/storage.h

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ Element

◆ Page

Constructor & Destructor Documentation

◆ Storage() [1/3]

◆ Storage() [2/3]

◆ Storage() [3/3]

◆ ~Storage()

Member Function Documentation

◆ allocate_back()

◆ back()

◆ begin()

◆ clear()

◆ deallocate_back()

◆ element_deleted() [1/2]

◆ element_deleted() [2/2]

◆ element_first_on_page() [1/2]

◆ element_first_on_page() [2/2]

◆ element_last_on_page() [1/2]

◆ element_last_on_page() [2/2]

◆ element_meta()

◆ element_next_page_ptr()

◆ element_prev_page_ptr()

◆ element_size() [1/2]

◆ element_size() [2/2]

◆ end()

◆ erase()

◆ first_possible_element_on_page()

◆ last_possible_element_on_page()

◆ next_element()

◆ number_of_elements_per_page()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ page_next_page_ptr()

◆ page_prev_page_ptr()

◆ page_size()

◆ prev_element()

◆ size()

Member Data Documentation

◆ ALIGN_TO

◆ ELEMENT_DELETED

◆ ELEMENT_FIRST_ON_PAGE

◆ ELEMENT_LAST_ON_PAGE

◆ m_allocator

◆ m_bytes_used_per_element

◆ m_element_size

◆ m_first_page

◆ m_last_element

◆ m_last_page

◆ m_number_of_elements

◆ m_number_of_elements_per_page

◆ META_BYTES_PER_ELEMENT

◆ META_BYTES_PER_PAGE