29 #ifndef INCLUDED_MDDS_TRIE_MAP_HPP
30 #define INCLUDED_MDDS_TRIE_MAP_HPP
32 #include "trie_map_itr.hpp"
47 template<
typename ContainerT>
142 using std_string_traits = std_container_traits<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);
191 template<
typename T,
typename U =
void>
197 struct value_serializer<T, typename std::enable_if<mdds::detail::has_value_type<T>::value>::type>
209 template<
typename KeyTraits,
typename ValueT>
218 template<
typename KeyTraits,
typename ValueT>
232 typedef KeyTraits key_traits_type;
233 typedef typename key_traits_type::key_type key_type;
234 typedef typename key_traits_type::key_buffer_type key_buffer_type;
235 typedef typename key_traits_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 = std::bool_constant<IsConst>;
265 using child_pos_type =
270 trie_node_type* node;
271 child_pos_type child_pos;
273 stack_item(trie_node_type* _node,
const child_pos_type& _child_pos) : node(_node), child_pos(_child_pos)
276 bool operator==(
const stack_item& r)
const
278 return node == r.node && child_pos == r.child_pos;
281 bool operator!=(
const stack_item& r)
const
283 return !operator==(r);
287 using const_node_stack_type = std::vector<stack_item<true>>;
288 using node_stack_type = std::vector<stack_item<false>>;
308 trie_map& operator=(trie_map other);
310 void swap(trie_map& other);
318 void insert(
const key_type& key,
const value_type& value);
328 void insert(
const key_unit_type* key, size_type len,
const value_type& value);
339 bool erase(
const key_unit_type* key, size_type len);
383 iterator find(
const key_unit_type* input, size_type len);
409 search_results
prefix_search(
const key_unit_type* prefix, size_type len)
const;
416 size_type
size()
const;
418 bool empty()
const noexcept;
432 packed_type
pack()
const;
435 void insert_into_tree(
436 trie_node& node,
const key_unit_type* key,
const key_unit_type* key_end,
const value_type& value);
438 const trie_node* find_prefix_node(
439 const trie_node& node,
const key_unit_type* prefix,
const key_unit_type* prefix_end)
const;
441 template<
bool IsConst>
442 void find_prefix_node_with_stack(
443 std::vector<stack_item<IsConst>>& node_stack, mdds::detail::const_t<trie_node, IsConst>& node,
444 const key_unit_type* prefix,
const key_unit_type* prefix_end)
const;
446 template<
bool IsConst>
447 key_buffer_type build_key_buffer_from_node_stack(
const std::vector<stack_item<IsConst>>& node_stack)
const;
449 void count_values(size_type& n,
const trie_node& node)
const;
465 template<
typename KeyTraits,
typename ValueT>
472 typedef KeyTraits key_traits_type;
473 typedef typename key_traits_type::key_type key_type;
474 typedef typename key_traits_type::key_buffer_type key_buffer_type;
475 typedef typename key_traits_type::key_unit_type key_unit_type;
476 typedef ValueT value_type;
477 typedef size_t size_type;
478 typedef std::pair<key_type, value_type> key_value_type;
488 const key_unit_type* key;
492 entry(
const key_unit_type* _key, size_type _keylen, value_type _value)
493 : key(_key), keylen(_keylen), value(_value)
501 const value_type* value;
503 std::deque<trie_node*> children;
505 trie_node(key_unit_type _key) : key(_key), value(nullptr)
511 const uintptr_t* node_pos;
512 const uintptr_t* child_pos;
513 const uintptr_t* child_end;
515 stack_item(
const uintptr_t* _node_pos,
const uintptr_t* _child_pos,
const uintptr_t* _child_end)
516 : node_pos(_node_pos), child_pos(_child_pos), child_end(_child_end)
519 bool operator==(
const stack_item& other)
const
521 return node_pos == other.node_pos && child_pos == other.child_pos;
524 bool operator!=(
const stack_item& other)
const
526 return !operator==(other);
529 bool has_value()
const
531 const value_type* pv =
reinterpret_cast<const value_type*
>(*node_pos);
535 const value_type* get_value()
const
537 return reinterpret_cast<const value_type*
>(*node_pos);
541 typedef std::vector<stack_item> node_stack_type;
543 typedef std::deque<trie_node> node_pool_type;
544 typedef std::vector<uintptr_t> packed_type;
545 typedef std::deque<value_type> value_store_type;
546 typedef std::vector<std::tuple<size_t, key_unit_type>> child_offsets_type;
559 packed_trie_map(
const entry* entries, size_type entry_size);
567 packed_trie_map(
const trie_map<key_traits_type, value_type>& other);
569 packed_trie_map(
const packed_trie_map& other);
571 packed_trie_map(packed_trie_map&& other);
573 packed_trie_map& operator=(packed_trie_map other);
575 bool operator==(
const packed_trie_map& other)
const;
577 bool operator!=(
const packed_trie_map& other)
const;
579 const_iterator begin()
const;
581 const_iterator end()
const;
583 const_iterator cbegin()
const;
585 const_iterator cend()
const;
595 const_iterator
find(
const key_type& key)
const;
607 const_iterator
find(
const key_unit_type* input, size_type len)
const;
632 search_results
prefix_search(
const key_unit_type* prefix, size_type len)
const;
639 size_type
size() const noexcept;
641 bool empty() const noexcept;
643 void swap(packed_trie_map& other);
650 template<typename FuncT = trie::value_serializer<value_type>>
659 template<typename FuncT = trie::value_serializer<value_type>>
670 node_stack_type get_root_stack() const;
673 trie_node& root, node_pool_type& node_pool, const entry* start, const entry* end, size_type pos);
675 size_type compact_node(const trie_node& node);
676 size_type compact_node(const typename trie_map<KeyTraits, ValueT>::trie_node& node);
678 void push_child_offsets(size_type offset, const child_offsets_type& child_offsets);
680 void compact(const trie_node& root);
681 void compact(const typename trie_map<KeyTraits, ValueT>::trie_node& root);
683 const uintptr_t* find_prefix_node(
684 const uintptr_t* p, const key_unit_type* prefix, const key_unit_type* prefix_end) const;
686 void find_prefix_node_with_stack(
687 node_stack_type& node_stack, const uintptr_t* p, const key_unit_type* prefix,
688 const key_unit_type* prefix_end) const;
690 template<typename _Handler>
691 void traverse_tree(_Handler hdl) const;
693 template<typename _Handler>
694 void traverse_buffer(_Handler hdl) const;
696 #ifdef MDDS_TRIE_MAP_DEBUG
697 void dump_node(key_buffer_type& buffer,
const trie_node& node)
const;
698 void dump_trie(
const trie_node& root)
const;
699 void dump_packed_trie()
const;
703 value_store_type m_value_store;
704 packed_type m_packed;
709 #include "trie_map_def.inl"
size_type size() const noexcept
Definition: trie_map_itr.hpp:500
key_type key_buffer_type
Definition: trie_map.hpp:59
search_results prefix_search(const key_type &prefix) const
void load_state(std::istream &is)
Definition: trie_map_itr.hpp:349
void save_state(std::ostream &os) const
Definition: trie_map.hpp:192
const_iterator find(const key_type &key) const
void dump_structure() const
Definition: trie_map_itr.hpp:88
Definition: trie_map_itr.hpp:346
Definition: trie_map.hpp:48
Definition: trie_map.hpp:486
Definition: trie_map_itr.hpp:85
Definition: trie_map.hpp:210
Definition: global.hpp:182
Definition: trie_map.hpp:159
void insert(const key_type &key, const value_type &value)
ContainerT key_type
Definition: trie_map.hpp:51
Definition: global.hpp:146
const_iterator find(const key_type &key) const
static key_buffer_type to_key_buffer(const key_type &key)
Definition: trie_map.hpp:90
static void push_back(key_buffer_type &buffer, key_unit_type c)
Definition: trie_map.hpp:112
Definition: trie_map.hpp:173
static key_type to_key(const key_buffer_type &buf)
Definition: trie_map.hpp:136
Definition: trie_map.hpp:219
search_results prefix_search(const key_type &prefix) const
Definition: flat_segment_tree.hpp:46
Definition: trie_map_itr.hpp:70
static void pop_back(key_buffer_type &buffer)
Definition: trie_map.hpp:123
Definition: trie_map.hpp:146
static key_buffer_type to_key_buffer(const key_unit_type *str, size_t length)
Definition: trie_map.hpp:77
typename key_type::value_type key_unit_type
Definition: trie_map.hpp:66
bool erase(const key_unit_type *key, size_type len)
Definition: trie_map_itr.hpp:497