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