Coverage Report

Created: 2025-04-21 15:34

/root/doris/be/src/util/path_trie.hpp
Line
Count
Source (jump to first uncovered line)
1
// Licensed to the Apache Software Foundation (ASF) under one
2
// or more contributor license agreements.  See the NOTICE file
3
// distributed with this work for additional information
4
// regarding copyright ownership.  The ASF licenses this file
5
// to you under the Apache License, Version 2.0 (the
6
// "License"); you may not use this file except in compliance
7
// with the License.  You may obtain a copy of the License at
8
//
9
//   http://www.apache.org/licenses/LICENSE-2.0
10
//
11
// Unless required by applicable law or agreed to in writing,
12
// software distributed under the License is distributed on an
13
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14
// KIND, either express or implied.  See the License for the
15
// specific language governing permissions and limitations
16
// under the License.
17
18
#pragma once
19
20
#include <map>
21
#include <memory>
22
#include <string>
23
#include <vector>
24
25
namespace doris {
26
27
// This tree is usd for manage restful api path.
28
template <class T>
29
class PathTrie {
30
public:
31
25
    PathTrie() : _root("/", "*"), _root_value(nullptr), _separator('/') {}
_ZN5doris8PathTrieIiEC2Ev
Line
Count
Source
31
7
    PathTrie() : _root("/", "*"), _root_value(nullptr), _separator('/') {}
_ZN5doris8PathTrieIPNS_11HttpHandlerEEC2Ev
Line
Count
Source
31
18
    PathTrie() : _root("/", "*"), _root_value(nullptr), _separator('/') {}
32
33
25
    ~PathTrie() {
34
25
        if (_root_value != nullptr) {
35
2
            _allocator.destroy(_root_value);
36
2
            _allocator.deallocate(_root_value, 1);
37
2
        }
38
25
    }
_ZN5doris8PathTrieIiED2Ev
Line
Count
Source
33
7
    ~PathTrie() {
34
7
        if (_root_value != nullptr) {
35
1
            _allocator.destroy(_root_value);
36
1
            _allocator.deallocate(_root_value, 1);
37
1
        }
38
7
    }
_ZN5doris8PathTrieIPNS_11HttpHandlerEED2Ev
Line
Count
Source
33
18
    ~PathTrie() {
34
18
        if (_root_value != nullptr) {
35
1
            _allocator.destroy(_root_value);
36
1
            _allocator.deallocate(_root_value, 1);
37
1
        }
38
18
    }
39
40
    class Allocator {
41
    public:
42
        using value_type = T;
43
44
73
        T* allocate(size_t n) { return static_cast<T*>(::operator new(sizeof(T) * n)); }
_ZN5doris8PathTrieIiE9Allocator8allocateEm
Line
Count
Source
44
11
        T* allocate(size_t n) { return static_cast<T*>(::operator new(sizeof(T) * n)); }
_ZN5doris8PathTrieIPNS_11HttpHandlerEE9Allocator8allocateEm
Line
Count
Source
44
62
        T* allocate(size_t n) { return static_cast<T*>(::operator new(sizeof(T) * n)); }
45
46
        template <typename... Args>
47
138
        void construct(T* p, Args&&... args) {
48
138
            new (p) T(std::forward<Args>(args)...);
49
138
        }
_ZN5doris8PathTrieIiE9Allocator9constructIJRKiEEEvPiDpOT_
Line
Count
Source
47
11
        void construct(T* p, Args&&... args) {
48
11
            new (p) T(std::forward<Args>(args)...);
49
11
        }
_ZN5doris8PathTrieIiE9Allocator9constructIJRiEEEvPiDpOT_
Line
Count
Source
47
12
        void construct(T* p, Args&&... args) {
48
12
            new (p) T(std::forward<Args>(args)...);
49
12
        }
_ZN5doris8PathTrieIPNS_11HttpHandlerEE9Allocator9constructIJRKS2_EEEvPS2_DpOT_
Line
Count
Source
47
62
        void construct(T* p, Args&&... args) {
48
62
            new (p) T(std::forward<Args>(args)...);
49
62
        }
_ZN5doris8PathTrieIPNS_11HttpHandlerEE9Allocator9constructIJRS2_EEEvPS2_DpOT_
Line
Count
Source
47
53
        void construct(T* p, Args&&... args) {
48
53
            new (p) T(std::forward<Args>(args)...);
49
53
        }
50
51
73
        void destroy(T* p) { p->~T(); }
_ZN5doris8PathTrieIiE9Allocator7destroyEPi
Line
Count
Source
51
11
        void destroy(T* p) { p->~T(); }
_ZN5doris8PathTrieIPNS_11HttpHandlerEE9Allocator7destroyEPS2_
Line
Count
Source
51
62
        void destroy(T* p) { p->~T(); }
52
53
73
        void deallocate(T* p, size_t n) { ::operator delete(p); }
_ZN5doris8PathTrieIiE9Allocator10deallocateEPim
Line
Count
Source
53
11
        void deallocate(T* p, size_t n) { ::operator delete(p); }
_ZN5doris8PathTrieIPNS_11HttpHandlerEE9Allocator10deallocateEPS2_m
Line
Count
Source
53
62
        void deallocate(T* p, size_t n) { ::operator delete(p); }
54
    };
55
56
    class TrieNode {
57
    public:
58
        TrieNode(const std::string& key, const std::string& wildcard)
59
70
                : _value(nullptr), _wildcard(wildcard) {
60
70
            if (is_named_wildcard(key)) {
61
7
                _named_wildcard = extract_template(key);
62
7
            }
63
70
        }
_ZN5doris8PathTrieIiE8TrieNodeC2ERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEESA_
Line
Count
Source
59
15
                : _value(nullptr), _wildcard(wildcard) {
60
15
            if (is_named_wildcard(key)) {
61
2
                _named_wildcard = extract_template(key);
62
2
            }
63
15
        }
_ZN5doris8PathTrieIPNS_11HttpHandlerEE8TrieNodeC2ERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEESC_
Line
Count
Source
59
55
                : _value(nullptr), _wildcard(wildcard) {
60
55
            if (is_named_wildcard(key)) {
61
5
                _named_wildcard = extract_template(key);
62
5
            }
63
55
        }
64
65
        TrieNode(const std::string& key, const T& value, const std::string& wildcard)
66
70
                : _value(nullptr), _wildcard(wildcard) {
67
70
            _value = _allocator.allocate(1);
68
70
            _allocator.construct(_value, value);
69
70
            if (is_named_wildcard(key)) {
70
11
                _named_wildcard = extract_template(key);
71
11
            }
72
70
        }
_ZN5doris8PathTrieIiE8TrieNodeC2ERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEERKiSA_
Line
Count
Source
66
9
                : _value(nullptr), _wildcard(wildcard) {
67
9
            _value = _allocator.allocate(1);
68
9
            _allocator.construct(_value, value);
69
9
            if (is_named_wildcard(key)) {
70
2
                _named_wildcard = extract_template(key);
71
2
            }
72
9
        }
_ZN5doris8PathTrieIPNS_11HttpHandlerEE8TrieNodeC2ERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEERKS2_SC_
Line
Count
Source
66
61
                : _value(nullptr), _wildcard(wildcard) {
67
61
            _value = _allocator.allocate(1);
68
61
            _allocator.construct(_value, value);
69
61
            if (is_named_wildcard(key)) {
70
9
                _named_wildcard = extract_template(key);
71
9
            }
72
61
        }
73
74
140
        ~TrieNode() {
75
140
            for (auto& iter : _children) {
76
115
                delete iter.second;
77
115
                iter.second = nullptr;
78
115
            }
79
140
            if (_value != nullptr) {
80
71
                _allocator.destroy(_value);
81
71
                _allocator.deallocate(_value, 1);
82
71
            }
83
140
        }
_ZN5doris8PathTrieIiE8TrieNodeD2Ev
Line
Count
Source
74
24
        ~TrieNode() {
75
24
            for (auto& iter : _children) {
76
17
                delete iter.second;
77
17
                iter.second = nullptr;
78
17
            }
79
24
            if (_value != nullptr) {
80
10
                _allocator.destroy(_value);
81
10
                _allocator.deallocate(_value, 1);
82
10
            }
83
24
        }
_ZN5doris8PathTrieIPNS_11HttpHandlerEE8TrieNodeD2Ev
Line
Count
Source
74
116
        ~TrieNode() {
75
116
            for (auto& iter : _children) {
76
98
                delete iter.second;
77
98
                iter.second = nullptr;
78
98
            }
79
116
            if (_value != nullptr) {
80
61
                _allocator.destroy(_value);
81
61
                _allocator.deallocate(_value, 1);
82
61
            }
83
116
        }
84
85
        // Return true if insert success.
86
168
        bool insert(const std::vector<std::string> path, int index, const T& value) {
87
168
            if (index >= path.size()) {
88
0
                return false;
89
0
            }
90
168
            const std::string& token = path[index];
91
168
            std::string key = token;
92
93
168
            if (is_named_wildcard(token)) {
94
25
                key = _wildcard;
95
25
            }
96
97
168
            TrieNode* node = get_child(key);
98
99
168
            if (node == nullptr) {
100
                // no exist child for this key
101
115
                if (index == path.size() - 1) {
102
70
                    node = new TrieNode(token, value, _wildcard);
103
70
                    _children.insert(std::make_pair(key, node));
104
70
                    return true;
105
70
                } else {
106
45
                    node = new TrieNode(token, _wildcard);
107
45
                    _children.insert(std::make_pair(key, node));
108
45
                }
109
115
            } else {
110
                // If this is a template, set this to the node
111
53
                if (is_named_wildcard(token)) {
112
7
                    std::string temp = extract_template(token);
113
7
                    if (node->_named_wildcard.empty() || node->_named_wildcard.compare(temp) == 0) {
114
6
                        node->_named_wildcard = temp;
115
6
                    } else {
116
                        // Duplicated
117
1
                        return false;
118
1
                    }
119
7
                }
120
52
                if (index == path.size() - 1) {
121
2
                    if (node->_value == nullptr) {
122
1
                        node->_value = _allocator.allocate(1);
123
1
                        _allocator.construct(node->_value, value);
124
1
                        return true;
125
1
                    }
126
                    // Already register by other path
127
1
                    return false;
128
2
                }
129
52
            }
130
95
            return node->insert(path, index + 1, value);
131
168
        }
_ZN5doris8PathTrieIiE8TrieNode6insertESt6vectorINSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEESaIS9_EEiRKi
Line
Count
Source
86
30
        bool insert(const std::vector<std::string> path, int index, const T& value) {
87
30
            if (index >= path.size()) {
88
0
                return false;
89
0
            }
90
30
            const std::string& token = path[index];
91
30
            std::string key = token;
92
93
30
            if (is_named_wildcard(token)) {
94
6
                key = _wildcard;
95
6
            }
96
97
30
            TrieNode* node = get_child(key);
98
99
30
            if (node == nullptr) {
100
                // no exist child for this key
101
17
                if (index == path.size() - 1) {
102
9
                    node = new TrieNode(token, value, _wildcard);
103
9
                    _children.insert(std::make_pair(key, node));
104
9
                    return true;
105
9
                } else {
106
8
                    node = new TrieNode(token, _wildcard);
107
8
                    _children.insert(std::make_pair(key, node));
108
8
                }
109
17
            } else {
110
                // If this is a template, set this to the node
111
13
                if (is_named_wildcard(token)) {
112
2
                    std::string temp = extract_template(token);
113
2
                    if (node->_named_wildcard.empty() || node->_named_wildcard.compare(temp) == 0) {
114
1
                        node->_named_wildcard = temp;
115
1
                    } else {
116
                        // Duplicated
117
1
                        return false;
118
1
                    }
119
2
                }
120
12
                if (index == path.size() - 1) {
121
2
                    if (node->_value == nullptr) {
122
1
                        node->_value = _allocator.allocate(1);
123
1
                        _allocator.construct(node->_value, value);
124
1
                        return true;
125
1
                    }
126
                    // Already register by other path
127
1
                    return false;
128
2
                }
129
12
            }
130
18
            return node->insert(path, index + 1, value);
131
30
        }
_ZN5doris8PathTrieIPNS_11HttpHandlerEE8TrieNode6insertESt6vectorINSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEESaISB_EEiRKS2_
Line
Count
Source
86
138
        bool insert(const std::vector<std::string> path, int index, const T& value) {
87
138
            if (index >= path.size()) {
88
0
                return false;
89
0
            }
90
138
            const std::string& token = path[index];
91
138
            std::string key = token;
92
93
138
            if (is_named_wildcard(token)) {
94
19
                key = _wildcard;
95
19
            }
96
97
138
            TrieNode* node = get_child(key);
98
99
138
            if (node == nullptr) {
100
                // no exist child for this key
101
98
                if (index == path.size() - 1) {
102
61
                    node = new TrieNode(token, value, _wildcard);
103
61
                    _children.insert(std::make_pair(key, node));
104
61
                    return true;
105
61
                } else {
106
37
                    node = new TrieNode(token, _wildcard);
107
37
                    _children.insert(std::make_pair(key, node));
108
37
                }
109
98
            } else {
110
                // If this is a template, set this to the node
111
40
                if (is_named_wildcard(token)) {
112
5
                    std::string temp = extract_template(token);
113
5
                    if (node->_named_wildcard.empty() || node->_named_wildcard.compare(temp) == 0) {
114
5
                        node->_named_wildcard = temp;
115
5
                    } else {
116
                        // Duplicated
117
0
                        return false;
118
0
                    }
119
5
                }
120
40
                if (index == path.size() - 1) {
121
0
                    if (node->_value == nullptr) {
122
0
                        node->_value = _allocator.allocate(1);
123
0
                        _allocator.construct(node->_value, value);
124
0
                        return true;
125
0
                    }
126
                    // Already register by other path
127
0
                    return false;
128
0
                }
129
40
            }
130
77
            return node->insert(path, index + 1, value);
131
138
        }
132
133
        bool retrieve(const std::vector<std::string> path, int index, T* value,
134
148
                      std::map<std::string, std::string>* params) {
135
            // check max index
136
148
            if (index >= path.size()) {
137
0
                return false;
138
0
            }
139
148
            bool use_wildcard = false;
140
148
            const std::string& token = path[index];
141
148
            TrieNode* node = get_child(token);
142
148
            if (node == nullptr) {
143
23
                node = get_child(_wildcard);
144
23
                if (node == nullptr) {
145
3
                    return false;
146
3
                }
147
20
                use_wildcard = true;
148
125
            } else {
149
                // If we the last one, but we have no value, check wildcard
150
125
                if (index == path.size() - 1 && node->_value == nullptr &&
151
125
                    get_child(_wildcard) != nullptr) {
152
0
                    node = get_child(_wildcard);
153
0
                    use_wildcard = true;
154
125
                } else {
155
125
                    use_wildcard = (token.compare(_wildcard) == 0);
156
125
                }
157
125
            }
158
159
145
            put(params, node, token);
160
161
145
            if (index == path.size() - 1) {
162
63
                if (node->_value == nullptr) {
163
0
                    return false;
164
0
                }
165
63
                _allocator.construct(value, *node->_value);
166
63
                return true;
167
63
            }
168
169
            // find exact
170
82
            if (node->retrieve(path, index + 1, value, params)) {
171
80
                return true;
172
80
            }
173
174
            // backtrace to test if wildcard can match
175
2
            if (!use_wildcard) {
176
2
                node = get_child(_wildcard);
177
2
                if (node != nullptr) {
178
0
                    put(params, node, token);
179
0
                    return node->retrieve(path, index + 1, value, params);
180
0
                }
181
2
            }
182
2
            return false;
183
2
        }
_ZN5doris8PathTrieIiE8TrieNode8retrieveESt6vectorINSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEESaIS9_EEiPiPSt3mapIS9_S9_St4lessIS9_ESaISt4pairIKS9_S9_EEE
Line
Count
Source
134
29
                      std::map<std::string, std::string>* params) {
135
            // check max index
136
29
            if (index >= path.size()) {
137
0
                return false;
138
0
            }
139
29
            bool use_wildcard = false;
140
29
            const std::string& token = path[index];
141
29
            TrieNode* node = get_child(token);
142
29
            if (node == nullptr) {
143
9
                node = get_child(_wildcard);
144
9
                if (node == nullptr) {
145
2
                    return false;
146
2
                }
147
7
                use_wildcard = true;
148
20
            } else {
149
                // If we the last one, but we have no value, check wildcard
150
20
                if (index == path.size() - 1 && node->_value == nullptr &&
151
20
                    get_child(_wildcard) != nullptr) {
152
0
                    node = get_child(_wildcard);
153
0
                    use_wildcard = true;
154
20
                } else {
155
20
                    use_wildcard = (token.compare(_wildcard) == 0);
156
20
                }
157
20
            }
158
159
27
            put(params, node, token);
160
161
27
            if (index == path.size() - 1) {
162
10
                if (node->_value == nullptr) {
163
0
                    return false;
164
0
                }
165
10
                _allocator.construct(value, *node->_value);
166
10
                return true;
167
10
            }
168
169
            // find exact
170
17
            if (node->retrieve(path, index + 1, value, params)) {
171
15
                return true;
172
15
            }
173
174
            // backtrace to test if wildcard can match
175
2
            if (!use_wildcard) {
176
2
                node = get_child(_wildcard);
177
2
                if (node != nullptr) {
178
0
                    put(params, node, token);
179
0
                    return node->retrieve(path, index + 1, value, params);
180
0
                }
181
2
            }
182
2
            return false;
183
2
        }
_ZN5doris8PathTrieIPNS_11HttpHandlerEE8TrieNode8retrieveESt6vectorINSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEESaISB_EEiPS2_PSt3mapISB_SB_St4lessISB_ESaISt4pairIKSB_SB_EEE
Line
Count
Source
134
119
                      std::map<std::string, std::string>* params) {
135
            // check max index
136
119
            if (index >= path.size()) {
137
0
                return false;
138
0
            }
139
119
            bool use_wildcard = false;
140
119
            const std::string& token = path[index];
141
119
            TrieNode* node = get_child(token);
142
119
            if (node == nullptr) {
143
14
                node = get_child(_wildcard);
144
14
                if (node == nullptr) {
145
1
                    return false;
146
1
                }
147
13
                use_wildcard = true;
148
105
            } else {
149
                // If we the last one, but we have no value, check wildcard
150
105
                if (index == path.size() - 1 && node->_value == nullptr &&
151
105
                    get_child(_wildcard) != nullptr) {
152
0
                    node = get_child(_wildcard);
153
0
                    use_wildcard = true;
154
105
                } else {
155
105
                    use_wildcard = (token.compare(_wildcard) == 0);
156
105
                }
157
105
            }
158
159
118
            put(params, node, token);
160
161
118
            if (index == path.size() - 1) {
162
53
                if (node->_value == nullptr) {
163
0
                    return false;
164
0
                }
165
53
                _allocator.construct(value, *node->_value);
166
53
                return true;
167
53
            }
168
169
            // find exact
170
65
            if (node->retrieve(path, index + 1, value, params)) {
171
65
                return true;
172
65
            }
173
174
            // backtrace to test if wildcard can match
175
0
            if (!use_wildcard) {
176
0
                node = get_child(_wildcard);
177
0
                if (node != nullptr) {
178
0
                    put(params, node, token);
179
0
                    return node->retrieve(path, index + 1, value, params);
180
0
                }
181
0
            }
182
0
            return false;
183
0
        }
184
185
    private:
186
361
        bool is_named_wildcard(const std::string& key) {
187
361
            if (key.find('{') != std::string::npos && key.find('}') != std::string::npos) {
188
50
                return true;
189
50
            }
190
311
            return false;
191
361
        }
_ZN5doris8PathTrieIiE8TrieNode17is_named_wildcardERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE
Line
Count
Source
186
67
        bool is_named_wildcard(const std::string& key) {
187
67
            if (key.find('{') != std::string::npos && key.find('}') != std::string::npos) {
188
12
                return true;
189
12
            }
190
55
            return false;
191
67
        }
_ZN5doris8PathTrieIPNS_11HttpHandlerEE8TrieNode17is_named_wildcardERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE
Line
Count
Source
186
294
        bool is_named_wildcard(const std::string& key) {
187
294
            if (key.find('{') != std::string::npos && key.find('}') != std::string::npos) {
188
38
                return true;
189
38
            }
190
256
            return false;
191
294
        }
192
193
25
        std::string extract_template(const std::string& key) {
194
25
            std::size_t left = key.find_first_of('{') + 1;
195
25
            std::size_t right = key.find_last_of('}');
196
25
            return key.substr(left, right - left);
197
25
        }
_ZN5doris8PathTrieIiE8TrieNode16extract_templateERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE
Line
Count
Source
193
6
        std::string extract_template(const std::string& key) {
194
6
            std::size_t left = key.find_first_of('{') + 1;
195
6
            std::size_t right = key.find_last_of('}');
196
6
            return key.substr(left, right - left);
197
6
        }
_ZN5doris8PathTrieIPNS_11HttpHandlerEE8TrieNode16extract_templateERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE
Line
Count
Source
193
19
        std::string extract_template(const std::string& key) {
194
19
            std::size_t left = key.find_first_of('{') + 1;
195
19
            std::size_t right = key.find_last_of('}');
196
19
            return key.substr(left, right - left);
197
19
        }
198
199
341
        TrieNode* get_child(const std::string& key) {
200
341
            auto pair = _children.find(key);
201
341
            if (pair == _children.end()) {
202
143
                return nullptr;
203
143
            }
204
198
            return pair->second;
205
341
        }
_ZN5doris8PathTrieIiE8TrieNode9get_childERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE
Line
Count
Source
199
70
        TrieNode* get_child(const std::string& key) {
200
70
            auto pair = _children.find(key);
201
70
            if (pair == _children.end()) {
202
30
                return nullptr;
203
30
            }
204
40
            return pair->second;
205
70
        }
_ZN5doris8PathTrieIPNS_11HttpHandlerEE8TrieNode9get_childERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE
Line
Count
Source
199
271
        TrieNode* get_child(const std::string& key) {
200
271
            auto pair = _children.find(key);
201
271
            if (pair == _children.end()) {
202
113
                return nullptr;
203
113
            }
204
158
            return pair->second;
205
271
        }
206
207
        void put(std::map<std::string, std::string>* params, TrieNode* node,
208
145
                 const std::string& token) {
209
145
            if (params != nullptr && !node->_named_wildcard.empty()) {
210
17
                params->insert(std::make_pair(node->_named_wildcard, token));
211
17
            }
212
145
        }
_ZN5doris8PathTrieIiE8TrieNode3putEPSt3mapINSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEES9_St4lessIS9_ESaISt4pairIKS9_S9_EEEPS2_RSD_
Line
Count
Source
208
27
                 const std::string& token) {
209
27
            if (params != nullptr && !node->_named_wildcard.empty()) {
210
4
                params->insert(std::make_pair(node->_named_wildcard, token));
211
4
            }
212
27
        }
_ZN5doris8PathTrieIPNS_11HttpHandlerEE8TrieNode3putEPSt3mapINSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEESB_St4lessISB_ESaISt4pairIKSB_SB_EEEPS4_RSF_
Line
Count
Source
208
118
                 const std::string& token) {
209
118
            if (params != nullptr && !node->_named_wildcard.empty()) {
210
13
                params->insert(std::make_pair(node->_named_wildcard, token));
211
13
            }
212
118
        }
213
214
        T* _value;
215
        std::string _wildcard;
216
        std::string _named_wildcard;
217
        std::map<std::string, TrieNode*> _children;
218
        Allocator _allocator;
219
    };
220
221
76
    bool insert(const std::string& path, const T& value) {
222
76
        std::vector<std::string> path_array;
223
76
        split(path, &path_array);
224
76
        if (path_array.empty()) {
225
3
            if (_root_value == nullptr) {
226
2
                _root_value = _allocator.allocate(1);
227
2
                _allocator.construct(_root_value, value);
228
2
                return true;
229
2
            } else {
230
1
                return false;
231
1
            }
232
3
        }
233
73
        int index = 0;
234
73
        if (path_array[0].empty()) {
235
0
            index = 1;
236
0
        }
237
73
        return _root.insert(path_array, index, value);
238
76
    }
_ZN5doris8PathTrieIiE6insertERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEERKi
Line
Count
Source
221
14
    bool insert(const std::string& path, const T& value) {
222
14
        std::vector<std::string> path_array;
223
14
        split(path, &path_array);
224
14
        if (path_array.empty()) {
225
2
            if (_root_value == nullptr) {
226
1
                _root_value = _allocator.allocate(1);
227
1
                _allocator.construct(_root_value, value);
228
1
                return true;
229
1
            } else {
230
1
                return false;
231
1
            }
232
2
        }
233
12
        int index = 0;
234
12
        if (path_array[0].empty()) {
235
0
            index = 1;
236
0
        }
237
12
        return _root.insert(path_array, index, value);
238
14
    }
_ZN5doris8PathTrieIPNS_11HttpHandlerEE6insertERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEERKS2_
Line
Count
Source
221
62
    bool insert(const std::string& path, const T& value) {
222
62
        std::vector<std::string> path_array;
223
62
        split(path, &path_array);
224
62
        if (path_array.empty()) {
225
1
            if (_root_value == nullptr) {
226
1
                _root_value = _allocator.allocate(1);
227
1
                _allocator.construct(_root_value, value);
228
1
                return true;
229
1
            } else {
230
0
                return false;
231
0
            }
232
1
        }
233
61
        int index = 0;
234
61
        if (path_array[0].empty()) {
235
0
            index = 1;
236
0
        }
237
61
        return _root.insert(path_array, index, value);
238
62
    }
239
240
9
    bool retrieve(const std::string& path, T* value) { return retrieve(path, value, nullptr); }
241
242
68
    bool retrieve(const std::string& path, T* value, std::map<std::string, std::string>* params) {
243
68
        if (path.empty()) {
244
1
            if (_root_value == nullptr) {
245
0
                return false;
246
1
            } else {
247
1
                _allocator.construct(value, *_root_value);
248
1
                return true;
249
1
            }
250
1
        }
251
67
        std::vector<std::string> path_array;
252
67
        split(path, &path_array);
253
67
        if (path_array.empty()) {
254
1
            if (_root_value == nullptr) {
255
0
                return false;
256
1
            } else {
257
1
                _allocator.construct(value, *_root_value);
258
1
                return true;
259
1
            }
260
1
        }
261
66
        int index = 0;
262
66
        if (path_array[0].empty()) {
263
0
            index = 1;
264
0
        }
265
66
        return _root.retrieve(path_array, index, value, params);
266
67
    }
_ZN5doris8PathTrieIiE8retrieveERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEEPiPSt3mapIS7_S7_St4lessIS7_ESaISt4pairIS8_S7_EEE
Line
Count
Source
242
14
    bool retrieve(const std::string& path, T* value, std::map<std::string, std::string>* params) {
243
14
        if (path.empty()) {
244
1
            if (_root_value == nullptr) {
245
0
                return false;
246
1
            } else {
247
1
                _allocator.construct(value, *_root_value);
248
1
                return true;
249
1
            }
250
1
        }
251
13
        std::vector<std::string> path_array;
252
13
        split(path, &path_array);
253
13
        if (path_array.empty()) {
254
1
            if (_root_value == nullptr) {
255
0
                return false;
256
1
            } else {
257
1
                _allocator.construct(value, *_root_value);
258
1
                return true;
259
1
            }
260
1
        }
261
12
        int index = 0;
262
12
        if (path_array[0].empty()) {
263
0
            index = 1;
264
0
        }
265
12
        return _root.retrieve(path_array, index, value, params);
266
13
    }
_ZN5doris8PathTrieIPNS_11HttpHandlerEE8retrieveERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEEPS2_PSt3mapIS9_S9_St4lessIS9_ESaISt4pairISA_S9_EEE
Line
Count
Source
242
54
    bool retrieve(const std::string& path, T* value, std::map<std::string, std::string>* params) {
243
54
        if (path.empty()) {
244
0
            if (_root_value == nullptr) {
245
0
                return false;
246
0
            } else {
247
0
                _allocator.construct(value, *_root_value);
248
0
                return true;
249
0
            }
250
0
        }
251
54
        std::vector<std::string> path_array;
252
54
        split(path, &path_array);
253
54
        if (path_array.empty()) {
254
0
            if (_root_value == nullptr) {
255
0
                return false;
256
0
            } else {
257
0
                _allocator.construct(value, *_root_value);
258
0
                return true;
259
0
            }
260
0
        }
261
54
        int index = 0;
262
54
        if (path_array[0].empty()) {
263
0
            index = 1;
264
0
        }
265
54
        return _root.retrieve(path_array, index, value, params);
266
54
    }
267
268
private:
269
147
    void split(const std::string& path, std::vector<std::string>* array) {
270
147
        const char* path_str = path.c_str();
271
147
        std::size_t start = 0;
272
147
        std::size_t pos = 0;
273
2.62k
        for (; pos < path.length(); ++pos) {
274
2.47k
            if (path_str[pos] == _separator) {
275
330
                if (pos - start > 0) {
276
184
                    array->push_back(path.substr(start, pos - start));
277
184
                }
278
330
                start = pos + 1;
279
330
            }
280
2.47k
        }
281
147
        if (pos - start > 0) {
282
141
            array->push_back(path.substr(start, pos - start));
283
141
        }
284
147
    }
_ZN5doris8PathTrieIiE5splitERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEEPSt6vectorIS7_SaIS7_EE
Line
Count
Source
269
31
    void split(const std::string& path, std::vector<std::string>* array) {
270
31
        const char* path_str = path.c_str();
271
31
        std::size_t start = 0;
272
31
        std::size_t pos = 0;
273
343
        for (; pos < path.length(); ++pos) {
274
312
            if (path_str[pos] == _separator) {
275
74
                if (pos - start > 0) {
276
42
                    array->push_back(path.substr(start, pos - start));
277
42
                }
278
74
                start = pos + 1;
279
74
            }
280
312
        }
281
31
        if (pos - start > 0) {
282
26
            array->push_back(path.substr(start, pos - start));
283
26
        }
284
31
    }
_ZN5doris8PathTrieIPNS_11HttpHandlerEE5splitERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEEPSt6vectorIS9_SaIS9_EE
Line
Count
Source
269
116
    void split(const std::string& path, std::vector<std::string>* array) {
270
116
        const char* path_str = path.c_str();
271
116
        std::size_t start = 0;
272
116
        std::size_t pos = 0;
273
2.28k
        for (; pos < path.length(); ++pos) {
274
2.16k
            if (path_str[pos] == _separator) {
275
256
                if (pos - start > 0) {
276
142
                    array->push_back(path.substr(start, pos - start));
277
142
                }
278
256
                start = pos + 1;
279
256
            }
280
2.16k
        }
281
116
        if (pos - start > 0) {
282
115
            array->push_back(path.substr(start, pos - start));
283
115
        }
284
116
    }
285
286
    TrieNode _root;
287
    T* _root_value;
288
    char _separator;
289
    Allocator _allocator;
290
};
291
292
} // namespace doris