179 using traits_type = TraitsT;
181 typedef KeyT key_type;
182 typedef typename key_type::value_type key_unit_type;
183 typedef ValueT value_type;
184 typedef size_t size_type;
193 typedef std::map<key_unit_type, trie_node> children_type;
195 children_type children;
200 trie_node(
const trie_node& other);
201 trie_node(trie_node&& other);
203 void swap(trie_node& other);
206 template<
bool IsConst>
209 using _is_const = std::bool_constant<IsConst>;
211 using child_pos_type =
216 trie_node_type* node;
217 child_pos_type child_pos;
219 stack_item(trie_node_type* _node,
const child_pos_type& _child_pos) : node(_node), child_pos(_child_pos)
222 bool operator==(
const stack_item& r)
const
224 return node == r.node && child_pos == r.child_pos;
227 bool operator!=(
const stack_item& r)
const
229 return !operator==(r);
233 using const_node_stack_type = std::vector<stack_item<true>>;
234 using node_stack_type = std::vector<stack_item<false>>;
244 const trie_node* m_ref_node =
nullptr;
319 bool operator==(
const trie_map& other)
const;
320 bool operator!=(
const trie_map& other)
const;
337 void insert(
const key_type& key, value_type value);
347 void insert(
const key_unit_type* key, size_type len, value_type value);
358 bool erase(
const key_unit_type* key, size_type len);
437 bool empty() const noexcept;
465 void insert_into_tree(trie_node& node, const key_unit_type* key, const key_unit_type* key_end, value_type value);
467 const trie_node* find_prefix_node(
468 const trie_node& node, const key_unit_type* prefix, const key_unit_type* prefix_end) const;
470 template<
bool IsConst>
471 void find_prefix_node_with_stack(
472 std::vector<stack_item<IsConst>>& node_stack, mdds::detail::const_t<trie_node, IsConst>& node,
473 const key_unit_type* prefix, const key_unit_type* prefix_end) const;
475 template<
bool IsConst>
476 key_type build_key_buffer_from_node_stack(const std::vector<stack_item<IsConst>>& node_stack) const;
478 void count_values(size_type& n, const trie_node& node) const;
480 bool descend_for_equality(const trie_node& left, const trie_node& right) const;
499 using pack_value_type =
typename TraitsT::pack_value_type;
500 using packed_type = std::vector<pack_value_type>;
504 friend class trie_map<KeyT, ValueT, TraitsT>;
508 using traits_type = TraitsT;
509 typedef KeyT key_type;
510 typedef typename key_type::value_type key_unit_type;
511 typedef ValueT value_type;
512 typedef size_t size_type;
522 const key_unit_type* key;
526 entry(
const key_unit_type* _key, size_type _keylen, value_type _value)
527 : key(_key), keylen(_keylen), value(_value)
532 using value_store_type = std::deque<value_type>;
535 static constexpr auto null_value = std::numeric_limits<pack_value_type>::max();
537 static constexpr auto max_value_pos = null_value - 1u;
542 const value_type* value;
544 std::deque<trie_node*> children;
546 trie_node(key_unit_type _key) : key(_key), value(nullptr)
552 const value_store_type* value_store =
nullptr;
554 const pack_value_type* node_pos =
nullptr;
555 const pack_value_type* child_pos =
nullptr;
556 const pack_value_type* child_end =
nullptr;
559 const value_store_type* _value_store,
const pack_value_type* _node_pos,
const pack_value_type* _child_pos,
560 const pack_value_type* _child_end)
561 : value_store(_value_store), node_pos(_node_pos), child_pos(_child_pos), child_end(_child_end)
564 bool operator==(
const stack_item& other)
const
566 return value_store == other.value_store && node_pos == other.node_pos && child_pos == other.child_pos &&
567 child_end == other.child_end;
570 bool operator!=(
const stack_item& other)
const
572 return !operator==(other);
575 bool has_value()
const
577 return *node_pos != null_value;
580 pack_value_type get_value_pos()
const
586 typedef std::vector<stack_item> node_stack_type;
587 typedef std::deque<trie_node> node_pool_type;
588 typedef std::vector<std::tuple<size_t, key_unit_type>> child_offsets_type;
590 packed_trie_map(trie::detail::move_to_pack, trie_map<KeyT, ValueT, TraitsT>& from);
600 const packed_type* m_packed =
nullptr;
601 const value_store_type* m_value_store =
nullptr;
602 const pack_value_type* m_pos =
nullptr;
604 const_node_type(
const packed_type* packed,
const value_store_type* value_store,
const pack_value_type* p);
758 size_type
size() const noexcept;
760 bool empty() const noexcept;
776 template<typename FuncT = trie::value_serializer<value_type>>
777 void save_state(std::ostream& os) const;
785 template<typename FuncT = trie::value_serializer<value_type>>
786 void load_state(std::istream& is);
794 std::
string dump_structure(trie::dump_structure_type type) const;
797 void dump_trie_traversal(std::ostream& os) const;
799 node_stack_type get_root_stack() const;
802 trie_node& root, node_pool_type& node_pool, const
entry* start, const
entry* end, size_type pos);
804 size_type compact_node(const trie_node& node);
806 template<typename ModeT, typename NodeT>
807 size_type compact_node(ModeT, NodeT& node);
809 void check_value_size_or_throw() const;
811 size_type push_value_to_store(trie::detail::copy_to_pack, const value_type& value);
812 size_type push_value_to_store(trie::detail::move_to_pack, value_type& value);
814 void push_child_offsets(size_type offset, const child_offsets_type& child_offsets);
817 void compact(const trie_node& root);
819 template<typename ModeT, typename NodeT>
820 void compact(ModeT, NodeT& root);
822 template<typename _Handler>
823 void traverse_tree(_Handler hdl) const;
826 value_store_type m_value_store;
827 packed_type m_packed;
Definition trie_map.hpp:521