001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 * 019 */ 020package org.apache.directory.mavibot.btree; 021 022 023import java.util.LinkedList; 024 025import org.apache.directory.mavibot.btree.serializer.ElementSerializer; 026 027 028/** 029 * This class construct a B-tree from a serialized version of a B-tree. We need it 030 * to avoid exposing all the methods of the B-tree class.<br> 031 * 032 * All its methods are static. 033 * 034 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 035 * 036 * @param <K> The B-tree key type 037 * @param <V> The B-tree value type 038 */ 039public class BTreeFactory<K, V> 040{ 041 //-------------------------------------------------------------------------------------------- 042 // Create persisted btrees 043 //-------------------------------------------------------------------------------------------- 044 /** 045 * Creates a new persisted B-tree, with no initialization. 046 * 047 * @return a new B-tree instance 048 */ 049 public static <K, V> BTree<K, V> createPersistedBTree() 050 { 051 BTree<K, V> btree = new PersistedBTree<K, V>(); 052 053 return btree; 054 } 055 056 057 /** 058 * Creates a new persisted B-tree, with no initialization. 059 * 060 * @return a new B-tree instance 061 */ 062 public static <K, V> BTree<K, V> createPersistedBTree( BTreeTypeEnum type ) 063 { 064 BTree<K, V> btree = new PersistedBTree<K, V>(); 065 ( ( AbstractBTree<K, V> ) btree ).setType( type ); 066 067 return btree; 068 } 069 070 071 /** 072 * Sets the btreeHeader offset for a Persisted BTree 073 * 074 * @param btree The btree to update 075 * @param btreeHeaderOffset The offset 076 */ 077 public static <K, V> void setBtreeHeaderOffset( PersistedBTree<K, V> btree, long btreeHeaderOffset ) 078 { 079 btree.setBtreeHeaderOffset( btreeHeaderOffset ); 080 } 081 082 083 /** 084 * Creates a new persisted B-tree using the BTreeConfiguration to initialize the 085 * B-tree 086 * 087 * @param configuration The configuration to use 088 * @return a new B-tree instance 089 */ 090 public static <K, V> BTree<K, V> createPersistedBTree( PersistedBTreeConfiguration<K, V> configuration ) 091 { 092 BTree<K, V> btree = new PersistedBTree<K, V>( configuration ); 093 094 return btree; 095 } 096 097 098 /** 099 * Creates a new persisted B-tree using the parameters to initialize the 100 * B-tree 101 * 102 * @param name The B-tree's name 103 * @param keySerializer Key serializer 104 * @param valueSerializer Value serializer 105 * @return a new B-tree instance 106 */ 107 public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer, 108 ElementSerializer<V> valueSerializer ) 109 { 110 PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>(); 111 112 configuration.setName( name ); 113 configuration.setKeySerializer( keySerializer ); 114 configuration.setValueSerializer( valueSerializer ); 115 configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE ); 116 configuration.setAllowDuplicates( BTree.FORBID_DUPLICATES ); 117 configuration.setCacheSize( PersistedBTree.DEFAULT_CACHE_SIZE ); 118 configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE ); 119 120 BTree<K, V> btree = new PersistedBTree<K, V>( configuration ); 121 122 return btree; 123 } 124 125 126 /** 127 * Creates a new persisted B-tree using the parameters to initialize the 128 * B-tree 129 * 130 * @param name The B-tree's name 131 * @param keySerializer Key serializer 132 * @param valueSerializer Value serializer 133 * @param allowDuplicates Tells if the B-tree allows multiple value for a given key 134 * @return a new B-tree instance 135 */ 136 public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer, 137 ElementSerializer<V> valueSerializer, boolean allowDuplicates ) 138 { 139 PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>(); 140 141 configuration.setName( name ); 142 configuration.setKeySerializer( keySerializer ); 143 configuration.setValueSerializer( valueSerializer ); 144 configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE ); 145 configuration.setAllowDuplicates( allowDuplicates ); 146 configuration.setCacheSize( PersistedBTree.DEFAULT_CACHE_SIZE ); 147 configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE ); 148 149 BTree<K, V> btree = new PersistedBTree<K, V>( configuration ); 150 151 return btree; 152 } 153 154 155 /** 156 * Creates a new persisted B-tree using the parameters to initialize the 157 * B-tree 158 * 159 * @param name The B-tree's name 160 * @param keySerializer Key serializer 161 * @param valueSerializer Value serializer 162 * @param allowDuplicates Tells if the B-tree allows multiple value for a given key 163 * @param cacheSize The size to be used for this B-tree cache 164 * @return a new B-tree instance 165 */ 166 public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer, 167 ElementSerializer<V> valueSerializer, boolean allowDuplicates, int cacheSize ) 168 { 169 PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>(); 170 171 configuration.setName( name ); 172 configuration.setKeySerializer( keySerializer ); 173 configuration.setValueSerializer( valueSerializer ); 174 configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE ); 175 configuration.setAllowDuplicates( allowDuplicates ); 176 configuration.setCacheSize( cacheSize ); 177 configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE ); 178 179 BTree<K, V> btree = new PersistedBTree<K, V>( configuration ); 180 181 return btree; 182 } 183 184 185 /** 186 * Creates a new persisted B-tree using the parameters to initialize the 187 * B-tree 188 * 189 * @param name The B-tree's name 190 * @param keySerializer Key serializer 191 * @param valueSerializer Value serializer 192 * @param pageSize Size of the page 193 * @return a new B-tree instance 194 */ 195 public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer, 196 ElementSerializer<V> valueSerializer, int pageSize ) 197 { 198 PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>(); 199 200 configuration.setName( name ); 201 configuration.setKeySerializer( keySerializer ); 202 configuration.setValueSerializer( valueSerializer ); 203 configuration.setPageSize( pageSize ); 204 configuration.setAllowDuplicates( BTree.FORBID_DUPLICATES ); 205 configuration.setCacheSize( PersistedBTree.DEFAULT_CACHE_SIZE ); 206 configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE ); 207 208 BTree<K, V> btree = new PersistedBTree<K, V>( configuration ); 209 210 return btree; 211 } 212 213 214 /** 215 * Creates a new persisted B-tree using the parameters to initialize the 216 * B-tree 217 * 218 * @param name The B-tree's name 219 * @param keySerializer Key serializer 220 * @param valueSerializer Value serializer 221 * @param pageSize Size of the page 222 * @param allowDuplicates Tells if the B-tree allows multiple value for a given key 223 * @return a new B-tree instance 224 */ 225 public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer, 226 ElementSerializer<V> valueSerializer, int pageSize, boolean allowDuplicates ) 227 { 228 PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>(); 229 230 configuration.setName( name ); 231 configuration.setKeySerializer( keySerializer ); 232 configuration.setValueSerializer( valueSerializer ); 233 configuration.setPageSize( pageSize ); 234 configuration.setAllowDuplicates( allowDuplicates ); 235 configuration.setCacheSize( PersistedBTree.DEFAULT_CACHE_SIZE ); 236 configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE ); 237 238 BTree<K, V> btree = new PersistedBTree<K, V>( configuration ); 239 240 return btree; 241 } 242 243 244 /** 245 * Creates a new persisted B-tree using the parameters to initialize the 246 * B-tree 247 * 248 * @param name The B-tree's name 249 * @param keySerializer Key serializer 250 * @param valueSerializer Value serializer 251 * @param pageSize Size of the page 252 * @param allowDuplicates Tells if the B-tree allows multiple value for a given key 253 * @param cacheSize The size to be used for this B-tree cache 254 * @return a new B-tree instance 255 */ 256 public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer, 257 ElementSerializer<V> valueSerializer, int pageSize, boolean allowDuplicates, int cacheSize ) 258 { 259 PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>(); 260 261 configuration.setName( name ); 262 configuration.setKeySerializer( keySerializer ); 263 configuration.setValueSerializer( valueSerializer ); 264 configuration.setPageSize( pageSize ); 265 configuration.setAllowDuplicates( allowDuplicates ); 266 configuration.setCacheSize( cacheSize ); 267 configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE ); 268 269 BTree<K, V> btree = new PersistedBTree<K, V>( configuration ); 270 271 return btree; 272 } 273 274 275 //-------------------------------------------------------------------------------------------- 276 // Create in-memory B-trees 277 //-------------------------------------------------------------------------------------------- 278 /** 279 * Creates a new in-memory B-tree, with no initialization. 280 * 281 * @return a new B-tree instance 282 */ 283 public static <K, V> BTree<K, V> createInMemoryBTree() 284 { 285 BTree<K, V> btree = new InMemoryBTree<K, V>(); 286 287 return btree; 288 } 289 290 291 /** 292 * Creates a new in-memory B-tree using the BTreeConfiguration to initialize the 293 * B-tree 294 * 295 * @param configuration The configuration to use 296 * @return a new B-tree instance 297 */ 298 public static <K, V> BTree<K, V> createInMemoryBTree( InMemoryBTreeConfiguration<K, V> configuration ) 299 { 300 BTree<K, V> btree = new InMemoryBTree<K, V>( configuration ); 301 302 return btree; 303 } 304 305 306 /** 307 * Creates a new in-memory B-tree using the parameters to initialize the 308 * B-tree 309 * 310 * @param name The B-tree's name 311 * @param keySerializer Key serializer 312 * @param valueSerializer Value serializer 313 * @return a new B-tree instance 314 */ 315 public static <K, V> BTree<K, V> createInMemoryBTree( String name, ElementSerializer<K> keySerializer, 316 ElementSerializer<V> valueSerializer ) 317 { 318 InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>(); 319 320 configuration.setName( name ); 321 configuration.setKeySerializer( keySerializer ); 322 configuration.setValueSerializer( valueSerializer ); 323 configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE ); 324 configuration.setAllowDuplicates( BTree.FORBID_DUPLICATES ); 325 configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE ); 326 327 BTree<K, V> btree = new InMemoryBTree<K, V>( configuration ); 328 329 return btree; 330 } 331 332 333 /** 334 * Creates a new in-memory B-tree using the parameters to initialize the 335 * B-tree 336 * 337 * @param name The B-tree's name 338 * @param keySerializer Key serializer 339 * @param valueSerializer Value serializer 340 * @param allowDuplicates Tells if the B-tree allows multiple value for a given key 341 * @return a new B-tree instance 342 */ 343 public static <K, V> BTree<K, V> createInMemoryBTree( String name, ElementSerializer<K> keySerializer, 344 ElementSerializer<V> valueSerializer, boolean allowDuplicates ) 345 { 346 InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>(); 347 348 configuration.setName( name ); 349 configuration.setKeySerializer( keySerializer ); 350 configuration.setValueSerializer( valueSerializer ); 351 configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE ); 352 configuration.setAllowDuplicates( allowDuplicates ); 353 configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE ); 354 355 BTree<K, V> btree = new InMemoryBTree<K, V>( configuration ); 356 357 return btree; 358 } 359 360 361 /** 362 * Creates a new in-memory B-tree using the parameters to initialize the 363 * B-tree 364 * 365 * @param name The B-tree's name 366 * @param keySerializer Key serializer 367 * @param valueSerializer Value serializer 368 * @param pageSize Size of the page 369 * @return a new B-tree instance 370 */ 371 public static <K, V> BTree<K, V> createInMemoryBTree( String name, ElementSerializer<K> keySerializer, 372 ElementSerializer<V> valueSerializer, int pageSize ) 373 { 374 InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>(); 375 376 configuration.setName( name ); 377 configuration.setKeySerializer( keySerializer ); 378 configuration.setValueSerializer( valueSerializer ); 379 configuration.setPageSize( pageSize ); 380 configuration.setAllowDuplicates( BTree.FORBID_DUPLICATES ); 381 configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE ); 382 383 BTree<K, V> btree = new InMemoryBTree<K, V>( configuration ); 384 385 return btree; 386 } 387 388 389 /** 390 * Creates a new in-memory B-tree using the parameters to initialize the 391 * B-tree 392 * 393 * @param name The B-tree's name 394 * @param filePath The name of the data directory with absolute path 395 * @param keySerializer Key serializer 396 * @param valueSerializer Value serializer 397 * @return a new B-tree instance 398 */ 399 public static <K, V> BTree<K, V> createInMemoryBTree( String name, String filePath, 400 ElementSerializer<K> keySerializer, 401 ElementSerializer<V> valueSerializer ) 402 { 403 InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>(); 404 405 configuration.setName( name ); 406 configuration.setFilePath( filePath ); 407 configuration.setKeySerializer( keySerializer ); 408 configuration.setValueSerializer( valueSerializer ); 409 configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE ); 410 configuration.setAllowDuplicates( BTree.FORBID_DUPLICATES ); 411 configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE ); 412 413 BTree<K, V> btree = new InMemoryBTree<K, V>( configuration ); 414 415 return btree; 416 } 417 418 419 /** 420 * Creates a new in-memory B-tree using the parameters to initialize the 421 * B-tree 422 * 423 * @param name The B-tree's name 424 * @param filePath The name of the data directory with absolute path 425 * @param keySerializer Key serializer 426 * @param valueSerializer Value serializer 427 * @param pageSize Size of the page 428 * @return a new B-tree instance 429 */ 430 public static <K, V> BTree<K, V> createInMemoryBTree( String name, String filePath, 431 ElementSerializer<K> keySerializer, ElementSerializer<V> valueSerializer, int pageSize ) 432 { 433 InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>(); 434 435 configuration.setName( name ); 436 configuration.setFilePath( filePath ); 437 configuration.setKeySerializer( keySerializer ); 438 configuration.setValueSerializer( valueSerializer ); 439 configuration.setPageSize( pageSize ); 440 configuration.setAllowDuplicates( BTree.FORBID_DUPLICATES ); 441 configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE ); 442 443 BTree<K, V> btree = new InMemoryBTree<K, V>( configuration ); 444 445 return btree; 446 } 447 448 449 /** 450 * Creates a new in-memory B-tree using the parameters to initialize the 451 * B-tree 452 * 453 * @param name The B-tree's name 454 * @param filePath The name of the data directory with absolute path 455 * @param keySerializer Key serializer 456 * @param valueSerializer Value serializer 457 * @param pageSize Size of the page 458 * @param allowDuplicates Tells if the B-tree allows multiple value for a given key 459 * @return a new B-tree instance 460 */ 461 public static <K, V> BTree<K, V> createInMemoryBTree( String name, String filePath, 462 ElementSerializer<K> keySerializer, 463 ElementSerializer<V> valueSerializer, int pageSize, boolean allowDuplicates ) 464 { 465 InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>(); 466 467 configuration.setName( name ); 468 configuration.setFilePath( filePath ); 469 configuration.setKeySerializer( keySerializer ); 470 configuration.setValueSerializer( valueSerializer ); 471 configuration.setPageSize( pageSize ); 472 configuration.setAllowDuplicates( allowDuplicates ); 473 configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE ); 474 475 BTree<K, V> btree = new InMemoryBTree<K, V>( configuration ); 476 477 return btree; 478 } 479 480 481 //-------------------------------------------------------------------------------------------- 482 // Create Pages 483 //-------------------------------------------------------------------------------------------- 484 /** 485 * Create a new Leaf for the given B-tree. 486 * 487 * @param btree The B-tree which will contain this leaf 488 * @param revision The Leaf's revision 489 * @param nbElems The number or elements in this leaf 490 * 491 * @return A Leaf instance 492 */ 493 /* no qualifier*/static <K, V> Page<K, V> createLeaf( BTree<K, V> btree, long revision, int nbElems ) 494 { 495 if ( btree.getType() != BTreeTypeEnum.IN_MEMORY ) 496 { 497 return new PersistedLeaf<K, V>( btree, revision, nbElems ); 498 } 499 else 500 { 501 return new InMemoryLeaf<K, V>( btree, revision, nbElems ); 502 } 503 } 504 505 506 /** 507 * Create a new Node for the given B-tree. 508 * 509 * @param btree The B-tree which will contain this node 510 * @param revision The Node's revision 511 * @param nbElems The number or elements in this node 512 * @return A Node instance 513 */ 514 /* no qualifier*/static <K, V> Page<K, V> createNode( BTree<K, V> btree, long revision, int nbElems ) 515 { 516 if ( btree.getType() != BTreeTypeEnum.IN_MEMORY ) 517 { 518 //System.out.println( "Creating a node with nbElems : " + nbElems ); 519 return new PersistedNode<K, V>( btree, revision, nbElems ); 520 } 521 else 522 { 523 return new InMemoryNode<K, V>( btree, revision, nbElems ); 524 } 525 } 526 527 528 //-------------------------------------------------------------------------------------------- 529 // Update pages 530 //-------------------------------------------------------------------------------------------- 531 /** 532 * Set the key at a give position 533 * 534 * @param btree The B-tree to update 535 * @param page The page to update 536 * @param pos The position in the keys array 537 * @param key The key to inject 538 */ 539 /* no qualifier*/static <K, V> void setKey( BTree<K, V> btree, Page<K, V> page, int pos, K key ) 540 { 541 KeyHolder<K> keyHolder; 542 543 if ( btree.getType() != BTreeTypeEnum.IN_MEMORY ) 544 { 545 keyHolder = new PersistedKeyHolder<K>( btree.getKeySerializer(), key ); 546 } 547 else 548 { 549 keyHolder = new KeyHolder<K>( key ); 550 } 551 552 ( ( AbstractPage<K, V> ) page ).setKey( pos, keyHolder ); 553 } 554 555 556 /** 557 * Set the value at a give position 558 * 559 * @param btree The B-tree to update 560 * @param page The page to update 561 * @param pos The position in the values array 562 * @param value the value to inject 563 */ 564 /* no qualifier*/static <K, V> void setValue( BTree<K, V> btree, Page<K, V> page, int pos, ValueHolder<V> value ) 565 { 566 if ( btree.getType() != BTreeTypeEnum.IN_MEMORY ) 567 { 568 ( ( PersistedLeaf<K, V> ) page ).setValue( pos, value ); 569 } 570 else 571 { 572 ( ( InMemoryLeaf<K, V> ) page ).setValue( pos, value ); 573 } 574 } 575 576 577 /** 578 * Set the page at a give position 579 * 580 * @param btree The B-tree to update 581 * @param page The page to update 582 * @param pos The position in the values array 583 * @param child the child page to inject 584 */ 585 /* no qualifier*/static <K, V> void setPage( BTree<K, V> btree, Page<K, V> page, int pos, Page<K, V> child ) 586 { 587 if ( btree.getType() != BTreeTypeEnum.IN_MEMORY ) 588 { 589 ( ( PersistedNode<K, V> ) page ).setValue( pos, new PersistedPageHolder<K, V>( btree, child ) ); 590 } 591 else 592 { 593 ( ( InMemoryNode<K, V> ) page ).setPageHolder( pos, new PageHolder<K, V>( btree, child ) ); 594 } 595 } 596 597 598 //-------------------------------------------------------------------------------------------- 599 // Update B-tree 600 //-------------------------------------------------------------------------------------------- 601 /** 602 * Sets the KeySerializer into the B-tree 603 * 604 * @param btree The B-tree to update 605 * @param keySerializerFqcn the Key serializer FQCN to set 606 * @throws ClassNotFoundException If the key serializer class cannot be found 607 * @throws InstantiationException If the key serializer class cannot be instanciated 608 * @throws IllegalAccessException If the key serializer class cannot be accessed 609 * @throws NoSuchFieldException 610 * @throws SecurityException 611 * @throws IllegalArgumentException 612 */ 613 /* no qualifier*/static <K, V> void setKeySerializer( BTree<K, V> btree, String keySerializerFqcn ) 614 throws ClassNotFoundException, IllegalAccessException, InstantiationException, IllegalArgumentException, 615 SecurityException, NoSuchFieldException 616 { 617 Class<?> keySerializer = Class.forName( keySerializerFqcn ); 618 @SuppressWarnings("unchecked") 619 ElementSerializer<K> instance = null; 620 try 621 { 622 instance = ( ElementSerializer<K> ) keySerializer.getDeclaredField( "INSTANCE" ).get( null ); 623 } 624 catch ( NoSuchFieldException e ) 625 { 626 // ignore 627 } 628 629 if ( instance == null ) 630 { 631 instance = ( ElementSerializer<K> ) keySerializer.newInstance(); 632 } 633 634 btree.setKeySerializer( instance ); 635 } 636 637 638 /** 639 * Sets the ValueSerializer into the B-tree 640 * 641 * @param btree The B-tree to update 642 * @param valueSerializerFqcn the Value serializer FQCN to set 643 * @throws ClassNotFoundException If the value serializer class cannot be found 644 * @throws InstantiationException If the value serializer class cannot be instanciated 645 * @throws IllegalAccessException If the value serializer class cannot be accessed 646 * @throws NoSuchFieldException 647 * @throws SecurityException 648 * @throws IllegalArgumentException 649 */ 650 /* no qualifier*/static <K, V> void setValueSerializer( BTree<K, V> btree, String valueSerializerFqcn ) 651 throws ClassNotFoundException, IllegalAccessException, InstantiationException, IllegalArgumentException, 652 SecurityException, NoSuchFieldException 653 { 654 Class<?> valueSerializer = Class.forName( valueSerializerFqcn ); 655 @SuppressWarnings("unchecked") 656 ElementSerializer<V> instance = null; 657 try 658 { 659 instance = ( ElementSerializer<V> ) valueSerializer.getDeclaredField( "INSTANCE" ).get( null ); 660 } 661 catch ( NoSuchFieldException e ) 662 { 663 // ignore 664 } 665 666 if ( instance == null ) 667 { 668 instance = ( ElementSerializer<V> ) valueSerializer.newInstance(); 669 } 670 671 btree.setValueSerializer( instance ); 672 } 673 674 675 /** 676 * Set the new root page for this tree. Used for debug purpose only. The revision 677 * will always be 0; 678 * 679 * @param btree The B-tree to update 680 * @param root the new root page. 681 */ 682 /* no qualifier*/static <K, V> void setRootPage( BTree<K, V> btree, Page<K, V> root ) 683 { 684 ( ( AbstractBTree<K, V> ) btree ).setRootPage( root ); 685 } 686 687 688 /** 689 * Return the B-tree root page 690 * 691 * @param btree The B-tree we want to root page from 692 * @return The root page 693 */ 694 /* no qualifier */static <K, V> Page<K, V> getRootPage( BTree<K, V> btree ) 695 { 696 return btree.getRootPage(); 697 } 698 699 700 /** 701 * Update the B-tree number of elements 702 * 703 * @param btree The B-tree to update 704 * @param nbElems the nbElems to set 705 */ 706 /* no qualifier */static <K, V> void setNbElems( BTree<K, V> btree, long nbElems ) 707 { 708 ( ( AbstractBTree<K, V> ) btree ).setNbElems( nbElems ); 709 } 710 711 712 /** 713 * Update the B-tree revision 714 * 715 * @param btree The B-tree to update 716 * @param revision the revision to set 717 */ 718 /* no qualifier*/static <K, V> void setRevision( BTree<K, V> btree, long revision ) 719 { 720 ( ( AbstractBTree<K, V> ) btree ).setRevision( revision ); 721 } 722 723 724 /** 725 * Set the B-tree name 726 * 727 * @param btree The B-tree to update 728 * @param name the name to set 729 */ 730 /* no qualifier */static <K, V> void setName( BTree<K, V> btree, String name ) 731 { 732 btree.setName( name ); 733 } 734 735 736 /** 737 * Set the maximum number of elements we can store in a page. 738 * 739 * @param btree The B-tree to update 740 * @param pageSize The requested page size 741 */ 742 /* no qualifier */static <K, V> void setPageSize( BTree<K, V> btree, int pageSize ) 743 { 744 btree.setPageSize( pageSize ); 745 } 746 747 748 //-------------------------------------------------------------------------------------------- 749 // Utility method 750 //-------------------------------------------------------------------------------------------- 751 /** 752 * Includes the intermediate nodes in the path up to and including the right most leaf of the tree 753 * 754 * @param btree the B-tree 755 * @return a LinkedList of all the nodes and the final leaf 756 */ 757 /* no qualifier*/static <K, V> LinkedList<ParentPos<K, V>> getPathToRightMostLeaf( BTree<K, V> btree ) 758 { 759 LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>(); 760 761 ParentPos<K, V> last = new ParentPos<K, V>( btree.getRootPage(), btree.getRootPage().getNbElems() ); 762 stack.push( last ); 763 764 if ( btree.getRootPage().isLeaf() ) 765 { 766 Page<K, V> leaf = btree.getRootPage(); 767 ValueHolder<V> valueHolder = ( ( AbstractPage<K, V> ) leaf ).getValue( last.pos ); 768 last.valueCursor = valueHolder.getCursor(); 769 } 770 else 771 { 772 Page<K, V> node = btree.getRootPage(); 773 774 while ( true ) 775 { 776 Page<K, V> p = ( ( AbstractPage<K, V> ) node ).getPage( node.getNbElems() ); 777 778 last = new ParentPos<K, V>( p, p.getNbElems() ); 779 stack.push( last ); 780 781 if ( p.isLeaf() ) 782 { 783 Page<K, V> leaf = last.page; 784 ValueHolder<V> valueHolder = ( ( AbstractPage<K, V> ) leaf ).getValue( last.pos ); 785 last.valueCursor = valueHolder.getCursor(); 786 break; 787 } 788 } 789 } 790 791 return stack; 792 } 793 794 795 //-------------------------------------------------------------------------------------------- 796 // Persisted B-tree methods 797 //-------------------------------------------------------------------------------------------- 798 /** 799 * Set the rootPage offset of the B-tree 800 * 801 * @param btree The B-tree to update 802 * @param rootPageOffset The rootPageOffset to set 803 */ 804 /* no qualifier*/static <K, V> void setRootPageOffset( BTree<K, V> btree, long rootPageOffset ) 805 { 806 if ( btree instanceof PersistedBTree ) 807 { 808 ( ( PersistedBTree<K, V> ) btree ).getBtreeHeader().setRootPageOffset( rootPageOffset ); 809 } 810 else 811 { 812 throw new IllegalArgumentException( "The B-tree must be a PersistedBTree" ); 813 } 814 } 815 816 817 /** 818 * Set the RecordManager 819 * 820 * @param btree The B-tree to update 821 * @param recordManager The injected RecordManager 822 */ 823 /* no qualifier*/static <K, V> void setRecordManager( BTree<K, V> btree, RecordManager recordManager ) 824 { 825 if ( btree instanceof PersistedBTree ) 826 { 827 ( ( PersistedBTree<K, V> ) btree ).setRecordManager( recordManager ); 828 } 829 else 830 { 831 throw new IllegalArgumentException( "The B-tree must be a PersistedBTree" ); 832 } 833 } 834 835 836 /** 837 * Set the key at a give position 838 * 839 * @param btree The B-tree to update 840 * @param page The page to update 841 * @param pos The position of this key in the page 842 * @param buffer The byte[] containing the serialized key 843 */ 844 /* no qualifier*/static <K, V> void setKey( BTree<K, V> btree, Page<K, V> page, int pos, byte[] buffer ) 845 { 846 if ( btree instanceof PersistedBTree ) 847 { 848 KeyHolder<K> keyHolder = new PersistedKeyHolder<K>( btree.getKeySerializer(), buffer ); 849 ( ( AbstractPage<K, V> ) page ).setKey( pos, keyHolder ); 850 } 851 else 852 { 853 throw new IllegalArgumentException( "The B-tree must be a PersistedBTree" ); 854 } 855 } 856 857 858 /** 859 * Includes the intermediate nodes in the path up to and including the left most leaf of the tree 860 * 861 * @param btree The B-tree to process 862 * @return a LinkedList of all the nodes and the final leaf 863 */ 864 /* no qualifier*/static <K, V> LinkedList<ParentPos<K, V>> getPathToLeftMostLeaf( BTree<K, V> btree ) 865 { 866 if ( btree instanceof PersistedBTree ) 867 { 868 LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>(); 869 870 ParentPos<K, V> first = new ParentPos<K, V>( btree.getRootPage(), 0 ); 871 stack.push( first ); 872 873 if ( btree.getRootPage().isLeaf() ) 874 { 875 Page<K, V> leaf = btree.getRootPage(); 876 ValueHolder<V> valueHolder = ( ( AbstractPage<K, V> ) leaf ).getValue( first.pos ); 877 first.valueCursor = valueHolder.getCursor(); 878 } 879 else 880 { 881 Page<K, V> node = btree.getRootPage(); 882 883 while ( true ) 884 { 885 Page<K, V> page = ( ( AbstractPage<K, V> ) node ).getPage( 0 ); 886 887 first = new ParentPos<K, V>( page, 0 ); 888 stack.push( first ); 889 890 if ( page.isLeaf() ) 891 { 892 ValueHolder<V> valueHolder = ( ( AbstractPage<K, V> ) page ).getValue( first.pos ); 893 first.valueCursor = valueHolder.getCursor(); 894 break; 895 } 896 } 897 } 898 899 return stack; 900 } 901 else 902 { 903 throw new IllegalArgumentException( "The B-tree must be a PersistedBTree" ); 904 } 905 } 906}