1bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com/* 2bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com * Copyright 2012 Google Inc. 3bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com * 4bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com * Use of this source code is governed by a BSD-style license that can be 5bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com * found in the LICENSE file. 6bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com */ 7bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 8bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com#include "SkRandom.h" 9bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com#include "SkTInternalLList.h" 10bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com#include "SkTLList.h" 118f6884aab8aecd7657cf3f9cdbc682f0deca29c5tfarina@chromium.org#include "Test.h" 12bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 13bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.comclass ListElement { 14bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.compublic: 15bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com ListElement(int id) : fID(id) { 16bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 17bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com bool operator== (const ListElement& other) { return fID == other.fID; } 18bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 194e23068b374023d43c4c725138d523721d975892bsalomon@google.com#if SK_ENABLE_INST_COUNT 20bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com // Make the instance count available publicly. 21bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com static int InstanceCount() { return GetInstanceCount(); } 22bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com#endif 23bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 24bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com int fID; 25bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 26bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.comprivate: 27bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SK_DECLARE_INST_COUNT_ROOT(ListElement); 28bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SK_DECLARE_INTERNAL_LLIST_INTERFACE(ListElement); 29bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com}; 30bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 31bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.comstatic void check_list(const SkTInternalLList<ListElement>& list, 32bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com skiatest::Reporter* reporter, 33bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com bool empty, 34bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com int numElements, 35bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com bool in0, bool in1, bool in2, bool in3, 36bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com ListElement elements[4]) { 37bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 38bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, empty == list.isEmpty()); 39515dcd36032997ce335daa0163c6d67e851bcad1commit-bot@chromium.org#ifdef SK_DEBUG 40dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com list.validate(); 41bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, numElements == list.countEntries()); 42bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, in0 == list.isInList(&elements[0])); 43bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, in1 == list.isInList(&elements[1])); 44bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, in2 == list.isInList(&elements[2])); 45bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, in3 == list.isInList(&elements[3])); 46bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com#endif 47bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com} 48bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 49bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.comstatic void TestTInternalLList(skiatest::Reporter* reporter) { 50bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkTInternalLList<ListElement> list; 51bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com ListElement elements[4] = { 52bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com ListElement(0), 53bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com ListElement(1), 54bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com ListElement(2), 55bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com ListElement(3), 56bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com }; 57bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 58bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com // list should be empty to start with 59bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com check_list(list, reporter, true, 0, false, false, false, false, elements); 60bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 61bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list.addToHead(&elements[0]); 62bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 63bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com check_list(list, reporter, false, 1, true, false, false, false, elements); 64bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 65bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list.addToHead(&elements[1]); 66bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list.addToHead(&elements[2]); 67bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list.addToHead(&elements[3]); 68bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 69bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com check_list(list, reporter, false, 4, true, true, true, true, elements); 70bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 71bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com // test out iterators 72bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com typedef SkTInternalLList<ListElement>::Iter Iter; 73bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Iter iter; 74bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 75bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com ListElement* cur = iter.init(list, Iter::kHead_IterStart); 7649f085dddff10473b6ebf832a974288300224e60bsalomon for (int i = 0; cur; ++i, cur = iter.next()) { 77bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, cur->fID == 3-i); 78bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 79bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 80bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com cur = iter.init(list, Iter::kTail_IterStart); 8149f085dddff10473b6ebf832a974288300224e60bsalomon for (int i = 0; cur; ++i, cur = iter.prev()) { 82bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, cur->fID == i); 83bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 84bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 85bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com // remove middle, frontmost then backmost 86bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list.remove(&elements[1]); 87bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list.remove(&elements[3]); 88bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list.remove(&elements[0]); 89bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 90bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com check_list(list, reporter, false, 1, false, false, true, false, elements); 91bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 92bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com // remove last element 93bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list.remove(&elements[2]); 94bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 95bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com // list should be empty again 96bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com check_list(list, reporter, true, 0, false, false, false, false, elements); 97dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 98dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com // test out methods that add to the middle of the list. 99dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com list.addAfter(&elements[1], NULL); 100dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com check_list(list, reporter, false, 1, false, true, false, false, elements); 101dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 102dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com list.remove(&elements[1]); 103dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 104dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com list.addBefore(&elements[1], NULL); 105dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com check_list(list, reporter, false, 1, false, true, false, false, elements); 106dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 107dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com list.addBefore(&elements[0], &elements[1]); 108dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com check_list(list, reporter, false, 2, true, true, false, false, elements); 109dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 110dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com list.addAfter(&elements[3], &elements[1]); 111dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com check_list(list, reporter, false, 3, true, true, false, true, elements); 112dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 113dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com list.addBefore(&elements[2], &elements[3]); 114dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com check_list(list, reporter, false, 4, true, true, true, true, elements); 115dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 116dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com cur = iter.init(list, Iter::kHead_IterStart); 11749f085dddff10473b6ebf832a974288300224e60bsalomon for (int i = 0; cur; ++i, cur = iter.next()) { 118dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com REPORTER_ASSERT(reporter, cur->fID == i); 119dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com } 120bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com} 121bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 122bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.comstatic void TestTLList(skiatest::Reporter* reporter) { 123bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com typedef SkTLList<ListElement> ElList; 124bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com typedef ElList::Iter Iter; 125e0e7cfe44bb9d66d76120a79e5275c294bacaa22commit-bot@chromium.org SkRandom random; 126bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 127bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com for (int i = 1; i <= 16; i *= 2) { 128bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 129bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com ElList list1(i); 130bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com ElList list2(i); 131bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Iter iter1; 132bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Iter iter2; 133bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Iter iter3; 134bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Iter iter4; 135bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 1364e23068b374023d43c4c725138d523721d975892bsalomon@google.com#if SK_ENABLE_INST_COUNT 137bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(0 == ListElement::InstanceCount()); 138bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com#endif 139bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 140bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, list1.isEmpty()); 141bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, NULL == iter1.init(list1, Iter::kHead_IterStart)); 142bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, NULL == iter1.init(list1, Iter::kTail_IterStart)); 143bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com // Try popping an empty list 144bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list1.popHead(); 145bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list1.popTail(); 146bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, list1.isEmpty()); 147bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, list1 == list2); 148bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 149bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com // Create two identical lists, one by appending to head and the other to the tail. 150bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list1.addToHead(ListElement(1)); 151bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list2.addToTail(ListElement(1)); 1524e23068b374023d43c4c725138d523721d975892bsalomon@google.com#if SK_ENABLE_INST_COUNT 153bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(2 == ListElement::InstanceCount()); 154bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com#endif 155bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com iter1.init(list1, Iter::kHead_IterStart); 156bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com iter2.init(list1, Iter::kTail_IterStart); 157bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, iter1.get()->fID == iter2.get()->fID); 158bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com iter3.init(list2, Iter::kHead_IterStart); 159bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com iter4.init(list2, Iter::kTail_IterStart); 160bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID); 161bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID); 162bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, list1 == list2); 163e659c2e820de0b8d12d81247ed4430022ded0a90skia.committer@gmail.com 164dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com list2.reset(); 165dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 166dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com // use both before/after in-place construction on an empty list 167dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com SkNEW_INSERT_IN_LLIST_BEFORE(&list2, list2.headIter(), ListElement, (1)); 168dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com REPORTER_ASSERT(reporter, list2 == list1); 169dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com list2.reset(); 170e659c2e820de0b8d12d81247ed4430022ded0a90skia.committer@gmail.com 171dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com SkNEW_INSERT_IN_LLIST_AFTER(&list2, list2.tailIter(), ListElement, (1)); 172dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com REPORTER_ASSERT(reporter, list2 == list1); 173dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 174bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com // add an element to the second list, check that iters are still valid 175ebce0301082cda9dc3e3298f6db91d46fe66298bbsalomon@google.com iter3.init(list2, Iter::kHead_IterStart); 176ebce0301082cda9dc3e3298f6db91d46fe66298bbsalomon@google.com iter4.init(list2, Iter::kTail_IterStart); 177bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list2.addToHead(ListElement(2)); 178ebce0301082cda9dc3e3298f6db91d46fe66298bbsalomon@google.com 1794e23068b374023d43c4c725138d523721d975892bsalomon@google.com#if SK_ENABLE_INST_COUNT 180bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(3 == ListElement::InstanceCount()); 181bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com#endif 182dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 183bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID); 184bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID); 185bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, 1 == Iter(list2, Iter::kTail_IterStart).get()->fID); 186bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, 2 == Iter(list2, Iter::kHead_IterStart).get()->fID); 187bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, list1 != list2); 188bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list1.addToHead(ListElement(2)); 189bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, list1 == list2); 1904e23068b374023d43c4c725138d523721d975892bsalomon@google.com#if SK_ENABLE_INST_COUNT 191bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(4 == ListElement::InstanceCount()); 192bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com#endif 193bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, !list1.isEmpty()); 194bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 195bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list1.reset(); 196bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list2.reset(); 1974e23068b374023d43c4c725138d523721d975892bsalomon@google.com#if SK_ENABLE_INST_COUNT 198bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(0 == ListElement::InstanceCount()); 199bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com#endif 200bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, list1.isEmpty() && list2.isEmpty()); 201bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 202dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com // randomly perform insertions and deletions on a list and perform tests 203bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com int count = 0; 204bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com for (int j = 0; j < 100; ++j) { 205bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com if (list1.isEmpty() || random.nextBiasedBool(3 * SK_Scalar1 / 4)) { 206dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com int id = j; 207dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com // Choose one of three ways to insert a new element: at the head, at the tail, 208dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com // before a random element, after a random element 209dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com int numValidMethods = 0 == count ? 2 : 4; 210dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com int insertionMethod = random.nextULessThan(numValidMethods); 211dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com switch (insertionMethod) { 212dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com case 0: 213dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com list1.addToHead(ListElement(id)); 214dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com break; 215dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com case 1: 216dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com list1.addToTail(ListElement(id)); 217dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com break; 218dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com case 2: // fallthru to share code that picks random element. 219dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com case 3: { 220dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com int n = random.nextULessThan(list1.count()); 221dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com Iter iter = list1.headIter(); 222dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com // remember the elements before/after the insertion point. 223dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com while (n--) { 224dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com iter.next(); 225dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com } 226dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com Iter prev(iter); 227dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com Iter next(iter); 228dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com next.next(); 229dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com prev.prev(); 230dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 23149f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(iter.get()); 232dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com // insert either before or after the iterator, then check that the 233dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com // surrounding sequence is correct. 234dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com if (2 == insertionMethod) { 235dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com SkNEW_INSERT_IN_LLIST_BEFORE(&list1, iter, ListElement, (id)); 236dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com Iter newItem(iter); 237dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com newItem.prev(); 238dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com REPORTER_ASSERT(reporter, newItem.get()->fID == id); 239dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 24049f085dddff10473b6ebf832a974288300224e60bsalomon if (next.get()) { 241dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com REPORTER_ASSERT(reporter, next.prev()->fID == iter.get()->fID); 242dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com } 24349f085dddff10473b6ebf832a974288300224e60bsalomon if (prev.get()) { 244dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com REPORTER_ASSERT(reporter, prev.next()->fID == id); 245dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com } 246dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com } else { 247dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com SkNEW_INSERT_IN_LLIST_AFTER(&list1, iter, ListElement, (id)); 248dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com Iter newItem(iter); 249dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com newItem.next(); 250dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com REPORTER_ASSERT(reporter, newItem.get()->fID == id); 251dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 25249f085dddff10473b6ebf832a974288300224e60bsalomon if (next.get()) { 253dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com REPORTER_ASSERT(reporter, next.prev()->fID == id); 254dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com } 25549f085dddff10473b6ebf832a974288300224e60bsalomon if (prev.get()) { 256dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com REPORTER_ASSERT(reporter, prev.next()->fID == iter.get()->fID); 257dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com } 258dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com } 259e659c2e820de0b8d12d81247ed4430022ded0a90skia.committer@gmail.com } 260bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 261bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com ++count; 262bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } else { 263bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com // walk to a random place either forward or backwards and remove. 264bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com int n = random.nextULessThan(list1.count()); 265bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Iter::IterStart start; 266bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com ListElement* (Iter::*incrFunc)(); 267e659c2e820de0b8d12d81247ed4430022ded0a90skia.committer@gmail.com 268bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com if (random.nextBool()) { 269bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com start = Iter::kHead_IterStart; 270bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com incrFunc = &Iter::next; 271bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } else { 272bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com start = Iter::kTail_IterStart; 273bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com incrFunc = &Iter::prev; 274bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 275bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 276bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com // find the element 277bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Iter iter(list1, start); 278bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com while (n--) { 27949f085dddff10473b6ebf832a974288300224e60bsalomon REPORTER_ASSERT(reporter, iter.get()); 280bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com (iter.*incrFunc)(); 281bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 28249f085dddff10473b6ebf832a974288300224e60bsalomon REPORTER_ASSERT(reporter, iter.get()); 283bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 284bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com // remember the prev and next elements from the element to be removed 285bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Iter prev = iter; 286bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Iter next = iter; 287bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com prev.prev(); 288bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com next.next(); 289bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list1.remove(iter.get()); 290bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 291bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com // make sure the remembered next/prev iters still work 292bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Iter pn = prev; pn.next(); 293bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Iter np = next; np.prev(); 294bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com // pn should match next unless the target node was the head, in which case prev 295bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com // walked off the list. 296bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, pn.get() == next.get() || NULL == prev.get()); 297bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com // Similarly, np should match prev unless next originally walked off the tail. 298bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, np.get() == prev.get() || NULL == next.get()); 299bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com --count; 300bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 301bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com REPORTER_ASSERT(reporter, count == list1.count()); 3024e23068b374023d43c4c725138d523721d975892bsalomon@google.com#if SK_ENABLE_INST_COUNT 303bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(count == ListElement::InstanceCount()); 304bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com#endif 305bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 306bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com list1.reset(); 3074e23068b374023d43c4c725138d523721d975892bsalomon@google.com#if SK_ENABLE_INST_COUNT 308bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(0 == ListElement::InstanceCount()); 309bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com#endif 310bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 311bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com} 312bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 313e4fafb146e85cdfcf9d5418597b6818aa0754adatfarina@chromium.orgDEF_TEST(LList, reporter) { 314bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com TestTInternalLList(reporter); 315bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com TestTLList(reporter); 316bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com} 317