Fast implementation of QuadTree

src/core/SkTInternalSList.h

Index: src/core/SkTInternalSList.h
diff --git a/src/core/SkTInternalSList.h b/src/core/SkTInternalSList.h
new file mode 100644
index 0000000000000000000000000000000000000000..27b3faca86068577dec5d9f7871941019c851c01
--- /dev/null
+++ b/src/core/SkTInternalSList.h
@@ -0,0 +1,130 @@
+/*
+ * 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 SkTInternalSList_DEFINED
+#define SkTInternalSList_DEFINED
+
+#include "SkTInternalLList.h" // for SkPtrWrapper
+
+/**
+ * This macro creates the methods required by the SkTInternalSList class.
+ * It should be instantiated in the private block of the class you want to put
+ * into an SkTInternalSList.
+ * For most use cases you should use SK_DECLARE_INTERNAL_SLIST_INTERFACE and not
+ * this macro. If you care about the field name, or want to re-use an existing
+ * field, then you can use this macro to declare the methods pointing to a
+ * specific field.
+ * Unlike SK_DECLARE_INTERNAL_SLIST_INTERFACE this does not declare the field
+ * itself.
+ * It also makes SkTInternalSList<ClassName> a friend to give it access to the
+ * methods.
+ */
+#define SK_DECLARE_INTERNAL_SLIST_ADAPTER(ClassName, field)     \
+    ClassName* getSListNext() {                                 \

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

don't need this-> here

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

There are cases with template expansion that will insist on it.
I generally try to be over explicit in macros just because you are never sure
where they will be used.
Also will result in compile error if used outside a class declaration this way.

+        return this->field;                                     \
+    }                                                           \
+    void setSListNext(ClassName* next) {                        \

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

same here

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

as above

+        this->field = next;                                     \
+    }                                                           \
+    friend struct SkTInternalSList<ClassName>
+
+/**
+ * This macro declares an fSListNext that auto initializes to NULL and then
+ * uses SK_DECLARE_INTERNAL_SLIST_ADAPTER to add the methods needed by
+ * SkTInternalSList.
+ * It should be instantiated in the private block of the class you want to put
+ * into an SkTInternalSList.
+ */
+#define SK_DECLARE_INTERNAL_SLIST_INTERFACE(ClassName)          \
+    SK_DECLARE_INTERNAL_SLIST_ADAPTER(ClassName, fSListNext);   \
+    SkPtrWrapper<ClassName> fSListNext
+
+/**
+ * An implementation of an intrusive singly linked list.
+ * The type T must have a methods getSListNext and setSListNext that are visible
+ * to the list. The easiest way to do this is with
+ * SK_DECLARE_INTERNAL_SLIST_INTERFACE.
+ * The list does not maintain ownership of any of its elements, or ever delete
+ * them.
+ */
+template<typename T> class SkTInternalSList {
+public:
+    SkTInternalSList() : 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->getSListNext() == NULL);
+        entry->setSListNext(fHead);
+        fHead = entry;
+        ++fCount;
+    }
+
+    /**
+     * Takes all the items from another list.
+     * No ordering guarantees are made, and the other list will be emptied.
+     */
+    void takeAll(SkTInternalSList<T>* other) {

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

this->

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

Done.

+        if (isEmpty()) {

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

this->

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

Done.

+            swap(other);
+            return;
+        }
+        while(!other->isEmpty()) {

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

this->

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

Done.

+            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 (NULL == fHead) {
+            return NULL;
+        }
+        T* result = fHead;
+        fHead = result->getSListNext();
+        result->setSListNext(NULL);
+        --fCount;
+        return result;
+    }
+
+    T* head() const {
+        return fHead;
+    }
+
+    /**
+     * Returns true if the list has no elements.
+     */
+    bool isEmpty() const {
+        return NULL == fHead;
+    }
+
+    /**
+     * Swaps the contents of this list with another one.
+     */
+    void swap(SkTInternalSList<T>* other) {
+        SkTSwap(fHead, other->fHead);
+        SkTSwap(fCount, other->fCount);
+    }
+
+    /**
+     * Returns the count of elements in the list.
+     */
+    int getCount() const {
+        return fCount;
+    }
+private:
+    T* fHead;
+    int fCount;
+};
+
+
+#endif