API Reference¶

Containers¶

mdds::trie_map¶

template<typename KeyT, typename ValueT, typename TraitsT = trie::default_traits> class trie_map¶

Trie map provides storage for multiple key-value pairs where keys are either strings, or otherwise consist of arrays of characters. The keys are stored in an ordered tree structure known as trie, or sometimes referred to as prefix tree.

Public Types

using traits_type = TraitsT ¶

typedef packed_trie_map<KeyT, ValueT, TraitsT> packed_type¶

typedef KeyT key_type¶

typedef key_type::value_type key_unit_type¶

typedef ValueT value_type¶

typedef size_t size_type¶

using const_iterator = trie::detail::const_iterator<trie_map>¶

using iterator = trie::detail::iterator<trie_map>¶

typedef trie::detail::search_results<trie_map> search_results¶

Public Functions

trie_map()¶: Default constructor.

trie_map(const trie_map &other)¶

trie_map(trie_map &&other)¶

const_iterator begin() const¶

iterator begin()¶

const_iterator end() const¶

iterator end()¶

trie_map &operator=(trie_map other)¶

bool operator==(const trie_map &other) const¶

bool operator!=(const trie_map &other) const¶

void swap(trie_map &other)¶

const_node_type root_node() const¶

Obtain a root node of the trie to traverse it node-by-node.

Returns:: Root node of the trie.

void insert(const key_type &key, value_type value)¶

Insert a new key-value pair.

Parameters:

key – key value.
value – value to associate with the key.

void insert(const key_unit_type *key, size_type len, value_type value)¶

Insert a new key-value pair.

Parameters:

key – pointer to the first character of a character array that stores key value.
len – length of the character array storing the key.
value – value to associate with the key.

bool erase(const key_unit_type *key, size_type len)¶

Erase a key and the value associated with it.

Parameters:

key – pointer to the first character of a character array that stores key value.
len – length of the character array storing the key.

Returns:

true if a key is erased, false otherwise.

const_iterator find(const key_type &key) const¶

Find a value associated with a specified key.

Parameters:: key – key to match.
Returns:: immutable iterator that references a value associated with the key, or the end position in case the key is not found.

const_iterator find(const key_unit_type *input, size_type len) const¶

Find a value associated with a specified key.

Parameters:

input – pointer to an array whose value represents the key to match.
len – length of the matching key value.

Returns:

immutable iterator that references a value associated with the key, or the end position in case the key is not found.

iterator find(const key_type &key)¶

Find a value associated with a specified key.

Parameters:: key – key to match.
Returns:: mutable iterator that references a value associated with the key, or the end position in case the key is not found.

iterator find(const key_unit_type *input, size_type len)¶

Find a value associated with a specified key.

Parameters:

input – pointer to an array whose value represents the key to match.
len – length of the matching key value.

Returns:

mutable iterator that references a value associated with the key, or the end position in case the key is not found.

search_results prefix_search(const key_type &prefix) const¶

Retrieve all key-value pairs whose keys start with specified prefix. You can also retrieve all key-value pairs by passing a null prefix and a length of zero.

Parameters:: prefix – prefix to match.
Returns:: results object that contains all matching key-value pairs. The results are sorted by the key in ascending order.

search_results prefix_search(const key_unit_type *prefix, size_type len) const¶

Retrieve all key-value pairs whose keys start with specified prefix. You can also retrieve all key-value pairs by passing a null prefix and a length of zero.

Parameters:

prefix – pointer to an array whose value represents the prefix to match.
len – length of the prefix value to match.

Returns:

results object that contains all matching key-value pairs. The results are sorted by the key in ascending order.

size_type size() const¶

Return the number of entries in the map.

Returns:: the number of entries in the map.

bool empty() const noexcept¶

void clear()¶: Empty the container.

packed_type pack()¶

Create a compressed and immutable version of the container which provides better search performance and requires much less memory footprint.

Note

Calling this method will move all stored values into the packed variant. You should make a copy of the instance first if you need to preserve the original.

Throws:: mdds::size_error – When the number of entries exceeds maximum allowed number of key-value pairs. See trie::default_traits::pack_value_type for more detailed explanation.
Returns:: an instance of mdds::packed_trie_map with the same content, with all the values stored in the original instance moved into the returned instance.

Friends

friend class trie::detail::iterator_base< trie_map, true >

friend class trie::detail::iterator_base< trie_map, false >

friend class trie::detail::const_iterator< trie_map >

friend class trie::detail::iterator< trie_map >

friend class trie::detail::search_results< trie_map >

class const_node_type¶

Represents an individual node of a trie.

Public Functions

const_node_type()¶

const_node_type(const const_node_type &other)¶

const_node_type &operator=(const const_node_type &other)¶

bool valid() const¶

Query whether or not the node references an existing node in a tree.

Returns:: True if the node references an existing node in a tree, or false if the node does not reference any node in any tree.

bool has_child() const¶

Query whether or not the node has at least one child node.

Returns:: True if the node has at least one child node, or false if the node has no child nodes at all.

bool has_value() const¶

Query whether or not the node has a value associated with it.

Returns:: True if the node has a value, otherwise false.

const value_type &value() const¶

Access the value associated with the node.

Warning

The caller must ensure that the node has a value via has_value() before calling this method to access it. Calling this method on a node without a value is undefined.

Returns:: Reference to the value associated with the node.

const_node_type child(key_unit_type c) const¶

Move to a child node by a unit key.

Parameters:: c – A unit key associated with a child node relative to the current node.
Returns:: A valid node if a child node exists for the unit key passed to this method, otherwise an invalid node is returned.

mdds::packed_trie_map¶

template<typename KeyT, typename ValueT, typename TraitsT = trie::default_traits> class packed_trie_map¶

An immutable trie container that packs its content into a contiguous array to achieve both space efficiency and lookup performance. The user of this data structure must provide a pre-constructed list of key-value entries that are sorted by the key in ascending order, or construct from an instance of mdds::trie_map.

Note that, since this container is immutable, the content of the container cannot be modified once constructed.

Public Types

using traits_type = TraitsT ¶

typedef KeyT key_type¶

typedef key_type::value_type key_unit_type¶

typedef ValueT value_type¶

typedef size_t size_type¶

typedef trie::detail::packed_iterator_base<packed_trie_map> const_iterator¶

typedef trie::detail::packed_search_results<packed_trie_map> search_results¶

Public Functions

packed_trie_map()¶

packed_trie_map(const entry *entries, size_type entry_size)¶

Constructor that initializes the content from a static list of key-value entries. The caller must ensure that the key-value entries are sorted in ascending order, else the behavior is undefined.

Parameters:

entries – pointer to the array of key-value entries.
entry_size – size of the key-value entry array.

Throws:

mdds::size_error – When the number of entries exceeds maximum allowed number of key-value pairs. See trie::default_traits::pack_value_type for more detailed explanation.

packed_trie_map(const trie_map<KeyT, ValueT, TraitsT> &other)¶

Constructor to allow construction of an instance from the content of a mdds::trie_map instance.

Parameters:: other – mdds::trie_map instance to build content from.
Throws:: mdds::size_error – When the number of entries exceeds maximum allowed number of key-value pairs. See trie::default_traits::pack_value_type for more detailed explanation.

packed_trie_map(const packed_trie_map &other)¶

packed_trie_map(packed_trie_map &&other)¶

packed_trie_map &operator=(packed_trie_map other)¶

bool operator==(const packed_trie_map &other) const¶

bool operator!=(const packed_trie_map &other) const¶

const_iterator begin() const¶

const_iterator end() const¶

const_iterator cbegin() const¶

const_iterator cend() const¶

const_iterator find(const key_type &key) const¶

Find a value associated with a specified key.

Parameters:: key – key to match.
Returns:: iterator that references a value associated with the key, or the end position in case the key is not found.

const_iterator find(const key_unit_type *input, size_type len) const¶

Find a value associated with a specified key.

Parameters:

input – pointer to an array whose value represents the key to match.
len – length of the matching key value.

Returns:

iterator that references a value associated with the key, or the end position in case the key is not found.

search_results prefix_search(const key_type &prefix) const¶

Retrieve all key-value pairs whose keys start with specified prefix. You can also retrieve all key-value pairs by passing a null prefix and a length of zero.

Parameters:: prefix – prefix to match.
Returns:: results object containing all matching key-value pairs.

search_results prefix_search(const key_unit_type *prefix, size_type len) const¶

Retrieve all key-value pairs whose keys start with specified prefix. You can also retrieve all key-value pairs by passing a null prefix and a length of zero.

Parameters:

prefix – pointer to an array whose value represents the prefix to match.
len – length of the prefix value to match.

Returns:

results object that contains all matching key-value pairs. The results are sorted by the key in ascending order.

size_type size() const noexcept¶

Return the number of entries in the map.

Returns:: the number of entries in the map.

bool empty() const noexcept¶

void swap(packed_trie_map &other)¶

const_node_type root_node() const¶

Obtain a root node of the trie to traverse it node-by-node.

Returns:: Root node of the trie.

template<typename FuncT = trie::value_serializer<value_type>> void save_state(std::ostream &os) const¶

Save the state of the instance of this class to an external buffer.

Parameters:: os – output stream to write the state to.

template<typename FuncT = trie::value_serializer<value_type>> void load_state(std::istream &is)¶

Restore the state of the instance of this class from an external buffer.

Parameters:: is – input stream to load the state from.

std::string dump_structure(trie::dump_structure_type type) const¶

Dump the structure of the trie content in a specified human-readable textural format.

Parameters:: type – Output format type.

Friends

friend class trie::detail::packed_iterator_base< packed_trie_map >

friend class trie::detail::packed_search_results< packed_trie_map >

friend struct trie::detail::dump_packed_buffer< packed_trie_map, packed_type >

class const_node_type¶

Represents an individual node of a trie.

Public Functions

const_node_type() = default¶

const_node_type(const const_node_type &other) = default¶

const_node_type &operator=(const const_node_type &other)¶

bool valid() const¶

Query whether or not the node references an existing node in a tree.

Returns:: True if the node references an existing node in a tree, or false if the node does not reference any node in any tree.

bool has_child() const¶

Query whether or not the node has at least one child node.

Returns:: True if the node has at least one child node, or false if the node has no child nodes at all.

bool has_value() const¶

Query whether or not the node has a value associated with it.

Returns:: True if the node has a value, otherwise false.

const value_type &value() const¶

Access the value associated with the node.

Warning

The caller must ensure that the node has a value via has_value() before calling this method to access it. Calling this method on a node without a value is undefined.

Returns:: Reference to the value associated with the node.

const_node_type child(key_unit_type c) const¶

Move to a child node by a unit key.

Parameters:: c – A unit key associated with a child node relative to the current node.
Returns:: A valid node if a child node exists for the unit key passed to this method, otherwise an invalid node is returned.

struct entry¶

Single key-value entry. Caller must provide at compile time a static array of these entries.

Public Functions

inline entry(const key_unit_type *_key, size_type _keylen, value_type _value)¶

Public Members

const key_unit_type *key¶

size_type keylen¶

value_type value¶

Value Serializers¶

mdds::trie::value_serializer¶

template<typename T, typename U = void> struct value_serializer : public mdds::trie::numeric_value_serializer<T>¶: Default value serializer for mdds::packed_trie_map’s load_state and save_state methods. The primary template is used for numeric value types, and template specializations exist for std::string, as well as sequence containers, such as std::vector, whose elements are of numeric types.

mdds::trie::numeric_value_serializer¶

template<typename T> struct numeric_value_serializer¶

Serializer for numeric data types.

Subclassed by mdds::trie::value_serializer< T, U >

Public Static Functions

static void write(std::ostream &os, const T &v)¶

static void read(std::istream &is, size_t n, T &v)¶

Public Static Attributes

static constexpr bool variable_size = false¶

static constexpr size_t value_size = sizeof(T)¶

mdds::trie::variable_value_serializer¶

template<typename T> struct variable_value_serializer¶

Serializer for variable-size data types.

Public Static Functions

static void write(std::ostream &os, const T &v)¶

static void read(std::istream &is, size_t n, T &v)¶

Public Static Attributes

static constexpr bool variable_size = true¶

mdds::trie::numeric_sequence_value_serializer¶

template<typename T> struct numeric_sequence_value_serializer¶

Serializer for standard sequence container whose value type is of numeric value type.

Subclassed by mdds::trie::value_serializer< T, typename std::enable_if< mdds::detail::has_value_type< T >::value >::type >

Public Types

using element_serializer = numeric_value_serializer<typename T::value_type>¶

Public Static Functions

static void write(std::ostream &os, const T &v)¶

static void read(std::istream &is, size_t n, T &v)¶

Public Static Attributes

static constexpr bool variable_size = true¶

Other Types¶

mdds::trie::default_traits¶

struct default_traits¶

Public Types

using pack_value_type = uintptr_t¶: Unit value type of a buffer used in packed_trie_map to store its content. It must be an unsigned integral type.

Note

Maximum number of key-value pairs that can be stored in the packed_trie_map variant is the maximum value that can be expressed by this type minus one. For instance, if the size of this type is 8-bits, only up to 255 key-value pairs can be stored.

mdds::trie::dump_structure_type¶

enum class mdds::trie::dump_structure_type¶

Specifies the type of human-readable output to dump.

Values:

enumerator packed_buffer¶: Dump the in-memory buffer that stores the trie content in a linear fashion.

enumerator trie_traversal¶: Dump the traversal result of the trie in depth-first order.