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 | */ |
6 | package org.h2.mvstore; |
7 | |
8 | import java.util.AbstractList; |
9 | import java.util.AbstractMap; |
10 | import java.util.AbstractSet; |
11 | import java.util.HashMap; |
12 | import java.util.Iterator; |
13 | import java.util.List; |
14 | import java.util.Map; |
15 | import java.util.Set; |
16 | import java.util.concurrent.ConcurrentMap; |
17 | |
18 | import org.h2.mvstore.type.DataType; |
19 | import org.h2.mvstore.type.ObjectDataType; |
20 | import 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 | */ |
37 | public 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 | } |