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
15class TopoSortBench : public Benchmark {
16public:
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
27protected:
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
66private:
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
78DEF_BENCH( return new TopoSortBench(); )
79
80