mdds
Loading...
Searching...
No Matches
trie_map_itr.hpp
1/*************************************************************************
2 *
3 * Copyright (c) 2016-2020 Kohei Yoshida
4 *
5 * Permission is hereby granted, free of charge, to any person
6 * obtaining a copy of this software and associated documentation
7 * files (the "Software"), to deal in the Software without
8 * restriction, including without limitation the rights to use,
9 * copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following
12 * conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24 * OTHER DEALINGS IN THE SOFTWARE.
25 *
26 ************************************************************************/
27
28#ifndef INCLUDED_MDDS_TRIE_MAP_ITR_HPP
29#define INCLUDED_MDDS_TRIE_MAP_ITR_HPP
30
31#include <utility>
32#include <cassert>
33#include <iostream>
34#ifdef MDDS_TRIE_MAP_DEBUG
35#include <sstream>
36#endif
37
38#include "mdds/global.hpp"
39#include "mdds/ref_pair.hpp"
40
41namespace mdds { namespace trie { namespace detail {
42
43enum class iterator_type
44{
49 normal,
55 end,
61 empty
62};
63
64enum empty_iterator_type
65{
66 empty_iterator
67};
68
69template<typename _TrieType, typename _C>
71
72template<typename _TrieType>
73struct get_node_stack_type<_TrieType, std::true_type>
74{
75 using type = typename _TrieType::const_node_stack_type;
76};
77
78template<typename _TrieType>
79struct get_node_stack_type<_TrieType, std::false_type>
80{
81 using type = typename _TrieType::node_stack_type;
82};
83
84template<typename _TrieType>
85class search_results;
86
87template<typename _TrieType, bool IsConst>
89{
90protected:
91 using trie_type = _TrieType;
92
93 using _is_const = std::bool_constant<IsConst>;
94
95 friend trie_type;
97
98 using node_stack_type = typename get_node_stack_type<trie_type, _is_const>::type;
99 using trie_node_type = mdds::detail::const_t<typename trie_type::trie_node, IsConst>;
100 using trie_node_child_pos_type = typename mdds::detail::get_iterator_type<
101 typename std::remove_const<trie_node_type>::type::children_type, _is_const>::type;
102
103 using key_type = typename trie_type::key_type;
105
106public:
107 // iterator traits
109 using pointer = value_type*;
110 using reference = value_type&;
111 using difference_type = std::ptrdiff_t;
112 using iterator_category = std::bidirectional_iterator_tag;
113
114protected:
115 node_stack_type m_node_stack;
116 key_type m_buffer;
117 key_type m_current_key;
118 trie_value_type* m_current_value_ptr;
119 iterator_type m_type;
120
121 static trie_node_type* push_child_node_to_stack(
122 node_stack_type& node_stack, key_type& buf, trie_node_child_pos_type& child_pos)
123 {
124 trie_node_type* node = &child_pos->second;
125 buf.push_back(child_pos->first);
126 node_stack.emplace_back(node, node->children.begin());
127
128 return node;
129 }
130
135 static trie_node_type* descend_to_previus_leaf_node(node_stack_type& node_stack, key_type& buf)
136 {
137 trie_node_type* cur_node = nullptr;
138
139 do
140 {
141 // Keep moving down on the right-most child nodes until the
142 // leaf node is reached.
143
144 auto& si = node_stack.back();
145
146 --si.child_pos;
147 buf.push_back(si.child_pos->first);
148 cur_node = &si.child_pos->second;
149 node_stack.emplace_back(cur_node, cur_node->children.end());
150 } while (!cur_node->children.empty());
151
152 return cur_node;
153 }
154
155 iterator_base(empty_iterator_type) : m_current_value_ptr(nullptr), m_type(iterator_type::empty)
156 {}
157
158public:
159 iterator_base() : m_current_value_ptr(nullptr), m_type(iterator_type::normal)
160 {}
161
162 iterator_base(node_stack_type&& node_stack, key_type&& buf, iterator_type type)
163 : m_node_stack(std::move(node_stack)), m_buffer(std::move(buf)), m_current_key(m_buffer),
164 m_current_value_ptr(&m_node_stack.back().node->value), m_type(type)
165 {}
166
167 bool operator==(const iterator_base& other) const
168 {
169 if (m_type != other.m_type)
170 return false;
171
172 if (m_type == iterator_type::empty)
173 return true;
174
175 return m_node_stack.back() == other.m_node_stack.back();
176 }
177
178 bool operator!=(const iterator_base& other) const
179 {
180 return !operator==(other);
181 }
182
183 value_type operator*()
184 {
185 return value_type(m_current_key, *m_current_value_ptr);
186 }
187
188 value_type operator->()
189 {
190 return value_type(m_current_key, *m_current_value_ptr);
191 }
192
193 iterator_base& operator++()
194 {
195 trie_node_type* cur_node = m_node_stack.back().node;
196
197 do
198 {
199 if (cur_node->children.empty())
200 {
201 // Current node is a leaf node. Keep moving up the stack until we
202 // reach a parent node with unvisited children.
203
204 while (true)
205 {
206 if (m_node_stack.size() == 1)
207 {
208#ifdef MDDS_TRIE_MAP_DEBUG
209 if (m_type == iterator_type::end)
210 {
211 std::ostringstream os;
212 os << "iterator_base::operator++#" << __LINE__ << ": moving past the end position!";
213 throw general_error(os.str());
214 }
215#endif
216 // We've reached the end position. Bail out.
217 m_type = iterator_type::end;
218 return *this;
219 }
220
221 // Move up one parent and see if it has an unvisited child node.
222 m_buffer.pop_back();
223 m_node_stack.pop_back();
224 auto& si = m_node_stack.back();
225 ++si.child_pos;
226
227 if (si.child_pos != si.node->children.end())
228 {
229 // Move down to this unvisited child node.
230 cur_node = push_child_node_to_stack(m_node_stack, m_buffer, si.child_pos);
231 break;
232 }
233 }
234 }
235 else
236 {
237 // Current node has child nodes. Follow the first child node.
238 auto child_pos = cur_node->children.begin();
239 cur_node = push_child_node_to_stack(m_node_stack, m_buffer, child_pos);
240 }
241 } while (!cur_node->has_value);
242
243 m_current_key = m_buffer;
244 m_current_value_ptr = &cur_node->value;
245 return *this;
246 }
247
248 iterator_base operator++(int)
249 {
250 iterator_base tmp(*this);
251 operator++();
252 return tmp;
253 }
254
255 iterator_base& operator--()
256 {
257 trie_node_type* cur_node = m_node_stack.back().node;
258
259 if (m_type == iterator_type::end && cur_node->has_value)
260 {
261 assert(m_node_stack.size() == 1);
262 m_type = iterator_type::normal;
263 }
264 else if (m_node_stack.size() == 1)
265 {
266 // This is the end position aka root node. Move down to the
267 // right-most leaf node.
268 auto& si = m_node_stack.back();
269 assert(si.child_pos == cur_node->children.end());
270 cur_node = descend_to_previus_leaf_node(m_node_stack, m_buffer);
271 m_type = iterator_type::normal;
272 }
273 else if (cur_node->children.empty())
274 {
275 // This is a leaf node. Keep going up until it finds a parent
276 // node with unvisited child nodes on the left side, then descend
277 // on that path all the way to its leaf.
278
279 do
280 {
281 // Go up one node.
282
283 m_buffer.pop_back();
284 m_node_stack.pop_back();
285 auto& si = m_node_stack.back();
286 cur_node = si.node;
287
288 if (si.child_pos != cur_node->children.begin())
289 {
290 // Left and down.
291 cur_node = descend_to_previus_leaf_node(m_node_stack, m_buffer);
292 assert(cur_node->has_value);
293 }
294 } while (!cur_node->has_value);
295 }
296 else
297 {
298 // Non-leaf node with value. Keep going up until either the root
299 // node or another node with value is reached.
300
301 assert(cur_node->has_value);
302 assert(m_node_stack.back().child_pos == cur_node->children.begin());
303
304 do
305 {
306 // Go up.
307 m_buffer.pop_back();
308 m_node_stack.pop_back();
309 auto& si = m_node_stack.back();
310 cur_node = si.node;
311
312 if (m_node_stack.size() == 1)
313 {
314 // Root node reached. Left and down.
315 cur_node = descend_to_previus_leaf_node(m_node_stack, m_buffer);
316 assert(cur_node->has_value);
317 }
318 } while (!cur_node->has_value);
319 }
320
321 assert(cur_node->has_value);
322 m_current_key = m_buffer;
323 m_current_value_ptr = &cur_node->value;
324 return *this;
325 }
326
327 iterator_base operator--(int)
328 {
329 iterator_base tmp(*this);
330 operator--();
331 return tmp;
332 }
333};
334
335template<typename _TrieType>
336class const_iterator;
337
338template<typename _TrieType>
339class iterator : public iterator_base<_TrieType, false>
340{
341 using trie_type = _TrieType;
342
343 friend trie_type;
346
348 using node_stack_type = typename base_type::node_stack_type;
349 using key_type = typename base_type::key_type;
350
351 iterator(empty_iterator_type t) : base_type(t)
352 {}
353
354public:
355 iterator() : base_type()
356 {}
357
358 iterator(node_stack_type&& node_stack, key_type&& buf, iterator_type type)
359 : base_type(std::move(node_stack), std::move(buf), type)
360 {}
361};
362
363template<typename _TrieType>
364class const_iterator : public iterator_base<_TrieType, true>
365{
366 using trie_type = _TrieType;
367
368 friend trie_type;
370
372 using node_stack_type = typename base_type::node_stack_type;
373 using key_type = typename base_type::key_type;
374
375 using base_type::m_buffer;
376 using base_type::m_current_key;
377 using base_type::m_current_value_ptr;
378 using base_type::m_node_stack;
379 using base_type::m_type;
380
381 const_iterator(empty_iterator_type t) : base_type(t)
382 {}
383
384public:
386 {}
387
388 const_iterator(node_stack_type&& node_stack, key_type&& buf, iterator_type type)
389 : base_type(std::move(node_stack), std::move(buf), type)
390 {}
391
393 {
394 m_buffer = it.m_buffer;
395 m_current_key = it.m_current_key;
396 m_current_value_ptr = it.m_current_value_ptr;
397 m_type = it.m_type;
398
399 for (const auto& e : it.m_node_stack)
400 m_node_stack.emplace_back(e.node, e.child_pos);
401 }
402};
403
404template<typename _TrieType>
405bool operator==(const iterator<_TrieType>& left, const const_iterator<_TrieType>& right)
406{
407 return const_iterator<_TrieType>(left) == right;
408}
409
410template<typename _TrieType>
411bool operator!=(const iterator<_TrieType>& left, const const_iterator<_TrieType>& right)
412{
413 return const_iterator<_TrieType>(left) != right;
414}
415
416template<typename _TrieType>
417bool operator==(const const_iterator<_TrieType>& left, const iterator<_TrieType>& right)
418{
419 return left == const_iterator<_TrieType>(right);
420}
421
422template<typename _TrieType>
423bool operator!=(const const_iterator<_TrieType>& left, const iterator<_TrieType>& right)
424{
425 return left != const_iterator<_TrieType>(right);
426}
427
428template<typename _TrieType>
430{
431 using trie_type = _TrieType;
432 friend trie_type;
433 using node_stack_type = typename trie_type::const_node_stack_type;
434
435 using trie_node = typename trie_type::trie_node;
436 using key_type = typename trie_type::key_type;
437 using key_unit_type = typename key_type::value_type;
438
439 const trie_node* m_node;
440 key_type m_buffer;
441 node_stack_type m_node_stack;
442
443 search_results(const trie_node* node, key_type&& buf) : m_node(node), m_buffer(buf)
444 {}
445
446public:
447 using const_iterator = typename trie_type::const_iterator;
448
449 const_iterator begin() const
450 {
451 if (!m_node)
452 // empty results.
453 return const_iterator(empty_iterator);
454
455 // Push the root node.
456 key_type buf(m_buffer);
457 node_stack_type node_stack;
458 node_stack.emplace_back(m_node, m_node->children.begin());
459
460 while (!node_stack.back().node->has_value)
461 {
462 // There should always be at least one value node along the
463 // left-most branch.
464
465 auto it = node_stack.back().child_pos;
466 const_iterator::push_child_node_to_stack(node_stack, buf, it);
467 }
468
469 return const_iterator(std::move(node_stack), std::move(buf), iterator_type::normal);
470 }
471
472 const_iterator end() const
473 {
474 if (!m_node)
475 // empty results.
476 return const_iterator(empty_iterator);
477
478 node_stack_type node_stack;
479 node_stack.emplace_back(m_node, m_node->children.end());
480 return const_iterator(std::move(node_stack), key_type(m_buffer), iterator_type::end);
481 }
482};
483
484template<typename _TrieType>
486
487template<typename TrieT>
489{
490 using trie_type = TrieT;
491 friend trie_type;
493
494 using stack_item = typename trie_type::stack_item;
495 using node_stack_type = typename trie_type::node_stack_type;
496
497 using key_type = typename trie_type::key_type;
498 using size_type = typename trie_type::size_type;
499 using trie_value_type = typename trie_type::value_type;
500 using value_store_type = typename trie_type::value_store_type;
501 using pack_value_type = typename trie_type::pack_value_type;
502 using key_unit_type = typename key_type::value_type;
503
504public:
505 // iterator traits
506 using value_type = mdds::detail::ref_pair<std::add_const_t<key_type>, std::add_const_t<trie_value_type>>;
507 using pointer = value_type*;
508 using reference = value_type&;
509 using difference_type = std::ptrdiff_t;
510 using iterator_category = std::bidirectional_iterator_tag;
511
512private:
513 const value_store_type* m_value_store = nullptr;
514 node_stack_type m_node_stack;
515 key_type m_buffer;
516 pack_value_type m_current_value = trie_type::null_value;
517 iterator_type m_type;
518
523 static void push_child_node_to_stack(
524 const value_store_type* value_store, node_stack_type& node_stack, key_type& buf,
525 const pack_value_type* child_pos)
526 {
527 assert(value_store);
528 const auto* node_pos = node_stack.back().node_pos;
529
530 key_unit_type c = static_cast<key_unit_type>(*child_pos);
531 buf.push_back(c);
532 ++child_pos;
533 auto offset = static_cast<size_type>(*child_pos);
534 node_pos -= offset; // Jump to the head of the child node.
535 const auto* p = node_pos;
536 ++p;
537 size_type index_size = *p;
538 ++p;
539 child_pos = p;
540 const auto* child_end = child_pos + index_size;
541
542 // Push it onto the stack.
543 node_stack.emplace_back(value_store, node_pos, child_pos, child_end);
544 }
545
546 static const void descend_to_previous_leaf_node(node_stack_type& node_stack, key_type& buf)
547 {
548 const pack_value_type* node_pos = nullptr;
549 size_t index_size = 0;
550
551 do
552 {
553 // Keep moving down on the right-most child nodes until the
554 // leaf node is reached.
555
556 stack_item* si = &node_stack.back();
557 node_pos = si->node_pos;
558 --si->child_pos;
559 size_t offset = *si->child_pos;
560 --si->child_pos;
561 key_unit_type c = *si->child_pos;
562 node_pos -= offset; // Jump to the head of the child node.
563 buf.push_back(c);
564
565 const auto* p = node_pos;
566 ++p;
567 index_size = *p;
568 ++p;
569 const auto* child_pos = p;
570 const auto* child_end = child_pos + index_size;
571 node_stack.emplace_back(node_stack.back().value_store, node_pos, child_end, child_end);
572 } while (index_size);
573 }
574
575 packed_iterator_base(empty_iterator_type) : m_type(iterator_type::empty)
576 {}
577
578public:
579 packed_iterator_base() : m_type(iterator_type::normal)
580 {}
581
583 const value_store_type* value_store, node_stack_type&& node_stack, key_type&& buf, pack_value_type pos)
584 : m_value_store(value_store), m_node_stack(std::move(node_stack)), m_buffer(std::move(buf)),
585 m_current_value(pos), m_type(iterator_type::normal)
586 {}
587
588 packed_iterator_base(const value_store_type* value_store, node_stack_type&& node_stack, key_type&& buf)
589 : m_value_store(value_store), m_node_stack(std::move(node_stack)), m_buffer(std::move(buf)),
590 m_type(iterator_type::end)
591 {}
592
593 bool operator==(const packed_iterator_base& other) const
594 {
595 if (m_type != other.m_type)
596 return false;
597
598 if (m_type == iterator_type::empty)
599 return true;
600
601 return m_node_stack.back() == other.m_node_stack.back();
602 }
603
604 bool operator!=(const packed_iterator_base& other) const
605 {
606 return !operator==(other);
607 }
608
609 value_type operator*()
610 {
611 assert(m_value_store);
612 assert(m_current_value != trie_type::null_value);
613 return value_type(m_buffer, (*m_value_store)[m_current_value]);
614 }
615
616 value_type operator->()
617 {
618 assert(m_value_store);
619 assert(m_current_value != trie_type::null_value);
620 return value_type(m_buffer, (*m_value_store)[m_current_value]);
621 }
622
623 packed_iterator_base& operator++()
624 {
625 stack_item* si = &m_node_stack.back();
626 pack_value_type v = trie_type::null_value;
627 size_t index_size = *(si->node_pos + 1);
628
629 do
630 {
631 if (!index_size)
632 {
633 // Current node is a leaf node. Keep moving up the stack until we
634 // reach a parent node with unvisited children.
635
636 while (true)
637 {
638 if (m_node_stack.size() == 1)
639 {
640#ifdef MDDS_TRIE_MAP_DEBUG
641 if (m_type == iterator_type::end)
642 {
643 std::ostringstream os;
644 os << "packed_iterator_base::operator++#" << __LINE__ << ": moving past the end position!";
645 throw general_error(os.str());
646 }
647#endif
648 // We've reached the end position. Bail out.
649 m_type = iterator_type::end;
650 return *this;
651 }
652
653 // Move up one parent and see if it has an unvisited child node.
654 m_buffer.pop_back();
655 m_node_stack.pop_back();
656 si = &m_node_stack.back();
657 std::advance(si->child_pos, 2);
658
659 if (si->child_pos != si->child_end)
660 {
661 // Move down to this unvisited child node.
662 push_child_node_to_stack(m_value_store, m_node_stack, m_buffer, si->child_pos);
663 break;
664 }
665 }
666 }
667 else
668 {
669 // Current node has child nodes. Follow the first child node.
670 push_child_node_to_stack(m_value_store, m_node_stack, m_buffer, si->child_pos);
671 }
672
673 si = &m_node_stack.back();
674 v = *si->node_pos;
675 index_size = *(si->node_pos + 1);
676 } while (v == trie_type::null_value);
677
678 assert(v != trie_type::null_value);
679 m_current_value = v;
680
681 return *this;
682 }
683
684 packed_iterator_base operator++(int)
685 {
686 packed_iterator_base tmp(*this);
687 operator++();
688 return tmp;
689 }
690
691 packed_iterator_base& operator--()
692 {
693 stack_item* si = &m_node_stack.back();
694 pack_value_type v = *si->node_pos;
695 size_t index_size = *(si->node_pos + 1); // index size for child nodes.
696
697 if (m_type == iterator_type::end && v != trie_type::null_value)
698 {
699 assert(m_node_stack.size() == 1);
700 m_type = iterator_type::normal;
701 }
702 else if (m_node_stack.size() == 1)
703 {
704 // This is the end position aka root node. Move down to the
705 // right-most leaf node.
706 assert(si->child_pos == si->child_end);
707 descend_to_previous_leaf_node(m_node_stack, m_buffer);
708 si = &m_node_stack.back();
709 v = *si->node_pos;
710 m_type = iterator_type::normal;
711 }
712 else if (!index_size)
713 {
714 // This is a leaf node. Keep going up until it finds a parent
715 // node with unvisited child nodes on the left side, then descend
716 // on that path all the way to its leaf.
717
718 do
719 {
720 // Go up one node.
721
722 m_buffer.pop_back();
723 m_node_stack.pop_back();
724 si = &m_node_stack.back();
725 const auto* p = si->node_pos;
726 v = *p;
727 ++p;
728 index_size = *p;
729 ++p;
730 const auto* first_child = p;
731
732 if (si->child_pos != first_child)
733 {
734 // Left and down.
735 descend_to_previous_leaf_node(m_node_stack, m_buffer);
736 si = &m_node_stack.back();
737 p = si->node_pos;
738 v = *p;
739 assert(v != trie_type::null_value);
740 }
741 } while (v == trie_type::null_value);
742 }
743 else
744 {
745 // Non-leaf node with value. Keep going up until either the root
746 // node or another node with value is reached.
747
748 assert(*si->node_pos); // this node should have a value.
749 assert(si->child_pos == (si->node_pos + 2));
750
751 do
752 {
753 // Go up.
754 m_buffer.pop_back();
755 m_node_stack.pop_back();
756 si = &m_node_stack.back();
757 v = *si->node_pos;
758
759 if (m_node_stack.size() == 1)
760 {
761 // Root node reached.
762 descend_to_previous_leaf_node(m_node_stack, m_buffer);
763 si = &m_node_stack.back();
764 v = *si->node_pos;
765 assert(v != trie_type::null_value);
766 }
767 } while (v == trie_type::null_value);
768 }
769
770 assert(v != trie_type::null_value);
771 m_current_value = v;
772
773 return *this;
774 }
775
776 packed_iterator_base operator--(int)
777 {
778 packed_iterator_base tmp(*this);
779 operator--();
780 return tmp;
781 }
782};
783
784template<typename _TrieType>
786{
787 using trie_type = _TrieType;
788 friend trie_type;
789 using node_stack_type = typename trie_type::node_stack_type;
790 using value_store_type = typename trie_type::value_store_type;
791 using pack_value_type = typename trie_type::pack_value_type;
792
793 using key_type = typename trie_type::key_type;
794 using key_unit_type = typename key_type::value_type;
795
796 const value_store_type* m_value_store = nullptr;
797 const pack_value_type* m_node = nullptr;
798 key_type m_buffer;
799
800 packed_search_results(const value_store_type* value_store, const pack_value_type* node, key_type&& buf)
801 : m_value_store(value_store), m_node(node), m_buffer(std::move(buf))
802 {
803 assert(m_value_store);
804 }
805
806 node_stack_type get_root_node() const
807 {
808 const auto* p = m_node;
809 ++p;
810 size_t index_size = *p;
811 ++p;
812 const auto* child_pos = p;
813 const auto* child_end = child_pos + index_size;
814
815 // Push this child node onto the stack.
816 node_stack_type node_stack;
817 node_stack.emplace_back(m_value_store, m_node, child_pos, child_end);
818 return node_stack;
819 }
820
821 void swap(packed_search_results& other)
822 {
823 std::swap(m_node, other.m_node);
824 std::swap(m_buffer, other.m_buffer);
825 }
826
827public:
829
830 packed_search_results() : m_node(nullptr)
831 {}
832
833 packed_search_results(const packed_search_results& other) : m_node(other.m_node), m_buffer(other.m_buffer)
834 {}
835
836 packed_search_results(packed_search_results&& other) : m_node(other.m_node), m_buffer(std::move(other.m_buffer))
837 {
838 other.m_node = nullptr;
839 }
840
842 {
843 packed_search_results tmp(std::move(other));
844 swap(tmp);
845 return *this;
846 }
847
848 const_iterator begin() const
849 {
850 if (!m_node)
851 // empty results.
852 return const_iterator(empty_iterator);
853
854 // Push the root node.
855 key_type buf(m_buffer);
856 node_stack_type node_stack = get_root_node();
857
858 while (!node_stack.back().has_value())
859 {
860 // There should always be at least one value node along the
861 // left-most branch.
862
863 const_iterator::push_child_node_to_stack(m_value_store, node_stack, buf, node_stack.back().child_pos);
864 }
865
866 return const_iterator(m_value_store, std::move(node_stack), std::move(buf), node_stack.back().get_value_pos());
867 }
868
869 const_iterator end() const
870 {
871 if (!m_node)
872 // empty results.
873 return const_iterator(empty_iterator);
874
875 node_stack_type node_stack = get_root_node();
876 auto& si = node_stack.back();
877 si.child_pos = si.child_end;
878 return const_iterator(m_value_store, std::move(node_stack), key_type(m_buffer));
879 }
880};
881
882}}} // namespace mdds::trie::detail
883
884#endif
Definition global.hpp:84
Definition trie_map_itr.hpp:365
Definition trie_map_itr.hpp:89
static trie_node_type * descend_to_previus_leaf_node(node_stack_type &node_stack, key_type &buf)
Definition trie_map_itr.hpp:135
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 global.hpp:146
Definition global.hpp:182
Definition ref_pair.hpp:37
Definition trie_map_itr.hpp:70