1b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer/* 2b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * Copyright (C) 2018 The Android Open Source Project 3b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * 4b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * Licensed under the Apache License, Version 2.0 (the "License"); 5b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * you may not use this file except in compliance with the License. 6b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * You may obtain a copy of the License at 7b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * 8b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * http://www.apache.org/licenses/LICENSE-2.0 9b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * 10b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * Unless required by applicable law or agreed to in writing, software 11b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * distributed under the License is distributed on an "AS IS" BASIS, 12b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * See the License for the specific language governing permissions and 14b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer * limitations under the License. 15b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer */ 16b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 17b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#include <map> 18b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#include <set> 19b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#include <sstream> 20b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 21b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#include <stdio.h> 22b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 23b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#include "perfetto/base/small_set.h" 24b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#include "src/traced/probes/filesystem/inode_file_data_source.h" 25b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#include "src/traced/probes/filesystem/prefix_finder.h" 26b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 27b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#ifndef SRC_TRACED_PROBES_FILESYSTEM_RANGE_TREE_H_ 28b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#define SRC_TRACED_PROBES_FILESYSTEM_RANGE_TREE_H_ 29b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 30b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayernamespace perfetto { 31b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayernamespace { 32b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 33b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayerconstexpr size_t kSetSize = 3; 34b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 35b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer} // namespace 36b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 37b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// Keep key value associations in ranges. Keeps kSetSize=3 possible values 38b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// for every key, where one is the correct one. 39b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// For instance, 40b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// 1 -> a 41b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// 2 -> b 42b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// 3 -> c 43b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// 4 -> d 44b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// 45b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// will be stored as 46b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// [1, 4) {a, b, c} 47b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// [4, inf) {d} 48b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// 49b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// This comes from the observation that close-by inode numbers tend to be 50b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// in the same directory. We are storing multiple values to be able to 51b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer// aggregate to larger ranges and reduce memory usage. 52b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayerclass RangeTree { 53b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer public: 54b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer using DataType = PrefixFinder::Node*; 55b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 56b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer const std::set<std::string> Get(Inode inode); 57b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer void Insert(Inode inode, DataType value); 58b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 59b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer private: 60b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer std::map<Inode, SmallSet<DataType, kSetSize>> map_; 61b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer}; 62b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 63b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer} // namespace perfetto 64b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer 65b21f4fb9463f40cb840a1c7a31c51422445fb8ccFlorian Mayer#endif // SRC_TRACED_PROBES_FILESYSTEM_RANGE_TREE_H_ 66