mdds
Loading...
Searching...
No Matches
trie_map.hpp
1/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2
3// SPDX-FileCopyrightText: 2015 - 2025 Kohei Yoshida
4//
5// SPDX-License-Identifier: MIT
6
7#pragma once
8
9#include "trie_map_itr.hpp"
10
11#include <vector>
12#include <string>
13#include <string_view>
14#include <span>
15#include <concepts>
16#include <deque>
17#include <map>
18#include <memory>
19#include <limits>
20#include <cstdint>
21
22namespace mdds {
23
24namespace trie {
25
26namespace detail {
27
29{
30};
31
33{
34};
35
36template<typename TrieT, typename PackedT>
38
40template<typename T>
41concept character_unit = std::same_as<T, char> || std::same_as<T, wchar_t> || std::same_as<T, char8_t> ||
42 std::same_as<T, char16_t> || std::same_as<T, char32_t>;
43
48template<typename T>
50{
51 using type = std::span<const T>;
52};
53
54template<character_unit T>
55struct key_view<T>
56{
57 using type = std::basic_string_view<T>;
58};
59
60template<typename T>
61using key_view_t = typename key_view<T>::type;
62
63} // namespace detail
64
66template<typename T>
68{
69 static constexpr bool variable_size = false;
70
71 static constexpr size_t value_size = sizeof(T);
72
73 static void write(std::ostream& os, const T& v);
74
75 static void read(std::istream& is, size_t n, T& v);
76};
77
79template<typename T>
81{
82 static constexpr bool variable_size = true;
83
84 static void write(std::ostream& os, const T& v);
85
86 static void read(std::istream& is, size_t n, T& v);
87};
88
93template<typename T>
95{
96 using element_serializer = numeric_value_serializer<typename T::value_type>;
97
98 static constexpr bool variable_size = true;
99
100 static void write(std::ostream& os, const T& v);
101
102 static void read(std::istream& is, size_t n, T& v);
103};
104
112template<typename T>
116
117template<mdds::detail::has_value_type T>
121
122template<>
123struct value_serializer<std::string> : variable_value_serializer<std::string>
124{
125};
126
128{
138 using pack_value_type = uintptr_t;
139};
140
144enum class dump_structure_type
145{
150 packed_buffer,
151
155 trie_traversal,
156};
157
158} // namespace trie
159
160template<typename KeyT, typename ValueT, typename TraitsT>
161class packed_trie_map;
162
169template<typename KeyT, typename ValueT, typename TraitsT = trie::default_traits>
171{
172 friend class packed_trie_map<KeyT, ValueT, TraitsT>;
173 friend class trie::detail::iterator_base<trie_map, true>;
174 friend class trie::detail::iterator_base<trie_map, false>;
176 friend class trie::detail::iterator<trie_map>;
180
181public:
182 using traits_type = TraitsT;
183 using packed_type = packed_trie_map<KeyT, ValueT, TraitsT>;
184 using key_type = KeyT;
185 using key_unit_type = typename key_type::value_type;
186 using key_view_type = trie::detail::key_view_t<key_unit_type>;
187 using value_type = ValueT;
188 using size_type = std::size_t;
189
190 using const_iterator = trie::detail::const_iterator<trie_map>;
191 using iterator = trie::detail::iterator<trie_map>;
192 using search_results = trie::detail::search_results<trie_map>;
193
194private:
195 struct trie_node
196 {
197 typedef std::map<key_unit_type, trie_node> children_type;
198
199 children_type children;
200 value_type value;
201 bool has_value;
202
203 trie_node();
204 trie_node(const trie_node& other);
205 trie_node(trie_node&& other);
206
207 void swap(trie_node& other);
208 };
209
210 template<bool IsConst>
211 struct stack_item
212 {
213 using is_const_type = std::bool_constant<IsConst>;
214
215 using child_pos_type =
217
219
220 trie_node_type* node;
221 child_pos_type child_pos;
222
223 stack_item(trie_node_type* _node, const child_pos_type& _child_pos) : node(_node), child_pos(_child_pos)
224 {}
225
226 bool operator==(const stack_item& r) const
227 {
228 return node == r.node && child_pos == r.child_pos;
229 }
230 };
231
232 using const_node_stack_type = std::vector<stack_item<true>>;
233 using node_stack_type = std::vector<stack_item<false>>;
234
235public:
239 class const_node_type
240 {
241 friend class trie_map;
242
243 const trie_node* m_ref_node = nullptr;
244
245 const_node_type(const trie_node* ref_node);
246
247 public:
248 const_node_type();
249 const_node_type(const const_node_type& other);
250
251 const_node_type& operator=(const const_node_type& other);
252
259 bool valid() const;
260
267 bool has_child() const;
268
274 bool has_value() const;
275
285 const value_type& value() const;
286
296 const_node_type child(key_unit_type c) const;
297 };
298
303
304 trie_map(const trie_map& other);
305
306 trie_map(trie_map&& other);
307
308 const_iterator begin() const;
309
310 iterator begin();
311
312 const_iterator end() const;
313
314 iterator end();
315
316 trie_map& operator=(trie_map other);
317
318 bool operator==(const trie_map& other) const;
319
320 void swap(trie_map& other);
321
328
335 void insert(key_view_type key, value_type value);
336
345 [[deprecated("use the overload taking key_view_type instead")]] void insert(
346 const key_unit_type* key, size_type len, value_type value);
347
355 bool erase(key_view_type key);
356
366 [[deprecated("use the overload taking key_view_type instead")]] bool erase(const key_unit_type* key, size_type len);
367
376 const_iterator find(key_view_type key) const;
377
388 [[deprecated("use the overload taking key_view_type instead")]] const_iterator find(
389 const key_unit_type* input, size_type len) const;
390
399 iterator find(key_view_type key);
400
411 [[deprecated("use the overload taking key_view_type instead")]] iterator find(
412 const key_unit_type* input, size_type len);
413
423 search_results prefix_search(key_view_type prefix) const;
424
437 [[deprecated("use the overload taking key_view_type instead")]] search_results prefix_search(
438 const key_unit_type* prefix, size_type len) const;
439
445 size_type size() const;
446
447 bool empty() const noexcept;
448
452 void clear();
453
472 packed_type pack();
473
474private:
475 void insert_into_tree(trie_node& node, const key_unit_type* key, const key_unit_type* key_end, value_type value);
476
477 const trie_node* find_prefix_node(
478 const trie_node& node, const key_unit_type* prefix, const key_unit_type* prefix_end) const;
479
480 template<bool IsConst>
481 void find_prefix_node_with_stack(
482 std::vector<stack_item<IsConst>>& node_stack, mdds::detail::const_t<trie_node, IsConst>& node,
483 const key_unit_type* prefix, const key_unit_type* prefix_end) const;
484
485 template<bool IsConst>
486 key_type build_key_buffer_from_node_stack(const std::vector<stack_item<IsConst>>& node_stack) const;
487
488 void count_values(size_type& n, const trie_node& node) const;
489
490 bool descend_for_equality(const trie_node& left, const trie_node& right) const;
491
492private:
493 trie_node m_root;
494};
495
506template<typename KeyT, typename ValueT, typename TraitsT = trie::default_traits>
507class packed_trie_map
508{
509 using pack_value_type = typename TraitsT::pack_value_type;
510 using packed_type = std::vector<pack_value_type>;
511
512 friend class trie::detail::packed_iterator_base<packed_trie_map>;
513 friend class trie::detail::packed_search_results<packed_trie_map>;
514 friend class trie_map<KeyT, ValueT, TraitsT>;
515 friend struct trie::detail::dump_packed_buffer<packed_trie_map, packed_type>;
516
517public:
518 using traits_type = TraitsT;
519 using key_type = KeyT;
520 using key_unit_type = typename key_type::value_type;
521 using key_view_type = trie::detail::key_view_t<key_unit_type>;
522 using value_type = ValueT;
523 using size_type = std::size_t;
526
531 struct entry
532 {
533 const key_unit_type* key;
534 size_type keylen;
535 value_type value;
536
537 entry(const key_unit_type* _key, size_type _keylen, value_type _value)
538 : key(_key), keylen(_keylen), value(std::move(_value))
539 {}
540 };
541
542private:
543 using value_store_type = std::deque<value_type>;
544
546 static constexpr auto null_value = std::numeric_limits<pack_value_type>::max();
548 static constexpr auto max_value_pos = null_value - 1u;
549
550 struct trie_node
551 {
552 key_unit_type key;
553 const value_type* value;
554
555 std::deque<trie_node*> children;
556
557 trie_node(key_unit_type _key) : key(_key), value(nullptr)
558 {}
559 };
560
561 struct stack_item
562 {
563 const value_store_type* value_store = nullptr;
564
565 const pack_value_type* node_pos = nullptr;
566 const pack_value_type* child_pos = nullptr;
567 const pack_value_type* child_end = nullptr;
568
569 stack_item(
570 const value_store_type* _value_store, const pack_value_type* _node_pos, const pack_value_type* _child_pos,
571 const pack_value_type* _child_end)
572 : value_store(_value_store), node_pos(_node_pos), child_pos(_child_pos), child_end(_child_end)
573 {}
574
575 bool operator==(const stack_item& other) const
576 {
577 return value_store == other.value_store && node_pos == other.node_pos && child_pos == other.child_pos &&
578 child_end == other.child_end;
579 }
580
581 bool has_value() const
582 {
583 return *node_pos != null_value;
584 }
585
586 pack_value_type get_value_pos() const
587 {
588 return *node_pos;
589 }
590 };
591
592 typedef std::vector<stack_item> node_stack_type;
593 typedef std::deque<trie_node> node_pool_type;
594 typedef std::vector<std::tuple<size_t, key_unit_type>> child_offsets_type;
595
596 packed_trie_map(trie::detail::move_to_pack, trie_map<KeyT, ValueT, TraitsT>& from);
597
598public:
602 class const_node_type
603 {
604 friend class packed_trie_map;
605
606 const packed_type* m_packed = nullptr;
607 const value_store_type* m_value_store = nullptr;
608 const pack_value_type* m_pos = nullptr;
609
610 const_node_type(const packed_type* packed, const value_store_type* value_store, const pack_value_type* p);
611
612 public:
613 const_node_type() = default;
614 const_node_type(const const_node_type& other) = default;
615
616 const_node_type& operator=(const const_node_type& other);
617
624 bool valid() const;
625
632 bool has_child() const;
633
639 bool has_value() const;
640
650 const value_type& value() const;
651
661 const_node_type child(key_unit_type c) const;
662 };
663
664 packed_trie_map();
665
678 packed_trie_map(std::span<const entry> entries);
679
693 [[deprecated("use the constructor taking std::span<const entry> instead")]] packed_trie_map(
694 const entry* entries, size_type entry_size);
695
708
709 packed_trie_map(const packed_trie_map& other);
710
711 packed_trie_map(packed_trie_map&& other);
712
713 packed_trie_map& operator=(packed_trie_map other);
714
715 bool operator==(const packed_trie_map& other) const;
716
717 const_iterator begin() const;
718
719 const_iterator end() const;
720
721 const_iterator cbegin() const;
722
723 const_iterator cend() const;
724
733 const_iterator find(key_view_type key) const;
734
745 [[deprecated("use the overload taking key_view_type instead")]] const_iterator find(
746 const key_unit_type* input, size_type len) const;
747
756 search_results prefix_search(key_view_type prefix) const;
757
770 [[deprecated("use the overload taking key_view_type instead")]] search_results prefix_search(
771 const key_unit_type* prefix, size_type len) const;
772
778 size_type size() const noexcept;
779
780 bool empty() const noexcept;
781
782 void swap(packed_trie_map& other);
783
789 const_node_type root_node() const;
790
796 template<typename FuncT = trie::value_serializer<value_type>>
797 void save_state(std::ostream& os) const;
798
805 template<typename FuncT = trie::value_serializer<value_type>>
806 void load_state(std::istream& is);
807
814 std::string dump_structure(trie::dump_structure_type type) const;
815
816private:
817 void dump_trie_traversal(std::ostream& os) const;
818
819 node_stack_type get_root_stack() const;
820
821 void traverse_range(
822 trie_node& root, node_pool_type& node_pool, const entry* start, const entry* end, size_type pos);
823
824 size_type compact_node(const trie_node& node);
825
826 template<typename ModeT, typename NodeT>
827 size_type compact_node(ModeT, NodeT& node);
828
829 void check_value_size_or_throw() const;
830
831 size_type push_value_to_store(trie::detail::copy_to_pack, const value_type& value);
832 size_type push_value_to_store(trie::detail::move_to_pack, value_type& value);
833
834 void push_child_offsets(size_type offset, const child_offsets_type& child_offsets);
835
836 void init_pack();
837 void compact(const trie_node& root);
838
839 template<typename ModeT, typename NodeT>
840 void compact(ModeT, NodeT& root);
841
842 template<typename _Handler>
843 void traverse_tree(_Handler hdl) const;
844
845private:
846 value_store_type m_value_store;
847 packed_type m_packed;
848};
849
850} // namespace mdds
851
852#include "trie_map_def.inl"
853
854/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
const value_type & value() const
const_node_type child(key_unit_type c) const
Definition trie_map.hpp:508
packed_trie_map(const entry *entries, size_type entry_size)
packed_trie_map(const trie_map< KeyT, ValueT, TraitsT > &other)
packed_trie_map(std::span< const entry > entries)
search_results prefix_search(key_view_type prefix) const
void save_state(std::ostream &os) const
size_type size() const noexcept
const_iterator find(const key_unit_type *input, size_type len) const
std::string dump_structure(trie::dump_structure_type type) const
const_iterator find(key_view_type key) const
search_results prefix_search(const key_unit_type *prefix, size_type len) const
Definition trie_map_itr.hpp:336
Definition trie_map_itr.hpp:65
Definition trie_map_itr.hpp:311
Definition trie_map_itr.hpp:448
Definition trie_map_itr.hpp:740
Definition trie_map_itr.hpp:389
Definition trie_map.hpp:240
const_node_type child(key_unit_type c) const
const value_type & value() const
Definition trie_map.hpp:171
void insert(const key_unit_type *key, size_type len, value_type value)
search_results prefix_search(key_view_type prefix) const
iterator find(key_view_type key)
bool erase(const key_unit_type *key, size_type len)
const_iterator find(const key_unit_type *input, size_type len) const
bool erase(key_view_type key)
void insert(key_view_type key, value_type value)
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
const_iterator find(key_view_type key) const
iterator find(const key_unit_type *input, size_type len)
Definition trie_map.hpp:41
Definition global.hpp:104
Definition global.hpp:140
Definition trie_map.hpp:128
uintptr_t pack_value_type
Definition trie_map.hpp:138
Definition trie_map.hpp:29
Definition trie_map.hpp:37
Definition trie_map_itr.hpp:46
Definition trie_map.hpp:50
Definition trie_map.hpp:33
Definition trie_map.hpp:68
Definition trie_map.hpp:114
Definition trie_map.hpp:81