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

COVERAGE SUMMARY FOR SOURCE FILE [PageBtreeLeaf.java]

nameclass, %method, %block, %line, %
PageBtreeLeaf.java100% (1/1)54%  (14/26)31%  (321/1040)39%  (79.7/205)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class PageBtreeLeaf100% (1/1)54%  (14/26)31%  (321/1040)39%  (79.7/205)
addRow (SearchRow, boolean): int 0%   (0/1)0%   (0/287)0%   (0/44)
addRowTry (SearchRow): int 0%   (0/1)0%   (0/9)0%   (0/3)
freeRecursive (): void 0%   (0/1)0%   (0/14)0%   (0/3)
getFirstLeaf (): PageBtreeLeaf 0%   (0/1)0%   (0/2)0%   (0/1)
getLastLeaf (): PageBtreeLeaf 0%   (0/1)0%   (0/2)0%   (0/1)
last (PageBtreeCursor): void 0%   (0/1)0%   (0/8)0%   (0/2)
previousPage (PageBtreeCursor): void 0%   (0/1)0%   (0/21)0%   (0/6)
remapChildren (): void 0%   (0/1)0%   (0/1)0%   (0/1)
remove (SearchRow): SearchRow 0%   (0/1)0%   (0/73)0%   (0/13)
removeRow (int): void 0%   (0/1)0%   (0/124)0%   (0/21)
split (int): PageBtree 0%   (0/1)0%   (0/35)0%   (0/8)
toString (): String 0%   (0/1)0%   (0/21)0%   (0/1)
nextPage (PageBtreeCursor): void 100% (1/1)38%  (8/21)50%  (3/6)
find (PageBtreeCursor, SearchRow, boolean): void 100% (1/1)48%  (16/33)44%  (4/9)
writeData (): void 100% (1/1)50%  (32/64)59%  (8.2/14)
read (): void 100% (1/1)66%  (65/98)86%  (14.6/17)
memoryChange (): void 100% (1/1)70%  (33/47)71%  (7.9/11)
moveTo (Session, int): void 100% (1/1)85%  (63/74)89%  (16/18)
writeHead (): void 100% (1/1)94%  (34/36)99%  (6.9/7)
PageBtreeLeaf (PageBtreeIndex, int, Data): void 100% (1/1)100% (12/12)100% (3/3)
create (PageBtreeIndex, int, int): PageBtreeLeaf 100% (1/1)100% (29/29)100% (7/7)
getEntryCount (): int 100% (1/1)100% (3/3)100% (1/1)
getRowCount (): int 100% (1/1)100% (3/3)100% (1/1)
read (PageBtreeIndex, Data, int): Page 100% (1/1)100% (11/11)100% (3/3)
setRowCountStored (int): void 100% (1/1)100% (1/1)100% (1/1)
write (): void 100% (1/1)100% (11/11)100% (3/3)

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;
9 
10import org.h2.api.ErrorCode;
11import org.h2.engine.Constants;
12import org.h2.engine.Session;
13import org.h2.engine.SysProperties;
14import org.h2.message.DbException;
15import org.h2.result.SearchRow;
16import org.h2.store.Data;
17import org.h2.store.Page;
18import org.h2.store.PageStore;
19 
20/**
21 * A b-tree leaf page that contains index data. Format:
22 * <ul>
23 * <li>page type: byte</li>
24 * <li>checksum: short</li>
25 * <li>parent page id (0 for root): int</li>
26 * <li>index id: varInt</li>
27 * <li>entry count: short</li>
28 * <li>list of offsets: short</li>
29 * <li>data (key: varLong, value,...)</li>
30 * </ul>
31 */
32public class PageBtreeLeaf extends PageBtree {
33 
34    private static final int OFFSET_LENGTH = 2;
35 
36    private final boolean optimizeUpdate;
37    private boolean writtenData;
38 
39    private PageBtreeLeaf(PageBtreeIndex index, int pageId, Data data) {
40        super(index, pageId, data);
41        this.optimizeUpdate = index.getDatabase().getSettings().optimizeUpdate;
42    }
43 
44    /**
45     * Read a b-tree leaf page.
46     *
47     * @param index the index
48     * @param data the data
49     * @param pageId the page id
50     * @return the page
51     */
52    public static Page read(PageBtreeIndex index, Data data, int pageId) {
53        PageBtreeLeaf p = new PageBtreeLeaf(index, pageId, data);
54        p.read();
55        return p;
56    }
57 
58    /**
59     * Create a new page.
60     *
61     * @param index the index
62     * @param pageId the page id
63     * @param parentPageId the parent
64     * @return the page
65     */
66    static PageBtreeLeaf create(PageBtreeIndex index, int pageId,
67            int parentPageId) {
68        PageBtreeLeaf p = new PageBtreeLeaf(index, pageId, index.getPageStore()
69                .createData());
70        index.getPageStore().logUndo(p, null);
71        p.rows = SearchRow.EMPTY_ARRAY;
72        p.parentPageId = parentPageId;
73        p.writeHead();
74        p.start = p.data.length();
75        return p;
76    }
77 
78    private void read() {
79        data.reset();
80        int type = data.readByte();
81        data.readShortInt();
82        this.parentPageId = data.readInt();
83        onlyPosition = (type & Page.FLAG_LAST) == 0;
84        int indexId = data.readVarInt();
85        if (indexId != index.getId()) {
86            throw DbException.get(ErrorCode.FILE_CORRUPTED_1,
87                    "page:" + getPos() + " expected index:" + index.getId() +
88                    "got:" + indexId);
89        }
90        entryCount = data.readShortInt();
91        offsets = new int[entryCount];
92        rows = new SearchRow[entryCount];
93        for (int i = 0; i < entryCount; i++) {
94            offsets[i] = data.readShortInt();
95        }
96        start = data.length();
97        written = true;
98        writtenData = true;
99    }
100 
101    @Override
102    int addRowTry(SearchRow row) {
103        int x = addRow(row, true);
104        memoryChange();
105        return x;
106    }
107 
108    private int addRow(SearchRow row, boolean tryOnly) {
109        int rowLength = index.getRowSize(data, row, onlyPosition);
110        int pageSize = index.getPageStore().getPageSize();
111        int last = entryCount == 0 ? pageSize : offsets[entryCount - 1];
112        if (last - rowLength < start + OFFSET_LENGTH) {
113            if (tryOnly && entryCount > 1) {
114                int x = find(row, false, true, true);
115                if (entryCount < 5) {
116                    // required, otherwise the index doesn't work correctly
117                    return entryCount / 2;
118                }
119                // split near the insertion point to better fill pages
120                // split in half would be:
121                // return entryCount / 2;
122                int third = entryCount / 3;
123                return x < third ? third : x >= 2 * third ? 2 * third : x;
124            }
125            readAllRows();
126            writtenData = false;
127            onlyPosition = true;
128            // change the offsets (now storing only positions)
129            int o = pageSize;
130            for (int i = 0; i < entryCount; i++) {
131                o -= index.getRowSize(data, getRow(i), true);
132                offsets[i] = o;
133            }
134            last = entryCount == 0 ? pageSize : offsets[entryCount - 1];
135            rowLength = index.getRowSize(data, row, true);
136            if (SysProperties.CHECK && last - rowLength < start + OFFSET_LENGTH) {
137                throw DbException.throwInternalError();
138            }
139        }
140        index.getPageStore().logUndo(this, data);
141        if (!optimizeUpdate) {
142            readAllRows();
143        }
144        changeCount = index.getPageStore().getChangeCount();
145        written = false;
146        int x;
147        if (entryCount == 0) {
148            x = 0;
149        } else {
150            x = find(row, false, true, true);
151        }
152        start += OFFSET_LENGTH;
153        int offset = (x == 0 ? pageSize : offsets[x - 1]) - rowLength;
154        if (optimizeUpdate && writtenData) {
155            if (entryCount > 0) {
156                byte[] d = data.getBytes();
157                int dataStart = offsets[entryCount - 1];
158                int dataEnd = offset;
159                System.arraycopy(d, dataStart, d, dataStart - rowLength,
160                        dataEnd - dataStart + rowLength);
161            }
162            index.writeRow(data, offset, row, onlyPosition);
163        }
164        offsets = insert(offsets, entryCount, x, offset);
165        add(offsets, x + 1, entryCount + 1, -rowLength);
166        rows = insert(rows, entryCount, x, row);
167        entryCount++;
168        index.getPageStore().update(this);
169        return -1;
170    }
171 
172    private void removeRow(int at) {
173        if (!optimizeUpdate) {
174            readAllRows();
175        }
176        index.getPageStore().logUndo(this, data);
177        entryCount--;
178        written = false;
179        changeCount = index.getPageStore().getChangeCount();
180        if (entryCount <= 0) {
181            DbException.throwInternalError();
182        }
183        int startNext = at > 0 ? offsets[at - 1] : index.getPageStore().getPageSize();
184        int rowLength = startNext - offsets[at];
185        start -= OFFSET_LENGTH;
186 
187        if (optimizeUpdate) {
188            if (writtenData) {
189                byte[] d = data.getBytes();
190                int dataStart = offsets[entryCount];
191                System.arraycopy(d, dataStart, d,
192                        dataStart + rowLength, offsets[at] - dataStart);
193                Arrays.fill(d, dataStart, dataStart + rowLength, (byte) 0);
194            }
195        }
196 
197        offsets = remove(offsets, entryCount + 1, at);
198        add(offsets, at, entryCount, rowLength);
199        rows = remove(rows, entryCount + 1, at);
200    }
201 
202    int getEntryCount() {
203        return entryCount;
204    }
205 
206    @Override
207    PageBtree split(int splitPoint) {
208        int newPageId = index.getPageStore().allocatePage();
209        PageBtreeLeaf p2 = PageBtreeLeaf.create(index, newPageId, parentPageId);
210        for (int i = splitPoint; i < entryCount;) {
211            p2.addRow(getRow(splitPoint), false);
212            removeRow(splitPoint);
213        }
214        memoryChange();
215        p2.memoryChange();
216        return p2;
217    }
218 
219    @Override
220    PageBtreeLeaf getFirstLeaf() {
221        return this;
222    }
223 
224    @Override
225    PageBtreeLeaf getLastLeaf() {
226        return this;
227    }
228 
229    @Override
230    SearchRow remove(SearchRow row) {
231        int at = find(row, false, false, true);
232        SearchRow delete = getRow(at);
233        if (index.compareRows(row, delete) != 0 || delete.getKey() != row.getKey()) {
234            throw DbException.get(ErrorCode.ROW_NOT_FOUND_WHEN_DELETING_1,
235                    index.getSQL() + ": " + row);
236        }
237        index.getPageStore().logUndo(this, data);
238        if (entryCount == 1) {
239            // the page is now empty
240            return row;
241        }
242        removeRow(at);
243        memoryChange();
244        index.getPageStore().update(this);
245        if (at == entryCount) {
246            // the last row changed
247            return getRow(at - 1);
248        }
249        // the last row didn't change
250        return null;
251    }
252 
253    @Override
254    void freeRecursive() {
255        index.getPageStore().logUndo(this, data);
256        index.getPageStore().free(getPos());
257    }
258 
259    @Override
260    int getRowCount() {
261        return entryCount;
262    }
263 
264    @Override
265    void setRowCountStored(int rowCount) {
266        // ignore
267    }
268 
269    @Override
270    public void write() {
271        writeData();
272        index.getPageStore().writePage(getPos(), data);
273    }
274 
275    private void writeHead() {
276        data.reset();
277        data.writeByte((byte) (Page.TYPE_BTREE_LEAF |
278                (onlyPosition ? 0 : Page.FLAG_LAST)));
279        data.writeShortInt(0);
280        data.writeInt(parentPageId);
281        data.writeVarInt(index.getId());
282        data.writeShortInt(entryCount);
283    }
284 
285    private void writeData() {
286        if (written) {
287            return;
288        }
289        if (!optimizeUpdate) {
290            readAllRows();
291        }
292        writeHead();
293        for (int i = 0; i < entryCount; i++) {
294            data.writeShortInt(offsets[i]);
295        }
296        if (!writtenData || !optimizeUpdate) {
297            for (int i = 0; i < entryCount; i++) {
298                index.writeRow(data, offsets[i], rows[i], onlyPosition);
299            }
300            writtenData = true;
301        }
302        written = true;
303        memoryChange();
304    }
305 
306    @Override
307    void find(PageBtreeCursor cursor, SearchRow first, boolean bigger) {
308        int i = find(first, bigger, false, false);
309        if (i > entryCount) {
310            if (parentPageId == PageBtree.ROOT) {
311                return;
312            }
313            PageBtreeNode next = (PageBtreeNode) index.getPage(parentPageId);
314            next.find(cursor, first, bigger);
315            return;
316        }
317        cursor.setCurrent(this, i);
318    }
319 
320    @Override
321    void last(PageBtreeCursor cursor) {
322        cursor.setCurrent(this, entryCount - 1);
323    }
324 
325    @Override
326    void remapChildren() {
327        // nothing to do
328    }
329 
330    /**
331     * Set the cursor to the first row of the next page.
332     *
333     * @param cursor the cursor
334     */
335    void nextPage(PageBtreeCursor cursor) {
336        if (parentPageId == PageBtree.ROOT) {
337            cursor.setCurrent(null, 0);
338            return;
339        }
340        PageBtreeNode next = (PageBtreeNode) index.getPage(parentPageId);
341        next.nextPage(cursor, getPos());
342    }
343 
344    /**
345     * Set the cursor to the last row of the previous page.
346     *
347     * @param cursor the cursor
348     */
349    void previousPage(PageBtreeCursor cursor) {
350        if (parentPageId == PageBtree.ROOT) {
351            cursor.setCurrent(null, 0);
352            return;
353        }
354        PageBtreeNode next = (PageBtreeNode) index.getPage(parentPageId);
355        next.previousPage(cursor, getPos());
356    }
357 
358    @Override
359    public String toString() {
360        return "page[" + getPos() + "] b-tree leaf table:" +
361                index.getId() + " entries:" + entryCount;
362    }
363 
364    @Override
365    public void moveTo(Session session, int newPos) {
366        PageStore store = index.getPageStore();
367        readAllRows();
368        PageBtreeLeaf p2 = PageBtreeLeaf.create(index, newPos, parentPageId);
369        store.logUndo(this, data);
370        store.logUndo(p2, null);
371        p2.rows = rows;
372        p2.entryCount = entryCount;
373        p2.offsets = offsets;
374        p2.onlyPosition = onlyPosition;
375        p2.parentPageId = parentPageId;
376        p2.start = start;
377        store.update(p2);
378        if (parentPageId == ROOT) {
379            index.setRootPageId(session, newPos);
380        } else {
381            PageBtreeNode p = (PageBtreeNode) store.getPage(parentPageId);
382            p.moveChild(getPos(), newPos);
383        }
384        store.free(getPos());
385    }
386 
387    @Override
388    protected void memoryChange() {
389        if (!PageBtreeIndex.isMemoryChangeRequired()) {
390            return;
391        }
392        int memory = Constants.MEMORY_PAGE_BTREE + index.getPageStore().getPageSize();
393        if (rows != null) {
394            memory += getEntryCount() * (4 + Constants.MEMORY_POINTER);
395            for (int i = 0; i < entryCount; i++) {
396                SearchRow r = rows[i];
397                if (r != null) {
398                    memory += r.getMemory();
399                }
400            }
401        }
402        index.memoryChange(memory >> 2);
403    }
404 
405}

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