Fast implementation of QuadTree

src/core/SkFreeList.h

Index: src/core/SkFreeList.h
diff --git a/src/core/SkFreeList.h b/src/core/SkFreeList.h
new file mode 100644
index 0000000000000000000000000000000000000000..1bbf40cac05934179a7604d2987d372411906b71
--- /dev/null
+++ b/src/core/SkFreeList.h
@@ -0,0 +1,88 @@
+/*
+ * 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 SkFreeList_DEFINED
+#define SkFreeList_DEFINED
+
+#include "SkTInternalSList.h"

[robertphillips, 2014/03/07 16:01:35]

Is this needed?

[iancottrell, 2014/03/07 16:11:14]

Yes.

+#include "SkRect.h"

[robertphillips, 2014/03/07 16:01:35]

Is this needed?

[iancottrell, 2014/03/07 16:11:14]

Done.

+#include "SkTDArray.h"

[robertphillips, 2014/03/07 16:01:35]

Do we need to include SkBBoxHierarchy.h?

[iancottrell, 2014/03/07 16:11:14]

Done.

+#include "SkBBoxHierarchy.h"
+
+
+/**
+ * An implementation of a self growing free list of objects.

[reed1, 2014/03/07 15:18:38]

I still don't grok what this class does. Is it effectively a heap, returning
space for new objects, and recycling space after they have been destroyed?

[robertphillips, 2014/03/07 16:01:35]

Apropos this comment, renaming it SkBlockMgr might be clearer. Maybe mention
that it is only for objects that can participate in an internal list?

[iancottrell, 2014/03/07 16:02:34]

I have renamed some stuff and added comments to make it clearer.

+ * 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.
+ */

[robertphillips, 2014/03/07 16:01:35]

growth -> numItemsPerBlock?

[iancottrell, 2014/03/07 16:11:14]

Done.

+template<typename T, int growth = 4096/sizeof(T)> class SkFreeList {
+public:
+    SkFreeList() {}
+    ~SkFreeList() {

[robertphillips, 2014/03/07 16:01:35]

Couldn't we add an assert here that all the managed object are back in the
fAvailable list?

[iancottrell, 2014/03/07 16:11:14]

There is no reason that should have to be the case. So long as the lifetimes are
coincident, why do the work of putting them all back. QuadTree does not.

+        while(!fBlocks.isEmpty()) { SkDELETE(fBlocks.pop()); }

[reed1, 2014/03/07 15:18:38]

style nit: 

while (..) {
    ...
}

[iancottrell, 2014/03/07 16:02:34]

Done.

+    }
+
+    /**
+     * Push an item into the free list.
+     * The item does not have to have come from the free list, but if it did not
+     * it must have a lifetime greater than the free list does.
+     * This method is *not* thread safe.
+     */
+    void push(T* entry) {
+        fAvailable.push(entry);
+    }
+
+    /**
+     * Takes all the items from another list.

[reed1, 2014/03/07 15:18:38]

- what is the state of other after this call?
- in what order were the items added to this?

please answer in the form of more dox

[iancottrell, 2014/03/07 16:02:34]

Sorry, I fixed the docs on list, but this was copied earlier.
Order is not relevant because this is not an iterable container.

+     */
+    void takeAll(SkTInternalSList<T>* other) {
+        fAvailable.takeAll(other);
+    }
+
+    /**
+     * 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() {

[reed1, 2014/03/07 15:18:38]

wow, this name is really confusing, since pop() is growing the collection.

Does this method return space for a new T to be stored? (like new)
Does this method initialize the space using T()?

[iancottrell, 2014/03/07 16:02:34]

Renamed, and comments added.

+        if (fAvailable.isEmpty()) { grow(); }

[reed1, 2014/03/07 15:18:38]

style nit:

if (...) {
   ...
}

[iancottrell, 2014/03/07 16:02:34]

Done.

+        return fAvailable.pop();
+    }
+private:
+    /**
+     * The type for a new block of entries for the list.
+     */
+    struct Block {
+        T entries[growth];
+        SK_DECLARE_INTERNAL_SLIST_INTERFACE(Block);
+    };
+    SkTInternalSList<Block> fBlocks;
+    SkTInternalSList<T> fAvailable;
+
+    /**
+     * When the free list runs out of items, this method is called to allocate
+     * a new block of them.
+     * It calls the constructors and then pushes the nodes into the available
+     * list.
+     */
+    void grow() {
+        Block* block = SkNEW(Block);
+        fBlocks.push(block);
+        for(int index = 0; index < growth; ++index) {

[robertphillips, 2014/03/07 16:01:35]

this->push

[iancottrell, 2014/03/07 16:11:14]

Already changed.

+            push(&block->entries[index]);
+        }
+    }
+
+};
+
+#endif