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"
 

[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:
  *
  * http://en.wikipedia.org/wiki/Quadtree
  */
 class SkQuadTree : public SkBBoxHierarchy {
 public:
     SK_DECLARE_INST_COUNT(SkQuadTree)
 
     /**
      * Create a new QuadTree

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

What is the bounds parameter?
Can the factory ever return NULL? (e.g. on bad input)

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

To be honest, I have no idea why this code has a factory method, I had not
actually looked at it. The implementation just calls new SkQuadTree (does not
even use SkNEW).
I don't think we need it, I will remove it and just make the constructor public.

      */
     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) {
+                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;
 };
 
 #endif