KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > h2 > index > TreeIndex


1 /*
2  * Copyright 2004-2006 H2 Group. Licensed under the H2 License, Version 1.0 (http://h2database.com/html/license.html).
3  * Initial Developer: H2 Group
4  */

5 package org.h2.index;
6
7 import java.sql.SQLException JavaDoc;
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 JavaDoc 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 JavaDoc {
31         root = null;
32     }
33
34     public void add(Session session, Row row) throws SQLException JavaDoc {
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 JavaDoc {
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             // x will be replaced with n later
149
n = x.left;
150             // swap d and x
151
int b = x.balance;
152             x.balance = d.balance;
153             d.balance = b;
154
155             // set x.parent
156
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             // TODO index / tree: link d.r = x(p?).r directly
170
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             // set d.left, d.right
192
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 JavaDoc {
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 JavaDoc {
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 JavaDoc {
297         return getCostRangeIndex(masks, tableData.getRowCount());
298     }
299
300     public void remove(Session session) throws SQLException JavaDoc {
301         truncate(session);
302     }
303
304     public void truncate(Session session) throws SQLException JavaDoc {
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 JavaDoc {
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 JavaDoc {
344         if(first) {
345             // TODO optimization: this loops through NULL values
346
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