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 #ifndef SRC_TRACED_PROBES_FILESYSTEM_PREFIX_FINDER_H_ 18 #define SRC_TRACED_PROBES_FILESYSTEM_PREFIX_FINDER_H_ 19 20 #include <memory> 21 #include <set> 22 #include <string> 23 #include <tuple> 24 #include <utility> 25 #include <vector> 26 27 #include "perfetto/base/logging.h" 28 29 namespace perfetto { 30 31 // PrefixFinder allows to find prefixes for filenames that ensure that 32 // they can be found again within a provided limit of steps when searching 33 // within that prefix in the same order. 34 // 35 // For instance, let the limit be 4 and the filesystem be. 36 // /a/1 37 // /a/2 38 // /a/3 39 // /b/4 40 // /b/5 41 // 42 // The prefix for /a/1, /a/2 and /a/3/ is /, the one for /b/4 and /b/5 is /b/. 43 class PrefixFinder { 44 public: 45 // Opaque placeholder for a prefix that can be turned into a string 46 // using ToString. 47 // Can not be constructed outside of PrefixFinder. 48 class Node { 49 public: 50 friend class PrefixFinder; Node(std::string name)51 Node(std::string name) : Node(std::move(name), nullptr) {} Node(std::string name,Node * parent)52 Node(std::string name, Node* parent) 53 : name_(std::move(name)), parent_(parent) {} 54 55 Node(const Node& that) = delete; 56 Node& operator=(const Node&) = delete; 57 58 // Return string representation of prefix, e.g. /foo/bar. 59 // Does not include a trailing /. 60 std::string ToString() const; 61 62 private: 63 // Add a new child to this node. 64 Node* AddChild(std::string name); 65 66 // Get existing child for this node. Return nullptr if it 67 // does not exist. 68 Node* MaybeChild(const std::string& name); 69 70 const std::string name_; 71 const Node* parent_; 72 class NodeComparator { 73 public: operator()74 bool operator()(const Node& one, const Node& other) const { 75 return one.name_ < other.name_; 76 } 77 }; 78 79 std::set<Node, NodeComparator> children_; 80 }; 81 82 explicit PrefixFinder(size_t limit); 83 84 // Add path to prefix mapping. 85 // Must be called in DFS order. 86 // Must be called before GetPrefix(path) for the same path. 87 // Must not be called after Finalize. 88 void AddPath(std::string path); 89 90 // Return identifier for prefix. Ownership remains with the PrefixFinder. 91 // Must be called after AddPath(path) for the same path. 92 // Must not be before after Finalize. 93 Node* GetPrefix(std::string path); 94 95 // Call this after the last AddPath and before the first GetPrefix. 96 void Finalize(); 97 98 private: 99 // We're about to remove the suffix of state from i onwards, 100 // if necessary add a prefix for anything in that suffix. 101 void Flush(size_t i); 102 void InsertPrefix(size_t len); 103 const size_t limit_; 104 // (path element, count) tuples for last path seen. 105 std::vector<std::pair<std::string, size_t>> state_{{"", 0}}; 106 Node root_{"", nullptr}; 107 #if PERFETTO_DCHECK_IS_ON() 108 bool finalized_ = false; 109 #endif 110 }; 111 112 } // namespace perfetto 113 #endif // SRC_TRACED_PROBES_FILESYSTEM_PREFIX_FINDER_H_ 114