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