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() const23std::string PrefixFinder::Node::ToString() const { 24 if (parent_ != nullptr) 25 return parent_->ToString() + "/" + name_; 26 return name_; 27 } 28 AddChild(std::string name)29PrefixFinder::Node* PrefixFinder::Node::AddChild(std::string name) { 30 return children_.Emplace(std::move(name), this); 31 } 32 MaybeChild(const std::string & name)33PrefixFinder::Node* PrefixFinder::Node::MaybeChild(const std::string& name) { 34 return children_.Get(name); 35 } 36 PrefixFinder(size_t limit)37PrefixFinder::PrefixFinder(size_t limit) : limit_(limit) {} 38 InsertPrefix(size_t len)39void PrefixFinder::InsertPrefix(size_t len) { 40 Node* cur = &root_; 41 for (auto it = state_.cbegin() + 1; 42 it != state_.cbegin() + static_cast<ssize_t>(len + 1); it++) { 43 Node* next = cur->MaybeChild(it->first); 44 if (!next) 45 next = cur->AddChild(it->first); 46 cur = next; 47 } 48 } 49 Flush(size_t i)50void PrefixFinder::Flush(size_t i) { 51 PERFETTO_CHECK(i > 0); 52 for (size_t j = i; j < state_.size(); ++j) { 53 if (state_[j - 1].second > limit_ && state_[j].second <= limit_) { 54 InsertPrefix(i); 55 break; 56 } 57 } 58 } 59 Finalize()60void PrefixFinder::Finalize() { 61 Flush(1); 62 state_.resize(1); 63 #if PERFETTO_DCHECK_IS_ON() 64 PERFETTO_DCHECK(!finalized_); 65 finalized_ = true; 66 #endif 67 } 68 AddPath(std::string path)69void PrefixFinder::AddPath(std::string path) { 70 perfetto::base::StringSplitter s(std::move(path), '/'); 71 // An artificial element for the root directory. 72 // This simplifies the logic below because we can always assume 73 // there is a parent element. 74 state_[0].second++; 75 for (size_t i = 1; s.Next(); ++i) { 76 char* token = s.cur_token(); 77 if (i < state_.size()) { 78 std::pair<std::string, size_t>& elem = state_[i]; 79 if (elem.first == token) { 80 elem.second++; 81 } else { 82 // Check if we need to write a prefix for any element 83 // in the previous state. 84 Flush(i); 85 elem.first = token; 86 elem.second = 1; 87 state_.resize(i + 1); 88 } 89 } else { 90 state_.emplace_back(token, 1); 91 } 92 } 93 } 94 GetPrefix(std::string path)95PrefixFinder::Node* PrefixFinder::GetPrefix(std::string path) { 96 #if PERFETTO_DCHECK_IS_ON() 97 PERFETTO_DCHECK(finalized_); 98 #endif 99 perfetto::base::StringSplitter s(std::move(path), '/'); 100 Node* cur = &root_; 101 for (size_t i = 0; s.Next(); ++i) { 102 char* token = s.cur_token(); 103 Node* next = cur->MaybeChild(token); 104 if (next == nullptr) 105 break; 106 cur = next; 107 PERFETTO_DCHECK(cur->name_ == token); 108 } 109 return cur; 110 } 111 112 } // namespace perfetto 113