src/third_party/skia/src/core/SkRTree.cpp

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