001 /** 002 * JDBM LICENSE v1.00 003 * 004 * Redistribution and use of this software and associated documentation 005 * ("Software"), with or without modification, are permitted provided 006 * that the following conditions are met: 007 * 008 * 1. Redistributions of source code must retain copyright 009 * statements and notices. Redistributions must also contain a 010 * copy of this document. 011 * 012 * 2. Redistributions in binary form must reproduce the 013 * above copyright notice, this list of conditions and the 014 * following disclaimer in the documentation and/or other 015 * materials provided with the distribution. 016 * 017 * 3. The name "JDBM" must not be used to endorse or promote 018 * products derived from this Software without prior written 019 * permission of Cees de Groot. For written permission, 020 * please contact cg@cdegroot.com. 021 * 022 * 4. Products derived from this Software may not be called "JDBM" 023 * nor may "JDBM" appear in their names without prior written 024 * permission of Cees de Groot. 025 * 026 * 5. Due credit should be given to the JDBM Project 027 * (http://jdbm.sourceforge.net/). 028 * 029 * THIS SOFTWARE IS PROVIDED BY THE JDBM PROJECT AND CONTRIBUTORS 030 * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT 031 * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 032 * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL 033 * CEES DE GROOT OR ANY CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 034 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 035 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 036 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 037 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 038 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 039 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 040 * OF THE POSSIBILITY OF SUCH DAMAGE. 041 * 042 * Copyright 2001 (C) Alex Boisvert. All Rights Reserved. 043 * Contributions are Copyright (C) 2001 by their associated contributors. 044 * 045 */ 046 047 package jdbm.btree; 048 049 050 import jdbm.helper.Serializer; 051 import jdbm.helper.Tuple; 052 import jdbm.helper.TupleBrowser; 053 054 import java.io.IOException; 055 import java.io.ByteArrayOutputStream; 056 import java.io.ByteArrayInputStream; 057 import java.io.ObjectInput; 058 import java.io.ObjectOutput; 059 import java.io.ObjectInputStream; 060 import java.io.ObjectOutputStream; 061 062 import org.apache.directory.server.i18n.I18n; 063 064 065 /** 066 * Page of a Btree. 067 * <p> 068 * The page contains a number of key-value pairs. Keys are ordered to allow 069 * dichotomic search. 070 * <p> 071 * If the page is a leaf page, the keys and values are user-defined and 072 * represent entries inserted by the user. 073 * <p> 074 * If the page is non-leaf, each key represents the greatest key in the 075 * underlying BPages and the values are recids pointing to the children BPages. 076 * The only exception is the rightmost BPage, which is considered to have an 077 * "infinite" key value, meaning that any insert will be to the left of this 078 * pseudo-key 079 * 080 * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a> 081 * @version $Id: BPage.java,v 1.6 2003/09/21 15:46:59 boisvert Exp $ 082 */ 083 public final class BPage implements Serializer 084 { 085 086 private static final boolean DEBUG = false; 087 088 /** 089 * Version id for serialization. 090 */ 091 final static long serialVersionUID = 1L; 092 093 /** 094 * Parent B+Tree. 095 */ 096 transient BTree _btree; 097 098 /** 099 * This BPage's record ID in the PageManager. 100 */ 101 protected transient long _recid; 102 103 /** 104 * Flag indicating if this is a leaf BPage. 105 */ 106 protected boolean _isLeaf; 107 108 /** 109 * Keys of children nodes 110 */ 111 protected Object[] _keys; 112 113 /** 114 * Values associated with keys. (Only valid if leaf BPage) 115 */ 116 protected Object[] _values; 117 118 /** 119 * Children pages (recids) associated with keys. (Only valid if non-leaf BPage) 120 */ 121 protected long[] _children; 122 123 /** 124 * Index of first used item at the page 125 */ 126 protected int _first; 127 128 /** 129 * Previous leaf BPage (only if this BPage is a leaf) 130 */ 131 protected long _previous; 132 133 /** 134 * Next leaf BPage (only if this BPage is a leaf) 135 */ 136 protected long _next; 137 138 139 /** 140 * No-argument constructor used by serialization. 141 */ 142 public BPage() 143 { 144 // empty 145 } 146 147 148 /** 149 * Root page overflow constructor 150 */ 151 BPage( BTree btree, BPage root, BPage overflow ) throws IOException 152 { 153 _btree = btree; 154 155 _isLeaf = false; 156 157 _first = _btree._pageSize - 2; 158 159 _keys = new Object[_btree._pageSize]; 160 _keys[_btree._pageSize - 2] = overflow.getLargestKey(); 161 _keys[_btree._pageSize - 1] = root.getLargestKey(); 162 163 _children = new long[_btree._pageSize]; 164 _children[_btree._pageSize - 2] = overflow._recid; 165 _children[_btree._pageSize - 1] = root._recid; 166 167 _recid = _btree._recman.insert( this, this ); 168 } 169 170 171 /** 172 * Root page (first insert) constructor. 173 */ 174 BPage( BTree btree, Object key, Object value ) throws IOException 175 { 176 _btree = btree; 177 178 _isLeaf = true; 179 180 _first = btree._pageSize - 2; 181 182 _keys = new Object[_btree._pageSize]; 183 _keys[_btree._pageSize - 2] = key; 184 _keys[_btree._pageSize - 1] = null; // I am the root BPage for now 185 186 _values = new Object[_btree._pageSize]; 187 _values[_btree._pageSize - 2] = value; 188 _values[_btree._pageSize - 1] = null; // I am the root BPage for now 189 190 _recid = _btree._recman.insert( this, this ); 191 } 192 193 194 /** 195 * Overflow page constructor. Creates an empty BPage. 196 */ 197 BPage( BTree btree, boolean isLeaf ) throws IOException 198 { 199 _btree = btree; 200 201 _isLeaf = isLeaf; 202 203 // page will initially be half-full 204 _first = _btree._pageSize / 2; 205 206 _keys = new Object[_btree._pageSize]; 207 if ( isLeaf ) 208 { 209 _values = new Object[_btree._pageSize]; 210 } 211 else 212 { 213 _children = new long[_btree._pageSize]; 214 } 215 216 _recid = _btree._recman.insert( this, this ); 217 } 218 219 220 /** 221 * Get largest key under this BPage. Null is considered to be the 222 * greatest possible key. 223 */ 224 Object getLargestKey() 225 { 226 return _keys[_btree._pageSize - 1]; 227 } 228 229 230 /** 231 * Return true if BPage is empty. 232 */ 233 boolean isEmpty() 234 { 235 if ( _isLeaf ) 236 { 237 return ( _first == _values.length - 1 ); 238 } 239 else 240 { 241 return ( _first == _children.length - 1 ); 242 } 243 } 244 245 246 /** 247 * Return true if BPage is full. 248 */ 249 boolean isFull() 250 { 251 return ( _first == 0 ); 252 } 253 254 255 /** 256 * Find the object associated with the given key. 257 * 258 * @param height Height of the current BPage (zero is leaf page) 259 * @param key The key 260 * @return TupleBrowser positionned just before the given key, or before 261 * next greater key if key isn't found. 262 */ 263 TupleBrowser find( int height, Object key ) throws IOException 264 { 265 int index = findChildren( key ); 266 267 /* 268 if ( DEBUG ) { 269 System.out.println( "BPage.find() current: " + this 270 + " height: " + height); 271 } 272 */ 273 274 height -= 1; 275 276 if ( height == 0 ) 277 { 278 // leaf BPage 279 return new Browser( this, index ); 280 } 281 else 282 { 283 // non-leaf BPage 284 BPage child = childBPage( index ); 285 return child.find( height, key ); 286 } 287 } 288 289 290 /** 291 * Find first entry and return a browser positioned before it. 292 * 293 * @return TupleBrowser positionned just before the first entry. 294 */ 295 TupleBrowser findFirst() throws IOException 296 { 297 if ( _isLeaf ) 298 { 299 return new Browser( this, _first ); 300 } 301 else 302 { 303 BPage child = childBPage( _first ); 304 return child.findFirst(); 305 } 306 } 307 308 309 /** 310 * Insert the given key and value. 311 * <p> 312 * Since the Btree does not support duplicate entries, the caller must 313 * specify whether to replace the existing value. 314 * 315 * @param height Height of the current BPage (zero is leaf page) 316 * @param key Insert key 317 * @param value Insert value 318 * @param replace Set to true to replace the existing value, if one exists. 319 * @return Insertion result containing existing value OR a BPage if the key 320 * was inserted and provoked a BPage overflow. 321 */ 322 InsertResult insert( int height, Object key, Object value, boolean replace ) throws IOException 323 { 324 InsertResult result; 325 long overflow; 326 327 int index = findChildren( key ); 328 329 height -= 1; 330 if ( height == 0 ) 331 { 332 333 result = new InsertResult(); 334 335 // inserting on a leaf BPage 336 overflow = -1; 337 if ( DEBUG ) 338 { 339 System.out.println( "Bpage.insert() Insert on leaf Bpage key=" + key + " value=" + value + " index=" 340 + index ); 341 } 342 if ( compare( key, _keys[index] ) == 0 ) 343 { 344 // key already exists 345 if ( DEBUG ) 346 { 347 System.out.println( "Bpage.insert() Key already exists." ); 348 } 349 result._existing = _values[index]; 350 if ( replace ) 351 { 352 _values[index] = value; 353 _btree._recman.update( _recid, this, this ); 354 } 355 // return the existing key 356 return result; 357 } 358 } 359 else 360 { 361 // non-leaf BPage 362 BPage child = childBPage( index ); 363 result = child.insert( height, key, value, replace ); 364 365 if ( result._existing != null ) 366 { 367 // return existing key, if any. 368 return result; 369 } 370 371 if ( result._overflow == null ) 372 { 373 // no overflow means we're done with insertion 374 return result; 375 } 376 377 // there was an overflow, we need to insert the overflow page 378 // on this BPage 379 if ( DEBUG ) 380 { 381 System.out.println( "BPage.insert() Overflow page: " + result._overflow._recid ); 382 } 383 key = result._overflow.getLargestKey(); 384 overflow = result._overflow._recid; 385 386 // update child's largest key 387 _keys[index] = child.getLargestKey(); 388 389 // clean result so we can reuse it 390 result._overflow = null; 391 } 392 393 // if we get here, we need to insert a new entry on the BPage 394 // before _children[ index ] 395 if ( !isFull() ) 396 { 397 if ( height == 0 ) 398 { 399 insertEntry( this, index - 1, key, value ); 400 } 401 else 402 { 403 insertChild( this, index - 1, key, overflow ); 404 } 405 _btree._recman.update( _recid, this, this ); 406 return result; 407 } 408 409 // page is full, we must divide the page 410 int half = _btree._pageSize >> 1; 411 BPage newPage = new BPage( _btree, _isLeaf ); 412 if ( index < half ) 413 { 414 // move lower-half of entries to overflow BPage, 415 // including new entry 416 if ( DEBUG ) 417 { 418 System.out 419 .println( "Bpage.insert() move lower-half of entries to overflow BPage, including new entry." ); 420 } 421 if ( height == 0 ) 422 { 423 copyEntries( this, 0, newPage, half, index ); 424 setEntry( newPage, half + index, key, value ); 425 copyEntries( this, index, newPage, half + index + 1, half - index - 1 ); 426 } 427 else 428 { 429 copyChildren( this, 0, newPage, half, index ); 430 setChild( newPage, half + index, key, overflow ); 431 copyChildren( this, index, newPage, half + index + 1, half - index - 1 ); 432 } 433 } 434 else 435 { 436 // move lower-half of entries to overflow BPage, 437 // new entry stays on this BPage 438 if ( DEBUG ) 439 { 440 System.out.println( "Bpage.insert() move lower-half of entries to overflow BPage. New entry stays" ); 441 } 442 if ( height == 0 ) 443 { 444 copyEntries( this, 0, newPage, half, half ); 445 copyEntries( this, half, this, half - 1, index - half ); 446 setEntry( this, index - 1, key, value ); 447 } 448 else 449 { 450 copyChildren( this, 0, newPage, half, half ); 451 copyChildren( this, half, this, half - 1, index - half ); 452 setChild( this, index - 1, key, overflow ); 453 } 454 } 455 456 _first = half - 1; 457 458 // nullify lower half of entries 459 for ( int i = 0; i < _first; i++ ) 460 { 461 if ( height == 0 ) 462 { 463 setEntry( this, i, null, null ); 464 } 465 else 466 { 467 setChild( this, i, null, -1 ); 468 } 469 } 470 471 if ( _isLeaf ) 472 { 473 // link newly created BPage 474 newPage._previous = _previous; 475 newPage._next = _recid; 476 if ( _previous != 0 ) 477 { 478 BPage previous = loadBPage( _previous ); 479 previous._next = newPage._recid; 480 _btree._recman.update( _previous, previous, this ); 481 } 482 _previous = newPage._recid; 483 } 484 485 _btree._recman.update( _recid, this, this ); 486 _btree._recman.update( newPage._recid, newPage, this ); 487 488 result._overflow = newPage; 489 return result; 490 } 491 492 493 /** 494 * Remove the entry associated with the given key. 495 * 496 * @param height Height of the current BPage (zero is leaf page) 497 * @param key Removal key 498 * @return Remove result object 499 */ 500 RemoveResult remove( int height, Object key ) throws IOException 501 { 502 RemoveResult result; 503 504 int half = _btree._pageSize / 2; 505 int index = findChildren( key ); 506 507 height -= 1; 508 if ( height == 0 ) 509 { 510 // remove leaf entry 511 if ( compare( _keys[index], key ) != 0 ) 512 { 513 throw new IllegalArgumentException( I18n.err( I18n.ERR_514, key ) ); 514 } 515 result = new RemoveResult(); 516 result._value = _values[index]; 517 removeEntry( this, index ); 518 519 // update this BPage 520 _btree._recman.update( _recid, this, this ); 521 522 } 523 else 524 { 525 // recurse into Btree to remove entry on a children page 526 BPage child = childBPage( index ); 527 result = child.remove( height, key ); 528 529 // update children 530 _keys[index] = child.getLargestKey(); 531 _btree._recman.update( _recid, this, this ); 532 533 if ( result._underflow ) 534 { 535 // underflow occured 536 if ( child._first != half + 1 ) 537 { 538 throw new IllegalStateException( I18n.err( I18n.ERR_513, "1" ) ); 539 } 540 if ( index < _children.length - 1 ) 541 { 542 // exists greater brother page 543 BPage brother = childBPage( index + 1 ); 544 int bfirst = brother._first; 545 if ( bfirst < half ) 546 { 547 // steal entries from "brother" page 548 int steal = ( half - bfirst + 1 ) / 2; 549 brother._first += steal; 550 child._first -= steal; 551 if ( child._isLeaf ) 552 { 553 copyEntries( child, half + 1, child, half + 1 - steal, half - 1 ); 554 copyEntries( brother, bfirst, child, 2 * half - steal, steal ); 555 } 556 else 557 { 558 copyChildren( child, half + 1, child, half + 1 - steal, half - 1 ); 559 copyChildren( brother, bfirst, child, 2 * half - steal, steal ); 560 } 561 562 for ( int i = bfirst; i < bfirst + steal; i++ ) 563 { 564 if ( brother._isLeaf ) 565 { 566 setEntry( brother, i, null, null ); 567 } 568 else 569 { 570 setChild( brother, i, null, -1 ); 571 } 572 } 573 574 // update child's largest key 575 _keys[index] = child.getLargestKey(); 576 577 // no change in previous/next BPage 578 579 // update BPages 580 _btree._recman.update( _recid, this, this ); 581 _btree._recman.update( brother._recid, brother, this ); 582 _btree._recman.update( child._recid, child, this ); 583 584 } 585 else 586 { 587 // move all entries from page "child" to "brother" 588 if ( brother._first != half ) 589 { 590 throw new IllegalStateException( I18n.err( I18n.ERR_513, "2" ) ); 591 } 592 593 brother._first = 1; 594 if ( child._isLeaf ) 595 { 596 copyEntries( child, half + 1, brother, 1, half - 1 ); 597 } 598 else 599 { 600 copyChildren( child, half + 1, brother, 1, half - 1 ); 601 } 602 _btree._recman.update( brother._recid, brother, this ); 603 604 // remove "child" from current BPage 605 if ( _isLeaf ) 606 { 607 copyEntries( this, _first, this, _first + 1, index - _first ); 608 setEntry( this, _first, null, null ); 609 } 610 else 611 { 612 copyChildren( this, _first, this, _first + 1, index - _first ); 613 setChild( this, _first, null, -1 ); 614 } 615 _first += 1; 616 _btree._recman.update( _recid, this, this ); 617 618 // re-link previous and next BPages 619 if ( child._previous != 0 ) 620 { 621 BPage prev = loadBPage( child._previous ); 622 prev._next = child._next; 623 _btree._recman.update( prev._recid, prev, this ); 624 } 625 if ( child._next != 0 ) 626 { 627 BPage next = loadBPage( child._next ); 628 next._previous = child._previous; 629 _btree._recman.update( next._recid, next, this ); 630 } 631 632 // delete "child" BPage 633 _btree._recman.delete( child._recid ); 634 } 635 } 636 else 637 { 638 // page "brother" is before "child" 639 BPage brother = childBPage( index - 1 ); 640 int bfirst = brother._first; 641 if ( bfirst < half ) 642 { 643 // steal entries from "brother" page 644 int steal = ( half - bfirst + 1 ) / 2; 645 brother._first += steal; 646 child._first -= steal; 647 if ( child._isLeaf ) 648 { 649 copyEntries( brother, 2 * half - steal, child, half + 1 - steal, steal ); 650 copyEntries( brother, bfirst, brother, bfirst + steal, 2 * half - bfirst - steal ); 651 } 652 else 653 { 654 copyChildren( brother, 2 * half - steal, child, half + 1 - steal, steal ); 655 copyChildren( brother, bfirst, brother, bfirst + steal, 2 * half - bfirst - steal ); 656 } 657 658 for ( int i = bfirst; i < bfirst + steal; i++ ) 659 { 660 if ( brother._isLeaf ) 661 { 662 setEntry( brother, i, null, null ); 663 } 664 else 665 { 666 setChild( brother, i, null, -1 ); 667 } 668 } 669 670 // update brother's largest key 671 _keys[index - 1] = brother.getLargestKey(); 672 673 // no change in previous/next BPage 674 675 // update BPages 676 _btree._recman.update( _recid, this, this ); 677 _btree._recman.update( brother._recid, brother, this ); 678 _btree._recman.update( child._recid, child, this ); 679 680 } 681 else 682 { 683 // move all entries from page "brother" to "child" 684 if ( brother._first != half ) 685 { 686 throw new IllegalStateException( I18n.err( I18n.ERR_513, "3" ) ); 687 } 688 689 child._first = 1; 690 if ( child._isLeaf ) 691 { 692 copyEntries( brother, half, child, 1, half ); 693 } 694 else 695 { 696 copyChildren( brother, half, child, 1, half ); 697 } 698 _btree._recman.update( child._recid, child, this ); 699 700 // remove "brother" from current BPage 701 if ( _isLeaf ) 702 { 703 copyEntries( this, _first, this, _first + 1, index - 1 - _first ); 704 setEntry( this, _first, null, null ); 705 } 706 else 707 { 708 copyChildren( this, _first, this, _first + 1, index - 1 - _first ); 709 setChild( this, _first, null, -1 ); 710 } 711 _first += 1; 712 _btree._recman.update( _recid, this, this ); 713 714 // re-link previous and next BPages 715 if ( brother._previous != 0 ) 716 { 717 BPage prev = loadBPage( brother._previous ); 718 prev._next = brother._next; 719 _btree._recman.update( prev._recid, prev, this ); 720 } 721 if ( brother._next != 0 ) 722 { 723 BPage next = loadBPage( brother._next ); 724 next._previous = brother._previous; 725 _btree._recman.update( next._recid, next, this ); 726 } 727 728 // delete "brother" BPage 729 _btree._recman.delete( brother._recid ); 730 } 731 } 732 } 733 } 734 735 // underflow if page is more than half-empty 736 result._underflow = _first > half; 737 738 return result; 739 } 740 741 742 /** 743 * Find the first children node with a key equal or greater than the given 744 * key. 745 * 746 * @return index of first children with equal or greater key. 747 */ 748 private int findChildren( Object key ) 749 { 750 int left = _first; 751 int right = _btree._pageSize - 1; 752 753 // binary search 754 while ( left < right ) 755 { 756 int middle = ( left + right ) / 2; 757 if ( compare( _keys[middle], key ) < 0 ) 758 { 759 left = middle + 1; 760 } 761 else 762 { 763 right = middle; 764 } 765 } 766 return right; 767 } 768 769 770 /** 771 * Insert entry at given position. 772 */ 773 private static void insertEntry( BPage page, int index, Object key, Object value ) 774 { 775 Object[] keys = page._keys; 776 Object[] values = page._values; 777 int start = page._first; 778 int count = index - page._first + 1; 779 780 // shift entries to the left 781 System.arraycopy( keys, start, keys, start - 1, count ); 782 System.arraycopy( values, start, values, start - 1, count ); 783 page._first -= 1; 784 keys[index] = key; 785 values[index] = value; 786 } 787 788 789 /** 790 * Insert child at given position. 791 */ 792 private static void insertChild( BPage page, int index, Object key, long child ) 793 { 794 Object[] keys = page._keys; 795 long[] children = page._children; 796 int start = page._first; 797 int count = index - page._first + 1; 798 799 // shift entries to the left 800 System.arraycopy( keys, start, keys, start - 1, count ); 801 System.arraycopy( children, start, children, start - 1, count ); 802 page._first -= 1; 803 keys[index] = key; 804 children[index] = child; 805 } 806 807 808 /** 809 * Remove entry at given position. 810 */ 811 private static void removeEntry( BPage page, int index ) 812 { 813 Object[] keys = page._keys; 814 Object[] values = page._values; 815 int start = page._first; 816 int count = index - page._first; 817 818 System.arraycopy( keys, start, keys, start + 1, count ); 819 keys[start] = null; 820 System.arraycopy( values, start, values, start + 1, count ); 821 values[start] = null; 822 page._first++; 823 } 824 825 826 /** 827 * Remove child at given position. 828 */ 829 /* 830 private static void removeChild( BPage page, int index ) 831 { 832 Object[] keys = page._keys; 833 long[] children = page._children; 834 int start = page._first; 835 int count = index-page._first; 836 837 System.arraycopy( keys, start, keys, start+1, count ); 838 keys[ start ] = null; 839 System.arraycopy( children, start, children, start+1, count ); 840 children[ start ] = (long) -1; 841 page._first++; 842 } 843 */ 844 845 /** 846 * Set the entry at the given index. 847 */ 848 private static void setEntry( BPage page, int index, Object key, Object value ) 849 { 850 page._keys[index] = key; 851 page._values[index] = value; 852 } 853 854 855 /** 856 * Set the child BPage recid at the given index. 857 */ 858 private static void setChild( BPage page, int index, Object key, long recid ) 859 { 860 page._keys[index] = key; 861 page._children[index] = recid; 862 } 863 864 865 /** 866 * Copy entries between two BPages 867 */ 868 private static void copyEntries( BPage source, int indexSource, BPage dest, int indexDest, int count ) 869 { 870 System.arraycopy( source._keys, indexSource, dest._keys, indexDest, count ); 871 System.arraycopy( source._values, indexSource, dest._values, indexDest, count ); 872 } 873 874 875 /** 876 * Copy child BPage recids between two BPages 877 */ 878 private static void copyChildren( BPage source, int indexSource, BPage dest, int indexDest, int count ) 879 { 880 System.arraycopy( source._keys, indexSource, dest._keys, indexDest, count ); 881 System.arraycopy( source._children, indexSource, dest._children, indexDest, count ); 882 } 883 884 885 /** 886 * Return the child BPage at given index. 887 */ 888 BPage childBPage( int index ) throws IOException 889 { 890 return loadBPage( _children[index] ); 891 } 892 893 894 /** 895 * Load the BPage at the given recid. 896 */ 897 private BPage loadBPage( long recid ) throws IOException 898 { 899 BPage child = ( BPage ) _btree._recman.fetch( recid, this ); 900 child._recid = recid; 901 child._btree = _btree; 902 return child; 903 } 904 905 906 private final int compare( Object value1, Object value2 ) 907 { 908 if ( value1 == null ) 909 { 910 return 1; 911 } 912 if ( value2 == null ) 913 { 914 return -1; 915 } 916 return _btree._comparator.compare( value1, value2 ); 917 } 918 919 920 static byte[] readByteArray( ObjectInput in ) throws IOException 921 { 922 int len = in.readInt(); 923 if ( len < 0 ) 924 { 925 return null; 926 } 927 byte[] buf = new byte[len]; 928 in.readFully( buf ); 929 return buf; 930 } 931 932 933 static void writeByteArray( ObjectOutput out, byte[] buf ) throws IOException 934 { 935 if ( buf == null ) 936 { 937 out.writeInt( -1 ); 938 } 939 else 940 { 941 out.writeInt( buf.length ); 942 out.write( buf ); 943 } 944 } 945 946 947 /** 948 * Dump the structure of the tree on the screen. This is used for debugging 949 * purposes only. 950 */ 951 private void dump( int height ) 952 { 953 String prefix = ""; 954 for ( int i = 0; i < height; i++ ) 955 { 956 prefix += " "; 957 } 958 System.out.println( prefix + "-------------------------------------- BPage recid=" + _recid ); 959 System.out.println( prefix + "first=" + _first ); 960 for ( int i = 0; i < _btree._pageSize; i++ ) 961 { 962 if ( _isLeaf ) 963 { 964 System.out.println( prefix + "BPage [" + i + "] " + _keys[i] + " " + _values[i] ); 965 } 966 else 967 { 968 System.out.println( prefix + "BPage [" + i + "] " + _keys[i] + " " + _children[i] ); 969 } 970 } 971 System.out.println( prefix + "--------------------------------------" ); 972 } 973 974 975 /** 976 * Recursively dump the state of the BTree on screen. This is used for 977 * debugging purposes only. 978 */ 979 void dumpRecursive( int height, int level ) throws IOException 980 { 981 height -= 1; 982 level += 1; 983 if ( height > 0 ) 984 { 985 for ( int i = _first; i < _btree._pageSize; i++ ) 986 { 987 if ( _keys[i] == null ) 988 break; 989 BPage child = childBPage( i ); 990 child.dump( level ); 991 child.dumpRecursive( height, level ); 992 } 993 } 994 } 995 996 997 /** 998 * Assert the ordering of the keys on the BPage. This is used for testing 999 * purposes only. 1000 */ 1001 private void assertConsistency() 1002 { 1003 for ( int i = _first; i < _btree._pageSize - 1; i++ ) 1004 { 1005 if ( compare( ( byte[] ) _keys[i], ( byte[] ) _keys[i + 1] ) >= 0 ) 1006 { 1007 dump( 0 ); 1008 throw new Error( I18n.err( I18n.ERR_515 ) ); 1009 } 1010 } 1011 } 1012 1013 1014 /** 1015 * Recursively assert the ordering of the BPage entries on this page 1016 * and sub-pages. This is used for testing purposes only. 1017 */ 1018 void assertConsistencyRecursive( int height ) throws IOException 1019 { 1020 assertConsistency(); 1021 if ( --height > 0 ) 1022 { 1023 for ( int i = _first; i < _btree._pageSize; i++ ) 1024 { 1025 if ( _keys[i] == null ) 1026 break; 1027 BPage child = childBPage( i ); 1028 if ( compare( ( byte[] ) _keys[i], child.getLargestKey() ) != 0 ) 1029 { 1030 dump( 0 ); 1031 child.dump( 0 ); 1032 throw new Error( I18n.err( I18n.ERR_516 ) ); 1033 } 1034 child.assertConsistencyRecursive( height ); 1035 } 1036 } 1037 } 1038 1039 1040 /** 1041 * Deserialize the content of an object from a byte array. 1042 * 1043 * @param serialized Byte array representation of the object 1044 * @return deserialized object 1045 * 1046 */ 1047 public Object deserialize( byte[] serialized ) throws IOException 1048 { 1049 ByteArrayInputStream bais; 1050 ObjectInputStream ois; 1051 BPage bpage; 1052 1053 bpage = new BPage(); 1054 bais = new ByteArrayInputStream( serialized ); 1055 ois = new ObjectInputStream( bais ); 1056 1057 bpage._isLeaf = ois.readBoolean(); 1058 if ( bpage._isLeaf ) 1059 { 1060 bpage._previous = ois.readLong(); 1061 bpage._next = ois.readLong(); 1062 } 1063 1064 bpage._first = ois.readInt(); 1065 1066 bpage._keys = new Object[_btree._pageSize]; 1067 try 1068 { 1069 for ( int i = bpage._first; i < _btree._pageSize; i++ ) 1070 { 1071 if ( _btree._keySerializer == null ) 1072 { 1073 bpage._keys[i] = ois.readObject(); 1074 } 1075 else 1076 { 1077 serialized = readByteArray( ois ); 1078 if ( serialized != null ) 1079 { 1080 bpage._keys[i] = _btree._keySerializer.deserialize( serialized ); 1081 } 1082 } 1083 } 1084 } 1085 catch ( ClassNotFoundException except ) 1086 { 1087 throw new IOException( except.getLocalizedMessage() ); 1088 } 1089 1090 if ( bpage._isLeaf ) 1091 { 1092 bpage._values = new Object[_btree._pageSize]; 1093 try 1094 { 1095 for ( int i = bpage._first; i < _btree._pageSize; i++ ) 1096 { 1097 if ( _btree._valueSerializer == null ) 1098 { 1099 bpage._values[i] = ois.readObject(); 1100 } 1101 else 1102 { 1103 serialized = readByteArray( ois ); 1104 if ( serialized != null ) 1105 { 1106 bpage._values[i] = _btree._valueSerializer.deserialize( serialized ); 1107 } 1108 } 1109 } 1110 } 1111 catch ( ClassNotFoundException except ) 1112 { 1113 throw new IOException( except.getLocalizedMessage() ); 1114 } 1115 } 1116 else 1117 { 1118 bpage._children = new long[_btree._pageSize]; 1119 for ( int i = bpage._first; i < _btree._pageSize; i++ ) 1120 { 1121 bpage._children[i] = ois.readLong(); 1122 } 1123 } 1124 ois.close(); 1125 bais.close(); 1126 1127 return bpage; 1128 } 1129 1130 1131 /** 1132 * Serialize the content of an object into a byte array. 1133 * 1134 * @param obj Object to serialize 1135 * @return a byte array representing the object's state 1136 * 1137 */ 1138 public byte[] serialize( Object obj ) throws IOException 1139 { 1140 byte[] serialized; 1141 ByteArrayOutputStream baos; 1142 ObjectOutputStream oos; 1143 BPage bpage; 1144 byte[] data; 1145 1146 // note: It is assumed that BPage instance doing the serialization is the parent 1147 // of the BPage object being serialized. 1148 1149 bpage = ( BPage ) obj; 1150 baos = new ByteArrayOutputStream(); 1151 oos = new ObjectOutputStream( baos ); 1152 1153 oos.writeBoolean( bpage._isLeaf ); 1154 if ( bpage._isLeaf ) 1155 { 1156 oos.writeLong( bpage._previous ); 1157 oos.writeLong( bpage._next ); 1158 } 1159 1160 oos.writeInt( bpage._first ); 1161 1162 for ( int i = bpage._first; i < _btree._pageSize; i++ ) 1163 { 1164 if ( _btree._keySerializer == null ) 1165 { 1166 oos.writeObject( bpage._keys[i] ); 1167 } 1168 else 1169 { 1170 if ( bpage._keys[i] != null ) 1171 { 1172 serialized = _btree._keySerializer.serialize( bpage._keys[i] ); 1173 writeByteArray( oos, serialized ); 1174 } 1175 else 1176 { 1177 writeByteArray( oos, null ); 1178 } 1179 } 1180 } 1181 1182 if ( bpage._isLeaf ) 1183 { 1184 for ( int i = bpage._first; i < _btree._pageSize; i++ ) 1185 { 1186 if ( _btree._valueSerializer == null ) 1187 { 1188 oos.writeObject( bpage._values[i] ); 1189 } 1190 else 1191 { 1192 if ( bpage._values[i] != null ) 1193 { 1194 serialized = _btree._valueSerializer.serialize( bpage._values[i] ); 1195 writeByteArray( oos, serialized ); 1196 } 1197 else 1198 { 1199 writeByteArray( oos, null ); 1200 } 1201 } 1202 } 1203 } 1204 else 1205 { 1206 for ( int i = bpage._first; i < _btree._pageSize; i++ ) 1207 { 1208 oos.writeLong( bpage._children[i] ); 1209 } 1210 } 1211 1212 oos.flush(); 1213 data = baos.toByteArray(); 1214 oos.close(); 1215 baos.close(); 1216 return data; 1217 } 1218 1219 /** STATIC INNER CLASS 1220 * Result from insert() method call 1221 */ 1222 static class InsertResult 1223 { 1224 1225 /** 1226 * Overflow page. 1227 */ 1228 BPage _overflow; 1229 1230 /** 1231 * Existing value for the insertion key. 1232 */ 1233 Object _existing; 1234 1235 } 1236 1237 /** STATIC INNER CLASS 1238 * Result from remove() method call 1239 */ 1240 static class RemoveResult 1241 { 1242 1243 /** 1244 * Set to true if underlying pages underflowed 1245 */ 1246 boolean _underflow; 1247 1248 /** 1249 * Removed entry value 1250 */ 1251 Object _value; 1252 } 1253 1254 /** PRIVATE INNER CLASS 1255 * Browser to traverse leaf BPages. 1256 */ 1257 static class Browser extends TupleBrowser 1258 { 1259 1260 /** 1261 * Current page. 1262 */ 1263 private BPage _page; 1264 1265 /** 1266 * Current index in the page. The index positionned on the next 1267 * tuple to return. 1268 */ 1269 private int _index; 1270 1271 1272 /** 1273 * Create a browser. 1274 * 1275 * @param page Current page 1276 * @param index Position of the next tuple to return. 1277 */ 1278 Browser( BPage page, int index ) 1279 { 1280 _page = page; 1281 _index = index; 1282 } 1283 1284 1285 public boolean getNext( Tuple tuple ) throws IOException 1286 { 1287 if ( _index < _page._btree._pageSize ) 1288 { 1289 if ( _page._keys[_index] == null ) 1290 { 1291 // reached end of the tree. 1292 return false; 1293 } 1294 } 1295 else if ( _page._next != 0 ) 1296 { 1297 // move to next page 1298 _page = _page.loadBPage( _page._next ); 1299 _index = _page._first; 1300 } 1301 tuple.setKey( _page._keys[_index] ); 1302 tuple.setValue( _page._values[_index] ); 1303 _index++; 1304 return true; 1305 } 1306 1307 1308 public boolean getPrevious( Tuple tuple ) throws IOException 1309 { 1310 if ( _index == _page._first ) 1311 { 1312 1313 if ( _page._previous != 0 ) 1314 { 1315 _page = _page.loadBPage( _page._previous ); 1316 _index = _page._btree._pageSize; 1317 } 1318 else 1319 { 1320 // reached beginning of the tree 1321 return false; 1322 } 1323 } 1324 _index--; 1325 tuple.setKey( _page._keys[_index] ); 1326 tuple.setValue( _page._values[_index] ); 1327 return true; 1328 1329 } 1330 } 1331 1332 }