1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
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;
}
}
|
