182 using traits_type = TraitsT;
184 using key_type = KeyT;
185 using key_unit_type =
typename key_type::value_type;
186 using key_view_type = trie::detail::key_view_t<key_unit_type>;
187 using value_type = ValueT;
188 using size_type = std::size_t;
197 typedef std::map<key_unit_type, trie_node> children_type;
199 children_type children;
204 trie_node(
const trie_node& other);
205 trie_node(trie_node&& other);
207 void swap(trie_node& other);
210 template<
bool IsConst>
213 using is_const_type = std::bool_constant<IsConst>;
215 using child_pos_type =
220 trie_node_type* node;
221 child_pos_type child_pos;
223 stack_item(trie_node_type* _node,
const child_pos_type& _child_pos) : node(_node), child_pos(_child_pos)
226 bool operator==(
const stack_item& r)
const
228 return node == r.node && child_pos == r.child_pos;
232 using const_node_stack_type = std::vector<stack_item<true>>;
233 using node_stack_type = std::vector<stack_item<false>>;
239 class const_node_type
241 friend class trie_map;
243 const trie_node* m_ref_node =
nullptr;
245 const_node_type(
const trie_node* ref_node);
249 const_node_type(
const const_node_type& other);
251 const_node_type& operator=(
const const_node_type& other);
296 const_node_type
child(key_unit_type c)
const;
308 const_iterator begin()
const;
312 const_iterator end()
const;
318 bool operator==(
const trie_map& other)
const;
335 void insert(key_view_type key, value_type value);
345 [[deprecated(
"use the overload taking key_view_type instead")]]
void insert(
346 const key_unit_type* key, size_type len, value_type value);
366 [[deprecated(
"use the overload taking key_view_type instead")]]
bool erase(
const key_unit_type* key, size_type len);
376 const_iterator
find(key_view_type key)
const;
388 [[deprecated(
"use the overload taking key_view_type instead")]] const_iterator
find(
389 const key_unit_type* input, size_type len)
const;
399 iterator
find(key_view_type key);
411 [[deprecated(
"use the overload taking key_view_type instead")]] iterator
find(
412 const key_unit_type* input, size_type len);
437 [[deprecated(
"use the overload taking key_view_type instead")]] search_results
prefix_search(
438 const key_unit_type* prefix, size_type len)
const;
447 bool empty() const noexcept;
475 void insert_into_tree(trie_node& node, const key_unit_type* key, const key_unit_type* key_end, value_type value);
477 const trie_node* find_prefix_node(
478 const trie_node& node, const key_unit_type* prefix, const key_unit_type* prefix_end) const;
480 template<
bool IsConst>
481 void find_prefix_node_with_stack(
482 std::vector<stack_item<IsConst>>& node_stack, mdds::detail::const_t<trie_node, IsConst>& node,
483 const key_unit_type* prefix, const key_unit_type* prefix_end) const;
485 template<
bool IsConst>
486 key_type build_key_buffer_from_node_stack(const std::vector<stack_item<IsConst>>& node_stack) const;
488 void count_values(size_type& n, const trie_node& node) const;
490 bool descend_for_equality(const trie_node& left, const trie_node& right) const;
509 using pack_value_type =
typename TraitsT::pack_value_type;
510 using packed_type = std::vector<pack_value_type>;
514 friend class trie_map<KeyT, ValueT, TraitsT>;
518 using traits_type = TraitsT;
519 using key_type = KeyT;
520 using key_unit_type =
typename key_type::value_type;
521 using key_view_type = trie::detail::key_view_t<key_unit_type>;
522 using value_type = ValueT;
523 using size_type = std::size_t;
533 const key_unit_type* key;
537 entry(
const key_unit_type* _key, size_type _keylen, value_type _value)
538 : key(_key), keylen(_keylen), value(std::move(_value))
543 using value_store_type = std::deque<value_type>;
546 static constexpr auto null_value = std::numeric_limits<pack_value_type>::max();
548 static constexpr auto max_value_pos = null_value - 1u;
553 const value_type* value;
555 std::deque<trie_node*> children;
557 trie_node(key_unit_type _key) : key(_key), value(nullptr)
563 const value_store_type* value_store =
nullptr;
565 const pack_value_type* node_pos =
nullptr;
566 const pack_value_type* child_pos =
nullptr;
567 const pack_value_type* child_end =
nullptr;
570 const value_store_type* _value_store,
const pack_value_type* _node_pos,
const pack_value_type* _child_pos,
571 const pack_value_type* _child_end)
572 : value_store(_value_store), node_pos(_node_pos), child_pos(_child_pos), child_end(_child_end)
575 bool operator==(
const stack_item& other)
const
577 return value_store == other.value_store && node_pos == other.node_pos && child_pos == other.child_pos &&
578 child_end == other.child_end;
581 bool has_value()
const
583 return *node_pos != null_value;
586 pack_value_type get_value_pos()
const
592 typedef std::vector<stack_item> node_stack_type;
593 typedef std::deque<trie_node> node_pool_type;
594 typedef std::vector<std::tuple<size_t, key_unit_type>> child_offsets_type;
602 class const_node_type
604 friend class packed_trie_map;
606 const packed_type* m_packed =
nullptr;
607 const value_store_type* m_value_store =
nullptr;
608 const pack_value_type* m_pos =
nullptr;
610 const_node_type(
const packed_type* packed,
const value_store_type* value_store,
const pack_value_type* p);
613 const_node_type() =
default;
614 const_node_type(
const const_node_type& other) =
default;
616 const_node_type& operator=(
const const_node_type& other);
661 const_node_type
child(key_unit_type c)
const;
693 [[deprecated(
"use the constructor taking std::span<const entry> instead")]]
packed_trie_map(
694 const entry* entries, size_type entry_size);
709 packed_trie_map(
const packed_trie_map& other);
711 packed_trie_map(packed_trie_map&& other);
713 packed_trie_map& operator=(packed_trie_map other);
715 bool operator==(
const packed_trie_map& other)
const;
717 const_iterator begin()
const;
719 const_iterator end()
const;
721 const_iterator cbegin()
const;
723 const_iterator cend()
const;
733 const_iterator
find(key_view_type key)
const;
745 [[deprecated(
"use the overload taking key_view_type instead")]] const_iterator
find(
746 const key_unit_type* input, size_type len)
const;
770 [[deprecated(
"use the overload taking key_view_type instead")]] search_results
prefix_search(
771 const key_unit_type* prefix, size_type len)
const;
778 size_type
size() const noexcept;
780 bool empty() const noexcept;
782 void swap(packed_trie_map& other);
796 template<typename FuncT = trie::value_serializer<value_type>>
805 template<typename FuncT = trie::value_serializer<value_type>>
817 void dump_trie_traversal(std::ostream& os) const;
819 node_stack_type get_root_stack() const;
822 trie_node& root, node_pool_type& node_pool, const entry* start, const entry* end, size_type pos);
824 size_type compact_node(const trie_node& node);
826 template<typename ModeT, typename NodeT>
827 size_type compact_node(ModeT, NodeT& node);
829 void check_value_size_or_throw() const;
831 size_type push_value_to_store(trie::detail::copy_to_pack, const value_type& value);
832 size_type push_value_to_store(trie::detail::move_to_pack, value_type& value);
834 void push_child_offsets(size_type offset, const child_offsets_type& child_offsets);
837 void compact(const trie_node& root);
839 template<typename ModeT, typename NodeT>
840 void compact(ModeT, NodeT& root);
842 template<typename _Handler>
843 void traverse_tree(_Handler hdl) const;
846 value_store_type m_value_store;
847 packed_type m_packed;