The Tor Browser: comparison gfx/skia/trunk/src/core/SkRTree.h

--1:000000000000
+:faef2f53f46d
+/*
+* Copyright 2012 Google Inc.
+*
+* Use of this source code is governed by a BSD-style license that can be
+* found in the LICENSE file.
+*/
+#ifndef SkRTree_DEFINED
+#define SkRTree_DEFINED
+#include "SkRect.h"
+#include "SkTDArray.h"
+#include "SkChunkAlloc.h"
+#include "SkBBoxHierarchy.h"
+/**
+* An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of
+* bounding rectangles.
+*
+* Much like a B-Tree it maintains balance by enforcing minimum and maximum child counts, and
+* splitting nodes when they become overfull. Unlike B-trees, however, we're using spatial data; so
+* there isn't a canonical ordering to use when choosing insertion locations and splitting
+* distributions. A variety of heuristics have been proposed for these problems; here, we're using
+* something resembling an R*-tree, which attempts to minimize area and overlap during insertion,
+* and aims to minimize a combination of margin, overlap, and area when splitting.
+*
+* One detail that is thus far unimplemented that may improve tree quality is attempting to remove
+* and reinsert nodes when they become full, instead of immediately splitting (nodes that may have
+* been placed well early on may hurt the tree later when more nodes have been added; removing
+* and reinserting nodes generally helps reduce overlap and make a better tree). Deletion of nodes
+* is also unimplemented.
+*
+* 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"
+*
+* It also supports bulk-loading from a batch of bounds and values; if you don't require the tree
+* to be usable in its intermediate states while it is being constructed, this is significantly
+* quicker than individual insertions and produces more consistent trees.
+*/
+class SkRTree : public SkBBoxHierarchy {
+public:
+SK_DECLARE_INST_COUNT(SkRTree)
+/**
+* Create a new R-Tree with specified min/max child counts.
+* The child counts are valid iff:
+* - (max + 1) / 2 >= min (splitting an overfull node must be enough to populate 2 nodes)
+* - min < max
+* - min > 0
+* - max < SK_MaxU16
+* If you have some prior information about the distribution of bounds you're expecting, you
+* can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to create
+* better proportioned tiles of rectangles.
+*/
+static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRatio = 1,
+bool orderWhenBulkLoading = true);
+virtual ~SkRTree();
+/**
+* Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
+* need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load
+* a large batch of nodes at once, which tends to be faster and produce a better tree).
+*  @param data The data value
+*  @param bounds The corresponding bounding box
+*  @param defer Can this insert be deferred? (this may be ignored)
+*/
+virtual void insert(void* data, const SkIRect& bounds, bool defer = false) SK_OVERRIDE;
+/**
+* If any inserts have been deferred, this will add them into the tree
+*/
+virtual void flushDeferredInserts() SK_OVERRIDE;
+/**
+* Given a query rectangle, populates the passed-in array with the elements it intersects
+*/
+virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;
+virtual void clear() SK_OVERRIDE;
+bool isEmpty() const { return 0 == fCount; }
+/**
+* Gets the depth of the tree structure
+*/
+virtual int getDepth() const SK_OVERRIDE {
+return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1;
+}
+/**
+* This gets the insertion count (rather than the node count)
+*/
+virtual int getCount() const SK_OVERRIDE { return fCount; }
+virtual void rewindInserts() SK_OVERRIDE;
+private:
+struct Node;
+/**
+* A branch of the tree, this may contain a pointer to another interior node, or a data value
+*/
+struct Branch {
+union {
+Node* subtree;
+void* data;
+} fChild;
+SkIRect fBounds;
+};
+/**
+* A node in the tree, has between fMinChildren and fMaxChildren (the root is a special case)
+*/
+struct Node {
+uint16_t fNumChildren;
+uint16_t fLevel;
+bool isLeaf() { return 0 == fLevel; }
+// Since we want to be able to pick min/max child counts at runtime, we assume the creator
+// has allocated sufficient space directly after us in memory, and index into that space
+Branch* child(size_t index) {
+return reinterpret_cast<Branch*>(this + 1) + index;
+}
+};
+typedef int32_t SkIRect::*SortSide;
+// Helper for sorting our children arrays by sides of their rects
+struct RectLessThan {
+RectLessThan(SkRTree::SortSide side) : fSide(side) { }
+bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) const {
+return lhs.fBounds.*fSide < rhs.fBounds.*fSide;
+}
+private:
+const SkRTree::SortSide fSide;
+};
+struct RectLessX {
+bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) {
+return ((lhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1) <
+((rhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1);
+}
+};
+struct RectLessY {
+bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) {
+return ((lhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1) <
+((rhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1);
+}
+};
+SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio, bool orderWhenBulkLoading);
+/**
+* Recursively descend the tree to find an insertion position for 'branch', updates
+* bounding boxes on the way up.
+*/
+Branch* insert(Node* root, Branch* branch, uint16_t level = 0);
+int chooseSubtree(Node* root, Branch* branch);
+SkIRect computeBounds(Node* n);
+int distributeChildren(Branch* children);
+void search(Node* root, const SkIRect query, SkTDArray<void*>* results) const;
+/**
+* This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm, this
+* seems to generally produce better, more consistent trees at significantly lower cost than
+* repeated insertions.
+*
+* This consumes the input array.
+*
+* TODO: 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).
+*/
+Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0);
+void validate();
+int validateSubtree(Node* root, SkIRect bounds, bool isRoot = false);
+const int fMinChildren;
+const int fMaxChildren;
+const size_t fNodeSize;
+// This is the count of data elements (rather than total nodes in the tree)
+int fCount;
+Branch fRoot;
+SkChunkAlloc fNodes;
+SkTDArray<Branch> fDeferredInserts;
+SkScalar fAspectRatio;
+bool fSortWhenBulkLoading;
+Node* allocateNode(uint16_t level);
+typedef SkBBoxHierarchy INHERITED;
+};
+#endif

The Tor Browser / file comparison

comparison: gfx/skia/trunk/src/core/SkRTree.h

gfx/skia/trunk/src/core/SkRTree.h