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 */ 020 021package org.apache.directory.mavibot.btree; 022 023 024import java.io.IOException; 025import java.lang.reflect.Array; 026import java.util.ArrayList; 027import java.util.Iterator; 028import java.util.List; 029 030import org.apache.directory.mavibot.btree.serializer.ElementSerializer; 031 032 033/** 034 * A BTree builder that builds a tree from the bottom. 035 * 036 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 037 */ 038public class InMemoryBTreeBuilder<K, V> 039{ 040 /** The Btree configuration */ 041 private InMemoryBTreeConfiguration<K, V> btreeConfiguration; 042 043 044 /** 045 * Creates a new instance of InMemoryBTreeBuilder. 046 * 047 * @param name The BTree name 048 * @param numKeysInNode The number of keys per node 049 * @param keySerializer The key serializer 050 * @param valueSerializer The value serializer 051 */ 052 public InMemoryBTreeBuilder( String name, int numKeysInNode, ElementSerializer<K> keySerializer, 053 ElementSerializer<V> valueSerializer ) 054 { 055 btreeConfiguration = new InMemoryBTreeConfiguration<K, V>(); 056 btreeConfiguration.setName( name ); 057 btreeConfiguration.setPageSize( numKeysInNode ); 058 btreeConfiguration.setKeySerializer( keySerializer ); 059 btreeConfiguration.setValueSerializer( valueSerializer ); 060 } 061 062 063 /** 064 * Creates a new instance of InMemoryBTreeBuilder. 065 * 066 * @param btreeConfiguration The Btree configuration 067 */ 068 public InMemoryBTreeBuilder( InMemoryBTreeConfiguration<K, V> btreeConfiguration ) 069 { 070 this.btreeConfiguration = btreeConfiguration; 071 } 072 073 074 @SuppressWarnings("unchecked") 075 public BTree<K, V> build( Iterator<Tuple<K, V>> sortedTupleItr ) throws IOException 076 { 077 BTree<K, V> btree = BTreeFactory.createInMemoryBTree( btreeConfiguration ); 078 int pageSize = btree.getPageSize(); 079 int maxElements = ( pageSize + 1 ) * pageSize; 080 081 // The stack used to store all the levels. No need to have more than 16 levels, 082 // it will allow the storage of 2^64 elements with pages containing 4 elements each. 083 List<InMemoryNode<K, V>>[] pageStack = new ArrayList[15]; 084 085 for ( int i = 0; i < 15; i++ ) 086 { 087 pageStack[i] = new ArrayList<InMemoryNode<K, V>>( maxElements ); 088 } 089 090 // The number of added elements 091 int nbAdded = 0; 092 093 // The btree height 094 int btreeHeight = 0; 095 096 // An array containing the number of elements necessary to fulfill a layer : 097 // pageSize * (pageSize + 1) 098 List<Tuple<K, V>> tuples = new ArrayList<Tuple<K, V>>( maxElements ); 099 100 // A list of nodes that are going to be created 101 List<InMemoryNode<K, V>> nodes = new ArrayList<InMemoryNode<K, V>>(); 102 103 // Now, loop on all the elements 104 while ( sortedTupleItr.hasNext() ) 105 { 106 nbAdded++; 107 108 // Get the tuple to inject 109 Tuple<K, V> tuple = sortedTupleItr.next(); 110 tuples.add( tuple ); 111 112 if ( tuples.size() == maxElements ) 113 { 114 // We have enough elements to create pageSize leaves, and the upper node 115 InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) addLeaves( btree, tuples, maxElements ); 116 int level = 0; 117 118 if ( node != null ) 119 { 120 while ( true ) 121 { 122 pageStack[level].add( node ); 123 124 // If the node list has enough elements to fulfill a parent node, 125 // then process 126 if ( pageStack[level].size() > btree.getPageSize() ) 127 { 128 node = createParentNode( btree, pageStack[level], btree.getPageSize() ); 129 pageStack[level].clear(); 130 level++; 131 } 132 else 133 { 134 break; 135 } 136 } 137 138 ( ( AbstractBTree<K, V> ) btree ).setRootPage( pageStack[level].get( 0 ) ); 139 140 // Update the btree height 141 if ( btreeHeight < level ) 142 { 143 btreeHeight = level; 144 } 145 } 146 147 tuples.clear(); 148 } 149 } 150 151 if ( tuples.size() > 0 ) 152 { 153 // Let's deal with the remaining elements 154 Page<K, V> page = addLeaves( btree, tuples, maxElements ); 155 156 if ( page instanceof InMemoryNode ) 157 { 158 nodes.add( ( InMemoryNode<K, V> ) page ); 159 160 // If the node list has enough elements to fulfill a parent node, 161 // then process 162 if ( nodes.size() == maxElements ) 163 { 164 Page<K, V> rootPage = createParentNode( btree, nodes, maxElements ); 165 166 ( ( AbstractBTree<K, V> ) btree ).setRootPage( rootPage ); 167 } 168 } 169 else 170 { 171 InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) page; 172 173 // Its a leaf. That means we may have to balance the btree 174 if ( pageStack[0].size() != 0 ) 175 { 176 // We have some leaves in level 0, which means we just have to add the new leaf 177 // there, after having check we don't have to borrow some elements from the last leaf 178 if ( leaf.getNbElems() < btree.getPageSize() / 2 ) 179 { 180 // Not enough elements in the added leaf. Borrow some from the left. 181 // TODO 182 } 183 else 184 { 185 // Enough elements in the added leaf (at least N/2). We just have to update 186 // the parent's node. 187 // TODO 188 } 189 } 190 } 191 } 192 193 // Update the number of elements 194 ( ( AbstractBTree<K, V> ) btree ).getBtreeHeader().setNbElems( nbAdded ); 195 196 return btree; 197 } 198 199 200 /** 201 * Creates all the nodes using the provided node pages, and update the upper laye 202 */ 203 private InMemoryNode<K, V> createParentNode( BTree<K, V> btree, List<InMemoryNode<K, V>> nodes, int maxElements ) 204 { 205 // We have enough tuples to fulfill the upper node. 206 // First, create the new node 207 InMemoryNode<K, V> parentNode = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0, 208 btreeConfiguration.getPageSize() ); 209 210 int nodePos = 0; 211 212 // Then iterate on the tuples, creating the needed pages 213 for ( InMemoryNode<K, V> node : nodes ) 214 { 215 if ( nodePos != 0 ) 216 { 217 K key = node.getLeftMostKey(); 218 BTreeFactory.setKey( btree, parentNode, nodePos - 1, key ); 219 } 220 221 PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, node ); 222 parentNode.setPageHolder( nodePos, pageHolder ); 223 nodePos++; 224 } 225 226 // And return the node 227 return parentNode; 228 } 229 230 231 /** 232 * Creates all the leaves using the provided tuples, and update the upper layer if needed 233 */ 234 private Page<K, V> addLeaves( BTree<K, V> btree, List<Tuple<K, V>> tuples, int maxElements ) 235 { 236 if ( tuples.size() == 0 ) 237 { 238 // No element to inject in the BTree 239 return null; 240 } 241 242 // The insertion position in the leaf 243 int leafPos = 0; 244 245 // Deal with special cases : 246 // First, everything will fit in a single page 247 if ( tuples.size() < btree.getPageSize() ) 248 { 249 // The leaf will be the rootPage 250 // creates a first leaf 251 InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0, 252 btreeConfiguration.getPageSize() ); 253 254 // Iterate on the tuples 255 for ( Tuple<K, V> tuple : tuples ) 256 { 257 injectTuple( btree, leaf, leafPos, tuple ); 258 leafPos++; 259 } 260 261 return leaf; 262 } 263 264 // Second, the data will fit into a 2 level tree 265 if ( tuples.size() < maxElements ) 266 { 267 // We will just create the necessary leaves and the upper node if needed 268 // We have enough tuples to fulfill the uper node. 269 // First, create the new node 270 InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0, 271 btreeConfiguration.getPageSize() ); 272 273 // creates a first leaf 274 InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0, 275 btreeConfiguration.getPageSize() ); 276 277 int nodePos = 0; 278 279 // Then iterate on the tuples, creating the needed pages 280 for ( Tuple<K, V> tuple : tuples ) 281 { 282 if ( leafPos == btree.getPageSize() ) 283 { 284 // The leaf is full, we need to attach it to its parent's node 285 // and to create a new leaf 286 BTreeFactory.setKey( btree, node, nodePos, tuple.getKey() ); 287 PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, leaf ); 288 node.setPageHolder( nodePos, pageHolder ); 289 nodePos++; 290 291 // When done, we need to create a new leaf 292 leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0, 293 btree.getPageSize() ); 294 295 // and inject the tuple in the leaf 296 injectTuple( btree, leaf, 0, tuple ); 297 leafPos = 1; 298 } 299 else 300 { 301 // Inject the tuple in the leaf 302 injectTuple( btree, leaf, leafPos, tuple ); 303 leafPos++; 304 } 305 } 306 307 // Last, not least, deal with the last created leaf, which has to be injected in its parent's node 308 if ( leafPos > 0 ) 309 { 310 PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, leaf ); 311 node.setPageHolder( nodePos, pageHolder ); 312 } 313 314 return node; 315 } 316 else 317 { 318 // We have enough tuples to fulfill the upper node. 319 // First, create the new node 320 InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0, 321 btreeConfiguration.getPageSize() ); 322 323 // creates a first leaf 324 InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0, 325 btreeConfiguration.getPageSize() ); 326 327 int nodePos = 0; 328 329 // Then iterate on the tuples, creating the needed pages 330 for ( Tuple<K, V> tuple : tuples ) 331 { 332 if ( leafPos == btree.getPageSize() ) 333 { 334 // The leaf is full, we need to attach it to its parent's node 335 // and to create a new node 336 BTreeFactory.setKey( btree, node, nodePos, tuple.getKey() ); 337 PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, leaf ); 338 node.setPageHolder( nodePos, pageHolder ); 339 nodePos++; 340 341 // When done, we need to create a new leaf 342 leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0, 343 btree.getPageSize() ); 344 345 // and inject the tuple in the leaf 346 injectTuple( btree, leaf, 0, tuple ); 347 leafPos = 1; 348 } 349 else 350 { 351 // Inject the tuple in the leaf 352 injectTuple( btree, leaf, leafPos, tuple ); 353 leafPos++; 354 } 355 } 356 357 // Last, not least, deal with the last created leaf, which has to be injected in its parent's node 358 if ( leafPos > 0 ) 359 { 360 PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, leaf ); 361 node.setPageHolder( nodePos, pageHolder ); 362 } 363 364 // And return the node 365 return node; 366 } 367 } 368 369 370 private void injectTuple( BTree<K, V> btree, InMemoryLeaf<K, V> leaf, int leafPos, Tuple<K, V> tuple ) 371 { 372 BTreeFactory.setKey( btree, leaf, leafPos, tuple.getKey() ); 373 ValueHolder<V> valueHolder = new InMemoryValueHolder<V>( btree, tuple.getValue() ); 374 BTreeFactory.setValue( btree, leaf, leafPos, valueHolder ); 375 } 376 377 378 private int add( BTree<K, V> btree, Page<K, V>[] pageStack, int level, Page<K, V> page, Tuple<K, V> tuple ) 379 { 380 if ( page == null ) 381 { 382 // No existing page at this level, create a new one 383 if ( level == 0 ) 384 { 385 // creates a leaf 386 InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0, 387 btreeConfiguration.getPageSize() ); 388 389 // Store the new leaf in the stack 390 pageStack[level] = leaf; 391 392 // Inject the tuple in the leaf 393 BTreeFactory.setKey( btree, leaf, 0, tuple.getKey() ); 394 ValueHolder<V> valueHolder = new InMemoryValueHolder<V>( btree, tuple.getValue() ); 395 BTreeFactory.setValue( btree, leaf, 0, valueHolder ); 396 } 397 else 398 { 399 // Create a node 400 InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0, 401 btreeConfiguration.getPageSize() ); 402 403 // Inject the tuple key in the node 404 BTreeFactory.setKey( btree, node, 0, tuple.getKey() ); 405 PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, pageStack[level - 1] ); 406 node.setPageHolder( 0, pageHolder ); 407 } 408 } 409 else 410 { 411 // Check first if the current page is full 412 if ( page.getNbElems() == btree.getPageSize() ) 413 { 414 // Ok, it's full. We need to create a new page and to propagate the 415 // added element to the upper level 416 //TODO 417 } 418 else 419 { 420 // We just have to inject the tuple in the current page 421 // be it a leaf or a node 422 if ( page.isLeaf() ) 423 { 424 // It's a leaf 425 BTreeFactory.setKey( btree, page, page.getNbElems(), tuple.getKey() ); 426 ValueHolder<V> valueHolder = new InMemoryValueHolder<V>( btree, tuple.getValue() ); 427 BTreeFactory.setValue( btree, page, page.getNbElems(), valueHolder ); 428 } 429 else 430 { 431 // It's a node 432 BTreeFactory.setKey( btree, page, page.getNbElems(), tuple.getKey() ); 433 PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, pageStack[level - 1] ); 434 ( ( InMemoryNode<K, V> ) page ).setPageHolder( page.getNbElems(), pageHolder ); 435 } 436 } 437 } 438 439 return level; 440 } 441 442 443 @SuppressWarnings("unchecked") 444 private Page<K, V> attachNodes( List<Page<K, V>> children, BTree<K, V> btree ) throws IOException 445 { 446 if ( children.size() == 1 ) 447 { 448 return children.get( 0 ); 449 } 450 451 List<Page<K, V>> lstNodes = new ArrayList<Page<K, V>>(); 452 453 int numChildren = btreeConfiguration.getPageSize() + 1; 454 455 InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0, 456 btreeConfiguration.getPageSize() ); 457 lstNodes.add( node ); 458 int i = 0; 459 int totalNodes = 0; 460 461 for ( Page<K, V> p : children ) 462 { 463 if ( i != 0 ) 464 { 465 BTreeFactory.setKey( btree, node, i - 1, p.getLeftMostKey() ); 466 } 467 468 node.setPageHolder( i, new PageHolder<K, V>( btree, p ) ); 469 470 i++; 471 totalNodes++; 472 473 if ( ( totalNodes % numChildren ) == 0 ) 474 { 475 i = 0; 476 node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0, btreeConfiguration.getPageSize() ); 477 lstNodes.add( node ); 478 } 479 } 480 481 // remove null keys and values from the last node and resize 482 AbstractPage<K, V> lastNode = ( AbstractPage<K, V> ) lstNodes.get( lstNodes.size() - 1 ); 483 484 for ( int j = 0; j < lastNode.getNbElems(); j++ ) 485 { 486 if ( lastNode.getKey( j ) == null ) 487 { 488 int n = j; 489 lastNode.setNbElems( n ); 490 KeyHolder<K>[] keys = lastNode.getKeys(); 491 492 lastNode.setKeys( ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n ) ); 493 System.arraycopy( keys, 0, lastNode.getKeys(), 0, n ); 494 495 break; 496 } 497 } 498 499 return attachNodes( lstNodes, btree ); 500 } 501}