Add SkTTopoSort

Add SkTTopoSort

BUG=skia:4094
Committed: https://skia.googlesource.com/skia/+/423f6461e98ba28730d05e5894804a4970a09bde

[robertphillips, 2015-10-17 21:08:19]

robertphillips@google.com changed reviewers:
+ bsalomon@google.com

[bsalomon, 2015-10-19 14:19:14]

Seems like a nice design. Some Qs inline.

https://codereview.chromium.org/1414503003/diff/20001/src/core/SkTTopoSort.h
File src/core/SkTTopoSort.h (right):

https://codereview.chromium.org/1414503003/diff/20001/src/core/SkTTopoSort.h#...
src/core/SkTTopoSort.h:64: template <typename T, typename Traits = T>
Maybe comment about what signatures are required on Traits?

https://codereview.chromium.org/1414503003/diff/20001/src/core/SkTTopoSort.h#...
src/core/SkTTopoSort.h:65: bool SkTTopoSort(SkTDArray<T*>* graph) {
Wondering in consideration of GrDT graph if the graph should allow disjoint sets
and take a seed node (i.e. the GrDT we actually want to flush).

https://codereview.chromium.org/1414503003/diff/20001/tests/TopoSortTest.cpp
File tests/TopoSortTest.cpp (right):

https://codereview.chromium.org/1414503003/diff/20001/tests/TopoSortTest.cpp#...
tests/TopoSortTest.cpp:13: // Shared with TopoSortBench.cpp
Is there any place we could stick the test node class that'd be accessible to
both?

[robertphillips, 2015-10-19 16:21:07]

https://codereview.chromium.org/1414503003/diff/20001/src/core/SkTTopoSort.h
File src/core/SkTTopoSort.h (right):

https://codereview.chromium.org/1414503003/diff/20001/src/core/SkTTopoSort.h#...
src/core/SkTTopoSort.h:64: template <typename T, typename Traits = T>
On 2015/10/19 14:19:13, bsalomon wrote:
> Maybe comment about what signatures are required on Traits?

Done.

https://codereview.chromium.org/1414503003/diff/20001/src/core/SkTTopoSort.h#...
src/core/SkTTopoSort.h:65: bool SkTTopoSort(SkTDArray<T*>* graph) {
On 2015/10/19 14:19:13, bsalomon wrote:
> Wondering in consideration of GrDT graph if the graph should allow disjoint
sets
> and take a seed node (i.e. the GrDT we actually want to flush).

Interesting. I think we could just call SkTTopoSort_Visit but a wrapper would
probably be more comprehensible. I've added a TODO.

https://codereview.chromium.org/1414503003/diff/20001/tests/TopoSortTest.cpp
File tests/TopoSortTest.cpp (right):

https://codereview.chromium.org/1414503003/diff/20001/tests/TopoSortTest.cpp#...
tests/TopoSortTest.cpp:13: // Shared with TopoSortBench.cpp
On 2015/10/19 14:19:13, bsalomon wrote:
> Is there any place we could stick the test node class that'd be accessible to
> both?

Done - although we might want to create a top-level utils directory sometime for
code shared between bench, gm & tests.

[mtklein, 2015-10-19 16:40:05]

> Done - although we might want to create a top-level utils directory sometime
for
> code shared between bench, gm & tests.

tools/ ?

[bsalomon, 2015-10-19 18:27:18]

lgtm

[robertphillips, 2015-10-19 18:28:51]

The CQ bit was checked by robertphillips@google.com to run a CQ dry run

[commit-bot: I haz the power, 2015-10-19 18:28:57]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1414503003/80001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1414503003/80001

[commit-bot: I haz the power, 2015-10-19 18:29:58]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-10-19 18:29:59]

Dry run: Try jobs failed on following builders:
  Build-Ubuntu-GCC-Arm64-Debug-Android-Trybot on client.skia.compile
(JOB_FAILED,
http://build.chromium.org/p/client.skia.compile/builders/Build-Ubuntu-GCC-Arm...)
  Build-Ubuntu-GCC-Mips-Debug-Android-Trybot on client.skia.compile (JOB_FAILED,
http://build.chromium.org/p/client.skia.compile/builders/Build-Ubuntu-GCC-Mip...)

[robertphillips, 2015-10-19 18:45:13]

The CQ bit was checked by robertphillips@google.com to run a CQ dry run

[commit-bot: I haz the power, 2015-10-19 18:45:16]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1414503003/100001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1414503003/100001

[commit-bot: I haz the power, 2015-10-19 18:54:55]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-10-19 18:54:55]

Dry run: This issue passed the CQ dry run.

[robertphillips, 2015-10-19 19:15:10]

The CQ bit was checked by robertphillips@google.com

[robertphillips, 2015-10-19 19:15:10]

The patchset sent to the CQ was uploaded after l-g-t-m from bsalomon@google.com
Link to the patchset: https://codereview.chromium.org/1414503003/#ps100001
(title: "Fixed comment format")

[commit-bot: I haz the power, 2015-10-19 19:15:20]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1414503003/100001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1414503003/100001

[commit-bot: I haz the power, 2015-10-19 19:15:58]

Committed patchset #6 (id:100001) as
https://skia.googlesource.com/skia/+/423f6461e98ba28730d05e5894804a4970a09bde