chromium/third_party/perfetto/src/trace_processor/containers/implicit_segment_forest.h

/*
 * Copyright (C) 2024 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef SRC_TRACE_PROCESSOR_CONTAINERS_IMPLICIT_SEGMENT_FOREST_H_
#define SRC_TRACE_PROCESSOR_CONTAINERS_IMPLICIT_SEGMENT_FOREST_H_

#include <cstddef>
#include <cstdint>
#include <vector>

#include "perfetto/base/logging.h"

namespace perfetto::trace_processor {

// An implementation of a segment tree data structure [1] with:
// 1) parent-child relationships are implicit, saving memory.
// 2) the requirement for the number of values being a power of two, turning
//    the tree into a forest.
//
// Segment trees are a very powerful data structure allowing O(log(n)) aggregate
// queries to be performed on an arbitrary range of elements in an array.
// Specifically, for `T x[n]`, and an associative and commutative operation
// AggOp (e.g. +, *, min, max, etc.), segment trees can compute
// ```
//   T y = AggOp()(x[i], x[i + 1], x[i + 2], ..., x[j])
// ```
// in O(log(n)) time.
//
// Practically, in trace processor, this is useful for computing aggregations
// over events in a trace. For example:
// ```
// struct Slice { int64_t ts; int64_t dur; };
// struct MaxDurSlice {
//   Slice operator()(const Slice& a, const Slice& b) {
//     return a.dur < b.dur ? b : a;
//   }
// }
// using MipMap = ImplicitSegmentForest<Slice, MaxDurSlice>;
// ```
// allows building a "mipmap" [2] of a track in a trace in a UI. The UI can show
// a representation of the items in the track when very zoomed out while
// skipping the rendering slices which are smaller than one pixel.
//
// The design and implementation of this class takes heavy inspiration from
// Tristan Hume's "IForestIndex" data structure [3] as described in his blog
// post [4].
//
// [1] https://en.algorithmica.org/hpc/data-structures/segment-trees/
// [2] https://en.wikipedia.org/wiki/Mipmap
// [3]
// https://github.com/trishume/gigatrace/blob/dfde0d7244f356bdc9aeefb387d904dd8b09d94a/src/iforest.rs
// [4] https://thume.ca/2021/03/14/iforests/
template <typename T, typename AggOp>
class ImplicitSegmentForest { … };

}  // namespace perfetto::trace_processor

#endif  // SRC_TRACE_PROCESSOR_CONTAINERS_IMPLICIT_SEGMENT_FOREST_H_