1 /*
2 * Copyright (C) 2018 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "src/traced/probes/filesystem/prefix_finder.h"
18 #include "perfetto/base/logging.h"
19 #include "perfetto/base/string_splitter.h"
20
21 namespace perfetto {
22
ToString() const23 std::string PrefixFinder::Node::ToString() const {
24 if (parent_ != nullptr)
25 return parent_->ToString() + "/" + name_;
26 return name_;
27 }
28
AddChild(std::string name)29 PrefixFinder::Node* PrefixFinder::Node::AddChild(std::string name) {
30 auto p = children_.emplace(std::move(name), this);
31 PERFETTO_DCHECK(p.second);
32 // This is fine as long as the comparator only uses const members of Node.
33 return const_cast<Node*>(&(*p.first));
34 }
35
MaybeChild(const std::string & name)36 PrefixFinder::Node* PrefixFinder::Node::MaybeChild(const std::string& name) {
37 // This will be nicer with C++14 transparent comparators.
38 // Then we will be able to look up by just the name using a sutiable
39 // comparator.
40 Node search_node(name, nullptr);
41 auto it = children_.find(search_node);
42 if (it == children_.end())
43 return nullptr;
44 // This is fine as long as the comparator only uses const members of Node.
45 return const_cast<Node*>(&(*it));
46 }
47
PrefixFinder(size_t limit)48 PrefixFinder::PrefixFinder(size_t limit) : limit_(limit) {}
49
InsertPrefix(size_t len)50 void PrefixFinder::InsertPrefix(size_t len) {
51 Node* cur = &root_;
52 for (auto it = state_.cbegin() + 1;
53 it != state_.cbegin() + static_cast<ssize_t>(len + 1); it++) {
54 Node* next = cur->MaybeChild(it->first);
55 if (!next)
56 next = cur->AddChild(it->first);
57 cur = next;
58 }
59 }
60
Flush(size_t i)61 void PrefixFinder::Flush(size_t i) {
62 PERFETTO_CHECK(i > 0);
63 for (size_t j = i; j < state_.size(); ++j) {
64 if (state_[j - 1].second > limit_ && state_[j].second <= limit_) {
65 InsertPrefix(i);
66 break;
67 }
68 }
69 }
70
Finalize()71 void PrefixFinder::Finalize() {
72 Flush(1);
73 state_.resize(1);
74 #if PERFETTO_DCHECK_IS_ON()
75 PERFETTO_DCHECK(!finalized_);
76 finalized_ = true;
77 #endif
78 }
79
AddPath(std::string path)80 void PrefixFinder::AddPath(std::string path) {
81 perfetto::base::StringSplitter s(std::move(path), '/');
82 // An artificial element for the root directory.
83 // This simplifies the logic below because we can always assume
84 // there is a parent element.
85 state_[0].second++;
86 for (size_t i = 1; s.Next(); ++i) {
87 char* token = s.cur_token();
88 if (i < state_.size()) {
89 std::pair<std::string, size_t>& elem = state_[i];
90 if (elem.first == token) {
91 elem.second++;
92 } else {
93 // Check if we need to write a prefix for any element
94 // in the previous state.
95 Flush(i);
96 elem.first = token;
97 elem.second = 1;
98 state_.resize(i + 1);
99 }
100 } else {
101 state_.emplace_back(token, 1);
102 }
103 }
104 }
105
GetPrefix(std::string path)106 PrefixFinder::Node* PrefixFinder::GetPrefix(std::string path) {
107 #if PERFETTO_DCHECK_IS_ON()
108 PERFETTO_DCHECK(finalized_);
109 #endif
110 perfetto::base::StringSplitter s(std::move(path), '/');
111 Node* cur = &root_;
112 for (size_t i = 0; s.Next(); ++i) {
113 char* token = s.cur_token();
114 Node* next = cur->MaybeChild(token);
115 if (next == nullptr)
116 break;
117 cur = next;
118 PERFETTO_DCHECK(cur->name_ == token);
119 }
120 return cur;
121 }
122
123 } // namespace perfetto
124