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
29namespace 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/.
43class 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;
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.
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