tp: implement an implicit segment-tree like data structure
This CL implements an implicit variant of a segment-tree [1] most
closely described by [2].
This data structure will be used in upcoming CLs to compute aggregations
over events in large traces for the UI, significantly speeding up
the queries UI makes against trace processor.
[1] https://en.algorithmica.org/hpc/data-structures/segment-trees/
[2] https://thume.ca/2021/03/14/iforests/
Change-Id: I9fe71b67985b1c777733407136e95900f6e9c5a3
diff --git a/Android.bp b/Android.bp
index 6cb0053..db1ef89 100644
--- a/Android.bp
+++ b/Android.bp
@@ -11304,6 +11304,7 @@
name: "perfetto_src_trace_processor_containers_unittests",
srcs: [
"src/trace_processor/containers/bit_vector_unittest.cc",
+ "src/trace_processor/containers/implicit_segment_forest_unittest.cc",
"src/trace_processor/containers/null_term_string_view_unittest.cc",
"src/trace_processor/containers/row_map_unittest.cc",
"src/trace_processor/containers/string_pool_unittest.cc",
