From acc71aa5c2e9349d9501d1b2a6cb6a33325cd73c Mon Sep 17 00:00:00 2001 From: "bsalomon@google.com" Date: Mon, 3 Dec 2012 19:18:57 +0000 Subject: [PATCH] Revert 6649 due to build breaks. git-svn-id: http://skia.googlecode.com/svn/trunk@6651 2bbb7eff-a529-9590-31e7-b0007b416f81 --- include/core/SkTInternalLList.h | 72 ------------------------- src/core/SkTLList.h | 82 +--------------------------- tests/LListTest.cpp | 95 ++------------------------------- 3 files changed, 7 insertions(+), 242 deletions(-) diff --git a/include/core/SkTInternalLList.h b/include/core/SkTInternalLList.h index 78c82bab7e..32245b51eb 100644 --- a/include/core/SkTInternalLList.h +++ b/include/core/SkTInternalLList.h @@ -109,64 +109,6 @@ public: #endif } - /** - * Inserts a new list entry before an existing list entry. The new entry must not already be - * a member of this or any other list. If existingEntry is NULL then the new entry is added - * at the tail. - */ - void addBefore(T* newEntry, T* existingEntry) { - SkASSERT(NULL != newEntry); - - if (NULL == existingEntry) { - this->addToTail(newEntry); - return; - } - - SkASSERT(this->isInList(existingEntry)); - newEntry->fNext = existingEntry; - T* prev = existingEntry->fPrev; - existingEntry->fPrev = newEntry; - newEntry->fPrev = prev; - if (NULL == prev) { - SkASSERT(fHead == existingEntry); - fHead = newEntry; - } else { - prev->fNext = newEntry; - } -#if SK_DEBUG - newEntry->fList = this; -#endif - } - - /** - * Inserts a new list entry after an existing list entry. The new entry must not already be - * a member of this or any other list. If existingEntry is NULL then the new entry is added - * at the head. - */ - void addAfter(T* newEntry, T* existingEntry) { - SkASSERT(NULL != newEntry); - - if (NULL == existingEntry) { - this->addToHead(newEntry); - return; - } - - SkASSERT(this->isInList(existingEntry)); - newEntry->fPrev = existingEntry; - T* next = existingEntry->fNext; - existingEntry->fNext = newEntry; - newEntry->fNext = next; - if (NULL == next) { - SkASSERT(fTail == existingEntry); - fTail = newEntry; - } else { - next->fPrev = newEntry; - } -#if SK_DEBUG - newEntry->fList = this; -#endif - } - bool isEmpty() const { return NULL == fHead && NULL == fTail; } @@ -226,20 +168,6 @@ public: #ifdef SK_DEBUG void validate() const { SkASSERT(!fHead == !fTail); - Iter iter; - for (T* item = iter.init(*this, Iter::kHead_IterStart); NULL != (item = iter.next()); ) { - SkASSERT(this->isInList(item)); - if (NULL == item->fPrev) { - SkASSERT(fHead == item); - } else { - SkASSERT(item->fPrev->fNext == item); - } - if (NULL == item->fNext) { - SkASSERT(fTail == item); - } else { - SkASSERT(item->fNext->fPrev == item); - } - } } /** diff --git a/src/core/SkTLList.h b/src/core/SkTLList.h index b7934e180f..41f0c0b4af 100644 --- a/src/core/SkTLList.h +++ b/src/core/SkTLList.h @@ -10,14 +10,7 @@ /** 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. - - Elements of the list can be constructed in place using the following macros: - SkNEW_INSERT_IN_LLIST_BEFORE(list, location, type_name, args) - SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args) - where list is a SkTLList*, location is an iterator, and args is the paren-surrounded - constructor arguments for type_name. These macros behave like addBefore() and addAfter(). -*/ + space for entries based on a param passed to the constructor. */ template class SkTLList : public SkNoncopyable { private: @@ -30,9 +23,6 @@ private: typedef SkTInternalLList NodeList; public: - - class Iter; - /** 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) { @@ -73,22 +63,6 @@ public: this->validate(); } - /** Adds a new element to the list before the location indicated by the iterator. If the - iterator refers to a NULL location then the new element is added at the tail */ - void addBefore(const T& t, const Iter& location) { - SkNEW_PLACEMENT_ARGS(this->internalAddBefore(location), T, (t)); - } - - /** Adds a new element to the list after the location indicated by the iterator. If the - iterator refers to a NULL location then the new element is added at the head */ - void addAfter(const T& t, const Iter& location) { - SkNEW_PLACEMENT_ARGS(this->internalAddAfter(location), T, (t)); - } - - /** Convenience methods for getting an iterator initialized to the head/tail of the list. */ - Iter headIter() const { return Iter(*this, Iter::kHead_IterStart); } - Iter tailIter() const { return Iter(*this, Iter::kTail_IterStart); } - void popHead() { this->validate(); Node* node = fList.head(); @@ -181,9 +155,6 @@ public: Iter& operator= (const Iter& iter) { INHERITED::operator=(iter); return *this; } private: - friend class SkTLList; - Node* getNode() { return INHERITED::get(); } - T* nodeToObj(Node* node) { if (NULL != node) { return reinterpret_cast(node->fObj); @@ -193,12 +164,6 @@ public: } }; - // For use with operator new - enum Placement { - kBefore_Placement, - kAfter_Placement, - }; - private: struct Block { int fNodesInUse; @@ -233,6 +198,7 @@ private: fList.remove(node); reinterpret_cast(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) { @@ -299,52 +265,8 @@ private: #endif } - // Support in-place initializing of objects inserted into the list via operator new. - template - friend void *operator new(size_t, - SkTLList* list, - Placement placement, - const typename SkTLList::Iter& location); - - // Helpers that insert the node and returns a pointer to where the new object should be init'ed. - void* internalAddBefore(Iter location) { - this->validate(); - Node* node = this->createNode(); - fList.addBefore(node, location.getNode()); - this->validate(); - return node->fObj; - } - - void* internalAddAfter(Iter location) { - this->validate(); - Node* node = this->createNode(); - fList.addAfter(node, location.getNode()); - this->validate(); - return node->fObj; - } - NodeList fList; NodeList fFreeList; int fCount; int fAllocCnt; - }; - -// Use the below macros rather than calling this directly -template -inline void *operator new(size_t, SkTLList* list, - typename SkTLList::Placement placement, - const typename SkTLList::Iter& location) { - SkASSERT(NULL != list); - if (SkTLList::kBefore_Placement == placement) { - return list->internalAddBefore(location); - } else { - return list->internalAddAfter(location); - } -} - -#define SkNEW_INSERT_IN_LLIST_BEFORE(list, location, type_name, args) \ - (new (list, SkTLList< type_name >::kBefore_Placement, location) type_name args) - -#define SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args) \ - (new (list, SkTLList< type_name >::kAfter_Placement, location) type_name args) \ No newline at end of file diff --git a/tests/LListTest.cpp b/tests/LListTest.cpp index 985e6754ea..65470aeb55 100644 --- a/tests/LListTest.cpp +++ b/tests/LListTest.cpp @@ -37,7 +37,6 @@ static void check_list(const SkTInternalLList& list, bool in0, bool in1, bool in2, bool in3, ListElement elements[4]) { - list.validate(); REPORTER_ASSERT(reporter, empty == list.isEmpty()); #if SK_DEBUG REPORTER_ASSERT(reporter, numElements == list.countEntries()); @@ -96,29 +95,6 @@ static void TestTInternalLList(skiatest::Reporter* reporter) { // list should be empty again check_list(list, reporter, true, 0, false, false, false, false, elements); - - // test out methods that add to the middle of the list. - list.addAfter(&elements[1], NULL); - check_list(list, reporter, false, 1, false, true, false, false, elements); - - list.remove(&elements[1]); - - list.addBefore(&elements[1], NULL); - check_list(list, reporter, false, 1, false, true, false, false, elements); - - list.addBefore(&elements[0], &elements[1]); - check_list(list, reporter, false, 2, true, true, false, false, elements); - - list.addAfter(&elements[3], &elements[1]); - check_list(list, reporter, false, 3, true, true, false, true, elements); - - list.addBefore(&elements[2], &elements[3]); - check_list(list, reporter, false, 4, true, true, true, true, elements); - - cur = iter.init(list, Iter::kHead_IterStart); - for (int i = 0; NULL != cur; ++i, cur = iter.next()) { - REPORTER_ASSERT(reporter, cur->fID == i); - } } static void TestTLList(skiatest::Reporter* reporter) { @@ -162,23 +138,12 @@ static void TestTLList(skiatest::Reporter* reporter) { REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID); REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID); REPORTER_ASSERT(reporter, list1 == list2); - - list2.reset(); - - // use both before/after in-place construction on an empty list - SkNEW_INSERT_IN_LLIST_BEFORE(&list2, list2.headIter(), ListElement, (1)); - REPORTER_ASSERT(reporter, list2 == list1); - list2.reset(); - SkNEW_INSERT_IN_LLIST_AFTER(&list2, list2.tailIter(), ListElement, (1)); - REPORTER_ASSERT(reporter, list2 == list1); - // 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); @@ -198,64 +163,14 @@ static void TestTLList(skiatest::Reporter* reporter) { #endif REPORTER_ASSERT(reporter, list1.isEmpty() && list2.isEmpty()); - // randomly perform insertions and deletions on a list and perform tests int count = 0; for (int j = 0; j < 100; ++j) { if (list1.isEmpty() || random.nextBiasedBool(3 * SK_Scalar1 / 4)) { - int id = j; - // Choose one of three ways to insert a new element: at the head, at the tail, - // before a random element, after a random element - int numValidMethods = 0 == count ? 2 : 4; - int insertionMethod = random.nextULessThan(numValidMethods); - switch (insertionMethod) { - case 0: - list1.addToHead(ListElement(id)); - break; - case 1: - list1.addToTail(ListElement(id)); - break; - case 2: // fallthru to share code that picks random element. - case 3: { - int n = random.nextULessThan(list1.count()); - Iter iter = list1.headIter(); - // remember the elements before/after the insertion point. - while (n--) { - iter.next(); - } - Iter prev(iter); - Iter next(iter); - next.next(); - prev.prev(); - - SkASSERT(NULL != iter.get()); - // insert either before or after the iterator, then check that the - // surrounding sequence is correct. - if (2 == insertionMethod) { - SkNEW_INSERT_IN_LLIST_BEFORE(&list1, iter, ListElement, (id)); - Iter newItem(iter); - newItem.prev(); - REPORTER_ASSERT(reporter, newItem.get()->fID == id); - - if (NULL != next.get()) { - REPORTER_ASSERT(reporter, next.prev()->fID == iter.get()->fID); - } - if (NULL != prev.get()) { - REPORTER_ASSERT(reporter, prev.next()->fID == id); - } - } else { - SkNEW_INSERT_IN_LLIST_AFTER(&list1, iter, ListElement, (id)); - Iter newItem(iter); - newItem.next(); - REPORTER_ASSERT(reporter, newItem.get()->fID == id); - - if (NULL != next.get()) { - REPORTER_ASSERT(reporter, next.prev()->fID == id); - } - if (NULL != prev.get()) { - REPORTER_ASSERT(reporter, prev.next()->fID == iter.get()->fID); - } - } - } + int id = static_cast(random.nextU()); + if (random.nextBool()) { + list1.addToHead(ListElement(id)); + } else { + list1.addToTail(ListElement(id)); } ++count; } else { -- 2.34.1