29 #ifndef INCLUDED_MDDS_TRIE_MAP_HPP 30 #define INCLUDED_MDDS_TRIE_MAP_HPP 72 static buffer_type
init_buffer(
const char_type* str,
size_t length)
84 static void push_back(buffer_type& buffer, char_type c)
116 template<
typename _KeyTrait,
typename _ValueT>
125 template<
typename _KeyTrait,
typename _ValueT>
132 typedef _KeyTrait key_trait_type;
133 typedef typename key_trait_type::string_type
string_type;
134 typedef typename key_trait_type::buffer_type
buffer_type;
135 typedef typename key_trait_type::char_type
char_type;
136 typedef _ValueT value_type;
137 typedef size_t size_type;
138 typedef std::pair<string_type, value_type> key_value_type;
144 typedef std::map<char_type, trie_node> children_type;
146 children_type children;
150 trie_node() : has_value(
false) {}
176 void insert(
const char_type* key, size_type len,
const value_type& value);
187 bool erase(
const char_type* key, size_type len);
199 value_type find(
const char_type* input, size_type len)
const;
213 std::vector<key_value_type> prefix_search(
const char_type* prefix, size_type len)
const;
220 size_type size()
const;
234 packed_type pack()
const;
237 void insert_into_tree(
238 trie_node& node,
const char_type* key,
const char_type* key_end,
const value_type& value);
240 const trie_node* find_prefix_node(
241 const trie_node& node,
const char_type* prefix,
const char_type* prefix_end)
const;
243 void fill_child_node_items(
244 std::vector<key_value_type>& items, buffer_type& buffer,
const trie_node& node)
const;
246 void count_values(size_type& n,
const trie_node& node)
const;
249 value_type m_null_value;
263 template<
typename _KeyTrait,
typename _ValueT>
267 typedef _KeyTrait key_trait_type;
268 typedef typename key_trait_type::string_type
string_type;
269 typedef typename key_trait_type::buffer_type
buffer_type;
270 typedef typename key_trait_type::char_type
char_type;
271 typedef _ValueT value_type;
272 typedef size_t size_type;
273 typedef std::pair<string_type, value_type> key_value_type;
281 const char_type* key;
285 entry(
const char_type* _key, size_type _keylen, value_type _value) :
286 key(_key), keylen(_keylen), value(_value) {}
293 const value_type* value;
295 std::deque<trie_node*> children;
297 trie_node(char_type _key) : key(_key), value(
nullptr) {}
300 typedef std::deque<trie_node> node_pool_type;
301 typedef std::vector<uintptr_t> packed_type;
302 typedef std::deque<value_type> value_store_type;
303 typedef std::vector<std::tuple<size_t, char_type>> child_offsets_type;
342 value_type find(
const char_type* input, size_type len)
const;
356 std::vector<key_value_type> prefix_search(
const char_type* prefix, size_type len)
const;
363 size_type size()
const;
367 trie_node& root, node_pool_type& node_pool,
const entry* start,
const entry* end,
370 size_type compact_node(
const trie_node& node);
373 void push_child_offsets(size_type offset,
const child_offsets_type& child_offsets);
375 void compact(
const trie_node& root);
378 const uintptr_t* find_prefix_node(
379 const uintptr_t* p,
const char_type* prefix,
const char_type* prefix_end)
const;
381 void fill_child_node_items(
382 std::vector<key_value_type>& items, buffer_type& buffer,
const uintptr_t* p)
const;
384 #ifdef MDDS_TRIE_MAP_DEBUG 385 void dump_node(buffer_type& buffer,
const trie_node& node)
const;
386 void dump_trie(
const trie_node& root)
const;
387 void dump_packed_trie(
const std::vector<uintptr_t>& packed)
const;
391 value_type m_null_value;
392 size_type m_entry_size;
394 value_store_type m_value_store;
395 packed_type m_packed;
400 #include "trie_map_def.inl" char char_type
Definition: trie_map.hpp:61
static buffer_type init_buffer(const char_type *str, size_t length)
Definition: trie_map.hpp:72
static void pop_back(buffer_type &buffer)
Definition: trie_map.hpp:95
Definition: trie_map.hpp:279
Definition: trie_map.hpp:45
Definition: trie_map.hpp:117
std::string string_type
Definition: trie_map.hpp:48
static string_type to_string(const buffer_type &buf)
Definition: trie_map.hpp:108
std::string buffer_type
Definition: trie_map.hpp:54
static void push_back(buffer_type &buffer, char_type c)
Definition: trie_map.hpp:84
Definition: trie_map.hpp:126
Definition: default_deleter.hpp:33