1 /*
2 * Copyright (c) 2007, 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
24 package nsk.share.gc.tree;
25
26 import nsk.share.gc.Memory;
27 import nsk.share.gc.gp.GarbageProducer;
28
29 /**
30 * A node of binary tree.
31 *
32 * A height of subtree defined by this node is kept in the node.
33 * Additionaly, a byte array is used to control how much memory
34 * this node will occupy.
35 */
36 public final class TreeNode {
37 private TreeNode left, right;
38 // The height of the tree
39 private int height;
40 private int size;
41 private Object storage;
42
43
44 /**
45 * Create a tree node that will occupy approximately given memory.
46 *
47 * @param memory memory
48 */
49 public TreeNode(long memory) {
50 int length = (int) (memory - (4 * 2 + 2 * Memory.getReferenceSize() + Memory.getObjectExtraSize()));
51 size = length;
52 if (length <= 0) {
53 return;
54 }
55 if (Memory.isValhallaEnabled()) {
56 storage = new Integer[Memory.getArrayLength(memory, Memory.getIntegerArrayElementSize())];
57 } else {
58 storage = new int[Memory.getArrayLength(memory, Memory.getIntSize())];
59 }
60 }
61
62 /**
63 * Create a tree node that will occupy approximately given memory.
64 *
65 * @param memory memory
66 */
67 public TreeNode(long size, GarbageProducer gp) {
68 int length = (int) (size - (4 * 2 + 2 * Memory.getReferenceSize() + Memory.getObjectExtraSize()));
69 if (length > 0)
70 storage = gp.create(length);
71 size = length;
72 }
73 /**
74 * Create a tree node that will occupy approximately given memory
75 * with given left and right children.
76 *
77 * @param memory memory
78 * @param left left child
79 * @param right right child
80 */
81 public TreeNode(long memory, TreeNode left, TreeNode right) {
82 this(memory);
83 setLeft(left);
84 setRight(right);
85 setHeight(1 + Math.max(left == null ? 0 : left.getHeight(), right == null ? 0 : right.getHeight()));
86 }
87
88 /**
89 * Create a tree node that will occupy approximately given memory
90 * with given left and right children.
91 *
92 * @param memory memory
93 * @param left left child
94 * @param right right child
95 */
96 public TreeNode(long memory, GarbageProducer gp, TreeNode left, TreeNode right) {
97 this(memory, gp);
98 setLeft(left);
99 setRight(right);
100 setHeight(1 + Math.max(left == null ? 0 : left.getHeight(), right == null ? 0 : right.getHeight()));
101 }
102
103 /**
104 * Get memory that this node occupies.
105 *
106 * @return memory size
107 */
108 public long getSize() {
109 int length = storage == null ? 0 : size;
110 return length + 4 * 2 + 2 * Memory.getReferenceSize() + Memory.getObjectExtraSize();
111 }
112
113 /**
114 * Get memory that this subtree occupies.
115 *
116 * @return memory size
117 */
118 public long getTotalSize() {
119 long memory = getSize();
120 if (left != null)
121 memory += left.getSize();
122 if (right != null)
123 memory += right.getSize();
124 return memory;
125 }
126
127 /**
128 * Follow path determined by bits given integer and depth.
129 *
130 * @param path path encoded in integer
131 * @param depth depth to follow
132 * @return end of the path
133 */
134 public TreeNode follow(int path, int depth) {
135 if (depth == 0)
136 return this;
137 TreeNode current = this;
138 TreeNode prev = null;
139 for (int i = 0; i < depth; ++i) {
140 prev = current;
141 if ((path & 1) == 0)
142 current = current.left;
143 else
144 current = current.right;
145 path >>= 1;
146 }
147 return prev;
148 }
149
150 /**
151 * Swap left child of this node with left child of another node.
152 *
153 * @param another another node
154 */
155 public void swapLeft(TreeNode another) {
156 TreeNode tmp = another.left;
157 another.left = left;
158 left = tmp;
159 }
160 /**
161 * Swap right child of this node with right child of another node.
162 *
163 * @param another another node
164 */
165 public void swapRight(TreeNode another) {
166 TreeNode tmp = another.right;
167 another.right = right;
168 right = tmp;
169 }
170
171 public final TreeNode getLeft() {
172 return left;
173 }
174
175 public final void setLeft(TreeNode left) {
176 this.left = left;
177 }
178
179 public final TreeNode getRight() {
180 return right;
181 }
182
183 public final void setRight(TreeNode right) {
184 this.right = right;
185 }
186
187 public final int getHeight() {
188 return height;
189 }
190
191 public boolean hasLeft() {
192 return left != null;
193 }
194
195 public boolean hasRight() {
196 return right != null;
197 }
198
199 /**
200 * Get actual height of the tree.
201 */
202 public int getActualHeight() {
203 return 1 + Math.max(left == null ? 0 : left.getActualHeight(), right == null ? 0 : right.getActualHeight());
204 }
205
206 /**
207 * Get lenght of shortest path from root to leaf in the tree.
208 */
209 public int getShortestPath() {
210 return 1 + Math.min(left == null ? 0 : left.getActualHeight(), right == null ? 0 : right.getActualHeight());
211 }
212
213 public final void setHeight(int value) {
214 this.height = value;
215 }
216 }