29#ifndef INCLUDED_MDDS_TRIE_MAP_HPP
30#define INCLUDED_MDDS_TRIE_MAP_HPP
32#include "trie_map_itr.hpp"
47template<
typename ContainerT>
142using std_string_trait = std_container_trait<std::string>;
148 static constexpr bool variable_size =
false;
150 static constexpr size_t value_size =
sizeof(T);
152 static void write(std::ostream& os,
const T& v);
154 static void read(std::istream& is,
size_t n, T& v);
161 static constexpr bool variable_size =
true;
163 static void write(std::ostream& os,
const T& v);
165 static void read(std::istream& is,
size_t n, T& v);
177 static constexpr bool variable_size =
true;
179 static void write(std::ostream& os,
const T& v);
181 static void read(std::istream& is,
size_t n, T& v);
191template<
typename T,
typename U =
void>
209template<
typename _KeyTrait,
typename _ValueT>
218template<
typename _KeyTrait,
typename _ValueT>
232 typedef _KeyTrait key_trait_type;
233 typedef typename key_trait_type::key_type key_type;
234 typedef typename key_trait_type::key_buffer_type key_buffer_type;
235 typedef typename key_trait_type::key_unit_type key_unit_type;
236 typedef _ValueT value_type;
237 typedef size_t size_type;
238 typedef std::pair<key_type, value_type> key_value_type;
247 typedef std::map<key_unit_type, trie_node> children_type;
249 children_type children;
254 trie_node(
const trie_node& other);
255 trie_node(trie_node&& other);
257 void swap(trie_node& other);
260 template<
bool _IsConst>
263 using _is_const = bool_constant<_IsConst>;
269 trie_node_type* node;
270 child_pos_type child_pos;
272 stack_item(trie_node_type* _node,
const child_pos_type& _child_pos) : node(_node), child_pos(_child_pos)
275 bool operator==(
const stack_item& r)
const
277 return node == r.node && child_pos == r.child_pos;
280 bool operator!=(
const stack_item& r)
const
282 return !operator==(r);
286 using const_node_stack_type = std::vector<stack_item<true>>;
287 using node_stack_type = std::vector<stack_item<false>>;
317 void insert(
const key_type& key,
const value_type& value);
327 void insert(
const key_unit_type* key, size_type len,
const value_type& value);
338 bool erase(
const key_unit_type* key, size_type len);
417 bool empty() const noexcept;
434 void insert_into_tree(
435 trie_node& node, const key_unit_type* key, const key_unit_type* key_end, const value_type& value);
437 const trie_node* find_prefix_node(
438 const trie_node& node, const key_unit_type* prefix, const key_unit_type* prefix_end) const;
440 template<
bool _IsConst>
441 void find_prefix_node_with_stack(
442 std::vector<stack_item<_IsConst>>& node_stack, const_t<trie_node, _IsConst>& node, const key_unit_type* prefix,
443 const key_unit_type* prefix_end) const;
445 template<
bool _IsConst>
446 key_buffer_type build_key_buffer_from_node_stack(const std::vector<stack_item<_IsConst>>& node_stack) const;
448 void count_values(size_type& n, const trie_node& node) const;
464template<typename _KeyTrait, typename _ValueT>
471 typedef _KeyTrait key_trait_type;
472 typedef typename key_trait_type::key_type key_type;
473 typedef typename key_trait_type::key_buffer_type key_buffer_type;
474 typedef typename key_trait_type::key_unit_type key_unit_type;
475 typedef _ValueT value_type;
476 typedef size_t size_type;
477 typedef std::pair<key_type, value_type> key_value_type;
487 const key_unit_type* key;
491 entry(
const key_unit_type* _key, size_type _keylen, value_type _value)
492 : key(_key), keylen(_keylen), value(_value)
500 const value_type* value;
502 std::deque<trie_node*> children;
504 trie_node(key_unit_type _key) : key(_key), value(nullptr)
510 const uintptr_t* node_pos;
511 const uintptr_t* child_pos;
512 const uintptr_t* child_end;
514 stack_item(
const uintptr_t* _node_pos,
const uintptr_t* _child_pos,
const uintptr_t* _child_end)
515 : node_pos(_node_pos), child_pos(_child_pos), child_end(_child_end)
518 bool operator==(
const stack_item& other)
const
520 return node_pos == other.node_pos && child_pos == other.child_pos;
523 bool operator!=(
const stack_item& other)
const
525 return !operator==(other);
528 bool has_value()
const
530 const value_type* pv =
reinterpret_cast<const value_type*
>(*node_pos);
534 const value_type* get_value()
const
536 return reinterpret_cast<const value_type*
>(*node_pos);
540 typedef std::vector<stack_item> node_stack_type;
542 typedef std::deque<trie_node> node_pool_type;
543 typedef std::vector<uintptr_t> packed_type;
544 typedef std::deque<value_type> value_store_type;
545 typedef std::vector<std::tuple<size_t, key_unit_type>> child_offsets_type;
638 size_type
size() const noexcept;
640 bool empty() const noexcept;
649 template<typename _Func = trie::value_serializer<value_type>>
650 void save_state(std::ostream& os) const;
658 template<typename _Func = trie::value_serializer<value_type>>
659 void load_state(std::istream& is);
666 void dump_structure() const;
669 node_stack_type get_root_stack() const;
672 trie_node& root, node_pool_type& node_pool, const
entry* start, const
entry* end, size_type pos);
674 size_type compact_node(const trie_node& node);
675 size_type compact_node(const typename
trie_map<_KeyTrait, _ValueT>::trie_node& node);
677 void push_child_offsets(size_type offset, const child_offsets_type& child_offsets);
679 void compact(const trie_node& root);
680 void compact(const typename
trie_map<_KeyTrait, _ValueT>::trie_node& root);
682 const uintptr_t* find_prefix_node(
683 const uintptr_t* p, const key_unit_type* prefix, const key_unit_type* prefix_end) const;
685 void find_prefix_node_with_stack(
686 node_stack_type& node_stack, const uintptr_t* p, const key_unit_type* prefix,
687 const key_unit_type* prefix_end) const;
689 template<typename _Handler>
690 void traverse_tree(_Handler hdl) const;
692 template<typename _Handler>
693 void traverse_buffer(_Handler hdl) const;
695#ifdef MDDS_TRIE_MAP_DEBUG
696 void dump_node(key_buffer_type& buffer,
const trie_node& node)
const;
697 void dump_trie(
const trie_node& root)
const;
698 void dump_packed_trie()
const;
702 value_store_type m_value_store;
703 packed_type m_packed;
708#include "trie_map_def.inl"
Definition trie_map.hpp:466
const_iterator find(const key_unit_type *input, size_type len) const
search_results prefix_search(const key_unit_type *prefix, size_type len) const
size_type size() const noexcept
const_iterator find(const key_type &key) const
packed_trie_map(const trie_map< key_trait_type, value_type > &other)
packed_trie_map(const entry *entries, size_type entry_size)
search_results prefix_search(const key_type &prefix) const
Definition trie_map_itr.hpp:375
Definition trie_map_itr.hpp:89
Definition trie_map_itr.hpp:350
Definition trie_map_itr.hpp:501
Definition trie_map_itr.hpp:795
Definition trie_map_itr.hpp:440
Definition trie_map.hpp:220
void insert(const key_type &key, const value_type &value)
search_results prefix_search(const key_unit_type *prefix, size_type len) const
search_results prefix_search(const key_type &prefix) const
iterator find(const key_unit_type *input, size_type len)
const_iterator find(const key_unit_type *input, size_type len) const
bool erase(const key_unit_type *key, size_type len)
void insert(const key_unit_type *key, size_type len, const value_type &value)
iterator find(const key_type &key)
const_iterator find(const key_type &key) const
Definition global.hpp:147
Definition global.hpp:165
Definition trie_map.hpp:486
Definition trie_map_itr.hpp:70
Definition trie_map.hpp:174
Definition trie_map.hpp:147
Definition trie_map.hpp:49
key_type key_buffer_type
Definition trie_map.hpp:59
static void push_back(key_buffer_type &buffer, key_unit_type c)
Definition trie_map.hpp:112
static key_buffer_type to_key_buffer(const key_unit_type *str, size_t length)
Definition trie_map.hpp:77
static key_type to_key(const key_buffer_type &buf)
Definition trie_map.hpp:136
static key_buffer_type to_key_buffer(const key_type &key)
Definition trie_map.hpp:90
ContainerT key_type
Definition trie_map.hpp:51
typename key_type::value_type key_unit_type
Definition trie_map.hpp:66
static void pop_back(key_buffer_type &buffer)
Definition trie_map.hpp:123
Definition trie_map.hpp:193
Definition trie_map.hpp:160