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

COVERAGE SUMMARY FOR SOURCE FILE [MVMap.java]

nameclass, %method, %block, %line, %
MVMap.java100% (6/6)87%  (83/95)91%  (1635/1795)89%  (376.3/421)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class MVMap$3100% (1/1)50%  (2/4)70%  (21/30)50%  (2/4)
contains (Object): boolean 0%   (0/1)0%   (0/5)0%   (0/1)
size (): int 0%   (0/1)0%   (0/4)0%   (0/1)
MVMap$3 (MVMap, MVMap, Page): void 100% (1/1)100% (12/12)100% (1/1)
iterator (): Iterator 100% (1/1)100% (9/9)100% (1/1)
     
class MVMap$2100% (1/1)50%  (2/4)75%  (27/36)60%  (3/5)
contains (Object): boolean 0%   (0/1)0%   (0/5)0%   (0/1)
size (): int 0%   (0/1)0%   (0/4)0%   (0/1)
MVMap$2 (MVMap, MVMap, Page): void 100% (1/1)100% (12/12)100% (1/1)
iterator (): Iterator 100% (1/1)100% (15/15)100% (2/2)
     
class MVMap$Builder100% (1/1)67%  (4/6)86%  (37/43)85%  (11/13)
getKeyType (): DataType 0%   (0/1)0%   (0/3)0%   (0/1)
getValueType (): DataType 0%   (0/1)0%   (0/3)0%   (0/1)
MVMap$Builder (): void 100% (1/1)100% (3/3)100% (2/2)
create (): MVMap 100% (1/1)100% (24/24)100% (5/5)
keyType (DataType): MVMap$Builder 100% (1/1)100% (5/5)100% (2/2)
valueType (DataType): MVMap$Builder 100% (1/1)100% (5/5)100% (2/2)
     
class MVMap$2$1100% (1/1)75%  (3/4)89%  (25/28)80%  (4/5)
remove (): void 0%   (0/1)0%   (0/3)0%   (0/1)
MVMap$2$1 (MVMap$2, Cursor): void 100% (1/1)100% (9/9)100% (1/1)
hasNext (): boolean 100% (1/1)100% (4/4)100% (1/1)
next (): Map$Entry 100% (1/1)100% (12/12)100% (2/2)
     
class MVMap100% (1/1)93%  (68/73)92%  (1503/1636)90%  (356.3/394)
binarySearchPage (Page, Object): Page 0%   (0/1)0%   (0/31)0%   (0/10)
equals (Object): boolean 0%   (0/1)0%   (0/7)0%   (0/1)
hashCode (): int 0%   (0/1)0%   (0/3)0%   (0/1)
putBranch (Page, Object, Object): Page 0%   (0/1)0%   (0/30)0%   (0/6)
toString (): String 0%   (0/1)0%   (0/4)0%   (0/1)
rewrite (Set): boolean 100% (1/1)67%  (26/39)54%  (7/13)
rewrite (Page, Set): int 100% (1/1)77%  (92/119)75%  (24/32)
size (): int 100% (1/1)83%  (10/12)92%  (1.8/2)
beforeWrite (): void 100% (1/1)85%  (17/20)83%  (5/6)
remove (Object): Object 100% (1/1)91%  (51/56)97%  (13.5/14)
getKey (long): Object 100% (1/1)95%  (69/73)89%  (16/18)
put (Object, Object): Object 100% (1/1)97%  (35/36)100% (8/8)
openVersion (long): MVMap 100% (1/1)97%  (108/111)95%  (20/21)
MVMap (DataType, DataType): void 100% (1/1)100% (19/19)100% (6/6)
areValuesEqual (Object, Object): boolean 100% (1/1)100% (21/21)100% (5/5)
asString (String): String 100% (1/1)100% (33/33)100% (9/9)
binarySearch (Page, Object): Object 100% (1/1)100% (33/33)100% (10/10)
ceilingKey (Object): Object 100% (1/1)100% (6/6)100% (1/1)
clear (): void 100% (1/1)100% (12/12)100% (4/4)
close (): void 100% (1/1)100% (4/4)100% (2/2)
compare (Object, Object): int 100% (1/1)100% (6/6)100% (1/1)
containsKey (Object): boolean 100% (1/1)100% (8/8)100% (1/1)
copy (Page, CursorPos): Page 100% (1/1)100% (97/97)100% (21/21)
copyFrom (MVMap): void 100% (1/1)100% (10/10)100% (3/3)
cursor (Object): Cursor 100% (1/1)100% (8/8)100% (1/1)
entrySet (): Set 100% (1/1)100% (12/12)100% (3/3)
firstKey (): Object 100% (1/1)100% (4/4)100% (1/1)
floorKey (Object): Object 100% (1/1)100% (6/6)100% (1/1)
get (Object): Object 100% (1/1)100% (6/6)100% (1/1)
getChildPageCount (Page): int 100% (1/1)100% (3/3)100% (1/1)
getCreateVersion (): long 100% (1/1)100% (3/3)100% (1/1)
getFirstLast (boolean): Object 100% (1/1)100% (35/35)100% (6/6)
getId (): int 100% (1/1)100% (3/3)100% (1/1)
getKeyIndex (Object): long 100% (1/1)100% (57/57)100% (16/16)
getKeyType (): DataType 100% (1/1)100% (3/3)100% (1/1)
getMapKey (int): String 100% (1/1)100% (10/10)100% (1/1)
getMapRootKey (int): String 100% (1/1)100% (10/10)100% (1/1)
getMinMax (Object, boolean, boolean): Object 100% (1/1)100% (8/8)100% (1/1)
getMinMax (Page, Object, boolean, boolean): Object 100% (1/1)100% (85/85)100% (20/20)
getName (): String 100% (1/1)100% (6/6)100% (1/1)
getRoot (): Page 100% (1/1)100% (3/3)100% (1/1)
getStore (): MVStore 100% (1/1)100% (3/3)100% (1/1)
getType (): String 100% (1/1)100% (2/2)100% (1/1)
getValueType (): DataType 100% (1/1)100% (3/3)100% (1/1)
getVersion (): long 100% (1/1)100% (4/4)100% (1/1)
higherKey (Object): Object 100% (1/1)100% (6/6)100% (1/1)
init (MVStore, HashMap): void 100% (1/1)100% (20/20)100% (5/5)
isClosed (): boolean 100% (1/1)100% (3/3)100% (1/1)
isEmpty (): boolean 100% (1/1)100% (12/12)100% (1/1)
isReadOnly (): boolean 100% (1/1)100% (3/3)100% (1/1)
isVolatile (): boolean 100% (1/1)100% (3/3)100% (1/1)
keyIterator (Object): Iterator 100% (1/1)100% (8/8)100% (1/1)
keyList (): List 100% (1/1)100% (5/5)100% (1/1)
keySet (): Set 100% (1/1)100% (12/12)100% (3/3)
lastKey (): Object 100% (1/1)100% (4/4)100% (1/1)
lowerKey (Object): Object 100% (1/1)100% (6/6)100% (1/1)
newRoot (Page): void 100% (1/1)100% (36/36)100% (8/8)
openReadOnly (): MVMap 100% (1/1)100% (38/38)100% (8/8)
put (Page, long, Object, Object): Object 100% (1/1)100% (93/93)100% (21/21)
putIfAbsent (Object, Object): Object 100% (1/1)100% (13/13)100% (4/4)
readPage (long): Page 100% (1/1)100% (6/6)100% (1/1)
remove (Object, Object): boolean 100% (1/1)100% (17/17)100% (5/5)
remove (Page, long, Object): Object 100% (1/1)100% (70/70)100% (20/20)
removePage (long, int): void 100% (1/1)100% (7/7)100% (2/2)
removeUnusedOldVersions (): void 100% (1/1)100% (37/37)100% (10/10)
replace (Object, Object): Object 100% (1/1)100% (15/15)100% (5/5)
replace (Object, Object, Object): boolean 100% (1/1)100% (18/18)100% (5/5)
rollbackTo (long): void 100% (1/1)100% (39/39)100% (12/12)
setRootPos (long, long): void 100% (1/1)100% (18/18)100% (3/3)
setVolatile (boolean): void 100% (1/1)100% (4/4)100% (2/2)
setWriteVersion (long): void 100% (1/1)100% (4/4)100% (2/2)
sizeAsLong (): long 100% (1/1)100% (4/4)100% (1/1)
splitRootIfNeeded (Page, long): Page 100% (1/1)100% (71/71)100% (10/10)
     
class MVMap$1100% (1/1)100% (4/4)100% (22/22)100% (4/4)
MVMap$1 (MVMap): void 100% (1/1)100% (6/6)100% (1/1)
get (int): Object 100% (1/1)100% (6/6)100% (1/1)
indexOf (Object): int 100% (1/1)100% (6/6)100% (1/1)
size (): int 100% (1/1)100% (4/4)100% (1/1)

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.util.AbstractList;
9import java.util.AbstractMap;
10import java.util.AbstractSet;
11import java.util.HashMap;
12import java.util.Iterator;
13import java.util.List;
14import java.util.Map;
15import java.util.Set;
16import java.util.concurrent.ConcurrentMap;
17 
18import org.h2.mvstore.type.DataType;
19import org.h2.mvstore.type.ObjectDataType;
20import org.h2.util.New;
21 
22/**
23 * A stored map.
24 * <p>
25 * Read operations can happen concurrently with all other
26 * operations, without risk of corruption.
27 * <p>
28 * Write operations first read the relevant area from disk to memory
29 * concurrently, and only then modify the data. The in-memory part of write
30 * operations is synchronized. For scalable concurrent in-memory write
31 * operations, the map should be split into multiple smaller sub-maps that are
32 * then synchronized independently.
33 *
34 * @param <K> the key class
35 * @param <V> the value class
36 */
37public class MVMap<K, V> extends AbstractMap<K, V>
38        implements ConcurrentMap<K, V> {
39 
40    /**
41     * The store.
42     */
43    protected MVStore store;
44 
45    /**
46     * The current root page (may not be null).
47     */
48    protected volatile Page root;
49 
50    /**
51     * The version used for writing.
52     */
53    protected volatile long writeVersion;
54 
55    private int id;
56    private long createVersion;
57    private final DataType keyType;
58    private final DataType valueType;
59 
60    private ConcurrentArrayList<Page> oldRoots =
61            new ConcurrentArrayList<Page>();
62 
63    private boolean closed;
64    private boolean readOnly;
65    private boolean isVolatile;
66 
67    protected MVMap(DataType keyType, DataType valueType) {
68        this.keyType = keyType;
69        this.valueType = valueType;
70        this.root = Page.createEmpty(this,  -1);
71    }
72 
73    /**
74     * Get the metadata key for the root of the given map id.
75     *
76     * @param mapId the map id
77     * @return the metadata key
78     */
79    static String getMapRootKey(int mapId) {
80        return "root." + Integer.toHexString(mapId);
81    }
82 
83    /**
84     * Get the metadata key for the given map id.
85     *
86     * @param mapId the map id
87     * @return the metadata key
88     */
89    static String getMapKey(int mapId) {
90        return "map." + Integer.toHexString(mapId);
91    }
92 
93    /**
94     * Open this map with the given store and configuration.
95     *
96     * @param store the store
97     * @param config the configuration
98     */
99    protected void init(MVStore store, HashMap<String, Object> config) {
100        this.store = store;
101        this.id = DataUtils.readHexInt(config, "id", 0);
102        this.createVersion = DataUtils.readHexLong(config, "createVersion", 0);
103        this.writeVersion = store.getCurrentVersion();
104    }
105 
106    /**
107     * Add or replace a key-value pair.
108     *
109     * @param key the key (may not be null)
110     * @param value the value (may not be null)
111     * @return the old value if the key existed, or null otherwise
112     */
113    @Override
114    @SuppressWarnings("unchecked")
115    public synchronized V put(K key, V value) {
116        DataUtils.checkArgument(value != null, "The value may not be null");
117        beforeWrite();
118        long v = writeVersion;
119        Page p = root.copy(v);
120        p = splitRootIfNeeded(p, v);
121        Object result = put(p, v, key, value);
122        newRoot(p);
123        return (V) result;
124    }
125 
126    /**
127     * Add or replace a key-value pair in a branch.
128     *
129     * @param root the root page
130     * @param key the key (may not be null)
131     * @param value the value (may not be null)
132     * @return the new root page
133     */
134    synchronized Page putBranch(Page root, K key, V value) {
135        DataUtils.checkArgument(value != null, "The value may not be null");
136        long v = writeVersion;
137        Page p = root.copy(v);
138        p = splitRootIfNeeded(p, v);
139        put(p, v, key, value);
140        return p;
141    }
142 
143    /**
144     * Split the root page if necessary.
145     *
146     * @param p the page
147     * @param writeVersion the write version
148     * @return the new sibling
149     */
150    protected Page splitRootIfNeeded(Page p, long writeVersion) {
151        if (p.getMemory() <= store.getPageSplitSize() || p.getKeyCount() <= 1) {
152            return p;
153        }
154        int at = p.getKeyCount() / 2;
155        long totalCount = p.getTotalCount();
156        Object k = p.getKey(at);
157        Page split = p.split(at);
158        Object[] keys = { k };
159        Page.PageReference[] children = {
160                new Page.PageReference(p, p.getPos(), p.getTotalCount()),
161                new Page.PageReference(split, split.getPos(), split.getTotalCount()),
162        };
163        p = Page.create(this, writeVersion,
164                keys, null,
165                children,
166                totalCount, 0);
167        return p;
168    }
169 
170    /**
171     * Add or update a key-value pair.
172     *
173     * @param p the page
174     * @param writeVersion the write version
175     * @param key the key (may not be null)
176     * @param value the value (may not be null)
177     * @return the old value, or null
178     */
179    protected Object put(Page p, long writeVersion, Object key, Object value) {
180        int index = p.binarySearch(key);
181        if (p.isLeaf()) {
182            if (index < 0) {
183                index = -index - 1;
184                p.insertLeaf(index, key, value);
185                return null;
186            }
187            return p.setValue(index, value);
188        }
189        // p is a node
190        if (index < 0) {
191            index = -index - 1;
192        } else {
193            index++;
194        }
195        Page c = p.getChildPage(index).copy(writeVersion);
196        if (c.getMemory() > store.getPageSplitSize() && c.getKeyCount() > 1) {
197            // split on the way down
198            int at = c.getKeyCount() / 2;
199            Object k = c.getKey(at);
200            Page split = c.split(at);
201            p.setChild(index, split);
202            p.insertNode(index, k, c);
203            // now we are not sure where to add
204            return put(p, writeVersion, key, value);
205        }
206        Object result = put(c, writeVersion, key, value);
207        p.setChild(index, c);
208        return result;
209    }
210 
211    /**
212     * Get the first key, or null if the map is empty.
213     *
214     * @return the first key, or null
215     */
216    public K firstKey() {
217        return getFirstLast(true);
218    }
219 
220    /**
221     * Get the last key, or null if the map is empty.
222     *
223     * @return the last key, or null
224     */
225    public K lastKey() {
226        return getFirstLast(false);
227    }
228 
229    /**
230     * Get the key at the given index.
231     * <p>
232     * This is a O(log(size)) operation.
233     *
234     * @param index the index
235     * @return the key
236     */
237    @SuppressWarnings("unchecked")
238    public K getKey(long index) {
239        if (index < 0 || index >= size()) {
240            return null;
241        }
242        Page p = root;
243        long offset = 0;
244        while (true) {
245            if (p.isLeaf()) {
246                if (index >= offset + p.getKeyCount()) {
247                    return null;
248                }
249                return (K) p.getKey((int) (index - offset));
250            }
251            int i = 0, size = getChildPageCount(p);
252            for (; i < size; i++) {
253                long c = p.getCounts(i);
254                if (index < c + offset) {
255                    break;
256                }
257                offset += c;
258            }
259            if (i == size) {
260                return null;
261            }
262            p = p.getChildPage(i);
263        }
264    }
265 
266    /**
267     * Get the key list. The list is a read-only representation of all keys.
268     * <p>
269     * The get and indexOf methods are O(log(size)) operations. The result of
270     * indexOf is cast to an int.
271     *
272     * @return the key list
273     */
274    public List<K> keyList() {
275        return new AbstractList<K>() {
276 
277            @Override
278            public K get(int index) {
279                return getKey(index);
280            }
281 
282            @Override
283            public int size() {
284                return MVMap.this.size();
285            }
286 
287            @Override
288            @SuppressWarnings("unchecked")
289            public int indexOf(Object key) {
290                return (int) getKeyIndex((K) key);
291            }
292 
293        };
294    }
295 
296    /**
297     * Get the index of the given key in the map.
298     * <p>
299     * This is a O(log(size)) operation.
300     * <p>
301     * If the key was found, the returned value is the index in the key array.
302     * If not found, the returned value is negative, where -1 means the provided
303     * key is smaller than any keys. See also Arrays.binarySearch.
304     *
305     * @param key the key
306     * @return the index
307     */
308    public long getKeyIndex(K key) {
309        if (size() == 0) {
310            return -1;
311        }
312        Page p = root;
313        long offset = 0;
314        while (true) {
315            int x = p.binarySearch(key);
316            if (p.isLeaf()) {
317                if (x < 0) {
318                    return -offset + x;
319                }
320                return offset + x;
321            }
322            if (x < 0) {
323                x = -x - 1;
324            } else {
325                x++;
326            }
327            for (int i = 0; i < x; i++) {
328                offset += p.getCounts(i);
329            }
330            p = p.getChildPage(x);
331        }
332    }
333 
334    /**
335     * Get the first (lowest) or last (largest) key.
336     *
337     * @param first whether to retrieve the first key
338     * @return the key, or null if the map is empty
339     */
340    @SuppressWarnings("unchecked")
341    protected K getFirstLast(boolean first) {
342        if (size() == 0) {
343            return null;
344        }
345        Page p = root;
346        while (true) {
347            if (p.isLeaf()) {
348                return (K) p.getKey(first ? 0 : p.getKeyCount() - 1);
349            }
350            p = p.getChildPage(first ? 0 : getChildPageCount(p) - 1);
351        }
352    }
353 
354    /**
355     * Get the smallest key that is larger than the given key, or null if no
356     * such key exists.
357     *
358     * @param key the key
359     * @return the result
360     */
361    public K higherKey(K key) {
362        return getMinMax(key, false, true);
363    }
364 
365    /**
366     * Get the smallest key that is larger or equal to this key.
367     *
368     * @param key the key
369     * @return the result
370     */
371    public K ceilingKey(K key) {
372        return getMinMax(key, false, false);
373    }
374 
375    /**
376     * Get the largest key that is smaller or equal to this key.
377     *
378     * @param key the key
379     * @return the result
380     */
381    public K floorKey(K key) {
382        return getMinMax(key, true, false);
383    }
384 
385    /**
386     * Get the largest key that is smaller than the given key, or null if no
387     * such key exists.
388     *
389     * @param key the key
390     * @return the result
391     */
392    public K lowerKey(K key) {
393        return getMinMax(key, true, true);
394    }
395 
396    /**
397     * Get the smallest or largest key using the given bounds.
398     *
399     * @param key the key
400     * @param min whether to retrieve the smallest key
401     * @param excluding if the given upper/lower bound is exclusive
402     * @return the key, or null if no such key exists
403     */
404    protected K getMinMax(K key, boolean min, boolean excluding) {
405        return getMinMax(root, key, min, excluding);
406    }
407 
408    @SuppressWarnings("unchecked")
409    private K getMinMax(Page p, K key, boolean min, boolean excluding) {
410        if (p.isLeaf()) {
411            int x = p.binarySearch(key);
412            if (x < 0) {
413                x = -x - (min ? 2 : 1);
414            } else if (excluding) {
415                x += min ? -1 : 1;
416            }
417            if (x < 0 || x >= p.getKeyCount()) {
418                return null;
419            }
420            return (K) p.getKey(x);
421        }
422        int x = p.binarySearch(key);
423        if (x < 0) {
424            x = -x - 1;
425        } else {
426            x++;
427        }
428        while (true) {
429            if (x < 0 || x >= getChildPageCount(p)) {
430                return null;
431            }
432            K k = getMinMax(p.getChildPage(x), key, min, excluding);
433            if (k != null) {
434                return k;
435            }
436            x += min ? -1 : 1;
437        }
438    }
439 
440 
441    /**
442     * Get a value.
443     *
444     * @param key the key
445     * @return the value, or null if not found
446     */
447    @Override
448    @SuppressWarnings("unchecked")
449    public V get(Object key) {
450        return (V) binarySearch(root, key);
451    }
452 
453    /**
454     * Get the value for the given key, or null if not found.
455     *
456     * @param p the page
457     * @param key the key
458     * @return the value or null
459     */
460    protected Object binarySearch(Page p, Object key) {
461        int x = p.binarySearch(key);
462        if (!p.isLeaf()) {
463            if (x < 0) {
464                x = -x - 1;
465            } else {
466                x++;
467            }
468            p = p.getChildPage(x);
469            return binarySearch(p, key);
470        }
471        if (x >= 0) {
472            return p.getValue(x);
473        }
474        return null;
475    }
476 
477    @Override
478    public boolean containsKey(Object key) {
479        return get(key) != null;
480    }
481 
482    /**
483     * Get the value for the given key, or null if not found.
484     *
485     * @param p the parent page
486     * @param key the key
487     * @return the page or null
488     */
489    protected Page binarySearchPage(Page p, Object key) {
490        int x = p.binarySearch(key);
491        if (!p.isLeaf()) {
492            if (x < 0) {
493                x = -x - 1;
494            } else {
495                x++;
496            }
497            p = p.getChildPage(x);
498            return binarySearchPage(p, key);
499        }
500        if (x >= 0) {
501            return p;
502        }
503        return null;
504    }
505 
506    /**
507     * Remove all entries.
508     */
509    @Override
510    public synchronized void clear() {
511        beforeWrite();
512        root.removeAllRecursive();
513        newRoot(Page.createEmpty(this, writeVersion));
514    }
515 
516    /**
517     * Close the map. Accessing the data is still possible (to allow concurrent
518     * reads), but it is marked as closed.
519     */
520    void close() {
521        closed = true;
522    }
523 
524    public boolean isClosed() {
525        return closed;
526    }
527 
528    /**
529     * Remove a key-value pair, if the key exists.
530     *
531     * @param key the key (may not be null)
532     * @return the old value if the key existed, or null otherwise
533     */
534    @Override
535    @SuppressWarnings("unchecked")
536    public V remove(Object key) {
537        beforeWrite();
538        V result = get(key);
539        if (result == null) {
540            return null;
541        }
542        long v = writeVersion;
543        synchronized (this) {
544            Page p = root.copy(v);
545            result = (V) remove(p, v, key);
546            if (!p.isLeaf() && p.getTotalCount() == 0) {
547                p.removePage();
548                p = Page.createEmpty(this,  p.getVersion());
549            }
550            newRoot(p);
551        }
552        return result;
553    }
554 
555    /**
556     * Add a key-value pair if it does not yet exist.
557     *
558     * @param key the key (may not be null)
559     * @param value the new value
560     * @return the old value if the key existed, or null otherwise
561     */
562    @Override
563    public synchronized V putIfAbsent(K key, V value) {
564        V old = get(key);
565        if (old == null) {
566            put(key, value);
567        }
568        return old;
569    }
570 
571    /**
572     * Remove a key-value pair if the value matches the stored one.
573     *
574     * @param key the key (may not be null)
575     * @param value the expected value
576     * @return true if the item was removed
577     */
578    @Override
579    public synchronized boolean remove(Object key, Object value) {
580        V old = get(key);
581        if (areValuesEqual(old, value)) {
582            remove(key);
583            return true;
584        }
585        return false;
586    }
587 
588    /**
589     * Check whether the two values are equal.
590     *
591     * @param a the first value
592     * @param b the second value
593     * @return true if they are equal
594     */
595    public boolean areValuesEqual(Object a, Object b) {
596        if (a == b) {
597            return true;
598        } else if (a == null || b == null) {
599            return false;
600        }
601        return valueType.compare(a, b) == 0;
602    }
603 
604    /**
605     * Replace a value for an existing key, if the value matches.
606     *
607     * @param key the key (may not be null)
608     * @param oldValue the expected value
609     * @param newValue the new value
610     * @return true if the value was replaced
611     */
612    @Override
613    public synchronized boolean replace(K key, V oldValue, V newValue) {
614        V old = get(key);
615        if (areValuesEqual(old, oldValue)) {
616            put(key, newValue);
617            return true;
618        }
619        return false;
620    }
621 
622    /**
623     * Replace a value for an existing key.
624     *
625     * @param key the key (may not be null)
626     * @param value the new value
627     * @return the old value, if the value was replaced, or null
628     */
629    @Override
630    public synchronized V replace(K key, V value) {
631        V old = get(key);
632        if (old != null) {
633            put(key, value);
634            return old;
635        }
636        return null;
637    }
638 
639    /**
640     * Remove a key-value pair.
641     *
642     * @param p the page (may not be null)
643     * @param writeVersion the write version
644     * @param key the key
645     * @return the old value, or null if the key did not exist
646     */
647    protected Object remove(Page p, long writeVersion, Object key) {
648        int index = p.binarySearch(key);
649        Object result = null;
650        if (p.isLeaf()) {
651            if (index >= 0) {
652                result = p.getValue(index);
653                p.remove(index);
654            }
655            return result;
656        }
657        // node
658        if (index < 0) {
659            index = -index - 1;
660        } else {
661            index++;
662        }
663        Page cOld = p.getChildPage(index);
664        Page c = cOld.copy(writeVersion);
665        result = remove(c, writeVersion, key);
666        if (result == null || c.getTotalCount() != 0) {
667            // no change, or
668            // there are more nodes
669            p.setChild(index, c);
670        } else {
671            // this child was deleted
672            if (p.getKeyCount() == 0) {
673                p.setChild(index, c);
674                c.removePage();
675            } else {
676                p.remove(index);
677            }
678        }
679        return result;
680    }
681 
682    /**
683     * Use the new root page from now on.
684     *
685     * @param newRoot the new root page
686     */
687    protected void newRoot(Page newRoot) {
688        if (root != newRoot) {
689            removeUnusedOldVersions();
690            if (root.getVersion() != newRoot.getVersion()) {
691                Page last = oldRoots.peekLast();
692                if (last == null || last.getVersion() != root.getVersion()) {
693                    oldRoots.add(root);
694                }
695            }
696            root = newRoot;
697        }
698    }
699 
700    /**
701     * Compare two keys.
702     *
703     * @param a the first key
704     * @param b the second key
705     * @return -1 if the first key is smaller, 1 if bigger, 0 if equal
706     */
707    int compare(Object a, Object b) {
708        return keyType.compare(a, b);
709    }
710 
711    /**
712     * Get the key type.
713     *
714     * @return the key type
715     */
716    public DataType getKeyType() {
717        return keyType;
718    }
719 
720    /**
721     * Get the value type.
722     *
723     * @return the value type
724     */
725    public DataType getValueType() {
726        return valueType;
727    }
728 
729    /**
730     * Read a page.
731     *
732     * @param pos the position of the page
733     * @return the page
734     */
735    Page readPage(long pos) {
736        return store.readPage(this, pos);
737    }
738 
739    /**
740     * Set the position of the root page.
741     *
742     * @param rootPos the position, 0 for empty
743     * @param version the version of the root
744     */
745    void setRootPos(long rootPos, long version) {
746        root = rootPos == 0 ? Page.createEmpty(this, -1) : readPage(rootPos);
747        root.setVersion(version);
748    }
749 
750    /**
751     * Iterate over a number of keys.
752     *
753     * @param from the first key to return
754     * @return the iterator
755     */
756    public Iterator<K> keyIterator(K from) {
757        return new Cursor<K, V>(this, root, from);
758    }
759 
760    /**
761     * Re-write any pages that belong to one of the chunks in the given set.
762     *
763     * @param set the set of chunk ids
764     * @return whether rewriting was successful
765     */
766    boolean rewrite(Set<Integer> set) {
767        // read from old version, to avoid concurrent reads
768        long previousVersion = store.getCurrentVersion() - 1;
769        if (previousVersion < createVersion) {
770            // a new map
771            return true;
772        }
773        MVMap<K, V> readMap;
774        try {
775            readMap = openVersion(previousVersion);
776        } catch (IllegalArgumentException e) {
777            // unknown version: ok
778            // TODO should not rely on exception handling
779            return true;
780        }
781        try {
782            rewrite(readMap.root, set);
783            return true;
784        } catch (IllegalStateException e) {
785            // TODO should not rely on exception handling
786            if (DataUtils.getErrorCode(e.getMessage()) == DataUtils.ERROR_CHUNK_NOT_FOUND) {
787                // ignore
788                return false;
789            }
790            throw e;
791        }
792    }
793 
794    private int rewrite(Page p, Set<Integer> set) {
795        if (p.isLeaf()) {
796            long pos = p.getPos();
797            int chunkId = DataUtils.getPageChunkId(pos);
798            if (!set.contains(chunkId)) {
799                return 0;
800            }
801            if (p.getKeyCount() > 0) {
802                @SuppressWarnings("unchecked")
803                K key = (K) p.getKey(0);
804                V value = get(key);
805                if (value != null) {
806                    replace(key, value, value);
807                }
808            }
809            return 1;
810        }
811        int writtenPageCount = 0;
812        for (int i = 0; i < getChildPageCount(p); i++) {
813            long childPos = p.getChildPagePos(i);
814            if (childPos != 0 && DataUtils.getPageType(childPos) == DataUtils.PAGE_TYPE_LEAF) {
815                // we would need to load the page, and it's a leaf:
816                // only do that if it's within the set of chunks we are
817                // interested in
818                int chunkId = DataUtils.getPageChunkId(childPos);
819                if (!set.contains(chunkId)) {
820                    continue;
821                }
822            }
823            writtenPageCount += rewrite(p.getChildPage(i), set);
824        }
825        if (writtenPageCount == 0) {
826            long pos = p.getPos();
827            int chunkId = DataUtils.getPageChunkId(pos);
828            if (set.contains(chunkId)) {
829                // an inner node page that is in one of the chunks,
830                // but only points to chunks that are not in the set:
831                // if no child was changed, we need to do that now
832                // (this is not needed if anyway one of the children
833                // was changed, as this would have updated this
834                // page as well)
835                Page p2 = p;
836                while (!p2.isLeaf()) {
837                    p2 = p2.getChildPage(0);
838                }
839                @SuppressWarnings("unchecked")
840                K key = (K) p2.getKey(0);
841                V value = get(key);
842                if (value != null) {
843                    replace(key, value, value);
844                }
845                writtenPageCount++;
846            }
847        }
848        return writtenPageCount;
849    }
850 
851    /**
852     * Get a cursor to iterate over a number of keys and values.
853     *
854     * @param from the first key to return
855     * @return the cursor
856     */
857    public Cursor<K, V> cursor(K from) {
858        return new Cursor<K, V>(this, root, from);
859    }
860 
861    @Override
862    public Set<Map.Entry<K, V>> entrySet() {
863        final MVMap<K, V> map = this;
864        final Page root = this.root;
865        return new AbstractSet<Entry<K, V>>() {
866 
867            @Override
868            public Iterator<Entry<K, V>> iterator() {
869                final Cursor<K, V> cursor = new Cursor<K, V>(map, root, null);
870                return new Iterator<Entry<K, V>>() {
871 
872                    @Override
873                    public boolean hasNext() {
874                        return cursor.hasNext();
875                    }
876 
877                    @Override
878                    public Entry<K, V> next() {
879                        K k = cursor.next();
880                        return new DataUtils.MapEntry<K, V>(k, cursor.getValue());
881                    }
882 
883                    @Override
884                    public void remove() {
885                        throw DataUtils.newUnsupportedOperationException(
886                                "Removing is not supported");
887                    }
888                };
889 
890            }
891 
892            @Override
893            public int size() {
894                return MVMap.this.size();
895            }
896 
897            @Override
898            public boolean contains(Object o) {
899                return MVMap.this.containsKey(o);
900            }
901 
902        };
903 
904    }
905 
906    @Override
907    public Set<K> keySet() {
908        final MVMap<K, V> map = this;
909        final Page root = this.root;
910        return new AbstractSet<K>() {
911 
912            @Override
913            public Iterator<K> iterator() {
914                return new Cursor<K, V>(map, root, null);
915            }
916 
917            @Override
918            public int size() {
919                return MVMap.this.size();
920            }
921 
922            @Override
923            public boolean contains(Object o) {
924                return MVMap.this.containsKey(o);
925            }
926 
927        };
928    }
929 
930    /**
931     * Get the root page.
932     *
933     * @return the root page
934     */
935    public Page getRoot() {
936        return root;
937    }
938 
939    /**
940     * Get the map name.
941     *
942     * @return the name
943     */
944    public String getName() {
945        return store.getMapName(id);
946    }
947 
948    public MVStore getStore() {
949        return store;
950    }
951 
952    /**
953     * Get the map id. Please note the map id may be different after compacting
954     * a store.
955     *
956     * @return the map id
957     */
958    public int getId() {
959        return id;
960    }
961 
962    /**
963     * Rollback to the given version.
964     *
965     * @param version the version
966     */
967    void rollbackTo(long version) {
968        beforeWrite();
969        if (version <= createVersion) {
970            // the map is removed later
971        } else if (root.getVersion() >= version) {
972            while (true) {
973                Page last = oldRoots.peekLast();
974                if (last == null) {
975                    break;
976                }
977                // slow, but rollback is not a common operation
978                oldRoots.removeLast(last);
979                root = last;
980                if (root.getVersion() < version) {
981                    break;
982                }
983            }
984        }
985    }
986 
987    /**
988     * Forget those old versions that are no longer needed.
989     */
990    void removeUnusedOldVersions() {
991        long oldest = store.getOldestVersionToKeep();
992        if (oldest == -1) {
993            return;
994        }
995        Page last = oldRoots.peekLast();
996        while (true) {
997            Page p = oldRoots.peekFirst();
998            if (p == null || p.getVersion() >= oldest || p == last) {
999                break;
1000            }
1001            oldRoots.removeFirst(p);
1002        }
1003    }
1004 
1005    public boolean isReadOnly() {
1006        return readOnly;
1007    }
1008 
1009    /**
1010     * Set the volatile flag of the map.
1011     *
1012     * @param isVolatile the volatile flag
1013     */
1014    public void setVolatile(boolean isVolatile) {
1015        this.isVolatile = isVolatile;
1016    }
1017 
1018    /**
1019     * Whether this is volatile map, meaning that changes
1020     * are not persisted. By default (even if the store is not persisted),
1021     * maps are not volatile.
1022     *
1023     * @return whether this map is volatile
1024     */
1025    public boolean isVolatile() {
1026        return isVolatile;
1027    }
1028 
1029    /**
1030     * This method is called before writing to the map. The default
1031     * implementation checks whether writing is allowed, and tries
1032     * to detect concurrent modification.
1033     *
1034     * @throws UnsupportedOperationException if the map is read-only,
1035     *      or if another thread is concurrently writing
1036     */
1037    protected void beforeWrite() {
1038        if (closed) {
1039            throw DataUtils.newIllegalStateException(
1040                    DataUtils.ERROR_CLOSED, "This map is closed");
1041        }
1042        if (readOnly) {
1043            throw DataUtils.newUnsupportedOperationException(
1044                    "This map is read-only");
1045        }
1046        store.beforeWrite(this);
1047    }
1048 
1049    @Override
1050    public int hashCode() {
1051        return id;
1052    }
1053 
1054    @Override
1055    public boolean equals(Object o) {
1056        return this == o;
1057    }
1058 
1059    /**
1060     * Get the number of entries, as a integer. Integer.MAX_VALUE is returned if
1061     * there are more than this entries.
1062     *
1063     * @return the number of entries, as an integer
1064     */
1065    @Override
1066    public int size() {
1067        long size = sizeAsLong();
1068        return size > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) size;
1069    }
1070 
1071    /**
1072     * Get the number of entries, as a long.
1073     *
1074     * @return the number of entries
1075     */
1076    public long sizeAsLong() {
1077        return root.getTotalCount();
1078    }
1079 
1080    @Override
1081    public boolean isEmpty() {
1082        // could also use (sizeAsLong() == 0)
1083        return root.isLeaf() && root.getKeyCount() == 0;
1084    }
1085 
1086    public long getCreateVersion() {
1087        return createVersion;
1088    }
1089 
1090    /**
1091     * Remove the given page (make the space available).
1092     *
1093     * @param pos the position of the page to remove
1094     * @param memory the number of bytes used for this page
1095     */
1096    protected void removePage(long pos, int memory) {
1097        store.removePage(this, pos, memory);
1098    }
1099 
1100    /**
1101     * Open an old version for the given map.
1102     *
1103     * @param version the version
1104     * @return the map
1105     */
1106    public MVMap<K, V> openVersion(long version) {
1107        if (readOnly) {
1108            throw DataUtils.newUnsupportedOperationException(
1109                    "This map is read-only; need to call " +
1110                    "the method on the writable map");
1111        }
1112        DataUtils.checkArgument(version >= createVersion,
1113                "Unknown version {0}; this map was created in version is {1}",
1114                version, createVersion);
1115        Page newest = null;
1116        // need to copy because it can change
1117        Page r = root;
1118        if (version >= r.getVersion() &&
1119                (version == writeVersion ||
1120                r.getVersion() >= 0 ||
1121                version <= createVersion ||
1122                store.getFileStore() == null)) {
1123            newest = r;
1124        } else {
1125            Page last = oldRoots.peekFirst();
1126            if (last == null || version < last.getVersion()) {
1127                // smaller than all in-memory versions
1128                return store.openMapVersion(version, id, this);
1129            }
1130            Iterator<Page> it = oldRoots.iterator();
1131            while (it.hasNext()) {
1132                Page p = it.next();
1133                if (p.getVersion() > version) {
1134                    break;
1135                }
1136                last = p;
1137            }
1138            newest = last;
1139        }
1140        MVMap<K, V> m = openReadOnly();
1141        m.root = newest;
1142        return m;
1143    }
1144 
1145    /**
1146     * Open a copy of the map in read-only mode.
1147     *
1148     * @return the opened map
1149     */
1150    MVMap<K, V> openReadOnly() {
1151        MVMap<K, V> m = new MVMap<K, V>(keyType, valueType);
1152        m.readOnly = true;
1153        HashMap<String, Object> config = New.hashMap();
1154        config.put("id", id);
1155        config.put("createVersion", createVersion);
1156        m.init(store, config);
1157        m.root = root;
1158        return m;
1159    }
1160 
1161    public long getVersion() {
1162        return root.getVersion();
1163    }
1164 
1165    /**
1166     * Get the child page count for this page. This is to allow another map
1167     * implementation to override the default, in case the last child is not to
1168     * be used.
1169     *
1170     * @param p the page
1171     * @return the number of direct children
1172     */
1173    protected int getChildPageCount(Page p) {
1174        return p.getRawChildPageCount();
1175    }
1176 
1177    /**
1178     * Get the map type. When opening an existing map, the map type must match.
1179     *
1180     * @return the map type
1181     */
1182    public String getType() {
1183        return null;
1184    }
1185 
1186    /**
1187     * Get the map metadata as a string.
1188     *
1189     * @param name the map name (or null)
1190     * @return the string
1191     */
1192    String asString(String name) {
1193        StringBuilder buff = new StringBuilder();
1194        if (name != null) {
1195            DataUtils.appendMap(buff, "name", name);
1196        }
1197        if (createVersion != 0) {
1198            DataUtils.appendMap(buff, "createVersion", createVersion);
1199        }
1200        String type = getType();
1201        if (type != null) {
1202            DataUtils.appendMap(buff, "type", type);
1203        }
1204        return buff.toString();
1205    }
1206 
1207    void setWriteVersion(long writeVersion) {
1208        this.writeVersion = writeVersion;
1209    }
1210 
1211    /**
1212     * Copy a map. All pages are copied.
1213     *
1214     * @param sourceMap the source map
1215     */
1216    void copyFrom(MVMap<K, V> sourceMap) {
1217        beforeWrite();
1218        newRoot(copy(sourceMap.root, null));
1219    }
1220 
1221    private Page copy(Page source, CursorPos parent) {
1222        Page target = Page.create(this, writeVersion, source);
1223        if (source.isLeaf()) {
1224            Page child = target;
1225            for (CursorPos p = parent; p != null; p = p.parent) {
1226                p.page.setChild(p.index, child);
1227                p.page = p.page.copy(writeVersion);
1228                child = p.page;
1229                if (p.parent == null) {
1230                    newRoot(p.page);
1231                    beforeWrite();
1232                }
1233            }
1234        } else {
1235            // temporarily, replace child pages with empty pages,
1236            // to ensure there are no links to the old store
1237            for (int i = 0; i < getChildPageCount(target); i++) {
1238                target.setChild(i, null);
1239            }
1240            CursorPos pos = new CursorPos(target, 0, parent);
1241            for (int i = 0; i < getChildPageCount(target); i++) {
1242                pos.index = i;
1243                long p = source.getChildPagePos(i);
1244                if (p != 0) {
1245                    // p == 0 means no child
1246                    // (for example the last entry of an r-tree node)
1247                    // (the MVMap is also used for r-trees for compacting)
1248                    copy(source.getChildPage(i), pos);
1249                }
1250            }
1251            target = pos.page;
1252        }
1253        return target;
1254    }
1255 
1256    @Override
1257    public String toString() {
1258        return asString(null);
1259    }
1260 
1261    /**
1262     * A builder for maps.
1263     *
1264     * @param <M> the map type
1265     * @param <K> the key type
1266     * @param <V> the value type
1267     */
1268    public interface MapBuilder<M extends MVMap<K, V>, K, V> {
1269 
1270        /**
1271         * Create a new map of the given type.
1272         *
1273         * @return the map
1274         */
1275        M create();
1276 
1277    }
1278 
1279    /**
1280     * A builder for this class.
1281     *
1282     * @param <K> the key type
1283     * @param <V> the value type
1284     */
1285    public static class Builder<K, V> implements MapBuilder<MVMap<K, V>, K, V> {
1286 
1287        protected DataType keyType;
1288        protected DataType valueType;
1289 
1290        /**
1291         * Create a new builder with the default key and value data types.
1292         */
1293        public Builder() {
1294            // ignore
1295        }
1296 
1297        /**
1298         * Set the key data type.
1299         *
1300         * @param keyType the key type
1301         * @return this
1302         */
1303        public Builder<K, V> keyType(DataType keyType) {
1304            this.keyType = keyType;
1305            return this;
1306        }
1307 
1308        public DataType getKeyType() {
1309            return keyType;
1310        }
1311 
1312        public DataType getValueType() {
1313            return valueType;
1314        }
1315 
1316        /**
1317         * Set the value data type.
1318         *
1319         * @param valueType the value type
1320         * @return this
1321         */
1322        public Builder<K, V> valueType(DataType valueType) {
1323            this.valueType = valueType;
1324            return this;
1325        }
1326 
1327        @Override
1328        public MVMap<K, V> create() {
1329            if (keyType == null) {
1330                keyType = new ObjectDataType();
1331            }
1332            if (valueType == null) {
1333                valueType = new ObjectDataType();
1334            }
1335            return new MVMap<K, V>(keyType, valueType);
1336        }
1337 
1338    }
1339 
1340}

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