--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/test/hotspot/jtreg/vmTestbase/nsk/share/gc/tree/TreeNode.java Mon Apr 30 18:10:24 2018 -0700
@@ -0,0 +1,210 @@
+/*
+ * Copyright (c) 2007, 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package nsk.share.gc.tree;
+
+import nsk.share.gc.Memory;
+import nsk.share.gc.gp.GarbageProducer;
+
+/**
+ * A node of binary tree.
+ *
+ * A height of subtree defined by this node is kept in the node.
+ * Additionaly, a byte array is used to control how much memory
+ * this node will occupy.
+ */
+public final class TreeNode {
+ private TreeNode left, right;
+ // The height of the tree
+ private int height;
+ private int size;
+ private Object storage;
+
+
+ /**
+ * Create a tree node that will occupy approximately given memory.
+ *
+ * @param memory memory
+ */
+ public TreeNode(long memory) {
+ int length = (int) (memory - (4 * 2 + 2 * Memory.getReferenceSize() + Memory.getObjectExtraSize()));
+ if (length > 0)
+ storage = new byte[length];
+ size = length;
+ }
+
+ /**
+ * Create a tree node that will occupy approximately given memory.
+ *
+ * @param memory memory
+ */
+ public TreeNode(long size, GarbageProducer gp) {
+ int length = (int) (size - (4 * 2 + 2 * Memory.getReferenceSize() + Memory.getObjectExtraSize()));
+ if (length > 0)
+ storage = gp.create(length);
+ size = length;
+ }
+ /**
+ * Create a tree node that will occupy approximately given memory
+ * with given left and right children.
+ *
+ * @param memory memory
+ * @param left left child
+ * @param right right child
+ */
+ public TreeNode(long memory, TreeNode left, TreeNode right) {
+ this(memory);
+ setLeft(left);
+ setRight(right);
+ setHeight(1 + Math.max(left == null ? 0 : left.getHeight(), right == null ? 0 : right.getHeight()));
+ }
+
+ /**
+ * Create a tree node that will occupy approximately given memory
+ * with given left and right children.
+ *
+ * @param memory memory
+ * @param left left child
+ * @param right right child
+ */
+ public TreeNode(long memory, GarbageProducer gp, TreeNode left, TreeNode right) {
+ this(memory, gp);
+ setLeft(left);
+ setRight(right);
+ setHeight(1 + Math.max(left == null ? 0 : left.getHeight(), right == null ? 0 : right.getHeight()));
+ }
+
+ /**
+ * Get memory that this node occupies.
+ *
+ * @return memory size
+ */
+ public long getSize() {
+ int length = storage == null ? 0 : size;
+ return length + 4 * 2 + 2 * Memory.getReferenceSize() + Memory.getObjectExtraSize();
+ }
+
+ /**
+ * Get memory that this subtree occupies.
+ *
+ * @return memory size
+ */
+ public long getTotalSize() {
+ long memory = getSize();
+ if (left != null)
+ memory += left.getSize();
+ if (right != null)
+ memory += right.getSize();
+ return memory;
+ }
+
+ /**
+ * Follow path determined by bits given integer and depth.
+ *
+ * @param path path encoded in integer
+ * @param depth depth to follow
+ * @return end of the path
+ */
+ public TreeNode follow(int path, int depth) {
+ if (depth == 0)
+ return this;
+ TreeNode current = this;
+ TreeNode prev = null;
+ for (int i = 0; i < depth; ++i) {
+ prev = current;
+ if ((path & 1) == 0)
+ current = current.left;
+ else
+ current = current.right;
+ path >>= 1;
+ }
+ return prev;
+ }
+
+ /**
+ * Swap left child of this node with left child of another node.
+ *
+ * @param another another node
+ */
+ public void swapLeft(TreeNode another) {
+ TreeNode tmp = another.left;
+ another.left = left;
+ left = tmp;
+ }
+ /**
+ * Swap right child of this node with right child of another node.
+ *
+ * @param another another node
+ */
+ public void swapRight(TreeNode another) {
+ TreeNode tmp = another.right;
+ another.right = right;
+ right = tmp;
+ }
+
+ public final TreeNode getLeft() {
+ return left;
+ }
+
+ public final void setLeft(TreeNode left) {
+ this.left = left;
+ }
+
+ public final TreeNode getRight() {
+ return right;
+ }
+
+ public final void setRight(TreeNode right) {
+ this.right = right;
+ }
+
+ public final int getHeight() {
+ return height;
+ }
+
+ public boolean hasLeft() {
+ return left != null;
+ }
+
+ public boolean hasRight() {
+ return right != null;
+ }
+
+ /**
+ * Get actual height of the tree.
+ */
+ public int getActualHeight() {
+ return 1 + Math.max(left == null ? 0 : left.getActualHeight(), right == null ? 0 : right.getActualHeight());
+ }
+
+ /**
+ * Get lenght of shortest path from root to leaf in the tree.
+ */
+ public int getShortestPath() {
+ return 1 + Math.min(left == null ? 0 : left.getActualHeight(), right == null ? 0 : right.getActualHeight());
+ }
+
+ public final void setHeight(int value) {
+ this.height = value;
+ }
+}