EMMA Coverage Report (generated Sun Mar 01 22:06:14 CET 2015)
[all classes][org.h2.index]

COVERAGE SUMMARY FOR SOURCE FILE [TreeIndex.java]

nameclass, %method, %block, %line, %
TreeIndex.java100% (1/1)68%  (15/22)44%  (372/854)49%  (113.4/233)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class TreeIndex100% (1/1)68%  (15/22)44%  (372/854)49%  (113.4/233)
checkRename (): void 0%   (0/1)0%   (0/1)0%   (0/1)
getCost (Session, int [], TableFilter, SortOrder): double 0%   (0/1)0%   (0/10)0%   (0/1)
getDiskSpaceUsed (): long 0%   (0/1)0%   (0/2)0%   (0/1)
getRowCount (Session): long 0%   (0/1)0%   (0/3)0%   (0/1)
getRowCountApproximation (): long 0%   (0/1)0%   (0/3)0%   (0/1)
remove (Session): void 0%   (0/1)0%   (0/4)0%   (0/2)
truncate (Session): void 0%   (0/1)0%   (0/7)0%   (0/3)
remove (Session, Row): void 100% (1/1)17%  (58/334)21%  (18.8/88)
findFirstOrLast (Session, boolean): Cursor 100% (1/1)27%  (22/83)25%  (7/28)
balance (TreeNode, boolean): void 100% (1/1)41%  (63/152)56%  (16.7/30)
add (Session, Row): void 100% (1/1)75%  (66/88)80%  (20.8/26)
findFirstNode (SearchRow, boolean): TreeNode 100% (1/1)91%  (43/47)93%  (14/15)
TreeIndex (RegularTable, int, String, IndexColumn [], IndexType): void 100% (1/1)100% (19/19)100% (6/6)
canGetFirstOrLast (): boolean 100% (1/1)100% (2/2)100% (1/1)
child (TreeNode, boolean): TreeNode 100% (1/1)100% (8/8)100% (1/1)
close (Session): void 100% (1/1)100% (7/7)100% (3/3)
find (SearchRow, SearchRow): Cursor 100% (1/1)100% (37/37)100% (10/10)
find (Session, SearchRow, SearchRow): Cursor 100% (1/1)100% (5/5)100% (1/1)
find (TableFilter, SearchRow, SearchRow): Cursor 100% (1/1)100% (5/5)100% (1/1)
needRebuild (): boolean 100% (1/1)100% (2/2)100% (1/1)
replace (TreeNode, TreeNode): void 100% (1/1)100% (20/20)100% (6/6)
set (TreeNode, boolean, TreeNode): void 100% (1/1)100% (15/15)100% (6/6)

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

[all classes][org.h2.index]
EMMA 2.0.5312 (C) Vladimir Roubtsov