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 "Benchmark.h"
9 #include "SkRandom.h"
10 #include "SkString.h"
11 #include "SkTTopoSort.h"
12 
13 #include "sk_tool_utils.h"
14 
15 class TopoSortBench : public Benchmark {
16 public:
17     TopoSortBench() { }
18 
19     ~TopoSortBench() override {
20         sk_tool_utils::TopoTestNode::DeallocNodes(&fGraph);
21     }
22 
23     bool isSuitableFor(Backend backend) override {
24         return kNonRendering_Backend == backend;
25     }
26 
27 protected:
28     const char* onGetName() override {
29         return "sort_topo_rand";
30     }
31 
32     // Delayed initialization only done if onDraw will be called.
33     void onDelayedSetup() override {
34         sk_tool_utils::TopoTestNode::AllocNodes(&fGraph, kNumElements);
35 
36         for (int i = kNumElements-1; i > 0; --i) {
37             int numEdges = fRand.nextU() % (kMaxEdges+1);
38 
39             for (int j = 0; j < numEdges; ++j) {
40                 int dep = fRand.nextU() % i;
41 
42                 fGraph[i]->dependsOn(fGraph[dep]);
43             }
44         }
45     }
46 
47     void onDraw(int loops, SkCanvas*) override {
48         for (int i = 0; i < loops; ++i) {
49             for (int j = 0; j < fGraph.count(); ++j) {
50                 fGraph[j]->reset();
51             }
52 
53             sk_tool_utils::TopoTestNode::Shuffle(&fGraph, &fRand);
54 
55             SkDEBUGCODE(bool actualResult =) SkTTopoSort<sk_tool_utils::TopoTestNode>(&fGraph);
56             SkASSERT(actualResult);
57 
58 #ifdef SK_DEBUG
59             for (int j = 0; j < fGraph.count(); ++j) {
60                 SkASSERT(fGraph[j]->check());
61             }
62 #endif
63         }
64     }
65 
66 private:
67     static const int kNumElements = 1000;
68     static const int kMaxEdges = 5;
69 
70     SkTDArray<sk_tool_utils::TopoTestNode*> fGraph;
71     SkRandom fRand;
72 
73     typedef Benchmark INHERITED;
74 };
75 
76 ///////////////////////////////////////////////////////////////////////////////
77 
78 DEF_BENCH( return new TopoSortBench(); )
79