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	container_type = std::vector< entry_type >

using	const_iterator = typename container_type::const_iterator

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.

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
	Returns an iterator pointing to the first entry of the index.

const_iterator	cbegin () const

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

const_iterator	cend () const

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

void	dump () const override

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
container_type	data_
	A vector holding the index entries consisting of pairs of key and value.

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 52 of file Index.hpp.

Member Typedef Documentation

◆ const_iterator

template<typename Key >

using m::idx::ArrayIndex< Key >::const_iterator = typename container_type::const_iterator

Definition at line 58 of file Index.hpp.

◆ container_type

template<typename Key >

using m::idx::ArrayIndex< Key >::container_type = std::vector<entry_type>

Definition at line 57 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 56 of file Index.hpp.

◆ key_type

template<typename Key >

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

Definition at line 54 of file Index.hpp.

◆ value_type

template<typename Key >

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

Definition at line 55 of file Index.hpp.

Constructor & Destructor Documentation

◆ ArrayIndex()

template<typename Key >

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

inline

Definition at line 81 of file Index.hpp.

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 142 of file Index.cpp.

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

◆ begin()

template<typename Key >

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

inline

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

Definition at line 124 of file Index.hpp.

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

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

◆ 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 53 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 125 of file Index.hpp.

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

◆ cend()

template<typename Key >

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

inline

Definition at line 128 of file Index.hpp.

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

◆ 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 131 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 130 of file Index.hpp.

◆ end()

template<typename Key >

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

inline

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

Definition at line 127 of file Index.hpp.

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

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

◆ 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 99 of file Index.hpp.

References m::idx::ArrayIndex< Key >::cmp, m::idx::ArrayIndex< Key >::data_, 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 105 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 110 of file Index.hpp.

References m::idx::ArrayIndex< Key >::cmp, m::idx::ArrayIndex< Key >::data_, and m::idx::ArrayIndex< Key >::finalized_.

◆ 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 92 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 89 of file Index.hpp.

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

◆ 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 118 of file Index.hpp.

References m::idx::ArrayIndex< Key >::cmp, m::idx::ArrayIndex< Key >::data_, and m::idx::ArrayIndex< Key >::finalized_.

Field Documentation

◆

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:54

Definition at line 70 of file Index.hpp.

◆ data_

template<typename Key >

container_type m::idx::ArrayIndex< Key >::data_

protected

A vector holding the index entries consisting of pairs of key and value.

Definition at line 61 of file Index.hpp.

Referenced by m::idx::ArrayIndex< Key >::begin(), m::idx::ArrayIndex< Key >::cbegin(), m::idx::ArrayIndex< Key >::cend(), m::idx::ArrayIndex< Key >::end(), m::idx::ArrayIndex< Key >::finalize(), m::idx::ArrayIndex< Key >::lower_bound(), m::idx::ArrayIndex< Key >::num_entries(), m::idx::RecursiveModelIndex< Key >::predict(), and m::idx::ArrayIndex< Key >::upper_bound().

◆ 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 62 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().

◆ 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 72 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 Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ container_type

◆ entry_type

◆ key_type

◆ value_type

Constructor & Destructor Documentation

◆ ArrayIndex()

Member Function Documentation

◆ add()

◆ begin()

◆ build_query()

◆ bulkload()

◆ cbegin()

◆ cend()

◆ dump() [1/2]

◆ dump() [2/2]

◆ end()

◆ finalize()

◆ finalized()

◆ lower_bound()

◆ method()

◆ num_entries()

◆ upper_bound()

Field Documentation

◆

◆ const

◆ data_

◆ finalized_

◆ rhs