File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\mvstore\Page.java.html

1 /*
2 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
3 * Version 1.0, and under the Eclipse Public License, Version 1.0
4 * (http://h2database.com/html/license.html).
5 * Initial Developer: H2 Group
6 */
7 package org.h2.mvstore;
8
9 import java.io.IOException;
10 import java.nio.ByteBuffer;
11 import java.nio.channels.FileChannel;
12 import java.util.Arrays;
13 import org.h2.compress.Compressor;
14 import org.h2.mvstore.type.DataType;
15
16 /**
17 * A page (a node or a leaf).
18 * <p>
19 * For b-tree nodes, the key at a given index is larger than the largest key of
20 * the child at the same index.
21 * <p>
22 * File format:
23 * page length (including length): int
24 * check value: short
25 * map id: varInt
26 * number of keys: varInt
27 * type: byte (0: leaf, 1: node; +2: compressed)
28 * compressed: bytes saved (varInt)
29 * keys
30 * leaf: values (one for each key)
31 * node: children (1 more than keys)
32 */
33 public class Page {
34
35 private static final int SHARED_KEYS = 1, SHARED_VALUES = 2, SHARED_CHILDREN = 4, SHARED_COUNTS = 8;
36
37 private static final Object[] EMPTY_OBJECT_ARRAY = new Object[0];
38
39 private final MVMap<?, ?> map;
40 private long version;
41 private long pos;
42 private long totalCount;
43 private int keyCount;
44
45 /**
46 * The last result of a find operation is cached.
47 */
48 private int cachedCompare;
49
50 /**
51 * Which arrays are shared with another version of this page.
52 */
53 private int sharedFlags;
54
55 /**
56 * The estimated memory used.
57 */
58 private int memory;
59
60 private Object[] keys;
61 private Object[] values;
62 private long[] children;
63 private Page[] childrenPages;
64 private long[] counts;
65
66 Page(MVMap<?, ?> map, long version) {
67 this.map = map;
68 this.version = version;
69 }
70
71 /**
72 * Create a new, empty page.
73 *
74 * @param map the map
75 * @param version the version
76 * @return the new page
77 */
78 public static Page createEmpty(MVMap<?, ?> map, long version) {
79 return create(map, version, 0,
80 EMPTY_OBJECT_ARRAY, EMPTY_OBJECT_ARRAY,
81 null, null, null, 0, 0, DataUtils.PAGE_MEMORY);
82 }
83
84 /**
85 * Create a new page. The arrays are not cloned.
86 *
87 * @param map the map
88 * @param version the version
89 * @param keyCount the number of keys
90 * @param keys the keys
91 * @param values the values
92 * @param children the children
93 * @param childrenPages the children pages
94 * @param counts the children counts
95 * @param totalCount the total number of keys
96 * @param sharedFlags which arrays are shared
97 * @param memory the memory used in bytes
98 * @return the page
99 */
100 public static Page create(MVMap<?, ?> map, long version,
101 int keyCount, Object[] keys,
102 Object[] values, long[] children, Page[] childrenPages, long[] counts,
103 long totalCount, int sharedFlags, int memory) {
104 Page p = new Page(map, version);
105 // the position is 0
106 p.keys = keys;
107 p.keyCount = keyCount;
108 p.values = values;
109 p.children = children;
110 p.childrenPages = childrenPages;
111 p.counts = counts;
112 p.totalCount = totalCount;
113 p.sharedFlags = sharedFlags;
114 p.memory = memory == 0 ? p.calculateMemory() : memory;
115 return p;
116 }
117
118 /**
119 * Read a page.
120 *
121 * @param file the file
122 * @param map the map
123 * @param pos the page position
124 * @param filePos the position in the file
125 * @param fileSize the file size (to avoid reading past EOF)
126 * @return the page
127 */
128 static Page read(FileChannel file, MVMap<?, ?> map,
129 long pos, long filePos, long fileSize) {
130 ByteBuffer buff;
131 int maxLength = DataUtils.getPageMaxLength(pos);
132 try {
133 maxLength = (int) Math.min(fileSize - filePos, maxLength);
134 int length = maxLength;
135 if (maxLength == Integer.MAX_VALUE) {
136 buff = ByteBuffer.allocate(128);
137 DataUtils.readFully(file, filePos, buff);
138 maxLength = buff.getInt();
139 //read the first bytes again
140 }
141 buff = ByteBuffer.allocate(length);
142 DataUtils.readFully(file, filePos, buff);
143 } catch (IOException e) {
144 throw new RuntimeException(e);
145 }
146 Page p = new Page(map, 0);
147 p.pos = pos;
148 int chunkId = DataUtils.getPageChunkId(pos);
149 int offset = DataUtils.getPageOffset(pos);
150 p.read(buff, chunkId, offset, maxLength);
151 return p;
152 }
153
154 /**
155 * Get the key at the given index.
156 *
157 * @param index the index
158 * @return the key
159 */
160 public Object getKey(int index) {
161 return keys[index];
162 }
163
164 /**
165 * Get the child page at the given index.
166 *
167 * @param index the index
168 * @return the child page
169 */
170 public Page getChildPage(int index) {
171 Page p = childrenPages[index];
172 return p != null ? p : map.readPage(children[index]);
173 }
174
175 /**
176 * Get the position of the child page at the given index.
177 *
178 * @param index the index
179 * @return the position
180 */
181 long getChildPagePos(int index) {
182 return children[index];
183 }
184
185 /**
186 * Get the value at the given index.
187 *
188 * @param index the index
189 * @return the value
190 */
191 public Object getValue(int index) {
192 return values[index];
193 }
194
195 /**
196 * Get the number of keys in this page.
197 *
198 * @return the number of keys
199 */
200 public int getKeyCount() {
201 return keyCount;
202 }
203
204 /**
205 * Check whether this is a leaf page.
206 *
207 * @return true if it is a leaf
208 */
209 public boolean isLeaf() {
210 return children == null;
211 }
212
213 /**
214 * Get the position of the page
215 *
216 * @return the position
217 */
218 public long getPos() {
219 return pos;
220 }
221
222 public String toString() {
223 StringBuilder buff = new StringBuilder();
224 buff.append("pos: ").append(pos).append("\n");
225 for (int i = 0; i <= keyCount; i++) {
226 if (i > 0) {
227 buff.append(" ");
228 }
229 if (children != null) {
230 buff.append("[" + children[i] + "] ");
231 }
232 if (i < keyCount) {
233 buff.append(keys[i]);
234 if (values != null) {
235 buff.append(':');
236 buff.append(values[i]);
237 }
238 }
239 }
240 return buff.toString();
241 }
242
243 /**
244 * Create a copy of this page, if the write version is higher than the
245 * current version.
246 *
247 * @param writeVersion the write version
248 * @return a page with the given write version
249 */
250 public Page copyOnWrite(long writeVersion) {
251 if (version == writeVersion) {
252 return this;
253 }
254 map.getStore().removePage(pos);
255 Page newPage = create(map, writeVersion,
256 keyCount, keys, values, children, childrenPages,
257 counts, totalCount,
258 SHARED_KEYS | SHARED_VALUES | SHARED_CHILDREN | SHARED_COUNTS,
259 memory);
260 map.getStore().registerUnsavedPage();
261 newPage.cachedCompare = cachedCompare;
262 return newPage;
263 }
264
265 /**
266 * Search the key in this page using a binary search. Instead of always
267 * starting the search in the middle, the last found index is cached.
268 * <p>
269 * If the key was found, the returned value is the index in the key array.
270 * If not found, the returned value is negative, where -1 means the provided
271 * key is smaller than any keys in this page. See also Arrays.binarySearch.
272 *
273 * @param key the key
274 * @return the value or null
275 */
276 public int binarySearch(Object key) {
277 int low = 0, high = keyCount - 1;
278 int x = cachedCompare - 1;
279 if (x < 0 || x > high) {
280 x = (low + high) >>> 1;
281 }
282 Object[] k = keys;
283 while (low <= high) {
284 int compare = map.compare(key, k[x]);
285 if (compare > 0) {
286 low = x + 1;
287 } else if (compare < 0) {
288 high = x - 1;
289 } else {
290 cachedCompare = x + 1;
291 return x;
292 }
293 x = (low + high) >>> 1;
294 }
295 cachedCompare = low;
296 return -(low + 1);
297
298 // regular binary search (without caching)
299 // int low = 0, high = keyCount - 1;
300 // while (low <= high) {
301 // int x = (low + high) >>> 1;
302 // int compare = map.compare(key, keys[x]);
303 // if (compare > 0) {
304 // low = x + 1;
305 // } else if (compare < 0) {
306 // high = x - 1;
307 // } else {
308 // return x;
309 // }
310 // }
311 // return -(low + 1);
312 }
313
314 /**
315 * Split the page. This modifies the current page.
316 *
317 * @param at the split index
318 * @return the page with the entries after the split index
319 */
320 public Page split(int at) {
321 return isLeaf() ? splitLeaf(at) : splitNode(at);
322 }
323
324 private Page splitLeaf(int at) {
325 int a = at, b = keyCount - a;
326 Object[] aKeys = new Object[a];
327 Object[] bKeys = new Object[b];
328 System.arraycopy(keys, 0, aKeys, 0, a);
329 System.arraycopy(keys, a, bKeys, 0, b);
330 keys = aKeys;
331 keyCount = a;
332 Object[] aValues = new Object[a];
333 Object[] bValues = new Object[b];
334 bValues = new Object[b];
335 System.arraycopy(values, 0, aValues, 0, a);
336 System.arraycopy(values, a, bValues, 0, b);
337 values = aValues;
338 sharedFlags &= ~(SHARED_KEYS | SHARED_VALUES);
339 totalCount = a;
340 Page newPage = create(map, version, b,
341 bKeys, bValues, null, null, null,
342 bKeys.length, 0, 0);
343 map.getStore().registerUnsavedPage();
344 memory = calculateMemory();
345 newPage.memory = newPage.calculateMemory();
346 return newPage;
347 }
348
349 private Page splitNode(int at) {
350 int a = at, b = keyCount - a;
351
352 Object[] aKeys = new Object[a];
353 Object[] bKeys = new Object[b - 1];
354 System.arraycopy(keys, 0, aKeys, 0, a);
355 System.arraycopy(keys, a + 1, bKeys, 0, b - 1);
356 keys = aKeys;
357 keyCount = a;
358
359 long[] aChildren = new long[a + 1];
360 long[] bChildren = new long[b];
361 System.arraycopy(children, 0, aChildren, 0, a + 1);
362 System.arraycopy(children, a + 1, bChildren, 0, b);
363 children = aChildren;
364
365 Page[] aChildrenPages = new Page[a + 1];
366 Page[] bChildrenPages = new Page[b];
367 System.arraycopy(childrenPages, 0, aChildrenPages, 0, a + 1);
368 System.arraycopy(childrenPages, a + 1, bChildrenPages, 0, b);
369 childrenPages = aChildrenPages;
370
371 long[] aCounts = new long[a + 1];
372 long[] bCounts = new long[b];
373 System.arraycopy(counts, 0, aCounts, 0, a + 1);
374 System.arraycopy(counts, a + 1, bCounts, 0, b);
375 counts = aCounts;
376
377 sharedFlags &= ~(SHARED_KEYS | SHARED_CHILDREN | SHARED_COUNTS);
378 long t = 0;
379 for (long x : aCounts) {
380 t += x;
381 }
382 totalCount = t;
383 t = 0;
384 for (long x : bCounts) {
385 t += x;
386 }
387 Page newPage = create(map, version, b - 1,
388 bKeys, null, bChildren, bChildrenPages,
389 bCounts, t, 0, 0);
390 map.getStore().registerUnsavedPage();
391 memory = calculateMemory();
392 newPage.memory = newPage.calculateMemory();
393 return newPage;
394 }
395
396 /**
397 * Get the total number of key-value pairs, including child pages.
398 *
399 * @return the number of key-value pairs
400 */
401 public long getTotalCount() {
402 if (MVStore.ASSERT) {
403 long check = 0;
404 if (isLeaf()) {
405 check = keyCount;
406 } else {
407 for (long x : counts) {
408 check += x;
409 }
410 }
411 if (check != totalCount) {
412 throw new AssertionError("Expected: " + check + " got: "
413 + totalCount);
414 }
415 }
416 return totalCount;
417 }
418
419 /**
420 * Get the descendant counts for the given child.
421 *
422 * @param index the child index
423 * @return the descendant count
424 */
425 long getCounts(int index) {
426 return counts[index];
427 }
428
429 /**
430 * Replace the child page.
431 *
432 * @param index the index
433 * @param c the new child page
434 */
435 public void setChild(int index, Page c) {
436 if (c != childrenPages[index] || c.getPos() != children[index]) {
437 if ((sharedFlags & SHARED_CHILDREN) != 0) {
438 children = Arrays.copyOf(children, children.length);
439 childrenPages = Arrays.copyOf(childrenPages, childrenPages.length);
440 sharedFlags &= ~SHARED_CHILDREN;
441 }
442 children[index] = c.getPos();
443 childrenPages[index] = c;
444 }
445 if (c.getTotalCount() != counts[index]) {
446 if ((sharedFlags & SHARED_COUNTS) != 0) {
447 counts = Arrays.copyOf(counts, counts.length);
448 sharedFlags &= ~SHARED_COUNTS;
449 }
450 long oldCount = counts[index];
451 counts[index] = c.getTotalCount();
452 totalCount += counts[index] - oldCount;
453 }
454 }
455
456 /**
457 * Replace the key.
458 *
459 * @param index the index
460 * @param key the new key
461 */
462 public void setKey(int index, Object key) {
463 if ((sharedFlags & SHARED_KEYS) != 0) {
464 keys = Arrays.copyOf(keys, keys.length);
465 sharedFlags &= ~SHARED_KEYS;
466 }
467 Object old = keys[index];
468 if (old != null) {
469 memory -= map.getKeyType().getMemory(old);
470 }
471 memory += map.getKeyType().getMemory(key);
472 keys[index] = key;
473 }
474
475 /**
476 * Replace the value.
477 *
478 * @param index the index
479 * @param value the new value
480 * @return the old value
481 */
482 public Object setValue(int index, Object value) {
483 Object old = values[index];
484 if ((sharedFlags & SHARED_VALUES) != 0) {
485 values = Arrays.copyOf(values, values.length);
486 sharedFlags &= ~SHARED_VALUES;
487 }
488 memory -= map.getValueType().getMemory(old);
489 memory += map.getValueType().getMemory(value);
490 values[index] = value;
491 return old;
492 }
493
494 /**
495 * Remove this page and all child pages.
496 */
497 void removeAllRecursive() {
498 if (children != null) {
499 for (int i = 0, size = children.length; i < size; i++) {
500 Page p = childrenPages[i];
501 if (p != null) {
502 p.removeAllRecursive();
503 } else {
504 long c = children[i];
505 int type = DataUtils.getPageType(c);
506 if (type == DataUtils.PAGE_TYPE_LEAF) {
507 map.getStore().removePage(c);
508 } else {
509 map.readPage(c).removeAllRecursive();
510 }
511 }
512 }
513 }
514 map.getStore().removePage(pos);
515 }
516
517 /**
518 * Insert a key-value pair into this leaf.
519 *
520 * @param index the index
521 * @param key the key
522 * @param value the value
523 */
524 public void insertLeaf(int index, Object key, Object value) {
525 if (((sharedFlags & SHARED_KEYS) == 0) && keys.length > keyCount + 1) {
526 if (index < keyCount) {
527 System.arraycopy(keys, index, keys, index + 1, keyCount - index);
528 System.arraycopy(values, index, values, index + 1, keyCount - index);
529 }
530 } else {
531 int len = keyCount + 6;
532 Object[] newKeys = new Object[len];
533 DataUtils.copyWithGap(keys, newKeys, keyCount, index);
534 keys = newKeys;
535 Object[] newValues = new Object[len];
536 DataUtils.copyWithGap(values, newValues, keyCount, index);
537 values = newValues;
538 }
539 keys[index] = key;
540 values[index] = value;
541 keyCount++;
542 sharedFlags &= ~(SHARED_KEYS | SHARED_VALUES);
543 totalCount++;
544 memory += map.getKeyType().getMemory(key);
545 memory += map.getValueType().getMemory(value);
546 }
547
548 /**
549 * Insert a child into this node.
550 *
551 * @param index the index
552 * @param key the key
553 * @param childPage the child page
554 */
555 public void insertNode(int index, Object key, Page childPage) {
556
557 Object[] newKeys = new Object[keyCount + 1];
558 DataUtils.copyWithGap(keys, newKeys, keyCount, index);
559 newKeys[index] = key;
560 keys = newKeys;
561 keyCount++;
562
563 long[] newChildren = new long[children.length + 1];
564 DataUtils.copyWithGap(children, newChildren, children.length, index);
565 newChildren[index] = childPage.getPos();
566 children = newChildren;
567
568 Page[] newChildrenPages = new Page[childrenPages.length + 1];
569 DataUtils.copyWithGap(childrenPages, newChildrenPages, childrenPages.length, index);
570 newChildrenPages[index] = childPage;
571 childrenPages = newChildrenPages;
572
573 long[] newCounts = new long[counts.length + 1];
574 DataUtils.copyWithGap(counts, newCounts, counts.length, index);
575 newCounts[index] = childPage.getTotalCount();
576 counts = newCounts;
577
578 sharedFlags &= ~(SHARED_KEYS | SHARED_CHILDREN | SHARED_COUNTS);
579 totalCount += childPage.getTotalCount();
580 memory += map.getKeyType().getMemory(key);
581 memory += DataUtils.PAGE_MEMORY_CHILD;
582 }
583
584 /**
585 * Remove the key and value (or child) at the given index.
586 *
587 * @param index the index
588 */
589 public void remove(int index) {
590 int keyIndex = index >= keyCount ? index - 1 : index;
591 Object old = keys[keyIndex];
592 memory -= map.getKeyType().getMemory(old);
593 if ((sharedFlags & SHARED_KEYS) == 0 && keys.length > keyCount - 4) {
594 if (keyIndex < keyCount - 1) {
595 System.arraycopy(keys, keyIndex + 1, keys, keyIndex, keyCount - keyIndex - 1);
596 }
597 keys[keyCount - 1] = null;
598 } else {
599 Object[] newKeys = new Object[keyCount - 1];
600 DataUtils.copyExcept(keys, newKeys, keyCount, keyIndex);
601 keys = newKeys;
602 sharedFlags &= ~SHARED_KEYS;
603 }
604
605 if (values != null) {
606 old = values[index];
607 memory -= map.getValueType().getMemory(old);
608 if ((sharedFlags & SHARED_VALUES) == 0 && values.length > keyCount - 4) {
609 if (index < keyCount - 1) {
610 System.arraycopy(values, index + 1, values, index, keyCount - index - 1);
611 }
612 values[keyCount - 1] = null;
613 } else {
614 Object[] newValues = new Object[keyCount - 1];
615 DataUtils.copyExcept(values, newValues, keyCount, index);
616 values = newValues;
617 sharedFlags &= ~SHARED_VALUES;
618 }
619 totalCount--;
620 }
621 keyCount--;
622 if (children != null) {
623 memory -= DataUtils.PAGE_MEMORY_CHILD;
624 long countOffset = counts[index];
625
626 long[] newChildren = new long[children.length - 1];
627 DataUtils.copyExcept(children, newChildren, children.length, index);
628 children = newChildren;
629
630 Page[] newChildrenPages = new Page[childrenPages.length - 1];
631 DataUtils.copyExcept(childrenPages, newChildrenPages,
632 childrenPages.length, index);
633 childrenPages = newChildrenPages;
634
635 long[] newCounts = new long[counts.length - 1];
636 DataUtils.copyExcept(counts, newCounts, counts.length, index);
637 counts = newCounts;
638
639 sharedFlags &= ~(SHARED_CHILDREN | SHARED_COUNTS);
640 totalCount -= countOffset;
641 }
642 }
643
644 /**
645 * Read the page from the buffer.
646 *
647 * @param buff the buffer
648 * @param chunkId the chunk id
649 * @param offset the offset within the chunk
650 * @param maxLength the maximum length
651 */
652 void read(ByteBuffer buff, int chunkId, int offset, int maxLength) {
653 int start = buff.position();
654 int pageLength = buff.getInt();
655 if (pageLength > maxLength) {
656 throw new RuntimeException("Length too large, expected =< "
657 + maxLength + " got " + pageLength);
658 }
659 short check = buff.getShort();
660 int mapId = DataUtils.readVarInt(buff);
661 if (mapId != map.getId()) {
662 throw new RuntimeException("Error reading page, expected map "
663 + map.getId() + " got " + mapId);
664 }
665 int checkTest = DataUtils.getCheckValue(chunkId)
666 ^ DataUtils.getCheckValue(offset)
667 ^ DataUtils.getCheckValue(pageLength);
668 if (check != (short) checkTest) {
669 throw new RuntimeException("Error in check value, expected "
670 + checkTest + " got " + check);
671 }
672 int len = DataUtils.readVarInt(buff);
673 keys = new Object[len];
674 keyCount = len;
675 int type = buff.get();
676 boolean node = (type & 1) == DataUtils.PAGE_TYPE_NODE;
677 boolean compressed = (type & DataUtils.PAGE_COMPRESSED) != 0;
678 if (compressed) {
679 Compressor compressor = map.getStore().getCompressor();
680 int lenAdd = DataUtils.readVarInt(buff);
681 int compLen = pageLength + start - buff.position();
682 byte[] comp = new byte[compLen];
683 buff.get(comp);
684 int l = compLen + lenAdd;
685 buff = ByteBuffer.allocate(l);
686 compressor.expand(comp, 0, compLen, buff.array(), 0, l);
687 }
688 DataType keyType = map.getKeyType();
689 for (int i = 0; i < len; i++) {
690 Object k = keyType.read(buff);
691 keys[i] = k;
692 }
693 if (node) {
694 children = new long[len + 1];
695 for (int i = 0; i <= len; i++) {
696 children[i] = buff.getLong();
697 }
698 childrenPages = new Page[len + 1];
699 counts = new long[len + 1];
700 long total = 0;
701 for (int i = 0; i <= len; i++) {
702 long s = DataUtils.readVarLong(buff);
703 total += s;
704 counts[i] = s;
705 }
706 totalCount = total;
707 } else {
708 values = new Object[len];
709 DataType valueType = map.getValueType();
710 for (int i = 0; i < len; i++) {
711 Object v = valueType.read(buff);
712 values[i] = v;
713 }
714 totalCount = len;
715 }
716 memory = calculateMemory();
717 }
718
719 /**
720 * Store the page and update the position.
721 *
722 * @param chunk the chunk
723 * @param buff the target buffer
724 */
725 private void write(Chunk chunk, ByteBuffer buff) {
726 int start = buff.position();
727 buff.putInt(0);
728 buff.putShort((byte) 0);
729 DataUtils.writeVarInt(buff, map.getId());
730 int len = keyCount;
731 DataUtils.writeVarInt(buff, len);
732 Compressor compressor = map.getStore().getCompressor();
733 int type = children != null ? DataUtils.PAGE_TYPE_NODE
734 : DataUtils.PAGE_TYPE_LEAF;
735 buff.put((byte) type);
736 int compressStart = buff.position();
737 for (int i = 0; i < len; i++) {
738 map.getKeyType().write(buff, keys[i]);
739 }
740 if (type == DataUtils.PAGE_TYPE_NODE) {
741 for (int i = 0; i <= len; i++) {
742 buff.putLong(children[i]);
743 }
744 for (int i = 0; i <= len; i++) {
745 DataUtils.writeVarLong(buff, counts[i]);
746 }
747 } else {
748 for (int i = 0; i < len; i++) {
749 map.getValueType().write(buff, values[i]);
750 }
751 }
752 if (compressor != null) {
753 int expLen = buff.position() - compressStart;
754 byte[] exp = new byte[expLen];
755 buff.position(compressStart);
756 buff.get(exp);
757 byte[] comp = new byte[exp.length * 2];
758 int compLen = compressor.compress(exp, exp.length, comp, 0);
759 if (compLen + DataUtils.getVarIntLen(compLen - expLen) < expLen) {
760 buff.position(compressStart - 1);
761 buff.put((byte) (type + DataUtils.PAGE_COMPRESSED));
762 DataUtils.writeVarInt(buff, expLen - compLen);
763 buff.put(comp, 0, compLen);
764 }
765 }
766 int pageLength = buff.position() - start;
767 buff.putInt(start, pageLength);
768 int chunkId = chunk.id;
769 int check = DataUtils.getCheckValue(chunkId)
770 ^ DataUtils.getCheckValue(start)
771 ^ DataUtils.getCheckValue(pageLength);
772 buff.putShort(start + 4, (short) check);
773 this.pos = DataUtils.getPagePos(chunkId, start, pageLength, type);
774 long max = DataUtils.getPageMaxLength(pos);
775 chunk.maxLength += max;
776 chunk.maxLengthLive += max;
777 chunk.pageCount++;
778 }
779
780 /**
781 * Get the maximum length in bytes to store temporary records, recursively.
782 *
783 * @return the maximum length
784 */
785 int getMaxLengthTempRecursive() {
786 int maxLength = getMaxLength();
787 if (!isLeaf()) {
788 for (int i = 0; i <= keyCount; i++) {
789 Page p = childrenPages[i];
790 if (p != null) {
791 maxLength += p.getMaxLengthTempRecursive();
792 }
793 }
794 }
795 return maxLength;
796 }
797
798 int getMaxLength() {
799 // length, check, map id, key length, type
800 int maxLength = 4 + 2 + DataUtils.MAX_VAR_INT_LEN
801 + DataUtils.MAX_VAR_INT_LEN + 1;
802 int len = keyCount;
803 for (int i = 0; i < len; i++) {
804 maxLength += map.getKeyType().getMaxLength(keys[i]);
805 }
806 if (isLeaf()) {
807 for (int i = 0; i < len; i++) {
808 maxLength += map.getValueType().getMaxLength(values[i]);
809 }
810 } else {
811 maxLength += 8 * len;
812 maxLength += DataUtils.MAX_VAR_LONG_LEN * len;
813 }
814 return maxLength;
815 }
816
817 /**
818 * Store this page and all children that are changed, in reverse order, and
819 * update the position and the children.
820 *
821 * @param chunk the chunk
822 * @param buff the target buffer
823 * @return the page id
824 */
825 long writeUnsavedRecursive(Chunk chunk, ByteBuffer buff) {
826 if (!isLeaf()) {
827 int len = children.length;
828 for (int i = 0; i < len; i++) {
829 Page p = childrenPages[i];
830 if (p != null) {
831 children[i] = p.writeUnsavedRecursive(chunk, buff);
832 childrenPages[i] = null;
833 }
834 }
835 }
836 write(chunk, buff);
837 return pos;
838 }
839
840 long getVersion() {
841 return version;
842 }
843
844 public int getChildPageCount() {
845 return children.length;
846 }
847
848 public boolean equals(Object other) {
849 if (other == this) {
850 return true;
851 }
852 if (other instanceof Page) {
853 if (pos != 0 && ((Page) other).pos == pos) {
854 return true;
855 }
856 return this == other;
857 }
858 return false;
859 }
860
861 public int hashCode() {
862 return pos != 0 ? (int) (pos | (pos >>> 32)) : super.hashCode();
863 }
864
865 public int getMemory() {
866 if (MVStore.ASSERT) {
867 if (memory != calculateMemory()) {
868 throw new RuntimeException("Memory calculation error");
869 }
870 }
871 return memory;
872 }
873
874 private int calculateMemory() {
875 int mem = DataUtils.PAGE_MEMORY;
876 for (int i = 0; i < keyCount; i++) {
877 mem += map.getKeyType().getMemory(keys[i]);
878 }
879 if (this.isLeaf()) {
880 for (int i = 0; i < keyCount; i++) {
881 mem += map.getValueType().getMemory(values[i]);
882 }
883 } else {
884 mem += this.getChildPageCount() * DataUtils.PAGE_MEMORY_CHILD;
885 }
886 return mem;
887 }
888
889 void setVersion(long version) {
890 this.version = version;
891 }
892
893 }
894