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 30 namespace perfetto { 31 namespace { 32 33 constexpr 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. 52 class 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
