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

COVERAGE SUMMARY FOR SOURCE FILE [PageDataLeaf.java]

nameclass, %method, %block, %line, %
PageDataLeaf.java100% (1/1)76%  (25/33)59%  (988/1683)61%  (199.2/327)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class PageDataLeaf100% (1/1)76%  (25/33)59%  (988/1683)61%  (199.2/327)
freeOverflow (): void 0%   (0/1)0%   (0/19)0%   (0/7)
freeRecursive (): void 0%   (0/1)0%   (0/16)0%   (0/4)
getDiskSpaceUsed (): long 0%   (0/1)0%   (0/6)0%   (0/1)
getFirstLeaf (): PageDataLeaf 0%   (0/1)0%   (0/2)0%   (0/1)
isStream (): boolean 0%   (0/1)0%   (0/7)0%   (0/1)
setOverflow (int, int): void 0%   (0/1)0%   (0/53)0%   (0/10)
split (int): PageData 0%   (0/1)0%   (0/43)0%   (0/9)
toString (): String 0%   (0/1)0%   (0/60)0%   (0/1)
remapChildren (int): void 100% (1/1)20%  (4/20)33%  (2/6)
getNextPage (): PageDataLeaf 100% (1/1)22%  (5/23)50%  (2/4)
getRowAt (int): Row 100% (1/1)37%  (41/110)36%  (9/25)
addRowTry (Row): int 100% (1/1)51%  (222/437)44%  (35/80)
remove (long): boolean 100% (1/1)53%  (35/66)70%  (7/10)
findInsertionPoint (long): int 100% (1/1)59%  (17/29)75%  (3/4)
read (): void 100% (1/1)65%  (87/133)83%  (19/23)
moveTo (Session, int): void 100% (1/1)79%  (86/109)85%  (22/26)
removeRow (int): void 100% (1/1)81%  (152/188)74%  (26/35)
readRow (Data, int, int): Row 100% (1/1)85%  (28/33)91%  (6.4/7)
writeData (): void 100% (1/1)87%  (80/92)85%  (17/20)
writeHead (): void 100% (1/1)92%  (47/51)86%  (12/14)
memoryChange (boolean, Row): void 100% (1/1)94%  (33/35)96%  (3.8/4)
PageDataLeaf (PageDataIndex, int, Data): void 100% (1/1)100% (12/12)100% (3/3)
create (PageDataIndex, int, int): PageDataLeaf 100% (1/1)100% (35/35)100% (8/8)
find (Session, long, long, boolean): Cursor 100% (1/1)100% (13/13)100% (2/2)
getEntryCount (): int 100% (1/1)100% (3/3)100% (1/1)
getLastKey (): long 100% (1/1)100% (13/13)100% (3/3)
getRowCount (): int 100% (1/1)100% (3/3)100% (1/1)
getRowLength (Row): int 100% (1/1)100% (21/21)100% (4/4)
getRowWithKey (long): Row 100% (1/1)100% (8/8)100% (2/2)
read (PageDataIndex, Data, int): Page 100% (1/1)100% (11/11)100% (3/3)
readAllRows (): void 100% (1/1)100% (13/13)100% (3/3)
setRowCountStored (int): void 100% (1/1)100% (1/1)100% (1/1)
write (): void 100% (1/1)100% (18/18)100% (4/4)

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.lang.ref.SoftReference;
9import java.util.Arrays;
10 
11import org.h2.api.ErrorCode;
12import org.h2.engine.Constants;
13import org.h2.engine.Session;
14import org.h2.engine.SysProperties;
15import org.h2.message.DbException;
16import org.h2.result.Row;
17import org.h2.store.Data;
18import org.h2.store.Page;
19import org.h2.store.PageStore;
20import org.h2.table.RegularTable;
21import org.h2.value.Value;
22 
23/**
24 * A leaf page that contains data of one or multiple rows. Format:
25 * <ul>
26 * <li>page type: byte (0)</li>
27 * <li>checksum: short (1-2)</li>
28 * <li>parent page id (0 for root): int (3-6)</li>
29 * <li>table id: varInt</li>
30 * <li>column count: varInt</li>
31 * <li>entry count: short</li>
32 * <li>with overflow: the first overflow page id: int</li>
33 * <li>list of key / offset pairs (key: varLong, offset: shortInt)</li>
34 * <li>data</li>
35 * </ul>
36 */
37public class PageDataLeaf extends PageData {
38 
39    private final boolean optimizeUpdate;
40 
41    /**
42     * The row offsets.
43     */
44    private int[] offsets;
45 
46    /**
47     * The rows.
48     */
49    private Row[] rows;
50 
51    /**
52     * For pages with overflow: the soft reference to the row
53     */
54    private SoftReference<Row> rowRef;
55 
56    /**
57     * The page id of the first overflow page (0 if no overflow).
58     */
59    private int firstOverflowPageId;
60 
61    /**
62     * The start of the data area.
63     */
64    private int start;
65 
66    /**
67     * The size of the row in bytes for large rows.
68     */
69    private int overflowRowSize;
70 
71    private int columnCount;
72 
73    private int memoryData;
74 
75    private boolean writtenData;
76 
77    private PageDataLeaf(PageDataIndex index, int pageId, Data data) {
78        super(index, pageId, data);
79        this.optimizeUpdate = index.getDatabase().getSettings().optimizeUpdate;
80    }
81 
82    /**
83     * Create a new page.
84     *
85     * @param index the index
86     * @param pageId the page id
87     * @param parentPageId the parent
88     * @return the page
89     */
90    static PageDataLeaf create(PageDataIndex index, int pageId, int parentPageId) {
91        PageDataLeaf p = new PageDataLeaf(index, pageId, index.getPageStore()
92                .createData());
93        index.getPageStore().logUndo(p, null);
94        p.rows = Row.EMPTY_ARRAY;
95        p.parentPageId = parentPageId;
96        p.columnCount = index.getTable().getColumns().length;
97        p.writeHead();
98        p.start = p.data.length();
99        return p;
100    }
101 
102    /**
103     * Read a data leaf page.
104     *
105     * @param index the index
106     * @param data the data
107     * @param pageId the page id
108     * @return the page
109     */
110    public static Page read(PageDataIndex index, Data data, int pageId) {
111        PageDataLeaf p = new PageDataLeaf(index, pageId, data);
112        p.read();
113        return p;
114    }
115 
116    private void read() {
117        data.reset();
118        int type = data.readByte();
119        data.readShortInt();
120        this.parentPageId = data.readInt();
121        int tableId = data.readVarInt();
122        if (tableId != index.getId()) {
123            throw DbException.get(ErrorCode.FILE_CORRUPTED_1,
124                    "page:" + getPos() + " expected table:" + index.getId() +
125                    " got:" + tableId + " type:" + type);
126        }
127        columnCount = data.readVarInt();
128        entryCount = data.readShortInt();
129        offsets = new int[entryCount];
130        keys = new long[entryCount];
131        rows = new Row[entryCount];
132        if (type == Page.TYPE_DATA_LEAF) {
133            if (entryCount != 1) {
134                DbException.throwInternalError("entries: " + entryCount);
135            }
136            firstOverflowPageId = data.readInt();
137        }
138        for (int i = 0; i < entryCount; i++) {
139            keys[i] = data.readVarLong();
140            offsets[i] = data.readShortInt();
141        }
142        start = data.length();
143        written = true;
144        writtenData = true;
145    }
146 
147    private int getRowLength(Row row) {
148        int size = 0;
149        for (int i = 0; i < columnCount; i++) {
150            size += data.getValueLen(row.getValue(i));
151        }
152        return size;
153    }
154 
155    private int findInsertionPoint(long key) {
156        int x = find(key);
157        if (x < entryCount && keys[x] == key) {
158            throw index.getDuplicateKeyException(""+key);
159        }
160        return x;
161    }
162 
163    @Override
164    int addRowTry(Row row) {
165        index.getPageStore().logUndo(this, data);
166        int rowLength = getRowLength(row);
167        int pageSize = index.getPageStore().getPageSize();
168        int last = entryCount == 0 ? pageSize : offsets[entryCount - 1];
169        int keyOffsetPairLen = 2 + Data.getVarLongLen(row.getKey());
170        if (entryCount > 0 && last - rowLength < start + keyOffsetPairLen) {
171            int x = findInsertionPoint(row.getKey());
172            if (entryCount > 1) {
173                if (entryCount < 5) {
174                    // required, otherwise the index doesn't work correctly
175                    return entryCount / 2;
176                }
177                if (index.isSortedInsertMode()) {
178                    return x < 2 ? 1 : x > entryCount - 1 ? entryCount - 1 : x;
179                }
180                // split near the insertion point to better fill pages
181                // split in half would be:
182                // return entryCount / 2;
183                int third = entryCount / 3;
184                return x < third ? third : x >= 2 * third ? 2 * third : x;
185            }
186            return x;
187        }
188        index.getPageStore().logUndo(this, data);
189        int x;
190        if (entryCount == 0) {
191            x = 0;
192        } else {
193            if (!optimizeUpdate) {
194                readAllRows();
195            }
196            x = findInsertionPoint(row.getKey());
197        }
198        written = false;
199        changeCount = index.getPageStore().getChangeCount();
200        last = x == 0 ? pageSize : offsets[x - 1];
201        int offset = last - rowLength;
202        start += keyOffsetPairLen;
203        offsets = insert(offsets, entryCount, x, offset);
204        add(offsets, x + 1, entryCount + 1, -rowLength);
205        keys = insert(keys, entryCount, x, row.getKey());
206        rows = insert(rows, entryCount, x, row);
207        entryCount++;
208        index.getPageStore().update(this);
209        if (optimizeUpdate) {
210            if (writtenData && offset >= start) {
211                byte[] d = data.getBytes();
212                int dataStart = offsets[entryCount - 1] + rowLength;
213                int dataEnd = offsets[x];
214                System.arraycopy(d, dataStart, d, dataStart - rowLength,
215                        dataEnd - dataStart + rowLength);
216                data.setPos(dataEnd);
217                for (int j = 0; j < columnCount; j++) {
218                    data.writeValue(row.getValue(j));
219                }
220            }
221        }
222        if (offset < start) {
223            writtenData = false;
224            if (entryCount > 1) {
225                DbException.throwInternalError();
226            }
227            // need to write the overflow page id
228            start += 4;
229            int remaining = rowLength - (pageSize - start);
230            // fix offset
231            offset = start;
232            offsets[x] = offset;
233            int previous = getPos();
234            int dataOffset = pageSize;
235            int page = index.getPageStore().allocatePage();
236            firstOverflowPageId = page;
237            this.overflowRowSize = pageSize + rowLength;
238            writeData();
239            // free up the space used by the row
240            Row r = rows[0];
241            rowRef = new SoftReference<Row>(r);
242            rows[0] = null;
243            Data all = index.getPageStore().createData();
244            all.checkCapacity(data.length());
245            all.write(data.getBytes(), 0, data.length());
246            data.truncate(index.getPageStore().getPageSize());
247            do {
248                int type, size, next;
249                if (remaining <= pageSize - PageDataOverflow.START_LAST) {
250                    type = Page.TYPE_DATA_OVERFLOW | Page.FLAG_LAST;
251                    size = remaining;
252                    next = 0;
253                } else {
254                    type = Page.TYPE_DATA_OVERFLOW;
255                    size = pageSize - PageDataOverflow.START_MORE;
256                    next = index.getPageStore().allocatePage();
257                }
258                PageDataOverflow overflow = PageDataOverflow.create(index.getPageStore(),
259                        page, type, previous, next, all, dataOffset, size);
260                index.getPageStore().update(overflow);
261                dataOffset += size;
262                remaining -= size;
263                previous = page;
264                page = next;
265            } while (remaining > 0);
266        }
267        if (rowRef == null) {
268            memoryChange(true, row);
269        } else {
270            memoryChange(true, null);
271        }
272        return -1;
273    }
274 
275    private void removeRow(int i) {
276        index.getPageStore().logUndo(this, data);
277        written = false;
278        changeCount = index.getPageStore().getChangeCount();
279        if (!optimizeUpdate) {
280            readAllRows();
281        }
282        Row r = getRowAt(i);
283        if (r != null) {
284            memoryChange(false, r);
285        }
286        entryCount--;
287        if (entryCount < 0) {
288            DbException.throwInternalError();
289        }
290        if (firstOverflowPageId != 0) {
291            start -= 4;
292            freeOverflow();
293            firstOverflowPageId = 0;
294            overflowRowSize = 0;
295            rowRef = null;
296        }
297        int keyOffsetPairLen = 2 + Data.getVarLongLen(keys[i]);
298        int startNext = i > 0 ? offsets[i - 1] : index.getPageStore().getPageSize();
299        int rowLength = startNext - offsets[i];
300        if (optimizeUpdate) {
301            if (writtenData) {
302                byte[] d = data.getBytes();
303                int dataStart = offsets[entryCount];
304                System.arraycopy(d, dataStart, d, dataStart + rowLength,
305                        offsets[i] - dataStart);
306                Arrays.fill(d, dataStart, dataStart + rowLength, (byte) 0);
307            }
308        } else {
309            int clearStart = offsets[entryCount];
310            Arrays.fill(data.getBytes(), clearStart, clearStart + rowLength, (byte) 0);
311        }
312        start -= keyOffsetPairLen;
313        offsets = remove(offsets, entryCount + 1, i);
314        add(offsets, i, entryCount, rowLength);
315        keys = remove(keys, entryCount + 1, i);
316        rows = remove(rows, entryCount + 1, i);
317    }
318 
319    @Override
320    Cursor find(Session session, long minKey, long maxKey, boolean multiVersion) {
321        int x = find(minKey);
322        return new PageDataCursor(session, this, x, maxKey, multiVersion);
323    }
324 
325    /**
326     * Get the row at the given index.
327     *
328     * @param at the index
329     * @return the row
330     */
331    Row getRowAt(int at) {
332        Row r = rows[at];
333        if (r == null) {
334            if (firstOverflowPageId == 0) {
335                r = readRow(data, offsets[at], columnCount);
336            } else {
337                if (rowRef != null) {
338                    r = rowRef.get();
339                    if (r != null) {
340                        return r;
341                    }
342                }
343                PageStore store = index.getPageStore();
344                Data buff = store.createData();
345                int pageSize = store.getPageSize();
346                int offset = offsets[at];
347                buff.write(data.getBytes(), offset, pageSize - offset);
348                int next = firstOverflowPageId;
349                do {
350                    PageDataOverflow page = index.getPageOverflow(next);
351                    next = page.readInto(buff);
352                } while (next != 0);
353                overflowRowSize = pageSize + buff.length();
354                r = readRow(buff, 0, columnCount);
355            }
356            r.setKey(keys[at]);
357            if (firstOverflowPageId != 0) {
358                rowRef = new SoftReference<Row>(r);
359            } else {
360                rows[at] = r;
361                memoryChange(true, r);
362            }
363        }
364        return r;
365    }
366 
367    int getEntryCount() {
368        return entryCount;
369    }
370 
371    @Override
372    PageData split(int splitPoint) {
373        int newPageId = index.getPageStore().allocatePage();
374        PageDataLeaf p2 = PageDataLeaf.create(index, newPageId, parentPageId);
375        for (int i = splitPoint; i < entryCount;) {
376            int split = p2.addRowTry(getRowAt(splitPoint));
377            if (split != -1) {
378                DbException.throwInternalError("split " + split);
379            }
380            removeRow(splitPoint);
381        }
382        return p2;
383    }
384 
385    @Override
386    long getLastKey() {
387        // TODO re-use keys, but remove this mechanism
388        if (entryCount == 0) {
389            return 0;
390        }
391        return getRowAt(entryCount - 1).getKey();
392    }
393 
394    PageDataLeaf getNextPage() {
395        if (parentPageId == PageData.ROOT) {
396            return null;
397        }
398        PageDataNode next = (PageDataNode) index.getPage(parentPageId, -1);
399        return next.getNextPage(keys[entryCount - 1]);
400    }
401 
402    @Override
403    PageDataLeaf getFirstLeaf() {
404        return this;
405    }
406 
407    @Override
408    protected void remapChildren(int old) {
409        if (firstOverflowPageId == 0) {
410            return;
411        }
412        PageDataOverflow overflow = index.getPageOverflow(firstOverflowPageId);
413        overflow.setParentPageId(getPos());
414        index.getPageStore().update(overflow);
415    }
416 
417    @Override
418    boolean remove(long key) {
419        int i = find(key);
420        if (keys == null || keys[i] != key) {
421            throw DbException.get(ErrorCode.ROW_NOT_FOUND_WHEN_DELETING_1,
422                    index.getSQL() + ": " + key + " " + (keys == null ? -1 : keys[i]));
423        }
424        index.getPageStore().logUndo(this, data);
425        if (entryCount == 1) {
426            freeRecursive();
427            return true;
428        }
429        removeRow(i);
430        index.getPageStore().update(this);
431        return false;
432    }
433 
434    @Override
435    void freeRecursive() {
436        index.getPageStore().logUndo(this, data);
437        index.getPageStore().free(getPos());
438        freeOverflow();
439    }
440 
441    private void freeOverflow() {
442        if (firstOverflowPageId != 0) {
443            int next = firstOverflowPageId;
444            do {
445                PageDataOverflow page = index.getPageOverflow(next);
446                page.free();
447                next = page.getNextOverflow();
448            } while (next != 0);
449        }
450    }
451 
452    @Override
453    Row getRowWithKey(long key) {
454        int at = find(key);
455        return getRowAt(at);
456    }
457 
458    @Override
459    int getRowCount() {
460        return entryCount;
461    }
462 
463    @Override
464    void setRowCountStored(int rowCount) {
465        // ignore
466    }
467 
468    @Override
469    long getDiskSpaceUsed() {
470        return index.getPageStore().getPageSize();
471    }
472 
473    @Override
474    public void write() {
475        writeData();
476        index.getPageStore().writePage(getPos(), data);
477        data.truncate(index.getPageStore().getPageSize());
478    }
479 
480    private void readAllRows() {
481        for (int i = 0; i < entryCount; i++) {
482            getRowAt(i);
483        }
484    }
485 
486    private void writeHead() {
487        data.reset();
488        int type;
489        if (firstOverflowPageId == 0) {
490            type = Page.TYPE_DATA_LEAF | Page.FLAG_LAST;
491        } else {
492            type = Page.TYPE_DATA_LEAF;
493        }
494        data.writeByte((byte) type);
495        data.writeShortInt(0);
496        if (SysProperties.CHECK2) {
497            if (data.length() != START_PARENT) {
498                DbException.throwInternalError();
499            }
500        }
501        data.writeInt(parentPageId);
502        data.writeVarInt(index.getId());
503        data.writeVarInt(columnCount);
504        data.writeShortInt(entryCount);
505    }
506 
507    private void writeData() {
508        if (written) {
509            return;
510        }
511        if (!optimizeUpdate) {
512            readAllRows();
513        }
514        writeHead();
515        if (firstOverflowPageId != 0) {
516            data.writeInt(firstOverflowPageId);
517            data.checkCapacity(overflowRowSize);
518        }
519        for (int i = 0; i < entryCount; i++) {
520            data.writeVarLong(keys[i]);
521            data.writeShortInt(offsets[i]);
522        }
523        if (!writtenData || !optimizeUpdate) {
524            for (int i = 0; i < entryCount; i++) {
525                data.setPos(offsets[i]);
526                Row r = getRowAt(i);
527                for (int j = 0; j < columnCount; j++) {
528                    data.writeValue(r.getValue(j));
529                }
530            }
531            writtenData = true;
532        }
533        written = true;
534    }
535 
536    @Override
537    public String toString() {
538        return "page[" + getPos() + "] data leaf table:" +
539            index.getId() + " " + index.getTable().getName() +
540            " entries:" + entryCount + " parent:" + parentPageId +
541            (firstOverflowPageId == 0 ? "" : " overflow:" + firstOverflowPageId) +
542            " keys:" + Arrays.toString(keys) + " offsets:" + Arrays.toString(offsets);
543    }
544 
545    @Override
546    public void moveTo(Session session, int newPos) {
547        PageStore store = index.getPageStore();
548        // load the pages into the cache, to ensure old pages
549        // are written
550        if (parentPageId != ROOT) {
551            store.getPage(parentPageId);
552        }
553        store.logUndo(this, data);
554        PageDataLeaf p2 = PageDataLeaf.create(index, newPos, parentPageId);
555        readAllRows();
556        p2.keys = keys;
557        p2.overflowRowSize = overflowRowSize;
558        p2.firstOverflowPageId = firstOverflowPageId;
559        p2.rowRef = rowRef;
560        p2.rows = rows;
561        if (firstOverflowPageId != 0) {
562            p2.rows[0] = getRowAt(0);
563        }
564        p2.entryCount = entryCount;
565        p2.offsets = offsets;
566        p2.start = start;
567        p2.remapChildren(getPos());
568        p2.writeData();
569        p2.data.truncate(index.getPageStore().getPageSize());
570        store.update(p2);
571        if (parentPageId == ROOT) {
572            index.setRootPageId(session, newPos);
573        } else {
574            PageDataNode p = (PageDataNode) store.getPage(parentPageId);
575            p.moveChild(getPos(), newPos);
576        }
577        store.free(getPos());
578    }
579 
580    /**
581     * Set the overflow page id.
582     *
583     * @param old the old overflow page id
584     * @param overflow the new overflow page id
585     */
586    void setOverflow(int old, int overflow) {
587        if (SysProperties.CHECK && old != firstOverflowPageId) {
588            DbException.throwInternalError("move " + this + " " + firstOverflowPageId);
589        }
590        index.getPageStore().logUndo(this, data);
591        firstOverflowPageId = overflow;
592        if (written) {
593            changeCount = index.getPageStore().getChangeCount();
594            writeHead();
595            data.writeInt(firstOverflowPageId);
596        }
597        index.getPageStore().update(this);
598    }
599 
600    private void memoryChange(boolean add, Row r) {
601        int diff = r == null ? 0 : 4 + 8 + Constants.MEMORY_POINTER + r.getMemory();
602        memoryData += add ? diff : -diff;
603        index.memoryChange((Constants.MEMORY_PAGE_DATA +
604                memoryData + index.getPageStore().getPageSize()) >> 2);
605    }
606 
607    @Override
608    public boolean isStream() {
609        return firstOverflowPageId > 0;
610    }
611 
612    /**
613     * Read a row from the data page at the given position.
614     *
615     * @param data the data page
616     * @param pos the position to read from
617     * @param columnCount the number of columns
618     * @return the row
619     */
620    private static Row readRow(Data data, int pos, int columnCount) {
621        Value[] values = new Value[columnCount];
622        synchronized (data) {
623            data.setPos(pos);
624            for (int i = 0; i < columnCount; i++) {
625                values[i] = data.readValue();
626            }
627        }
628        return RegularTable.createRow(values);
629    }
630 
631}

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