Fast implementation of QuadTree

src/core/SkQuadTree.h

Index: src/core/SkQuadTree.h
diff --git a/src/core/SkQuadTree.h b/src/core/SkQuadTree.h
index a26174960953d97a039cb94d6b2cbf895ddb7b9b..fca99a007403bd17e0dbe80d8380d484479bccb1 100644
--- a/src/core/SkQuadTree.h
+++ b/src/core/SkQuadTree.h
@@ -13,7 +13,137 @@
 #include "SkBBoxHierarchy.h"
 

[robertphillips, 2014/03/05 13:08:53]

Might be worth mirroring SkTInternalList.h

[iancottrell, 2014/03/07 15:06:34]

Done.

 /**
- * An QuadTree implementation. In short, it is a tree containing a hierarchy of bounding rectangles
+ * An implementation of an intrusive singly linked list.
+ * The type T must have a field fNext that is visible to the list.
+ * The list does not maintain ownership of any of its elements, or ever delete
+ * them.
+ * The fNext must be null on any object handed to push, and will be NULL when
+ * returned from pop. It is free to use while the object is not in the a list.
+ */
+template<typename T> class SkSList {
+public:
+    SkSList() : fHead(NULL), fCount(0) {}
+
+    /**
+     * Push an item onto the head of the list.
+     * This method is *not* thread safe.
+     */
+    void push(T* entry) {
+        SkASSERT(entry->fNext == NULL);
+        entry->fNext = fHead;
+        fHead = entry;
+        ++fCount;
+    }
+
+    /**
+     * Takes all the items from another list.

[reed1, 2014/03/05 14:33:01]

Are they added to the head or the tail of this list?
Are they kept in their same order?
Is the "other" head now empty?

[iancottrell, 2014/03/07 15:06:34]

Done.

+     */
+    void takeAll(SkSList<T>& other) {

[reed1, 2014/03/05 14:33:01]

typically in Skia if the argument is changed, we pass a pointer instead of a
reference.

[iancottrell, 2014/03/07 15:06:34]

Done.

+        if (isEmpty()) {
+            swap(other);
+            return;
+        }
+        while(!other.isEmpty()) {
+            push(other.pop());
+        }
+    }
+
+    /**
+     * Pop an item from the head of the list.
+     * Returns NULL if the list is empty.
+     * This method is *not* thread safe.
+     */
+    T* pop() {
+        if (fHead == NULL) {
+            return NULL;
+        }
+        T* result = fHead;
+        fHead = result->fNext;
+        result->fNext = NULL;
+        --fCount;
+        return result;
+    }
+
+    T* head() {
+        return fHead;
+    }
+
+    /**
+     * Returns true if the list has no elements.
+     */
+    bool isEmpty() {

[reed1, 2014/03/05 14:33:01]

const

[iancottrell, 2014/03/07 15:06:34]

Done.

+        return fHead == NULL;

[reed1, 2014/03/05 14:33:01]

tiny nit: Skia tries to be paranoid, and writes this expression as

return NULL == fHead

to avoid accidental assignment

[iancottrell, 2014/03/07 15:06:34]

Done.

+    }
+
+    /**
+     * Swaps the contents of this list with another one.
+     */
+    void swap(SkSList<T>& other) {
+        SkTSwap(fHead, other.fHead);
+        SkTSwap(fCount, other.fCount);
+    }
+
+    /**
+     * Returns the count of elements in the list.
+     */
+    int getCount() {

[reed1, 2014/03/05 14:33:01]

const

[iancottrell, 2014/03/07 15:06:34]

Done.

+        return fCount;
+    }
+private:
+    T* fHead;
+    int fCount;
+};
+
+
+/**
+ * An implementation of a self growing free list of objects.
+ * Constructors and destructors will be called on the objects.
+ * All memory will be reclaimed when the free list is destroyed, so the free
+ * list must survive longer than you are using any item taken from it.
+ */
+template<typename T, int growth = 4096/sizeof(T)> class SkFreeList : public SkSList<T> {
+public:
+    SkFreeList() {}
+    ~SkFreeList() {
+        while(!fBlocks.isEmpty()) { SkDELETE(fBlocks.pop()); }
+    }
+    /**
+     * Get an item from the free list.
+     * If the free list has no items, it will grow.
+     * The free list will never shrink, it will use the maximum memory it has
+     * ever reached until destroyed.
+     * The returned item is only valid as long as the free list has not been
+     * destroyed, at that point all memory allocated by grow will have been
+     * reclaimed.
+     * This method is *not* thread safe.
+     */
+    T* pop() {
+        if (this->isEmpty()) { grow(); }
+        return SkSList<T>::pop();
+    }
+private:
+    /**
+     * The type for a new block of entries for the list.
+     */
+    struct Block {
+        Block() : fNext(0) {}
+        Block* fNext;
+        T entries[growth];
+    };
+    SkSList<Block> fBlocks;
+
+    void grow() {
+        Block* block = SkNEW(Block);
+        fBlocks.push(block);
+        for(int index = 0; index < growth; ++index) {
+            push(&block->entries[index]);
+        }
+    }
+
+};
+
+/**
+ * A QuadTree implementation. In short, it is a tree containing a hierarchy of bounding rectangles
  * in which each internal node has exactly four children.
  *
  * For more details see:
@@ -43,7 +173,7 @@ public:
     /**
      * If any inserts have been deferred, this will add them into the tree
      */
-    virtual void flushDeferredInserts() SK_OVERRIDE {}
+    virtual void flushDeferredInserts() SK_OVERRIDE;
 
     /**
      * Given a query rectangle, populates the passed-in array with the elements it intersects
@@ -60,19 +190,47 @@ public:
     /**
      * This gets the insertion count (rather than the node count)
      */
-    virtual int getCount() const SK_OVERRIDE { return fCount; }
+    virtual int getCount() const SK_OVERRIDE { return fEntryCount; }
 
     virtual void rewindInserts() SK_OVERRIDE;
 
 private:
-    class QuadTreeNode;
+    struct Entry {
+        Entry() : fNext(NULL), fData(NULL) {}
+        Entry* fNext;
+        SkIRect fBounds;
+        void* fData;
+    };
+
+    static const int kChildCount = 4;
+
+    struct Node {
+        Node() : fNext(NULL) {
+            for (int index=0; index<kChildCount; ++index) {
+                fChildren[index] = NULL;
+            }
+        }
+        SkSList<Entry> fEntries;
+        SkIRect fBounds;
+        SkIPoint fSplitPoint; // Only valid if the node has children.
+        union { // Unioned only to save space
+            Node* fNext; // Used when in a free list, where it has no children.
+            Node* fChildren[kChildCount];
+        };
+    };
+
+    SkFreeList<Entry> fFreeEntries;
+    SkFreeList<Node> fFreeNodes;
+    int fEntryCount;
+    Node* fRoot;
+    SkSList<Entry> fDeferred;
 
     SkQuadTree(const SkIRect& bounds);
-
-    // This is the count of data elements (rather than total nodes in the tree)
-    int fCount;
-
-    QuadTreeNode* fRoot;
+    Node* pickChild(Node* node, const SkIRect& bounds) const;
+    void insert(Node* node, Entry* entry);
+    void search(Node* node, const SkIRect& query, SkTDArray<void*>* results) const;
+    void clear(Node* node);
+    int getDepth(Node* node) const;
 
     typedef SkBBoxHierarchy INHERITED;
 };