mdds
trie_map.hpp
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*************************************************************************
3  *
4  * Copyright (c) 2015 Kohei Yoshida
5  *
6  * Permission is hereby granted, free of charge, to any person
7  * obtaining a copy of this software and associated documentation
8  * files (the "Software"), to deal in the Software without
9  * restriction, including without limitation the rights to use,
10  * copy, modify, merge, publish, distribute, sublicense, and/or sell
11  * copies of the Software, and to permit persons to whom the
12  * Software is furnished to do so, subject to the following
13  * conditions:
14  *
15  * The above copyright notice and this permission notice shall be
16  * included in all copies or substantial portions of the Software.
17  *
18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
20  * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
22  * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
23  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
25  * OTHER DEALINGS IN THE SOFTWARE.
26  *
27  ************************************************************************/
28 
29 #ifndef INCLUDED_MDDS_TRIE_MAP_HPP
30 #define INCLUDED_MDDS_TRIE_MAP_HPP
31 
32 #include <vector>
33 #include <string>
34 #include <deque>
35 #include <map>
36 
37 namespace mdds {
38 
39 namespace trie {
40 
46 {
48  typedef std::string string_type;
49 
54  typedef std::string buffer_type;
55 
61  typedef char char_type;
62 
72  static buffer_type init_buffer(const char_type* str, size_t length)
73  {
74  return buffer_type(str, length);
75  }
76 
84  static void push_back(buffer_type& buffer, char_type c)
85  {
86  buffer.push_back(c);
87  }
88 
95  static void pop_back(buffer_type& buffer)
96  {
97  buffer.pop_back();
98  }
99 
108  static string_type to_string(const buffer_type& buf)
109  {
110  return buf;
111  }
112 };
113 
114 }
115 
116 template<typename _KeyTrait, typename _ValueT>
118 
125 template<typename _KeyTrait, typename _ValueT>
126 class trie_map
127 {
128  friend class packed_trie_map<_KeyTrait, _ValueT>;
129 
130 public:
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;
139 
140 private:
141 
142  struct trie_node
143  {
144  typedef std::map<char_type, trie_node> children_type;
145 
146  children_type children;
147  value_type value;
148  bool has_value;
149 
150  trie_node() : has_value(false) {}
151  };
152 
153 public:
154 
158  trie_map() = delete;
159 
166  trie_map(value_type null_value);
167 
176  void insert(const char_type* key, size_type len, const value_type& value);
177 
187  bool erase(const char_type* key, size_type len);
188 
199  value_type find(const char_type* input, size_type len) const;
200 
213  std::vector<key_value_type> prefix_search(const char_type* prefix, size_type len) const;
214 
220  size_type size() const;
221 
225  void clear();
226 
234  packed_type pack() const;
235 
236 private:
237  void insert_into_tree(
238  trie_node& node, const char_type* key, const char_type* key_end, const value_type& value);
239 
240  const trie_node* find_prefix_node(
241  const trie_node& node, const char_type* prefix, const char_type* prefix_end) const;
242 
243  void fill_child_node_items(
244  std::vector<key_value_type>& items, buffer_type& buffer, const trie_node& node) const;
245 
246  void count_values(size_type& n, const trie_node& node) const;
247 
248 private:
249  value_type m_null_value;
250  trie_node m_root;
251 };
252 
263 template<typename _KeyTrait, typename _ValueT>
264 class packed_trie_map
265 {
266 public:
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;
274 
279  struct entry
280  {
281  const char_type* key;
282  size_type keylen;
283  value_type value;
284 
285  entry(const char_type* _key, size_type _keylen, value_type _value) :
286  key(_key), keylen(_keylen), value(_value) {}
287  };
288 
289 private:
290  struct trie_node
291  {
292  char_type key;
293  const value_type* value;
294 
295  std::deque<trie_node*> children;
296 
297  trie_node(char_type _key) : key(_key), value(nullptr) {}
298  };
299 
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;
304 
305 public:
306 
310  packed_trie_map() = delete;
311 
322  packed_trie_map(const entry* entries, size_type entry_size, value_type null_value);
323 
331 
342  value_type find(const char_type* input, size_type len) const;
343 
356  std::vector<key_value_type> prefix_search(const char_type* prefix, size_type len) const;
357 
363  size_type size() const;
364 
365 private:
366  void traverse_range(
367  trie_node& root, node_pool_type& node_pool, const entry* start, const entry* end,
368  size_type pos);
369 
370  size_type compact_node(const trie_node& node);
371  size_type compact_node(const typename trie_map<_KeyTrait, _ValueT>::trie_node& node);
372 
373  void push_child_offsets(size_type offset, const child_offsets_type& child_offsets);
374 
375  void compact(const trie_node& root);
376  void compact(const typename trie_map<_KeyTrait, _ValueT>::trie_node& root);
377 
378  const uintptr_t* find_prefix_node(
379  const uintptr_t* p, const char_type* prefix, const char_type* prefix_end) const;
380 
381  void fill_child_node_items(
382  std::vector<key_value_type>& items, buffer_type& buffer, const uintptr_t* p) const;
383 
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;
388 #endif
389 
390 private:
391  value_type m_null_value;
392  size_type m_entry_size;
393 
394  value_store_type m_value_store;
395  packed_type m_packed;
396 };
397 
398 }
399 
400 #include "trie_map_def.inl"
401 
402 #endif
403 
404 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
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