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.kahadb.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.kahadb.index.BTreeIndex.Prefixer; 030 import org.apache.kahadb.page.Page; 031 import org.apache.kahadb.page.Transaction; 032 import org.apache.kahadb.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: Cylce 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 } else { 297 298 // The child was a leaf. Then we need to actually remove it from this branch node.. 299 // and relink the previous leaf to skip to the next leaf. 300 301 BTreeNode<Key, Value> previousLeaf = null; 302 if( idx > 0 ) { 303 // easy if we this node hold the previous child. 304 previousLeaf = getChild(tx, idx-1).getRightLeaf(tx); 305 } else { 306 // less easy if we need to go to the parent to find the previous child. 307 BTreeNode<Key, Value> lp = getLeftPeer(tx, this); 308 if( lp!=null ) { 309 previousLeaf = lp.getRightLeaf(tx); 310 } 311 // lp will be null if there was no previous child. 312 } 313 314 if( previousLeaf !=null ) { 315 previousLeaf.next = child.next; 316 index.storeNode(tx, previousLeaf, true); 317 } 318 319 if( idx < children.length-1 ) { 320 // Delete it and key to the right. 321 setBranchData(arrayDelete(keys, idx), arrayDelete(children, idx)); 322 } else { 323 // It was the last child.. Then delete it and key to the left 324 setBranchData(arrayDelete(keys, idx-1), arrayDelete(children, idx)); 325 } 326 327 // If we are the root node, and only have 1 child left. Then 328 // make the root be the leaf node. 329 if( children.length == 1 && parent==null ) { 330 child = getChild(tx, 0); 331 keys = child.keys; 332 children = child.children; 333 values = child.values; 334 // free up the page.. 335 tx.free(child.getPage()); 336 } 337 338 } 339 index.storeNode(tx, this, true); 340 } 341 342 return rc; 343 } else { 344 int idx = Arrays.binarySearch(keys, key); 345 if (idx < 0) { 346 return null; 347 } else { 348 Value oldValue = values[idx]; 349 setLeafData(arrayDelete(keys, idx), arrayDelete(values, idx)); 350 351 if( keys.length==0 && parent!=null) { 352 tx.free(getPage()); 353 } else { 354 index.storeNode(tx, this, true); 355 } 356 357 return oldValue; 358 } 359 } 360 } 361 362 public Value put(Transaction tx, Key key, Value value) throws IOException { 363 if (key == null) { 364 throw new IllegalArgumentException("Key cannot be null"); 365 } 366 367 if( isBranch() ) { 368 return getLeafNode(tx, this, key).put(tx, key, value); 369 } else { 370 int idx = Arrays.binarySearch(keys, key); 371 372 Value oldValue=null; 373 if (idx >= 0) { 374 // Key was found... Overwrite 375 oldValue = values[idx]; 376 values[idx] = value; 377 setLeafData(keys, values); 378 } else { 379 // Key was not found, Insert it 380 idx = -(idx + 1); 381 setLeafData(arrayInsert(keys, key, idx), arrayInsert(values, value, idx)); 382 } 383 384 try { 385 index.storeNode(tx, this, allowOverflow()); 386 } catch ( Transaction.PageOverflowIOException e ) { 387 // If we get an overflow 388 split(tx); 389 } 390 391 return oldValue; 392 } 393 } 394 395 private void promoteValue(Transaction tx, Key key, long nodeId) throws IOException { 396 397 int idx = Arrays.binarySearch(keys, key); 398 idx = idx < 0 ? -(idx + 1) : idx + 1; 399 setBranchData(arrayInsert(keys, key, idx), arrayInsert(children, nodeId, idx + 1)); 400 401 try { 402 index.storeNode(tx, this, allowOverflow()); 403 } catch ( Transaction.PageOverflowIOException e ) { 404 split(tx); 405 } 406 407 } 408 409 /** 410 * Internal to the BTreeNode method 411 */ 412 private void split(Transaction tx) throws IOException { 413 Key[] leftKeys; 414 Key[] rightKeys; 415 Value[] leftValues=null; 416 Value[] rightValues=null; 417 long[] leftChildren=null; 418 long[] rightChildren=null; 419 Key separator; 420 421 int vc = keys.length; 422 int pivot = vc / 2; 423 424 // Split the node into two nodes 425 if( isBranch() ) { 426 427 leftKeys = createKeyArray(pivot); 428 leftChildren = new long[leftKeys.length + 1]; 429 rightKeys = createKeyArray(vc - (pivot + 1)); 430 rightChildren = new long[rightKeys.length + 1]; 431 432 System.arraycopy(keys, 0, leftKeys, 0, leftKeys.length); 433 System.arraycopy(children, 0, leftChildren, 0, leftChildren.length); 434 System.arraycopy(keys, leftKeys.length + 1, rightKeys, 0, rightKeys.length); 435 System.arraycopy(children, leftChildren.length, rightChildren, 0, rightChildren.length); 436 437 // Is it a Simple Prefix BTree?? 438 Prefixer<Key> prefixer = index.getPrefixer(); 439 if(prefixer!=null) { 440 separator = prefixer.getSimplePrefix(leftKeys[leftKeys.length - 1], rightKeys[0]); 441 } else { 442 separator = keys[leftKeys.length]; 443 } 444 445 446 } else { 447 448 leftKeys = createKeyArray(pivot); 449 leftValues = createValueArray(leftKeys.length); 450 rightKeys = createKeyArray(vc - pivot); 451 rightValues = createValueArray(rightKeys.length); 452 453 System.arraycopy(keys, 0, leftKeys, 0, leftKeys.length); 454 System.arraycopy(values, 0, leftValues, 0, leftValues.length); 455 System.arraycopy(keys, leftKeys.length, rightKeys, 0, rightKeys.length); 456 System.arraycopy(values, leftValues.length, rightValues, 0, rightValues.length); 457 458 // separator = getSeparator(leftVals[leftVals.length - 1], 459 // rightVals[0]); 460 separator = rightKeys[0]; 461 462 } 463 464 // Promote the pivot to the parent branch 465 if (parent == null) { 466 467 // This can only happen if this is the root 468 BTreeNode<Key,Value> rNode = this.index.createNode(tx, this); 469 BTreeNode<Key,Value> lNode = this.index.createNode(tx, this); 470 471 if( isBranch() ) { 472 rNode.setBranchData(rightKeys, rightChildren); 473 lNode.setBranchData(leftKeys, leftChildren); 474 } else { 475 rNode.setLeafData(rightKeys, rightValues); 476 lNode.setLeafData(leftKeys, leftValues); 477 lNode.setNext(rNode.getPageId()); 478 } 479 480 Key[] v = createKeyArray(1); 481 v[0]=separator; 482 setBranchData(v, new long[] { lNode.getPageId(), rNode.getPageId() }); 483 484 index.storeNode(tx, this, true); 485 index.storeNode(tx, rNode, true); 486 index.storeNode(tx, lNode, true); 487 488 } else { 489 BTreeNode<Key,Value> rNode = this.index.createNode(tx, parent); 490 491 if( isBranch() ) { 492 setBranchData(leftKeys, leftChildren); 493 rNode.setBranchData(rightKeys, rightChildren); 494 } else { 495 rNode.setNext(next); 496 next = rNode.getPageId(); 497 setLeafData(leftKeys, leftValues); 498 rNode.setLeafData(rightKeys, rightValues); 499 } 500 501 index.storeNode(tx, this, true); 502 index.storeNode(tx, rNode, true); 503 parent.promoteValue(tx, separator, rNode.getPageId()); 504 } 505 } 506 507 public void printStructure(Transaction tx, PrintWriter out, String prefix) throws IOException { 508 if( prefix.length()>0 && parent == null ) { 509 throw new IllegalStateException("Cycle back to root node detected."); 510 } 511 512 if( isBranch() ) { 513 for(int i=0 ; i < children.length; i++) { 514 BTreeNode<Key, Value> child = getChild(tx, i); 515 if( i == children.length-1) { 516 out.println(prefix+"\\- "+child.getPageId()+(child.isBranch()?" ("+child.children.length+")":"")); 517 child.printStructure(tx, out, prefix+" "); 518 } else { 519 out.println(prefix+"|- "+child.getPageId()+(child.isBranch()?" ("+child.children.length+")":"")+" : "+keys[i]); 520 child.printStructure(tx, out, prefix+" "); 521 } 522 } 523 } 524 } 525 526 527 public int getMinLeafDepth(Transaction tx, int depth) throws IOException { 528 depth++; 529 if( isBranch() ) { 530 int min = Integer.MAX_VALUE; 531 for(int i=0 ; i < children.length; i++) { 532 min = Math.min(min, getChild(tx, i).getMinLeafDepth(tx, depth)); 533 } 534 return min; 535 } else { 536 // print(depth*2, "- "+page.getPageId()); 537 return depth; 538 } 539 } 540 541 public int getMaxLeafDepth(Transaction tx, int depth) throws IOException { 542 depth++; 543 if( isBranch() ) { 544 int v = 0; 545 for(int i=0 ; i < children.length; i++) { 546 v = Math.max(v, getChild(tx, i).getMaxLeafDepth(tx, depth)); 547 } 548 depth = v; 549 } 550 return depth; 551 } 552 553 public Value get(Transaction tx, Key key) throws IOException { 554 if (key == null) { 555 throw new IllegalArgumentException("Key cannot be null"); 556 } 557 if( isBranch() ) { 558 return getLeafNode(tx, this, key).get(tx, key); 559 } else { 560 int idx = Arrays.binarySearch(keys, key); 561 if (idx < 0) { 562 return null; 563 } else { 564 return values[idx]; 565 } 566 } 567 } 568 569 public boolean isEmpty(final Transaction tx) throws IOException { 570 return keys.length==0; 571 } 572 573 public void visit(Transaction tx, BTreeVisitor<Key, Value> visitor) throws IOException { 574 if (visitor == null) { 575 throw new IllegalArgumentException("Visitor cannot be null"); 576 } 577 if( isBranch() ) { 578 for(int i=0; i < this.children.length; i++) { 579 Key key1 = null; 580 if( i!=0 ) { 581 key1 = keys[i-1]; 582 } 583 Key key2 = null; 584 if( i!=this.children.length-1 ) { 585 key2 = keys[i]; 586 } 587 if( visitor.isInterestedInKeysBetween(key1, key2) ) { 588 BTreeNode<Key, Value> child = getChild(tx, i); 589 child.visit(tx, visitor); 590 } 591 } 592 } else { 593 visitor.visit(Arrays.asList(keys), Arrays.asList(values)); 594 } 595 } 596 597 public Map.Entry<Key,Value> getFirst(Transaction tx) throws IOException { 598 BTreeNode<Key, Value> node = this; 599 while( node .isBranch() ) { 600 node = node.getChild(tx, 0); 601 } 602 if( node.values.length>0 ) { 603 return new KeyValueEntry(node.keys[0], node.values[0]); 604 } else { 605 return null; 606 } 607 } 608 609 public Map.Entry<Key,Value> getLast(Transaction tx) throws IOException { 610 BTreeNode<Key, Value> node = this; 611 while( node.isBranch() ) { 612 node = node.getChild(tx, node.children.length-1); 613 } 614 if( node.values.length>0 ) { 615 int idx = node.values.length-1; 616 return new KeyValueEntry(node.keys[idx], node.values[idx]); 617 } else { 618 return null; 619 } 620 } 621 622 public BTreeNode<Key,Value> getFirstLeafNode(Transaction tx) throws IOException { 623 BTreeNode<Key, Value> node = this; 624 while( node .isBranch() ) { 625 node = node.getChild(tx, 0); 626 } 627 return node; 628 } 629 630 public Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx, Key startKey) throws IOException { 631 if (startKey == null) { 632 return iterator(tx); 633 } 634 if( isBranch() ) { 635 return getLeafNode(tx, this, startKey).iterator(tx, startKey); 636 } else { 637 int idx = Arrays.binarySearch(keys, startKey); 638 if (idx < 0) { 639 idx = -(idx + 1); 640 } 641 return new BTreeIterator(tx, this, idx); 642 } 643 } 644 645 public Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx) throws IOException { 646 return new BTreeIterator(tx, getFirstLeafNode(tx), 0); 647 } 648 649 public void clear(Transaction tx) throws IOException { 650 if( isBranch() ) { 651 for (int i = 0; i < children.length; i++) { 652 BTreeNode<Key, Value> node = index.loadNode(tx, children[i], this); 653 node.clear(tx); 654 tx.free(node.getPage()); 655 } 656 } 657 // Reset the root node to be a leaf. 658 if( parent == null ) { 659 setLeafData(createKeyArray(0), createValueArray(0)); 660 next=-1; 661 index.storeNode(tx, this, true); 662 } 663 } 664 665 666 private static <Key,Value> BTreeNode<Key, Value> getLeafNode(Transaction tx, final BTreeNode<Key, Value> node, Key key) throws IOException { 667 BTreeNode<Key, Value> current = node; 668 while( true ) { 669 if( current.isBranch() ) { 670 int idx = Arrays.binarySearch(current.keys, key); 671 idx = idx < 0 ? -(idx + 1) : idx + 1; 672 BTreeNode<Key, Value> child = current.getChild(tx, idx); 673 674 // A little cycle detection for sanity's sake 675 if( child == node ) { 676 throw new IOException("BTree corrupted: Cylce detected."); 677 } 678 679 current = child; 680 } else { 681 break; 682 } 683 } 684 return current; 685 } 686 687 public boolean contains(Transaction tx, Key key) throws IOException { 688 if (key == null) { 689 throw new IllegalArgumentException("Key cannot be null"); 690 } 691 692 if( isBranch() ) { 693 return getLeafNode(tx, this, key).contains(tx, key); 694 } else { 695 int idx = Arrays.binarySearch(keys, key); 696 if (idx < 0) { 697 return false; 698 } else { 699 return true; 700 } 701 } 702 } 703 704 /////////////////////////////////////////////////////////////////// 705 // Implementation methods 706 /////////////////////////////////////////////////////////////////// 707 708 709 private boolean allowOverflow() { 710 // Only allow page overflow if there are <= 3 keys in the node. Otherwise a split will occur on overflow 711 return this.keys.length<=3; 712 } 713 714 715 private void setLeafData(Key[] keys, Value[] values) { 716 this.keys = keys; 717 this.values = values; 718 this.children = null; 719 } 720 721 private void setBranchData(Key[] keys, long[] nodeIds) { 722 this.keys = keys; 723 this.children = nodeIds; 724 this.values = null; 725 } 726 727 @SuppressWarnings("unchecked") 728 private Key[] createKeyArray(int size) { 729 return (Key[])new Object[size]; 730 } 731 732 @SuppressWarnings("unchecked") 733 private Value[] createValueArray(int size) { 734 return (Value[])new Object[size]; 735 } 736 737 @SuppressWarnings("unchecked") 738 static private <T> T[] arrayDelete(T[] vals, int idx) { 739 T[] newVals = (T[])new Object[vals.length - 1]; 740 if (idx > 0) { 741 System.arraycopy(vals, 0, newVals, 0, idx); 742 } 743 if (idx < newVals.length) { 744 System.arraycopy(vals, idx + 1, newVals, idx, newVals.length - idx); 745 } 746 return newVals; 747 } 748 749 static private long[] arrayDelete(long[] vals, int idx) { 750 long[] newVals = new long[vals.length - 1]; 751 if (idx > 0) { 752 System.arraycopy(vals, 0, newVals, 0, idx); 753 } 754 if (idx < newVals.length) { 755 System.arraycopy(vals, idx + 1, newVals, idx, newVals.length - idx); 756 } 757 return newVals; 758 } 759 760 @SuppressWarnings("unchecked") 761 static private <T> T[] arrayInsert(T[] vals, T val, int idx) { 762 T[] newVals = (T[])new Object[vals.length + 1]; 763 if (idx > 0) { 764 System.arraycopy(vals, 0, newVals, 0, idx); 765 } 766 newVals[idx] = val; 767 if (idx < vals.length) { 768 System.arraycopy(vals, idx, newVals, idx + 1, vals.length - idx); 769 } 770 return newVals; 771 } 772 773 774 static private long[] arrayInsert(long[] vals, long val, int idx) { 775 776 long[] newVals = new long[vals.length + 1]; 777 if (idx > 0) { 778 System.arraycopy(vals, 0, newVals, 0, idx); 779 } 780 newVals[idx] = val; 781 if (idx < vals.length) { 782 System.arraycopy(vals, idx, newVals, idx + 1, vals.length - idx); 783 } 784 return newVals; 785 } 786 787 /////////////////////////////////////////////////////////////////// 788 // Property Accessors 789 /////////////////////////////////////////////////////////////////// 790 private boolean isBranch() { 791 return children!=null; 792 } 793 794 public long getPageId() { 795 return page.getPageId(); 796 } 797 798 public BTreeNode<Key, Value> getParent() { 799 return parent; 800 } 801 802 public void setParent(BTreeNode<Key, Value> parent) { 803 this.parent = parent; 804 } 805 806 public Page<BTreeNode<Key, Value>> getPage() { 807 return page; 808 } 809 810 public void setPage(Page<BTreeNode<Key, Value>> page) { 811 this.page = page; 812 } 813 814 public long getNext() { 815 return next; 816 } 817 818 public void setNext(long next) { 819 this.next = next; 820 } 821 822 @Override 823 public String toString() { 824 return "[BTreeNode "+(isBranch()?"branch":"leaf")+": "+Arrays.asList(keys)+"]"; 825 } 826 827 } 828 829