From 08cb7286c6fe50ceaabc15a16f0020d808390f43 Mon Sep 17 00:00:00 2001 From: "bsalomon@google.com" Date: Mon, 3 Dec 2012 15:59:52 +0000 Subject: Revert change accidentally committed. git-svn-id: http://skia.googlecode.com/svn/trunk@6645 2bbb7eff-a529-9590-31e7-b0007b416f81 --- gyp/core.gypi | 1 - gyp/tests.gyp | 2 +- src/core/SkTLList.h | 270 --------------------------------------------- tests/LListTest.cpp | 231 -------------------------------------- tests/TDLinkedListTest.cpp | 90 +++++++++++++++ 5 files changed, 91 insertions(+), 503 deletions(-) delete mode 100644 src/core/SkTLList.h delete mode 100644 tests/LListTest.cpp create mode 100644 tests/TDLinkedListTest.cpp 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 -class SkTLList : public SkNoncopyable { -private: - struct Block; - struct Node { - SkAlignedSTStorage<1, T> fObj; - SK_DECLARE_INTERNAL_LLIST_INTERFACE(Node); - Block* fBlock; - }; - typedef SkTInternalLList 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(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(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(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(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& 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 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::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 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(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& 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 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::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) -- cgit v1.2.3