GCC Code Coverage Report

Directory: ./
File: src/utils/path_trie.cpp
Date: 2024-07-09 12:21:25
Exec Total Coverage
Lines: 72 93 77.4%
Functions: 6 9 66.7%
Branches: 48 92 52.2%
Line Branch Exec Source
1 /*
2 * Copyright (c) 2024 Muhammad Nawaz
3 * Licensed under the MIT License. See LICENSE file for more information.
4 */
5 // [ END OF LICENSE c6bd0f49d040fca8d8a9cb05868e66aa63f0e2e0 ]
6
7 #include "utils/path_trie.hpp"
8 #include "utils/common.hpp"
9
10 67 PathTrie::PathTrie()
11 67 : root_(new Node())
12 {
13 67 }
14
15 ✗ PathTrie::PathTrie(const PathTrie& other)
16 ✗ : root_(nullptr)
17 {
18 ✗ if (other.root_) {
19 ✗ root_ = new Node(*other.root_);
20 ✗ CopyNode(root_, other.root_);
21 }
22 ✗ }
23
24 ✗ PathTrie& PathTrie::operator=(const PathTrie& other)
25 {
26 ✗ if (this == &other)
27 ✗ return *this;
28
29 ✗ DeleteNode(root_);
30 ✗ if (other.root_) {
31 ✗ root_ = new Node(*other.root_);
32 ✗ CopyNode(root_, other.root_);
33 } else {
34 ✗ root_ = nullptr;
35 }
36
37 ✗ return *this;
38 }
39
40 ✗ void PathTrie::CopyNode(Node*& thisNode, Node* otherNode)
41 {
42 ✗ if (otherNode) {
43 ✗ thisNode = new Node(*otherNode);
44 ✗ for (const auto& child : otherNode->children) {
45 ✗ CopyNode(thisNode->children[child.first], child.second);
46 }
47 }
48 ✗ }
49
50 190 void PathTrie::Insert(const std::string& path)
51 {
52 190 auto* node = root_;
53 190 const char* dir_start = path.data();
54 190 const char* const path_end = dir_start + path.length();
55 const char* dir_end;
56 190 int fragment_index = 0;
57
58
2/2
✓ Branch 0 taken 796 times.
✓ Branch 1 taken 190 times.
 986 while (dir_start < path_end) {
59 796 dir_end = Seek(dir_start, path_end, '/');
60
1/2
✓ Branch 2 taken 796 times.
✗ Branch 3 not taken.
 796 std::string dir(dir_start, dir_end);
61 796 fragment_index++;
62
63
3/4
✓ Branch 1 taken 796 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 213 times.
✓ Branch 4 taken 583 times.
 796 if (dir[0] == '{') {
64 213 node->is_param = true;
65
1/2
✓ Branch 1 taken 213 times.
✗ Branch 2 not taken.
 213 node->dir = dir;
66 }
67
68
3/4
✓ Branch 2 taken 796 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 436 times.
✓ Branch 6 taken 360 times.
 796 if (node->children.find(dir) == node->children.end()) {
69
1/2
✓ Branch 1 taken 436 times.
✗ Branch 2 not taken.
 436 auto* new_node = new Node();
70 436 new_node->frag_idx = fragment_index; // Set the fragmentIndex for the new node
71
1/2
✓ Branch 1 taken 436 times.
✗ Branch 2 not taken.
 436 node->children[dir] = new_node;
72 }
73
1/2
✓ Branch 1 taken 796 times.
✗ Branch 2 not taken.
 796 node = node->children[dir];
74
75 796 dir_start = dir_end + 1; // skip '/'
76 796 }
77 190 }
78
79 14 bool PathTrie::Search(const char* beg, const char* const end, std::string& oas_path)
80 {
81 14 auto* node = root_;
82 const char* dir_end;
83 14 oas_path.clear();
84
85
2/2
✓ Branch 0 taken 54 times.
✓ Branch 1 taken 13 times.
 67 while (beg < end) {
86 54 dir_end = Seek(beg, end, '/');
87
1/2
✓ Branch 2 taken 54 times.
✗ Branch 3 not taken.
 54 std::string dir(beg, dir_end);
88
1/2
✓ Branch 1 taken 54 times.
✗ Branch 2 not taken.
 54 auto it = node->children.find(dir);
89
90
2/2
✓ Branch 2 taken 13 times.
✓ Branch 3 taken 41 times.
 54 if (it == node->children.end()) {
91
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 1 times.
 13 if (node->is_param) {
92
2/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 12 times.
✗ Branch 5 not taken.
 12 oas_path += node->dir + "/";
93 12 node = node->children.begin()->second;
94 } else {
95 1 oas_path.clear();
96 1 return false;
97 }
98 } else {
99
2/4
✓ Branch 1 taken 41 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 41 times.
✗ Branch 5 not taken.
 41 oas_path += dir + "/";
100 41 node = it->second;
101 }
102
103 53 beg = dir_end + 1; // skip '/'
104
2/2
✓ Branch 1 taken 53 times.
✓ Branch 2 taken 1 times.
 54 }
105
106
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 if (!oas_path.empty()) {
107 13 oas_path.pop_back(); // remove trailing '/'
108 }
109
110 13 return true;
111 }
112
113 33 bool PathTrie::Search(const char* beg, const char* const end, std::string& oas_path,
114 std::unordered_map<size_t, ParamRange>& param_idxs)
115 {
116 33 auto* node = root_;
117 const char* dir_end;
118 33 oas_path.clear();
119
120
2/2
✓ Branch 0 taken 142 times.
✓ Branch 1 taken 32 times.
 174 while (beg < end) {
121 142 dir_end = Seek(beg, end, '/');
122
1/2
✓ Branch 2 taken 142 times.
✗ Branch 3 not taken.
 142 std::string dir(beg, dir_end);
123
1/2
✓ Branch 1 taken 142 times.
✗ Branch 2 not taken.
 142 auto it = node->children.find(dir);
124
125
2/2
✓ Branch 2 taken 40 times.
✓ Branch 3 taken 102 times.
 142 if (it == node->children.end()) {
126
2/2
✓ Branch 0 taken 39 times.
✓ Branch 1 taken 1 times.
 40 if (node->is_param) {
127
2/4
✓ Branch 1 taken 39 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 39 times.
✗ Branch 5 not taken.
 39 oas_path += node->dir + "/";
128
1/2
✓ Branch 1 taken 39 times.
✗ Branch 2 not taken.
 39 param_idxs.emplace(node->frag_idx, ParamRange{beg, dir_end});
129 39 node = node->children.begin()->second;
130 } else {
131 1 oas_path.clear();
132 1 return false;
133 }
134 } else {
135
2/4
✓ Branch 1 taken 102 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 102 times.
✗ Branch 5 not taken.
 102 oas_path += dir + "/";
136 102 node = it->second;
137 }
138
139 141 beg = dir_end + 1; // skip '/'
140
2/2
✓ Branch 1 taken 141 times.
✓ Branch 2 taken 1 times.
 142 }
141
142
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 if (!oas_path.empty()) {
143 32 oas_path.pop_back(); // remove trailing '/'
144 }
145
146 32 return true;
147 }
148
149 67 PathTrie::~PathTrie()
150 {
151 #ifndef LUA_OAS_VALIDATOR // LUA manages garbage collection itself
152 67 DeleteNode(root_);
153 #endif // LUA_OAS_VALIDATOR
154 67 }
155
156 503 void PathTrie::DeleteNode(Node* node)
157 {
158 #ifndef LUA_OAS_VALIDATOR // LUA manages garbage collection itself
159
2/2
✓ Branch 5 taken 436 times.
✓ Branch 6 taken 503 times.
 939 for (auto& pair : node->children) {
160
1/2
✓ Branch 1 taken 436 times.
✗ Branch 2 not taken.
 436 DeleteNode(pair.second);
161 }
162
1/2
✓ Branch 0 taken 503 times.
✗ Branch 1 not taken.
 503 delete node;
163 #endif // LUA_OAS_VALIDATOR
164 503 }
165