1 // Licensed to the .NET Foundation under one or more agreements.
2 // The .NET Foundation licenses this file to you under the MIT license.
3 // See the LICENSE file in the project root for more information.
6 using Microsoft.Xunit.Performance;
8 using System.Runtime.CompilerServices;
11 [assembly: OptimizeForBenchmarks]
13 namespace Benchstone.BenchI
15 public static class TreeSort
19 public const int Iterations = 1;
21 public const int Iterations = 1200;
24 const int SortElements = 5000;
25 const int Modulus = 65536;
41 static int s_littlest;
44 static void InitRand() {
48 static int Rand(ref int seed) {
49 int multiplier = 25173;
50 int increment = 13849;
51 seed = (multiplier * seed + increment) % Modulus;
55 static void InitArray(int[] sortList) {
59 for (int i = 1; i <= SortElements; i++) {
60 sortList[i] = Rand(ref s_seed) - 1;
61 if (sortList[i] > s_biggest) {
62 s_biggest = sortList[i];
64 else if (sortList[i] < s_littlest) {
65 s_littlest = sortList[i];
70 static void Insert(int n, Node t) {
80 if (t.Right == null) {
81 t.Right = new Node(n);
89 static bool CheckTree(Node p) {
92 if (p.Left.Val <= p.Val) {
96 result &= CheckTree(p.Left);
100 if (p.Right != null) {
101 if (p.Right.Val >= p.Val) {
105 result &= CheckTree(p.Right);
112 static bool Trees(int[] sortList) {
114 Node tree = new Node(sortList[1]);
115 for (int i = 2; i <= SortElements; i++) {
116 Insert(sortList[i], tree);
118 bool result = CheckTree(tree);
122 [MethodImpl(MethodImplOptions.NoInlining)]
123 static bool Bench() {
124 int[] sortList = new int[SortElements + 1];
125 bool result = Trees(sortList);
130 public static void Test() {
131 foreach (var iteration in Benchmark.Iterations) {
132 using (iteration.StartMeasurement()) {
133 for (int i = 0; i < Iterations; i++) {
140 static bool TestBase() {
142 for (int i = 0; i < Iterations; i++) {
148 public static int Main() {
149 bool result = TestBase();
150 return (result ? 100 : -1);