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