src/third_party/skia/src/core/SkQuadTree.cpp

   1 /*
   2  * Copyright 2014 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 "SkQuadTree.h"
   9 #include "SkTSort.h"
  10 #include <stdio.h>
  11
  12 static const int kSplitThreshold = 8;
  13
  14 enum {
  15     kTopLeft,
  16     kTopRight,
  17     kBottomLeft,
  18     kBottomRight,
  19 };
  20 enum {
  21     kTopLeft_Bit = 1 << kTopLeft,
  22     kTopRight_Bit = 1 << kTopRight,
  23     kBottomLeft_Bit = 1 << kBottomLeft,
  24     kBottomRight_Bit = 1 << kBottomRight,
  25 };
  26 enum {
  27     kMaskLeft = kTopLeft_Bit | kBottomLeft_Bit,
  28     kMaskRight = kTopRight_Bit | kBottomRight_Bit,
  29     kMaskTop = kTopLeft_Bit | kTopRight_Bit,
  30     kMaskBottom = kBottomLeft_Bit | kBottomRight_Bit,
  31 };
  32
  33 static U8CPU child_intersect(const SkIRect& query, const SkIPoint& split) {
  34     // fast quadrant test
  35     U8CPU intersect = 0xf;
  36     if (query.fRight <  split.fX) {
  37         intersect &= ~kMaskRight;
  38     } else if(query.fLeft >= split.fX) {
  39         intersect &= ~kMaskLeft;
  40     }
  41     if (query.fBottom < split.fY) {
  42         intersect &= ~kMaskBottom;
  43     } else if(query.fTop >= split.fY) {
  44         intersect &= ~kMaskTop;
  45     }
  46     return intersect;
  47 }
  48
  49 SkQuadTree::SkQuadTree(const SkIRect& bounds)
  50     : fRoot(NULL) {
  51     SkASSERT((bounds.width() * bounds.height()) > 0);
  52     fRootBounds = bounds;
  53 }
  54
  55 SkQuadTree::~SkQuadTree() {
  56 }
  57
  58 void SkQuadTree::insert(Node* node, Entry* entry) {
  59     // does it belong in a child?
  60     if (NULL != node->fChildren[0]) {
  61         switch(child_intersect(entry->fBounds, node->fSplitPoint)) {
  62             case kTopLeft_Bit:
  63                 this->insert(node->fChildren[kTopLeft], entry);
  64                 return;
  65             case kTopRight_Bit:
  66                 this->insert(node->fChildren[kTopRight], entry);
  67                 return;
  68             case kBottomLeft_Bit:
  69                 this->insert(node->fChildren[kBottomLeft], entry);
  70                 return;
  71             case kBottomRight_Bit:
  72                 this->insert(node->fChildren[kBottomRight], entry);
  73                 return;
  74             default:
  75                 node->fEntries.push(entry);
  76                 return;
  77         }
  78     }
  79     // No children yet, add to this node
  80     node->fEntries.push(entry);
  81     // should I split?
  82     if (node->fEntries.getCount() > kSplitThreshold) {
  83         this->split(node);
  84     }
  85 }
  86
  87 void SkQuadTree::split(Node* node) {
  88     // Build all the children
  89     node->fSplitPoint = SkIPoint::Make(node->fBounds.centerX(),
  90                                        node->fBounds.centerY());
  91     for(int index=0; index<kChildCount; ++index) {
  92         node->fChildren[index] = fNodePool.acquire();
  93     }
  94     node->fChildren[0]->fBounds = SkIRect::MakeLTRB(
  95         node->fBounds.fLeft,    node->fBounds.fTop,
  96         node->fSplitPoint.fX,   node->fSplitPoint.fY);
  97     node->fChildren[1]->fBounds = SkIRect::MakeLTRB(
  98         node->fSplitPoint.fX,   node->fBounds.fTop,
  99         node->fBounds.fRight,   node->fSplitPoint.fY);
 100     node->fChildren[2]->fBounds = SkIRect::MakeLTRB(
 101         node->fBounds.fLeft,    node->fSplitPoint.fY,
 102         node->fSplitPoint.fX,   node->fBounds.fBottom);
 103     node->fChildren[3]->fBounds = SkIRect::MakeLTRB(
 104         node->fSplitPoint.fX,   node->fSplitPoint.fY,
 105         node->fBounds.fRight,   node->fBounds.fBottom);
 106     // reinsert all the entries of this node to allow child trickle
 107     SkTInternalSList<Entry> entries;
 108     entries.pushAll(&node->fEntries);
 109     while(!entries.isEmpty()) {
 110         this->insert(node, entries.pop());
 111     }
 112 }
 113
 114 void SkQuadTree::search(Node* node, const SkIRect& query,
 115                         SkTDArray<void*>* results) const {
 116     for (Entry* entry = node->fEntries.head(); NULL != entry;
 117         entry = entry->getSListNext()) {
 118         if (SkIRect::IntersectsNoEmptyCheck(entry->fBounds, query)) {
 119             results->push(entry->fData);
 120         }
 121     }
 122     if (NULL == node->fChildren[0]) {
 123         return;
 124     }
 125     U8CPU intersect = child_intersect(query, node->fSplitPoint);
 126     for(int index=0; index<kChildCount; ++index) {
 127         if (intersect & (1 << index)) {
 128             this->search(node->fChildren[index], query, results);
 129         }
 130     }
 131 }
 132
 133 void SkQuadTree::clear(Node* node) {
 134     // first clear the entries of this node
 135     fEntryPool.releaseAll(&node->fEntries);
 136     // recurse into and clear all child nodes
 137     for(int index=0; index<kChildCount; ++index) {
 138         Node* child = node->fChildren[index];
 139         node->fChildren[index] = NULL;
 140         if (NULL != child) {
 141             this->clear(child);
 142             fNodePool.release(child);
 143         }
 144     }
 145 }
 146
 147 int SkQuadTree::getDepth(Node* node) const {
 148     int maxDepth = 0;
 149     if (NULL != node) {
 150         for(int index=0; index<kChildCount; ++index) {
 151             maxDepth = SkMax32(maxDepth, getDepth(node->fChildren[index]));
 152         }
 153     }
 154     return maxDepth + 1;
 155 }
 156
 157 void SkQuadTree::insert(void* data, const SkIRect& bounds, bool) {
 158     if (bounds.isEmpty()) {
 159         SkASSERT(false);
 160         return;
 161     }
 162     Entry* entry = fEntryPool.acquire();
 163     entry->fData = data;
 164     entry->fBounds = bounds;
 165     if (NULL == fRoot) {
 166         fDeferred.push(entry);
 167     } else {
 168         this->insert(fRoot, entry);
 169     }
 170 }
 171
 172 void SkQuadTree::search(const SkIRect& query, SkTDArray<void*>* results) {
 173     SkASSERT(NULL != fRoot);
 174     SkASSERT(NULL != results);
 175     if (SkIRect::Intersects(fRootBounds, query)) {
 176         this->search(fRoot, query, results);
 177     }
 178 }
 179
 180 void SkQuadTree::clear() {
 181     if (NULL != fRoot) {
 182         this->clear(fRoot);
 183         fNodePool.release(fRoot);
 184         fRoot = NULL;
 185     }
 186 }
 187
 188 int SkQuadTree::getDepth() const {
 189     return this->getDepth(fRoot);
 190 }
 191
 192 void SkQuadTree::rewindInserts() {
 193     SkASSERT(fClient);
 194      // Currently only supports deferred inserts
 195     SkASSERT(NULL == fRoot);
 196     SkTInternalSList<Entry> entries;
 197     entries.pushAll(&fDeferred);
 198     while(!entries.isEmpty()) {
 199         Entry* entry = entries.pop();
 200         if (fClient->shouldRewind(entry->fData)) {
 201             entry->fData = NULL;
 202             fEntryPool.release(entry);
 203         } else {
 204             fDeferred.push(entry);
 205         }
 206     }
 207 }
 208
 209 void SkQuadTree::flushDeferredInserts() {
 210     if (NULL == fRoot) {
 211         fRoot = fNodePool.acquire();
 212         fRoot->fBounds = fRootBounds;
 213     }
 214     while(!fDeferred.isEmpty()) {
 215         this->insert(fRoot, fDeferred.pop());
 216     }
 217 }