29 #ifndef INCLUDED_MDDS_TRIE_MAP_HPP 30 #define INCLUDED_MDDS_TRIE_MAP_HPP 32 #include "trie_map_itr.hpp" 76 static key_buffer_type
to_key_buffer(
const key_unit_type* str,
size_t length)
94 static const key_unit_type* buffer_data(
const key_buffer_type& buf)
99 static size_t buffer_size(
const key_buffer_type& buf)
111 static void push_back(key_buffer_type& buffer, key_unit_type c)
135 static key_type
to_key(
const key_buffer_type& buf)
143 template<
typename _KeyTrait,
typename _ValueT>
152 template<
typename _KeyTrait,
typename _ValueT>
161 typedef _KeyTrait key_trait_type;
162 typedef typename key_trait_type::key_type
key_type;
164 typedef typename key_trait_type::key_unit_type
key_unit_type;
165 typedef _ValueT value_type;
166 typedef size_t size_type;
167 typedef std::pair<key_type, value_type> key_value_type;
176 typedef std::map<key_unit_type, trie_node> children_type;
178 children_type children;
182 trie_node() : value(value_type()), has_value(
false) {}
187 typedef typename trie_node::children_type::const_iterator child_pos_type;
188 const trie_node* node;
189 child_pos_type child_pos;
191 stack_item(
const trie_node* _node,
const child_pos_type& _child_pos) :
192 node(_node), child_pos(_child_pos) {}
194 bool operator== (
const stack_item& r)
const 196 return node == r.node && child_pos == r.child_pos;
199 bool operator!= (
const stack_item& r)
const 201 return !operator== (r);
205 typedef std::vector<stack_item> node_stack_type;
214 const_iterator begin()
const;
216 const_iterator end()
const;
224 void insert(
const key_type& key,
const value_type& value);
234 void insert(
const key_unit_type* key, size_type len,
const value_type& value);
245 bool erase(
const key_unit_type* key, size_type len);
255 const_iterator find(
const key_type& key)
const;
267 const_iterator find(
const key_unit_type* input, size_type len)
const;
278 search_results prefix_search(
const key_type& prefix)
const;
292 search_results prefix_search(
const key_unit_type* prefix, size_type len)
const;
299 size_type size()
const;
313 packed_type pack()
const;
316 void insert_into_tree(
317 trie_node& node,
const key_unit_type* key,
const key_unit_type* key_end,
const value_type& value);
319 const trie_node* find_prefix_node(
320 const trie_node& node,
const key_unit_type* prefix,
const key_unit_type* prefix_end)
const;
322 void find_prefix_node_with_stack(
323 node_stack_type& node_stack,
324 const trie_node& node,
const key_unit_type* prefix,
const key_unit_type* prefix_end)
const;
326 void count_values(size_type& n,
const trie_node& node)
const;
342 template<
typename _KeyTrait,
typename _ValueT>
349 typedef _KeyTrait key_trait_type;
350 typedef typename key_trait_type::key_type
key_type;
352 typedef typename key_trait_type::key_unit_type
key_unit_type;
353 typedef _ValueT value_type;
354 typedef size_t size_type;
355 typedef std::pair<key_type, value_type> key_value_type;
365 const key_unit_type* key;
369 entry(
const key_unit_type* _key, size_type _keylen, value_type _value) :
370 key(_key), keylen(_keylen), value(_value) {}
377 const value_type* value;
379 std::deque<trie_node*> children;
381 trie_node(key_unit_type _key) : key(_key), value(
nullptr) {}
386 const uintptr_t* node_pos;
387 const uintptr_t* child_pos;
388 const uintptr_t* child_end;
390 stack_item(
const uintptr_t* _node_pos,
const uintptr_t* _child_pos,
const uintptr_t* _child_end) :
391 node_pos(_node_pos), child_pos(_child_pos), child_end(_child_end) {}
393 bool operator== (
const stack_item& other)
const 395 return node_pos == other.node_pos && child_pos == other.child_pos;
398 bool operator!= (
const stack_item& other)
const 400 return !operator==(other);
403 bool has_value()
const 405 const value_type* pv =
reinterpret_cast<const value_type*
>(*node_pos);
409 const value_type* get_value()
const 411 return reinterpret_cast<const value_type*
>(*node_pos);
415 typedef std::vector<stack_item> node_stack_type;
417 typedef std::deque<trie_node> node_pool_type;
418 typedef std::vector<uintptr_t> packed_type;
419 typedef std::deque<value_type> value_store_type;
420 typedef std::vector<std::tuple<size_t, key_unit_type>> child_offsets_type;
427 packed_trie_map() =
delete;
439 packed_trie_map(
const entry* entries, size_type entry_size);
449 const_iterator begin()
const;
451 const_iterator end()
const;
461 const_iterator find(
const key_type& key)
const;
473 const_iterator find(
const key_unit_type* input, size_type len)
const;
484 search_results prefix_search(
const key_type& prefix)
const;
498 search_results prefix_search(
const key_unit_type* prefix, size_type len)
const;
505 size_type size()
const;
508 node_stack_type get_root_stack()
const;
511 trie_node& root, node_pool_type& node_pool,
const entry* start,
const entry* end,
514 size_type compact_node(
const trie_node& node);
517 void push_child_offsets(size_type offset,
const child_offsets_type& child_offsets);
519 void compact(
const trie_node& root);
522 const uintptr_t* find_prefix_node(
523 const uintptr_t* p,
const key_unit_type* prefix,
const key_unit_type* prefix_end)
const;
525 void find_prefix_node_with_stack(
526 node_stack_type& node_stack,
527 const uintptr_t* p,
const key_unit_type* prefix,
const key_unit_type* prefix_end)
const;
529 #ifdef MDDS_TRIE_MAP_DEBUG 530 void dump_node(key_buffer_type& buffer,
const trie_node& node)
const;
531 void dump_trie(
const trie_node& root)
const;
532 void dump_packed_trie(
const std::vector<uintptr_t>& packed)
const;
536 size_type m_entry_size;
538 value_store_type m_value_store;
539 packed_type m_packed;
544 #include "trie_map_def.inl" Definition: trie_map_itr.hpp:387
std::string key_buffer_type
Definition: trie_map.hpp:58
static void pop_back(key_buffer_type &buffer)
Definition: trie_map.hpp:122
Definition: trie_map_itr.hpp:69
Definition: trie_map.hpp:363
Definition: trie_map.hpp:47
Definition: trie_map_itr.hpp:66
static key_type to_key(const key_buffer_type &buf)
Definition: trie_map.hpp:135
Definition: trie_map.hpp:144
char key_unit_type
Definition: trie_map.hpp:65
static key_buffer_type to_key_buffer(const key_type &key)
Definition: trie_map.hpp:89
Definition: trie_map.hpp:153
Definition: flat_segment_tree.hpp:46
static void push_back(key_buffer_type &buffer, key_unit_type c)
Definition: trie_map.hpp:111
static key_buffer_type to_key_buffer(const key_unit_type *str, size_t length)
Definition: trie_map.hpp:76
std::string key_type
Definition: trie_map.hpp:50
Definition: trie_map_itr.hpp:384