test/hotspot/jtreg/vmTestbase/nsk/share/gc/tree/TreeNode.java

/*
 * 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;
        }
}