• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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  */
create_graph0(SkTDArray<sk_tool_utils::TopoTestNode * > * graph)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  */
create_graph1(SkTDArray<sk_tool_utils::TopoTestNode * > * graph)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  */
create_graph2(SkTDArray<sk_tool_utils::TopoTestNode * > * graph)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  */
create_graph3(SkTDArray<sk_tool_utils::TopoTestNode * > * graph)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  */
create_graph4(SkTDArray<sk_tool_utils::TopoTestNode * > * graph)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 
DEF_TEST(TopoSort,reporter)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