Home | History | Annotate | Download | only in tests 
      1 /*
      2  * Copyright 2015 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 "SkTTopoSort.h"
     10 #include "Test.h"
     11 
     12 #include "sk_tool_utils.h"
     13 
     14 typedef void (*CreateGraphPF)(SkTDArray<sk_tool_utils::TopoTestNode*>* graph);
     15 
     16 /* Simple diamond
     17  *       3
     18  *     /   \
     19  *    1     2
     20  *     \   /
     21  *       0
     22  */
     23 static void create_graph0(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
     24     sk_tool_utils::TopoTestNode::AllocNodes(graph, 4);
     25 
     26     (*graph)[0]->dependsOn((*graph)[1]);
     27     (*graph)[0]->dependsOn((*graph)[2]);
     28     (*graph)[1]->dependsOn((*graph)[3]);
     29     (*graph)[2]->dependsOn((*graph)[3]);
     30 }
     31 
     32 /* Simple chain
     33  *     3
     34  *     |
     35  *     2
     36  *     |
     37  *     1
     38  *     |
     39  *     0
     40  */
     41 static void create_graph1(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
     42     sk_tool_utils::TopoTestNode::AllocNodes(graph, 4);
     43 
     44     (*graph)[0]->dependsOn((*graph)[1]);
     45     (*graph)[1]->dependsOn((*graph)[2]);
     46     (*graph)[2]->dependsOn((*graph)[3]);
     47 }
     48 
     49 /* Loop
     50  *       2
     51  *     /   \
     52  *    0 --- 1
     53  */
     54 static void create_graph2(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
     55     sk_tool_utils::TopoTestNode::AllocNodes(graph, 3);
     56 
     57     (*graph)[0]->dependsOn((*graph)[1]);
     58     (*graph)[1]->dependsOn((*graph)[2]);
     59     (*graph)[2]->dependsOn((*graph)[0]);
     60 }
     61 
     62 /* Double diamond
     63  *       6
     64  *     /   \
     65  *    4     5
     66  *     \   /
     67  *       3
     68  *     /   \
     69  *    1     2
     70  *     \   /
     71  *       0
     72  */
     73 static void create_graph3(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
     74     sk_tool_utils::TopoTestNode::AllocNodes(graph, 7);
     75 
     76     (*graph)[0]->dependsOn((*graph)[1]);
     77     (*graph)[0]->dependsOn((*graph)[2]);
     78     (*graph)[1]->dependsOn((*graph)[3]);
     79     (*graph)[2]->dependsOn((*graph)[3]);
     80 
     81     (*graph)[3]->dependsOn((*graph)[4]);
     82     (*graph)[3]->dependsOn((*graph)[5]);
     83     (*graph)[4]->dependsOn((*graph)[6]);
     84     (*graph)[5]->dependsOn((*graph)[6]);
     85 }
     86 
     87 /* Two independent diamonds
     88  *       3           7
     89  *     /   \       /   \
     90  *    1     2     5     6
     91  *     \   /       \   /
     92  *       0           4
     93  */
     94 static void create_graph4(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
     95     sk_tool_utils::TopoTestNode::AllocNodes(graph, 8);
     96 
     97     (*graph)[0]->dependsOn((*graph)[1]);
     98     (*graph)[0]->dependsOn((*graph)[2]);
     99     (*graph)[1]->dependsOn((*graph)[3]);
    100     (*graph)[2]->dependsOn((*graph)[3]);
    101 
    102     (*graph)[4]->dependsOn((*graph)[5]);
    103     (*graph)[4]->dependsOn((*graph)[6]);
    104     (*graph)[5]->dependsOn((*graph)[7]);
    105     (*graph)[6]->dependsOn((*graph)[7]);
    106 }
    107 
    108 DEF_TEST(TopoSort, reporter) {
    109     SkRandom rand;
    110 
    111     struct {
    112         CreateGraphPF fCreate;
    113         bool          fExpectedResult;
    114     } tests[] = {
    115         { create_graph0, true  },
    116         { create_graph1, true  },
    117         { create_graph2, false },
    118         { create_graph3, true  },
    119         { create_graph4, true  },
    120     };
    121 
    122     for (size_t i = 0; i < SK_ARRAY_COUNT(tests); ++i) {
    123         SkTDArray<sk_tool_utils::TopoTestNode*> graph;
    124 
    125         (tests[i].fCreate)(&graph);
    126 
    127         sk_tool_utils::TopoTestNode::Shuffle(&graph, &rand);
    128 
    129         bool actualResult = SkTTopoSort<sk_tool_utils::TopoTestNode>(&graph);
    130         REPORTER_ASSERT(reporter, actualResult == tests[i].fExpectedResult);
    131 
    132         if (tests[i].fExpectedResult) {
    133             for (int j = 0; j < graph.count(); ++j) {
    134                 REPORTER_ASSERT(reporter, graph[j]->check());
    135             }
    136         }
    137 
    138         //SkDEBUGCODE(print(graph);)
    139         sk_tool_utils::TopoTestNode::DeallocNodes(&graph);
    140     }
    141 }
    142