Slightly faster quadtree searching

src/core/SkQuadTree.cpp

 /*
  * 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>
 #include <vector>
 
 static const int kSplitThreshold = 8;
-static const int kMinDimensions = 128;
+
+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)
-    : fEntryCount(0)
-    , fRoot(NULL) {
+    : fRoot(NULL) {
     SkASSERT((bounds.width() * bounds.height()) > 0);
-    fRoot = fNodePool.acquire();
-    fRoot->fBounds = bounds;
+    fRootBounds = bounds;
 }
 
 SkQuadTree::~SkQuadTree() {
 }
 
-SkQuadTree::Node* SkQuadTree::pickChild(Node* node,
-                                        const SkIRect& bounds) const {
-    // is it entirely to the left?
-    int index = 0;
-    if (bounds.fRight < node->fSplitPoint.fX) {
-        // Inside the left side
-    } else if(bounds.fLeft >= node->fSplitPoint.fX) {
-        // Inside the right side
-        index |= 1;
-    } else {
-        // Not inside any children
-        return NULL;
-    }
-    if (bounds.fBottom < node->fSplitPoint.fY) {
-        // Inside the top side
-    } else if(bounds.fTop >= node->fSplitPoint.fY) {
-        // Inside the bottom side
-        index |= 2;
-    } else {
-        // Not inside any children
-        return NULL;
-    }
-    return node->fChildren[index];
-}
-
 void SkQuadTree::insert(Node* node, Entry* entry) {
     // does it belong in a child?
     if (NULL != node->fChildren[0]) {
-        Node* child = pickChild(node, entry->fBounds);
-        if (NULL != child) {
-            insert(child, entry);
-        } else {
-            node->fEntries.push(entry);
+        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;
         }
-        return;
     }
     // No children yet, add to this node
     node->fEntries.push(entry);
     // should I split?
-    if (node->fEntries.getCount() < kSplitThreshold) {
-        return;
+    if (node->fEntries.getCount() > kSplitThreshold) {
+        this->split(node);
     }
+}
 
-    if ((node->fBounds.width() < kMinDimensions) ||
-        (node->fBounds.height() < kMinDimensions)) {
-        return;
-    }
-
+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()) {
-        insert(node, entries.pop());
+        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;
     }
-    // fast quadrant test
-    bool left = true;
-    bool right = true;
-    if (query.fRight < node->fSplitPoint.fX) {
-        right = false;
-    } else if(query.fLeft >= node->fSplitPoint.fX) {
-        left = false;
-    }
-    bool top = true;
-    bool bottom = true;
-    if (query.fBottom < node->fSplitPoint.fY) {
-        bottom = false;
-    } else if(query.fTop >= node->fSplitPoint.fY) {
-        top = false;
-    }
-    // search all the active quadrants
-    if (top && left) {
-        search(node->fChildren[0], query, results);
-    }
-    if (top && right) {
-        search(node->fChildren[1], query, results);
-    }
-    if (bottom && left) {
-        search(node->fChildren[2], query, results);
-    }
-    if (bottom && right) {
-        search(node->fChildren[3], query, results);
+    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) {
-            clear(child);
+            this->clear(child);
             fNodePool.release(child);
         }
     }
 }
 
 int SkQuadTree::getDepth(Node* node) const {
     int maxDepth = 0;
-    if (NULL != node->fChildren[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;
-    ++fEntryCount;
-    if (fRoot->fEntries.isEmpty() && (NULL == fRoot->fChildren[0])) {
+    if (NULL == fRoot) {
         fDeferred.push(entry);
     } else {
-        insert(fRoot, entry);
+        this->insert(fRoot, entry);
     }
 }
 
 void SkQuadTree::search(const SkIRect& query, SkTDArray<void*>* results) {
-    SkASSERT(fDeferred.isEmpty());
+    SkASSERT(NULL != fRoot);
     SkASSERT(NULL != results);
-    if (SkIRect::Intersects(fRoot->fBounds, query)) {
-        search(fRoot, query, results);
+    if (SkIRect::Intersects(fRootBounds, query)) {
+        this->search(fRoot, query, results);
     }
 }
 
 void SkQuadTree::clear() {
-    fEntryCount = 0;
-    clear(fRoot);
+    if (NULL != fRoot) {
+        this->clear(fRoot);
+        fNodePool.release(fRoot);
+        fRoot = NULL;
+    }
 }
 
 int SkQuadTree::getDepth() const {
-    return getDepth(fRoot);
+    return this->getDepth(fRoot);
 }
 
 void SkQuadTree::rewindInserts() {
     SkASSERT(fClient);
      // Currently only supports deferred inserts
-    SkASSERT(fRoot->fEntries.isEmpty() && fRoot->fChildren[0] == NULL);
+    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);
-            --fEntryCount;
         } else {
             fDeferred.push(entry);
         }
     }
 }
 
 void SkQuadTree::flushDeferredInserts() {
+    if (NULL == fRoot) {
+        fRoot = fNodePool.acquire();
+        fRoot->fBounds = fRootBounds;
+    }
     while(!fDeferred.isEmpty()) {
-        insert(fRoot, fDeferred.pop());
+        this->insert(fRoot, fDeferred.pop());
     }
 }