29 #ifndef INCLUDED_MDDS_TRIE_MAP_HPP 30 #define INCLUDED_MDDS_TRIE_MAP_HPP 32 #include "trie_map_itr.hpp" 47 template<
typename ContainerT>
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>
202 template<
typename _KeyTrait,
typename _ValueT>
211 template<
typename _KeyTrait,
typename _ValueT>
225 typedef _KeyTrait key_trait_type;
226 typedef typename key_trait_type::key_type
key_type;
228 typedef typename key_trait_type::key_unit_type
key_unit_type;
229 typedef _ValueT value_type;
230 typedef size_t size_type;
231 typedef std::pair<key_type, value_type> key_value_type;
241 typedef std::map<key_unit_type, trie_node> children_type;
243 children_type children;
248 trie_node(
const trie_node& other);
249 trie_node(trie_node&& other);
251 void swap(trie_node& other);
254 template<
bool _IsConst>
257 using _is_const = bool_constant<_IsConst>;
259 using child_pos_type =
261 typename trie_node::children_type, _is_const>::type;
265 trie_node_type* node;
266 child_pos_type child_pos;
268 stack_item(trie_node_type* _node,
const child_pos_type& _child_pos) :
269 node(_node), child_pos(_child_pos) {}
271 bool operator== (
const stack_item& r)
const 273 return node == r.node && child_pos == r.child_pos;
276 bool operator!= (
const stack_item& r)
const 278 return !operator== (r);
282 using const_node_stack_type = std::vector<stack_item<true>>;
283 using node_stack_type = std::vector<stack_item<false>>;
292 trie_map(
const trie_map& other);
294 trie_map(trie_map&& other);
304 trie_map& operator= (trie_map other);
306 void swap(trie_map& other);
314 void insert(
const key_type& key,
const value_type& value);
324 void insert(
const key_unit_type* key, size_type len,
const value_type& value);
335 bool erase(
const key_unit_type* key, size_type len);
357 const_iterator find(
const key_unit_type* input, size_type len)
const;
379 iterator find(
const key_unit_type* input, size_type len);
391 search_results prefix_search(
const key_type& prefix)
const;
405 search_results prefix_search(
const key_unit_type* prefix, size_type len)
const;
412 size_type size()
const;
414 bool empty()
const noexcept;
428 packed_type pack()
const;
431 void insert_into_tree(
432 trie_node& node,
const key_unit_type* key,
const key_unit_type* key_end,
const value_type& value);
434 const trie_node* find_prefix_node(
435 const trie_node& node,
const key_unit_type* prefix,
const key_unit_type* prefix_end)
const;
437 template<
bool _IsConst>
438 void find_prefix_node_with_stack(
439 std::vector<stack_item<_IsConst>>& node_stack,
440 const_t<trie_node, _IsConst>& node,
441 const key_unit_type* prefix,
442 const key_unit_type* prefix_end)
const;
444 template<
bool _IsConst>
445 key_buffer_type build_key_buffer_from_node_stack(
446 const std::vector<stack_item<_IsConst>>& node_stack)
const;
448 void count_values(size_type& n,
const trie_node& node)
const;
464 template<
typename _KeyTrait,
typename _ValueT>
471 typedef _KeyTrait key_trait_type;
472 typedef typename key_trait_type::key_type
key_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) {}
499 const value_type* value;
501 std::deque<trie_node*> children;
503 trie_node(key_unit_type _key) : key(_key), value(
nullptr) {}
508 const uintptr_t* node_pos;
509 const uintptr_t* child_pos;
510 const uintptr_t* child_end;
512 stack_item(
const uintptr_t* _node_pos,
const uintptr_t* _child_pos,
const uintptr_t* _child_end) :
513 node_pos(_node_pos), child_pos(_child_pos), child_end(_child_end) {}
515 bool operator== (
const stack_item& other)
const 517 return node_pos == other.node_pos && child_pos == other.child_pos;
520 bool operator!= (
const stack_item& other)
const 522 return !operator==(other);
525 bool has_value()
const 527 const value_type* pv =
reinterpret_cast<const value_type*
>(*node_pos);
531 const value_type* get_value()
const 533 return reinterpret_cast<const value_type*
>(*node_pos);
537 typedef std::vector<stack_item> node_stack_type;
539 typedef std::deque<trie_node> node_pool_type;
540 typedef std::vector<uintptr_t> packed_type;
541 typedef std::deque<value_type> value_store_type;
542 typedef std::vector<std::tuple<size_t, key_unit_type>> child_offsets_type;
558 packed_trie_map(
const entry* entries, size_type entry_size);
568 packed_trie_map(
const packed_trie_map& other);
570 packed_trie_map(packed_trie_map&& other);
572 packed_trie_map& operator= (packed_trie_map other);
574 bool operator== (
const packed_trie_map& other)
const;
576 bool operator!= (
const packed_trie_map& other)
const;
578 const_iterator begin()
const;
580 const_iterator end()
const;
582 const_iterator cbegin()
const;
584 const_iterator cend()
const;
594 const_iterator find(
const key_type& key)
const;
606 const_iterator find(
const key_unit_type* input, size_type len)
const;
617 search_results prefix_search(
const key_type& prefix)
const;
631 search_results prefix_search(
const key_unit_type* prefix, size_type len)
const;
638 size_type size()
const noexcept;
640 bool empty()
const noexcept;
642 void swap(packed_trie_map& other);
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,
675 size_type compact_node(
const trie_node& node);
678 void push_child_offsets(size_type offset,
const child_offsets_type& child_offsets);
680 void compact(
const 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,
688 const uintptr_t* p,
const key_unit_type* prefix,
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" Definition: trie_map_itr.hpp:503
static key_buffer_type to_key_buffer(const key_unit_type *str, size_t length)
Definition: trie_map.hpp:77
Definition: trie_map_itr.hpp:354
typename key_type::value_type key_unit_type
Definition: trie_map.hpp:66
Definition: trie_map.hpp:192
key_type key_buffer_type
Definition: trie_map.hpp:59
ContainerT key_type
Definition: trie_map.hpp:51
Definition: trie_map_itr.hpp:85
Definition: trie_map_itr.hpp:351
static key_buffer_type to_key_buffer(const key_type &key)
Definition: trie_map.hpp:90
Definition: trie_map.hpp:485
Definition: trie_map_itr.hpp:82
Definition: trie_map.hpp:203
Definition: trie_map.hpp:159
Definition: global.hpp:136
static void push_back(key_buffer_type &buffer, key_unit_type c)
Definition: trie_map.hpp:112
static void pop_back(key_buffer_type &buffer)
Definition: trie_map.hpp:123
Definition: trie_map.hpp:173
Definition: trie_map.hpp:212
Definition: global.hpp:154
Definition: flat_segment_tree.hpp:46
Definition: trie_map.hpp:48
static key_type to_key(const key_buffer_type &buf)
Definition: trie_map.hpp:136
Definition: trie_map_itr.hpp:67
Definition: trie_map.hpp:146
Definition: trie_map_itr.hpp:500