diff options
| -rw-r--r-- | gyp/core.gypi | 1 | ||||
| -rw-r--r-- | gyp/tests.gyp | 2 | ||||
| -rw-r--r-- | src/core/SkTLList.h | 272 | ||||
| -rw-r--r-- | tests/LListTest.cpp | 233 | ||||
| -rw-r--r-- | tests/TDLinkedListTest.cpp | 90 |
5 files changed, 507 insertions, 91 deletions
diff --git a/gyp/core.gypi b/gyp/core.gypi index 960af338a9..f3402b1c2f 100644 --- a/gyp/core.gypi +++ b/gyp/core.gypi @@ -164,6 +164,7 @@ '<(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 1c649336dc..3353d9a227 100644 --- a/gyp/tests.gyp +++ b/gyp/tests.gyp @@ -56,6 +56,7 @@ '../tests/GrMemoryPoolTest.cpp', '../tests/HashCacheTest.cpp', '../tests/InfRectTest.cpp', + '../tests/LListTest.cpp', '../tests/MathTest.cpp', '../tests/MatrixTest.cpp', '../tests/Matrix44Test.cpp', @@ -91,7 +92,6 @@ '../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 new file mode 100644 index 0000000000..41f0c0b4af --- /dev/null +++ b/src/core/SkTLList.h @@ -0,0 +1,272 @@ +/* + * 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. This class block-allocates + space for entries based on a param passed to the constructor. */ +template <typename T> +class SkTLList : public SkNoncopyable { +private: + struct Block; + struct Node { + char fObj[sizeof(T)]; + SK_DECLARE_INTERNAL_LLIST_INTERFACE(Node); + Block* fBlock; // owning block. + }; + 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(); + typename NodeList::Iter iter; + Node* node = iter.init(fList, Iter::kHead_IterStart); + while (NULL != node) { + reinterpret_cast<T*>(node->fObj)->~T(); + Block* block = node->fBlock; + node = iter.next(); + if (0 == --block->fNodesInUse) { + for (int i = 0; i < fAllocCnt; ++i) { + block->fNodes[i].~Node(); + } + sk_free(block); + } + } + } + + void addToHead(const T& t) { + this->validate(); + Node* node = this->createNode(); + fList.addToHead(node); + SkNEW_PLACEMENT_ARGS(node->fObj, T, (t)); + this->validate(); + } + + void addToTail(const T& t) { + this->validate(); + Node* node = this->createNode(); + fList.addToTail(node); + SkNEW_PLACEMENT_ARGS(node->fObj, 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(reinterpret_cast<T*>(node->fObj) == 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 0 == 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()); // already checked that counts match. + 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() {} + + Iter(const SkTLList& list, IterStart start) { + 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); + } 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 = fFreeList.head(); + if (NULL != node) { + 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); + reinterpret_cast<T*>(node->fObj)->~T(); + if (0 == --node->fBlock->fNodesInUse) { + // Delete a block when it no longer has any nodes in use to reduce memory consumption. + 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(); + typename 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; +}; diff --git a/tests/LListTest.cpp b/tests/LListTest.cpp new file mode 100644 index 0000000000..65470aeb55 --- /dev/null +++ b/tests/LListTest.cpp @@ -0,0 +1,233 @@ +/* + * 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 tail. + 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 + REPORTER_ASSERT(reporter, !list1.isEmpty()); + + 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 deleted file mode 100644 index b4ea0b7100..0000000000 --- a/tests/TDLinkedListTest.cpp +++ /dev/null @@ -1,90 +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 "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) |