1 /*
2 * Copyright (c) 2003, 2021, 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
24 package nsk.share.gc;
25
26 import nsk.share.test.ExecutionController;
27 import nsk.share.test.LocalRandom;
28
29 import java.io.PrintStream;
30
31 /**
32 * <tt>NonbranchyTree</tt> defines a tree structure. Each node of the tree
33 * always has one son. A node may have the second son with probability
34 * <tt>branchiness</tt>.
35 */
36 public class NonbranchyTree {
37
38 /** Minimal size of each node (in bytes) */
39 public final static int MIN_NODE_SIZE = 20;
40 private final Node root;
41 private final float branchiness;
42 private final ExecutionController controller;
43
44 /**
45 * Creates a new tree with number of nodes not more than
46 * <tt>numberOfNodes</tt>. The implementation uses recursion to build the
47 * tree, so if <tt>StackOverflowError</tt> or <tt>OutOfMemoryError</tt> is
48 * thrown, the recursion is stopped and the method finishes building of the
49 * tree. Each node consists of <tt>byte[]</tt> of length <tt>size</tt>.
50 *
51 * @param numberOfNodes maximum number of nodes for the tree.
52 * @param branchiness probability for each node to have the second son.
53 * @param size number of bytes to store in a node.
54 *
55 * @throws <i>IllegalArgumentException</i> if <tt>numberOfNodes</tt> is
56 * less than 1; or <tt>branchiness</tt> is greater than 1, or less
57 * or equal than 0; or <tt>size</tt> is less than 1.
58 *
59 */
60 public NonbranchyTree(int numberOfNodes, float branchiness, int size) {
61 this(numberOfNodes, branchiness, size, null);
62 }
63
64 public NonbranchyTree(int numberOfNodes, float branchiness, int size, ExecutionController controller) {
65 if (numberOfNodes < 1) {
66 throw new IllegalArgumentException("Illegal number of nodes: "
67 + numberOfNodes + ", must be at least 1.");
68 }
69 if ((branchiness >= 1) || (branchiness <= 0)) {
70 throw new IllegalArgumentException("Illegal value of branchiness: "
71 + branchiness + ", must be greater than 0 and less than 1.");
72 }
73 if (size < 1) {
74 throw new IllegalArgumentException("Illegal size of nodes: "
75 + size + ", must be at least 1.");
76 }
77 // ensure that LocalRandom is loaded and has enough memory
78 LocalRandom.nextBoolean();
79 this.branchiness = branchiness;
80 this.controller = controller;
81 this.root = createTree(numberOfNodes, size);
82 }
83
84 // Create a new tree with specified number of nodes and size of each node
85 private Node createTree(int numberOfNodes, int size) {
86 // Make sure we respect the controller and stop test after
87 // given time.
88 if (controller != null && !controller.continueExecution()) {
89 return null;
90 }
91
92 Node node = new Node(size);
93 try {
94 if (numberOfNodes == 0) {
95 // No more nodes need to be built
96 return null;
97 } else if (numberOfNodes == 1) {
98 return node;
99 } else if (numberOfNodes == 2) {
100 node.left = createTree(1, size);
101 return node;
102 } else {
103 // Create a few nodes
104 if (makeRightNode()) {
105 // The node will have two sons
106 int leftNodes = 1 + LocalRandom.nextInt(numberOfNodes - 2);
107 int rightNodes = numberOfNodes - 1 - leftNodes;
108
109 node.left = createTree(leftNodes, size);
110 node.right = createTree(rightNodes, size);
111 } else {
112 // The node will have just one son
113 Node leftTree = createTree(numberOfNodes - 1, size);
114 node.left = leftTree;
115 }
116 return node;
117 } // if
118 } catch(StackOverflowError e) {
119 // No more memory for such long tree
120 return node;
121 } catch(OutOfMemoryError e) {
122 // No more memory for such long tree
123 return node;
124 } // try
125 } // createTree()
126
127 // Define the "branchiness" of the tree
128 private boolean makeRightNode() {
129 return (LocalRandom.nextFloat() < branchiness);
130 }
131
132 /**
133 * Bends the tree. A son of a leaf of the tree is set to the root node.
134 *
135 */
136 public void bend() {
137 bend(root);
138 }
139
140 // Bend the tree: make a reference from a leat of the tree to the specified
141 // node
142 private void bend(Node markedNode) {
143 Node node = root;
144
145 while ( (node.left != null) || (node.right != null) )
146 node = node.left;
147 node.right = markedNode;
148 }
149
150 /**
151 * Prints the whole tree from the root to the defined PrintStream.
152 *
153 * @param out PrintStream to print the tree in
154 *
155 */
156 public void print(PrintStream out) {
157 print(out, root);
158 }
159
160 // Print the sub-tree from the specified node and down
161 private void print(PrintStream out, Node node) {
162 node.print(out);
163 if (node.left != null)
164 print(out, node.left);
165 if (node.right != null)
166 print(out, node.right);
167 }
168 }
169
170 // The class defines a node of a tree
171 class Node {
172 Node left;
173 Node right;
174 byte[] core;
175
176 Node(int size) {
177 left = null;
178 right = null;
179 core = new byte[size];
180
181 // Initizlize the core array
182 for (int i = 0; i < size; i++)
183 core[i] = (byte) i;
184 }
185
186 // Print the node info
187 void print(PrintStream out) {
188 out.println("node = " + this + " (" + left + ", " + right + ")");
189 }
190 }