1 /* 2 * Copyright (C) 2024 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_TRACE_PROCESSOR_CONTAINERS_INTERVAL_TREE_H_ 18 #define SRC_TRACE_PROCESSOR_CONTAINERS_INTERVAL_TREE_H_ 19 20 #include <algorithm> 21 #include <cstdint> 22 #include <limits> 23 #include <map> 24 #include <memory> 25 #include <optional> 26 #include <set> 27 #include <vector> 28 #include "perfetto/base/logging.h" 29 #include "perfetto/ext/base/small_vector.h" 30 31 namespace perfetto::trace_processor { 32 33 using Ts = uint64_t; 34 using Id = uint32_t; 35 36 // An implementation of a centered interval tree data structure, designed to 37 // efficiently find all overlap queries on a set of intervals. Centered interval 38 // tree has a build complexity of O(N*logN) and a query time of O(logN + k), 39 // where k is the number of overlaps in the dataset. 40 class IntervalTree { 41 public: 42 // Maps to one trace processor slice. 43 struct Interval { 44 Ts start; 45 Ts end; 46 Id id; 47 }; 48 49 // Creates an interval tree from the vector of intervals. IntervalTree(const std::vector<Interval> & sorted_intervals)50 explicit IntervalTree(const std::vector<Interval>& sorted_intervals) { 51 nodes_.reserve(sorted_intervals.size()); 52 Node root_node(sorted_intervals.data(), sorted_intervals.size(), nodes_); 53 nodes_.emplace_back(std::move(root_node)); 54 root_ = nodes_.size() - 1; 55 } 56 57 // Modifies |res| to contain Interval::Id of all intervals that overlap 58 // interval (s, e). Has a complexity of O(log(size of tree) + (number of 59 // overlaps)). FindOverlaps(uint64_t s,uint64_t e,std::vector<Id> & res)60 void FindOverlaps(uint64_t s, uint64_t e, std::vector<Id>& res) const { 61 std::vector<const Node*> stack{nodes_.data() + root_}; 62 while (!stack.empty()) { 63 const Node* n = stack.back(); 64 stack.pop_back(); 65 66 for (const Interval& i : n->intervals_) { 67 // As we know that each interval overlaps the center, if the interval 68 // starts after the |end| we know [start,end] can't intersect the 69 // center. 70 if (i.start > e) { 71 break; 72 } 73 74 if (e > i.start && s < i.end) { 75 res.push_back(i.id); 76 } 77 } 78 79 if (e > n->center_ && 80 n->right_node_ != std::numeric_limits<size_t>::max()) { 81 stack.push_back(&nodes_[n->right_node_]); 82 } 83 if (s < n->center_ && 84 n->left_node_ != std::numeric_limits<size_t>::max()) { 85 stack.push_back(&nodes_[n->left_node_]); 86 } 87 } 88 } 89 90 private: 91 struct Node { 92 base::SmallVector<Interval, 2> intervals_; 93 uint64_t center_ = 0; 94 size_t left_node_ = std::numeric_limits<size_t>::max(); 95 size_t right_node_ = std::numeric_limits<size_t>::max(); 96 NodeNode97 explicit Node(const Interval* intervals, 98 size_t intervals_size, 99 std::vector<Node>& nodes) { 100 const Interval& mid_interval = intervals[intervals_size / 2]; 101 center_ = (mid_interval.start + mid_interval.end) / 2; 102 103 // Find intervals that overlap the center_ and intervals that belong to 104 // the left node (finish before the center_). If an interval starts after 105 // the center break and assign all remining intervals to the right node. 106 // We can do this as the provided intervals are in sorted order. 107 std::vector<Interval> left; 108 for (uint32_t i = 0; i < intervals_size; i++) { 109 const Interval& inter = intervals[i]; 110 // Starts after the center. As intervals are sorted on timestamp we 111 // know the rest of intervals will go to the right node. 112 if (inter.start > center_) { 113 Node n(intervals + i, intervals_size - i, nodes); 114 nodes.emplace_back(std::move(n)); 115 right_node_ = nodes.size() - 1; 116 break; 117 } 118 119 // Finishes before the center. 120 if (inter.end < center_) { 121 left.push_back(intervals[i]); 122 } else { 123 // Overlaps the center. 124 intervals_.emplace_back(intervals[i]); 125 } 126 } 127 128 if (!left.empty()) { 129 Node n(left.data(), left.size(), nodes); 130 nodes.emplace_back(std::move(n)); 131 left_node_ = nodes.size() - 1; 132 } 133 } 134 135 Node(const Node&) = delete; 136 Node& operator=(const Node&) = delete; 137 138 Node(Node&&) = default; 139 Node& operator=(Node&&) = default; 140 }; 141 142 size_t root_; 143 std::vector<Node> nodes_; 144 }; 145 146 } // namespace perfetto::trace_processor 147 148 #endif // SRC_TRACE_PROCESSOR_CONTAINERS_INTERVAL_TREE_H_ 149