Revert change accidentally committed.

git-svn-id: http://skia.googlecode.com/svn/trunk@6645 2bbb7eff-a529-9590-31e7-b0007b416f81

5 files changed, 91 insertions, 503 deletions

diff --git a/gyp/core.gypi b/gyp/core.gypi
index f3402b1c2f..960af338a9 100644
--- a/gyp/core.gypi
+++ b/gyp/core.gypi
@@ -164,7 +164,6 @@
         '<(skia_src_path)/core/SkTextFormatParams.h',
         '<(skia_src_path)/core/SkTileGrid.cpp',
         '<(skia_src_path)/core/SkTileGrid.h',
-        '<(skia_src_path)/core/SkTLList.h',
         '<(skia_src_path)/core/SkTLS.cpp',
         '<(skia_src_path)/core/SkTSearch.cpp',
         '<(skia_src_path)/core/SkTSort.h',
diff --git a/gyp/tests.gyp b/gyp/tests.gyp
index 3353d9a227..1c649336dc 100644
--- a/gyp/tests.gyp
+++ b/gyp/tests.gyp
@@ -56,7 +56,6 @@
         '../tests/GrMemoryPoolTest.cpp',
         '../tests/HashCacheTest.cpp',
         '../tests/InfRectTest.cpp',
-        '../tests/LListTest.cpp',
         '../tests/MathTest.cpp',
         '../tests/MatrixTest.cpp',
         '../tests/Matrix44Test.cpp',
@@ -92,6 +91,7 @@
         '../tests/StreamTest.cpp',
         '../tests/StringTest.cpp',
         '../tests/StrokeTest.cpp',
+        '../tests/TDLinkedListTest.cpp',
         '../tests/Test.cpp',
         '../tests/Test.h',
         '../tests/TestSize.cpp',
diff --git a/src/core/SkTLList.h b/src/core/SkTLList.h
deleted file mode 100644
index dd3d4fb244..0000000000
--- a/src/core/SkTLList.h
+++ /dev/null
@@ -1,270 +0,0 @@
-/*
- * Copyright 2012 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-
-#include "SkTInternalLList.h"
-#include "SkTemplates.h"
-
-/** Doubly-linked list of objects. The objects' lifetimes are controlled by the list. I.e. the
-    the list creates the objects and they are deleted upon removal. */
-template <typename T>
-class SkTLList : public SkNoncopyable {
-private:
-    struct Block;
-    struct Node {
-        SkAlignedSTStorage<1, T> fObj;
-        SK_DECLARE_INTERNAL_LLIST_INTERFACE(Node);
-        Block* fBlock;
-    };
-    typedef SkTInternalLList<Node> NodeList;
-
-public:
-    /** allocCnt is the number of objects to allocate as a group. In the worst case fragmentation
-        each object is using the space required for allocCnt unfragmented objects. */
-    SkTLList(int allocCnt = 1) : fCount(0), fAllocCnt(allocCnt) {
-        SkASSERT(allocCnt > 0);
-        this->validate();
-    }
-
-    ~SkTLList() {
-        this->validate();
-        NodeList::Iter iter;
-        Node* node = iter.init(fList, Iter::kHead_IterStart);
-        while (NULL != node) {
-            reinterpret_cast<T*>(node->fObj.get())->~T();
-            Block* block = node->fBlock;
-            node = iter.next();
-            if (0 == --block->fNodesInUse) {
-                sk_free(block);
-                for (int i = 0; i < fAllocCnt; ++i) {
-                    block->fNodes[i].~Node();
-                }
-            }
-        }
-    }
-    
-    void addToHead(const T& t) {
-        this->validate();
-        Node* node = this->createNode();
-        fList.addToHead(node);
-        SkNEW_PLACEMENT_ARGS(node->fObj.get(), T, (t));
-        this->validate();
-    }
-
-    void addToTail(const T& t) {
-        this->validate();
-        Node* node = this->createNode();
-        fList.addToTail(node);
-        SkNEW_PLACEMENT_ARGS(node->fObj.get(), T, (t));
-        this->validate();
-    }
-
-    void popHead() {
-        this->validate();
-        Node* node = fList.head();
-        if (NULL != node) {
-            this->removeNode(node);
-        }
-        this->validate();
-    }
-
-    void popTail() {
-        this->validate();
-        Node* node = fList.head();
-        if (NULL != node) {
-            this->removeNode(node);
-        }
-        this->validate();
-    }
-
-    void remove(T* t) {
-        this->validate();
-        Node* node = reinterpret_cast<Node*>(t);
-        SkASSERT(node->fObj.get() == t);
-        this->removeNode(node);
-        this->validate();
-    }
-
-    void reset() {
-        this->validate();
-        Iter iter(*this, Iter::kHead_IterStart);
-        while (iter.get()) {
-            Iter next = iter;
-            next.next();
-            this->remove(iter.get());
-            iter = next;
-        }
-        SkASSERT(0 == fCount);
-        this->validate();
-    }
-
-    int count() const { return fCount; }
-    bool isEmpty() const { this->validate(); return NULL == fCount; }
-
-    bool operator== (const SkTLList& list) const {
-        if (this == &list) {
-            return true;
-        }
-        if (fCount != list.fCount) {
-            return false;
-        }
-        for (Iter a(*this, Iter::kHead_IterStart), b(list, Iter::kHead_IterStart);
-             a.get();
-             a.next(), b.next()) {
-            SkASSERT(NULL != b.get());
-            if (!(*a.get() == *b.get())) {
-                return false;
-            }
-        }
-        return true;
-    }
-    bool operator!= (const SkTLList& list) const { return !(*this == list); }
-
-    /** The iterator becomes invalid if the element it refers to is removed from the list. */
-    class Iter : private NodeList::Iter {
-    private:
-        typedef typename NodeList::Iter INHERITED;
-
-    public:
-        typedef typename INHERITED::IterStart IterStart;
-        //!< Start the iterator at the head of the list.
-        static const IterStart kHead_IterStart = INHERITED::kHead_IterStart;
-        //!< Start the iterator at the tail of the list.
-        static const IterStart kTail_IterStart = INHERITED::kTail_IterStart;
-
-        Iter() : INHERITED() {}
-
-        Iter(const SkTLList& list, IterStart start) : INHERITED() {
-            INHERITED::init(list.fList, start);
-        }
-
-        T* init(const SkTLList& list, IterStart start) {
-            return this->nodeToObj(INHERITED::init(list.fList, start));
-        }
-
-        T* get() { return this->nodeToObj(INHERITED::get()); }
-
-        T* next() { return this->nodeToObj(INHERITED::next()); }
-
-        T* prev() { return this->nodeToObj(INHERITED::prev()); }
-
-        Iter& operator= (const Iter& iter) { INHERITED::operator=(iter); return *this; }
-
-    private:
-        T* nodeToObj(Node* node) {
-            if (NULL != node) {
-                return reinterpret_cast<T*>(node->fObj.get());
-            } else {
-                return NULL;
-            }
-        }
-    };
-
-private:
-    struct Block {
-        int fNodesInUse;
-        Node fNodes[1];
-    };
-
-    size_t blockSize() const { return sizeof(Block) + sizeof(Node) * (fAllocCnt-1); }
-
-    Node* createNode() {
-        Node* node;
-        if (node = fFreeList.head()) {
-            fFreeList.remove(node);
-            ++node->fBlock->fNodesInUse;
-        } else {
-            Block* block = reinterpret_cast<Block*>(sk_malloc_flags(this->blockSize(), 0));
-            node = &block->fNodes[0];
-            SkNEW_PLACEMENT(node, Node);
-            node->fBlock = block;
-            block->fNodesInUse = 1;
-            for (int i = 1; i < fAllocCnt; ++i) {
-                SkNEW_PLACEMENT(block->fNodes + i, Node);
-                fFreeList.addToHead(block->fNodes + i);
-                block->fNodes[i].fBlock = block;
-            }
-        }
-        ++fCount;
-        return node;
-    }
-
-    void removeNode(Node* node) {
-        SkASSERT(NULL != node);
-        fList.remove(node);
-        ((T*)node->fObj.get())->~T();
-        if (0 == --node->fBlock->fNodesInUse) {
-            Block* block = node->fBlock;
-            for (int i = 0; i < fAllocCnt; ++i) {
-                if (block->fNodes + i != node) {
-                    fFreeList.remove(block->fNodes + i);
-                }
-                block->fNodes[i].~Node();
-            }
-            sk_free(block);
-        } else {
-            fFreeList.addToHead(node);
-        }
-        --fCount;
-        this->validate();
-    }
-
-    void validate() const {
-#ifdef SK_DEBUG
-        SkASSERT((0 == fCount) == fList.isEmpty());
-        SkASSERT((0 != fCount) || fFreeList.isEmpty());
-
-        fList.validate();
-        fFreeList.validate();
-        NodeList::Iter iter;
-        Node* freeNode = iter.init(fFreeList, Iter::kHead_IterStart);
-        while (freeNode) {
-            SkASSERT(fFreeList.isInList(freeNode));
-            Block* block = freeNode->fBlock;
-            SkASSERT(block->fNodesInUse > 0 && block->fNodesInUse < fAllocCnt);
-
-            int activeCnt = 0;
-            int freeCnt = 0;
-            for (int i = 0; i < fAllocCnt; ++i) {
-                bool free = fFreeList.isInList(block->fNodes + i);
-                bool active = fList.isInList(block->fNodes + i);
-                SkASSERT(free != active);
-                activeCnt += active;
-                freeCnt += free;
-            }
-            SkASSERT(activeCnt == block->fNodesInUse);
-            freeNode = iter.next();
-        }
-
-        int count = 0;
-        Node* activeNode = iter.init(fList, Iter::kHead_IterStart);
-        while (activeNode) {
-            ++count;
-            SkASSERT(fList.isInList(activeNode));
-            Block* block = activeNode->fBlock;
-            SkASSERT(block->fNodesInUse > 0 && block->fNodesInUse <= fAllocCnt);
-
-            int activeCnt = 0;
-            int freeCnt = 0;
-            for (int i = 0; i < fAllocCnt; ++i) {
-                bool free = fFreeList.isInList(block->fNodes + i);
-                bool active = fList.isInList(block->fNodes + i);
-                SkASSERT(free != active);
-                activeCnt += active;
-                freeCnt += free;
-            }
-            SkASSERT(activeCnt == block->fNodesInUse);
-            activeNode = iter.next();
-        }
-        SkASSERT(count == fCount);
-#endif
-    }
-
-    NodeList fList;
-    NodeList fFreeList;
-    int fCount;
-    int fAllocCnt;
-};
\ No newline at end of file
diff --git a/tests/LListTest.cpp b/tests/LListTest.cpp
deleted file mode 100644
index 9d48e28135..0000000000
--- a/tests/LListTest.cpp
+++ /dev/null
@@ -1,231 +0,0 @@
-/*
- * Copyright 2012 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-
-#include "Test.h"
-#include "SkRandom.h"
-#include "SkTInternalLList.h"
-#include "SkTLList.h"
-
-class ListElement {
-public:
-    ListElement(int id) : fID(id) {
-    }
-    bool operator== (const ListElement& other) { return fID == other.fID; }
-
-#ifdef SK_ENABLE_INST_COUNT
-    // Make the instance count available publicly.
-    static int InstanceCount() { return GetInstanceCount(); }
-#endif
-
-    int fID;
-
-private:
-    SK_DECLARE_INST_COUNT_ROOT(ListElement);
-    SK_DECLARE_INTERNAL_LLIST_INTERFACE(ListElement);
-};
-
-SK_DEFINE_INST_COUNT(ListElement);
-
-static void check_list(const SkTInternalLList<ListElement>& list,
-                       skiatest::Reporter* reporter,
-                       bool empty,
-                       int numElements,
-                       bool in0, bool in1, bool in2, bool in3,
-                       ListElement elements[4]) {
-
-    REPORTER_ASSERT(reporter, empty == list.isEmpty());
-#if SK_DEBUG
-    REPORTER_ASSERT(reporter, numElements == list.countEntries());
-    REPORTER_ASSERT(reporter, in0 == list.isInList(&elements[0]));
-    REPORTER_ASSERT(reporter, in1 == list.isInList(&elements[1]));
-    REPORTER_ASSERT(reporter, in2 == list.isInList(&elements[2]));
-    REPORTER_ASSERT(reporter, in3 == list.isInList(&elements[3]));
-#endif
-}
-
-static void TestTInternalLList(skiatest::Reporter* reporter) {
-    SkTInternalLList<ListElement> list;
-    ListElement elements[4] = {
-        ListElement(0),
-        ListElement(1),
-        ListElement(2),
-        ListElement(3),
-    };
-
-    // list should be empty to start with
-    check_list(list, reporter, true, 0, false, false, false, false, elements);
-
-    list.addToHead(&elements[0]);
-
-    check_list(list, reporter, false, 1, true, false, false, false, elements);
-
-    list.addToHead(&elements[1]);
-    list.addToHead(&elements[2]);
-    list.addToHead(&elements[3]);
-
-    check_list(list, reporter, false, 4, true, true, true, true, elements);
-
-    // test out iterators
-    typedef SkTInternalLList<ListElement>::Iter Iter;
-    Iter iter;
-
-    ListElement* cur = iter.init(list, Iter::kHead_IterStart);
-    for (int i = 0; NULL != cur; ++i, cur = iter.next()) {
-        REPORTER_ASSERT(reporter, cur->fID == 3-i);
-    }
-
-    cur = iter.init(list, Iter::kTail_IterStart);
-    for (int i = 0; NULL != cur; ++i, cur = iter.prev()) {
-        REPORTER_ASSERT(reporter, cur->fID == i);
-    }
-
-    // remove middle, frontmost then backmost
-    list.remove(&elements[1]);
-    list.remove(&elements[3]);
-    list.remove(&elements[0]);
-
-    check_list(list, reporter, false, 1, false, false, true, false, elements);
-
-    // remove last element
-    list.remove(&elements[2]);
-
-    // list should be empty again
-    check_list(list, reporter, true, 0, false, false, false, false, elements);
-}
-
-static void TestTLList(skiatest::Reporter* reporter) {
-    typedef SkTLList<ListElement> ElList;
-    typedef ElList::Iter Iter;
-    SkRandom random;
-
-    for (int i = 1; i <= 16; i *= 2) {
-
-        ElList list1(i);
-        ElList list2(i);
-        Iter iter1;
-        Iter iter2;
-        Iter iter3;
-        Iter iter4;
-
-#ifdef SK_ENABLE_INST_COUNT
-        SkASSERT(0 == ListElement::InstanceCount());
-#endif
-
-        REPORTER_ASSERT(reporter, list1.isEmpty());
-        REPORTER_ASSERT(reporter, NULL == iter1.init(list1, Iter::kHead_IterStart));
-        REPORTER_ASSERT(reporter, NULL == iter1.init(list1, Iter::kTail_IterStart));
-        // Try popping an empty list
-        list1.popHead();
-        list1.popTail();
-        REPORTER_ASSERT(reporter, list1.isEmpty());
-        REPORTER_ASSERT(reporter, list1 == list2);
-
-        // Create two identical lists, one by appending to head and the other to the head.
-        list1.addToHead(ListElement(1));
-        list2.addToTail(ListElement(1));
-#ifdef SK_ENABLE_INST_COUNT
-        SkASSERT(2 == ListElement::InstanceCount());
-#endif
-        iter1.init(list1, Iter::kHead_IterStart);
-        iter2.init(list1, Iter::kTail_IterStart);
-        REPORTER_ASSERT(reporter, iter1.get()->fID == iter2.get()->fID);
-        iter3.init(list2, Iter::kHead_IterStart);
-        iter4.init(list2, Iter::kTail_IterStart);
-        REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID);
-        REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID);
-        REPORTER_ASSERT(reporter, list1 == list2);
-    
-        // add an element to the second list, check that iters are still valid
-        list2.addToHead(ListElement(2));
-#ifdef SK_ENABLE_INST_COUNT
-        SkASSERT(3 == ListElement::InstanceCount());
-#endif
-        REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID);
-        REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID);
-        REPORTER_ASSERT(reporter, 1 == Iter(list2, Iter::kTail_IterStart).get()->fID);
-        REPORTER_ASSERT(reporter, 2 == Iter(list2, Iter::kHead_IterStart).get()->fID);
-        REPORTER_ASSERT(reporter, list1 != list2);
-        list1.addToHead(ListElement(2));
-        REPORTER_ASSERT(reporter, list1 == list2);
-#ifdef SK_ENABLE_INST_COUNT
-        SkASSERT(4 == ListElement::InstanceCount());
-#endif
-        list1.reset();
-        list2.reset();
-#ifdef SK_ENABLE_INST_COUNT
-        SkASSERT(0 == ListElement::InstanceCount());
-#endif
-        REPORTER_ASSERT(reporter, list1.isEmpty() && list2.isEmpty());
-
-        int count = 0;
-        for (int j = 0; j < 100; ++j) {
-            if (list1.isEmpty() || random.nextBiasedBool(3  * SK_Scalar1 / 4)) {
-                int id = static_cast<int>(random.nextU());
-                if (random.nextBool()) {
-                    list1.addToHead(ListElement(id));
-                } else {
-                    list1.addToTail(ListElement(id));
-                }
-                ++count;
-            } else {
-                // walk to a random place either forward or backwards and remove.
-                int n = random.nextULessThan(list1.count());
-                Iter::IterStart start;
-                ListElement* (Iter::*incrFunc)();
-                
-                if (random.nextBool()) {
-                    start = Iter::kHead_IterStart;
-                    incrFunc = &Iter::next;
-                } else {
-                    start = Iter::kTail_IterStart;
-                    incrFunc = &Iter::prev;
-                }
-
-                // find the element
-                Iter iter(list1, start);
-                while (n--) {
-                    REPORTER_ASSERT(reporter, NULL != iter.get());
-                    (iter.*incrFunc)();
-                }
-                REPORTER_ASSERT(reporter, NULL != iter.get());
-
-                // remember the prev and next elements from the element to be removed
-                Iter prev = iter;
-                Iter next = iter;
-                prev.prev();
-                next.next();
-                list1.remove(iter.get());
-
-                // make sure the remembered next/prev iters still work
-                Iter pn = prev; pn.next();
-                Iter np = next; np.prev();
-                // pn should match next unless the target node was the head, in which case prev
-                // walked off the list.
-                REPORTER_ASSERT(reporter, pn.get() == next.get() || NULL == prev.get());
-                // Similarly, np should match prev unless next originally walked off the tail.
-                REPORTER_ASSERT(reporter, np.get() == prev.get() || NULL == next.get());
-                --count;
-            }
-            REPORTER_ASSERT(reporter, count == list1.count());
-#ifdef SK_ENABLE_INST_COUNT
-            SkASSERT(count == ListElement::InstanceCount());
-#endif
-        }
-        list1.reset();
-#ifdef SK_ENABLE_INST_COUNT
-        SkASSERT(0 == ListElement::InstanceCount());
-#endif
-    }
-}
-
-static void test_llists(skiatest::Reporter* reporter) {
-    TestTInternalLList(reporter);
-    TestTLList(reporter);
-}
-
-#include "TestClassDef.h"
-DEFINE_TESTCLASS("LList", TestLListClass, test_llists)
diff --git a/tests/TDLinkedListTest.cpp b/tests/TDLinkedListTest.cpp
new file mode 100644
index 0000000000..b4ea0b7100
--- /dev/null
+++ b/tests/TDLinkedListTest.cpp
@@ -0,0 +1,90 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "Test.h"
+#include "SkTInternalLList.h"
+
+class ListElement {
+public:
+    ListElement(int id) : fID(id) {
+    }
+
+    int fID;
+
+private:
+    SK_DECLARE_INTERNAL_LLIST_INTERFACE(ListElement);
+};
+
+static void CheckList(const SkTInternalLList<ListElement>& list,
+                      skiatest::Reporter* reporter,
+                      bool empty,
+                      int numElements,
+                      bool in0, bool in1, bool in2, bool in3,
+                      ListElement elements[4]) {
+
+    REPORTER_ASSERT(reporter, empty == list.isEmpty());
+#if SK_DEBUG
+    REPORTER_ASSERT(reporter, numElements == list.countEntries());
+    REPORTER_ASSERT(reporter, in0 == list.isInList(&elements[0]));
+    REPORTER_ASSERT(reporter, in1 == list.isInList(&elements[1]));
+    REPORTER_ASSERT(reporter, in2 == list.isInList(&elements[2]));
+    REPORTER_ASSERT(reporter, in3 == list.isInList(&elements[3]));
+#endif
+}
+
+static void TestTDLinkedList(skiatest::Reporter* reporter) {
+    SkTInternalLList<ListElement> list;
+    ListElement elements[4] = {
+        ListElement(0),
+        ListElement(1),
+        ListElement(2),
+        ListElement(3),
+    };
+
+    // list should be empty to start with
+    CheckList(list, reporter, true, 0, false, false, false, false, elements);
+
+    list.addToHead(&elements[0]);
+
+    CheckList(list, reporter, false, 1, true, false, false, false, elements);
+
+    list.addToHead(&elements[1]);
+    list.addToHead(&elements[2]);
+    list.addToHead(&elements[3]);
+
+    CheckList(list, reporter, false, 4, true, true, true, true, elements);
+
+    // test out iterators
+    typedef SkTInternalLList<ListElement>::Iter Iter;
+    Iter iter;
+
+    ListElement* cur = iter.init(list, Iter::kHead_IterStart);
+    for (int i = 0; NULL != cur; ++i, cur = iter.next()) {
+        REPORTER_ASSERT(reporter, cur->fID == 3-i);
+    }
+
+    cur = iter.init(list, Iter::kTail_IterStart);
+    for (int i = 0; NULL != cur; ++i, cur = iter.prev()) {
+        REPORTER_ASSERT(reporter, cur->fID == i);
+    }
+
+    // remove middle, frontmost then backmost
+    list.remove(&elements[1]);
+    list.remove(&elements[3]);
+    list.remove(&elements[0]);
+
+    CheckList(list, reporter, false, 1, false, false, true, false, elements);
+
+    // remove last element
+    list.remove(&elements[2]);
+
+    // list should be empty again
+    CheckList(list, reporter, true, 0, false, false, false, false, elements);
+}
+
+#include "TestClassDef.h"
+DEFINE_TESTCLASS("TDLinkedList", TestTDLinkedListClass, TestTDLinkedList)