TopoSortTest.cpp 3.6 KB

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