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/ext/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 it = children_.emplace(std::move(name), this);
31   return const_cast<Node*>(&(*it.first));
32 }
33 
MaybeChild(const std::string & name)34 PrefixFinder::Node* PrefixFinder::Node::MaybeChild(const std::string& name) {
35   // This will be nicer with C++14 transparent comparators.
36   // Then we will be able to look up by just the key using a sutiable
37   // comparator.
38   //
39   // For now we need to allow to construct Node from the key.
40   Node node(name);
41   auto it = children_.find(node);
42   if (it == children_.end())
43     return nullptr;
44   return const_cast<Node*>(&(*it));
45 }
46 
PrefixFinder(size_t limit)47 PrefixFinder::PrefixFinder(size_t limit) : limit_(limit) {}
48 
InsertPrefix(size_t len)49 void PrefixFinder::InsertPrefix(size_t len) {
50   Node* cur = &root_;
51   for (auto it = state_.cbegin() + 1;
52        it != state_.cbegin() + static_cast<ssize_t>(len + 1); it++) {
53     Node* next = cur->MaybeChild(it->first);
54     if (!next)
55       next = cur->AddChild(it->first);
56     cur = next;
57   }
58 }
59 
Flush(size_t i)60 void PrefixFinder::Flush(size_t i) {
61   PERFETTO_CHECK(i > 0);
62   for (size_t j = i; j < state_.size(); ++j) {
63     if (state_[j - 1].second > limit_ && state_[j].second <= limit_) {
64       InsertPrefix(i);
65       break;
66     }
67   }
68 }
69 
Finalize()70 void PrefixFinder::Finalize() {
71   Flush(1);
72   state_.resize(1);
73 #if PERFETTO_DCHECK_IS_ON()
74   PERFETTO_DCHECK(!finalized_);
75   finalized_ = true;
76 #endif
77 }
78 
AddPath(std::string path)79 void PrefixFinder::AddPath(std::string path) {
80   perfetto::base::StringSplitter s(std::move(path), '/');
81   // An artificial element for the root directory.
82   // This simplifies the logic below because we can always assume
83   // there is a parent element.
84   state_[0].second++;
85   for (size_t i = 1; s.Next(); ++i) {
86     char* token = s.cur_token();
87     if (i < state_.size()) {
88       std::pair<std::string, size_t>& elem = state_[i];
89       if (elem.first == token) {
90         elem.second++;
91       } else {
92         // Check if we need to write a prefix for any element
93         // in the previous state.
94         Flush(i);
95         elem.first = token;
96         elem.second = 1;
97         state_.resize(i + 1);
98       }
99     } else {
100       state_.emplace_back(token, 1);
101     }
102   }
103 }
104 
GetPrefix(std::string path)105 PrefixFinder::Node* PrefixFinder::GetPrefix(std::string path) {
106 #if PERFETTO_DCHECK_IS_ON()
107   PERFETTO_DCHECK(finalized_);
108 #endif
109   perfetto::base::StringSplitter s(std::move(path), '/');
110   Node* cur = &root_;
111   for (size_t i = 0; s.Next(); ++i) {
112     char* token = s.cur_token();
113     Node* next = cur->MaybeChild(token);
114     if (next == nullptr)
115       break;
116     cur = next;
117     PERFETTO_DCHECK(cur->name_ == token);
118   }
119   return cur;
120 }
121 
122 }  // namespace perfetto
123