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.nio.ByteBuffer; |
9 | import java.util.Arrays; |
10 | import java.util.HashSet; |
11 | import java.util.Set; |
12 | |
13 | import org.h2.compress.Compressor; |
14 | import org.h2.mvstore.type.DataType; |
15 | import 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 | */ |
34 | public 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 | } |