mdds
Loading...
Searching...
No Matches
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#include <limits>
40#include <cstdint>
41
42namespace mdds {
43
44namespace trie {
45
46namespace detail {
47
49{
50};
51
53{
54};
55
56template<typename TrieT, typename PackedT>
58
59} // namespace detail
60
62template<typename T>
64{
65 static constexpr bool variable_size = false;
66
67 static constexpr size_t value_size = sizeof(T);
68
69 static void write(std::ostream& os, const T& v);
70
71 static void read(std::istream& is, size_t n, T& v);
72};
73
75template<typename T>
77{
78 static constexpr bool variable_size = true;
79
80 static void write(std::ostream& os, const T& v);
81
82 static void read(std::istream& is, size_t n, T& v);
83};
84
89template<typename T>
91{
93
94 static constexpr bool variable_size = true;
95
96 static void write(std::ostream& os, const T& v);
97
98 static void read(std::istream& is, size_t n, T& v);
99};
100
108template<typename T, typename U = void>
112
113template<typename T>
114struct value_serializer<T, typename std::enable_if<mdds::detail::has_value_type<T>::value>::type>
116{
117};
118
119template<>
120struct value_serializer<std::string> : variable_value_serializer<std::string>
121{
122};
123
125{
135 using pack_value_type = uintptr_t;
136};
137
141enum class dump_structure_type
142{
147 packed_buffer,
148
152 trie_traversal,
153};
154
155} // namespace trie
156
157template<typename KeyT, typename ValueT, typename TraitsT>
158class packed_trie_map;
159
166template<typename KeyT, typename ValueT, typename TraitsT = trie::default_traits>
168{
169 friend class packed_trie_map<KeyT, ValueT, TraitsT>;
170 friend class trie::detail::iterator_base<trie_map, true>;
171 friend class trie::detail::iterator_base<trie_map, false>;
173 friend class trie::detail::iterator<trie_map>;
177
178public:
179 using traits_type = TraitsT;
181 typedef KeyT key_type;
182 typedef typename key_type::value_type key_unit_type;
183 typedef ValueT value_type;
184 typedef size_t size_type;
185
189
190private:
191 struct trie_node
192 {
193 typedef std::map<key_unit_type, trie_node> children_type;
194
195 children_type children;
196 value_type value;
197 bool has_value;
198
199 trie_node();
200 trie_node(const trie_node& other);
201 trie_node(trie_node&& other);
202
203 void swap(trie_node& other);
204 };
205
206 template<bool IsConst>
207 struct stack_item
208 {
209 using _is_const = std::bool_constant<IsConst>;
210
211 using child_pos_type =
213
214 using trie_node_type = typename mdds::detail::const_or_not<trie_node, _is_const>::type;
215
216 trie_node_type* node;
217 child_pos_type child_pos;
218
219 stack_item(trie_node_type* _node, const child_pos_type& _child_pos) : node(_node), child_pos(_child_pos)
220 {}
221
222 bool operator==(const stack_item& r) const
223 {
224 return node == r.node && child_pos == r.child_pos;
225 }
226
227 bool operator!=(const stack_item& r) const
228 {
229 return !operator==(r);
230 }
231 };
232
233 using const_node_stack_type = std::vector<stack_item<true>>;
234 using node_stack_type = std::vector<stack_item<false>>;
235
236public:
241 {
242 friend class trie_map;
243
244 const trie_node* m_ref_node = nullptr;
245
246 const_node_type(const trie_node* ref_node);
247
248 public:
250 const_node_type(const const_node_type& other);
251
252 const_node_type& operator=(const const_node_type& other);
253
260 bool valid() const;
261
268 bool has_child() const;
269
275 bool has_value() const;
276
286 const value_type& value() const;
287
297 const_node_type child(key_unit_type c) const;
298 };
299
304
305 trie_map(const trie_map& other);
306
307 trie_map(trie_map&& other);
308
309 const_iterator begin() const;
310
311 iterator begin();
312
313 const_iterator end() const;
314
315 iterator end();
316
317 trie_map& operator=(trie_map other);
318
319 bool operator==(const trie_map& other) const;
320 bool operator!=(const trie_map& other) const;
321
322 void swap(trie_map& other);
323
330
337 void insert(const key_type& key, value_type value);
338
347 void insert(const key_unit_type* key, size_type len, value_type value);
348
358 bool erase(const key_unit_type* key, size_type len);
359
368 const_iterator find(const key_type& key) const;
369
380 const_iterator find(const key_unit_type* input, size_type len) const;
381
390 iterator find(const key_type& key);
391
402 iterator find(const key_unit_type* input, size_type len);
403
414 search_results prefix_search(const key_type& prefix) const;
415
428 search_results prefix_search(const key_unit_type* prefix, size_type len) const;
429
435 size_type size() const;
436
437 bool empty() const noexcept;
438
442 void clear();
443
463
464private:
465 void insert_into_tree(trie_node& node, const key_unit_type* key, const key_unit_type* key_end, value_type value);
466
467 const trie_node* find_prefix_node(
468 const trie_node& node, const key_unit_type* prefix, const key_unit_type* prefix_end) const;
469
470 template<bool IsConst>
471 void find_prefix_node_with_stack(
472 std::vector<stack_item<IsConst>>& node_stack, mdds::detail::const_t<trie_node, IsConst>& node,
473 const key_unit_type* prefix, const key_unit_type* prefix_end) const;
474
475 template<bool IsConst>
476 key_type build_key_buffer_from_node_stack(const std::vector<stack_item<IsConst>>& node_stack) const;
477
478 void count_values(size_type& n, const trie_node& node) const;
479
480 bool descend_for_equality(const trie_node& left, const trie_node& right) const;
481
482private:
483 trie_node m_root;
484};
485
496template<typename KeyT, typename ValueT, typename TraitsT = trie::default_traits>
498{
499 using pack_value_type = typename TraitsT::pack_value_type;
500 using packed_type = std::vector<pack_value_type>;
501
504 friend class trie_map<KeyT, ValueT, TraitsT>;
505 friend struct trie::detail::dump_packed_buffer<packed_trie_map, packed_type>;
506
507public:
508 using traits_type = TraitsT;
509 typedef KeyT key_type;
510 typedef typename key_type::value_type key_unit_type;
511 typedef ValueT value_type;
512 typedef size_t size_type;
515
520 struct entry
521 {
522 const key_unit_type* key;
523 size_type keylen;
524 value_type value;
525
526 entry(const key_unit_type* _key, size_type _keylen, value_type _value)
527 : key(_key), keylen(_keylen), value(_value)
528 {}
529 };
530
531private:
532 using value_store_type = std::deque<value_type>;
533
535 static constexpr auto null_value = std::numeric_limits<pack_value_type>::max();
537 static constexpr auto max_value_pos = null_value - 1u;
538
539 struct trie_node
540 {
541 key_unit_type key;
542 const value_type* value;
543
544 std::deque<trie_node*> children;
545
546 trie_node(key_unit_type _key) : key(_key), value(nullptr)
547 {}
548 };
549
550 struct stack_item
551 {
552 const value_store_type* value_store = nullptr;
553
554 const pack_value_type* node_pos = nullptr;
555 const pack_value_type* child_pos = nullptr;
556 const pack_value_type* child_end = nullptr;
557
558 stack_item(
559 const value_store_type* _value_store, const pack_value_type* _node_pos, const pack_value_type* _child_pos,
560 const pack_value_type* _child_end)
561 : value_store(_value_store), node_pos(_node_pos), child_pos(_child_pos), child_end(_child_end)
562 {}
563
564 bool operator==(const stack_item& other) const
565 {
566 return value_store == other.value_store && node_pos == other.node_pos && child_pos == other.child_pos &&
567 child_end == other.child_end;
568 }
569
570 bool operator!=(const stack_item& other) const
571 {
572 return !operator==(other);
573 }
574
575 bool has_value() const
576 {
577 return *node_pos != null_value;
578 }
579
580 pack_value_type get_value_pos() const
581 {
582 return *node_pos;
583 }
584 };
585
586 typedef std::vector<stack_item> node_stack_type;
587 typedef std::deque<trie_node> node_pool_type;
588 typedef std::vector<std::tuple<size_t, key_unit_type>> child_offsets_type;
589
590 packed_trie_map(trie::detail::move_to_pack, trie_map<KeyT, ValueT, TraitsT>& from);
591
592public:
597 {
598 friend class packed_trie_map;
599
600 const packed_type* m_packed = nullptr;
601 const value_store_type* m_value_store = nullptr;
602 const pack_value_type* m_pos = nullptr;
603
604 const_node_type(const packed_type* packed, const value_store_type* value_store, const pack_value_type* p);
605
606 public:
607 const_node_type() = default;
608 const_node_type(const const_node_type& other) = default;
609
610 const_node_type& operator=(const const_node_type& other);
611
618 bool valid() const;
619
626 bool has_child() const;
627
633 bool has_value() const;
634
644 const value_type& value() const;
645
655 const_node_type child(key_unit_type c) const;
656 };
657
659
673 packed_trie_map(const entry* entries, size_type entry_size);
674
687
688 packed_trie_map(const packed_trie_map& other);
689
691
692 packed_trie_map& operator=(packed_trie_map other);
693
694 bool operator==(const packed_trie_map& other) const;
695
696 bool operator!=(const packed_trie_map& other) const;
697
698 const_iterator begin() const;
699
700 const_iterator end() const;
701
702 const_iterator cbegin() const;
703
704 const_iterator cend() const;
705
714 const_iterator find(const key_type& key) const;
715
726 const_iterator find(const key_unit_type* input, size_type len) const;
727
737 search_results prefix_search(const key_type& prefix) const;
738
751 search_results prefix_search(const key_unit_type* prefix, size_type len) const;
752
758 size_type size() const noexcept;
759
760 bool empty() const noexcept;
761
762 void swap(packed_trie_map& other);
763
770
776 template<typename FuncT = trie::value_serializer<value_type>>
777 void save_state(std::ostream& os) const;
778
785 template<typename FuncT = trie::value_serializer<value_type>>
786 void load_state(std::istream& is);
787
794 std::string dump_structure(trie::dump_structure_type type) const;
795
796private:
797 void dump_trie_traversal(std::ostream& os) const;
798
799 node_stack_type get_root_stack() const;
800
801 void traverse_range(
802 trie_node& root, node_pool_type& node_pool, const entry* start, const entry* end, size_type pos);
803
804 size_type compact_node(const trie_node& node);
805
806 template<typename ModeT, typename NodeT>
807 size_type compact_node(ModeT, NodeT& node);
808
809 void check_value_size_or_throw() const;
810
811 size_type push_value_to_store(trie::detail::copy_to_pack, const value_type& value);
812 size_type push_value_to_store(trie::detail::move_to_pack, value_type& value);
813
814 void push_child_offsets(size_type offset, const child_offsets_type& child_offsets);
815
816 void init_pack();
817 void compact(const trie_node& root);
818
819 template<typename ModeT, typename NodeT>
820 void compact(ModeT, NodeT& root);
821
822 template<typename _Handler>
823 void traverse_tree(_Handler hdl) const;
824
825private:
826 value_store_type m_value_store;
827 packed_type m_packed;
828};
829
830} // namespace mdds
831
832#include "trie_map_def.inl"
833
834#endif
835
836/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
Definition trie_map.hpp:597
const value_type & value() const
const_node_type child(key_unit_type c) const
Definition trie_map.hpp:498
packed_trie_map(const entry *entries, size_type entry_size)
packed_trie_map(const trie_map< KeyT, ValueT, TraitsT > &other)
search_results prefix_search(const key_type &prefix) const
size_type size() const noexcept
const_iterator find(const key_unit_type *input, size_type len) const
const_iterator find(const key_type &key) const
search_results prefix_search(const key_unit_type *prefix, size_type len) const
Definition trie_map_itr.hpp:365
Definition trie_map_itr.hpp:89
Definition trie_map_itr.hpp:340
Definition trie_map_itr.hpp:489
Definition trie_map_itr.hpp:786
Definition trie_map_itr.hpp:430
Definition trie_map.hpp:241
const_node_type child(key_unit_type c) const
const value_type & value() const
Definition trie_map.hpp:168
void insert(const key_unit_type *key, size_type len, value_type value)
bool erase(const key_unit_type *key, size_type len)
const_iterator find(const key_unit_type *input, size_type len) const
packed_type pack()
const_node_type root_node() 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
iterator find(const key_type &key)
const_iterator find(const key_type &key) const
void insert(const key_type &key, value_type value)
iterator find(const key_unit_type *input, size_type len)
Definition global.hpp:146
Definition global.hpp:182
Definition trie_map.hpp:521
Definition trie_map.hpp:125
uintptr_t pack_value_type
Definition trie_map.hpp:135
Definition trie_map.hpp:49
Definition trie_map.hpp:57
Definition trie_map_itr.hpp:70
Definition trie_map.hpp:53
Definition trie_map.hpp:64
Definition trie_map.hpp:110
Definition trie_map.hpp:77