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