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     // NOLINTNEXTLINE(bugprone-use-after-move)
    124     check_list(listB, reporter, true, 0, false, false, false, false, elements);
    125 
    126     listB.addToTail(&elements[0]);
    127     listA.concat(std::move(listB));
    128     check_list(listA, reporter, false, 1, true, false, false, false, elements);
    129     // NOLINTNEXTLINE(bugprone-use-after-move)
    130     check_list(listB, reporter, true, 0, false, false, false, false, elements);
    131 
    132     listB.addToTail(&elements[1]);
    133     listA.concat(std::move(listB));
    134     check_list(listA, reporter, false, 2, true, true, false, false, elements);
    135     // NOLINTNEXTLINE(bugprone-use-after-move)
    136     check_list(listB, reporter, true, 0, false, false, false, false, elements);
    137 
    138     listA.concat(std::move(listB));
    139     check_list(listA, reporter, false, 2, true, true, false, false, elements);
    140     // NOLINTNEXTLINE(bugprone-use-after-move)
    141     check_list(listB, reporter, true, 0, false, false, false, false, elements);
    142 
    143     listB.addToTail(&elements[2]);
    144     listB.addToTail(&elements[3]);
    145     listA.concat(std::move(listB));
    146     check_list(listA, reporter, false, 4, true, true, true, true, elements);
    147     // NOLINTNEXTLINE(bugprone-use-after-move)
    148     check_list(listB, reporter, true, 0, false, false, false, false, elements);
    149 
    150     cur = iter.init(listA, Iter::kHead_IterStart);
    151     for (int i = 0; cur; ++i, cur = iter.next()) {
    152         REPORTER_ASSERT(reporter, cur->fID == i);
    153     }
    154 }
    155 
    156 template <unsigned int N> static void test_tllist(skiatest::Reporter* reporter) {
    157     typedef SkTLList<ListElement, N> ElList;
    158     typedef typename ElList::Iter Iter;
    159     SkRandom random;
    160 
    161     ElList list1;
    162     ElList list2;
    163     Iter iter1;
    164     Iter iter2;
    165     Iter iter3;
    166     Iter iter4;
    167 
    168     REPORTER_ASSERT(reporter, list1.isEmpty());
    169     REPORTER_ASSERT(reporter, nullptr == iter1.init(list1, Iter::kHead_IterStart));
    170     REPORTER_ASSERT(reporter, nullptr == iter1.init(list1, Iter::kTail_IterStart));
    171     // Try popping an empty list
    172     list1.popHead();
    173     list1.popTail();
    174     REPORTER_ASSERT(reporter, list1.isEmpty());
    175     REPORTER_ASSERT(reporter, list1 == list2);
    176 
    177     // Create two identical lists, one by appending to head and the other to the tail.
    178     list1.addToHead(ListElement(1));
    179     list2.addToTail(ListElement(1));
    180     iter1.init(list1, Iter::kHead_IterStart);
    181     iter2.init(list1, Iter::kTail_IterStart);
    182     REPORTER_ASSERT(reporter, iter1.get()->fID == iter2.get()->fID);
    183     iter3.init(list2, Iter::kHead_IterStart);
    184     iter4.init(list2, Iter::kTail_IterStart);
    185     REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID);
    186     REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID);
    187     REPORTER_ASSERT(reporter, list1 == list2);
    188 
    189     list2.reset();
    190 
    191     // use both before/after in-place construction on an empty list
    192     list2.addBefore(list2.headIter(), 1);
    193     REPORTER_ASSERT(reporter, list2 == list1);
    194     list2.reset();
    195 
    196     list2.addAfter(list2.tailIter(), 1);
    197     REPORTER_ASSERT(reporter, list2 == list1);
    198 
    199     // add an element to the second list, check that iters are still valid
    200     iter3.init(list2, Iter::kHead_IterStart);
    201     iter4.init(list2, Iter::kTail_IterStart);
    202     list2.addToHead(ListElement(2));
    203 
    204     REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID);
    205     REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID);
    206     REPORTER_ASSERT(reporter, 1 == Iter(list2, Iter::kTail_IterStart).get()->fID);
    207     REPORTER_ASSERT(reporter, 2 == Iter(list2, Iter::kHead_IterStart).get()->fID);
    208     REPORTER_ASSERT(reporter, list1 != list2);
    209     list1.addToHead(ListElement(2));
    210     REPORTER_ASSERT(reporter, list1 == list2);
    211     REPORTER_ASSERT(reporter, !list1.isEmpty());
    212 
    213     list1.reset();
    214     list2.reset();
    215     REPORTER_ASSERT(reporter, list1.isEmpty() && list2.isEmpty());
    216 
    217     // randomly perform insertions and deletions on a list and perform tests
    218     int count = 0;
    219     for (int j = 0; j < 100; ++j) {
    220         if (list1.isEmpty() || random.nextBiasedBool(3  * SK_Scalar1 / 4)) {
    221             int id = j;
    222             // Choose one of three ways to insert a new element: at the head, at the tail,
    223             // before a random element, after a random element
    224             int numValidMethods = 0 == count ? 2 : 4;
    225             int insertionMethod = random.nextULessThan(numValidMethods);
    226             switch (insertionMethod) {
    227                 case 0:
    228                     list1.addToHead(ListElement(id));
    229                     break;
    230                 case 1:
    231                     list1.addToTail(ListElement(id));
    232                     break;
    233                 case 2: // fallthru to share code that picks random element.
    234                 case 3: {
    235                     int n = random.nextULessThan(list1.count());
    236                     Iter iter = list1.headIter();
    237                     // remember the elements before/after the insertion point.
    238                     while (n--) {
    239                         iter.next();
    240                     }
    241                     Iter prev(iter);
    242                     Iter next(iter);
    243                     next.next();
    244                     prev.prev();
    245 
    246                     SkASSERT(iter.get());
    247                     // insert either before or after the iterator, then check that the
    248                     // surrounding sequence is correct.
    249                     if (2 == insertionMethod) {
    250                         list1.addBefore(iter, id);
    251                         Iter newItem(iter);
    252                         newItem.prev();
    253                         REPORTER_ASSERT(reporter, newItem.get()->fID == id);
    254 
    255                         if (next.get()) {
    256                             REPORTER_ASSERT(reporter, next.prev()->fID == iter.get()->fID);
    257                         }
    258                         if (prev.get()) {
    259                             REPORTER_ASSERT(reporter, prev.next()->fID == id);
    260                         }
    261                     } else {
    262                         list1.addAfter(iter, id);
    263                         Iter newItem(iter);
    264                         newItem.next();
    265                         REPORTER_ASSERT(reporter, newItem.get()->fID == id);
    266 
    267                         if (next.get()) {
    268                             REPORTER_ASSERT(reporter, next.prev()->fID == id);
    269                         }
    270                         if (prev.get()) {
    271                             REPORTER_ASSERT(reporter, prev.next()->fID == iter.get()->fID);
    272                         }
    273                     }
    274                 }
    275             }
    276             ++count;
    277         } else {
    278             // walk to a random place either forward or backwards and remove.
    279             int n = random.nextULessThan(list1.count());
    280             typename Iter::IterStart start;
    281             ListElement* (Iter::*incrFunc)();
    282 
    283             if (random.nextBool()) {
    284                 start = Iter::kHead_IterStart;
    285                 incrFunc = &Iter::next;
    286             } else {
    287                 start = Iter::kTail_IterStart;
    288                 incrFunc = &Iter::prev;
    289             }
    290 
    291             // find the element
    292             Iter iter(list1, start);
    293             while (n--) {
    294                 REPORTER_ASSERT(reporter, iter.get());
    295                 (iter.*incrFunc)();
    296             }
    297             REPORTER_ASSERT(reporter, iter.get());
    298 
    299             // remember the prev and next elements from the element to be removed
    300             Iter prev = iter;
    301             Iter next = iter;
    302             prev.prev();
    303             next.next();
    304             list1.remove(iter.get());
    305 
    306             // make sure the remembered next/prev iters still work
    307             Iter pn = prev; pn.next();
    308             Iter np = next; np.prev();
    309             // pn should match next unless the target node was the head, in which case prev
    310             // walked off the list.
    311             REPORTER_ASSERT(reporter, pn.get() == next.get() || nullptr == prev.get());
    312             // Similarly, np should match prev unless next originally walked off the tail.
    313             REPORTER_ASSERT(reporter, np.get() == prev.get() || nullptr == next.get());
    314             --count;
    315         }
    316         REPORTER_ASSERT(reporter, count == list1.count());
    317     }
    318 }
    319 
    320 DEF_TEST(LList, reporter) {
    321     test_tinternallist(reporter);
    322     test_tllist<1>(reporter);
    323     test_tllist<3>(reporter);
    324     test_tllist<8>(reporter);
    325     test_tllist<10>(reporter);
    326     test_tllist<16>(reporter);
    327 }
    328