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,Node * parent)51 Node(std::string name, Node* parent) : name_(name), parent_(parent) {} 52 53 Node(const Node& that) = delete; 54 Node& operator=(const Node&) = delete; 55 56 // Return string representation of prefix, e.g. /foo/bar. 57 // Does not enclude a trailing /. 58 std::string ToString() const; 59 60 private: 61 class CompareNames { 62 public: 63 // ONLY USE CONST MEMBERS IN THIS AS WE ARE USING MUTABLE POINTERS 64 // TO SET ELEMENTS. operator()65 bool operator()(const Node& one, const Node& other) const { 66 return one.name_ < other.name_; 67 } 68 }; 69 70 // Add a new child to this node. 71 Node* AddChild(std::string name); 72 73 // Get existing child for this node. Return nullptr if it 74 // does not exist. 75 Node* MaybeChild(const std::string& name); 76 77 const std::string name_; 78 const Node* parent_; 79 std::set<Node, CompareNames> children_; 80 }; 81 82 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