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

COVERAGE SUMMARY FOR SOURCE FILE [PageDataNode.java]

nameclass, %method, %block, %line, %
PageDataNode.java100% (1/1)0%   (0/28)0%   (0/1262)0%   (0/235)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class PageDataNode100% (1/1)0%   (0/28)0%   (0/1262)0%   (0/235)
PageDataNode (PageDataIndex, int, Data): void 0%   (0/1)0%   (0/12)0%   (0/4)
addChild (int, int, long): void 0%   (0/1)0%   (0/54)0%   (0/8)
addRowTry (Row): int 0%   (0/1)0%   (0/92)0%   (0/18)
check (): void 0%   (0/1)0%   (0/22)0%   (0/6)
create (PageDataIndex, int, int): PageDataNode 0%   (0/1)0%   (0/28)0%   (0/6)
find (Session, long, long, boolean): Cursor 0%   (0/1)0%   (0/21)0%   (0/3)
freeRecursive (): void 0%   (0/1)0%   (0/36)0%   (0/6)
getDiskSpaceUsed (): long 0%   (0/1)0%   (0/71)0%   (0/9)
getFirstLeaf (): PageDataLeaf 0%   (0/1)0%   (0/13)0%   (0/2)
getLastKey (): long 0%   (0/1)0%   (0/12)0%   (0/1)
getNextPage (long): PageDataLeaf 0%   (0/1)0%   (0/40)0%   (0/8)
getRowCount (): int 0%   (0/1)0%   (0/76)0%   (0/11)
getRowWithKey (long): Row 0%   (0/1)0%   (0/18)0%   (0/3)
init (PageData, long, PageData): void 0%   (0/1)0%   (0/37)0%   (0/6)
moveChild (int, int): void 0%   (0/1)0%   (0/45)0%   (0/9)
moveTo (Session, int): void 0%   (0/1)0%   (0/121)0%   (0/26)
read (): void 0%   (0/1)0%   (0/113)0%   (0/19)
read (PageDataIndex, Data, int): Page 0%   (0/1)0%   (0/11)0%   (0/3)
remapChildren (int): void 0%   (0/1)0%   (0/31)0%   (0/6)
remove (long): boolean 0%   (0/1)0%   (0/54)0%   (0/13)
removeChild (int): void 0%   (0/1)0%   (0/70)0%   (0/11)
setRowCountStored (int): void 0%   (0/1)0%   (0/34)0%   (0/9)
split (int): PageData 0%   (0/1)0%   (0/71)0%   (0/12)
toString (): String 0%   (0/1)0%   (0/27)0%   (0/1)
updateRowCount (int): void 0%   (0/1)0%   (0/35)0%   (0/9)
write (): void 0%   (0/1)0%   (0/11)0%   (0/3)
writeData (): void 0%   (0/1)0%   (0/65)0%   (0/12)
writeHead (): void 0%   (0/1)0%   (0/42)0%   (0/11)

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 java.util.Arrays;
9import org.h2.api.DatabaseEventListener;
10import org.h2.api.ErrorCode;
11import org.h2.engine.Session;
12import org.h2.engine.SysProperties;
13import org.h2.message.DbException;
14import org.h2.result.Row;
15import org.h2.store.Data;
16import org.h2.store.Page;
17import org.h2.store.PageStore;
18import org.h2.util.Utils;
19 
20/**
21 * A leaf page that contains data of one or multiple rows. Format:
22 * <ul>
23 * <li>page type: byte (0)</li>
24 * <li>checksum: short (1-2)</li>
25 * <li>parent page id (0 for root): int (3-6)</li>
26 * <li>table id: varInt</li>
27 * <li>count of all children (-1 if not known): int</li>
28 * <li>entry count: short</li>
29 * <li>rightmost child page id: int</li>
30 * <li>entries (child page id: int, key: varLong)</li>
31 * </ul>
32 * The key is the largest key of the respective child, meaning key[0] is the
33 * largest key of child[0].
34 */
35public class PageDataNode extends PageData {
36 
37    /**
38     * The page ids of the children.
39     */
40    private int[] childPageIds;
41 
42    private int rowCountStored = UNKNOWN_ROWCOUNT;
43 
44    private int rowCount = UNKNOWN_ROWCOUNT;
45 
46    /**
47     * The number of bytes used in the page
48     */
49    private int length;
50 
51    private PageDataNode(PageDataIndex index, int pageId, Data data) {
52        super(index, pageId, data);
53    }
54 
55    /**
56     * Create a new page.
57     *
58     * @param index the index
59     * @param pageId the page id
60     * @param parentPageId the parent
61     * @return the page
62     */
63    static PageDataNode create(PageDataIndex index, int pageId, int parentPageId) {
64        PageDataNode p = new PageDataNode(index, pageId,
65                index.getPageStore().createData());
66        index.getPageStore().logUndo(p, null);
67        p.parentPageId = parentPageId;
68        p.writeHead();
69        // 4 bytes for the rightmost child page id
70        p.length = p.data.length() + 4;
71        return p;
72    }
73 
74    /**
75     * Read a data node page.
76     *
77     * @param index the index
78     * @param data the data
79     * @param pageId the page id
80     * @return the page
81     */
82    public static Page read(PageDataIndex index, Data data, int pageId) {
83        PageDataNode p = new PageDataNode(index, pageId, data);
84        p.read();
85        return p;
86    }
87 
88    private void read() {
89        data.reset();
90        data.readByte();
91        data.readShortInt();
92        this.parentPageId = data.readInt();
93        int indexId = data.readVarInt();
94        if (indexId != index.getId()) {
95            throw DbException.get(ErrorCode.FILE_CORRUPTED_1,
96                    "page:" + getPos() + " expected index:" + index.getId() +
97                    "got:" + indexId);
98        }
99        rowCount = rowCountStored = data.readInt();
100        entryCount = data.readShortInt();
101        childPageIds = new int[entryCount + 1];
102        childPageIds[entryCount] = data.readInt();
103        keys = Utils.newLongArray(entryCount);
104        for (int i = 0; i < entryCount; i++) {
105            childPageIds[i] = data.readInt();
106            keys[i] = data.readVarLong();
107        }
108        length = data.length();
109        check();
110        written = true;
111    }
112 
113    private void addChild(int x, int childPageId, long key) {
114        index.getPageStore().logUndo(this, data);
115        written = false;
116        changeCount = index.getPageStore().getChangeCount();
117        childPageIds = insert(childPageIds, entryCount + 1, x + 1, childPageId);
118        keys = insert(keys, entryCount, x, key);
119        entryCount++;
120        length += 4 + Data.getVarLongLen(key);
121    }
122 
123    @Override
124    int addRowTry(Row row) {
125        index.getPageStore().logUndo(this, data);
126        int keyOffsetPairLen = 4 + Data.getVarLongLen(row.getKey());
127        while (true) {
128            int x = find(row.getKey());
129            PageData page = index.getPage(childPageIds[x], getPos());
130            int splitPoint = page.addRowTry(row);
131            if (splitPoint == -1) {
132                break;
133            }
134            if (length + keyOffsetPairLen > index.getPageStore().getPageSize()) {
135                return entryCount / 2;
136            }
137            long pivot = splitPoint == 0 ? row.getKey() : page.getKey(splitPoint - 1);
138            PageData page2 = page.split(splitPoint);
139            index.getPageStore().update(page);
140            index.getPageStore().update(page2);
141            addChild(x, page2.getPos(), pivot);
142            index.getPageStore().update(this);
143        }
144        updateRowCount(1);
145        return -1;
146    }
147 
148    private void updateRowCount(int offset) {
149        if (rowCount != UNKNOWN_ROWCOUNT) {
150            rowCount += offset;
151        }
152        if (rowCountStored != UNKNOWN_ROWCOUNT) {
153            rowCountStored = UNKNOWN_ROWCOUNT;
154            index.getPageStore().logUndo(this, data);
155            if (written) {
156                writeHead();
157            }
158            index.getPageStore().update(this);
159        }
160    }
161 
162    @Override
163    Cursor find(Session session, long minKey, long maxKey, boolean multiVersion) {
164        int x = find(minKey);
165        int child = childPageIds[x];
166        return index.getPage(child, getPos()).find(session, minKey, maxKey,
167                multiVersion);
168    }
169 
170    @Override
171    PageData split(int splitPoint) {
172        int newPageId = index.getPageStore().allocatePage();
173        PageDataNode p2 = PageDataNode.create(index, newPageId, parentPageId);
174        int firstChild = childPageIds[splitPoint];
175        for (int i = splitPoint; i < entryCount;) {
176            p2.addChild(p2.entryCount, childPageIds[splitPoint + 1], keys[splitPoint]);
177            removeChild(splitPoint);
178        }
179        int lastChild = childPageIds[splitPoint - 1];
180        removeChild(splitPoint - 1);
181        childPageIds[splitPoint - 1] = lastChild;
182        p2.childPageIds[0] = firstChild;
183        p2.remapChildren(getPos());
184        return p2;
185    }
186 
187    @Override
188    protected void remapChildren(int old) {
189        for (int i = 0; i < entryCount + 1; i++) {
190            int child = childPageIds[i];
191            PageData p = index.getPage(child, old);
192            p.setParentPageId(getPos());
193            index.getPageStore().update(p);
194        }
195    }
196 
197    /**
198     * Initialize the page.
199     *
200     * @param page1 the first child page
201     * @param pivot the pivot key
202     * @param page2 the last child page
203     */
204    void init(PageData page1, long pivot, PageData page2) {
205        entryCount = 1;
206        childPageIds = new int[] { page1.getPos(), page2.getPos() };
207        keys = new long[] { pivot };
208        length += 4 + Data.getVarLongLen(pivot);
209        check();
210    }
211 
212    @Override
213    long getLastKey() {
214        return index.getPage(childPageIds[entryCount], getPos()).getLastKey();
215    }
216 
217    /**
218     * Get the next leaf page.
219     *
220     * @param key the last key of the current page
221     * @return the next leaf page
222     */
223    PageDataLeaf getNextPage(long key) {
224        int i = find(key) + 1;
225        if (i > entryCount) {
226            if (parentPageId == PageData.ROOT) {
227                return null;
228            }
229            PageDataNode next = (PageDataNode) index.getPage(parentPageId, -1);
230            return next.getNextPage(key);
231        }
232        PageData page = index.getPage(childPageIds[i], getPos());
233        return page.getFirstLeaf();
234    }
235 
236    @Override
237    PageDataLeaf getFirstLeaf() {
238        int child = childPageIds[0];
239        return index.getPage(child, getPos()).getFirstLeaf();
240    }
241 
242    @Override
243    boolean remove(long key) {
244        int at = find(key);
245        // merge is not implemented to allow concurrent usage
246        // TODO maybe implement merge
247        PageData page = index.getPage(childPageIds[at], getPos());
248        boolean empty = page.remove(key);
249        index.getPageStore().logUndo(this, data);
250        updateRowCount(-1);
251        if (!empty) {
252            // the first row didn't change - nothing to do
253            return false;
254        }
255        // this child is now empty
256        index.getPageStore().free(page.getPos());
257        if (entryCount < 1) {
258            // no more children - this page is empty as well
259            return true;
260        }
261        removeChild(at);
262        index.getPageStore().update(this);
263        return false;
264    }
265 
266    @Override
267    void freeRecursive() {
268        index.getPageStore().logUndo(this, data);
269        index.getPageStore().free(getPos());
270        for (int i = 0; i < entryCount + 1; i++) {
271            int child = childPageIds[i];
272            index.getPage(child, getPos()).freeRecursive();
273        }
274    }
275 
276    @Override
277    Row getRowWithKey(long key) {
278        int at = find(key);
279        PageData page = index.getPage(childPageIds[at], getPos());
280        return page.getRowWithKey(key);
281    }
282 
283    @Override
284    int getRowCount() {
285        if (rowCount == UNKNOWN_ROWCOUNT) {
286            int count = 0;
287            for (int i = 0; i < entryCount + 1; i++) {
288                int child = childPageIds[i];
289                PageData page = index.getPage(child, getPos());
290                if (getPos() == page.getPos()) {
291                    throw DbException.throwInternalError("Page is its own child: " + getPos());
292                }
293                count += page.getRowCount();
294                index.getDatabase().setProgress(DatabaseEventListener.STATE_SCAN_FILE,
295                        index.getTable() + "." + index.getName(), count, Integer.MAX_VALUE);
296            }
297            rowCount = count;
298        }
299        return rowCount;
300    }
301 
302    @Override
303    long getDiskSpaceUsed() {
304        long count = 0;
305        for (int i = 0; i < entryCount + 1; i++) {
306            int child = childPageIds[i];
307            PageData page = index.getPage(child, getPos());
308            if (getPos() == page.getPos()) {
309                throw DbException.throwInternalError("Page is its own child: " + getPos());
310            }
311            count += page.getDiskSpaceUsed();
312            index.getDatabase().setProgress(DatabaseEventListener.STATE_SCAN_FILE,
313                    index.getTable() + "." + index.getName(),
314                    (int) (count >> 16), Integer.MAX_VALUE);
315        }
316        return count;
317    }
318 
319    @Override
320    void setRowCountStored(int rowCount) {
321        this.rowCount = rowCount;
322        if (rowCountStored != rowCount) {
323            rowCountStored = rowCount;
324            index.getPageStore().logUndo(this, data);
325            if (written) {
326                changeCount = index.getPageStore().getChangeCount();
327                writeHead();
328            }
329            index.getPageStore().update(this);
330        }
331    }
332 
333    private void check() {
334        if (SysProperties.CHECK) {
335            for (int i = 0; i < entryCount + 1; i++) {
336                int child = childPageIds[i];
337                if (child == 0) {
338                    DbException.throwInternalError();
339                }
340            }
341        }
342    }
343 
344    @Override
345    public void write() {
346        writeData();
347        index.getPageStore().writePage(getPos(), data);
348    }
349 
350    private void writeHead() {
351        data.reset();
352        data.writeByte((byte) Page.TYPE_DATA_NODE);
353        data.writeShortInt(0);
354        if (SysProperties.CHECK2) {
355            if (data.length() != START_PARENT) {
356                DbException.throwInternalError();
357            }
358        }
359        data.writeInt(parentPageId);
360        data.writeVarInt(index.getId());
361        data.writeInt(rowCountStored);
362        data.writeShortInt(entryCount);
363    }
364 
365    private void writeData() {
366        if (written) {
367            return;
368        }
369        check();
370        writeHead();
371        data.writeInt(childPageIds[entryCount]);
372        for (int i = 0; i < entryCount; i++) {
373            data.writeInt(childPageIds[i]);
374            data.writeVarLong(keys[i]);
375        }
376        if (length != data.length()) {
377            DbException.throwInternalError("expected pos: " + length +
378                    " got: " + data.length());
379        }
380        written = true;
381    }
382 
383    private void removeChild(int i) {
384        index.getPageStore().logUndo(this, data);
385        written = false;
386        changeCount = index.getPageStore().getChangeCount();
387        int removedKeyIndex = i < entryCount ? i : i - 1;
388        entryCount--;
389        length -= 4 + Data.getVarLongLen(keys[removedKeyIndex]);
390        if (entryCount < 0) {
391            DbException.throwInternalError();
392        }
393        keys = remove(keys, entryCount + 1, removedKeyIndex);
394        childPageIds = remove(childPageIds, entryCount + 2, i);
395    }
396 
397    @Override
398    public String toString() {
399        return "page[" + getPos() + "] data node table:" + index.getId() +
400            " entries:" + entryCount + " " + Arrays.toString(childPageIds);
401    }
402 
403    @Override
404    public void moveTo(Session session, int newPos) {
405        PageStore store = index.getPageStore();
406        // load the pages into the cache, to ensure old pages
407        // are written
408        for (int i = 0; i < entryCount + 1; i++) {
409            int child = childPageIds[i];
410            store.getPage(child);
411        }
412        if (parentPageId != ROOT) {
413            store.getPage(parentPageId);
414        }
415        store.logUndo(this, data);
416        PageDataNode p2 = PageDataNode.create(index, newPos, parentPageId);
417        p2.rowCountStored = rowCountStored;
418        p2.rowCount = rowCount;
419        p2.childPageIds = childPageIds;
420        p2.keys = keys;
421        p2.entryCount = entryCount;
422        p2.length = length;
423        store.update(p2);
424        if (parentPageId == ROOT) {
425            index.setRootPageId(session, newPos);
426        } else {
427            PageDataNode p = (PageDataNode) store.getPage(parentPageId);
428            p.moveChild(getPos(), newPos);
429        }
430        for (int i = 0; i < entryCount + 1; i++) {
431            int child = childPageIds[i];
432            PageData p = (PageData) store.getPage(child);
433            p.setParentPageId(newPos);
434            store.update(p);
435        }
436        store.free(getPos());
437    }
438 
439    /**
440     * One of the children has moved to another page.
441     *
442     * @param oldPos the old position
443     * @param newPos the new position
444     */
445    void moveChild(int oldPos, int newPos) {
446        for (int i = 0; i < entryCount + 1; i++) {
447            if (childPageIds[i] == oldPos) {
448                index.getPageStore().logUndo(this, data);
449                written = false;
450                changeCount = index.getPageStore().getChangeCount();
451                childPageIds[i] = newPos;
452                index.getPageStore().update(this);
453                return;
454            }
455        }
456        throw DbException.throwInternalError();
457    }
458 
459}

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