File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\index\TreeIndex.java.html

1 /*
2 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
3 * Version 1.0, and under the Eclipse Public License, Version 1.0
4 * (http://h2database.com/html/license.html).
5 * Initial Developer: H2 Group
6 */
7 package org.h2.index;
8
9 import org.h2.constant.SysProperties;
10 import org.h2.engine.Session;
11 import org.h2.message.DbException;
12 import org.h2.result.Row;
13 import org.h2.result.SearchRow;
14 import org.h2.table.IndexColumn;
15 import org.h2.table.RegularTable;
16 import org.h2.table.TableFilter;
17 import org.h2.value.Value;
18 import org.h2.value.ValueNull;
19
20 /**
21 * The tree index is an in-memory index based on a binary AVL trees.
22 */
23 public class TreeIndex extends BaseIndex {
24
25 private TreeNode root;
26 private final RegularTable tableData;
27 private long rowCount;
28 private boolean closed;
29
30 public TreeIndex(RegularTable table, int id, String indexName, IndexColumn[] columns, IndexType indexType) {
31 initBaseIndex(table, id, indexName, columns, indexType);
32 tableData = table;
33 }
34
35 public void close(Session session) {
36 root = null;
37 closed = true;
38 }
39
40 public void add(Session session, Row row) {
41 if (closed) {
42 throw DbException.throwInternalError();
43 }
44 TreeNode i = new TreeNode(row);
45 TreeNode n = root, x = n;
46 boolean isLeft = true;
47 while (true) {
48 if (n == null) {
49 if (x == null) {
50 root = i;
51 rowCount++;
52 return;
53 }
54 set(x, isLeft, i);
55 break;
56 }
57 Row r = n.row;
58 int compare = compareRows(row, r);
59 if (compare == 0) {
60 if (indexType.isUnique()) {
61 if (!containsNullAndAllowMultipleNull(row)) {
62 throw getDuplicateKeyException();
63 }
64 }
65 compare = compareKeys(row, r);
66 }
67 isLeft = compare < 0;
68 x = n;
69 n = child(x, isLeft);
70 }
71 balance(x, isLeft);
72 rowCount++;
73 }
74
75 private void balance(TreeNode x, boolean isLeft) {
76 while (true) {
77 int sign = isLeft ? 1 : -1;
78 switch (x.balance * sign) {
79 case 1:
80 x.balance = 0;
81 return;
82 case 0:
83 x.balance = -sign;
84 break;
85 case -1:
86 TreeNode l = child(x, isLeft);
87 if (l.balance == -sign) {
88 replace(x, l);
89 set(x, isLeft, child(l, !isLeft));
90 set(l, !isLeft, x);
91 x.balance = 0;
92 l.balance = 0;
93 } else {
94 TreeNode r = child(l, !isLeft);
95 replace(x, r);
96 set(l, !isLeft, child(r, isLeft));
97 set(r, isLeft, l);
98 set(x, isLeft, child(r, !isLeft));
99 set(r, !isLeft, x);
100 int rb = r.balance;
101 x.balance = (rb == -sign) ? sign : 0;
102 l.balance = (rb == sign) ? -sign : 0;
103 r.balance = 0;
104 }
105 return;
106 default:
107 DbException.throwInternalError("b:" + x.balance * sign);
108 }
109 if (x == root) {
110 return;
111 }
112 isLeft = x.isFromLeft();
113 x = x.parent;
114 }
115 }
116
117 private static TreeNode child(TreeNode x, boolean isLeft) {
118 return isLeft ? x.left : x.right;
119 }
120
121 private void replace(TreeNode x, TreeNode n) {
122 if (x == root) {
123 root = n;
124 if (n != null) {
125 n.parent = null;
126 }
127 } else {
128 set(x.parent, x.isFromLeft(), n);
129 }
130 }
131
132 private static void set(TreeNode parent, boolean left, TreeNode n) {
133 if (left) {
134 parent.left = n;
135 } else {
136 parent.right = n;
137 }
138 if (n != null) {
139 n.parent = parent;
140 }
141 }
142
143 public void remove(Session session, Row row) {
144 if (closed) {
145 throw DbException.throwInternalError();
146 }
147 TreeNode x = findFirstNode(row, true);
148 if (x == null) {
149 throw DbException.throwInternalError("not found!");
150 }
151 TreeNode n;
152 if (x.left == null) {
153 n = x.right;
154 } else if (x.right == null) {
155 n = x.left;
156 } else {
157 TreeNode d = x;
158 x = x.left;
159 for (TreeNode temp = x; (temp = temp.right) != null;) {
160 x = temp;
161 }
162 // x will be replaced with n later
163 n = x.left;
164 // swap d and x
165 int b = x.balance;
166 x.balance = d.balance;
167 d.balance = b;
168
169 // set x.parent
170 TreeNode xp = x.parent;
171 TreeNode dp = d.parent;
172 if (d == root) {
173 root = x;
174 }
175 x.parent = dp;
176 if (dp != null) {
177 if (dp.right == d) {
178 dp.right = x;
179 } else {
180 dp.left = x;
181 }
182 }
183 // TODO index / tree: link d.r = x(p?).r directly
184 if (xp == d) {
185 d.parent = x;
186 if (d.left == x) {
187 x.left = d;
188 x.right = d.right;
189 } else {
190 x.right = d;
191 x.left = d.left;
192 }
193 } else {
194 d.parent = xp;
195 xp.right = d;
196 x.right = d.right;
197 x.left = d.left;
198 }
199
200 if (SysProperties.CHECK && x.right == null) {
201 DbException.throwInternalError("tree corrupted");
202 }
203 x.right.parent = x;
204 x.left.parent = x;
205 // set d.left, d.right
206 d.left = n;
207 if (n != null) {
208 n.parent = d;
209 }
210 d.right = null;
211 x = d;
212 }
213 rowCount--;
214
215 boolean isLeft = x.isFromLeft();
216 replace(x, n);
217 n = x.parent;
218 while (n != null) {
219 x = n;
220 int sign = isLeft ? 1 : -1;
221 switch (x.balance * sign) {
222 case -1:
223 x.balance = 0;
224 break;
225 case 0:
226 x.balance = sign;
227 return;
228 case 1:
229 TreeNode r = child(x, !isLeft);
230 int b = r.balance;
231 if (b * sign >= 0) {
232 replace(x, r);
233 set(x, !isLeft, child(r, isLeft));
234 set(r, isLeft, x);
235 if (b == 0) {
236 x.balance = sign;
237 r.balance = -sign;
238 return;
239 }
240 x.balance = 0;
241 r.balance = 0;
242 x = r;
243 } else {
244 TreeNode l = child(r, isLeft);
245 replace(x, l);
246 b = l.balance;
247 set(r, isLeft, child(l, !isLeft));
248 set(l, !isLeft, r);
249 set(x, !isLeft, child(l, isLeft));
250 set(l, isLeft, x);
251 x.balance = (b == sign) ? -sign : 0;
252 r.balance = (b == -sign) ? sign : 0;
253 l.balance = 0;
254 x = l;
255 }
256 break;
257 default:
258 DbException.throwInternalError("b: " + x.balance * sign);
259 }
260 isLeft = x.isFromLeft();
261 n = x.parent;
262 }
263 }
264
265 private TreeNode findFirstNode(SearchRow row, boolean withKey) {
266 TreeNode x = root, result = x;
267 while (x != null) {
268 result = x;
269 int compare = compareRows(x.row, row);
270 if (compare == 0 && withKey) {
271 compare = compareKeys(x.row, row);
272 }
273 if (compare == 0) {
274 if (withKey) {
275 return x;
276 }
277 x = x.left;
278 } else if (compare > 0) {
279 x = x.left;
280 } else {
281 x = x.right;
282 }
283 }
284 return result;
285 }
286
287 public Cursor find(TableFilter filter, SearchRow first, SearchRow last) {
288 return find(first, last);
289 }
290
291 public Cursor find(Session session, SearchRow first, SearchRow last) {
292 return find(first, last);
293 }
294
295 private Cursor find(SearchRow first, SearchRow last) {
296 if (first == null) {
297 TreeNode x = root, n;
298 while (x != null) {
299 n = x.left;
300 if (n == null) {
301 break;
302 }
303 x = n;
304 }
305 return new TreeCursor(this, x, null, last);
306 }
307 TreeNode x = findFirstNode(first, false);
308 return new TreeCursor(this, x, first, last);
309 }
310
311 public double getCost(Session session, int[] masks) {
312 return getCostRangeIndex(masks, tableData.getRowCountApproximation());
313 }
314
315 public void remove(Session session) {
316 truncate(session);
317 }
318
319 public void truncate(Session session) {
320 root = null;
321 rowCount = 0;
322 }
323
324 public void checkRename() {
325 // nothing to do
326 }
327
328 public boolean needRebuild() {
329 return true;
330 }
331
332 public boolean canGetFirstOrLast() {
333 return true;
334 }
335
336 public Cursor findFirstOrLast(Session session, boolean first) {
337 if (closed) {
338 throw DbException.throwInternalError();
339 }
340 if (first) {
341 // TODO optimization: this loops through NULL
342 Cursor cursor = find(session, null, null);
343 while (cursor.next()) {
344 SearchRow row = cursor.getSearchRow();
345 Value v = row.getValue(columnIds[0]);
346 if (v != ValueNull.INSTANCE) {
347 return cursor;
348 }
349 }
350 return cursor;
351 }
352 TreeNode x = root, n;
353 while (x != null) {
354 n = x.right;
355 if (n == null) {
356 break;
357 }
358 x = n;
359 }
360 TreeCursor cursor = new TreeCursor(this, x, null, null);
361 if (x == null) {
362 return cursor;
363 }
364 // TODO optimization: this loops through NULL elements
365 do {
366 SearchRow row = cursor.getSearchRow();
367 if (row == null) {
368 break;
369 }
370 Value v = row.getValue(columnIds[0]);
371 if (v != ValueNull.INSTANCE) {
372 return cursor;
373 }
374 } while (cursor.previous());
375 return cursor;
376 }
377
378 public long getRowCount(Session session) {
379 return rowCount;
380 }
381
382 public long getRowCountApproximation() {
383 return rowCount;
384 }
385
386 }
387