1b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer/* 2b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * Copyright (C) 2018 The Android Open Source Project 3b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * 4b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * Licensed under the Apache License, Version 2.0 (the "License"); 5b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * you may not use this file except in compliance with the License. 6b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * You may obtain a copy of the License at 7b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * 8b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * http://www.apache.org/licenses/LICENSE-2.0 9b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * 10b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * Unless required by applicable law or agreed to in writing, software 11b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * distributed under the License is distributed on an "AS IS" BASIS, 12b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * See the License for the specific language governing permissions and 14b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * limitations under the License. 15b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer */ 16b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 17b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#ifndef SRC_TRACED_PROBES_FILESYSTEM_PREFIX_FINDER_H_ 18b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#define SRC_TRACED_PROBES_FILESYSTEM_PREFIX_FINDER_H_ 19b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 20b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#include <memory> 2173ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer#include <set> 22b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#include <string> 23b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#include <tuple> 24b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#include <utility> 25b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#include <vector> 26b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 27b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#include "perfetto/base/logging.h" 28b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 29b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayernamespace perfetto { 30b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 31b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// PrefixFinder allows to find prefixes for filenames that ensure that 32b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// they can be found again within a provided limit of steps when searching 33b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// within that prefix in the same order. 34b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// 35b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// For instance, let the limit be 4 and the filesystem be. 36b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// /a/1 37b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// /a/2 38b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// /a/3 39b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// /b/4 40b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// /b/5 41b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// 42b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// The prefix for /a/1, /a/2 and /a/3/ is /, the one for /b/4 and /b/5 is /b/. 43b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayerclass PrefixFinder { 44b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer public: 45b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer // Opaque placeholder for a prefix that can be turned into a string 46b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer // using ToString. 47b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer // Can not be constructed outside of PrefixFinder. 48b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer class Node { 49b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer public: 50b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer friend class PrefixFinder; 5173ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer Node(std::string name, Node* parent) : name_(name), parent_(parent) {} 52b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 53b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer Node(const Node& that) = delete; 54b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer Node& operator=(const Node&) = delete; 55b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 56b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer // Return string representation of prefix, e.g. /foo/bar. 57b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer // Does not enclude a trailing /. 5873ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer std::string ToString() const; 59b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 60b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer private: 6173ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer class CompareNames { 6273ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer public: 6373ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer // ONLY USE CONST MEMBERS IN THIS AS WE ARE USING MUTABLE POINTERS 6473ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer // TO SET ELEMENTS. 6573ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer bool operator()(const Node& one, const Node& other) const { 6673ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer return one.name_ < other.name_; 6773ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer } 6873ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer }; 6973ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer 7073ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer // Add a new child to this node. 7173ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer Node* AddChild(std::string name); 72b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 7373ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer // Get existing child for this node. Return nullptr if it 7473ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer // does not exist. 75b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer Node* MaybeChild(const std::string& name); 76b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 7773ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer const std::string name_; 7873ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer const Node* parent_; 7973ec13354b5f0f6faec6b8184dff56036d49d3d0Florian Mayer std::set<Node, CompareNames> children_; 80b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer }; 81b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 82b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer PrefixFinder(size_t limit); 83b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 84b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer // Add path to prefix mapping. 85b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer // Must be called in DFS order. 86b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer // Must be called before GetPrefix(path) for the same path. 87b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer // Must not be called after Finalize. 88b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer void AddPath(std::string path); 89b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 90b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer // Return identifier for prefix. Ownership remains with the PrefixFinder. 91b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer // Must be called after AddPath(path) for the same path. 92b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer // Must not be before after Finalize. 93b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer Node* GetPrefix(std::string path); 94b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 95b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer // Call this after the last AddPath and before the first GetPrefix. 96b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer void Finalize(); 97b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 98b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer private: 99b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer // We're about to remove the suffix of state from i onwards, 100b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer // if necessary add a prefix for anything in that suffix. 101b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer void Flush(size_t i); 102b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer void InsertPrefix(size_t len); 103b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer const size_t limit_; 104b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer // (path element, count) tuples for last path seen. 105b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer std::vector<std::pair<std::string, size_t>> state_{{"", 0}}; 106b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer Node root_{"", nullptr}; 107b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#if PERFETTO_DCHECK_IS_ON() 108b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer bool finalized_ = false; 109b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#endif 110b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer}; 111b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 112b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer} // namespace perfetto 113b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#endif // SRC_TRACED_PROBES_FILESYSTEM_PREFIX_FINDER_H_ 114