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

COVERAGE SUMMARY FOR SOURCE FILE [PageBtreeIndex.java]

nameclass, %method, %block, %line, %
PageBtreeIndex.java100% (1/1)37%  (13/35)27%  (252/947)28%  (55.9/203)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class PageBtreeIndex100% (1/1)37%  (13/35)27%  (252/947)28%  (55.9/203)
add (Session, Row): void 0%   (0/1)0%   (0/37)0%   (0/7)
addRow (SearchRow): void 0%   (0/1)0%   (0/106)0%   (0/26)
canFindNext (): boolean 0%   (0/1)0%   (0/2)0%   (0/1)
canGetFirstOrLast (): boolean 0%   (0/1)0%   (0/2)0%   (0/1)
checkRename (): void 0%   (0/1)0%   (0/1)0%   (0/1)
findFirstOrLast (Session, boolean): Cursor 0%   (0/1)0%   (0/71)0%   (0/21)
findNext (Session, SearchRow, SearchRow): Cursor 0%   (0/1)0%   (0/7)0%   (0/1)
getDiskSpaceUsed (): long 0%   (0/1)0%   (0/4)0%   (0/1)
getRow (Session, long): Row 0%   (0/1)0%   (0/6)0%   (0/1)
getRowCount (Session): long 0%   (0/1)0%   (0/3)0%   (0/1)
getRowCountApproximation (): long 0%   (0/1)0%   (0/4)0%   (0/1)
getRowSize (Data, SearchRow, boolean): int 0%   (0/1)0%   (0/36)0%   (0/6)
getSearchRow (Row): SearchRow 0%   (0/1)0%   (0/43)0%   (0/6)
hasData (SearchRow): boolean 0%   (0/1)0%   (0/12)0%   (0/1)
invalidateRowCount (): void 0%   (0/1)0%   (0/9)0%   (0/3)
readRow (Data, int, boolean, boolean): SearchRow 0%   (0/1)0%   (0/83)0%   (0/16)
readRow (long): SearchRow 0%   (0/1)0%   (0/6)0%   (0/1)
remove (Session): void 0%   (0/1)0%   (0/21)0%   (0/6)
remove (Session, Row): void 0%   (0/1)0%   (0/55)0%   (0/11)
removeAllRows (): void 0%   (0/1)0%   (0/36)0%   (0/9)
truncate (Session): void 0%   (0/1)0%   (0/26)0%   (0/7)
writeRow (Data, int, SearchRow, boolean): void 0%   (0/1)0%   (0/35)0%   (0/7)
getPage (int): PageBtree 100% (1/1)32%  (13/40)44%  (4/9)
close (Session): void 100% (1/1)52%  (11/21)75%  (4.5/6)
memoryChange (int): void 100% (1/1)55%  (23/42)75%  (3/4)
writeRowCount (): void 100% (1/1)76%  (13/17)68%  (3.4/5)
PageBtreeIndex (RegularTable, int, String, IndexColumn [], IndexType, boolean... 100% (1/1)80%  (109/136)92%  (22/24)
find (Session, SearchRow, boolean, SearchRow): Cursor 100% (1/1)89%  (24/27)83%  (5/6)
find (Session, SearchRow, SearchRow): Cursor 100% (1/1)100% (7/7)100% (1/1)
getCost (Session, int [], TableFilter, SortOrder): double 100% (1/1)100% (13/13)100% (1/1)
getMemoryPerPage (): int 100% (1/1)100% (3/3)100% (1/1)
getPageStore (): PageStore 100% (1/1)100% (3/3)100% (1/1)
isMemoryChangeRequired (): boolean 100% (1/1)100% (12/12)100% (4/4)
needRebuild (): boolean 100% (1/1)100% (3/3)100% (1/1)
setRootPageId (Session, int): void 100% (1/1)100% (18/18)100% (5/5)

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.api.ErrorCode;
9import org.h2.engine.Constants;
10import org.h2.engine.Session;
11import org.h2.engine.SysProperties;
12import org.h2.message.DbException;
13import org.h2.result.Row;
14import org.h2.result.SearchRow;
15import org.h2.result.SortOrder;
16import org.h2.store.Data;
17import org.h2.store.Page;
18import org.h2.store.PageStore;
19import org.h2.table.Column;
20import org.h2.table.IndexColumn;
21import org.h2.table.RegularTable;
22import org.h2.table.TableFilter;
23import org.h2.util.MathUtils;
24import org.h2.value.Value;
25import org.h2.value.ValueNull;
26 
27/**
28 * This is the most common type of index, a b tree index.
29 * Only the data of the indexed columns are stored in the index.
30 */
31public class PageBtreeIndex extends PageIndex {
32 
33    private static int memoryChangeRequired;
34 
35    private final PageStore store;
36    private final RegularTable tableData;
37    private final boolean needRebuild;
38    private long rowCount;
39    private int memoryPerPage;
40    private int memoryCount;
41 
42    public PageBtreeIndex(RegularTable table, int id, String indexName,
43            IndexColumn[] columns,
44            IndexType indexType, boolean create, Session session) {
45        initBaseIndex(table, id, indexName, columns, indexType);
46        if (!database.isStarting() && create) {
47            checkIndexColumnTypes(columns);
48        }
49        // int test;
50        // trace.setLevel(TraceSystem.DEBUG);
51        tableData = table;
52        if (!database.isPersistent() || id < 0) {
53            throw DbException.throwInternalError("" + indexName);
54        }
55        this.store = database.getPageStore();
56        store.addIndex(this);
57        if (create) {
58            // new index
59            rootPageId = store.allocatePage();
60            // TODO currently the head position is stored in the log
61            // it should not for new tables, otherwise redo of other operations
62            // must ensure this page is not used for other things
63            store.addMeta(this, session);
64            PageBtreeLeaf root = PageBtreeLeaf.create(this, rootPageId, PageBtree.ROOT);
65            store.logUndo(root, null);
66            store.update(root);
67        } else {
68            rootPageId = store.getRootPageId(id);
69            PageBtree root = getPage(rootPageId);
70            rowCount = root.getRowCount();
71        }
72        this.needRebuild = create || (rowCount == 0 && store.isRecoveryRunning());
73        if (trace.isDebugEnabled()) {
74            trace.debug("opened {0} rows: {1}", getName() , rowCount);
75        }
76        memoryPerPage = (Constants.MEMORY_PAGE_BTREE + store.getPageSize()) >> 2;
77    }
78 
79    @Override
80    public void add(Session session, Row row) {
81        if (trace.isDebugEnabled()) {
82            trace.debug("{0} add {1}", getName(), row);
83        }
84        // safe memory
85        SearchRow newRow = getSearchRow(row);
86        try {
87            addRow(newRow);
88        } finally {
89            store.incrementChangeCount();
90        }
91    }
92 
93    private void addRow(SearchRow newRow) {
94        while (true) {
95            PageBtree root = getPage(rootPageId);
96            int splitPoint = root.addRowTry(newRow);
97            if (splitPoint == -1) {
98                break;
99            }
100            if (trace.isDebugEnabled()) {
101                trace.debug("split {0}", splitPoint);
102            }
103            SearchRow pivot = root.getRow(splitPoint - 1);
104            store.logUndo(root, root.data);
105            PageBtree page1 = root;
106            PageBtree page2 = root.split(splitPoint);
107            store.logUndo(page2, null);
108            int id = store.allocatePage();
109            page1.setPageId(id);
110            page1.setParentPageId(rootPageId);
111            page2.setParentPageId(rootPageId);
112            PageBtreeNode newRoot = PageBtreeNode.create(
113                    this, rootPageId, PageBtree.ROOT);
114            store.logUndo(newRoot, null);
115            newRoot.init(page1, pivot, page2);
116            store.update(page1);
117            store.update(page2);
118            store.update(newRoot);
119            root = newRoot;
120        }
121        invalidateRowCount();
122        rowCount++;
123    }
124 
125    /**
126     * Create a search row for this row.
127     *
128     * @param row the row
129     * @return the search row
130     */
131    private SearchRow getSearchRow(Row row) {
132        SearchRow r = table.getTemplateSimpleRow(columns.length == 1);
133        r.setKeyAndVersion(row);
134        for (Column c : columns) {
135            int idx = c.getColumnId();
136            r.setValue(idx, row.getValue(idx));
137        }
138        return r;
139    }
140 
141    /**
142     * Read the given page.
143     *
144     * @param id the page id
145     * @return the page
146     */
147    PageBtree getPage(int id) {
148        Page p = store.getPage(id);
149        if (p == null) {
150            PageBtreeLeaf empty = PageBtreeLeaf.create(this, id, PageBtree.ROOT);
151            // could have been created before, but never committed
152            store.logUndo(empty, null);
153            store.update(empty);
154            return empty;
155        } else if (!(p instanceof PageBtree)) {
156            throw DbException.get(ErrorCode.FILE_CORRUPTED_1, "" + p);
157        }
158        return (PageBtree) p;
159    }
160 
161    @Override
162    public boolean canGetFirstOrLast() {
163        return true;
164    }
165 
166    @Override
167    public Cursor findNext(Session session, SearchRow first, SearchRow last) {
168        return find(session, first, true, last);
169    }
170 
171    @Override
172    public Cursor find(Session session, SearchRow first, SearchRow last) {
173        return find(session, first, false, last);
174    }
175 
176    private Cursor find(Session session, SearchRow first, boolean bigger,
177            SearchRow last) {
178        if (SysProperties.CHECK && store == null) {
179            throw DbException.get(ErrorCode.OBJECT_CLOSED);
180        }
181        PageBtree root = getPage(rootPageId);
182        PageBtreeCursor cursor = new PageBtreeCursor(session, this, last);
183        root.find(cursor, first, bigger);
184        return cursor;
185    }
186 
187    @Override
188    public Cursor findFirstOrLast(Session session, boolean first) {
189        if (first) {
190            // TODO optimization: this loops through NULL elements
191            Cursor cursor = find(session, null, false, null);
192            while (cursor.next()) {
193                SearchRow row = cursor.getSearchRow();
194                Value v = row.getValue(columnIds[0]);
195                if (v != ValueNull.INSTANCE) {
196                    return cursor;
197                }
198            }
199            return cursor;
200        }
201        PageBtree root = getPage(rootPageId);
202        PageBtreeCursor cursor = new PageBtreeCursor(session, this, null);
203        root.last(cursor);
204        cursor.previous();
205        // TODO optimization: this loops through NULL elements
206        do {
207            SearchRow row = cursor.getSearchRow();
208            if (row == null) {
209                break;
210            }
211            Value v = row.getValue(columnIds[0]);
212            if (v != ValueNull.INSTANCE) {
213                return cursor;
214            }
215        } while (cursor.previous());
216        return cursor;
217    }
218 
219    @Override
220    public double getCost(Session session, int[] masks, TableFilter filter,
221            SortOrder sortOrder) {
222        return 10 * getCostRangeIndex(masks, tableData.getRowCount(session),
223                filter, sortOrder);
224    }
225 
226    @Override
227    public boolean needRebuild() {
228        return needRebuild;
229    }
230 
231    @Override
232    public void remove(Session session, Row row) {
233        if (trace.isDebugEnabled()) {
234            trace.debug("{0} remove {1}", getName(), row);
235        }
236        // TODO invalidate row count
237        // setChanged(session);
238        if (rowCount == 1) {
239            removeAllRows();
240        } else {
241            try {
242                PageBtree root = getPage(rootPageId);
243                root.remove(row);
244                invalidateRowCount();
245                rowCount--;
246            } finally {
247                store.incrementChangeCount();
248            }
249        }
250    }
251 
252    @Override
253    public void remove(Session session) {
254        if (trace.isDebugEnabled()) {
255            trace.debug("remove");
256        }
257        removeAllRows();
258        store.free(rootPageId);
259        store.removeMeta(this, session);
260    }
261 
262    @Override
263    public void truncate(Session session) {
264        if (trace.isDebugEnabled()) {
265            trace.debug("truncate");
266        }
267        removeAllRows();
268        if (tableData.getContainsLargeObject()) {
269            database.getLobStorage().removeAllForTable(table.getId());
270        }
271        tableData.setRowCount(0);
272    }
273 
274    private void removeAllRows() {
275        try {
276            PageBtree root = getPage(rootPageId);
277            root.freeRecursive();
278            root = PageBtreeLeaf.create(this, rootPageId, PageBtree.ROOT);
279            store.removeFromCache(rootPageId);
280            store.update(root);
281            rowCount = 0;
282        } finally {
283            store.incrementChangeCount();
284        }
285    }
286 
287    @Override
288    public void checkRename() {
289        // ok
290    }
291 
292    /**
293     * Get a row from the main index.
294     *
295     * @param session the session
296     * @param key the row key
297     * @return the row
298     */
299    @Override
300    public Row getRow(Session session, long key) {
301        return tableData.getRow(session, key);
302    }
303 
304    PageStore getPageStore() {
305        return store;
306    }
307 
308    @Override
309    public long getRowCountApproximation() {
310        return tableData.getRowCountApproximation();
311    }
312 
313    @Override
314    public long getDiskSpaceUsed() {
315        return tableData.getDiskSpaceUsed();
316    }
317 
318    @Override
319    public long getRowCount(Session session) {
320        return rowCount;
321    }
322 
323    @Override
324    public void close(Session session) {
325        if (trace.isDebugEnabled()) {
326            trace.debug("close");
327        }
328        // can not close the index because it might get used afterwards,
329        // for example after running recovery
330        try {
331            writeRowCount();
332        } finally {
333            store.incrementChangeCount();
334        }
335    }
336 
337    /**
338     * Read a row from the data page at the given offset.
339     *
340     * @param data the data
341     * @param offset the offset
342     * @param onlyPosition whether only the position of the row is stored
343     * @param needData whether the row data is required
344     * @return the row
345     */
346    SearchRow readRow(Data data, int offset, boolean onlyPosition,
347            boolean needData) {
348        synchronized (data) {
349            data.setPos(offset);
350            long key = data.readVarLong();
351            if (onlyPosition) {
352                if (needData) {
353                    return tableData.getRow(null, key);
354                }
355                SearchRow row = table.getTemplateSimpleRow(true);
356                row.setKey(key);
357                return row;
358            }
359            SearchRow row = table.getTemplateSimpleRow(columns.length == 1);
360            row.setKey(key);
361            for (Column col : columns) {
362                int idx = col.getColumnId();
363                row.setValue(idx, data.readValue());
364            }
365            return row;
366        }
367    }
368 
369    /**
370     * Get the complete row from the data index.
371     *
372     * @param key the key
373     * @return the row
374     */
375    SearchRow readRow(long key) {
376        return tableData.getRow(null, key);
377    }
378 
379    /**
380     * Write a row to the data page at the given offset.
381     *
382     * @param data the data
383     * @param offset the offset
384     * @param onlyPosition whether only the position of the row is stored
385     * @param row the row to write
386     */
387    void writeRow(Data data, int offset, SearchRow row, boolean onlyPosition) {
388        data.setPos(offset);
389        data.writeVarLong(row.getKey());
390        if (!onlyPosition) {
391            for (Column col : columns) {
392                int idx = col.getColumnId();
393                data.writeValue(row.getValue(idx));
394            }
395        }
396    }
397 
398    /**
399     * Get the size of a row (only the part that is stored in the index).
400     *
401     * @param dummy a dummy data page to calculate the size
402     * @param row the row
403     * @param onlyPosition whether only the position of the row is stored
404     * @return the number of bytes
405     */
406    int getRowSize(Data dummy, SearchRow row, boolean onlyPosition) {
407        int rowsize = Data.getVarLongLen(row.getKey());
408        if (!onlyPosition) {
409            for (Column col : columns) {
410                Value v = row.getValue(col.getColumnId());
411                rowsize += dummy.getValueLen(v);
412            }
413        }
414        return rowsize;
415    }
416 
417    @Override
418    public boolean canFindNext() {
419        return true;
420    }
421 
422    /**
423     * The root page has changed.
424     *
425     * @param session the session
426     * @param newPos the new position
427     */
428    void setRootPageId(Session session, int newPos) {
429        store.removeMeta(this, session);
430        this.rootPageId = newPos;
431        store.addMeta(this, session);
432        store.addIndex(this);
433    }
434 
435    private void invalidateRowCount() {
436        PageBtree root = getPage(rootPageId);
437        root.setRowCountStored(PageData.UNKNOWN_ROWCOUNT);
438    }
439 
440    @Override
441    public void writeRowCount() {
442        if (SysProperties.MODIFY_ON_WRITE && rootPageId == 0) {
443            // currently creating the index
444            return;
445        }
446        PageBtree root = getPage(rootPageId);
447        root.setRowCountStored(MathUtils.convertLongToInt(rowCount));
448    }
449 
450    /**
451     * Check whether the given row contains data.
452     *
453     * @param row the row
454     * @return true if it contains data
455     */
456    boolean hasData(SearchRow row) {
457        return row.getValue(columns[0].getColumnId()) != null;
458    }
459 
460    int getMemoryPerPage() {
461        return memoryPerPage;
462    }
463 
464    /**
465     * The memory usage of a page was changed. The new value is used to adopt
466     * the average estimated memory size of a page.
467     *
468     * @param x the new memory size
469     */
470    void memoryChange(int x) {
471        if (memoryCount < Constants.MEMORY_FACTOR) {
472            memoryPerPage += (x - memoryPerPage) / ++memoryCount;
473        } else {
474            memoryPerPage += (x > memoryPerPage ? 1 : -1) +
475                    ((x - memoryPerPage) / Constants.MEMORY_FACTOR);
476        }
477    }
478 
479    /**
480     * Check if calculating the memory is required.
481     *
482     * @return true if it is
483     */
484    static boolean isMemoryChangeRequired() {
485        if (memoryChangeRequired-- <= 0) {
486            memoryChangeRequired = 10;
487            return true;
488        }
489        return false;
490    }
491 
492}

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