diff options
| -rw-r--r-- | include/core/SkTInternalLList.h | 72 | ||||
| -rw-r--r-- | src/core/SkTLList.h | 82 | ||||
| -rw-r--r-- | tests/LListTest.cpp | 95 |
3 files changed, 242 insertions, 7 deletions
diff --git a/include/core/SkTInternalLList.h b/include/core/SkTInternalLList.h index 32245b51eb..78c82bab7e 100644 --- a/include/core/SkTInternalLList.h +++ b/include/core/SkTInternalLList.h @@ -109,6 +109,64 @@ 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; } @@ -168,6 +226,20 @@ 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 41f0c0b4af..b7934e180f 100644 --- a/src/core/SkTLList.h +++ b/src/core/SkTLList.h @@ -10,7 +10,14 @@ /** 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. */ + 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<type_name>*, location is an iterator, and args is the paren-surrounded + constructor arguments for type_name. These macros behave like addBefore() and addAfter(). +*/ template <typename T> class SkTLList : public SkNoncopyable { private: @@ -23,6 +30,9 @@ private: typedef SkTInternalLList<Node> 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) { @@ -63,6 +73,22 @@ 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(); @@ -155,6 +181,9 @@ 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<T*>(node->fObj); @@ -164,6 +193,12 @@ public: } }; + // For use with operator new + enum Placement { + kBefore_Placement, + kAfter_Placement, + }; + private: struct Block { int fNodesInUse; @@ -198,7 +233,6 @@ private: 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) { @@ -265,8 +299,52 @@ private: #endif } + // Support in-place initializing of objects inserted into the list via operator new. + template <typename S> + friend void *operator new(size_t, + SkTLList<S>* list, + Placement placement, + const typename SkTLList<S>::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 <typename T> +inline void *operator new(size_t, SkTLList<T>* list, + typename SkTLList<T>::Placement placement, + const typename SkTLList<T>::Iter& location) { + SkASSERT(NULL != list); + if (SkTLList<T>::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 65470aeb55..985e6754ea 100644 --- a/tests/LListTest.cpp +++ b/tests/LListTest.cpp @@ -37,6 +37,7 @@ static void check_list(const SkTInternalLList<ListElement>& 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()); @@ -95,6 +96,29 @@ 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) { @@ -138,12 +162,23 @@ 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); @@ -163,14 +198,64 @@ 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 = static_cast<int>(random.nextU()); - if (random.nextBool()) { - list1.addToHead(ListElement(id)); - } else { - list1.addToTail(ListElement(id)); + 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); + } + } + } } ++count; } else { |