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