Fast implementation of QuadTree

src/core/SkQuadTree.h

 /*
  * Copyright 2014 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #ifndef SkQuadTree_DEFINED
 #define SkQuadTree_DEFINED
 
 #include "SkRect.h"
 #include "SkTDArray.h"
 #include "SkBBoxHierarchy.h"
+#include "SkChunkAlloc.h"
+
+/**
+ * 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 it's elements, or ever delete

[tomhudson, 2014/03/05 11:56:56]

Nit: no apostrophe

[iancottrell, 2014/03/05 12:11:16]

Done.

+ * 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.
+     */
+    void takeAll(SkSList<T>& other) {
+        if (isEmpty()) {
+            swap(other);
+            return;
+        }
+        while(!other.isEmpty()) {

[tomhudson, 2014/03/05 11:56:56]

Can't we just graft the other list onto this one? Or is this safer in some
sense?

(Either way we'll need to traverse *one* of the lists, I guess, so maybe no
win.)

[iancottrell, 2014/03/05 12:11:16]

Yes, I decided it made the code less readable for no average performance gain,
so I did not bother.

+            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() {
+        return fHead == NULL;
+    }
+
+    /**
+     * Swaps the contents of this list with another one.
+     */
+    void swap(SkSList<T>& other) {
+        SkTSwap(fHead, other.fHead);
+    }
+
+    /**
+     * Returns the count of elements in the list.
+     */
+    int getCount() {
+        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]);
+        }
+    }
+
+};
 
 /**
  * An QuadTree implementation. In short, it is a tree containing a hierarchy of bounding rectangles

[tomhudson, 2014/03/05 11:56:56]

Nit-among-nits: An -> A?

[iancottrell, 2014/03/05 12:11:16]

Done.

  * in which each internal node has exactly four children.
  *
  * For more details see:
  *
  * http://en.wikipedia.org/wiki/Quadtree
  */
 class SkQuadTree : public SkBBoxHierarchy {
 public:
     SK_DECLARE_INST_COUNT(SkQuadTree)
 
     /**
      * Create a new QuadTree
      */
     static SkQuadTree* Create(const SkIRect& bounds);
     virtual ~SkQuadTree();
 
     /**
      * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
      * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load
      * a large batch of nodes at once, which tends to be faster and produce a better tree).
      *  @param data The data value
      *  @param bounds The corresponding bounding box
      *  @param defer Can this insert be deferred? (this may be ignored)
      */
     virtual void insert(void* data, const SkIRect& bounds, bool defer = false) SK_OVERRIDE;
 
     /**
      * 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
      */
     virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;
 
     virtual void clear() SK_OVERRIDE;
 
     /**
      * Gets the depth of the tree structure
      */
     virtual int getDepth() const SK_OVERRIDE;
 
     /**
      * 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) {

[tomhudson, 2014/03/05 11:56:56]

Nit: Skia style has more spaces than you do. (At least one, after the for)

[iancottrell, 2014/03/05 12:11:16]

Done.

+                fChildren[index] = NULL;
+            }
+        }
+        SkSList<Entry> fEntries;
+        SkIRect fBounds;
+        SkIPoint fCenter;

[tomhudson, 2014/03/05 11:56:56]

// Uninitialized until the Node has children (fChildren != NULL and not in free
list).

[iancottrell, 2014/03/05 12:11:16]

Done. Also renamed for clarity.

+        union {

[tomhudson, 2014/03/05 11:56:56]

// A Node is only in a SkFreeList when it is free, and has no children.

[iancottrell, 2014/03/05 12:11:16]

Done.

+            Node* fNext;
+            Node* fChildren[kChildCount];
+        };
+    };
+
+    SkFreeList<Entry> fAllEntries;
+    SkFreeList<Node> fAllNodes;

[tomhudson, 2014/03/05 11:56:56]

This isn't really *All*Nodes, it's all nodes not currently part of the universe.
Spare nodes? Free nodes? (Yeah, the type name implies it's a freelist, but the
variable name is what we see at callsites.)

[iancottrell, 2014/03/05 12:11:16]

Done.

+    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;
 };
 
 #endif