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#include <map>
18#include <set>
19#include <sstream>
20
21#include <stdio.h>
22
23#include "perfetto/base/small_set.h"
24#include "src/traced/probes/filesystem/inode_file_data_source.h"
25#include "src/traced/probes/filesystem/prefix_finder.h"
26
27#ifndef SRC_TRACED_PROBES_FILESYSTEM_RANGE_TREE_H_
28#define SRC_TRACED_PROBES_FILESYSTEM_RANGE_TREE_H_
29
30namespace perfetto {
31namespace {
32
33constexpr size_t kSetSize = 3;
34
35}  // namespace
36
37// Keep key value associations in ranges. Keeps kSetSize=3 possible values
38// for every key, where one is the correct one.
39// For instance,
40// 1 -> a
41// 2 -> b
42// 3 -> c
43// 4 -> d
44//
45// will be stored as
46// [1, 4) {a, b, c}
47// [4, inf) {d}
48//
49// This comes from the observation that close-by inode numbers tend to be
50// in the same directory. We are storing multiple values to be able to
51// aggregate to larger ranges and reduce memory usage.
52class RangeTree {
53 public:
54  using DataType = PrefixFinder::Node*;
55
56  const std::set<std::string> Get(Inode inode);
57  void Insert(Inode inode, DataType value);
58
59 private:
60  std::map<Inode, SmallSet<DataType, kSetSize>> map_;
61};
62
63}  // namespace perfetto
64
65#endif  // SRC_TRACED_PROBES_FILESYSTEM_RANGE_TREE_H_
66