|
1
5 package org.h2.index;
6
7 import java.sql.SQLException  ;
8
9 import org.h2.engine.Constants;
10 import org.h2.engine.Session;
11 import org.h2.message.Message;
12 import org.h2.result.Row;
13 import org.h2.result.SearchRow;
14 import org.h2.table.Column;
15 import org.h2.table.TableData;
16 import org.h2.value.Value;
17 import org.h2.value.ValueNull;
18
19
20 public class TreeIndex extends Index {
21
22 private TreeNode root;
23 private TableData tableData;
24
25 public TreeIndex(TableData table, int id, String indexName, Column[] columns, IndexType indexType) {
26 super(table, id, indexName, columns, indexType);
27 tableData = table;
28 }
29
30 public void close(Session session) throws SQLException {
31 root = null;
32 }
33
34 public void add(Session session, Row row) throws SQLException {
35 TreeNode i = new TreeNode(row);
36 TreeNode n = root, x = n;
37 boolean isleft = true;
38 while (true) {
39 if (n == null) {
40 if (x == null) {
41 root = i;
42 rowCount++;
43 return;
44 }
45 set(x, isleft, i);
46 break;
47 }
48 Row r = n.row;
49 int compare = compareRows(row, r);
50 if (compare == 0) {
51 if(indexType.isUnique()) {
52 if(!isNull(row)) {
53 throw getDuplicateKeyException();
54 }
55 }
56 compare = compareKeys(row, r);
57 }
58 isleft = compare < 0;
59 x = n;
60 n = child(x, isleft);
61 }
62 balance(x, isleft);
63 rowCount++;
64 }
65
66 private void balance(TreeNode x, boolean isleft) {
67 while (true) {
68 int sign = isleft ? 1 : -1;
69 switch (x.balance * sign) {
70 case 1 :
71 x.balance = 0;
72 return;
73 case 0 :
74 x.balance = -sign;
75 break;
76 case -1 :
77 TreeNode l = child(x, isleft);
78 if (l.balance == -sign) {
79 replace(x, l);
80 set(x, isleft, child(l, !isleft));
81 set(l, !isleft, x);
82 x.balance = 0;
83 l.balance = 0;
84 } else {
85 TreeNode r = child(l, !isleft);
86 replace(x, r);
87 set(l, !isleft, child(r, isleft));
88 set(r, isleft, l);
89 set(x, isleft, child(r, !isleft));
90 set(r, !isleft, x);
91 int rb = r.balance;
92 x.balance = (rb == -sign) ? sign : 0;
93 l.balance = (rb == sign) ? -sign : 0;
94 r.balance = 0;
95 }
96 return;
97 }
98 if (x == root) {
99 return;
100 }
101 isleft = x.isFromLeft();
102 x = x.parent;
103 }
104 }
105
106 private TreeNode child(TreeNode x, boolean isleft) {
107 return isleft ? x.left : x.right;
108 }
109
110 private void replace(TreeNode x, TreeNode n) {
111 if (x == root) {
112 root = n;
113 if (n != null) {
114 n.parent = null;
115 }
116 } else {
117 set(x.parent, x.isFromLeft(), n);
118 }
119 }
120
121 private void set(TreeNode parent, boolean left, TreeNode n) {
122 if (left) {
123 parent.left = n;
124 } else {
125 parent.right = n;
126 }
127 if (n != null) {
128 n.parent = parent;
129 }
130 }
131
132 public void remove(Session session, Row row) throws SQLException {
133 TreeNode x = findFirstNode(row, true);
134 if (x == null) {
135 throw Message.getInternalError("not found!");
136 }
137 TreeNode n;
138 if (x.left == null) {
139 n = x.right;
140 } else if (x.right == null) {
141 n = x.left;
142 } else {
143 TreeNode d = x;
144 x = x.left;
145 for (TreeNode temp = x; (temp = temp.right) != null;) {
146 x = temp;
147 }
148 n = x.left;
150 int b = x.balance;
152 x.balance = d.balance;
153 d.balance = b;
154
155 TreeNode xp = x.parent;
157 TreeNode dp = d.parent;
158 if (d == root) {
159 root = x;
160 }
161 x.parent = dp;
162 if (dp != null) {
163 if (dp.right == d) {
164 dp.right = x;
165 } else {
166 dp.left = x;
167 }
168 }
169 if (xp == d) {
171 d.parent = x;
172 if (d.left == x) {
173 x.left = d;
174 x.right = d.right;
175 } else {
176 x.right = d;
177 x.left = d.left;
178 }
179 } else {
180 d.parent = xp;
181 xp.right = d;
182 x.right = d.right;
183 x.left = d.left;
184 }
185
186 if(Constants.CHECK && (x.right==null || x==null)) {
187 throw Message.getInternalError("tree corrupted");
188 }
189 x.right.parent = x;
190 x.left.parent = x;
191 d.left = n;
193 if (n != null) {
194 n.parent =d;
195 }
196 d.right =null;
197 x = d;
198 }
199 rowCount--;
200
201 boolean isleft = x.isFromLeft();
202 replace(x, n);
203 n = x.parent;
204 while (n != null) {
205 x = n;
206 int sign = isleft ? 1 : -1;
207 switch (x.balance * sign) {
208 case -1 :
209 x.balance = 0;
210 break;
211 case 0 :
212 x.balance = sign;
213 return;
214 case 1 :
215 TreeNode r = child(x, !isleft);
216 int b = r.balance;
217 if (b * sign >= 0) {
218 replace(x, r);
219 set(x, !isleft, child(r, isleft));
220 set(r, isleft, x);
221 if (b == 0) {
222 x.balance = sign;
223 r.balance = -sign;
224 return;
225 }
226 x.balance = 0;
227 r.balance = 0;
228 x = r;
229 } else {
230 TreeNode l = child(r, isleft);
231 replace(x, l);
232 b = l.balance;
233 set(r, isleft, child(l, !isleft));
234 set(l, !isleft, r);
235 set(x, !isleft, child(l, isleft));
236 set(l, isleft, x);
237 x.balance = (b == sign) ? -sign : 0;
238 r.balance = (b == -sign) ? sign : 0;
239 l.balance = 0;
240 x = l;
241 }
242 }
243 isleft = x.isFromLeft();
244 n = x.parent;
245 }
246 }
247
248 private TreeNode findFirstNode(SearchRow row, boolean withKey) throws SQLException {
249 TreeNode x = root, result = x;
250 while (x != null) {
251 result = x;
252 int compare = compareRows(x.row, row);
253 if (compare == 0 && withKey) {
254 compare = compareKeys(x.row, row);
255 }
256 if (compare == 0) {
257 if (withKey) {
258 return x;
259 }
260 x = x.left;
261 } else if (compare > 0) {
262 x = x.left;
263 } else {
264 x = x.right;
265 }
266 }
267 return result;
268 }
269
270 public Cursor find(Session session, SearchRow first, SearchRow last) throws SQLException {
271 if(first == null) {
272 TreeNode x = root, n;
273 while (x != null) {
274 n = x.left;
275 if (n == null) {
276 break;
277 }
278 x = n;
279 }
280 return new TreeCursor(this, x, null, last);
281 } else {
282 TreeNode x = findFirstNode(first, false);
283 return new TreeCursor(this, x, first, last);
284 }
285 }
286
287 public int getLookupCost(int rowCount) {
288 for(int i=0, j = 1; ; i++) {
289 j += j;
290 if(j>=rowCount) {
291 return i;
292 }
293 }
294 }
295
296 public int getCost(int[] masks) throws SQLException {
297 return getCostRangeIndex(masks, tableData.getRowCount());
298 }
299
300 public void remove(Session session) throws SQLException {
301 truncate(session);
302 }
303
304 public void truncate(Session session) throws SQLException {
305 root = null;
306 rowCount = 0;
307 }
308
309 TreeNode next(TreeNode x) {
310 if (x == null) {
311 return null;
312 }
313 TreeNode r = x.right;
314 if (r != null) {
315 x = r;
316 TreeNode l = x.left;
317 while (l != null) {
318 x = l;
319 l = x.left;
320 }
321 return x;
322 }
323 TreeNode ch = x;
324 x = x.parent;
325 while (x != null && ch == x.right) {
326 ch = x;
327 x = x.parent;
328 }
329 return x;
330 }
331
332 public void checkRename() throws SQLException {
333 }
334
335 public boolean needRebuild() {
336 return true;
337 }
338
339 public boolean canGetFirstOrLast(boolean first) {
340 return true;
341 }
342
343 public Value findFirstOrLast(Session session, boolean first) throws SQLException {
344 if(first) {
345 Cursor cursor = find(session, null, null);
347 while(cursor.next()) {
348 Value v = cursor.get().getValue(columnIndex[0]);
349 if(v != ValueNull.INSTANCE) {
350 return v;
351 }
352 }
353 return ValueNull.INSTANCE;
354 } else {
355 TreeNode x = root, n;
356 while (x != null) {
357 n = x.right;
358 if (n == null) {
359 break;
360 }
361 x = n;
362 }
363 if(x != null) {
364 Value v = x.row.getValue(columnIndex[0]);
365 return v;
366 }
367 return ValueNull.INSTANCE;
368 }
369 }
370
371 }
372 |
Popular Tags |
Java API By Example, From Geeks To Geeks.