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)(SkTArray<sk_sp<sk_tool_utils::TopoTestNode>>* graph);
15
16 /* Simple diamond
17 * 3
18 * / \
19 * 1 2
20 * \ /
21 * 0
22 */
create_graph0(SkTArray<sk_sp<sk_tool_utils::TopoTestNode>> * graph)23 static void create_graph0(SkTArray<sk_sp<sk_tool_utils::TopoTestNode>>* graph) {
24 sk_tool_utils::TopoTestNode::AllocNodes(graph, 4);
25
26 (*graph)[0]->dependsOn((*graph)[1].get());
27 (*graph)[0]->dependsOn((*graph)[2].get());
28 (*graph)[1]->dependsOn((*graph)[3].get());
29 (*graph)[2]->dependsOn((*graph)[3].get());
30 }
31
32 /* Simple chain
33 * 3
34 * |
35 * 2
36 * |
37 * 1
38 * |
39 * 0
40 */
create_graph1(SkTArray<sk_sp<sk_tool_utils::TopoTestNode>> * graph)41 static void create_graph1(SkTArray<sk_sp<sk_tool_utils::TopoTestNode>>* graph) {
42 sk_tool_utils::TopoTestNode::AllocNodes(graph, 4);
43
44 (*graph)[0]->dependsOn((*graph)[1].get());
45 (*graph)[1]->dependsOn((*graph)[2].get());
46 (*graph)[2]->dependsOn((*graph)[3].get());
47 }
48
49 /* Loop
50 * 2
51 * / \
52 * 0 --- 1
53 */
create_graph2(SkTArray<sk_sp<sk_tool_utils::TopoTestNode>> * graph)54 static void create_graph2(SkTArray<sk_sp<sk_tool_utils::TopoTestNode>>* graph) {
55 sk_tool_utils::TopoTestNode::AllocNodes(graph, 3);
56
57 (*graph)[0]->dependsOn((*graph)[1].get());
58 (*graph)[1]->dependsOn((*graph)[2].get());
59 (*graph)[2]->dependsOn((*graph)[0].get());
60 }
61
62 /* Double diamond
63 * 6
64 * / \
65 * 4 5
66 * \ /
67 * 3
68 * / \
69 * 1 2
70 * \ /
71 * 0
72 */
create_graph3(SkTArray<sk_sp<sk_tool_utils::TopoTestNode>> * graph)73 static void create_graph3(SkTArray<sk_sp<sk_tool_utils::TopoTestNode>>* graph) {
74 sk_tool_utils::TopoTestNode::AllocNodes(graph, 7);
75
76 (*graph)[0]->dependsOn((*graph)[1].get());
77 (*graph)[0]->dependsOn((*graph)[2].get());
78 (*graph)[1]->dependsOn((*graph)[3].get());
79 (*graph)[2]->dependsOn((*graph)[3].get());
80
81 (*graph)[3]->dependsOn((*graph)[4].get());
82 (*graph)[3]->dependsOn((*graph)[5].get());
83 (*graph)[4]->dependsOn((*graph)[6].get());
84 (*graph)[5]->dependsOn((*graph)[6].get());
85 }
86
87 /* Two independent diamonds
88 * 3 7
89 * / \ / \
90 * 1 2 5 6
91 * \ / \ /
92 * 0 4
93 */
create_graph4(SkTArray<sk_sp<sk_tool_utils::TopoTestNode>> * graph)94 static void create_graph4(SkTArray<sk_sp<sk_tool_utils::TopoTestNode>>* graph) {
95 sk_tool_utils::TopoTestNode::AllocNodes(graph, 8);
96
97 (*graph)[0]->dependsOn((*graph)[1].get());
98 (*graph)[0]->dependsOn((*graph)[2].get());
99 (*graph)[1]->dependsOn((*graph)[3].get());
100 (*graph)[2]->dependsOn((*graph)[3].get());
101
102 (*graph)[4]->dependsOn((*graph)[5].get());
103 (*graph)[4]->dependsOn((*graph)[6].get());
104 (*graph)[5]->dependsOn((*graph)[7].get());
105 (*graph)[6]->dependsOn((*graph)[7].get());
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 SkTArray<sk_sp<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 }
140 }
141