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

COVERAGE SUMMARY FOR SOURCE FILE [Page.java]

nameclass, %method, %block, %line, %
Page.java100% (3/3)92%  (47/51)83%  (1916/2316)90%  (407.8/452)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class Page$PageChildren100% (1/1)88%  (7/8)64%  (228/354)84%  (56.9/68)
collectReferencedChunks (Set): void 0%   (0/1)0%   (0/31)0%   (0/4)
read (FileStore, long, int, long, long): Page$PageChildren 100% (1/1)52%  (105/200)78%  (24.9/32)
<static initializer> 100% (1/1)100% (4/4)100% (1/1)
Page$PageChildren (Page): void 100% (1/1)100% (28/28)100% (7/7)
Page$PageChildren (long, long []): void 100% (1/1)100% (9/9)100% (4/4)
getMemory (): int 100% (1/1)100% (8/8)100% (1/1)
removeChild (int): void 100% (1/1)100% (30/30)100% (7/7)
removeDuplicateChunkReferences (): void 100% (1/1)100% (44/44)100% (12/12)
     
class Page100% (1/1)93%  (39/42)86%  (1676/1950)91%  (345.8/379)
equals (Object): boolean 0%   (0/1)0%   (0/31)0%   (0/7)
hashCode (): int 0%   (0/1)0%   (0/17)0%   (0/1)
toString (): String 0%   (0/1)0%   (0/117)0%   (0/18)
read (FileStore, long, MVMap, long, long): Page 100% (1/1)61%  (46/75)80%  (12/15)
read (ByteBuffer, int, int, int): void 100% (1/1)76%  (205/270)93%  (43/46)
setChild (int, Page): void 100% (1/1)90%  (82/91)99%  (12.8/13)
write (Chunk, WriteBuffer): int 100% (1/1)98%  (265/271)98%  (49/50)
<static initializer> 100% (1/1)100% (4/4)100% (1/1)
Page (MVMap, long): void 100% (1/1)100% (9/9)100% (4/4)
addMemory (int): void 100% (1/1)100% (7/7)100% (2/2)
binarySearch (Object): int 100% (1/1)100% (72/72)100% (17/17)
copy (long): Page 100% (1/1)100% (23/23)100% (4/4)
create (MVMap, long, Object [], Object [], Page$PageReference [], long, int):... 100% (1/1)100% (37/37)100% (12/12)
create (MVMap, long, Page): Page 100% (1/1)100% (37/37)100% (10/10)
createEmpty (MVMap, long): Page 100% (1/1)100% (9/9)100% (1/1)
getChildPage (int): Page 100% (1/1)100% (17/17)100% (2/2)
getChildPagePos (int): long 100% (1/1)100% (6/6)100% (1/1)
getCounts (int): long 100% (1/1)100% (6/6)100% (1/1)
getKey (int): Object 100% (1/1)100% (5/5)100% (1/1)
getKeyCount (): int 100% (1/1)100% (4/4)100% (1/1)
getMemory (): int 100% (1/1)100% (3/3)100% (1/1)
getPos (): long 100% (1/1)100% (3/3)100% (1/1)
getRawChildPageCount (): int 100% (1/1)100% (4/4)100% (1/1)
getTotalCount (): long 100% (1/1)100% (3/3)100% (1/1)
getValue (int): Object 100% (1/1)100% (5/5)100% (1/1)
getVersion (): long 100% (1/1)100% (3/3)100% (1/1)
insertLeaf (int, Object, Object): void 100% (1/1)100% (64/64)100% (12/12)
insertNode (int, Object, Page): void 100% (1/1)100% (68/68)100% (12/12)
isLeaf (): boolean 100% (1/1)100% (7/7)100% (1/1)
recalculateMemory (): void 100% (1/1)100% (64/64)100% (12/12)
remove (int): void 100% (1/1)100% (113/113)100% (23/23)
removeAllRecursive (): void 100% (1/1)100% (55/55)100% (14/14)
removePage (): void 100% (1/1)100% (17/17)100% (5/5)
setKey (int, Object): void 100% (1/1)100% (38/38)100% (9/9)
setValue (int, Object): Object 100% (1/1)100% (33/33)100% (6/6)
setVersion (long): void 100% (1/1)100% (4/4)100% (2/2)
split (int): Page 100% (1/1)100% (11/11)100% (1/1)
splitLeaf (int): Page 100% (1/1)100% (80/80)100% (17/17)
splitNode (int): Page 100% (1/1)100% (132/132)100% (22/22)
writeChildren (WriteBuffer): void 100% (1/1)100% (20/20)100% (4/4)
writeEnd (): void 100% (1/1)100% (51/51)100% (11/11)
writeUnsavedRecursive (Chunk, WriteBuffer): void 100% (1/1)100% (64/64)100% (15/15)
     
class Page$PageReference100% (1/1)100% (1/1)100% (12/12)100% (5/5)
Page$PageReference (Page, long, long): void 100% (1/1)100% (12/12)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.mvstore;
7 
8import java.nio.ByteBuffer;
9import java.util.Arrays;
10import java.util.HashSet;
11import java.util.Set;
12 
13import org.h2.compress.Compressor;
14import org.h2.mvstore.type.DataType;
15import org.h2.util.New;
16 
17/**
18 * A page (a node or a leaf).
19 * <p>
20 * For b-tree nodes, the key at a given index is larger than the largest key of
21 * the child at the same index.
22 * <p>
23 * File format:
24 * page length (including length): int
25 * check value: short
26 * map id: varInt
27 * number of keys: varInt
28 * type: byte (0: leaf, 1: node; +2: compressed)
29 * compressed: bytes saved (varInt)
30 * keys
31 * leaf: values (one for each key)
32 * node: children (1 more than keys)
33 */
34public class Page {
35 
36    /**
37     * An empty object array.
38     */
39    public static final Object[] EMPTY_OBJECT_ARRAY = new Object[0];
40 
41    private final MVMap<?, ?> map;
42    private long version;
43    private long pos;
44 
45    /**
46     * The total entry count of this page and all children.
47     */
48    private long totalCount;
49 
50    /**
51     * The last result of a find operation is cached.
52     */
53    private int cachedCompare;
54 
55    /**
56     * The estimated memory used.
57     */
58    private int memory;
59 
60    /**
61     * The keys.
62     * <p>
63     * The array might be larger than needed, to avoid frequent re-sizing.
64     */
65    private Object[] keys;
66 
67    /**
68     * The values.
69     * <p>
70     * The array might be larger than needed, to avoid frequent re-sizing.
71     */
72    private Object[] values;
73 
74    /**
75     * The child page references.
76     * <p>
77     * The array might be larger than needed, to avoid frequent re-sizing.
78     */
79    private PageReference[] children;
80 
81    /**
82     * Whether the page is an in-memory (not stored, or not yet stored) page,
83     * and it is removed. This is to keep track of pages that concurrently
84     * changed while they are being stored, in which case the live bookkeeping
85     * needs to be aware of such cases.
86     */
87    private volatile boolean removedInMemory;
88 
89    Page(MVMap<?, ?> map, long version) {
90        this.map = map;
91        this.version = version;
92    }
93 
94    /**
95     * Create a new, empty page.
96     *
97     * @param map the map
98     * @param version the version
99     * @return the new page
100     */
101    static Page createEmpty(MVMap<?, ?> map, long version) {
102        return create(map, version,
103                EMPTY_OBJECT_ARRAY, EMPTY_OBJECT_ARRAY,
104                null,
105                0, DataUtils.PAGE_MEMORY);
106    }
107 
108    /**
109     * Create a new page. The arrays are not cloned.
110     *
111     * @param map the map
112     * @param version the version
113     * @param keys the keys
114     * @param values the values
115     * @param children the child page positions
116     * @param totalCount the total number of keys
117     * @param memory the memory used in bytes
118     * @return the page
119     */
120    public static Page create(MVMap<?, ?> map, long version,
121            Object[] keys, Object[] values, PageReference[] children,
122            long totalCount, int memory) {
123        Page p = new Page(map, version);
124        // the position is 0
125        p.keys = keys;
126        p.values = values;
127        p.children = children;
128        p.totalCount = totalCount;
129        if (memory == 0) {
130            p.recalculateMemory();
131        } else {
132            p.addMemory(memory);
133        }
134        MVStore store = map.store;
135        if (store != null) {
136            store.registerUnsavedPage(p.memory);
137        }
138        return p;
139    }
140 
141    /**
142     * Create a copy of a page.
143     *
144     * @param map the map
145     * @param version the version
146     * @param source the source page
147     * @return the page
148     */
149    public static Page create(MVMap<?, ?> map, long version, Page source) {
150        Page p = new Page(map, version);
151        // the position is 0
152        p.keys = source.keys;
153        p.values = source.values;
154        p.children = source.children;
155        p.totalCount = source.totalCount;
156        p.memory = source.memory;
157        MVStore store = map.store;
158        if (store != null) {
159            store.registerUnsavedPage(p.memory);
160        }
161        return p;
162    }
163 
164    /**
165     * Read a page.
166     *
167     * @param fileStore the file store
168     * @param pos the position
169     * @param map the map
170     * @param filePos the position in the file
171     * @param maxPos the maximum position (the end of the chunk)
172     * @return the page
173     */
174    static Page read(FileStore fileStore, long pos, MVMap<?, ?> map,
175            long filePos, long maxPos) {
176        ByteBuffer buff;
177        int maxLength = DataUtils.getPageMaxLength(pos);
178        if (maxLength == DataUtils.PAGE_LARGE) {
179            buff = fileStore.readFully(filePos, 128);
180            maxLength = buff.getInt();
181            // read the first bytes again
182        }
183        maxLength = (int) Math.min(maxPos - filePos, maxLength);
184        int length = maxLength;
185        if (length < 0) {
186            throw DataUtils.newIllegalStateException(
187                    DataUtils.ERROR_FILE_CORRUPT,
188                    "Illegal page length {0} reading at {1}; max pos {2} ",
189                    length, filePos, maxPos);
190        }
191        buff = fileStore.readFully(filePos, length);
192        Page p = new Page(map, 0);
193        p.pos = pos;
194        int chunkId = DataUtils.getPageChunkId(pos);
195        int offset = DataUtils.getPageOffset(pos);
196        p.read(buff, chunkId, offset, maxLength);
197        return p;
198    }
199 
200    /**
201     * Get the key at the given index.
202     *
203     * @param index the index
204     * @return the key
205     */
206    public Object getKey(int index) {
207        return keys[index];
208    }
209 
210    /**
211     * Get the child page at the given index.
212     *
213     * @param index the index
214     * @return the child page
215     */
216    public Page getChildPage(int index) {
217        PageReference ref = children[index];
218        return ref.page != null ? ref.page : map.readPage(ref.pos);
219    }
220 
221    /**
222     * Get the position of the child.
223     *
224     * @param index the index
225     * @return the position
226     */
227    public long getChildPagePos(int index) {
228        return children[index].pos;
229    }
230 
231    /**
232     * Get the value at the given index.
233     *
234     * @param index the index
235     * @return the value
236     */
237    public Object getValue(int index) {
238        return values[index];
239    }
240 
241    /**
242     * Get the number of keys in this page.
243     *
244     * @return the number of keys
245     */
246    public int getKeyCount() {
247        return keys.length;
248    }
249 
250    /**
251     * Check whether this is a leaf page.
252     *
253     * @return true if it is a leaf
254     */
255    public boolean isLeaf() {
256        return children == null;
257    }
258 
259    /**
260     * Get the position of the page
261     *
262     * @return the position
263     */
264    public long getPos() {
265        return pos;
266    }
267 
268    @Override
269    public String toString() {
270        StringBuilder buff = new StringBuilder();
271        buff.append("id: ").append(System.identityHashCode(this)).append('\n');
272        buff.append("version: ").append(Long.toHexString(version)).append("\n");
273        buff.append("pos: ").append(Long.toHexString(pos)).append("\n");
274        if (pos != 0) {
275            int chunkId = DataUtils.getPageChunkId(pos);
276            buff.append("chunk: ").append(Long.toHexString(chunkId)).append("\n");
277        }
278        for (int i = 0; i <= keys.length; i++) {
279            if (i > 0) {
280                buff.append(" ");
281            }
282            if (children != null) {
283                buff.append("[" + Long.toHexString(children[i].pos) + "] ");
284            }
285            if (i < keys.length) {
286                buff.append(keys[i]);
287                if (values != null) {
288                    buff.append(':');
289                    buff.append(values[i]);
290                }
291            }
292        }
293        return buff.toString();
294    }
295 
296    /**
297     * Create a copy of this page.
298     *
299     * @param version the new version
300     * @return a page with the given version
301     */
302    public Page copy(long version) {
303        Page newPage = create(map, version,
304                keys, values,
305                children, totalCount,
306                getMemory());
307        // mark the old as deleted
308        removePage();
309        newPage.cachedCompare = cachedCompare;
310        return newPage;
311    }
312 
313    /**
314     * Search the key in this page using a binary search. Instead of always
315     * starting the search in the middle, the last found index is cached.
316     * <p>
317     * If the key was found, the returned value is the index in the key array.
318     * If not found, the returned value is negative, where -1 means the provided
319     * key is smaller than any keys in this page. See also Arrays.binarySearch.
320     *
321     * @param key the key
322     * @return the value or null
323     */
324    public int binarySearch(Object key) {
325        int low = 0, high = keys.length - 1;
326        // the cached index minus one, so that
327        // for the first time (when cachedCompare is 0),
328        // the default value is used
329        int x = cachedCompare - 1;
330        if (x < 0 || x > high) {
331            x = high >>> 1;
332        }
333        Object[] k = keys;
334        while (low <= high) {
335            int compare = map.compare(key, k[x]);
336            if (compare > 0) {
337                low = x + 1;
338            } else if (compare < 0) {
339                high = x - 1;
340            } else {
341                cachedCompare = x + 1;
342                return x;
343            }
344            x = (low + high) >>> 1;
345        }
346        cachedCompare = low;
347        return -(low + 1);
348 
349        // regular binary search (without caching)
350        // int low = 0, high = keys.length - 1;
351        // while (low <= high) {
352        //     int x = (low + high) >>> 1;
353        //     int compare = map.compare(key, keys[x]);
354        //     if (compare > 0) {
355        //         low = x + 1;
356        //     } else if (compare < 0) {
357        //         high = x - 1;
358        //     } else {
359        //         return x;
360        //     }
361        // }
362        // return -(low + 1);
363    }
364 
365    /**
366     * Split the page. This modifies the current page.
367     *
368     * @param at the split index
369     * @return the page with the entries after the split index
370     */
371    Page split(int at) {
372        return isLeaf() ? splitLeaf(at) : splitNode(at);
373    }
374 
375    private Page splitLeaf(int at) {
376        int a = at, b = keys.length - a;
377        Object[] aKeys = new Object[a];
378        Object[] bKeys = new Object[b];
379        System.arraycopy(keys, 0, aKeys, 0, a);
380        System.arraycopy(keys, a, bKeys, 0, b);
381        keys = aKeys;
382        Object[] aValues = new Object[a];
383        Object[] bValues = new Object[b];
384        bValues = new Object[b];
385        System.arraycopy(values, 0, aValues, 0, a);
386        System.arraycopy(values, a, bValues, 0, b);
387        values = aValues;
388        totalCount = a;
389        Page newPage = create(map, version,
390                bKeys, bValues,
391                null,
392                bKeys.length, 0);
393        recalculateMemory();
394        newPage.recalculateMemory();
395        return newPage;
396    }
397 
398    private Page splitNode(int at) {
399        int a = at, b = keys.length - a;
400 
401        Object[] aKeys = new Object[a];
402        Object[] bKeys = new Object[b - 1];
403        System.arraycopy(keys, 0, aKeys, 0, a);
404        System.arraycopy(keys, a + 1, bKeys, 0, b - 1);
405        keys = aKeys;
406 
407        PageReference[] aChildren = new PageReference[a + 1];
408        PageReference[] bChildren = new PageReference[b];
409        System.arraycopy(children, 0, aChildren, 0, a + 1);
410        System.arraycopy(children, a + 1, bChildren, 0, b);
411        children = aChildren;
412 
413        long t = 0;
414        for (PageReference x : aChildren) {
415            t += x.count;
416        }
417        totalCount = t;
418        t = 0;
419        for (PageReference x : bChildren) {
420            t += x.count;
421        }
422        Page newPage = create(map, version,
423                bKeys, null,
424                bChildren,
425                t, 0);
426        recalculateMemory();
427        newPage.recalculateMemory();
428        return newPage;
429    }
430 
431    /**
432     * Get the total number of key-value pairs, including child pages.
433     *
434     * @return the number of key-value pairs
435     */
436    public long getTotalCount() {
437        if (MVStore.ASSERT) {
438            long check = 0;
439            if (isLeaf()) {
440                check = keys.length;
441            } else {
442                for (PageReference x : children) {
443                    check += x.count;
444                }
445            }
446            if (check != totalCount) {
447                throw DataUtils.newIllegalStateException(
448                        DataUtils.ERROR_INTERNAL,
449                        "Expected: {0} got: {1}", check, totalCount);
450            }
451        }
452        return totalCount;
453    }
454 
455    /**
456     * Get the descendant counts for the given child.
457     *
458     * @param index the child index
459     * @return the descendant count
460     */
461    long getCounts(int index) {
462        return children[index].count;
463    }
464 
465    /**
466     * Replace the child page.
467     *
468     * @param index the index
469     * @param c the new child page
470     */
471    public void setChild(int index, Page c) {
472        if (c == null) {
473            long oldCount = children[index].count;
474            children = Arrays.copyOf(children, children.length);
475            PageReference ref = new PageReference(null, 0, 0);
476            children[index] = ref;
477            totalCount -= oldCount;
478        } else if (c != children[index].page ||
479                c.getPos() != children[index].pos) {
480            long oldCount = children[index].count;
481            children = Arrays.copyOf(children, children.length);
482            PageReference ref = new PageReference(c, c.pos, c.totalCount);
483            children[index] = ref;
484            totalCount += c.totalCount - oldCount;
485        }
486    }
487 
488    /**
489     * Replace the key at an index in this page.
490     *
491     * @param index the index
492     * @param key the new key
493     */
494    public void setKey(int index, Object key) {
495        keys = Arrays.copyOf(keys, keys.length);
496        Object old = keys[index];
497        DataType keyType = map.getKeyType();
498        int mem = keyType.getMemory(key);
499        if (old != null) {
500            mem -= keyType.getMemory(old);
501        }
502        addMemory(mem);
503        keys[index] = key;
504    }
505 
506    /**
507     * Replace the value at an index in this page.
508     *
509     * @param index the index
510     * @param value the new value
511     * @return the old value
512     */
513    public Object setValue(int index, Object value) {
514        Object old = values[index];
515        values = Arrays.copyOf(values, values.length);
516        DataType valueType = map.getValueType();
517        addMemory(valueType.getMemory(value) -
518                valueType.getMemory(old));
519        values[index] = value;
520        return old;
521    }
522 
523    /**
524     * Remove this page and all child pages.
525     */
526    void removeAllRecursive() {
527        if (children != null) {
528            for (int i = 0, size = map.getChildPageCount(this); i < size; i++) {
529                PageReference ref = children[i];
530                if (ref.page != null) {
531                    ref.page.removeAllRecursive();
532                } else {
533                    long c = children[i].pos;
534                    int type = DataUtils.getPageType(c);
535                    if (type == DataUtils.PAGE_TYPE_LEAF) {
536                        int mem = DataUtils.getPageMaxLength(c);
537                        map.removePage(c, mem);
538                    } else {
539                        map.readPage(c).removeAllRecursive();
540                    }
541                }
542            }
543        }
544        removePage();
545    }
546 
547    /**
548     * Insert a key-value pair into this leaf.
549     *
550     * @param index the index
551     * @param key the key
552     * @param value the value
553     */
554    public void insertLeaf(int index, Object key, Object value) {
555        int len = keys.length + 1;
556        Object[] newKeys = new Object[len];
557        DataUtils.copyWithGap(keys, newKeys, len - 1, index);
558        keys = newKeys;
559        Object[] newValues = new Object[len];
560        DataUtils.copyWithGap(values, newValues, len - 1, index);
561        values = newValues;
562        keys[index] = key;
563        values[index] = value;
564        totalCount++;
565        addMemory(map.getKeyType().getMemory(key) +
566                map.getValueType().getMemory(value));
567    }
568 
569    /**
570     * Insert a child page into this node.
571     *
572     * @param index the index
573     * @param key the key
574     * @param childPage the child page
575     */
576    public void insertNode(int index, Object key, Page childPage) {
577 
578        Object[] newKeys = new Object[keys.length + 1];
579        DataUtils.copyWithGap(keys, newKeys, keys.length, index);
580        newKeys[index] = key;
581        keys = newKeys;
582 
583        int childCount = children.length;
584        PageReference[] newChildren = new PageReference[childCount + 1];
585        DataUtils.copyWithGap(children, newChildren, childCount, index);
586        newChildren[index] = new PageReference(
587                childPage, childPage.getPos(), childPage.totalCount);
588        children = newChildren;
589 
590        totalCount += childPage.totalCount;
591        addMemory(map.getKeyType().getMemory(key) +
592                DataUtils.PAGE_MEMORY_CHILD);
593    }
594 
595    /**
596     * Remove the key and value (or child) at the given index.
597     *
598     * @param index the index
599     */
600    public void remove(int index) {
601        int keyLength = keys.length;
602        int keyIndex = index >= keyLength ? index - 1 : index;
603        Object old = keys[keyIndex];
604        addMemory(-map.getKeyType().getMemory(old));
605        Object[] newKeys = new Object[keyLength - 1];
606        DataUtils.copyExcept(keys, newKeys, keyLength, keyIndex);
607        keys = newKeys;
608 
609        if (values != null) {
610            old = values[index];
611            addMemory(-map.getValueType().getMemory(old));
612            Object[] newValues = new Object[keyLength - 1];
613            DataUtils.copyExcept(values, newValues, keyLength, index);
614            values = newValues;
615            totalCount--;
616        }
617        if (children != null) {
618            addMemory(-DataUtils.PAGE_MEMORY_CHILD);
619            long countOffset = children[index].count;
620 
621            int childCount = children.length;
622            PageReference[] newChildren = new PageReference[childCount - 1];
623            DataUtils.copyExcept(children, newChildren, childCount, index);
624            children = newChildren;
625 
626            totalCount -= countOffset;
627        }
628    }
629 
630    /**
631     * Read the page from the buffer.
632     *
633     * @param buff the buffer
634     * @param chunkId the chunk id
635     * @param offset the offset within the chunk
636     * @param maxLength the maximum length
637     */
638    void read(ByteBuffer buff, int chunkId, int offset, int maxLength) {
639        int start = buff.position();
640        int pageLength = buff.getInt();
641        if (pageLength > maxLength) {
642            throw DataUtils.newIllegalStateException(
643                    DataUtils.ERROR_FILE_CORRUPT,
644                    "File corrupted in chunk {0}, expected page length =< {1}, got {2}",
645                    chunkId, maxLength, pageLength);
646        }
647        buff.limit(start + pageLength);
648        short check = buff.getShort();
649        int mapId = DataUtils.readVarInt(buff);
650        if (mapId != map.getId()) {
651            throw DataUtils.newIllegalStateException(
652                    DataUtils.ERROR_FILE_CORRUPT,
653                    "File corrupted in chunk {0}, expected map id {1}, got {2}",
654                    chunkId, map.getId(), mapId);
655        }
656        int checkTest = DataUtils.getCheckValue(chunkId)
657                ^ DataUtils.getCheckValue(offset)
658                ^ DataUtils.getCheckValue(pageLength);
659        if (check != (short) checkTest) {
660            throw DataUtils.newIllegalStateException(
661                    DataUtils.ERROR_FILE_CORRUPT,
662                    "File corrupted in chunk {0}, expected check value {1}, got {2}",
663                    chunkId, checkTest, check);
664        }
665        int len = DataUtils.readVarInt(buff);
666        keys = new Object[len];
667        int type = buff.get();
668        boolean node = (type & 1) == DataUtils.PAGE_TYPE_NODE;
669        if (node) {
670            children = new PageReference[len + 1];
671            long[] p = new long[len + 1];
672            for (int i = 0; i <= len; i++) {
673                p[i] = buff.getLong();
674            }
675            long total = 0;
676            for (int i = 0; i <= len; i++) {
677                long s = DataUtils.readVarLong(buff);
678                total += s;
679                children[i] = new PageReference(null, p[i], s);
680            }
681            totalCount = total;
682        }
683        boolean compressed = (type & DataUtils.PAGE_COMPRESSED) != 0;
684        if (compressed) {
685            Compressor compressor;
686            if ((type & DataUtils.PAGE_COMPRESSED_HIGH) ==
687                    DataUtils.PAGE_COMPRESSED_HIGH) {
688                compressor = map.getStore().getCompressorHigh();
689            } else {
690                compressor = map.getStore().getCompressorFast();
691            }
692            int lenAdd = DataUtils.readVarInt(buff);
693            int compLen = pageLength + start - buff.position();
694            byte[] comp = DataUtils.newBytes(compLen);
695            buff.get(comp);
696            int l = compLen + lenAdd;
697            buff = ByteBuffer.allocate(l);
698            compressor.expand(comp, 0, compLen, buff.array(),
699                    buff.arrayOffset(), l);
700        }
701        map.getKeyType().read(buff, keys, len, true);
702        if (!node) {
703            values = new Object[len];
704            map.getValueType().read(buff, values, len, false);
705            totalCount = len;
706        }
707        recalculateMemory();
708    }
709 
710    /**
711     * Store the page and update the position.
712     *
713     * @param chunk the chunk
714     * @param buff the target buffer
715     * @return the position of the buffer just after the type
716     */
717    private int write(Chunk chunk, WriteBuffer buff) {
718        int start = buff.position();
719        int len = keys.length;
720        int type = children != null ? DataUtils.PAGE_TYPE_NODE
721                : DataUtils.PAGE_TYPE_LEAF;
722        buff.putInt(0).
723            putShort((byte) 0).
724            putVarInt(map.getId()).
725            putVarInt(len);
726        int typePos = buff.position();
727        buff.put((byte) type);
728        if (type == DataUtils.PAGE_TYPE_NODE) {
729            writeChildren(buff);
730            for (int i = 0; i <= len; i++) {
731                buff.putVarLong(children[i].count);
732            }
733        }
734        int compressStart = buff.position();
735        map.getKeyType().write(buff, keys, len, true);
736        if (type == DataUtils.PAGE_TYPE_LEAF) {
737            map.getValueType().write(buff, values, len, false);
738        }
739        MVStore store = map.getStore();
740        int expLen = buff.position() - compressStart;
741        if (expLen > 16) {
742            int compressionLevel = store.getCompressionLevel();
743            if (compressionLevel > 0) {
744                Compressor compressor;
745                int compressType;
746                if (compressionLevel == 1) {
747                    compressor = map.getStore().getCompressorFast();
748                    compressType = DataUtils.PAGE_COMPRESSED;
749                } else {
750                    compressor = map.getStore().getCompressorHigh();
751                    compressType = DataUtils.PAGE_COMPRESSED_HIGH;
752                }
753                byte[] exp = new byte[expLen];
754                buff.position(compressStart).get(exp);
755                byte[] comp = new byte[expLen * 2];
756                int compLen = compressor.compress(exp, expLen, comp, 0);
757                int plus = DataUtils.getVarIntLen(compLen - expLen);
758                if (compLen + plus < expLen) {
759                    buff.position(typePos).
760                        put((byte) (type + compressType));
761                    buff.position(compressStart).
762                        putVarInt(expLen - compLen).
763                        put(comp, 0, compLen);
764                }
765            }
766        }
767        int pageLength = buff.position() - start;
768        int chunkId = chunk.id;
769        int check = DataUtils.getCheckValue(chunkId)
770                ^ DataUtils.getCheckValue(start)
771                ^ DataUtils.getCheckValue(pageLength);
772        buff.putInt(start, pageLength).
773            putShort(start + 4, (short) check);
774        if (pos != 0) {
775            throw DataUtils.newIllegalStateException(
776                    DataUtils.ERROR_INTERNAL, "Page already stored");
777        }
778        pos = DataUtils.getPagePos(chunkId, start, pageLength, type);
779        store.cachePage(pos, this, getMemory());
780        if (type == DataUtils.PAGE_TYPE_NODE) {
781            // cache again - this will make sure nodes stays in the cache
782            // for a longer time
783            store.cachePage(pos, this, getMemory());
784        }
785        long max = DataUtils.getPageMaxLength(pos);
786        chunk.maxLen += max;
787        chunk.maxLenLive += max;
788        chunk.pageCount++;
789        chunk.pageCountLive++;
790        if (removedInMemory) {
791            // if the page was removed _before_ the position was assigned, we
792            // need to mark it removed here, so the fields are updated
793            // when the next chunk is stored
794            map.removePage(pos, memory);
795        }
796        return typePos + 1;
797    }
798 
799    private void writeChildren(WriteBuffer buff) {
800        int len = keys.length;
801        for (int i = 0; i <= len; i++) {
802            buff.putLong(children[i].pos);
803        }
804    }
805 
806    /**
807     * Store this page and all children that are changed, in reverse order, and
808     * update the position and the children.
809     *
810     * @param chunk the chunk
811     * @param buff the target buffer
812     */
813    void writeUnsavedRecursive(Chunk chunk, WriteBuffer buff) {
814        if (pos != 0) {
815            // already stored before
816            return;
817        }
818        int patch = write(chunk, buff);
819        if (!isLeaf()) {
820            int len = children.length;
821            for (int i = 0; i < len; i++) {
822                Page p = children[i].page;
823                if (p != null) {
824                    p.writeUnsavedRecursive(chunk, buff);
825                    children[i] = new PageReference(p, p.getPos(), p.totalCount);
826                }
827            }
828            int old = buff.position();
829            buff.position(patch);
830            writeChildren(buff);
831            buff.position(old);
832        }
833    }
834 
835    /**
836     * Unlink the children recursively after all data is written.
837     */
838    void writeEnd() {
839        if (isLeaf()) {
840            return;
841        }
842        int len = children.length;
843        for (int i = 0; i < len; i++) {
844            PageReference ref = children[i];
845            if (ref.page != null) {
846                if (ref.page.getPos() == 0) {
847                    throw DataUtils.newIllegalStateException(
848                            DataUtils.ERROR_INTERNAL, "Page not written");
849                }
850                ref.page.writeEnd();
851                children[i] = new PageReference(null, ref.pos, ref.count);
852            }
853        }
854    }
855 
856    long getVersion() {
857        return version;
858    }
859 
860    public int getRawChildPageCount() {
861        return children.length;
862    }
863 
864    @Override
865    public boolean equals(Object other) {
866        if (other == this) {
867            return true;
868        }
869        if (other instanceof Page) {
870            if (pos != 0 && ((Page) other).pos == pos) {
871                return true;
872            }
873            return this == other;
874        }
875        return false;
876    }
877 
878    @Override
879    public int hashCode() {
880        return pos != 0 ? (int) (pos | (pos >>> 32)) : super.hashCode();
881    }
882 
883    public int getMemory() {
884        if (MVStore.ASSERT) {
885            int mem = memory;
886            recalculateMemory();
887            if (mem != memory) {
888                throw DataUtils.newIllegalStateException(
889                        DataUtils.ERROR_INTERNAL, "Memory calculation error");
890            }
891        }
892        return memory;
893    }
894 
895    private void addMemory(int mem) {
896        memory += mem;
897    }
898 
899    private void recalculateMemory() {
900        int mem = DataUtils.PAGE_MEMORY;
901        DataType keyType = map.getKeyType();
902        for (int i = 0; i < keys.length; i++) {
903            mem += keyType.getMemory(keys[i]);
904        }
905        if (this.isLeaf()) {
906            DataType valueType = map.getValueType();
907            for (int i = 0; i < keys.length; i++) {
908                mem += valueType.getMemory(values[i]);
909            }
910        } else {
911            mem += this.getRawChildPageCount() * DataUtils.PAGE_MEMORY_CHILD;
912        }
913        addMemory(mem - memory);
914    }
915 
916    void setVersion(long version) {
917        this.version = version;
918    }
919 
920    /**
921     * Remove the page.
922     */
923    public void removePage() {
924        long p = pos;
925        if (p == 0) {
926            removedInMemory = true;
927        }
928        map.removePage(p, memory);
929    }
930 
931    /**
932     * A pointer to a page, either in-memory or using a page position.
933     */
934    public static class PageReference {
935 
936        /**
937         * The position, if known, or 0.
938         */
939        final long pos;
940 
941        /**
942         * The page, if in memory, or null.
943         */
944        final Page page;
945 
946        /**
947         * The descendant count for this child page.
948         */
949        final long count;
950 
951        public PageReference(Page page, long pos, long count) {
952            this.page = page;
953            this.pos = pos;
954            this.count = count;
955        }
956 
957    }
958 
959    /**
960     * Contains information about which other pages are referenced (directly or
961     * indirectly) by the given page. This is a subset of the page data, for
962     * pages of type node. This information is used for garbage collection (to
963     * quickly find out which chunks are still in use).
964     */
965    public static class PageChildren {
966 
967        /**
968         * An empty array of type long.
969         */
970        public static final long[] EMPTY_ARRAY = new long[0];
971 
972        /**
973         * The position of the page.
974         */
975        final long pos;
976 
977        /**
978         * The page positions of (direct or indirect) children. Depending on the
979         * use case, this can be the complete list, or only a subset of all
980         * children, for example only only one reference to a child in another
981         * chunk.
982         */
983        long[] children;
984 
985        /**
986         * Whether this object only contains the list of chunks.
987         */
988        boolean chunkList;
989 
990        private PageChildren(long pos, long[] children) {
991            this.pos = pos;
992            this.children = children;
993        }
994 
995        PageChildren(Page p) {
996            this.pos = p.getPos();
997            int count = p.getRawChildPageCount();
998            this.children = new long[count];
999            for (int i = 0; i < count; i++) {
1000                children[i] = p.getChildPagePos(i);
1001            }
1002        }
1003 
1004        int getMemory() {
1005            return 64 + 8 * children.length;
1006        }
1007 
1008        /**
1009         * Read an inner node page from the buffer, but ignore the keys and
1010         * values.
1011         *
1012         * @param fileStore the file store
1013         * @param pos the position
1014         * @param mapId the map id
1015         * @param filePos the position in the file
1016         * @param maxPos the maximum position (the end of the chunk)
1017         * @return the page children object
1018         */
1019        static PageChildren read(FileStore fileStore, long pos, int mapId,
1020                long filePos, long maxPos) {
1021            ByteBuffer buff;
1022            int maxLength = DataUtils.getPageMaxLength(pos);
1023            if (maxLength == DataUtils.PAGE_LARGE) {
1024                buff = fileStore.readFully(filePos, 128);
1025                maxLength = buff.getInt();
1026                // read the first bytes again
1027            }
1028            maxLength = (int) Math.min(maxPos - filePos, maxLength);
1029            int length = maxLength;
1030            if (length < 0) {
1031                throw DataUtils.newIllegalStateException(
1032                        DataUtils.ERROR_FILE_CORRUPT,
1033                        "Illegal page length {0} reading at {1}; max pos {2} ",
1034                        length, filePos, maxPos);
1035            }
1036            buff = fileStore.readFully(filePos, length);
1037            int chunkId = DataUtils.getPageChunkId(pos);
1038            int offset = DataUtils.getPageOffset(pos);
1039            int start = buff.position();
1040            int pageLength = buff.getInt();
1041            if (pageLength > maxLength) {
1042                throw DataUtils.newIllegalStateException(
1043                        DataUtils.ERROR_FILE_CORRUPT,
1044                        "File corrupted in chunk {0}, expected page length =< {1}, got {2}",
1045                        chunkId, maxLength, pageLength);
1046            }
1047            buff.limit(start + pageLength);
1048            short check = buff.getShort();
1049            int m = DataUtils.readVarInt(buff);
1050            if (m != mapId) {
1051                throw DataUtils.newIllegalStateException(
1052                        DataUtils.ERROR_FILE_CORRUPT,
1053                        "File corrupted in chunk {0}, expected map id {1}, got {2}",
1054                        chunkId, mapId, m);
1055            }
1056            int checkTest = DataUtils.getCheckValue(chunkId)
1057                    ^ DataUtils.getCheckValue(offset)
1058                    ^ DataUtils.getCheckValue(pageLength);
1059            if (check != (short) checkTest) {
1060                throw DataUtils.newIllegalStateException(
1061                        DataUtils.ERROR_FILE_CORRUPT,
1062                        "File corrupted in chunk {0}, expected check value {1}, got {2}",
1063                        chunkId, checkTest, check);
1064            }
1065            int len = DataUtils.readVarInt(buff);
1066            int type = buff.get();
1067            boolean node = (type & 1) == DataUtils.PAGE_TYPE_NODE;
1068            if (!node) {
1069                return null;
1070            }
1071            long[] children = new long[len + 1];
1072            for (int i = 0; i <= len; i++) {
1073                children[i] = buff.getLong();
1074            }
1075            return new PageChildren(pos, children);
1076        }
1077 
1078        /**
1079         * Only keep one reference to the same chunk. Only leaf references are
1080         * removed (references to inner nodes are not removed, as they could
1081         * indirectly point to other chunks).
1082         */
1083        void removeDuplicateChunkReferences() {
1084            HashSet<Integer> chunks = New.hashSet();
1085            // we don't need references to leaves in the same chunk
1086            chunks.add(DataUtils.getPageChunkId(pos));
1087            for (int i = 0; i < children.length; i++) {
1088                long p = children[i];
1089                int chunkId = DataUtils.getPageChunkId(p);
1090                boolean wasNew = chunks.add(chunkId);
1091                if (DataUtils.getPageType(p) == DataUtils.PAGE_TYPE_NODE) {
1092                    continue;
1093                }
1094                if (wasNew) {
1095                    continue;
1096                }
1097                removeChild(i--);
1098            }
1099        }
1100 
1101        /**
1102         * Collect the set of chunks referenced directly by this page.
1103         *
1104         * @param target the target set
1105         */
1106        void collectReferencedChunks(Set<Integer> target) {
1107            target.add(DataUtils.getPageChunkId(pos));
1108            for (long p : children) {
1109                target.add(DataUtils.getPageChunkId(p));
1110            }
1111        }
1112 
1113        private void removeChild(int index) {
1114            if (index == 0 && children.length == 1) {
1115                children = EMPTY_ARRAY;
1116                return;
1117            }
1118            long[] c2 = new long[children.length - 1];
1119            DataUtils.copyExcept(children, c2, children.length, index);
1120            children = c2;
1121        }
1122 
1123    }
1124 
1125}

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