diff -r 000000000000 -r 6474c204b198 gfx/skia/trunk/src/core/SkRTree.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gfx/skia/trunk/src/core/SkRTree.cpp	Wed Dec 31 06:09:35 2014 +0100
@@ -0,0 +1,482 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkRTree.h"
+#include "SkTSort.h"
+
+static inline uint32_t get_area(const SkIRect& rect);
+static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2);
+static inline uint32_t get_margin(const SkIRect& rect);
+static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2);
+static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out);
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+SkRTree* SkRTree::Create(int minChildren, int maxChildren, SkScalar aspectRatio,
+            bool sortWhenBulkLoading) {
+    if (minChildren < maxChildren && (maxChildren + 1) / 2 >= minChildren &&
+        minChildren > 0 && maxChildren < static_cast<int>(SK_MaxU16)) {
+        return new SkRTree(minChildren, maxChildren, aspectRatio, sortWhenBulkLoading);
+    }
+    return NULL;
+}
+
+SkRTree::SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio,
+        bool sortWhenBulkLoading)
+    : fMinChildren(minChildren)
+    , fMaxChildren(maxChildren)
+    , fNodeSize(sizeof(Node) + sizeof(Branch) * maxChildren)
+    , fCount(0)
+    , fNodes(fNodeSize * 256)
+    , fAspectRatio(aspectRatio)
+    , fSortWhenBulkLoading(sortWhenBulkLoading) {
+    SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren <
+             static_cast<int>(SK_MaxU16));
+    SkASSERT((maxChildren + 1) / 2 >= minChildren);
+    this->validate();
+}
+
+SkRTree::~SkRTree() {
+    this->clear();
+}
+
+void SkRTree::insert(void* data, const SkIRect& bounds, bool defer) {
+    this->validate();
+    if (bounds.isEmpty()) {
+        SkASSERT(false);
+        return;
+    }
+    Branch newBranch;
+    newBranch.fBounds = bounds;
+    newBranch.fChild.data = data;
+    if (this->isEmpty()) {
+        // since a bulk-load into an existing tree is as of yet unimplemented (and arguably not
+        // of vital importance right now), we only batch up inserts if the tree is empty.
+        if (defer) {
+            fDeferredInserts.push(newBranch);
+            return;
+        } else {
+            fRoot.fChild.subtree = allocateNode(0);
+            fRoot.fChild.subtree->fNumChildren = 0;
+        }
+    }
+
+    Branch* newSibling = insert(fRoot.fChild.subtree, &newBranch);
+    fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
+
+    if (NULL != newSibling) {
+        Node* oldRoot = fRoot.fChild.subtree;
+        Node* newRoot = this->allocateNode(oldRoot->fLevel + 1);
+        newRoot->fNumChildren = 2;
+        *newRoot->child(0) = fRoot;
+        *newRoot->child(1) = *newSibling;
+        fRoot.fChild.subtree = newRoot;
+        fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
+    }
+
+    ++fCount;
+    this->validate();
+}
+
+void SkRTree::flushDeferredInserts() {
+    this->validate();
+    if (this->isEmpty() && fDeferredInserts.count() > 0) {
+        fCount = fDeferredInserts.count();
+        if (1 == fCount) {
+            fRoot.fChild.subtree = allocateNode(0);
+            fRoot.fChild.subtree->fNumChildren = 0;
+            this->insert(fRoot.fChild.subtree, &fDeferredInserts[0]);
+            fRoot.fBounds = fDeferredInserts[0].fBounds;
+        } else {
+            fRoot = this->bulkLoad(&fDeferredInserts);
+        }
+    } else {
+        // TODO: some algorithm for bulk loading into an already populated tree
+        SkASSERT(0 == fDeferredInserts.count());
+    }
+    fDeferredInserts.rewind();
+    this->validate();
+}
+
+void SkRTree::search(const SkIRect& query, SkTDArray<void*>* results) {
+    this->validate();
+    if (0 != fDeferredInserts.count()) {
+        this->flushDeferredInserts();
+    }
+    if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query)) {
+        this->search(fRoot.fChild.subtree, query, results);
+    }
+    this->validate();
+}
+
+void SkRTree::clear() {
+    this->validate();
+    fNodes.reset();
+    fDeferredInserts.rewind();
+    fCount = 0;
+    this->validate();
+}
+
+SkRTree::Node* SkRTree::allocateNode(uint16_t level) {
+    Node* out = static_cast<Node*>(fNodes.allocThrow(fNodeSize));
+    out->fNumChildren = 0;
+    out->fLevel = level;
+    return out;
+}
+
+SkRTree::Branch* SkRTree::insert(Node* root, Branch* branch, uint16_t level) {
+    Branch* toInsert = branch;
+    if (root->fLevel != level) {
+        int childIndex = this->chooseSubtree(root, branch);
+        toInsert = this->insert(root->child(childIndex)->fChild.subtree, branch, level);
+        root->child(childIndex)->fBounds = this->computeBounds(
+            root->child(childIndex)->fChild.subtree);
+    }
+    if (NULL != toInsert) {
+        if (root->fNumChildren == fMaxChildren) {
+            // handle overflow by splitting. TODO: opportunistic reinsertion
+
+            // decide on a distribution to divide with
+            Node* newSibling = this->allocateNode(root->fLevel);
+            Branch* toDivide = SkNEW_ARRAY(Branch, fMaxChildren + 1);
+            for (int i = 0; i < fMaxChildren; ++i) {
+                toDivide[i] = *root->child(i);
+            }
+            toDivide[fMaxChildren] = *toInsert;
+            int splitIndex = this->distributeChildren(toDivide);
+
+            // divide up the branches
+            root->fNumChildren = splitIndex;
+            newSibling->fNumChildren = fMaxChildren + 1 - splitIndex;
+            for (int i = 0; i < splitIndex; ++i) {
+                *root->child(i) = toDivide[i];
+            }
+            for (int i = splitIndex; i < fMaxChildren + 1; ++i) {
+                *newSibling->child(i - splitIndex) = toDivide[i];
+            }
+            SkDELETE_ARRAY(toDivide);
+
+            // pass the new sibling branch up to the parent
+            branch->fChild.subtree = newSibling;
+            branch->fBounds = this->computeBounds(newSibling);
+            return branch;
+        } else {
+            *root->child(root->fNumChildren) = *toInsert;
+            ++root->fNumChildren;
+            return NULL;
+        }
+    }
+    return NULL;
+}
+
+int SkRTree::chooseSubtree(Node* root, Branch* branch) {
+    SkASSERT(!root->isLeaf());
+    if (1 < root->fLevel) {
+        // root's child pointers do not point to leaves, so minimize area increase
+        int32_t minAreaIncrease = SK_MaxS32;
+        int32_t minArea         = SK_MaxS32;
+        int32_t bestSubtree     = -1;
+        for (int i = 0; i < root->fNumChildren; ++i) {
+            const SkIRect& subtreeBounds = root->child(i)->fBounds;
+            int32_t areaIncrease = get_area_increase(subtreeBounds, branch->fBounds);
+            // break ties in favor of subtree with smallest area
+            if (areaIncrease < minAreaIncrease || (areaIncrease == minAreaIncrease &&
+                static_cast<int32_t>(get_area(subtreeBounds)) < minArea)) {
+                minAreaIncrease = areaIncrease;
+                minArea = get_area(subtreeBounds);
+                bestSubtree = i;
+            }
+        }
+        SkASSERT(-1 != bestSubtree);
+        return bestSubtree;
+    } else if (1 == root->fLevel) {
+        // root's child pointers do point to leaves, so minimize overlap increase
+        int32_t minOverlapIncrease = SK_MaxS32;
+        int32_t minAreaIncrease    = SK_MaxS32;
+        int32_t bestSubtree = -1;
+        for (int32_t i = 0; i < root->fNumChildren; ++i) {
+            const SkIRect& subtreeBounds = root->child(i)->fBounds;
+            SkIRect expandedBounds = subtreeBounds;
+            join_no_empty_check(branch->fBounds, &expandedBounds);
+            int32_t overlap = 0;
+            for (int32_t j = 0; j < root->fNumChildren; ++j) {
+                if (j == i) continue;
+                // Note: this would be more correct if we subtracted the original pre-expanded
+                // overlap, but computing overlaps is expensive and omitting it doesn't seem to
+                // hurt query performance. See get_overlap_increase()
+                overlap += get_overlap(expandedBounds, root->child(j)->fBounds);
+            }
+            // break ties with lowest area increase
+            if (overlap < minOverlapIncrease || (overlap == minOverlapIncrease &&
+                static_cast<int32_t>(get_area_increase(branch->fBounds, subtreeBounds)) <
+                minAreaIncrease)) {
+                minOverlapIncrease = overlap;
+                minAreaIncrease = get_area_increase(branch->fBounds, subtreeBounds);
+                bestSubtree = i;
+            }
+        }
+        return bestSubtree;
+    } else {
+        SkASSERT(false);
+        return 0;
+    }
+}
+
+SkIRect SkRTree::computeBounds(Node* n) {
+    SkIRect r = n->child(0)->fBounds;
+    for (int i = 1; i < n->fNumChildren; ++i) {
+        join_no_empty_check(n->child(i)->fBounds, &r);
+    }
+    return r;
+}
+
+int SkRTree::distributeChildren(Branch* children) {
+    // We have two sides to sort by on each of two axes:
+    const static SortSide sorts[2][2] = {
+        {&SkIRect::fLeft, &SkIRect::fRight},
+        {&SkIRect::fTop, &SkIRect::fBottom}
+    };
+
+    // We want to choose an axis to split on, then a distribution along that axis; we'll need
+    // three pieces of info: the split axis, the side to sort by on that axis, and the index
+    // to split the sorted array on.
+    int32_t sortSide = -1;
+    int32_t k        = -1;
+    int32_t axis     = -1;
+    int32_t bestS    = SK_MaxS32;
+
+    // Evaluate each axis, we want the min summed margin-value (s) over all distributions
+    for (int i = 0; i < 2; ++i) {
+        int32_t minOverlap   = SK_MaxS32;
+        int32_t minArea      = SK_MaxS32;
+        int32_t axisBestK    = 0;
+        int32_t axisBestSide = 0;
+        int32_t s = 0;
+
+        // Evaluate each sort
+        for (int j = 0; j < 2; ++j) {
+            SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[i][j]));
+
+            // Evaluate each split index
+            for (int32_t k = 1; k <= fMaxChildren - 2 * fMinChildren + 2; ++k) {
+                SkIRect r1 = children[0].fBounds;
+                SkIRect r2 = children[fMinChildren + k - 1].fBounds;
+                for (int32_t l = 1; l < fMinChildren - 1 + k; ++l) {
+                    join_no_empty_check(children[l].fBounds, &r1);
+                }
+                for (int32_t l = fMinChildren + k; l < fMaxChildren + 1; ++l) {
+                    join_no_empty_check(children[l].fBounds, &r2);
+                }
+
+                int32_t area = get_area(r1) + get_area(r2);
+                int32_t overlap = get_overlap(r1, r2);
+                s += get_margin(r1) + get_margin(r2);
+
+                if (overlap < minOverlap || (overlap == minOverlap && area < minArea)) {
+                    minOverlap = overlap;
+                    minArea = area;
+                    axisBestSide = j;
+                    axisBestK = k;
+                }
+            }
+        }
+
+        if (s < bestS) {
+            bestS = s;
+            axis = i;
+            sortSide = axisBestSide;
+            k = axisBestK;
+        }
+    }
+
+    // replicate the sort of the winning distribution, (we can skip this if the last
+    // sort ended up being best)
+    if (!(axis == 1 && sortSide == 1)) {
+        SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[axis][sortSide]));
+    }
+
+    return fMinChildren - 1 + k;
+}
+
+void SkRTree::search(Node* root, const SkIRect query, SkTDArray<void*>* results) const {
+    for (int i = 0; i < root->fNumChildren; ++i) {
+        if (SkIRect::IntersectsNoEmptyCheck(root->child(i)->fBounds, query)) {
+            if (root->isLeaf()) {
+                results->push(root->child(i)->fChild.data);
+            } else {
+                this->search(root->child(i)->fChild.subtree, query, results);
+            }
+        }
+    }
+}
+
+SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
+    if (branches->count() == 1) {
+        // Only one branch: it will be the root
+        Branch out = (*branches)[0];
+        branches->rewind();
+        return out;
+    } else {
+        // We sort the whole list by y coordinates, if we are told to do so.
+        //
+        // We expect Webkit / Blink to give us a reasonable x,y order.
+        // Avoiding this call resulted in a 17% win for recording with
+        // negligible difference in playback speed.
+        if (fSortWhenBulkLoading) {
+            SkTQSort(branches->begin(), branches->end() - 1, RectLessY());
+        }
+
+        int numBranches = branches->count() / fMaxChildren;
+        int remainder = branches->count() % fMaxChildren;
+        int newBranches = 0;
+
+        if (0 != remainder) {
+            ++numBranches;
+            // If the remainder isn't enough to fill a node, we'll need to add fewer nodes to
+            // some other branches to make up for it
+            if (remainder >= fMinChildren) {
+                remainder = 0;
+            } else {
+                remainder = fMinChildren - remainder;
+            }
+        }
+
+        int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) *
+                                     SkScalarInvert(fAspectRatio)));
+        int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) /
+                                    SkIntToScalar(numStrips));
+        int currentBranch = 0;
+
+        for (int i = 0; i < numStrips; ++i) {
+            // Once again, if we are told to do so, we sort by x.
+            if (fSortWhenBulkLoading) {
+                int begin = currentBranch;
+                int end = currentBranch + numTiles * fMaxChildren - SkMin32(remainder,
+                        (fMaxChildren - fMinChildren) * numTiles);
+                if (end > branches->count()) {
+                    end = branches->count();
+                }
+
+                // Now we sort horizontal strips of rectangles by their x coords
+                SkTQSort(branches->begin() + begin, branches->begin() + end - 1, RectLessX());
+            }
+
+            for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) {
+                int incrementBy = fMaxChildren;
+                if (remainder != 0) {
+                    // if need be, omit some nodes to make up for remainder
+                    if (remainder <= fMaxChildren - fMinChildren) {
+                        incrementBy -= remainder;
+                        remainder = 0;
+                    } else {
+                        incrementBy = fMinChildren;
+                        remainder -= fMaxChildren - fMinChildren;
+                    }
+                }
+                Node* n = allocateNode(level);
+                n->fNumChildren = 1;
+                *n->child(0) = (*branches)[currentBranch];
+                Branch b;
+                b.fBounds = (*branches)[currentBranch].fBounds;
+                b.fChild.subtree = n;
+                ++currentBranch;
+                for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) {
+                    b.fBounds.join((*branches)[currentBranch].fBounds);
+                    *n->child(k) = (*branches)[currentBranch];
+                    ++n->fNumChildren;
+                    ++currentBranch;
+                }
+                (*branches)[newBranches] = b;
+                ++newBranches;
+            }
+        }
+        branches->setCount(newBranches);
+        return this->bulkLoad(branches, level + 1);
+    }
+}
+
+void SkRTree::validate() {
+#ifdef SK_DEBUG
+    if (this->isEmpty()) {
+        return;
+    }
+    SkASSERT(fCount == this->validateSubtree(fRoot.fChild.subtree, fRoot.fBounds, true));
+#endif
+}
+
+int SkRTree::validateSubtree(Node* root, SkIRect bounds, bool isRoot) {
+    // make sure the pointer is pointing to a valid place
+    SkASSERT(fNodes.contains(static_cast<void*>(root)));
+
+    if (isRoot) {
+        // If the root of this subtree is the overall root, we have looser standards:
+        if (root->isLeaf()) {
+            SkASSERT(root->fNumChildren >= 1 && root->fNumChildren <= fMaxChildren);
+        } else {
+            SkASSERT(root->fNumChildren >= 2 && root->fNumChildren <= fMaxChildren);
+        }
+    } else {
+        SkASSERT(root->fNumChildren >= fMinChildren && root->fNumChildren <= fMaxChildren);
+    }
+
+    for (int i = 0; i < root->fNumChildren; ++i) {
+        SkASSERT(bounds.contains(root->child(i)->fBounds));
+    }
+
+    if (root->isLeaf()) {
+        SkASSERT(0 == root->fLevel);
+        return root->fNumChildren;
+    } else {
+        int childCount = 0;
+        for (int i = 0; i < root->fNumChildren; ++i) {
+            SkASSERT(root->child(i)->fChild.subtree->fLevel == root->fLevel - 1);
+            childCount += this->validateSubtree(root->child(i)->fChild.subtree,
+                                                root->child(i)->fBounds);
+        }
+        return childCount;
+    }
+}
+
+void SkRTree::rewindInserts() {
+    SkASSERT(this->isEmpty()); // Currently only supports deferred inserts
+    while (!fDeferredInserts.isEmpty() &&
+           fClient->shouldRewind(fDeferredInserts.top().fChild.data)) {
+        fDeferredInserts.pop();
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+static inline uint32_t get_area(const SkIRect& rect) {
+    return rect.width() * rect.height();
+}
+
+static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2) {
+    // I suspect there's a more efficient way of computing this...
+    return SkMax32(0, SkMin32(rect1.fRight, rect2.fRight) - SkMax32(rect1.fLeft, rect2.fLeft)) *
+           SkMax32(0, SkMin32(rect1.fBottom, rect2.fBottom) - SkMax32(rect1.fTop, rect2.fTop));
+}
+
+// Get the margin (aka perimeter)
+static inline uint32_t get_margin(const SkIRect& rect) {
+    return 2 * (rect.width() + rect.height());
+}
+
+static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2) {
+    join_no_empty_check(rect1, &rect2);
+    return get_area(rect2) - get_area(rect1);
+}
+
+// Expand 'out' to include 'joinWith'
+static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) {
+    // since we check for empty bounds on insert, we know we'll never have empty rects
+    // and we can save the empty check that SkIRect::join requires
+    if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; }
+    if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; }
+    if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; }
+    if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; }
+}