1 /*
2 * Copyright (c) 2008, 2018, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package jit.graph;
24
25 import java.util.*;
26 import java.lang.reflect.*;
27 import nsk.share.TestFailure;
28
29 public class test6
30 {
31 private static final int[] MethodID = {Globals.MethodID_Array[11]};
32
33 private static Random localNumGen = new Random(Globals.RANDOM_SEED);
34 private static final int maxEntries = 25;
35
36 //flattens the binary tree into an array
37 private void getSortedArray(Node root, int [] dataArray, int[] index)
38 {
39 if ((root != null) && (root!=RBTree.treeNull))
40 {
41 getSortedArray(root.getNode(Node.Left_son), dataArray, index);
42 dataArray[index[0]++] = root.getKey();
43 getSortedArray(root.getNode(Node.Right_son), dataArray, index);
44 }
45 }
46
47 public synchronized void rbTest(Vector summation, Vector ID, Long functionDepth, Integer staticFunctionDepth)
48 throws InvocationTargetException
49 {
50 Globals.appendSumToSumationVector(MethodID[0], summation);
51
52 if (CGT.shouldFinish())
53 return;
54
55 if (Globals.VERBOSE)
56 System.out.println("test6.rbTest");
57
58 if ((functionDepth.longValue() <= 0) && (staticFunctionDepth.intValue() <= 0))
59 {
60 return;
61 }
62 MethodData methodCallStr;
63 Long numFcalls;
64 Integer staticFcalls;
65
66 if (staticFunctionDepth.intValue() > 0)
67 {
68 numFcalls = functionDepth;
69 staticFcalls = new Integer(staticFunctionDepth.intValue()-1);
70 methodCallStr = Globals.returnNextStaticMethod(MethodID[0]);
71 }
72 else
73 {
74 numFcalls = new Long(functionDepth.longValue() -1);
75 staticFcalls = staticFunctionDepth;
76 methodCallStr = Globals.nextRandomMethod();
77 }
78
79 RBTree myTree = new RBTree();
80 int numElements = 1 + localNumGen.nextInt(maxEntries);
81 int dataArray[] = new int[numElements];
82 boolean insertArray[] = new boolean[numElements];
83
84 Vector temp = new Vector(numElements);
85 for(int i=0; i<numElements; i++)
86 { //code guarantees no duplicates
87 int nextKey = localNumGen.nextInt(16385);
88 while (temp.indexOf(new Integer(nextKey)) != -1)
89 nextKey = localNumGen.nextInt(16385);
90
91 temp.addElement(new Integer(nextKey));
92 dataArray[i] = nextKey;
93
94 insertArray[i] = false;
95 }
96 temp = null;
97
98 int numLoops = 10 + localNumGen.nextInt(1024);
99 for (int i=0; i<numLoops; i++)
100 {
101 int nextIndex = localNumGen.nextInt(numElements);
102 if (!insertArray[nextIndex])
103 {
104 myTree.RBInsert(dataArray[nextIndex]);
105 insertArray[nextIndex] = true;
106 }
107 else
108 {
109 myTree.RBDelete(dataArray[nextIndex]);
110 insertArray[nextIndex] = false;
111 }
112 }
113
114 int numValid = 0;
115 for (int i = 0; i<numElements; i++)
116 {
117 Node searchNode = myTree.Search(dataArray[i]);
118 if (insertArray[i] && (searchNode == RBTree.treeNull))
119 {
120 System.out.println("Valid Node Not Found in Binary Tree");
121 System.out.println("Node " + dataArray[i]);
122 System.exit(1);
123 }
124 else if ((!insertArray[i]) && (searchNode != RBTree.treeNull))
125 {
126 System.out.println("Deleted Node Found in Binary Tree");
127 System.out.println("Node " + dataArray[i]);
128 System.exit(1);
129 }
130 else if (insertArray[i])
131 numValid++;
132 insertArray[i] = true; //so that verification is only done once
133 }
134
135 int [] sortedArray = new int[numValid];
136 getSortedArray(myTree.getRoot(), sortedArray, new int [] {0});
137
138 for (int i=1; i<numValid; i++)
139 if (sortedArray[i] <= sortedArray[i-1])
140 {
141 String outStr = new String("Actual ");
142 for (int j=0; j<sortedArray.length; j++)
143 outStr += sortedArray[j] +", ";
144 System.out.println("Binary Tree Property Not Held");
145 System.out.println("Root " + myTree.getRoot().getKey());
146 System.out.println(outStr);
147 System.exit(1);
148 }
149
150 //Should make more memory available for future instances
151 myTree = null;
152 sortedArray = null;
153 dataArray = null;
154 insertArray = null;
155 // System.gc();
156
157 Globals.addFunctionIDToVector(methodCallStr.id, ID);
158 Globals.callMethod(methodCallStr,summation, ID, numFcalls, staticFcalls);
159
160
161 }
162 }