Debian Codegraph @

third_party/hat-trie/tsl/htrie_hash.h

raw
1 /**
2 * MIT License
3 *
4 * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <[email protected]>
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to deal
8 * in the Software without restriction, including without limitation the rights
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in all
14 * copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 */
24 #ifndef TSL_HTRIE_HASH_H
25 #define TSL_HTRIE_HASH_H
26
27 #include <algorithm>
28 #include <array>
29 #include <cmath>
30 #include <cstddef>
31 #include <cstdint>
32 #include <cstring>
33 #include <iterator>
34 #include <limits>
35 #include <memory>
36 #include <stdexcept>
37 #include <string>
38 #include <type_traits>
39 #include <utility>
40 #include <vector>
41 #include "array-hash/array_map.h"
42 #include "array-hash/array_set.h"
43
44
45 /*
46 * __has_include is a bit useless (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=79433),
47 * check also __cplusplus version.
48 */
49 #ifdef __has_include
50 # if __has_include(<string_view>) && __cplusplus >= 201703L
51 # define TSL_HT_HAS_STRING_VIEW
52 # endif
53 #endif
54
55
56 #ifdef TSL_HT_HAS_STRING_VIEW
57 # include <string_view>
58 #endif
59
60
61 #ifdef TSL_DEBUG
62 # define tsl_ht_assert(expr) assert(expr)
63 #else
64 # define tsl_ht_assert(expr) (static_cast<void>(0))
65 #endif
66
67
68 namespace tsl {
69
70 namespace detail_htrie_hash {
71
72 template<typename T, typename = void>
73 struct is_iterator: std::false_type {
74 };
75
76 template<typename T>
77 struct is_iterator<T, typename std::enable_if<!std::is_same<typename std::iterator_traits<T>::iterator_category, void>::value>::type>: std::true_type {
78 };
79
80 template<typename T, typename... U>
81 struct is_related: std::false_type {};
82
83 template<typename T, typename U>
84 struct is_related<T, U>: std::is_same<typename std::remove_cv<typename std::remove_reference<T>::type>::type,
85 typename std::remove_cv<typename std::remove_reference<U>::type>::type> {};
86
87 template<typename T, typename U>
88 static T numeric_cast(U value, const char* error_message = "numeric_cast() failed.") {
89 T ret = static_cast<T>(value);
90 if(static_cast<U>(ret) != value) {
91 THROW(std::runtime_error, error_message);
92 }
93
94 const bool is_same_signedness = (std::is_unsigned<T>::value && std::is_unsigned<U>::value) ||
95 (std::is_signed<T>::value && std::is_signed<U>::value);
96 if(!is_same_signedness && (ret < T{}) != (value < U{})) {
97 THROW(std::runtime_error, error_message);
98 }
99
100 return ret;
101 }
102
103
104 template<class T>
105 struct value_node {
106 /*
107 * Avoid conflict with copy constructor 'value_node(const value_node&)'. If we call the copy constructor
108 * with a mutable reference 'value_node(value_node&)', we don't want the forward constructor to be called.
109 */
110 template<class... Args, typename std::enable_if<!is_related<value_node, Args...>::value>::type* = nullptr>
111 value_node(Args&&... args): m_value(std::forward<Args>(args)...) {
112 }
113
114 T m_value;
115 };
116
117 template<>
118 struct value_node<void> {
119 };
120
121
122 /**
123 * T should be void if there is no value associated to a key (in a set for example).
124 */
125 template<class CharT,
126 class T,
127 class Hash,
128 class KeySizeT>
129 class htrie_hash {
130 private:
131 template<typename U>
132 using has_value = typename std::integral_constant<bool, !std::is_same<U, void>::value>;
133
134 static_assert(std::is_same<CharT, char>::value, "char is the only supported CharT type for now.");
135
136 static const std::size_t ALPHABET_SIZE =
137 std::numeric_limits<typename std::make_unsigned<CharT>::type>::max() + 1;
138
139
140 public:
141 template<bool IsConst, bool IsPrefixIterator>
142 class htrie_hash_iterator;
143
144
145 using char_type = CharT;
146 using key_size_type = KeySizeT;
147 using size_type = std::size_t;
148 using hasher = Hash;
149 using iterator = htrie_hash_iterator<false, false>;
150 using const_iterator = htrie_hash_iterator<true, false>;
151 using prefix_iterator = htrie_hash_iterator<false, true>;
152 using const_prefix_iterator = htrie_hash_iterator<true, true>;
153
154
155 private:
156 using array_hash_type =
157 typename std::conditional<
158 has_value<T>::value,
159 tsl::array_map<CharT, T, Hash, tsl::ah::str_equal<CharT>, false,
160 KeySizeT, std::uint16_t, tsl::ah::power_of_two_growth_policy<4>>,
161 tsl::array_set<CharT, Hash, tsl::ah::str_equal<CharT>, false,
162 KeySizeT, std::uint16_t, tsl::ah::power_of_two_growth_policy<4>>>::type;
163
164
165 private:
166 /*
167 * The tree is mainly composed of two nodes types: trie_node and hash_node which both have anode as base class.
168 * Each child is either a hash_node or a trie_node.
169 *
170 * A hash_node is always a leaf node, it doesn't have any child.
171 *
172 * Example:
173 * | ... | a |.. ..................... | f | ... | trie_node_1
174 * \ \
175 * hash_node_1 |array_hash = {"dd"}| |...| a | ... | trie_node_2
176 * /
177 * |array_hash = {"ble", "bric", "lse"}| hash_node_2
178 *
179 *
180 * Each trie_node may also have a value node, which contains a value T, if the trie_node marks
181 * the end of a string value.
182 *
183 * A trie node should at least have one child or a value node. There can't be a trie node without
184 * any child and no value node.
185 */
186
187 using value_node = tsl::detail_htrie_hash::value_node<T>;
188
189
190 class trie_node;
191 class hash_node;
192
193 // TODO better encapsulate operations modifying the tree.
194 class anode {
195 friend class trie_node;
196
197 public:
198 /*
199 * TODO Avoid the virtual to economize 8 bytes. We could use a custom deleter in the std::unique_ptr<anode>
200 * we use (as we know if an anode is a trie_node or hash_node).
201 */
202 virtual ~anode() = default;
203
204 bool is_trie_node() const noexcept {
205 return m_node_type == node_type::TRIE_NODE;
206 }
207
208 bool is_hash_node() const noexcept {
209 return m_node_type == node_type::HASH_NODE;
210 }
211
212 trie_node& as_trie_node() noexcept {
213 tsl_ht_assert(is_trie_node());
214 return static_cast<trie_node&>(*this);
215 }
216
217 hash_node& as_hash_node() noexcept {
218 tsl_ht_assert(is_hash_node());
219 return static_cast<hash_node&>(*this);
220 }
221
222 const trie_node& as_trie_node() const noexcept {
223 tsl_ht_assert(is_trie_node());
224 return static_cast<const trie_node&>(*this);
225 }
226
227 const hash_node& as_hash_node() const noexcept {
228 tsl_ht_assert(is_hash_node());
229 return static_cast<const hash_node&>(*this);
230 }
231
232 /**
233 * @see m_child_of_char
234 */
235 CharT child_of_char() const noexcept {
236 tsl_ht_assert(parent() != nullptr);
237 return m_child_of_char;
238 }
239
240 /**
241 * Return nullptr if none.
242 */
243 trie_node* parent() noexcept {
244 return m_parent_node;
245 }
246
247 const trie_node* parent() const noexcept {
248 return m_parent_node;
249 }
250
251 protected:
252 enum class node_type: unsigned char {
253 HASH_NODE,
254 TRIE_NODE
255 };
256
257 anode(node_type node_type_): m_node_type(node_type_), m_child_of_char(0),
258 m_parent_node(nullptr)
259 {
260 }
261
262 anode(node_type node_type_, CharT child_of_char): m_node_type(node_type_),
263 m_child_of_char(child_of_char),
264 m_parent_node(nullptr)
265 {
266 }
267
268
269 protected:
270 node_type m_node_type;
271
272 /**
273 * If the node has a parent, then it's a descendant of some char.
274 *
275 * Example:
276 * | ... | a | b | ... | trie_node_1
277 * \
278 * |...| a | ... | trie_node_2
279 * /
280 * |array_hash| hash_node_1
281 *
282 * trie_node_2 is a child of trie_node_1 through 'b', it will have 'b' as m_child_of_char.
283 * hash_node_1 is a child of trie_node_2 through 'a', it will have 'a' as m_child_of_char.
284 *
285 * trie_node_1 has no parent, its m_child_of_char is undefined.
286 */
287 CharT m_child_of_char;
288 trie_node* m_parent_node;
289 };
290
291 // Give the position in trie_node::m_children corresponding to the character c
292 static std::size_t as_position(CharT c) noexcept {
293 return static_cast<std::size_t>(static_cast<typename std::make_unsigned<CharT>::type>(c));
294 }
295
296 class trie_node: public anode {
297 public:
298 trie_node(): anode(anode::node_type::TRIE_NODE),
299 m_value_node(nullptr), m_children()
300 {
301 }
302
303 trie_node(const trie_node& other): anode(anode::node_type::TRIE_NODE, other.m_child_of_char),
304 m_value_node(nullptr), m_children()
305 {
306 if(other.m_value_node != nullptr) {
307 m_value_node = make_unique<value_node>(*other.m_value_node);
308 }
309
310 // TODO avoid recursion
311 for(std::size_t ichild = 0; ichild < other.m_children.size(); ichild++) {
312 if(other.m_children[ichild] != nullptr) {
313 if(other.m_children[ichild]->is_hash_node()) {
314 m_children[ichild] = make_unique<hash_node>(other.m_children[ichild]->as_hash_node());
315 }
316 else {
317 m_children[ichild] = make_unique<trie_node>(other.m_children[ichild]->as_trie_node());
318 }
319
320 m_children[ichild]->m_parent_node = this;
321 }
322 }
323 }
324
325 trie_node(trie_node&& other) = delete;
326 trie_node& operator=(const trie_node& other) = delete;
327 trie_node& operator=(trie_node&& other) = delete;
328
329 /**
330 * Return nullptr if none.
331 */
332 anode* first_child() noexcept {
333 return const_cast<anode*>(static_cast<const trie_node*>(this)->first_child());
334 }
335
336 const anode* first_child() const noexcept {
337 for(std::size_t ichild = 0; ichild < m_children.size(); ichild++) {
338 if(m_children[ichild] != nullptr) {
339 return m_children[ichild].get();
340 }
341 }
342
343 return nullptr;
344 }
345
346
347 /**
348 * Get the next_child that come after current_child. Return nullptr if no next child.
349 */
350 anode* next_child(const anode& current_child) noexcept {
351 return const_cast<anode*>(static_cast<const trie_node*>(this)->next_child(current_child));
352 }
353
354 const anode* next_child(const anode& current_child) const noexcept {
355 tsl_ht_assert(current_child.parent() == this);
356
357 for(std::size_t ichild = as_position(current_child.child_of_char()) + 1;
358 ichild < m_children.size();
359 ichild++)
360 {
361 if(m_children[ichild] != nullptr) {
362 return m_children[ichild].get();
363 }
364 }
365
366 return nullptr;
367 }
368
369
370 /**
371 * Return the first left-descendant trie node with an m_value_node. If none return the most left trie node.
372 */
373 trie_node& most_left_descendant_value_trie_node() noexcept {
374 return const_cast<trie_node&>(static_cast<const trie_node*>(this)->most_left_descendant_value_trie_node());
375 }
376
377 const trie_node& most_left_descendant_value_trie_node() const noexcept {
378 const trie_node* current_node = this;
379 while(true) {
380 if(current_node->m_value_node != nullptr) {
381 return *current_node;
382 }
383
384 const anode* first_child = current_node->first_child();
385 tsl_ht_assert(first_child != nullptr); // a trie_node must either have a value_node or at least one child.
386 if(first_child->is_hash_node()) {
387 return *current_node;
388 }
389
390 current_node = &first_child->as_trie_node();
391 }
392 }
393
394
395
396 size_type nb_children() const noexcept {
397 return std::count_if(m_children.cbegin(), m_children.cend(),
398 [](const std::unique_ptr<anode>& n) { return n != nullptr; });
399 }
400
401 bool empty() const noexcept {
402 return std::all_of(m_children.cbegin(), m_children.cend(),
403 [](const std::unique_ptr<anode>& n) { return n == nullptr; });
404 }
405
406 std::unique_ptr<anode>& child(CharT for_char) noexcept {
407 return m_children[as_position(for_char)];
408 }
409
410 const std::unique_ptr<anode>& child(CharT for_char) const noexcept {
411 return m_children[as_position(for_char)];
412 }
413
414 typename std::array<std::unique_ptr<anode>, ALPHABET_SIZE>::iterator begin() noexcept {
415 return m_children.begin();
416 }
417
418 typename std::array<std::unique_ptr<anode>, ALPHABET_SIZE>::iterator end() noexcept {
419 return m_children.end();
420 }
421
422 void set_child(CharT for_char, std::unique_ptr<anode> child) noexcept {
423 if(child != nullptr) {
424 child->m_child_of_char = for_char;
425 child->m_parent_node = this;
426 }
427
428 m_children[as_position(for_char)] = std::move(child);
429 }
430
431 std::unique_ptr<value_node>& val_node() noexcept {
432 return m_value_node;
433 }
434
435 const std::unique_ptr<value_node>& val_node() const noexcept {
436 return m_value_node;
437 }
438
439 private:
440 // TODO Avoid storing a value_node when has_value<T>::value is false
441 std::unique_ptr<value_node> m_value_node;
442
443 /**
444 * Each character CharT corresponds to one position in the array. To convert a character
445 * to a position use the as_position method.
446 *
447 * TODO Try to reduce the size of m_children with a hash map, linear/binary search on array, ...
448 * TODO Store number of non-null values in m_children. Check if we can store this value in the alignment
449 * space as we don't want the node to get bigger (empty() and nb_children() are rarely used so it is
450 * not an important variable).
451 */
452 std::array<std::unique_ptr<anode>, ALPHABET_SIZE> m_children;
453 };
454
455
456 class hash_node: public anode {
457 public:
458 hash_node(const Hash& hash, float max_load_factor):
459 hash_node(HASH_NODE_DEFAULT_INIT_BUCKETS_COUNT, hash, max_load_factor)
460 {
461 }
462
463 hash_node(size_type bucket_count, const Hash& hash, float max_load_factor):
464 anode(anode::node_type::HASH_NODE), m_array_hash(bucket_count, hash)
465 {
466 m_array_hash.max_load_factor(max_load_factor);
467 }
468
469 hash_node(array_hash_type&& array_hash) noexcept(std::is_nothrow_move_constructible<array_hash_type>::value):
470 anode(anode::node_type::HASH_NODE), m_array_hash(std::move(array_hash))
471 {
472 }
473
474 hash_node(const hash_node& other) = default;
475
476 hash_node(hash_node&& other) = delete;
477 hash_node& operator=(const hash_node& other) = delete;
478 hash_node& operator=(hash_node&& other) = delete;
479
480
481 array_hash_type& array_hash() noexcept {
482 return m_array_hash;
483 }
484
485 const array_hash_type& array_hash() const noexcept {
486 return m_array_hash;
487 }
488
489 private:
490 array_hash_type m_array_hash;
491 };
492
493
494
495 public:
496 template<bool IsConst, bool IsPrefixIterator>
497 class htrie_hash_iterator {
498 friend class htrie_hash;
499
500 private:
501 using anode_type = typename std::conditional<IsConst, const anode, anode>::type;
502 using trie_node_type = typename std::conditional<IsConst, const trie_node, trie_node>::type;
503 using hash_node_type = typename std::conditional<IsConst, const hash_node, hash_node>::type;
504
505 using array_hash_iterator_type =
506 typename std::conditional<IsConst,
507 typename array_hash_type::const_iterator,
508 typename array_hash_type::iterator>::type;
509
510 public:
511 using iterator_category = std::forward_iterator_tag;
512 using value_type = typename std::conditional<has_value<T>::value, T, void>::type;
513 using difference_type = std::ptrdiff_t;
514 using reference = typename std::conditional<
515 has_value<T>::value,
516 typename std::conditional<IsConst,
517 typename std::add_lvalue_reference<const T>::type,
518 typename std::add_lvalue_reference<T>::type>::type,
519 void>::type;
520 using pointer = typename std::conditional<
521 has_value<T>::value,
522 typename std::conditional<IsConst, const T*, T*>::type,
523 void>::type;
524
525 private:
526 /**
527 * Start reading from start_hash_node->array_hash().begin().
528 */
529 htrie_hash_iterator(hash_node_type& start_hash_node) noexcept:
530 htrie_hash_iterator(start_hash_node, start_hash_node.array_hash().begin())
531 {
532 }
533
534 /**
535 * Start reading from iterator begin in start_hash_node->array_hash().
536 */
537 htrie_hash_iterator(hash_node_type& start_hash_node, array_hash_iterator_type begin) noexcept:
538 m_current_trie_node(start_hash_node.parent()), m_current_hash_node(&start_hash_node),
539 m_array_hash_iterator(begin),
540 m_array_hash_end_iterator(start_hash_node.array_hash().end()),
541 m_read_trie_node_value(false)
542 {
543 tsl_ht_assert(!m_current_hash_node->array_hash().empty());
544 }
545
546 /**
547 * Start reading from the value in start_trie_node. start_trie_node->val_node() should be non-null.
548 */
549 htrie_hash_iterator(trie_node_type& start_trie_node) noexcept:
550 m_current_trie_node(&start_trie_node), m_current_hash_node(nullptr),
551 m_read_trie_node_value(true)
552 {
553 tsl_ht_assert(m_current_trie_node->val_node() != nullptr);
554 }
555
556 template<bool P = IsPrefixIterator, typename std::enable_if<!P>::type* = nullptr>
557 htrie_hash_iterator(trie_node_type* tnode, hash_node_type* hnode,
558 array_hash_iterator_type begin, array_hash_iterator_type end,
559 bool read_trie_node_value) noexcept:
560 m_current_trie_node(tnode), m_current_hash_node(hnode),
561 m_array_hash_iterator(begin), m_array_hash_end_iterator(end),
562 m_read_trie_node_value(read_trie_node_value)
563 {
564 }
565
566 template<bool P = IsPrefixIterator, typename std::enable_if<P>::type* = nullptr>
567 htrie_hash_iterator(trie_node_type* tnode, hash_node_type* hnode,
568 array_hash_iterator_type begin, array_hash_iterator_type end,
569 bool read_trie_node_value, std::basic_string<CharT> prefix_filter) noexcept:
570 m_current_trie_node(tnode), m_current_hash_node(hnode),
571 m_array_hash_iterator(begin), m_array_hash_end_iterator(end),
572 m_read_trie_node_value(read_trie_node_value), m_prefix_filter(std::move(prefix_filter))
573 {
574 }
575
576 public:
577 htrie_hash_iterator() noexcept {
578 }
579
580 // Copy constructor from iterator to const_iterator.
581 template<bool TIsConst = IsConst, bool TIsPrefixIterator = IsPrefixIterator,
582 typename std::enable_if<TIsConst && !TIsPrefixIterator>::type* = nullptr>
583 htrie_hash_iterator(const htrie_hash_iterator<!TIsConst, TIsPrefixIterator>& other) noexcept:
584 m_current_trie_node(other.m_current_trie_node), m_current_hash_node(other.m_current_hash_node),
585 m_array_hash_iterator(other.m_array_hash_iterator),
586 m_array_hash_end_iterator(other.m_array_hash_end_iterator),
587 m_read_trie_node_value(other.m_read_trie_node_value)
588 {
589 }
590
591 // Copy constructor from iterator to const_iterator.
592 template<bool TIsConst = IsConst, bool TIsPrefixIterator = IsPrefixIterator,
593 typename std::enable_if<TIsConst && TIsPrefixIterator>::type* = nullptr>
594 htrie_hash_iterator(const htrie_hash_iterator<!TIsConst, TIsPrefixIterator>& other) noexcept:
595 m_current_trie_node(other.m_current_trie_node), m_current_hash_node(other.m_current_hash_node),
596 m_array_hash_iterator(other.m_array_hash_iterator),
597 m_array_hash_end_iterator(other.m_array_hash_end_iterator),
598 m_read_trie_node_value(other.m_read_trie_node_value), m_prefix_filter(other.m_prefix_filter)
599 {
600 }
601
602 htrie_hash_iterator(const htrie_hash_iterator& other) = default;
603 htrie_hash_iterator(htrie_hash_iterator&& other) = default;
604 htrie_hash_iterator& operator=(const htrie_hash_iterator& other) = default;
605 htrie_hash_iterator& operator=(htrie_hash_iterator&& other) = default;
606
607 void key(std::basic_string<CharT>& key_buffer_out) const {
608 key_buffer_out.clear();
609
610 trie_node_type* tnode = m_current_trie_node;
611 while(tnode != nullptr && tnode->parent() != nullptr) {
612 key_buffer_out.push_back(tnode->child_of_char());
613 tnode = tnode->parent();
614 }
615
616 std::reverse(key_buffer_out.begin(), key_buffer_out.end());
617
618 if(!m_read_trie_node_value) {
619 tsl_ht_assert(m_current_hash_node != nullptr);
620 if(m_current_hash_node->parent() != nullptr) {
621 key_buffer_out.push_back(m_current_hash_node->child_of_char());
622 }
623
624 key_buffer_out.append(m_array_hash_iterator.key(), m_array_hash_iterator.key_size());
625 }
626 }
627
628 std::basic_string<CharT> key() const {
629 std::basic_string<CharT> key_buffer;
630 key(key_buffer);
631
632 return key_buffer;
633 }
634
635 template<class U = T, typename std::enable_if<has_value<U>::value>::type* = nullptr>
636 reference value() const {
637 if(this->m_read_trie_node_value) {
638 tsl_ht_assert(this->m_current_trie_node != nullptr);
639 tsl_ht_assert(this->m_current_trie_node->val_node() != nullptr);
640
641 return this->m_current_trie_node->val_node()->m_value;
642 }
643 else {
644 return this->m_array_hash_iterator.value();
645 }
646 }
647
648 template<class U = T, typename std::enable_if<has_value<U>::value>::type* = nullptr>
649 reference operator*() const {
650 return value();
651 }
652
653 template<class U = T, typename std::enable_if<has_value<U>::value>::type* = nullptr>
654 pointer operator->() const {
655 return std::addressof(value());
656 }
657
658 htrie_hash_iterator& operator++() {
659 if(m_read_trie_node_value) {
660 tsl_ht_assert(m_current_trie_node != nullptr);
661
662 m_read_trie_node_value = false;
663
664 anode_type* child = m_current_trie_node->first_child();
665 if(child != nullptr) {
666 set_most_left_descendant_as_next_node(*child);
667 }
668 else if(m_current_trie_node->parent() != nullptr) {
669 trie_node_type* current_node_child = m_current_trie_node;
670 m_current_trie_node = m_current_trie_node->parent();
671
672 set_next_node_ascending(*current_node_child);
673 }
674 else {
675 set_as_end_iterator();
676 }
677 }
678 else {
679 ++m_array_hash_iterator;
680 if(m_array_hash_iterator != m_array_hash_end_iterator) {
681 filter_prefix();
682 }
683 // End of the road, set the iterator as an end node.
684 else if(m_current_trie_node == nullptr) {
685 set_as_end_iterator();
686 }
687 else {
688 tsl_ht_assert(m_current_hash_node != nullptr);
689 set_next_node_ascending(*m_current_hash_node);
690 }
691 }
692
693
694 return *this;
695 }
696
697 htrie_hash_iterator operator++(int) {
698 htrie_hash_iterator tmp(*this);
699 ++*this;
700
701 return tmp;
702 }
703
704 friend bool operator==(const htrie_hash_iterator& lhs, const htrie_hash_iterator& rhs) {
705 if(lhs.m_current_trie_node != rhs.m_current_trie_node ||
706 lhs.m_read_trie_node_value != rhs.m_read_trie_node_value)
707 {
708 return false;
709 }
710 else if(lhs.m_read_trie_node_value) {
711 return true;
712 }
713 else {
714 if(lhs.m_current_hash_node != rhs.m_current_hash_node) {
715 return false;
716 }
717 else if(lhs.m_current_hash_node == nullptr) {
718 return true;
719 }
720 else {
721 return lhs.m_array_hash_iterator == rhs.m_array_hash_iterator &&
722 lhs.m_array_hash_end_iterator == rhs.m_array_hash_end_iterator;
723 }
724 }
725 }
726
727 friend bool operator!=(const htrie_hash_iterator& lhs, const htrie_hash_iterator& rhs) {
728 return !(lhs == rhs);
729 }
730
731 private:
732 void hash_node_prefix(std::basic_string<CharT>& key_buffer_out) const {
733 tsl_ht_assert(!m_read_trie_node_value);
734 key_buffer_out.clear();
735
736 trie_node_type* tnode = m_current_trie_node;
737 while(tnode != nullptr && tnode->parent() != nullptr) {
738 key_buffer_out.push_back(tnode->child_of_char());
739 tnode = tnode->parent();
740 }
741
742 std::reverse(key_buffer_out.begin(), key_buffer_out.end());
743
744 tsl_ht_assert(m_current_hash_node != nullptr);
745 if(m_current_hash_node->parent() != nullptr) {
746 key_buffer_out.push_back(m_current_hash_node->child_of_char());
747 }
748 }
749
750 template<bool P = IsPrefixIterator, typename std::enable_if<!P>::type* = nullptr>
751 void filter_prefix() {
752 }
753
754 template<bool P = IsPrefixIterator, typename std::enable_if<P>::type* = nullptr>
755 void filter_prefix() {
756 tsl_ht_assert(m_array_hash_iterator != m_array_hash_end_iterator);
757 tsl_ht_assert(!m_read_trie_node_value && m_current_hash_node != nullptr);
758
759 if(m_prefix_filter.empty()) {
760 return;
761 }
762
763 while((m_prefix_filter.size() > m_array_hash_iterator.key_size() ||
764 m_prefix_filter.compare(0, m_prefix_filter.size(),
765 m_array_hash_iterator.key(), m_prefix_filter.size()) != 0))
766 {
767 ++m_array_hash_iterator;
768 if(m_array_hash_iterator == m_array_hash_end_iterator) {
769 if(m_current_trie_node == nullptr) {
770 set_as_end_iterator();
771 }
772 else {
773 tsl_ht_assert(m_current_hash_node != nullptr);
774 set_next_node_ascending(*m_current_hash_node);
775 }
776
777 return;
778 }
779 }
780 }
781
782 /**
783 * Go back up in the tree to get the current_trie_node_child sibling.
784 * If none, try to go back up more in the tree to check the siblings of the ancestors.
785 */
786 void set_next_node_ascending(anode_type& current_trie_node_child) {
787 tsl_ht_assert(m_current_trie_node != nullptr);
788 tsl_ht_assert(current_trie_node_child.parent() == m_current_trie_node);
789
790 anode_type* next_node = m_current_trie_node->next_child(current_trie_node_child);
791 while(next_node == nullptr && m_current_trie_node->parent() != nullptr) {
792 anode_type* current_child = m_current_trie_node;
793 m_current_trie_node = m_current_trie_node->parent();
794 next_node = m_current_trie_node->next_child(*current_child);
795 }
796
797 // End of the road, set the iterator as an end node.
798 if(next_node == nullptr) {
799 set_as_end_iterator();
800 }
801 else {
802 set_most_left_descendant_as_next_node(*next_node);
803 }
804 }
805
806 void set_most_left_descendant_as_next_node(anode_type& search_start) {
807 if(search_start.is_hash_node()) {
808 set_current_hash_node(search_start.as_hash_node());
809 }
810 else {
811 m_current_trie_node = &search_start.as_trie_node().most_left_descendant_value_trie_node();
812 if(m_current_trie_node->val_node() != nullptr) {
813 m_read_trie_node_value = true;
814 }
815 else {
816 anode_type* first_child = m_current_trie_node->first_child();
817 // a trie_node must either have a value_node or at least one child.
818 tsl_ht_assert(first_child != nullptr);
819
820 set_current_hash_node(first_child->as_hash_node());
821 }
822 }
823 }
824
825 void set_current_hash_node(hash_node_type& hnode) {
826 tsl_ht_assert(!hnode.array_hash().empty());
827
828 m_current_hash_node = &hnode;
829 m_array_hash_iterator = m_current_hash_node->array_hash().begin();
830 m_array_hash_end_iterator = m_current_hash_node->array_hash().end();
831 }
832
833 void set_as_end_iterator() {
834 m_current_trie_node = nullptr;
835 m_current_hash_node = nullptr;
836 m_read_trie_node_value = false;
837 }
838
839 void skip_hash_node() {
840 tsl_ht_assert(!m_read_trie_node_value && m_current_hash_node != nullptr);
841 if(m_current_trie_node == nullptr) {
842 set_as_end_iterator();
843 }
844 else {
845 tsl_ht_assert(m_current_hash_node != nullptr);
846 set_next_node_ascending(*m_current_hash_node);
847 }
848 }
849
850 private:
851 trie_node_type* m_current_trie_node;
852 hash_node_type* m_current_hash_node;
853
854 array_hash_iterator_type m_array_hash_iterator;
855 array_hash_iterator_type m_array_hash_end_iterator;
856
857 bool m_read_trie_node_value;
858 // TODO can't have void if !IsPrefixIterator, use inheritance
859 typename std::conditional<IsPrefixIterator, std::basic_string<CharT>, bool>::type m_prefix_filter;
860 };
861
862
863
864 public:
865 htrie_hash(const Hash& hash, float max_load_factor, size_type burst_threshold):
866 m_root(nullptr), m_nb_elements(0),
867 m_hash(hash), m_max_load_factor(max_load_factor)
868 {
869 this->burst_threshold(burst_threshold);
870 }
871
872 htrie_hash(const htrie_hash& other): m_root(nullptr), m_nb_elements(other.m_nb_elements),
873 m_hash(other.m_hash), m_max_load_factor(other.m_max_load_factor),
874 m_burst_threshold(other.m_burst_threshold)
875 {
876 if(other.m_root != nullptr) {
877 if(other.m_root->is_hash_node()) {
878 m_root = make_unique<hash_node>(other.m_root->as_hash_node());
879 }
880 else {
881 m_root = make_unique<trie_node>(other.m_root->as_trie_node());
882 }
883 }
884 }
885
886 htrie_hash(htrie_hash&& other) noexcept(std::is_nothrow_move_constructible<Hash>::value)
887 : m_root(std::move(other.m_root)),
888 m_nb_elements(other.m_nb_elements),
889 m_hash(std::move(other.m_hash)),
890 m_max_load_factor(other.m_max_load_factor),
891 m_burst_threshold(other.m_burst_threshold)
892 {
893 other.clear();
894 }
895
896 htrie_hash& operator=(const htrie_hash& other) {
897 if(&other != this) {
898 std::unique_ptr<anode> new_root = nullptr;
899 if(other.m_root != nullptr) {
900 if(other.m_root->is_hash_node()) {
901 new_root = make_unique<hash_node>(other.m_root->as_hash_node());
902 }
903 else {
904 new_root = make_unique<trie_node>(other.m_root->as_trie_node());
905 }
906 }
907
908 m_hash = other.m_hash;
909 m_root = std::move(new_root);
910 m_nb_elements = other.m_nb_elements;
911 m_max_load_factor = other.m_max_load_factor;
912 m_burst_threshold = other.m_burst_threshold;
913 }
914
915 return *this;
916 }
917
918 htrie_hash& operator=(htrie_hash&& other) {
919 other.swap(*this);
920 other.clear();
921
922 return *this;
923 }
924
925 /*
926 * Iterators
927 */
928 iterator begin() noexcept {
929 return mutable_iterator(cbegin());
930 }
931
932 const_iterator begin() const noexcept {
933 return cbegin();
934 }
935
936 const_iterator cbegin() const noexcept {
937 if(empty()) {
938 return cend();
939 }
940
941 return cbegin<const_iterator>(*m_root);
942 }
943
944 iterator end() noexcept {
945 iterator it;
946 it.set_as_end_iterator();
947
948 return it;
949 }
950
951 const_iterator end() const noexcept {
952 return cend();
953 }
954
955 const_iterator cend() const noexcept {
956 const_iterator it;
957 it.set_as_end_iterator();
958
959 return it;
960 }
961
962
963 /*
964 * Capacity
965 */
966 bool empty() const noexcept {
967 return m_nb_elements == 0;
968 }
969
970 size_type size() const noexcept {
971 return m_nb_elements;
972 }
973
974 size_type max_size() const noexcept {
975 return std::numeric_limits<size_type>::max();
976 }
977
978 size_type max_key_size() const noexcept {
979 return array_hash_type::MAX_KEY_SIZE;
980 }
981
982 void shrink_to_fit() {
983 auto first = begin();
984 auto last = end();
985
986 while(first != last) {
987 if(first.m_read_trie_node_value) {
988 ++first;
989 }
990 else {
991 /*
992 * shrink_to_fit on array_hash will invalidate the iterators of array_hash.
993 * Save pointer to array_hash, skip the array_hash_node and then call
994 * shrink_to_fit on the saved pointer.
995 */
996 hash_node* hnode = first.m_current_hash_node;
997 first.skip_hash_node();
998
999 tsl_ht_assert(hnode != nullptr);
1000 hnode->array_hash().shrink_to_fit();
1001 }
1002 }
1003 }
1004
1005
1006 /*
1007 * Modifiers
1008 */
1009 void clear() noexcept {
1010 m_root.reset(nullptr);
1011 m_nb_elements = 0;
1012 }
1013
1014 template<class... ValueArgs>
1015 std::pair<iterator, bool> insert(const CharT* key, size_type key_size, ValueArgs&&... value_args) {
1016 if(key_size > max_key_size()) {
1017 THROW(std::length_error, "Key is too long.");
1018 }
1019
1020 if(m_root == nullptr) {
1021 m_root = make_unique<hash_node>(m_hash, m_max_load_factor);
1022 }
1023
1024 return insert_impl(*m_root, key, key_size, std::forward<ValueArgs>(value_args)...);
1025 }
1026
1027 iterator erase(const_iterator pos) {
1028 return erase(mutable_iterator(pos));
1029 }
1030
1031 iterator erase(const_iterator first, const_iterator last) {
1032 // TODO Optimize, could avoid the call to std::distance
1033 const std::size_t nb_to_erase = std::size_t(std::distance(first, last));
1034 auto to_delete = mutable_iterator(first);
1035 for(std::size_t i = 0; i < nb_to_erase; i++) {
1036 to_delete = erase(to_delete);
1037 }
1038
1039 return to_delete;
1040 }
1041
1042 size_type erase(const CharT* key, size_type key_size) {
1043 auto it = find(key, key_size);
1044 if(it != end()) {
1045 erase(it);
1046 return 1;
1047 }
1048 else {
1049 return 0;
1050 }
1051
1052 }
1053
1054 size_type erase_prefix(const CharT* prefix, size_type prefix_size) {
1055 if(m_root == nullptr) {
1056 return 0;
1057 }
1058
1059 anode* current_node = m_root.get();
1060 for(size_type iprefix = 0; iprefix < prefix_size; iprefix++) {
1061 if(current_node->is_trie_node()) {
1062 trie_node* tnode = &current_node->as_trie_node();
1063
1064 if(tnode->child(prefix[iprefix]) == nullptr) {
1065 return 0;
1066 }
1067 else {
1068 current_node = tnode->child(prefix[iprefix]).get();
1069 }
1070 }
1071 else {
1072 hash_node& hnode = current_node->as_hash_node();
1073 return erase_prefix_hash_node(hnode, prefix + iprefix, prefix_size - iprefix);
1074 }
1075 }
1076
1077
1078 if(current_node->is_trie_node()) {
1079 trie_node* parent = current_node->parent();
1080
1081 if(parent != nullptr) {
1082 const size_type nb_erased = size_descendants(current_node->as_trie_node());
1083
1084 parent->set_child(current_node->child_of_char(), nullptr);
1085 m_nb_elements -= nb_erased;
1086
1087 if(parent->empty()) {
1088 clear_empty_nodes(*parent);
1089 }
1090
1091 return nb_erased;
1092 }
1093 else {
1094 const size_type nb_erased = m_nb_elements;
1095 m_root.reset(nullptr);
1096 m_nb_elements = 0;
1097
1098 return nb_erased;
1099 }
1100 }
1101 else {
1102 const size_type nb_erased = current_node->as_hash_node().array_hash().size();
1103
1104 current_node->as_hash_node().array_hash().clear();
1105 m_nb_elements -= nb_erased;
1106
1107 clear_empty_nodes(current_node->as_hash_node());
1108
1109 return nb_erased;
1110 }
1111 }
1112
1113 void swap(htrie_hash& other) {
1114 using std::swap;
1115
1116 swap(m_hash, other.m_hash);
1117 swap(m_root, other.m_root);
1118 swap(m_nb_elements, other.m_nb_elements);
1119 swap(m_max_load_factor, other.m_max_load_factor);
1120 swap(m_burst_threshold, other.m_burst_threshold);
1121 }
1122
1123 /*
1124 * Lookup
1125 */
1126 template<class U = T, typename std::enable_if<has_value<U>::value>::type* = nullptr>
1127 U& at(const CharT* key, size_type key_size) {
1128 return const_cast<U&>(static_cast<const htrie_hash*>(this)->at(key, key_size));
1129 }
1130
1131 template<class U = T, typename std::enable_if<has_value<U>::value>::type* = nullptr>
1132 const U& at(const CharT* key, size_type key_size) const {
1133 auto it_find = find(key, key_size);
1134 if(it_find != cend()) {
1135 return it_find.value();
1136 }
1137 else {
1138 THROW(std::out_of_range, "Couldn't find key.");
1139 }
1140 }
1141
1142 //TODO optimize
1143 template<class U = T, typename std::enable_if<has_value<U>::value>::type* = nullptr>
1144 U& access_operator(const CharT* key, size_type key_size) {
1145 auto it_find = find(key, key_size);
1146 if(it_find != cend()) {
1147 return it_find.value();
1148 }
1149 else {
1150 return insert(key, key_size, U{}).first.value();
1151 }
1152 }
1153
1154 size_type count(const CharT* key, size_type key_size) const {
1155 if(find(key, key_size) != cend()) {
1156 return 1;
1157 }
1158 else {
1159 return 0;
1160 }
1161 }
1162
1163 iterator find(const CharT* key, size_type key_size) {
1164 if(m_root == nullptr) {
1165 return end();
1166 }
1167
1168 return find_impl(*m_root, key, key_size);
1169 }
1170
1171 const_iterator find(const CharT* key, size_type key_size) const {
1172 if(m_root == nullptr) {
1173 return cend();
1174 }
1175
1176 return find_impl(*m_root, key, key_size);
1177 }
1178
1179 std::pair<iterator, iterator> equal_range(const CharT* key, size_type key_size) {
1180 iterator it = find(key, key_size);
1181 return std::make_pair(it, (it == end())?it:std::next(it));
1182 }
1183
1184 std::pair<const_iterator, const_iterator> equal_range(const CharT* key, size_type key_size) const {
1185 const_iterator it = find(key, key_size);
1186 return std::make_pair(it, (it == cend())?it:std::next(it));
1187 }
1188
1189 std::pair<prefix_iterator, prefix_iterator> equal_prefix_range(const CharT* prefix, size_type prefix_size) {
1190 if(m_root == nullptr) {
1191 return std::make_pair(prefix_end(), prefix_end());
1192 }
1193
1194 return equal_prefix_range_impl(*m_root, prefix, prefix_size);
1195 }
1196
1197 std::pair<const_prefix_iterator, const_prefix_iterator> equal_prefix_range(const CharT* prefix,
1198 size_type prefix_size) const
1199 {
1200 if(m_root == nullptr) {
1201 return std::make_pair(prefix_cend(), prefix_cend());
1202 }
1203
1204 return equal_prefix_range_impl(*m_root, prefix, prefix_size);
1205 }
1206
1207 iterator longest_prefix(const CharT* key, size_type key_size) {
1208 if(m_root == nullptr) {
1209 return end();
1210 }
1211
1212 return longest_prefix_impl(*m_root, key, key_size);
1213 }
1214
1215 const_iterator longest_prefix(const CharT* key, size_type key_size) const {
1216 if(m_root == nullptr) {
1217 return cend();
1218 }
1219
1220 return longest_prefix_impl(*m_root, key, key_size);
1221 }
1222
1223
1224 /*
1225 * Hash policy
1226 */
1227 float max_load_factor() const {
1228 return m_max_load_factor;
1229 }
1230
1231 void max_load_factor(float ml) {
1232 m_max_load_factor = ml;
1233 }
1234
1235 /*
1236 * Burst policy
1237 */
1238 size_type burst_threshold() const {
1239 return m_burst_threshold;
1240 }
1241
1242 void burst_threshold(size_type threshold) {
1243 const size_type min_burst_threshold = MIN_BURST_THRESHOLD;
1244 m_burst_threshold = std::max(min_burst_threshold, threshold);
1245 }
1246
1247 /*
1248 * Observers
1249 */
1250 hasher hash_function() const {
1251 return m_hash;
1252 }
1253
1254 /*
1255 * Other
1256 */
1257 template<class Serializer>
1258 void serialize(Serializer& serializer) const {
1259 serialize_impl(serializer);
1260 }
1261
1262 template<class Deserializer>
1263 void deserialize(Deserializer& deserializer, bool hash_compatible) {
1264 deserialize_impl(deserializer, hash_compatible);
1265 }
1266
1267 private:
1268 /**
1269 * Get the begin iterator by searching for the most left descendant node starting at search_start_node.
1270 */
1271 template<typename Iterator>
1272 Iterator cbegin(const anode& search_start_node) const noexcept {
1273 if(search_start_node.is_hash_node()) {
1274 return Iterator(search_start_node.as_hash_node());
1275 }
1276
1277 const trie_node& tnode = search_start_node.as_trie_node().most_left_descendant_value_trie_node();
1278 if(tnode.val_node() != nullptr) {
1279 return Iterator(tnode);
1280 }
1281 else {
1282 const anode* first_child = tnode.first_child();
1283 tsl_ht_assert(first_child != nullptr);
1284
1285 return Iterator(first_child->as_hash_node());
1286 }
1287 }
1288
1289 /**
1290 * Get an iterator to the node that come just after the last descendant of search_start_node.
1291 */
1292 template<typename Iterator>
1293 Iterator cend(const anode& search_start_node) const noexcept {
1294 if(search_start_node.parent() == nullptr) {
1295 Iterator it;
1296 it.set_as_end_iterator();
1297
1298 return it;
1299 }
1300
1301 const trie_node* current_trie_node = search_start_node.parent();
1302 const anode* next_node = current_trie_node->next_child(search_start_node);
1303
1304 while(next_node == nullptr && current_trie_node->parent() != nullptr) {
1305 const anode* current_child = current_trie_node;
1306 current_trie_node = current_trie_node->parent();
1307 next_node = current_trie_node->next_child(*current_child);
1308 }
1309
1310 if(next_node == nullptr) {
1311 Iterator it;
1312 it.set_as_end_iterator();
1313
1314 return it;
1315 }
1316 else {
1317 return cbegin<Iterator>(*next_node);
1318 }
1319 }
1320
1321 prefix_iterator prefix_end() noexcept {
1322 prefix_iterator it;
1323 it.set_as_end_iterator();
1324
1325 return it;
1326 }
1327
1328 const_prefix_iterator prefix_cend() const noexcept {
1329 const_prefix_iterator it;
1330 it.set_as_end_iterator();
1331
1332 return it;
1333 }
1334
1335 size_type size_descendants(const anode& start_node) const {
1336 auto first = cbegin<const_iterator>(start_node);
1337 auto last = cend<const_iterator>(start_node);
1338
1339 size_type nb_elements = 0;
1340 while(first != last) {
1341 if(first.m_read_trie_node_value) {
1342 nb_elements++;
1343 ++first;
1344 }
1345 else {
1346 nb_elements += first.m_current_hash_node->array_hash().size();
1347 first.skip_hash_node();
1348 }
1349 }
1350
1351 return nb_elements;
1352 }
1353
1354 template<class... ValueArgs>
1355 std::pair<iterator, bool> insert_impl(anode& search_start_node,
1356 const CharT* key, size_type key_size, ValueArgs&&... value_args)
1357 {
1358 anode* current_node = &search_start_node;
1359
1360 for(size_type ikey = 0; ikey < key_size; ikey++) {
1361 if(current_node->is_trie_node()) {
1362 trie_node& tnode = current_node->as_trie_node();
1363
1364 if(tnode.child(key[ikey]) != nullptr) {
1365 current_node = tnode.child(key[ikey]).get();
1366 }
1367 else {
1368 auto hnode = make_unique<hash_node>(m_hash, m_max_load_factor);
1369 auto insert_it = hnode->array_hash().emplace_ks(key + ikey + 1, key_size - ikey - 1,
1370 std::forward<ValueArgs>(value_args)...);
1371
1372 tnode.set_child(key[ikey], std::move(hnode));
1373 m_nb_elements++;
1374
1375
1376 return std::make_pair(iterator(tnode.child(key[ikey])->as_hash_node(),
1377 insert_it.first), true);
1378 }
1379 }
1380 else {
1381 return insert_in_hash_node(current_node->as_hash_node(),
1382 key + ikey, key_size - ikey, std::forward<ValueArgs>(value_args)...);
1383 }
1384 }
1385
1386
1387 if(current_node->is_trie_node()) {
1388 trie_node& tnode = current_node->as_trie_node();
1389 if(tnode.val_node() != nullptr) {
1390 return std::make_pair(iterator(tnode), false);
1391 }
1392 else {
1393 tnode.val_node() = make_unique<value_node>(std::forward<ValueArgs>(value_args)...);
1394 m_nb_elements++;
1395
1396 return std::make_pair(iterator(tnode), true);
1397 }
1398 }
1399 else {
1400 return insert_in_hash_node(current_node->as_hash_node(),
1401 "", 0, std::forward<ValueArgs>(value_args)...);
1402 }
1403 }
1404
1405 template<class... ValueArgs>
1406 std::pair<iterator, bool> insert_in_hash_node(hash_node& hnode,
1407 const CharT* key, size_type key_size, ValueArgs&&... value_args)
1408 {
1409 if(need_burst(hnode)) {
1410 std::unique_ptr<trie_node> new_node = burst(hnode);
1411 if(hnode.parent() == nullptr) {
1412 tsl_ht_assert(m_root.get() == &hnode);
1413
1414 m_root = std::move(new_node);
1415 return insert_impl(*m_root, key, key_size, std::forward<ValueArgs>(value_args)...);
1416 }
1417 else {
1418 trie_node* parent = hnode.parent();
1419 const CharT child_of_char = hnode.child_of_char();
1420
1421 parent->set_child(child_of_char, std::move(new_node));
1422
1423 return insert_impl(*parent->child(child_of_char),
1424 key, key_size, std::forward<ValueArgs>(value_args)...);
1425 }
1426 }
1427 else {
1428 auto it_insert = hnode.array_hash().emplace_ks(key, key_size,
1429 std::forward<ValueArgs>(value_args)...);
1430 if(it_insert.second) {
1431 m_nb_elements++;
1432 }
1433
1434 return std::make_pair(iterator(hnode, it_insert.first), it_insert.second);
1435 }
1436 }
1437
1438
1439 iterator erase(iterator pos) {
1440 iterator next_pos = std::next(pos);
1441
1442 if(pos.m_read_trie_node_value) {
1443 tsl_ht_assert(pos.m_current_trie_node != nullptr && pos.m_current_trie_node->val_node() != nullptr);
1444
1445 pos.m_current_trie_node->val_node().reset(nullptr);
1446 m_nb_elements--;
1447
1448 if(pos.m_current_trie_node->empty()) {
1449 clear_empty_nodes(*pos.m_current_trie_node);
1450 }
1451
1452 return next_pos;
1453 }
1454 else {
1455 tsl_ht_assert(pos.m_current_hash_node != nullptr);
1456 auto next_array_hash_it = pos.m_current_hash_node->array_hash().erase(pos.m_array_hash_iterator);
1457 m_nb_elements--;
1458
1459 if(next_array_hash_it != pos.m_current_hash_node->array_hash().end()) {
1460 // The erase on array_hash invalidated the next_pos iterator, return the right one.
1461 return iterator(*pos.m_current_hash_node, next_array_hash_it);
1462 }
1463 else {
1464 if(pos.m_current_hash_node->array_hash().empty()) {
1465 clear_empty_nodes(*pos.m_current_hash_node);
1466 }
1467
1468 return next_pos;
1469 }
1470 }
1471 }
1472
1473 /**
1474 * Clear all the empty nodes from the tree starting from empty_node (empty for a hash_node means that
1475 * the array hash is empty, for a trie_node it means the node doesn't have any child or value_node
1476 * associated to it).
1477 */
1478 void clear_empty_nodes(anode& empty_node) noexcept {
1479 tsl_ht_assert(!empty_node.is_trie_node() ||
1480 (empty_node.as_trie_node().empty() && empty_node.as_trie_node().val_node() == nullptr));
1481 tsl_ht_assert(!empty_node.is_hash_node() || empty_node.as_hash_node().array_hash().empty());
1482
1483
1484 trie_node* parent = empty_node.parent();
1485 if(parent == nullptr) {
1486 tsl_ht_assert(m_root.get() == &empty_node);
1487 tsl_ht_assert(m_nb_elements == 0);
1488 m_root.reset(nullptr);
1489 }
1490 else if(parent->val_node() != nullptr || parent->nb_children() > 1) {
1491 parent->child(empty_node.child_of_char()).reset(nullptr);
1492 }
1493 else if(parent->parent() == nullptr) {
1494 tsl_ht_assert(m_root.get() == empty_node.parent());
1495 tsl_ht_assert(m_nb_elements == 0);
1496 m_root.reset(nullptr);
1497 }
1498 else {
1499 /**
1500 * Parent is empty if we remove its empty_node child.
1501 * Put empty_node as new child of the grand parent instead of parent (move hnode up,
1502 * and delete the parent). And recurse.
1503 *
1504 * We can't just set grand_parent->child(parent->child_of_char()) to nullptr as
1505 * the grand_parent may also become empty. We don't want empty trie_node with no value_node
1506 * in the tree.
1507 */
1508 trie_node* grand_parent = parent->parent();
1509 grand_parent->set_child(parent->child_of_char(),
1510 std::move(parent->child(empty_node.child_of_char())));
1511
1512
1513 clear_empty_nodes(empty_node);
1514 }
1515 }
1516
1517
1518
1519
1520 iterator find_impl(const anode& search_start_node, const CharT* key, size_type key_size) {
1521 return mutable_iterator(static_cast<const htrie_hash*>(this)->find_impl(search_start_node, key, key_size));
1522 }
1523
1524 const_iterator find_impl(const anode& search_start_node, const CharT* key, size_type key_size) const {
1525 const anode* current_node = &search_start_node;
1526
1527 for(size_type ikey = 0; ikey < key_size; ikey++) {
1528 if(current_node->is_trie_node()) {
1529 const trie_node* tnode = &current_node->as_trie_node();
1530
1531 if(tnode->child(key[ikey]) == nullptr) {
1532 return cend();
1533 }
1534 else {
1535 current_node = tnode->child(key[ikey]).get();
1536 }
1537 }
1538 else {
1539 return find_in_hash_node(current_node->as_hash_node(),
1540 key + ikey, key_size - ikey);
1541 }
1542 }
1543
1544
1545 if(current_node->is_trie_node()) {
1546 const trie_node& tnode = current_node->as_trie_node();
1547 return (tnode.val_node() != nullptr)?const_iterator(tnode):cend();
1548 }
1549 else {
1550 return find_in_hash_node(current_node->as_hash_node(), "", 0);
1551 }
1552 }
1553
1554 const_iterator find_in_hash_node(const hash_node& hnode,
1555 const CharT* key, size_type key_size) const
1556 {
1557 auto it = hnode.array_hash().find_ks(key, key_size);
1558 if(it != hnode.array_hash().end()) {
1559 return const_iterator(hnode, it);
1560 }
1561 else {
1562 return cend();
1563 }
1564 }
1565
1566
1567 iterator longest_prefix_impl(const anode& search_start_node,
1568 const CharT* value, size_type value_size)
1569 {
1570 return mutable_iterator(static_cast<const htrie_hash*>(this)->longest_prefix_impl(search_start_node,
1571 value, value_size));
1572 }
1573
1574 const_iterator longest_prefix_impl(const anode& search_start_node,
1575 const CharT* value, size_type value_size) const
1576 {
1577 const anode* current_node = &search_start_node;
1578 const_iterator longest_found_prefix = cend();
1579
1580 for(size_type ivalue = 0; ivalue < value_size; ivalue++) {
1581 if(current_node->is_trie_node()) {
1582 const trie_node& tnode = current_node->as_trie_node();
1583
1584 if(tnode.val_node() != nullptr) {
1585 longest_found_prefix = const_iterator(tnode);
1586 }
1587
1588 if(tnode.child(value[ivalue]) == nullptr) {
1589 return longest_found_prefix;
1590 }
1591 else {
1592 current_node = tnode.child(value[ivalue]).get();
1593 }
1594 }
1595 else {
1596 const hash_node& hnode = current_node->as_hash_node();
1597
1598 /**
1599 * Test the presence in the hash node of each substring from the
1600 * remaining [ivalue, value_size) string starting from the longest.
1601 * Also test the empty string.
1602 */
1603 for(std::size_t i = ivalue; i <= value_size; i++) {
1604 auto it = hnode.array_hash().find_ks(value + ivalue, (value_size - i));
1605 if(it != hnode.array_hash().end()) {
1606 return const_iterator(hnode, it);
1607 }
1608 }
1609
1610 return longest_found_prefix;
1611 }
1612 }
1613
1614 if(current_node->is_trie_node()) {
1615 const trie_node& tnode = current_node->as_trie_node();
1616
1617 if(tnode.val_node() != nullptr) {
1618 longest_found_prefix = const_iterator(tnode);
1619 }
1620 }
1621 else {
1622 const hash_node& hnode = current_node->as_hash_node();
1623
1624 auto it = hnode.array_hash().find_ks("", 0);
1625 if(it != hnode.array_hash().end()) {
1626 longest_found_prefix = const_iterator(hnode, it);
1627 }
1628 }
1629
1630 return longest_found_prefix;
1631 }
1632
1633
1634 std::pair<prefix_iterator, prefix_iterator> equal_prefix_range_impl(
1635 anode& search_start_node,
1636 const CharT* prefix, size_type prefix_size)
1637 {
1638 auto range = static_cast<const htrie_hash*>(this)->equal_prefix_range_impl(search_start_node,
1639 prefix, prefix_size);
1640 return std::make_pair(mutable_iterator(range.first), mutable_iterator(range.second));
1641 }
1642
1643 std::pair<const_prefix_iterator, const_prefix_iterator> equal_prefix_range_impl(
1644 const anode& search_start_node,
1645 const CharT* prefix, size_type prefix_size) const
1646 {
1647 const anode* current_node = &search_start_node;
1648
1649 for(size_type iprefix = 0; iprefix < prefix_size; iprefix++) {
1650 if(current_node->is_trie_node()) {
1651 const trie_node* tnode = &current_node->as_trie_node();
1652
1653 if(tnode->child(prefix[iprefix]) == nullptr) {
1654 return std::make_pair(prefix_cend(), prefix_cend());
1655 }
1656 else {
1657 current_node = tnode->child(prefix[iprefix]).get();
1658 }
1659 }
1660 else {
1661 const hash_node& hnode = current_node->as_hash_node();
1662 const_prefix_iterator begin(hnode.parent(), &hnode,
1663 hnode.array_hash().begin(), hnode.array_hash().end(),
1664 false, std::basic_string<CharT>(prefix + iprefix, prefix_size - iprefix));
1665 begin.filter_prefix();
1666
1667 const_prefix_iterator end = cend<const_prefix_iterator>(*current_node);
1668
1669 return std::make_pair(begin, end);
1670 }
1671 }
1672
1673
1674 const_prefix_iterator begin = cbegin<const_prefix_iterator>(*current_node);
1675 const_prefix_iterator end = cend<const_prefix_iterator>(*current_node);
1676
1677 return std::make_pair(begin, end);
1678 }
1679
1680 size_type erase_prefix_hash_node(hash_node& hnode, const CharT* prefix, size_type prefix_size) {
1681 size_type nb_erased = 0;
1682
1683 auto it = hnode.array_hash().begin();
1684 while(it != hnode.array_hash().end()) {
1685 if(it.key_size() >= prefix_size &&
1686 std::memcmp(prefix, it.key(), prefix_size * sizeof(CharT)) == 0)
1687 {
1688 it = hnode.array_hash().erase(it);
1689 ++nb_erased;
1690 --m_nb_elements;
1691 }
1692 else {
1693 ++it;
1694 }
1695 }
1696
1697 return nb_erased;
1698 }
1699
1700
1701 /*
1702 * Burst
1703 */
1704 bool need_burst(hash_node& node) const {
1705 return node.array_hash().size() >= m_burst_threshold;
1706 }
1707
1708
1709 /**
1710 * Burst the node and use the copy constructor instead of move constructor for the values.
1711 * Also use this method for trivial value types like int, int*, ... as it requires
1712 * less book-keeping (thus faster) than the burst using move constructors.
1713 */
1714 template<class U = T, typename std::enable_if<has_value<U>::value &&
1715 std::is_copy_constructible<U>::value &&
1716 (!std::is_nothrow_move_constructible<U>::value ||
1717 !std::is_nothrow_move_assignable<U>::value ||
1718 std::is_arithmetic<U>::value ||
1719 std::is_pointer<U>::value)>::type* = nullptr>
1720 std::unique_ptr<trie_node> burst(hash_node& node) {
1721 const std::array<size_type, ALPHABET_SIZE> first_char_count =
1722 get_first_char_count(node.array_hash().cbegin(),
1723 node.array_hash().cend());
1724
1725
1726 auto new_node = make_unique<trie_node>();
1727 for(auto it = node.array_hash().cbegin(); it != node.array_hash().cend(); ++it) {
1728 if(it.key_size() == 0) {
1729 new_node->val_node() = make_unique<value_node>(it.value());
1730 }
1731 else {
1732 hash_node& hnode = get_hash_node_for_char(first_char_count, *new_node, it.key()[0]);
1733 hnode.array_hash().insert_ks(it.key() + 1, it.key_size() - 1, it.value());
1734 }
1735 }
1736
1737
1738 tsl_ht_assert(new_node->val_node() != nullptr || !new_node->empty());
1739 return new_node;
1740 }
1741
1742 /**
1743 * Burst the node and use the move constructor and move assign operator
1744 */
1745 template<class U = T, typename std::enable_if<has_value<U>::value &&
1746 std::is_nothrow_move_constructible<U>::value &&
1747 std::is_nothrow_move_assignable<U>::value &&
1748 !std::is_arithmetic<U>::value &&
1749 !std::is_pointer<U>::value>::type* = nullptr>
1750 std::unique_ptr<trie_node> burst(hash_node& node) {
1751 /**
1752 * We burst the node->array_hash() into multiple arrays hash. While doing so, we move each value in
1753 * the node->array_hash() into the new arrays hash. After each move, we save a pointer to where the value
1754 * has been moved. In case of exception, we rollback these values into the original node->array_hash().
1755 */
1756 std::vector<T*> moved_values_rollback;
1757 moved_values_rollback.reserve(node.array_hash().size());
1758
1759 const std::array<size_type, ALPHABET_SIZE> first_char_count =
1760 get_first_char_count(node.array_hash().cbegin(), node.array_hash().cend());
1761
1762
1763 auto new_node = make_unique<trie_node>();
1764 for(auto it = node.array_hash().begin(); it != node.array_hash().end(); ++it) {
1765 if(it.key_size() == 0) {
1766 new_node->val_node() = make_unique<value_node>(std::move(it.value()));
1767 moved_values_rollback.push_back(std::addressof(new_node->val_node()->m_value));
1768 }
1769 else {
1770 hash_node& hnode = get_hash_node_for_char(first_char_count, *new_node, it.key()[0]);
1771 auto it_insert = hnode.array_hash().insert_ks(it.key() + 1, it.key_size() - 1,
1772 std::move(it.value()));
1773 moved_values_rollback.push_back(std::addressof(it_insert.first.value()));
1774 }
1775 }
1776
1777
1778 tsl_ht_assert(new_node->val_node() != nullptr || !new_node->empty());
1779 return new_node;
1780 }
1781
1782 template<class U = T, typename std::enable_if<!has_value<U>::value>::type* = nullptr>
1783 std::unique_ptr<trie_node> burst(hash_node& node) {
1784 const std::array<size_type, ALPHABET_SIZE> first_char_count =
1785 get_first_char_count(node.array_hash().begin(), node.array_hash().end());
1786
1787
1788 auto new_node = make_unique<trie_node>();
1789 for(auto it = node.array_hash().cbegin(); it != node.array_hash().cend(); ++it) {
1790 if(it.key_size() == 0) {
1791 new_node->val_node() = make_unique<value_node>();
1792 }
1793 else {
1794 hash_node& hnode = get_hash_node_for_char(first_char_count, *new_node, it.key()[0]);
1795 hnode.array_hash().insert_ks(it.key() + 1, it.key_size() - 1);
1796 }
1797 }
1798
1799
1800 tsl_ht_assert(new_node->val_node() != nullptr || !new_node->empty());
1801 return new_node;
1802 }
1803
1804 std::array<size_type, ALPHABET_SIZE> get_first_char_count(typename array_hash_type::const_iterator begin,
1805 typename array_hash_type::const_iterator end) const
1806 {
1807 std::array<size_type, ALPHABET_SIZE> count{{}};
1808 for(auto it = begin; it != end; ++it) {
1809 if(it.key_size() == 0) {
1810 continue;
1811 }
1812
1813 count[as_position(it.key()[0])]++;
1814 }
1815
1816 return count;
1817 }
1818
1819
1820 hash_node& get_hash_node_for_char(const std::array<size_type, ALPHABET_SIZE>& first_char_count,
1821 trie_node& tnode, CharT for_char)
1822 {
1823 if(tnode.child(for_char) == nullptr) {
1824 const size_type nb_buckets =
1825 size_type(
1826 std::ceil(float(first_char_count[as_position(for_char)] +
1827 HASH_NODE_DEFAULT_INIT_BUCKETS_COUNT/2)
1828 / m_max_load_factor
1829 ));
1830
1831 tnode.set_child(for_char,
1832 make_unique<hash_node>(nb_buckets, m_hash, m_max_load_factor));
1833 }
1834
1835 return tnode.child(for_char)->as_hash_node();
1836 }
1837
1838 iterator mutable_iterator(const_iterator it) noexcept {
1839 // end iterator or reading from a trie node value
1840 if(it.m_current_hash_node == nullptr || it.m_read_trie_node_value) {
1841 typename array_hash_type::iterator default_it;
1842
1843 return iterator(const_cast<trie_node*>(it.m_current_trie_node), nullptr,
1844 default_it, default_it, it.m_read_trie_node_value);
1845 }
1846 else {
1847 hash_node* hnode = const_cast<hash_node*>(it.m_current_hash_node);
1848 return iterator(const_cast<trie_node*>(it.m_current_trie_node), hnode,
1849 hnode->array_hash().mutable_iterator(it.m_array_hash_iterator),
1850 hnode->array_hash().mutable_iterator(it.m_array_hash_end_iterator),
1851 it.m_read_trie_node_value);
1852 }
1853 }
1854
1855 prefix_iterator mutable_iterator(const_prefix_iterator it) noexcept {
1856 // end iterator or reading from a trie node value
1857 if(it.m_current_hash_node == nullptr || it.m_read_trie_node_value) {
1858 typename array_hash_type::iterator default_it;
1859
1860 return prefix_iterator(const_cast<trie_node*>(it.m_current_trie_node), nullptr,
1861 default_it, default_it, it.m_read_trie_node_value, "");
1862 }
1863 else {
1864 hash_node* hnode = const_cast<hash_node*>(it.m_current_hash_node);
1865 return prefix_iterator(const_cast<trie_node*>(it.m_current_trie_node), hnode,
1866 hnode->array_hash().mutable_iterator(it.m_array_hash_iterator),
1867 hnode->array_hash().mutable_iterator(it.m_array_hash_end_iterator),
1868 it.m_read_trie_node_value, it.m_prefix_filter);
1869 }
1870 }
1871
1872 template<class Serializer>
1873 void serialize_impl(Serializer& serializer) const {
1874 const slz_size_type version = SERIALIZATION_PROTOCOL_VERSION;
1875 serializer(version);
1876
1877 const slz_size_type nb_elements = m_nb_elements;
1878 serializer(nb_elements);
1879
1880 const float max_load_factor = m_max_load_factor;
1881 serializer(max_load_factor);
1882
1883 const slz_size_type burst_threshold = m_burst_threshold;
1884 serializer(burst_threshold);
1885
1886
1887 std::basic_string<CharT> str_buffer;
1888
1889 auto it = begin();
1890 auto last = end();
1891
1892 while(it != last) {
1893 // Serialize trie node value
1894 if(it.m_read_trie_node_value) {
1895 const CharT node_type = static_cast<typename std::underlying_type<slz_node_type>::type>(slz_node_type::TRIE_NODE);
1896 serializer(&node_type, 1);
1897
1898 it.key(str_buffer);
1899
1900 const slz_size_type str_size = str_buffer.size();
1901 serializer(str_size);
1902 serializer(str_buffer.data(), str_buffer.size());
1903 serialize_value(serializer, it);
1904
1905
1906 ++it;
1907 }
1908 // Serialize hash node values
1909 else {
1910 const CharT node_type = static_cast<typename std::underlying_type<slz_node_type>::type>(slz_node_type::HASH_NODE);
1911 serializer(&node_type, 1);
1912
1913 it.hash_node_prefix(str_buffer);
1914
1915 const slz_size_type str_size = str_buffer.size();
1916 serializer(str_size);
1917 serializer(str_buffer.data(), str_buffer.size());
1918
1919 const hash_node* hnode = it.m_current_hash_node;
1920 tsl_ht_assert(hnode != nullptr);
1921 hnode->array_hash().serialize(serializer);
1922
1923
1924 it.skip_hash_node();
1925 }
1926 }
1927 }
1928
1929 template<class Serializer, class U = T,
1930 typename std::enable_if<!has_value<U>::value>::type* = nullptr>
1931 void serialize_value(Serializer& /*serializer*/, const_iterator /*it*/) const {
1932 }
1933
1934 template<class Serializer, class U = T,
1935 typename std::enable_if<has_value<U>::value>::type* = nullptr>
1936 void serialize_value(Serializer& serializer, const_iterator it) const {
1937 serializer(it.value());
1938 }
1939
1940 template<class Deserializer>
1941 void deserialize_impl(Deserializer& deserializer, bool hash_compatible) {
1942 tsl_ht_assert(m_nb_elements == 0 && m_root == nullptr); // Current trie must be empty
1943
1944 const slz_size_type version = deserialize_value<slz_size_type>(deserializer);
1945 // For now we only have one version of the serialization protocol.
1946 // If it doesn't match there is a problem with the file.
1947 if(version != SERIALIZATION_PROTOCOL_VERSION) {
1948 THROW(std::runtime_error, "Can't deserialize the htrie_map/set. The protocol version header is invalid.");
1949 }
1950
1951
1952 const slz_size_type nb_elements = deserialize_value<slz_size_type>(deserializer);
1953 const float max_load_factor = deserialize_value<float>(deserializer);
1954 const slz_size_type burst_threshold = deserialize_value<slz_size_type>(deserializer);
1955
1956 this->burst_threshold(numeric_cast<std::size_t>(burst_threshold, "Deserialized burst_threshold is too big."));
1957 this->max_load_factor(max_load_factor);
1958
1959
1960 std::vector<CharT> str_buffer;
1961 while(m_nb_elements < nb_elements) {
1962 CharT node_type_marker;
1963 deserializer(&node_type_marker, 1);
1964
1965 static_assert(std::is_same<CharT, typename std::underlying_type<slz_node_type>::type>::value, "");
1966 const slz_node_type node_type = static_cast<slz_node_type>(node_type_marker);
1967 if(node_type == slz_node_type::TRIE_NODE) {
1968 const std::size_t str_size = numeric_cast<std::size_t>(deserialize_value<slz_size_type>(deserializer),
1969 "Deserialized str_size is too big.");
1970
1971 str_buffer.resize(str_size);
1972 deserializer(str_buffer.data(), str_size);
1973
1974
1975 trie_node* current_node = insert_prefix_trie_nodes(str_buffer.data(), str_size);
1976 deserialize_value_node(deserializer, current_node);
1977 m_nb_elements++;
1978 }
1979 else if(node_type == slz_node_type::HASH_NODE) {
1980 const std::size_t str_size = numeric_cast<std::size_t>(deserialize_value<slz_size_type>(deserializer),
1981 "Deserialized str_size is too big.");
1982
1983 if(str_size == 0) {
1984 tsl_ht_assert(m_nb_elements == 0 && !m_root);
1985
1986 m_root = make_unique<hash_node>(array_hash_type::deserialize(deserializer, hash_compatible));
1987 m_nb_elements += m_root->as_hash_node().array_hash().size();
1988
1989 tsl_ht_assert(m_nb_elements == nb_elements);
1990 }
1991 else {
1992 str_buffer.resize(str_size);
1993 deserializer(str_buffer.data(), str_size);
1994
1995
1996 auto hnode = make_unique<hash_node>(array_hash_type::deserialize(deserializer, hash_compatible));
1997 m_nb_elements += hnode->array_hash().size();
1998
1999 trie_node* current_node = insert_prefix_trie_nodes(str_buffer.data(), str_size - 1);
2000 current_node->set_child(str_buffer[str_size - 1], std::move(hnode));
2001 }
2002 }
2003 else {
2004 THROW(std::runtime_error, "Unknown deserialized node type.");
2005 }
2006 }
2007
2008 tsl_ht_assert(m_nb_elements == nb_elements);
2009 }
2010
2011 trie_node* insert_prefix_trie_nodes(const CharT* prefix, std::size_t prefix_size) {
2012 if(m_root == nullptr) {
2013 m_root = make_unique<trie_node>();
2014 }
2015
2016 trie_node* current_node = &m_root->as_trie_node();
2017 for(std::size_t iprefix = 0; iprefix < prefix_size; iprefix++) {
2018 if(current_node->child(prefix[iprefix]) == nullptr) {
2019 current_node->set_child(prefix[iprefix], make_unique<trie_node>());
2020 }
2021
2022 current_node = &current_node->child(prefix[iprefix])->as_trie_node();
2023 }
2024
2025 return current_node;
2026 }
2027
2028 template<class Deserializer, class U = T,
2029 typename std::enable_if<!has_value<U>::value>::type* = nullptr>
2030 void deserialize_value_node(Deserializer& /*deserializer*/, trie_node* current_node) {
2031 tsl_ht_assert(!current_node->val_node());
2032 current_node->val_node() = make_unique<value_node>();
2033 }
2034
2035 template<class Deserializer, class U = T,
2036 typename std::enable_if<has_value<U>::value>::type* = nullptr>
2037 void deserialize_value_node(Deserializer& deserializer, trie_node* current_node) {
2038 tsl_ht_assert(!current_node->val_node());
2039 current_node->val_node() = make_unique<value_node>(deserialize_value<T>(deserializer));
2040 }
2041
2042 template<class U, class Deserializer>
2043 static U deserialize_value(Deserializer& deserializer) {
2044 // MSVC < 2017 is not conformant, circumvent the problem by removing the template keyword
2045 #if defined (_MSC_VER) && _MSC_VER < 1910
2046 return deserializer.Deserializer::operator()<U>();
2047 #else
2048 return deserializer.Deserializer::template operator()<U>();
2049 #endif
2050 }
2051
2052 // Same as std::make_unique for non-array types which is only available in C++14 (we need to support C++11).
2053 template<typename U, typename... Args>
2054 static std::unique_ptr<U> make_unique(Args&&... args) {
2055 return std::unique_ptr<U>(new U(std::forward<Args>(args)...));
2056 }
2057
2058 public:
2059 static constexpr float HASH_NODE_DEFAULT_MAX_LOAD_FACTOR = 8.0f;
2060 static const size_type DEFAULT_BURST_THRESHOLD = 16384;
2061
2062 private:
2063
2064 /**
2065 * Fixed size type used to represent size_type values on serialization. Need to be big enough
2066 * to represent a std::size_t on 32 and 64 bits platforms, and must be the same size on both platforms.
2067 */
2068 using slz_size_type = std::uint64_t;
2069 enum class slz_node_type: CharT { TRIE_NODE = 0, HASH_NODE = 1 };
2070
2071 /**
2072 * Protocol version currenlty used for serialization.
2073 */
2074 static const slz_size_type SERIALIZATION_PROTOCOL_VERSION = 1;
2075
2076 static const size_type HASH_NODE_DEFAULT_INIT_BUCKETS_COUNT = 32;
2077 static const size_type MIN_BURST_THRESHOLD = 4;
2078
2079 std::unique_ptr<anode> m_root;
2080 size_type m_nb_elements;
2081 Hash m_hash;
2082 float m_max_load_factor;
2083 size_type m_burst_threshold;
2084
2085 };
2086
2087 } // end namespace detail_htrie_hash
2088 } // end namespace tsl
2089
2090 #endif