Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1069)

Unified Diff: src/core/SkQuadTree.cpp

Issue 500373005: Remove SkQuadTree. (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Created 6 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/core/SkQuadTree.h ('k') | tests/BBoxHierarchyTest.cpp » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/core/SkQuadTree.cpp
diff --git a/src/core/SkQuadTree.cpp b/src/core/SkQuadTree.cpp
deleted file mode 100644
index 1fc3cd0192a26c64efe3a06ef5baf4cfd8a17aec..0000000000000000000000000000000000000000
--- a/src/core/SkQuadTree.cpp
+++ /dev/null
@@ -1,219 +0,0 @@
-/*
- * Copyright 2014 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-
-#include "SkQuadTree.h"
-#include "SkTSort.h"
-#include <stdio.h>
-
-static const int kSplitThreshold = 8;
-
-enum {
- kTopLeft,
- kTopRight,
- kBottomLeft,
- kBottomRight,
-};
-enum {
- kTopLeft_Bit = 1 << kTopLeft,
- kTopRight_Bit = 1 << kTopRight,
- kBottomLeft_Bit = 1 << kBottomLeft,
- kBottomRight_Bit = 1 << kBottomRight,
-};
-enum {
- kMaskLeft = kTopLeft_Bit | kBottomLeft_Bit,
- kMaskRight = kTopRight_Bit | kBottomRight_Bit,
- kMaskTop = kTopLeft_Bit | kTopRight_Bit,
- kMaskBottom = kBottomLeft_Bit | kBottomRight_Bit,
-};
-
-static U8CPU child_intersect(const SkIRect& query, const SkIPoint& split) {
- // fast quadrant test
- U8CPU intersect = 0xf;
- if (query.fRight < split.fX) {
- intersect &= ~kMaskRight;
- } else if(query.fLeft >= split.fX) {
- intersect &= ~kMaskLeft;
- }
- if (query.fBottom < split.fY) {
- intersect &= ~kMaskBottom;
- } else if(query.fTop >= split.fY) {
- intersect &= ~kMaskTop;
- }
- return intersect;
-}
-
-SkQuadTree::SkQuadTree(const SkIRect& bounds) : fRoot(NULL) {
- SkASSERT((bounds.width() * bounds.height()) > 0);
- fRootBounds = bounds;
-}
-
-SkQuadTree::~SkQuadTree() {
-}
-
-void SkQuadTree::insert(Node* node, Entry* entry) {
- // does it belong in a child?
- if (NULL != node->fChildren[0]) {
- switch(child_intersect(entry->fBounds, node->fSplitPoint)) {
- case kTopLeft_Bit:
- this->insert(node->fChildren[kTopLeft], entry);
- return;
- case kTopRight_Bit:
- this->insert(node->fChildren[kTopRight], entry);
- return;
- case kBottomLeft_Bit:
- this->insert(node->fChildren[kBottomLeft], entry);
- return;
- case kBottomRight_Bit:
- this->insert(node->fChildren[kBottomRight], entry);
- return;
- default:
- node->fEntries.push(entry);
- return;
- }
- }
- // No children yet, add to this node
- node->fEntries.push(entry);
- // should I split?
- if (node->fEntries.getCount() > kSplitThreshold) {
- this->split(node);
- }
-}
-
-void SkQuadTree::split(Node* node) {
- // Build all the children
- node->fSplitPoint = SkIPoint::Make(node->fBounds.centerX(),
- node->fBounds.centerY());
- for(int index=0; index<kChildCount; ++index) {
- node->fChildren[index] = fNodePool.acquire();
- }
- node->fChildren[0]->fBounds = SkIRect::MakeLTRB(
- node->fBounds.fLeft, node->fBounds.fTop,
- node->fSplitPoint.fX, node->fSplitPoint.fY);
- node->fChildren[1]->fBounds = SkIRect::MakeLTRB(
- node->fSplitPoint.fX, node->fBounds.fTop,
- node->fBounds.fRight, node->fSplitPoint.fY);
- node->fChildren[2]->fBounds = SkIRect::MakeLTRB(
- node->fBounds.fLeft, node->fSplitPoint.fY,
- node->fSplitPoint.fX, node->fBounds.fBottom);
- node->fChildren[3]->fBounds = SkIRect::MakeLTRB(
- node->fSplitPoint.fX, node->fSplitPoint.fY,
- node->fBounds.fRight, node->fBounds.fBottom);
- // reinsert all the entries of this node to allow child trickle
- SkTInternalSList<Entry> entries;
- entries.pushAll(&node->fEntries);
- while(!entries.isEmpty()) {
- this->insert(node, entries.pop());
- }
-}
-
-void SkQuadTree::search(Node* node, const SkIRect& query,
- SkTDArray<void*>* results) const {
- for (Entry* entry = node->fEntries.head(); NULL != entry;
- entry = entry->getSListNext()) {
- if (SkIRect::IntersectsNoEmptyCheck(entry->fBounds, query)) {
- results->push(entry->fData);
- }
- }
- if (NULL == node->fChildren[0]) {
- return;
- }
- U8CPU intersect = child_intersect(query, node->fSplitPoint);
- for(int index=0; index<kChildCount; ++index) {
- if (intersect & (1 << index)) {
- this->search(node->fChildren[index], query, results);
- }
- }
-}
-
-void SkQuadTree::clear(Node* node) {
- // first clear the entries of this node
- fEntryPool.releaseAll(&node->fEntries);
- // recurse into and clear all child nodes
- for(int index=0; index<kChildCount; ++index) {
- Node* child = node->fChildren[index];
- node->fChildren[index] = NULL;
- if (NULL != child) {
- this->clear(child);
- fNodePool.release(child);
- }
- }
-}
-
-int SkQuadTree::getDepth(Node* node) const {
- int maxDepth = 0;
- if (NULL != node) {
- for(int index=0; index<kChildCount; ++index) {
- maxDepth = SkMax32(maxDepth, getDepth(node->fChildren[index]));
- }
- }
- return maxDepth + 1;
-}
-
-void SkQuadTree::insert(void* data, const SkIRect& bounds, bool) {
- if (bounds.isEmpty()) {
- SkASSERT(false);
- return;
- }
- Entry* entry = fEntryPool.acquire();
- entry->fData = data;
- entry->fBounds = bounds;
- if (NULL == fRoot) {
- fDeferred.push(entry);
- } else {
- this->insert(fRoot, entry);
- }
-}
-
-void SkQuadTree::search(const SkIRect& query, SkTDArray<void*>* results) const {
- SkASSERT(NULL != fRoot);
- SkASSERT(NULL != results);
- if (SkIRect::Intersects(fRootBounds, query)) {
- this->search(fRoot, query, results);
- }
-}
-
-void SkQuadTree::clear() {
- this->flushDeferredInserts();
- if (NULL != fRoot) {
- this->clear(fRoot);
- fNodePool.release(fRoot);
- fRoot = NULL;
- }
- SkASSERT(fEntryPool.allocated() == fEntryPool.available());
- SkASSERT(fNodePool.allocated() == fNodePool.available());
-}
-
-int SkQuadTree::getDepth() const {
- return this->getDepth(fRoot);
-}
-
-void SkQuadTree::rewindInserts() {
- SkASSERT(fClient);
- // Currently only supports deferred inserts
- SkASSERT(NULL == fRoot);
- SkTInternalSList<Entry> entries;
- entries.pushAll(&fDeferred);
- while(!entries.isEmpty()) {
- Entry* entry = entries.pop();
- if (fClient->shouldRewind(entry->fData)) {
- entry->fData = NULL;
- fEntryPool.release(entry);
- } else {
- fDeferred.push(entry);
- }
- }
-}
-
-void SkQuadTree::flushDeferredInserts() {
- if (NULL == fRoot) {
- fRoot = fNodePool.acquire();
- fRoot->fBounds = fRootBounds;
- }
- while(!fDeferred.isEmpty()) {
- this->insert(fRoot, fDeferred.pop());
- }
-}
« no previous file with comments | « src/core/SkQuadTree.h ('k') | tests/BBoxHierarchyTest.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698