Reland r6649 with fix for build errors.
git-svn-id: http://skia.googlecode.com/svn/trunk@6653 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/tests/LListTest.cpp b/tests/LListTest.cpp
index 65470ae..c5a5663 100644
--- a/tests/LListTest.cpp
+++ b/tests/LListTest.cpp
@@ -39,6 +39,7 @@
REPORTER_ASSERT(reporter, empty == list.isEmpty());
#if SK_DEBUG
+ list.validate();
REPORTER_ASSERT(reporter, numElements == list.countEntries());
REPORTER_ASSERT(reporter, in0 == list.isInList(&elements[0]));
REPORTER_ASSERT(reporter, in1 == list.isInList(&elements[1]));
@@ -95,6 +96,29 @@
// 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 @@
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 @@
#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 {