A simple index based on a sorted array that maps keys to their tuple_id. More...

#include <Index.hpp>

Inheritance diagram for m::idx::ArrayIndex< Key >:

Collaboration diagram for m::idx::ArrayIndex< Key >:

Public Types
using	key_type = Key

using	value_type = std::size_t

using	entry_type = std::pair< key_type, value_type >

using	iterator = entry_type *

using	const_iterator = const entry_type *

Public Member Functions
	ArrayIndex ()

void	bulkload (const Table &table, const Schema &key_schema) override
	Bulkloads the index from `table` on the key contained in `key_schema` by executing a query and adding one entry after another.

std::size_t	num_entries () const override
	Returns the number of entries in the index.

IndexMethod	method () const override
	Returns the `IndexMethod` of the index.

const memory::Memory &	memory () const override
	Returns the underlying memory of the index.

std::size_t	size_in_bytes () const override

void	add (const key_type key, const value_type value)
	Adds a single pair of `key` and `value` to the index.

virtual void	finalize ()
	Sorts the underlying vector and flags the index as finalized.

bool	finalized () const
	Returns `true` iff the index is currently finalized.

virtual const_iterator	lower_bound (const key_type key) const
	Returns an iterator pointing to the first entry of the vector such that `entry.key` < `key` is `false`, i.e.

virtual const_iterator	upper_bound (const key_type key) const
	Returns an iterator pointing to the first entry of the vector such that `entry.key` < `key` is `true`, i.e.

const_iterator	begin () const

const_iterator	cbegin () const

const_iterator	end () const

const_iterator	cend () const

void	dump (std::ostream &out) const override

void	dump () const override

Static Public Attributes
static constexpr std::size_t	ALLOCATION_SIZE = 1UL << 30
	1 GiB

Protected Member Functions
iterator	begin ()
	Returns an iterator pointing to the first entry of the index.

iterator	end ()
	Returns an interator pointing to the first element following the last entry of the index.

Static Protected Member Functions
static std::string	build_query (const Table &table, const Schema &schema)
	Constructs a query string to select all attributes in `schema` from `table`.

Protected Attributes
memory::Memory	memory_
	‍the underlying memory for a vector holding the index entries consisting of pairs of key and value

std::size_t	num_entries_
	number of entries

bool	finalized_
	flag to signalize whether index is finalized, i.e. array is sorted

struct {
const U &_rhs const

key_type rhs = M_CONSTEXPR_COND((std::same_as<U, key_type>), _rhs, _rhs.first)

}	cmp
	Custom comparator class to handle the special case of.

Detailed Description

template<typename Key>
struct m::idx::ArrayIndex< Key >

A simple index based on a sorted array that maps keys to their tuple_id.

Definition at line 57 of file Index.hpp.

Member Typedef Documentation

◆ const_iterator

template<typename Key >

using m::idx::ArrayIndex< Key >::const_iterator = const entry_type*

Definition at line 69 of file Index.hpp.

◆ entry_type

template<typename Key >

using m::idx::ArrayIndex< Key >::entry_type = std::pair<key_type, value_type>

Definition at line 67 of file Index.hpp.

◆ iterator

template<typename Key >

using m::idx::ArrayIndex< Key >::iterator = entry_type*

Definition at line 68 of file Index.hpp.

◆ key_type

template<typename Key >

using m::idx::ArrayIndex< Key >::key_type = Key

Definition at line 65 of file Index.hpp.

◆ value_type

template<typename Key >

using m::idx::ArrayIndex< Key >::value_type = std::size_t

Definition at line 66 of file Index.hpp.

Constructor & Destructor Documentation

◆ ArrayIndex()

template<typename Key >

ArrayIndex::ArrayIndex

Definition at line 53 of file Index.cpp.

Member Function Documentation

◆ add()

template<typename Key >

void ArrayIndex::add	(	const key_type	key,
		const value_type	value
	)

Adds a single pair of key and value to the index.

Note that finalize() has to be called afterwards for the vector to be sorted and the index to be usable.

Definition at line 147 of file Index.cpp.

References m::Catalog::Get(), and m::Catalog::pool().

◆ begin() [1/2]

template<typename Key >

iterator m::idx::ArrayIndex< Key >::begin ( )

inlineprotected

Returns an iterator pointing to the first entry of the index.

Definition at line 145 of file Index.hpp.

References m::memory::Memory::addr(), and m::idx::ArrayIndex< Key >::memory_.

Referenced by m::idx::ArrayIndex< Key >::cbegin(), m::idx::ArrayIndex< Key >::finalize(), m::idx::ArrayIndex< Key >::lower_bound(), m::idx::RecursiveModelIndex< Key >::lower_bound(), m::idx::RecursiveModelIndex< Key >::lower_bound_exponential_search(), m::idx::ArrayIndex< Key >::upper_bound(), m::idx::RecursiveModelIndex< Key >::upper_bound(), and m::idx::RecursiveModelIndex< Key >::upper_bound_exponential_search().

◆ begin() [2/2]

template<typename Key >

const_iterator m::idx::ArrayIndex< Key >::begin ( ) const

inline

Definition at line 147 of file Index.hpp.

References m::memory::Memory::addr(), and m::idx::ArrayIndex< Key >::memory_.

◆ build_query()

std::string IndexBase::build_query	(	const Table &	table,
		const Schema &	schema
	)

staticprotectedinherited

Constructs a query string to select all attributes in schema from table.

Definition at line 40 of file Index.cpp.

References m::Schema::at(), m::Schema::entry_type::id, m::Table::name(), and m::Schema::num_entries().

◆ bulkload()

template<typename Key >

void ArrayIndex::bulkload	(	const Table &	table,
		const Schema &	key_schema
	)

overridevirtual

Bulkloads the index from table on the key contained in key_schema by executing a query and adding one entry after another.

The index is finalized in the end. Throws m::invalid_arguent if key_schema contains more than one entry or key_type and the attribute type of the entry in key_schema do not match.

Implements m::idx::IndexBase.

Definition at line 58 of file Index.cpp.

References m::Value::as(), m::Schema::at(), CHECK, m::Catalog::create_backend(), m::execute_query(), m::Catalog::Get(), m::Options::Get(), m::Tuple::get(), M_unreachable, m::Schema::num_entries(), m::statement_from_string(), m::Schema::entry_type::type, and m::visit().

◆ cbegin()

template<typename Key >

const_iterator m::idx::ArrayIndex< Key >::cbegin ( ) const

inline

Definition at line 148 of file Index.hpp.

References m::idx::ArrayIndex< Key >::begin().

◆ cend()

template<typename Key >

const_iterator m::idx::ArrayIndex< Key >::cend ( ) const

inline

Definition at line 154 of file Index.hpp.

References m::idx::ArrayIndex< Key >::end().

◆ dump() [1/2]

template<typename Key >

void m::idx::ArrayIndex< Key >::dump ( ) const

inlineoverridevirtual

Implements m::idx::IndexBase.

Reimplemented in m::idx::RecursiveModelIndex< Key >.

Definition at line 157 of file Index.hpp.

References m::idx::ArrayIndex< Key >::dump().

Referenced by m::idx::ArrayIndex< Key >::dump().

◆ dump() [2/2]

template<typename Key >

void m::idx::ArrayIndex< Key >::dump ( std::ostream & out ) const

inlineoverridevirtual

Implements m::idx::IndexBase.

Reimplemented in m::idx::RecursiveModelIndex< Key >.

Definition at line 156 of file Index.hpp.

◆ end() [1/2]

template<typename Key >

iterator m::idx::ArrayIndex< Key >::end ( )

inlineprotected

Returns an interator pointing to the first element following the last entry of the index.

Definition at line 151 of file Index.hpp.

References m::memory::Memory::addr(), m::idx::ArrayIndex< Key >::memory_, and m::idx::ArrayIndex< Key >::num_entries_.

Referenced by m::idx::ArrayIndex< Key >::cend(), m::idx::ArrayIndex< Key >::finalize(), m::idx::ArrayIndex< Key >::lower_bound(), m::idx::RecursiveModelIndex< Key >::lower_bound_exponential_search(), m::idx::ArrayIndex< Key >::upper_bound(), and m::idx::RecursiveModelIndex< Key >::upper_bound_exponential_search().

◆ end() [2/2]

template<typename Key >

const_iterator m::idx::ArrayIndex< Key >::end ( ) const

inline

Definition at line 153 of file Index.hpp.

References m::memory::Memory::addr(), m::idx::ArrayIndex< Key >::memory_, and m::idx::ArrayIndex< Key >::num_entries_.

◆ finalize()

template<typename Key >

virtual void m::idx::ArrayIndex< Key >::finalize ( )

inlinevirtual

Sorts the underlying vector and flags the index as finalized.

Reimplemented in m::idx::RecursiveModelIndex< Key >.

Definition at line 119 of file Index.hpp.

References m::idx::ArrayIndex< Key >::begin(), m::idx::ArrayIndex< Key >::cmp, m::idx::ArrayIndex< Key >::end(), and m::idx::ArrayIndex< Key >::finalized_.

◆ finalized()

template<typename Key >

bool m::idx::ArrayIndex< Key >::finalized ( ) const

inline

Returns true iff the index is currently finalized.

Definition at line 125 of file Index.hpp.

References m::idx::ArrayIndex< Key >::finalized_.

Referenced by m::idx::RecursiveModelIndex< Key >::lower_bound(), and m::idx::RecursiveModelIndex< Key >::upper_bound().

◆ lower_bound()

template<typename Key >

virtual const_iterator m::idx::ArrayIndex< Key >::lower_bound ( const key_type key ) const

inlinevirtual

Returns an iterator pointing to the first entry of the vector such that entry.key < key is false, i.e.

that is greater than or equal to key, or end() if no such element is found. Throws m::exception if the index is not finalized.

Reimplemented in m::idx::RecursiveModelIndex< Key >.

Definition at line 130 of file Index.hpp.

References m::idx::ArrayIndex< Key >::begin(), m::idx::ArrayIndex< Key >::cmp, m::idx::ArrayIndex< Key >::end(), and m::idx::ArrayIndex< Key >::finalized_.

◆ memory()

template<typename Key >

const memory::Memory & m::idx::ArrayIndex< Key >::memory ( ) const

inlineoverridevirtual

Returns the underlying memory of the index.

Implements m::idx::IndexBase.

Reimplemented in m::idx::RecursiveModelIndex< Key >.

Definition at line 108 of file Index.hpp.

References m::idx::ArrayIndex< Key >::memory_.

◆ method()

template<typename Key >

IndexMethod m::idx::ArrayIndex< Key >::method ( ) const

inlineoverridevirtual

Returns the IndexMethod of the index.

Implements m::idx::IndexBase.

Reimplemented in m::idx::RecursiveModelIndex< Key >.

Definition at line 105 of file Index.hpp.

References m::idx::Array.

◆ num_entries()

template<typename Key >

std::size_t m::idx::ArrayIndex< Key >::num_entries ( ) const

inlineoverridevirtual

Returns the number of entries in the index.

Implements m::idx::IndexBase.

Definition at line 102 of file Index.hpp.

References m::idx::ArrayIndex< Key >::num_entries_.

Referenced by m::idx::RecursiveModelIndex< Key >::predict().

◆ size_in_bytes()

template<typename Key >

std::size_t m::idx::ArrayIndex< Key >::size_in_bytes ( ) const

inlineoverridevirtual

Implements m::idx::IndexBase.

Reimplemented in m::idx::RecursiveModelIndex< Key >.

Definition at line 111 of file Index.hpp.

References m::idx::ArrayIndex< Key >::num_entries_.

◆ upper_bound()

template<typename Key >

virtual const_iterator m::idx::ArrayIndex< Key >::upper_bound ( const key_type key ) const

inlinevirtual

Returns an iterator pointing to the first entry of the vector such that entry.key < key is true, i.e.

that is strictly greater than key, or end() if no such element is found. Throws m::exception if the index is not finalized.

Reimplemented in m::idx::RecursiveModelIndex< Key >.

Definition at line 138 of file Index.hpp.

References m::idx::ArrayIndex< Key >::begin(), m::idx::ArrayIndex< Key >::cmp, m::idx::ArrayIndex< Key >::end(), and m::idx::ArrayIndex< Key >::finalized_.

Field Documentation

◆ ALLOCATION_SIZE

template<typename Key >

constexpr std::size_t m::idx::ArrayIndex< Key >::ALLOCATION_SIZE = 1UL << 30

staticconstexpr

1 GiB

Definition at line 60 of file Index.hpp.

◆

struct { ... } m::idx::ArrayIndex< Key >::cmp

Custom comparator class to handle the special case of.

Template Parameters

key_type being const char*.

Referenced by m::idx::ArrayIndex< Key >::finalize(), m::idx::ArrayIndex< Key >::lower_bound(), m::idx::RecursiveModelIndex< Key >::lower_bound_exponential_search(), m::idx::ArrayIndex< Key >::upper_bound(), and m::idx::RecursiveModelIndex< Key >::upper_bound_exponential_search().

◆ const

template<typename Key >

const U& _rhs m::idx::ArrayIndex< Key >::const

Initial value:

{

key_type lhs = M_CONSTEXPR_COND((std::same_as<T, key_type>), _lhs, _lhs.first)

M_CONSTEXPR_COND

#define M_CONSTEXPR_COND(COND, IF_TRUE, IF_FALSE)

Definition: macro.hpp:54

m::idx::ArrayIndex::key_type

Key key_type

Definition: Index.hpp:65

Definition at line 83 of file Index.hpp.

◆ finalized_

template<typename Key >

bool m::idx::ArrayIndex< Key >::finalized_

protected

flag to signalize whether index is finalized, i.e. array is sorted

Definition at line 75 of file Index.hpp.

Referenced by m::idx::ArrayIndex< Key >::finalize(), m::idx::ArrayIndex< Key >::finalized(), m::idx::ArrayIndex< Key >::lower_bound(), and m::idx::ArrayIndex< Key >::upper_bound().

◆ memory_

template<typename Key >

memory::Memory m::idx::ArrayIndex< Key >::memory_

protected

‍the underlying memory for a vector holding the index entries consisting of pairs of key and value

Definition at line 73 of file Index.hpp.

Referenced by m::idx::ArrayIndex< Key >::begin(), m::idx::ArrayIndex< Key >::end(), and m::idx::ArrayIndex< Key >::memory().

◆ num_entries_

template<typename Key >

std::size_t m::idx::ArrayIndex< Key >::num_entries_

protected

number of entries

Definition at line 74 of file Index.hpp.

Referenced by m::idx::ArrayIndex< Key >::end(), m::idx::ArrayIndex< Key >::num_entries(), and m::idx::ArrayIndex< Key >::size_in_bytes().

◆ rhs

template<typename Key >

key_type m::idx::ArrayIndex< Key >::rhs = M_CONSTEXPR_COND((std::same_as<U, key_type>), _rhs, _rhs.first)

Definition at line 85 of file Index.hpp.

The documentation for this struct was generated from the following files:

include/mutable/storage/Index.hpp
src/storage/Index.cpp

Public Types

Public Member Functions

Static Public Attributes

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ entry_type

◆ iterator

◆ key_type

◆ value_type

Constructor & Destructor Documentation

◆ ArrayIndex()

Member Function Documentation

◆ add()

◆ begin() [1/2]

◆ begin() [2/2]

◆ build_query()

◆ bulkload()

◆ cbegin()

◆ cend()

◆ dump() [1/2]

◆ dump() [2/2]

◆ end() [1/2]

◆ end() [2/2]

◆ finalize()

◆ finalized()

◆ lower_bound()

◆ memory()

◆ method()

◆ num_entries()

◆ size_in_bytes()

◆ upper_bound()

Field Documentation

◆ ALLOCATION_SIZE

◆

◆ const

◆ finalized_

◆ memory_

◆ num_entries_

◆ rhs