001 /**
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.activemq.store.kahadb.disk.index;
018
019 import java.io.DataInput;
020 import java.io.DataOutput;
021 import java.io.IOException;
022 import java.io.PrintWriter;
023 import java.util.Arrays;
024 import java.util.Iterator;
025 import java.util.Map;
026 import java.util.NoSuchElementException;
027 import java.util.Map.Entry;
028
029 import org.apache.activemq.store.kahadb.disk.index.BTreeIndex.Prefixer;
030 import org.apache.activemq.store.kahadb.disk.page.Page;
031 import org.apache.activemq.store.kahadb.disk.page.Transaction;
032 import org.apache.activemq.store.kahadb.disk.util.VariableMarshaller;
033
034
035 /**
036 * The BTreeNode class represents a node in the BTree object graph. It is stored in
037 * one Page of a PageFile.
038 */
039 public final class BTreeNode<Key,Value> {
040
041 // The index that this node is part of.
042 private final BTreeIndex<Key,Value> index;
043 // The parent node or null if this is the root node of the BTree
044 private BTreeNode<Key,Value> parent;
045 // The page associated with this node
046 private Page<BTreeNode<Key,Value>> page;
047
048 // Order list of keys in the node
049 private Key[] keys;
050 // Values associated with the Keys. Null if this is a branch node.
051 private Value[] values;
052 // nodeId pointers to children BTreeNodes. Null if this is a leaf node.
053 private long[] children;
054 // The next leaf node after this one. Used for fast iteration of the entries.
055 private long next = -1;
056
057 private final class KeyValueEntry implements Map.Entry<Key, Value> {
058 private final Key key;
059 private final Value value;
060
061 public KeyValueEntry(Key key, Value value) {
062 this.key = key;
063 this.value = value;
064 }
065
066 public Key getKey() {
067 return key;
068 }
069
070 public Value getValue() {
071 return value;
072 }
073
074 public Value setValue(Value value) {
075 throw new UnsupportedOperationException();
076 }
077
078 }
079
080 private final class BTreeIterator implements Iterator<Map.Entry<Key, Value>> {
081
082 private final Transaction tx;
083 BTreeNode<Key,Value> current;
084 int nextIndex;
085 Map.Entry<Key,Value> nextEntry;
086
087 private BTreeIterator(Transaction tx, BTreeNode<Key,Value> current, int nextIndex) {
088 this.tx = tx;
089 this.current = current;
090 this.nextIndex=nextIndex;
091 }
092
093 synchronized private void findNextPage() {
094 if( nextEntry!=null ) {
095 return;
096 }
097
098 try {
099 while( current!=null ) {
100 if( nextIndex >= current.keys.length ) {
101 // we need to roll to the next leaf..
102 if( current.next >= 0 ) {
103 current = index.loadNode(tx, current.next, null);
104 assert !current.isBranch() : "Should have linked to the next leaf node.";
105 nextIndex=0;
106 } else {
107 break;
108 }
109 } else {
110 nextEntry = new KeyValueEntry(current.keys[nextIndex], current.values[nextIndex]);
111 nextIndex++;
112 break;
113 }
114
115 }
116 } catch (IOException e) {
117 }
118 }
119
120 public boolean hasNext() {
121 findNextPage();
122 return nextEntry !=null;
123 }
124
125 public Entry<Key, Value> next() {
126 findNextPage();
127 if( nextEntry !=null ) {
128 Entry<Key, Value> lastEntry = nextEntry;
129 nextEntry=null;
130 return lastEntry;
131 } else {
132 throw new NoSuchElementException();
133 }
134 }
135
136 public void remove() {
137 throw new UnsupportedOperationException();
138 }
139 }
140
141 /**
142 * The Marshaller is used to store and load the data in the BTreeNode into a Page.
143 *
144 * @param <Key>
145 * @param <Value>
146 */
147 static public class Marshaller<Key,Value> extends VariableMarshaller<BTreeNode<Key,Value>> {
148 private final BTreeIndex<Key,Value> index;
149
150 public Marshaller(BTreeIndex<Key,Value> index) {
151 this.index = index;
152 }
153
154 public void writePayload(BTreeNode<Key,Value> node, DataOutput os) throws IOException {
155 // Write the keys
156 short count = (short)node.keys.length; // cast may truncate value...
157 if( count != node.keys.length ) {
158 throw new IOException("Too many keys");
159 }
160
161 os.writeShort(count);
162 for (int i = 0; i < node.keys.length; i++) {
163 index.getKeyMarshaller().writePayload(node.keys[i], os);
164 }
165
166 if( node.isBranch() ) {
167 // If this is a branch...
168 os.writeBoolean(true);
169 for (int i = 0; i < count+1; i++) {
170 os.writeLong(node.children[i]);
171 }
172
173 } else {
174 // If this is a leaf
175 os.writeBoolean(false);
176 for (int i = 0; i < count; i++) {
177 index.getValueMarshaller().writePayload(node.values[i], os);
178 }
179 os.writeLong(node.next);
180 }
181 }
182
183 @SuppressWarnings("unchecked")
184 public BTreeNode<Key,Value> readPayload(DataInput is) throws IOException {
185 BTreeNode<Key,Value> node = new BTreeNode<Key,Value>(index);
186 int count = is.readShort();
187
188 node.keys = (Key[])new Object[count];
189 for (int i = 0; i < count; i++) {
190 node.keys[i] = index.getKeyMarshaller().readPayload(is);
191 }
192
193 if( is.readBoolean() ) {
194 node.children = new long[count+1];
195 for (int i = 0; i < count+1; i++) {
196 node.children[i] = is.readLong();
197 }
198 } else {
199 node.values = (Value[])new Object[count];
200 for (int i = 0; i < count; i++) {
201 node.values[i] = index.getValueMarshaller().readPayload(is);
202 }
203 node.next = is.readLong();
204 }
205 return node;
206 }
207 }
208
209 public BTreeNode(BTreeIndex<Key,Value> index) {
210 this.index = index;
211 }
212
213 public void setEmpty() {
214 setLeafData(createKeyArray(0), createValueArray(0));
215 }
216
217
218 /**
219 * Internal (to the BTreeNode) method. Because this method is called only by
220 * BTreeNode itself, no synchronization done inside of this method.
221 * @throws IOException
222 */
223 private BTreeNode<Key,Value> getChild(Transaction tx, int idx) throws IOException {
224 if (isBranch() && idx >= 0 && idx < children.length) {
225 BTreeNode<Key, Value> result = this.index.loadNode(tx, children[idx], this);
226 return result;
227 } else {
228 return null;
229 }
230 }
231
232
233 /**
234 * Returns the right most leaf from the current btree graph.
235 * @throws IOException
236 */
237 private BTreeNode<Key,Value> getRightLeaf(Transaction tx) throws IOException {
238 BTreeNode<Key,Value> cur = this;
239 while(cur.isBranch()) {
240 cur = cur.getChild(tx, cur.keys.length);
241 }
242 return cur;
243 }
244
245 /**
246 * Returns the left most leaf from the current btree graph.
247 * @throws IOException
248 */
249 private BTreeNode<Key,Value> getLeftLeaf(Transaction tx) throws IOException {
250 BTreeNode<Key,Value> cur = this;
251 while(cur.isBranch()) {
252 cur = cur.getChild(tx, 0);
253 }
254 return cur;
255 }
256
257 /**
258 * Returns the left most leaf from the current btree graph.
259 * @throws IOException
260 */
261 private BTreeNode<Key,Value> getLeftPeer(Transaction tx, BTreeNode<Key,Value> x) throws IOException {
262 BTreeNode<Key,Value> cur = x;
263 while( cur.parent !=null ) {
264 if( cur.parent.children[0] == cur.getPageId() ) {
265 cur = cur.parent;
266 } else {
267 for( int i=0; i < cur.parent.children.length; i ++) {
268 if( cur.parent.children[i]==cur.getPageId() ) {
269 return cur.parent.getChild(tx, i-1);
270 }
271 }
272 throw new AssertionError("page "+x+" was decendent of "+cur.getPageId());
273 }
274 }
275 return null;
276 }
277
278 public Value remove(Transaction tx, Key key) throws IOException {
279
280 if(isBranch()) {
281 int idx = Arrays.binarySearch(keys, key);
282 idx = idx < 0 ? -(idx + 1) : idx + 1;
283 BTreeNode<Key, Value> child = getChild(tx, idx);
284 if( child.getPageId() == index.getPageId() ) {
285 throw new IOException("BTree corrupted: Cycle detected.");
286 }
287 Value rc = child.remove(tx, key);
288
289 // child node is now empty.. remove it from the branch node.
290 if( child.keys.length == 0 ) {
291
292 // If the child node is a branch, promote
293 if( child.isBranch() ) {
294 // This is cause branches are never really empty.. they just go down to 1 child..
295 children[idx] = child.children[0];
296 tx.free(child.getPage());
297 } else {
298
299 // The child was a leaf. Then we need to actually remove it from this branch node..
300 // and relink the previous leaf to skip to the next leaf.
301
302 BTreeNode<Key, Value> previousLeaf = null;
303 if( idx > 0 ) {
304 // easy if we this node hold the previous child.
305 previousLeaf = getChild(tx, idx-1).getRightLeaf(tx);
306 } else {
307 // less easy if we need to go to the parent to find the previous child.
308 BTreeNode<Key, Value> lp = getLeftPeer(tx, this);
309 if( lp!=null ) {
310 previousLeaf = lp.getRightLeaf(tx);
311 }
312 // lp will be null if there was no previous child.
313 }
314
315 if( previousLeaf !=null ) {
316 previousLeaf.next = child.next;
317 index.storeNode(tx, previousLeaf, true);
318 }
319
320 if( idx < children.length-1 ) {
321 // Delete it and key to the right.
322 setBranchData(arrayDelete(keys, idx), arrayDelete(children, idx));
323 } else {
324 // It was the last child.. Then delete it and key to the left
325 setBranchData(arrayDelete(keys, idx-1), arrayDelete(children, idx));
326 }
327
328 // If we are the root node, and only have 1 child left. Then
329 // make the root be the leaf node.
330 if( children.length == 1 && parent==null ) {
331 child = getChild(tx, 0);
332 keys = child.keys;
333 children = child.children;
334 values = child.values;
335 // free up the page..
336 tx.free(child.getPage());
337 }
338
339 }
340 index.storeNode(tx, this, true);
341 }
342
343 return rc;
344 } else {
345 int idx = Arrays.binarySearch(keys, key);
346 if (idx < 0) {
347 return null;
348 } else {
349 Value oldValue = values[idx];
350 setLeafData(arrayDelete(keys, idx), arrayDelete(values, idx));
351
352 if( keys.length==0 && parent!=null) {
353 tx.free(getPage());
354 } else {
355 index.storeNode(tx, this, true);
356 }
357
358 return oldValue;
359 }
360 }
361 }
362
363 public Value put(Transaction tx, Key key, Value value) throws IOException {
364 if (key == null) {
365 throw new IllegalArgumentException("Key cannot be null");
366 }
367
368 if( isBranch() ) {
369 return getLeafNode(tx, this, key).put(tx, key, value);
370 } else {
371 int idx = Arrays.binarySearch(keys, key);
372
373 Value oldValue=null;
374 if (idx >= 0) {
375 // Key was found... Overwrite
376 oldValue = values[idx];
377 values[idx] = value;
378 setLeafData(keys, values);
379 } else {
380 // Key was not found, Insert it
381 idx = -(idx + 1);
382 setLeafData(arrayInsert(keys, key, idx), arrayInsert(values, value, idx));
383 }
384
385 try {
386 index.storeNode(tx, this, allowOverflow());
387 } catch ( Transaction.PageOverflowIOException e ) {
388 // If we get an overflow
389 split(tx);
390 }
391
392 return oldValue;
393 }
394 }
395
396 private void promoteValue(Transaction tx, Key key, long nodeId) throws IOException {
397
398 int idx = Arrays.binarySearch(keys, key);
399 idx = idx < 0 ? -(idx + 1) : idx + 1;
400 setBranchData(arrayInsert(keys, key, idx), arrayInsert(children, nodeId, idx + 1));
401
402 try {
403 index.storeNode(tx, this, allowOverflow());
404 } catch ( Transaction.PageOverflowIOException e ) {
405 split(tx);
406 }
407
408 }
409
410 /**
411 * Internal to the BTreeNode method
412 */
413 private void split(Transaction tx) throws IOException {
414 Key[] leftKeys;
415 Key[] rightKeys;
416 Value[] leftValues=null;
417 Value[] rightValues=null;
418 long[] leftChildren=null;
419 long[] rightChildren=null;
420 Key separator;
421
422 int vc = keys.length;
423 int pivot = vc / 2;
424
425 // Split the node into two nodes
426 if( isBranch() ) {
427
428 leftKeys = createKeyArray(pivot);
429 leftChildren = new long[leftKeys.length + 1];
430 rightKeys = createKeyArray(vc - (pivot + 1));
431 rightChildren = new long[rightKeys.length + 1];
432
433 System.arraycopy(keys, 0, leftKeys, 0, leftKeys.length);
434 System.arraycopy(children, 0, leftChildren, 0, leftChildren.length);
435 System.arraycopy(keys, leftKeys.length + 1, rightKeys, 0, rightKeys.length);
436 System.arraycopy(children, leftChildren.length, rightChildren, 0, rightChildren.length);
437
438 // Is it a Simple Prefix BTree??
439 Prefixer<Key> prefixer = index.getPrefixer();
440 if(prefixer!=null) {
441 separator = prefixer.getSimplePrefix(leftKeys[leftKeys.length - 1], rightKeys[0]);
442 } else {
443 separator = keys[leftKeys.length];
444 }
445
446
447 } else {
448
449 leftKeys = createKeyArray(pivot);
450 leftValues = createValueArray(leftKeys.length);
451 rightKeys = createKeyArray(vc - pivot);
452 rightValues = createValueArray(rightKeys.length);
453
454 System.arraycopy(keys, 0, leftKeys, 0, leftKeys.length);
455 System.arraycopy(values, 0, leftValues, 0, leftValues.length);
456 System.arraycopy(keys, leftKeys.length, rightKeys, 0, rightKeys.length);
457 System.arraycopy(values, leftValues.length, rightValues, 0, rightValues.length);
458
459 // separator = getSeparator(leftVals[leftVals.length - 1],
460 // rightVals[0]);
461 separator = rightKeys[0];
462
463 }
464
465 // Promote the pivot to the parent branch
466 if (parent == null) {
467
468 // This can only happen if this is the root
469 BTreeNode<Key,Value> rNode = this.index.createNode(tx, this);
470 BTreeNode<Key,Value> lNode = this.index.createNode(tx, this);
471
472 if( isBranch() ) {
473 rNode.setBranchData(rightKeys, rightChildren);
474 lNode.setBranchData(leftKeys, leftChildren);
475 } else {
476 rNode.setLeafData(rightKeys, rightValues);
477 lNode.setLeafData(leftKeys, leftValues);
478 lNode.setNext(rNode.getPageId());
479 }
480
481 Key[] v = createKeyArray(1);
482 v[0]=separator;
483 setBranchData(v, new long[] { lNode.getPageId(), rNode.getPageId() });
484
485 index.storeNode(tx, this, true);
486 index.storeNode(tx, rNode, true);
487 index.storeNode(tx, lNode, true);
488
489 } else {
490 BTreeNode<Key,Value> rNode = this.index.createNode(tx, parent);
491
492 if( isBranch() ) {
493 setBranchData(leftKeys, leftChildren);
494 rNode.setBranchData(rightKeys, rightChildren);
495 } else {
496 rNode.setNext(next);
497 next = rNode.getPageId();
498 setLeafData(leftKeys, leftValues);
499 rNode.setLeafData(rightKeys, rightValues);
500 }
501
502 index.storeNode(tx, this, true);
503 index.storeNode(tx, rNode, true);
504 parent.promoteValue(tx, separator, rNode.getPageId());
505 }
506 }
507
508 public void printStructure(Transaction tx, PrintWriter out, String prefix) throws IOException {
509 if( prefix.length()>0 && parent == null ) {
510 throw new IllegalStateException("Cycle back to root node detected.");
511 }
512 if (parent == null) {
513 prefix += "|";
514 out.println(prefix + getPageId());
515 }
516 if( isBranch() ) {
517 for(int i=0 ; i < children.length; i++) {
518 BTreeNode<Key, Value> child = getChild(tx, i);
519 if( i == children.length-1) {
520 out.println(prefix+"\\- "+child.getPageId()+(child.isBranch()?" ("+child.children.length+")":""));
521 child.printStructure(tx, out, prefix+" ");
522 } else {
523 out.println(prefix+"|- "+child.getPageId()+(child.isBranch()?" ("+child.children.length+")":"")+" : "+keys[i]);
524 child.printStructure(tx, out, prefix+" ");
525 }
526 }
527 }
528 }
529
530
531 public int getMinLeafDepth(Transaction tx, int depth) throws IOException {
532 depth++;
533 if( isBranch() ) {
534 int min = Integer.MAX_VALUE;
535 for(int i=0 ; i < children.length; i++) {
536 min = Math.min(min, getChild(tx, i).getMinLeafDepth(tx, depth));
537 }
538 return min;
539 } else {
540 // print(depth*2, "- "+page.getPageId());
541 return depth;
542 }
543 }
544
545 public int getMaxLeafDepth(Transaction tx, int depth) throws IOException {
546 depth++;
547 if( isBranch() ) {
548 int v = 0;
549 for(int i=0 ; i < children.length; i++) {
550 v = Math.max(v, getChild(tx, i).getMaxLeafDepth(tx, depth));
551 }
552 depth = v;
553 }
554 return depth;
555 }
556
557 public Value get(Transaction tx, Key key) throws IOException {
558 if (key == null) {
559 throw new IllegalArgumentException("Key cannot be null");
560 }
561 if( isBranch() ) {
562 return getLeafNode(tx, this, key).get(tx, key);
563 } else {
564 int idx = Arrays.binarySearch(keys, key);
565 if (idx < 0) {
566 return null;
567 } else {
568 return values[idx];
569 }
570 }
571 }
572
573 public boolean isEmpty(final Transaction tx) throws IOException {
574 return keys.length==0;
575 }
576
577 public void visit(Transaction tx, BTreeVisitor<Key, Value> visitor) throws IOException {
578 if (visitor == null) {
579 throw new IllegalArgumentException("Visitor cannot be null");
580 }
581 if( isBranch() ) {
582 for(int i=0; i < this.children.length; i++) {
583 Key key1 = null;
584 if( i!=0 ) {
585 key1 = keys[i-1];
586 }
587 Key key2 = null;
588 if( i!=this.children.length-1 ) {
589 key2 = keys[i];
590 }
591 if( visitor.isInterestedInKeysBetween(key1, key2) ) {
592 BTreeNode<Key, Value> child = getChild(tx, i);
593 child.visit(tx, visitor);
594 }
595 }
596 } else {
597 visitor.visit(Arrays.asList(keys), Arrays.asList(values));
598 }
599 }
600
601 public Map.Entry<Key,Value> getFirst(Transaction tx) throws IOException {
602 BTreeNode<Key, Value> node = this;
603 while( node .isBranch() ) {
604 node = node.getChild(tx, 0);
605 }
606 if( node.values.length>0 ) {
607 return new KeyValueEntry(node.keys[0], node.values[0]);
608 } else {
609 return null;
610 }
611 }
612
613 public Map.Entry<Key,Value> getLast(Transaction tx) throws IOException {
614 BTreeNode<Key, Value> node = this;
615 while( node.isBranch() ) {
616 node = node.getChild(tx, node.children.length-1);
617 }
618 if( node.values.length>0 ) {
619 int idx = node.values.length-1;
620 return new KeyValueEntry(node.keys[idx], node.values[idx]);
621 } else {
622 return null;
623 }
624 }
625
626 public BTreeNode<Key,Value> getFirstLeafNode(Transaction tx) throws IOException {
627 BTreeNode<Key, Value> node = this;
628 while( node .isBranch() ) {
629 node = node.getChild(tx, 0);
630 }
631 return node;
632 }
633
634 public Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx, Key startKey) throws IOException {
635 if (startKey == null) {
636 return iterator(tx);
637 }
638 if( isBranch() ) {
639 return getLeafNode(tx, this, startKey).iterator(tx, startKey);
640 } else {
641 int idx = Arrays.binarySearch(keys, startKey);
642 if (idx < 0) {
643 idx = -(idx + 1);
644 }
645 return new BTreeIterator(tx, this, idx);
646 }
647 }
648
649 public Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx) throws IOException {
650 return new BTreeIterator(tx, getFirstLeafNode(tx), 0);
651 }
652
653 public void clear(Transaction tx) throws IOException {
654 if( isBranch() ) {
655 for (int i = 0; i < children.length; i++) {
656 BTreeNode<Key, Value> node = index.loadNode(tx, children[i], this);
657 node.clear(tx);
658 tx.free(node.getPage());
659 }
660 }
661 // Reset the root node to be a leaf.
662 if( parent == null ) {
663 setLeafData(createKeyArray(0), createValueArray(0));
664 next=-1;
665 index.storeNode(tx, this, true);
666 }
667 }
668
669
670 private static <Key,Value> BTreeNode<Key, Value> getLeafNode(Transaction tx, final BTreeNode<Key, Value> node, Key key) throws IOException {
671 BTreeNode<Key, Value> current = node;
672 while( true ) {
673 if( current.isBranch() ) {
674 int idx = Arrays.binarySearch(current.keys, key);
675 idx = idx < 0 ? -(idx + 1) : idx + 1;
676 BTreeNode<Key, Value> child = current.getChild(tx, idx);
677
678 // A little cycle detection for sanity's sake
679 if( child == node ) {
680 throw new IOException("BTree corrupted: Cylce detected.");
681 }
682
683 current = child;
684 } else {
685 break;
686 }
687 }
688 return current;
689 }
690
691 public boolean contains(Transaction tx, Key key) throws IOException {
692 if (key == null) {
693 throw new IllegalArgumentException("Key cannot be null");
694 }
695
696 if( isBranch() ) {
697 return getLeafNode(tx, this, key).contains(tx, key);
698 } else {
699 int idx = Arrays.binarySearch(keys, key);
700 if (idx < 0) {
701 return false;
702 } else {
703 return true;
704 }
705 }
706 }
707
708 ///////////////////////////////////////////////////////////////////
709 // Implementation methods
710 ///////////////////////////////////////////////////////////////////
711
712
713 private boolean allowOverflow() {
714 // Only allow page overflow if there are <= 3 keys in the node. Otherwise a split will occur on overflow
715 return this.keys.length<=3;
716 }
717
718
719 private void setLeafData(Key[] keys, Value[] values) {
720 this.keys = keys;
721 this.values = values;
722 this.children = null;
723 }
724
725 private void setBranchData(Key[] keys, long[] nodeIds) {
726 this.keys = keys;
727 this.children = nodeIds;
728 this.values = null;
729 }
730
731 @SuppressWarnings("unchecked")
732 private Key[] createKeyArray(int size) {
733 return (Key[])new Object[size];
734 }
735
736 @SuppressWarnings("unchecked")
737 private Value[] createValueArray(int size) {
738 return (Value[])new Object[size];
739 }
740
741 @SuppressWarnings("unchecked")
742 static private <T> T[] arrayDelete(T[] vals, int idx) {
743 T[] newVals = (T[])new Object[vals.length - 1];
744 if (idx > 0) {
745 System.arraycopy(vals, 0, newVals, 0, idx);
746 }
747 if (idx < newVals.length) {
748 System.arraycopy(vals, idx + 1, newVals, idx, newVals.length - idx);
749 }
750 return newVals;
751 }
752
753 static private long[] arrayDelete(long[] vals, int idx) {
754 long[] newVals = new long[vals.length - 1];
755 if (idx > 0) {
756 System.arraycopy(vals, 0, newVals, 0, idx);
757 }
758 if (idx < newVals.length) {
759 System.arraycopy(vals, idx + 1, newVals, idx, newVals.length - idx);
760 }
761 return newVals;
762 }
763
764 @SuppressWarnings("unchecked")
765 static private <T> T[] arrayInsert(T[] vals, T val, int idx) {
766 T[] newVals = (T[])new Object[vals.length + 1];
767 if (idx > 0) {
768 System.arraycopy(vals, 0, newVals, 0, idx);
769 }
770 newVals[idx] = val;
771 if (idx < vals.length) {
772 System.arraycopy(vals, idx, newVals, idx + 1, vals.length - idx);
773 }
774 return newVals;
775 }
776
777
778 static private long[] arrayInsert(long[] vals, long val, int idx) {
779
780 long[] newVals = new long[vals.length + 1];
781 if (idx > 0) {
782 System.arraycopy(vals, 0, newVals, 0, idx);
783 }
784 newVals[idx] = val;
785 if (idx < vals.length) {
786 System.arraycopy(vals, idx, newVals, idx + 1, vals.length - idx);
787 }
788 return newVals;
789 }
790
791 ///////////////////////////////////////////////////////////////////
792 // Property Accessors
793 ///////////////////////////////////////////////////////////////////
794 private boolean isBranch() {
795 return children!=null;
796 }
797
798 public long getPageId() {
799 return page.getPageId();
800 }
801
802 public BTreeNode<Key, Value> getParent() {
803 return parent;
804 }
805
806 public void setParent(BTreeNode<Key, Value> parent) {
807 this.parent = parent;
808 }
809
810 public Page<BTreeNode<Key, Value>> getPage() {
811 return page;
812 }
813
814 public void setPage(Page<BTreeNode<Key, Value>> page) {
815 this.page = page;
816 }
817
818 public long getNext() {
819 return next;
820 }
821
822 public void setNext(long next) {
823 this.next = next;
824 }
825
826 @Override
827 public String toString() {
828 return "[BTreeNode "+(isBranch()?"branch":"leaf")+": "+Arrays.asList(keys)+"]";
829 }
830
831 }
832
833