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