GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 28 / 0 / 28
Functions: 100.0% 10 / 0 / 10
Branches: 95.8% 23 / 0 / 24
src/ds/bt_trv/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../util/traits/ds/lib.hpp"
4
5 namespace tifa_libs {
6
7 template <tp2_ds_c pointer, class F>
8 requires requires(pointer p, F&& f) { f(p); }
9 CEXP void pre_order(pointer p, F&& f) NE {
10 if (p) f(p), pre_order(p->ch[0], std::forward<F>(f)), pre_order(p->ch[1], std::forward<F>(f));
11 }
12 template <tp2_ds_c pointer, class F>
13 requires requires(pointer p, F f) { f(p); }
14 CEXP void in_order(pointer p, F&& f) NE {
15 if (p) in_order(p->ch[0], std::forward<F>(f)), f(p), in_order(p->ch[1], std::forward<F>(f));
16 }
17 template <tp2_ds_c pointer, class F>
18 requires requires(pointer p, F f) { f(p); }
19 CEXP void post_order(pointer p, F&& f) NE {
20 if (p) post_order(p->ch[0], std::forward<F>(f)), post_order(p->ch[1], std::forward<F>(f)), f(p);
21 }
22 template <tp_ds_c pointer, class F>
23 requires requires(pointer p, u32 level, F f) { f(p, level); }
24 CEXP void level_order(pointer p, F&& f) NE {
25 if (!p) return;
26 u32 level = 0;
27 std::queue<pointer> q({p});
28 while (!q.empty()) {
29 flt_ (u32, i, 0, (u32)q.size()) {
30 auto now = q.front();
31 q.pop(), f(now, level);
32 for (auto&& s : now->ch) q.push(s);
33 }
34 ++level;
35 }
36 }
37 template <tp_ds_c pointer, class Alloc>
38 30976597 CEXP void dealloc_subtree(pointer p, Alloc& alloc) NE {
39
8/8
void tifa_libs::dealloc_subtree<tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*, std::pmr::polymorphic_allocator<tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA> >(tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*, std::pmr::polymorphic_allocator<tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA>&):
✓ Branch 0 taken 1376438 times.
✓ Branch 1 taken 1376420 times.
void tifa_libs::dealloc_subtree<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int> > >(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int> >&):
✓ Branch 0 taken 137200 times.
✓ Branch 1 taken 137190 times.
void tifa_libs::dealloc_subtree<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> > > >(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> > >&):
✓ Branch 0 taken 5873856 times.
✓ Branch 1 taken 5873836 times.
void tifa_libs::dealloc_subtree<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int> > >(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int> >&):
✓ Branch 0 taken 8100847 times.
✓ Branch 1 taken 8100810 times.
 30976597 if (!p) return;
40
8/8
void tifa_libs::dealloc_subtree<tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*, std::pmr::polymorphic_allocator<tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA> >(tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA*, std::pmr::polymorphic_allocator<tifa_libs::kdtree<long, &(op(long, long)), int, 2u, false>::TIFA>&):
✓ Branch 1 taken 2752840 times.
✓ Branch 2 taken 1376420 times.
void tifa_libs::dealloc_subtree<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int> > >(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int> >&):
✓ Branch 1 taken 274380 times.
✓ Branch 2 taken 137190 times.
void tifa_libs::dealloc_subtree<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> > > >(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> > >&):
✓ Branch 1 taken 11747672 times.
✓ Branch 2 taken 5873836 times.
void tifa_libs::dealloc_subtree<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int> > >(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int> >&):
✓ Branch 1 taken 16201620 times.
✓ Branch 2 taken 8100810 times.
 46464768 for (auto&& s : p->ch) dealloc_subtree(s, alloc);
41 15488256 alloc.deallocate(p, 1);
42 }
43
44 template <tp_ds_c pointer>
45 1490636 CEXP pointer most(pointer p, bool dir) NE {
46
3/4
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>* tifa_libs::most<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, bool):
✗ Branch 0 not taken.
✓ Branch 1 taken 35531 times.
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>* tifa_libs::most<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, bool):
✓ Branch 0 taken 72592 times.
✓ Branch 1 taken 1382513 times.
 1490636 if (!p) return nullptr;
47
4/4
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>* tifa_libs::most<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, bool):
✓ Branch 0 taken 37572 times.
✓ Branch 1 taken 35531 times.
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>* tifa_libs::most<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, bool):
✓ Branch 0 taken 7911720 times.
✓ Branch 1 taken 1382513 times.
 9367336 while (p->ch[dir]) p = p->ch[dir];
48 1418044 return p;
49 }
50 template <tp2_ds_c pointer>
51 291782 CEXP auto leftmost(pointer p) NE { return most(p, 0); }
52 template <tp2_ds_c pointer>
53 447828 CEXP auto rightmost(pointer p) NE { return most(p, 1); }
54
55 } // namespace tifa_libs
56