chromium/cc/base/rtree.h

// Copyright 2015 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifdef UNSAFE_BUFFERS_BUILD
// TODO(crbug.com/351564777): Remove this and convert code to safer constructs.
#pragma allow_unsafe_buffers
#endif

#ifndef CC_BASE_RTREE_H_
#define CC_BASE_RTREE_H_

#include <stddef.h>
#include <stdint.h>

#include <algorithm>
#include <cmath>
#include <map>
#include <optional>
#include <utility>
#include <vector>

#include "base/check_op.h"
#include "base/memory/raw_ptr_exclusion.h"
#include "base/numerics/clamped_math.h"
#include "ui/gfx/geometry/rect.h"

namespace cc {

// The following description and most of the implementation is borrowed from
// Skia's SkRTree implementation.
//
// An R-Tree implementation. In short, it is a balanced n-ary tree containing a
// hierarchy of bounding rectangles.
//
// It only supports bulk-loading, i.e. creation from a batch of bounding
// rectangles. This performs a bottom-up bulk load using the STR
// (sort-tile-recursive) algorithm.
//
// Things to do: Experiment with other bulk-load algorithms (in particular the
// Hilbert pack variant, which groups rects by position on the Hilbert curve, is
// probably worth a look). There also exist top-down bulk load variants
// (VAMSplit, TopDownGreedy, etc).
//
// For more details see:
//
//  Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990).
//  "The R*-tree: an efficient and robust access method for points and
//  rectangles"
template <typename T>
class RTree { … };

template <typename T>
RTree<T>::RTree() = default;

template <typename T>
RTree<T>::~RTree() = default;

template <typename T>
template <typename Container>
void RTree<T>::Build(const Container& items) { … }

template <typename T>
template <typename BoundsFunctor, typename PayloadFunctor>
void RTree<T>::Build(size_t item_count,
                     const BoundsFunctor& bounds_getter,
                     const PayloadFunctor& payload_getter) { … }

template <typename T>
auto RTree<T>::AllocateNodeAtLevel(int level) -> Node<T>* { … }

template <typename T>
auto RTree<T>::BuildRecursive(std::vector<Branch<T>>* branches, int level)
    -> Branch<T> { … }

template <typename T>
template <typename ResultFunctor>
void RTree<T>::Search(const gfx::Rect& query,
                      const ResultFunctor& result_handler) const { … }

template <typename T>
void RTree<T>::Search(const gfx::Rect& query,
                      std::vector<T>* results,
                      std::vector<gfx::Rect>* rects) const { … }

template <typename T>
void RTree<T>::SearchRefs(const gfx::Rect& query,
                          std::vector<const T*>* results) const { … }

template <typename T>
template <typename ResultFunctor>
void RTree<T>::SearchRecursive(Node<T>* node,
                               const gfx::Rect& query,
                               const ResultFunctor& result_handler) const { … }

// When !has_valid_bounds(), any non-leaf bounds may have overflowed and be
// invalid. Iterate over the entire tree, checking bounds at each leaf.
template <typename T>
template <typename ResultFunctor>
void RTree<T>::SearchRecursiveFallback(
    Node<T>* node,
    const gfx::Rect& query,
    const ResultFunctor& result_handler) const { … }

template <typename T>
std::optional<gfx::Rect> RTree<T>::bounds() const { … }

template <typename T>
std::map<T, gfx::Rect> RTree<T>::GetAllBoundsForTracing() const { … }

template <typename T>
void RTree<T>::GetAllBoundsRecursive(Node<T>* node,
                                     std::map<T, gfx::Rect>* results) const { … }

}  // namespace cc

#endif  // CC_BASE_RTREE_H_