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