The Tor Browser: gfx/skia/trunk/src/core/SkRTree.h@6474c204b198 (annotated)

gfx/skia/trunk/src/core/SkRTree.h@6474c204b198 (annotated)

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

Wed, 31 Dec 2014 06:09:35 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Wed, 31 Dec 2014 06:09:35 +0100
changeset 0: 6474c204b198
permissions: -rw-r--r--

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

 /*
  * 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 / annotate

gfx/skia/trunk/src/core/SkRTree.h@6474c204b198 (annotated)

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