mdds
trie_map.hpp
1/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2/*************************************************************************
3 *
4 * Copyright (c) 2015-2020 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 "trie_map_itr.hpp"
33
34#include <vector>
35#include <string>
36#include <deque>
37#include <map>
38#include <memory>
39
40namespace mdds {
41
42namespace trie {
43
47template<typename ContainerT>
49{
51 using key_type = ContainerT;
52
60
66 using key_unit_type = typename key_type::value_type;
67
77 static key_buffer_type to_key_buffer(const key_unit_type* str, size_t length)
78 {
79 return key_buffer_type(str, length);
80 }
81
91 {
92 return key_buffer_type(key);
93 }
94
95 static const key_unit_type* buffer_data(const key_buffer_type& buf)
96 {
97 return buf.data();
98 }
99
100 static size_t buffer_size(const key_buffer_type& buf)
101 {
102 return buf.size();
103 }
104
113 {
114 buffer.push_back(c);
115 }
116
123 static void pop_back(key_buffer_type& buffer)
124 {
125 buffer.pop_back();
126 }
127
136 static key_type to_key(const key_buffer_type& buf)
137 {
138 return buf;
139 }
140};
141
142using std_string_traits = std_container_traits<std::string>;
143
145template<typename T>
147{
148 static constexpr bool variable_size = false;
149
150 static constexpr size_t value_size = sizeof(T);
151
152 static void write(std::ostream& os, const T& v);
153
154 static void read(std::istream& is, size_t n, T& v);
155};
156
158template<typename T>
160{
161 static constexpr bool variable_size = true;
162
163 static void write(std::ostream& os, const T& v);
164
165 static void read(std::istream& is, size_t n, T& v);
166};
167
172template<typename T>
174{
176
177 static constexpr bool variable_size = true;
178
179 static void write(std::ostream& os, const T& v);
180
181 static void read(std::istream& is, size_t n, T& v);
182};
183
191template<typename T, typename U = void>
193{
194};
195
196template<typename T>
197struct value_serializer<T, typename std::enable_if<mdds::detail::has_value_type<T>::value>::type>
199{
200};
201
202template<>
203struct value_serializer<std::string> : variable_value_serializer<std::string>
204{
205};
206
207} // namespace trie
208
209template<typename KeyTraits, typename ValueT>
210class packed_trie_map;
211
218template<typename KeyTraits, typename ValueT>
220{
221 friend class packed_trie_map<KeyTraits, ValueT>;
222 friend class trie::detail::iterator_base<trie_map, true>;
223 friend class trie::detail::iterator_base<trie_map, false>;
225 friend class trie::detail::iterator<trie_map>;
229
230public:
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;
239
243
244private:
245 struct trie_node
246 {
247 typedef std::map<key_unit_type, trie_node> children_type;
248
249 children_type children;
250 value_type value;
251 bool has_value;
252
253 trie_node();
254 trie_node(const trie_node& other);
255 trie_node(trie_node&& other);
256
257 void swap(trie_node& other);
258 };
259
260 template<bool IsConst>
261 struct stack_item
262 {
263 using _is_const = bool_constant<IsConst>;
264
265 using child_pos_type =
267
268 using trie_node_type = typename mdds::detail::const_or_not<trie_node, _is_const>::type;
269
270 trie_node_type* node;
271 child_pos_type child_pos;
272
273 stack_item(trie_node_type* _node, const child_pos_type& _child_pos) : node(_node), child_pos(_child_pos)
274 {}
275
276 bool operator==(const stack_item& r) const
277 {
278 return node == r.node && child_pos == r.child_pos;
279 }
280
281 bool operator!=(const stack_item& r) const
282 {
283 return !operator==(r);
284 }
285 };
286
287 using const_node_stack_type = std::vector<stack_item<true>>;
288 using node_stack_type = std::vector<stack_item<false>>;
289
290public:
295
296 trie_map(const trie_map& other);
297
298 trie_map(trie_map&& other);
299
300 const_iterator begin() const;
301
302 iterator begin();
303
304 const_iterator end() const;
305
306 iterator end();
307
308 trie_map& operator=(trie_map other);
309
310 void swap(trie_map& other);
311
318 void insert(const key_type& key, const value_type& value);
319
328 void insert(const key_unit_type* key, size_type len, const value_type& value);
329
339 bool erase(const key_unit_type* key, size_type len);
340
349 const_iterator find(const key_type& key) const;
350
361 const_iterator find(const key_unit_type* input, size_type len) const;
362
371 iterator find(const key_type& key);
372
383 iterator find(const key_unit_type* input, size_type len);
384
395 search_results prefix_search(const key_type& prefix) const;
396
409 search_results prefix_search(const key_unit_type* prefix, size_type len) const;
410
416 size_type size() const;
417
418 bool empty() const noexcept;
419
423 void clear();
424
433
434private:
435 void insert_into_tree(
436 trie_node& node, const key_unit_type* key, const key_unit_type* key_end, const value_type& value);
437
438 const trie_node* find_prefix_node(
439 const trie_node& node, const key_unit_type* prefix, const key_unit_type* prefix_end) const;
440
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;
445
446 template<bool IsConst>
447 key_buffer_type build_key_buffer_from_node_stack(const std::vector<stack_item<IsConst>>& node_stack) const;
448
449 void count_values(size_type& n, const trie_node& node) const;
450
451private:
452 trie_node m_root;
453};
454
465template<typename KeyTraits, typename ValueT>
467{
470
471public:
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;
481
486 struct entry
487 {
488 const key_unit_type* key;
489 size_type keylen;
490 value_type value;
491
492 entry(const key_unit_type* _key, size_type _keylen, value_type _value)
493 : key(_key), keylen(_keylen), value(_value)
494 {}
495 };
496
497private:
498 struct trie_node
499 {
500 key_unit_type key;
501 const value_type* value;
502
503 std::deque<trie_node*> children;
504
505 trie_node(key_unit_type _key) : key(_key), value(nullptr)
506 {}
507 };
508
509 struct stack_item
510 {
511 const uintptr_t* node_pos;
512 const uintptr_t* child_pos;
513 const uintptr_t* child_end;
514
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)
517 {}
518
519 bool operator==(const stack_item& other) const
520 {
521 return node_pos == other.node_pos && child_pos == other.child_pos;
522 }
523
524 bool operator!=(const stack_item& other) const
525 {
526 return !operator==(other);
527 }
528
529 bool has_value() const
530 {
531 const value_type* pv = reinterpret_cast<const value_type*>(*node_pos);
532 return pv;
533 }
534
535 const value_type* get_value() const
536 {
537 return reinterpret_cast<const value_type*>(*node_pos);
538 }
539 };
540
541 typedef std::vector<stack_item> node_stack_type;
542
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;
547
548public:
549 packed_trie_map();
550
559 packed_trie_map(const entry* entries, size_type entry_size);
560
568
569 packed_trie_map(const packed_trie_map& other);
570
572
573 packed_trie_map& operator=(packed_trie_map other);
574
575 bool operator==(const packed_trie_map& other) const;
576
577 bool operator!=(const packed_trie_map& other) const;
578
579 const_iterator begin() const;
580
581 const_iterator end() const;
582
583 const_iterator cbegin() const;
584
585 const_iterator cend() const;
586
595 const_iterator find(const key_type& key) const;
596
607 const_iterator find(const key_unit_type* input, size_type len) const;
608
618 search_results prefix_search(const key_type& prefix) const;
619
632 search_results prefix_search(const key_unit_type* prefix, size_type len) const;
633
639 size_type size() const noexcept;
640
641 bool empty() const noexcept;
642
643 void swap(packed_trie_map& other);
644
650 template<typename FuncT = trie::value_serializer<value_type>>
651 void save_state(std::ostream& os) const;
652
659 template<typename FuncT = trie::value_serializer<value_type>>
660 void load_state(std::istream& is);
661
667 void dump_structure() const;
668
669private:
670 node_stack_type get_root_stack() const;
671
672 void traverse_range(
673 trie_node& root, node_pool_type& node_pool, const entry* start, const entry* end, size_type pos);
674
675 size_type compact_node(const trie_node& node);
676 size_type compact_node(const typename trie_map<KeyTraits, ValueT>::trie_node& node);
677
678 void push_child_offsets(size_type offset, const child_offsets_type& child_offsets);
679
680 void compact(const trie_node& root);
681 void compact(const typename trie_map<KeyTraits, ValueT>::trie_node& root);
682
683 const uintptr_t* find_prefix_node(
684 const uintptr_t* p, const key_unit_type* prefix, const key_unit_type* prefix_end) const;
685
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;
689
690 template<typename _Handler>
691 void traverse_tree(_Handler hdl) const;
692
693 template<typename _Handler>
694 void traverse_buffer(_Handler hdl) const;
695
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;
700#endif
701
702private:
703 value_store_type m_value_store;
704 packed_type m_packed;
705};
706
707} // namespace mdds
708
709#include "trie_map_def.inl"
710
711#endif
712
713/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
Definition: trie_map.hpp:467
search_results prefix_search(const key_unit_type *prefix, size_type len) const
const_iterator find(const key_type &key) const
const_iterator find(const key_unit_type *input, size_type len) const
packed_trie_map(const entry *entries, size_type entry_size)
search_results prefix_search(const key_type &prefix) const
size_type size() const noexcept
packed_trie_map(const trie_map< key_traits_type, value_type > &other)
Definition: trie_map_itr.hpp:375
Definition: trie_map_itr.hpp:89
Definition: trie_map_itr.hpp:350
Definition: trie_map_itr.hpp:501
Definition: trie_map_itr.hpp:795
Definition: trie_map_itr.hpp:440
Definition: trie_map.hpp:220
const_iterator find(const key_unit_type *input, size_type len) const
bool erase(const key_unit_type *key, size_type len)
packed_type pack() const
search_results prefix_search(const key_unit_type *prefix, size_type len) const
size_type size() const
search_results prefix_search(const key_type &prefix) const
void insert(const key_type &key, const value_type &value)
iterator find(const key_unit_type *input, size_type len)
iterator find(const key_type &key)
const_iterator find(const key_type &key) const
void insert(const key_unit_type *key, size_type len, const value_type &value)
Definition: global.hpp:149
Definition: global.hpp:167
Definition: trie_map.hpp:487
Definition: trie_map_itr.hpp:70
Definition: trie_map.hpp:147
Definition: trie_map.hpp:49
static void push_back(key_buffer_type &buffer, key_unit_type c)
Definition: trie_map.hpp:112
key_type key_buffer_type
Definition: trie_map.hpp:59
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
static void pop_back(key_buffer_type &buffer)
Definition: trie_map.hpp:123
static key_type to_key(const key_buffer_type &buf)
Definition: trie_map.hpp:136
ContainerT key_type
Definition: trie_map.hpp:51
static key_buffer_type to_key_buffer(const key_type &key)
Definition: trie_map.hpp:90
Definition: trie_map.hpp:193
Definition: trie_map.hpp:160