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

Tue, 06 Jan 2015 21:39:09 +0100

author
Michael Schloh von Bennewitz <michael@schloh.com>
date
Tue, 06 Jan 2015 21:39:09 +0100
branch
TOR_BUG_9701
changeset 8
97036ab72558
permissions
-rw-r--r--

Conditionally force memory storage according to privacy.thirdparty.isolate;
This solves Tor bug #9701, complying with disk avoidance documented in
https://www.torproject.org/projects/torbrowser/design/#disk-avoidance.

     1 /*
     2  * Copyright 2012 Google Inc.
     3  *
     4  * Use of this source code is governed by a BSD-style license that can be
     5  * found in the LICENSE file.
     6  */
     8 #include "SkRTree.h"
     9 #include "SkTSort.h"
    11 static inline uint32_t get_area(const SkIRect& rect);
    12 static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2);
    13 static inline uint32_t get_margin(const SkIRect& rect);
    14 static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2);
    15 static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out);
    17 ///////////////////////////////////////////////////////////////////////////////////////////////////
    19 SkRTree* SkRTree::Create(int minChildren, int maxChildren, SkScalar aspectRatio,
    20             bool sortWhenBulkLoading) {
    21     if (minChildren < maxChildren && (maxChildren + 1) / 2 >= minChildren &&
    22         minChildren > 0 && maxChildren < static_cast<int>(SK_MaxU16)) {
    23         return new SkRTree(minChildren, maxChildren, aspectRatio, sortWhenBulkLoading);
    24     }
    25     return NULL;
    26 }
    28 SkRTree::SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio,
    29         bool sortWhenBulkLoading)
    30     : fMinChildren(minChildren)
    31     , fMaxChildren(maxChildren)
    32     , fNodeSize(sizeof(Node) + sizeof(Branch) * maxChildren)
    33     , fCount(0)
    34     , fNodes(fNodeSize * 256)
    35     , fAspectRatio(aspectRatio)
    36     , fSortWhenBulkLoading(sortWhenBulkLoading) {
    37     SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren <
    38              static_cast<int>(SK_MaxU16));
    39     SkASSERT((maxChildren + 1) / 2 >= minChildren);
    40     this->validate();
    41 }
    43 SkRTree::~SkRTree() {
    44     this->clear();
    45 }
    47 void SkRTree::insert(void* data, const SkIRect& bounds, bool defer) {
    48     this->validate();
    49     if (bounds.isEmpty()) {
    50         SkASSERT(false);
    51         return;
    52     }
    53     Branch newBranch;
    54     newBranch.fBounds = bounds;
    55     newBranch.fChild.data = data;
    56     if (this->isEmpty()) {
    57         // since a bulk-load into an existing tree is as of yet unimplemented (and arguably not
    58         // of vital importance right now), we only batch up inserts if the tree is empty.
    59         if (defer) {
    60             fDeferredInserts.push(newBranch);
    61             return;
    62         } else {
    63             fRoot.fChild.subtree = allocateNode(0);
    64             fRoot.fChild.subtree->fNumChildren = 0;
    65         }
    66     }
    68     Branch* newSibling = insert(fRoot.fChild.subtree, &newBranch);
    69     fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
    71     if (NULL != newSibling) {
    72         Node* oldRoot = fRoot.fChild.subtree;
    73         Node* newRoot = this->allocateNode(oldRoot->fLevel + 1);
    74         newRoot->fNumChildren = 2;
    75         *newRoot->child(0) = fRoot;
    76         *newRoot->child(1) = *newSibling;
    77         fRoot.fChild.subtree = newRoot;
    78         fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
    79     }
    81     ++fCount;
    82     this->validate();
    83 }
    85 void SkRTree::flushDeferredInserts() {
    86     this->validate();
    87     if (this->isEmpty() && fDeferredInserts.count() > 0) {
    88         fCount = fDeferredInserts.count();
    89         if (1 == fCount) {
    90             fRoot.fChild.subtree = allocateNode(0);
    91             fRoot.fChild.subtree->fNumChildren = 0;
    92             this->insert(fRoot.fChild.subtree, &fDeferredInserts[0]);
    93             fRoot.fBounds = fDeferredInserts[0].fBounds;
    94         } else {
    95             fRoot = this->bulkLoad(&fDeferredInserts);
    96         }
    97     } else {
    98         // TODO: some algorithm for bulk loading into an already populated tree
    99         SkASSERT(0 == fDeferredInserts.count());
   100     }
   101     fDeferredInserts.rewind();
   102     this->validate();
   103 }
   105 void SkRTree::search(const SkIRect& query, SkTDArray<void*>* results) {
   106     this->validate();
   107     if (0 != fDeferredInserts.count()) {
   108         this->flushDeferredInserts();
   109     }
   110     if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query)) {
   111         this->search(fRoot.fChild.subtree, query, results);
   112     }
   113     this->validate();
   114 }
   116 void SkRTree::clear() {
   117     this->validate();
   118     fNodes.reset();
   119     fDeferredInserts.rewind();
   120     fCount = 0;
   121     this->validate();
   122 }
   124 SkRTree::Node* SkRTree::allocateNode(uint16_t level) {
   125     Node* out = static_cast<Node*>(fNodes.allocThrow(fNodeSize));
   126     out->fNumChildren = 0;
   127     out->fLevel = level;
   128     return out;
   129 }
   131 SkRTree::Branch* SkRTree::insert(Node* root, Branch* branch, uint16_t level) {
   132     Branch* toInsert = branch;
   133     if (root->fLevel != level) {
   134         int childIndex = this->chooseSubtree(root, branch);
   135         toInsert = this->insert(root->child(childIndex)->fChild.subtree, branch, level);
   136         root->child(childIndex)->fBounds = this->computeBounds(
   137             root->child(childIndex)->fChild.subtree);
   138     }
   139     if (NULL != toInsert) {
   140         if (root->fNumChildren == fMaxChildren) {
   141             // handle overflow by splitting. TODO: opportunistic reinsertion
   143             // decide on a distribution to divide with
   144             Node* newSibling = this->allocateNode(root->fLevel);
   145             Branch* toDivide = SkNEW_ARRAY(Branch, fMaxChildren + 1);
   146             for (int i = 0; i < fMaxChildren; ++i) {
   147                 toDivide[i] = *root->child(i);
   148             }
   149             toDivide[fMaxChildren] = *toInsert;
   150             int splitIndex = this->distributeChildren(toDivide);
   152             // divide up the branches
   153             root->fNumChildren = splitIndex;
   154             newSibling->fNumChildren = fMaxChildren + 1 - splitIndex;
   155             for (int i = 0; i < splitIndex; ++i) {
   156                 *root->child(i) = toDivide[i];
   157             }
   158             for (int i = splitIndex; i < fMaxChildren + 1; ++i) {
   159                 *newSibling->child(i - splitIndex) = toDivide[i];
   160             }
   161             SkDELETE_ARRAY(toDivide);
   163             // pass the new sibling branch up to the parent
   164             branch->fChild.subtree = newSibling;
   165             branch->fBounds = this->computeBounds(newSibling);
   166             return branch;
   167         } else {
   168             *root->child(root->fNumChildren) = *toInsert;
   169             ++root->fNumChildren;
   170             return NULL;
   171         }
   172     }
   173     return NULL;
   174 }
   176 int SkRTree::chooseSubtree(Node* root, Branch* branch) {
   177     SkASSERT(!root->isLeaf());
   178     if (1 < root->fLevel) {
   179         // root's child pointers do not point to leaves, so minimize area increase
   180         int32_t minAreaIncrease = SK_MaxS32;
   181         int32_t minArea         = SK_MaxS32;
   182         int32_t bestSubtree     = -1;
   183         for (int i = 0; i < root->fNumChildren; ++i) {
   184             const SkIRect& subtreeBounds = root->child(i)->fBounds;
   185             int32_t areaIncrease = get_area_increase(subtreeBounds, branch->fBounds);
   186             // break ties in favor of subtree with smallest area
   187             if (areaIncrease < minAreaIncrease || (areaIncrease == minAreaIncrease &&
   188                 static_cast<int32_t>(get_area(subtreeBounds)) < minArea)) {
   189                 minAreaIncrease = areaIncrease;
   190                 minArea = get_area(subtreeBounds);
   191                 bestSubtree = i;
   192             }
   193         }
   194         SkASSERT(-1 != bestSubtree);
   195         return bestSubtree;
   196     } else if (1 == root->fLevel) {
   197         // root's child pointers do point to leaves, so minimize overlap increase
   198         int32_t minOverlapIncrease = SK_MaxS32;
   199         int32_t minAreaIncrease    = SK_MaxS32;
   200         int32_t bestSubtree = -1;
   201         for (int32_t i = 0; i < root->fNumChildren; ++i) {
   202             const SkIRect& subtreeBounds = root->child(i)->fBounds;
   203             SkIRect expandedBounds = subtreeBounds;
   204             join_no_empty_check(branch->fBounds, &expandedBounds);
   205             int32_t overlap = 0;
   206             for (int32_t j = 0; j < root->fNumChildren; ++j) {
   207                 if (j == i) continue;
   208                 // Note: this would be more correct if we subtracted the original pre-expanded
   209                 // overlap, but computing overlaps is expensive and omitting it doesn't seem to
   210                 // hurt query performance. See get_overlap_increase()
   211                 overlap += get_overlap(expandedBounds, root->child(j)->fBounds);
   212             }
   213             // break ties with lowest area increase
   214             if (overlap < minOverlapIncrease || (overlap == minOverlapIncrease &&
   215                 static_cast<int32_t>(get_area_increase(branch->fBounds, subtreeBounds)) <
   216                 minAreaIncrease)) {
   217                 minOverlapIncrease = overlap;
   218                 minAreaIncrease = get_area_increase(branch->fBounds, subtreeBounds);
   219                 bestSubtree = i;
   220             }
   221         }
   222         return bestSubtree;
   223     } else {
   224         SkASSERT(false);
   225         return 0;
   226     }
   227 }
   229 SkIRect SkRTree::computeBounds(Node* n) {
   230     SkIRect r = n->child(0)->fBounds;
   231     for (int i = 1; i < n->fNumChildren; ++i) {
   232         join_no_empty_check(n->child(i)->fBounds, &r);
   233     }
   234     return r;
   235 }
   237 int SkRTree::distributeChildren(Branch* children) {
   238     // We have two sides to sort by on each of two axes:
   239     const static SortSide sorts[2][2] = {
   240         {&SkIRect::fLeft, &SkIRect::fRight},
   241         {&SkIRect::fTop, &SkIRect::fBottom}
   242     };
   244     // We want to choose an axis to split on, then a distribution along that axis; we'll need
   245     // three pieces of info: the split axis, the side to sort by on that axis, and the index
   246     // to split the sorted array on.
   247     int32_t sortSide = -1;
   248     int32_t k        = -1;
   249     int32_t axis     = -1;
   250     int32_t bestS    = SK_MaxS32;
   252     // Evaluate each axis, we want the min summed margin-value (s) over all distributions
   253     for (int i = 0; i < 2; ++i) {
   254         int32_t minOverlap   = SK_MaxS32;
   255         int32_t minArea      = SK_MaxS32;
   256         int32_t axisBestK    = 0;
   257         int32_t axisBestSide = 0;
   258         int32_t s = 0;
   260         // Evaluate each sort
   261         for (int j = 0; j < 2; ++j) {
   262             SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[i][j]));
   264             // Evaluate each split index
   265             for (int32_t k = 1; k <= fMaxChildren - 2 * fMinChildren + 2; ++k) {
   266                 SkIRect r1 = children[0].fBounds;
   267                 SkIRect r2 = children[fMinChildren + k - 1].fBounds;
   268                 for (int32_t l = 1; l < fMinChildren - 1 + k; ++l) {
   269                     join_no_empty_check(children[l].fBounds, &r1);
   270                 }
   271                 for (int32_t l = fMinChildren + k; l < fMaxChildren + 1; ++l) {
   272                     join_no_empty_check(children[l].fBounds, &r2);
   273                 }
   275                 int32_t area = get_area(r1) + get_area(r2);
   276                 int32_t overlap = get_overlap(r1, r2);
   277                 s += get_margin(r1) + get_margin(r2);
   279                 if (overlap < minOverlap || (overlap == minOverlap && area < minArea)) {
   280                     minOverlap = overlap;
   281                     minArea = area;
   282                     axisBestSide = j;
   283                     axisBestK = k;
   284                 }
   285             }
   286         }
   288         if (s < bestS) {
   289             bestS = s;
   290             axis = i;
   291             sortSide = axisBestSide;
   292             k = axisBestK;
   293         }
   294     }
   296     // replicate the sort of the winning distribution, (we can skip this if the last
   297     // sort ended up being best)
   298     if (!(axis == 1 && sortSide == 1)) {
   299         SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[axis][sortSide]));
   300     }
   302     return fMinChildren - 1 + k;
   303 }
   305 void SkRTree::search(Node* root, const SkIRect query, SkTDArray<void*>* results) const {
   306     for (int i = 0; i < root->fNumChildren; ++i) {
   307         if (SkIRect::IntersectsNoEmptyCheck(root->child(i)->fBounds, query)) {
   308             if (root->isLeaf()) {
   309                 results->push(root->child(i)->fChild.data);
   310             } else {
   311                 this->search(root->child(i)->fChild.subtree, query, results);
   312             }
   313         }
   314     }
   315 }
   317 SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
   318     if (branches->count() == 1) {
   319         // Only one branch: it will be the root
   320         Branch out = (*branches)[0];
   321         branches->rewind();
   322         return out;
   323     } else {
   324         // We sort the whole list by y coordinates, if we are told to do so.
   325         //
   326         // We expect Webkit / Blink to give us a reasonable x,y order.
   327         // Avoiding this call resulted in a 17% win for recording with
   328         // negligible difference in playback speed.
   329         if (fSortWhenBulkLoading) {
   330             SkTQSort(branches->begin(), branches->end() - 1, RectLessY());
   331         }
   333         int numBranches = branches->count() / fMaxChildren;
   334         int remainder = branches->count() % fMaxChildren;
   335         int newBranches = 0;
   337         if (0 != remainder) {
   338             ++numBranches;
   339             // If the remainder isn't enough to fill a node, we'll need to add fewer nodes to
   340             // some other branches to make up for it
   341             if (remainder >= fMinChildren) {
   342                 remainder = 0;
   343             } else {
   344                 remainder = fMinChildren - remainder;
   345             }
   346         }
   348         int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) *
   349                                      SkScalarInvert(fAspectRatio)));
   350         int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) /
   351                                     SkIntToScalar(numStrips));
   352         int currentBranch = 0;
   354         for (int i = 0; i < numStrips; ++i) {
   355             // Once again, if we are told to do so, we sort by x.
   356             if (fSortWhenBulkLoading) {
   357                 int begin = currentBranch;
   358                 int end = currentBranch + numTiles * fMaxChildren - SkMin32(remainder,
   359                         (fMaxChildren - fMinChildren) * numTiles);
   360                 if (end > branches->count()) {
   361                     end = branches->count();
   362                 }
   364                 // Now we sort horizontal strips of rectangles by their x coords
   365                 SkTQSort(branches->begin() + begin, branches->begin() + end - 1, RectLessX());
   366             }
   368             for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) {
   369                 int incrementBy = fMaxChildren;
   370                 if (remainder != 0) {
   371                     // if need be, omit some nodes to make up for remainder
   372                     if (remainder <= fMaxChildren - fMinChildren) {
   373                         incrementBy -= remainder;
   374                         remainder = 0;
   375                     } else {
   376                         incrementBy = fMinChildren;
   377                         remainder -= fMaxChildren - fMinChildren;
   378                     }
   379                 }
   380                 Node* n = allocateNode(level);
   381                 n->fNumChildren = 1;
   382                 *n->child(0) = (*branches)[currentBranch];
   383                 Branch b;
   384                 b.fBounds = (*branches)[currentBranch].fBounds;
   385                 b.fChild.subtree = n;
   386                 ++currentBranch;
   387                 for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) {
   388                     b.fBounds.join((*branches)[currentBranch].fBounds);
   389                     *n->child(k) = (*branches)[currentBranch];
   390                     ++n->fNumChildren;
   391                     ++currentBranch;
   392                 }
   393                 (*branches)[newBranches] = b;
   394                 ++newBranches;
   395             }
   396         }
   397         branches->setCount(newBranches);
   398         return this->bulkLoad(branches, level + 1);
   399     }
   400 }
   402 void SkRTree::validate() {
   403 #ifdef SK_DEBUG
   404     if (this->isEmpty()) {
   405         return;
   406     }
   407     SkASSERT(fCount == this->validateSubtree(fRoot.fChild.subtree, fRoot.fBounds, true));
   408 #endif
   409 }
   411 int SkRTree::validateSubtree(Node* root, SkIRect bounds, bool isRoot) {
   412     // make sure the pointer is pointing to a valid place
   413     SkASSERT(fNodes.contains(static_cast<void*>(root)));
   415     if (isRoot) {
   416         // If the root of this subtree is the overall root, we have looser standards:
   417         if (root->isLeaf()) {
   418             SkASSERT(root->fNumChildren >= 1 && root->fNumChildren <= fMaxChildren);
   419         } else {
   420             SkASSERT(root->fNumChildren >= 2 && root->fNumChildren <= fMaxChildren);
   421         }
   422     } else {
   423         SkASSERT(root->fNumChildren >= fMinChildren && root->fNumChildren <= fMaxChildren);
   424     }
   426     for (int i = 0; i < root->fNumChildren; ++i) {
   427         SkASSERT(bounds.contains(root->child(i)->fBounds));
   428     }
   430     if (root->isLeaf()) {
   431         SkASSERT(0 == root->fLevel);
   432         return root->fNumChildren;
   433     } else {
   434         int childCount = 0;
   435         for (int i = 0; i < root->fNumChildren; ++i) {
   436             SkASSERT(root->child(i)->fChild.subtree->fLevel == root->fLevel - 1);
   437             childCount += this->validateSubtree(root->child(i)->fChild.subtree,
   438                                                 root->child(i)->fBounds);
   439         }
   440         return childCount;
   441     }
   442 }
   444 void SkRTree::rewindInserts() {
   445     SkASSERT(this->isEmpty()); // Currently only supports deferred inserts
   446     while (!fDeferredInserts.isEmpty() &&
   447            fClient->shouldRewind(fDeferredInserts.top().fChild.data)) {
   448         fDeferredInserts.pop();
   449     }
   450 }
   452 ///////////////////////////////////////////////////////////////////////////////////////////////////
   454 static inline uint32_t get_area(const SkIRect& rect) {
   455     return rect.width() * rect.height();
   456 }
   458 static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2) {
   459     // I suspect there's a more efficient way of computing this...
   460     return SkMax32(0, SkMin32(rect1.fRight, rect2.fRight) - SkMax32(rect1.fLeft, rect2.fLeft)) *
   461            SkMax32(0, SkMin32(rect1.fBottom, rect2.fBottom) - SkMax32(rect1.fTop, rect2.fTop));
   462 }
   464 // Get the margin (aka perimeter)
   465 static inline uint32_t get_margin(const SkIRect& rect) {
   466     return 2 * (rect.width() + rect.height());
   467 }
   469 static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2) {
   470     join_no_empty_check(rect1, &rect2);
   471     return get_area(rect2) - get_area(rect1);
   472 }
   474 // Expand 'out' to include 'joinWith'
   475 static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) {
   476     // since we check for empty bounds on insert, we know we'll never have empty rects
   477     // and we can save the empty check that SkIRect::join requires
   478     if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; }
   479     if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; }
   480     if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; }
   481     if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; }
   482 }

mercurial