1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 package org.apache.directory.mavibot.btree;
22
23
24 import java.io.IOException;
25 import java.lang.reflect.Array;
26 import java.util.ArrayList;
27 import java.util.Iterator;
28 import java.util.List;
29
30 import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
31
32
33
34
35
36
37
38 public class InMemoryBTreeBuilder<K, V>
39 {
40
41 private InMemoryBTreeConfiguration<K, V> btreeConfiguration;
42
43
44
45
46
47
48
49
50
51
52 public InMemoryBTreeBuilder( String name, int numKeysInNode, ElementSerializer<K> keySerializer,
53 ElementSerializer<V> valueSerializer )
54 {
55 btreeConfiguration = new InMemoryBTreeConfiguration<K, V>();
56 btreeConfiguration.setName( name );
57 btreeConfiguration.setPageSize( numKeysInNode );
58 btreeConfiguration.setKeySerializer( keySerializer );
59 btreeConfiguration.setValueSerializer( valueSerializer );
60 }
61
62
63
64
65
66
67
68 public InMemoryBTreeBuilder( InMemoryBTreeConfiguration<K, V> btreeConfiguration )
69 {
70 this.btreeConfiguration = btreeConfiguration;
71 }
72
73
74 @SuppressWarnings("unchecked")
75 public BTree<K, V> build( Iterator<Tuple<K, V>> sortedTupleItr ) throws IOException
76 {
77 BTree<K, V> btree = BTreeFactory.createInMemoryBTree( btreeConfiguration );
78 int pageSize = btree.getPageSize();
79 int maxElements = ( pageSize + 1 ) * pageSize;
80
81
82
83 List<InMemoryNode<K, V>>[] pageStack = new ArrayList[15];
84
85 for ( int i = 0; i < 15; i++ )
86 {
87 pageStack[i] = new ArrayList<InMemoryNode<K, V>>( maxElements );
88 }
89
90
91 int nbAdded = 0;
92
93
94 int btreeHeight = 0;
95
96
97
98 List<Tuple<K, V>> tuples = new ArrayList<Tuple<K, V>>( maxElements );
99
100
101 List<InMemoryNode<K, V>> nodes = new ArrayList<InMemoryNode<K, V>>();
102
103
104 while ( sortedTupleItr.hasNext() )
105 {
106 nbAdded++;
107
108
109 Tuple<K, V> tuple = sortedTupleItr.next();
110 tuples.add( tuple );
111
112 if ( tuples.size() == maxElements )
113 {
114
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
125
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
141 if ( btreeHeight < level )
142 {
143 btreeHeight = level;
144 }
145 }
146
147 tuples.clear();
148 }
149 }
150
151 if ( tuples.size() > 0 )
152 {
153
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
161
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
174 if ( pageStack[0].size() != 0 )
175 {
176
177
178 if ( leaf.getNbElems() < btree.getPageSize() / 2 )
179 {
180
181 }
182 else
183 {
184
185
186 }
187 }
188 }
189 }
190
191
192 ( ( AbstractBTree<K, V> ) btree ).getBtreeHeader().setNbElems( nbAdded );
193
194 return btree;
195 }
196
197
198
199
200
201 private InMemoryNode<K, V> createParentNode( BTree<K, V> btree, List<InMemoryNode<K, V>> nodes, int maxElements )
202 {
203
204
205 InMemoryNode<K, V> parentNode = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0,
206 btreeConfiguration.getPageSize() );
207
208 int nodePos = 0;
209
210
211 for ( InMemoryNode<K, V> node : nodes )
212 {
213 if ( nodePos == 0 )
214 {
215 PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, node );
216 parentNode.setPageHolder( nodePos, pageHolder );
217 }
218 else if ( nodePos == btree.getPageSize() )
219 {
220 K key = node.getLeftMostKey();
221 BTreeFactory.setKey( btree, parentNode, nodePos - 1, key );
222 PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, node );
223 parentNode.setPageHolder( nodePos, pageHolder );
224 }
225 else
226 {
227 K key = node.getLeftMostKey();
228 BTreeFactory.setKey( btree, parentNode, nodePos - 1, key );
229 PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, node );
230 parentNode.setPageHolder( nodePos, pageHolder );
231 }
232
233 nodePos++;
234 }
235
236
237 return parentNode;
238 }
239
240
241
242
243
244 private Page<K, V> addLeaves( BTree<K, V> btree, List<Tuple<K, V>> tuples, int maxElements )
245 {
246 if ( tuples.size() == 0 )
247 {
248
249 return null;
250 }
251
252
253 int leafPos = 0;
254
255
256
257 if ( tuples.size() < btree.getPageSize() )
258 {
259
260
261 InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0,
262 btreeConfiguration.getPageSize() );
263
264
265 for ( Tuple<K, V> tuple : tuples )
266 {
267 injectTuple( btree, leaf, leafPos, tuple );
268 leafPos++;
269 }
270
271 return leaf;
272 }
273
274
275 if ( tuples.size() < maxElements )
276 {
277
278
279
280 InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0,
281 btreeConfiguration.getPageSize() );
282
283
284 InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0,
285 btreeConfiguration.getPageSize() );
286
287 int nodePos = 0;
288
289
290 for ( Tuple<K, V> tuple : tuples )
291 {
292 if ( leafPos == btree.getPageSize() )
293 {
294
295
296 BTreeFactory.setKey( btree, node, nodePos, tuple.getKey() );
297 PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, leaf );
298 node.setPageHolder( nodePos, pageHolder );
299 nodePos++;
300
301
302 leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0,
303 btree.getPageSize() );
304
305
306 injectTuple( btree, leaf, 0, tuple );
307 leafPos = 1;
308 }
309 else
310 {
311
312 injectTuple( btree, leaf, leafPos, tuple );
313 leafPos++;
314 }
315 }
316
317
318 if ( leafPos > 0 )
319 {
320 PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, leaf );
321 node.setPageHolder( nodePos, pageHolder );
322 }
323
324 return node;
325 }
326 else
327 {
328
329
330 InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0,
331 btreeConfiguration.getPageSize() );
332
333
334 InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0,
335 btreeConfiguration.getPageSize() );
336
337 int nodePos = 0;
338
339
340 for ( Tuple<K, V> tuple : tuples )
341 {
342 if ( leafPos == btree.getPageSize() )
343 {
344
345
346 BTreeFactory.setKey( btree, node, nodePos, tuple.getKey() );
347 PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, leaf );
348 node.setPageHolder( nodePos, pageHolder );
349 nodePos++;
350
351
352 leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0,
353 btree.getPageSize() );
354
355
356 injectTuple( btree, leaf, 0, tuple );
357 leafPos = 1;
358 }
359 else
360 {
361
362 injectTuple( btree, leaf, leafPos, tuple );
363 leafPos++;
364 }
365 }
366
367
368 if ( leafPos > 0 )
369 {
370 PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, leaf );
371 node.setPageHolder( nodePos, pageHolder );
372 }
373
374
375 return node;
376 }
377 }
378
379
380 private void injectTuple( BTree<K, V> btree, InMemoryLeaf<K, V> leaf, int leafPos, Tuple<K, V> tuple )
381 {
382 BTreeFactory.setKey( btree, leaf, leafPos, tuple.getKey() );
383 ValueHolder<V> valueHolder = new InMemoryValueHolder<V>( btree, tuple.getValue() );
384 BTreeFactory.setValue( btree, leaf, leafPos, valueHolder );
385 }
386
387
388 private int add( BTree<K, V> btree, Page<K, V>[] pageStack, int level, Page<K, V> page, Tuple<K, V> tuple )
389 {
390 if ( page == null )
391 {
392
393 if ( level == 0 )
394 {
395
396 InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0,
397 btreeConfiguration.getPageSize() );
398
399
400 pageStack[level] = leaf;
401
402
403 BTreeFactory.setKey( btree, leaf, 0, tuple.getKey() );
404 ValueHolder<V> valueHolder = new InMemoryValueHolder<V>( btree, tuple.getValue() );
405 BTreeFactory.setValue( btree, leaf, 0, valueHolder );
406 }
407 else
408 {
409
410 InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0,
411 btreeConfiguration.getPageSize() );
412
413
414 BTreeFactory.setKey( btree, node, 0, tuple.getKey() );
415 PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, pageStack[level - 1] );
416 node.setPageHolder( 0, pageHolder );
417 }
418 }
419 else
420 {
421
422 if ( page.getNbElems() == btree.getPageSize() )
423 {
424
425
426 }
427 else
428 {
429
430
431 if ( page.isLeaf() )
432 {
433
434 BTreeFactory.setKey( btree, page, page.getNbElems(), tuple.getKey() );
435 ValueHolder<V> valueHolder = new InMemoryValueHolder<V>( btree, tuple.getValue() );
436 BTreeFactory.setValue( btree, page, page.getNbElems(), valueHolder );
437 }
438 else
439 {
440
441 BTreeFactory.setKey( btree, page, page.getNbElems(), tuple.getKey() );
442 PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, pageStack[level - 1] );
443 ( ( InMemoryNode<K, V> ) page ).setPageHolder( page.getNbElems(), pageHolder );
444 }
445 }
446 }
447
448 return level;
449 }
450
451
452 @SuppressWarnings("unchecked")
453 private Page<K, V> attachNodes( List<Page<K, V>> children, BTree<K, V> btree ) throws IOException
454 {
455 if ( children.size() == 1 )
456 {
457 return children.get( 0 );
458 }
459
460 List<Page<K, V>> lstNodes = new ArrayList<Page<K, V>>();
461
462 int numChildren = btreeConfiguration.getPageSize() + 1;
463
464 InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0,
465 btreeConfiguration.getPageSize() );
466 lstNodes.add( node );
467 int i = 0;
468 int totalNodes = 0;
469
470 for ( Page<K, V> p : children )
471 {
472 if ( i != 0 )
473 {
474 BTreeFactory.setKey( btree, node, i - 1, p.getLeftMostKey() );
475 }
476
477 node.setPageHolder( i, new PageHolder<K, V>( btree, p ) );
478
479 i++;
480 totalNodes++;
481
482 if ( ( totalNodes % numChildren ) == 0 )
483 {
484 i = 0;
485 node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0, btreeConfiguration.getPageSize() );
486 lstNodes.add( node );
487 }
488 }
489
490
491 AbstractPage<K, V> lastNode = ( AbstractPage<K, V> ) lstNodes.get( lstNodes.size() - 1 );
492
493 for ( int j = 0; j < lastNode.getNbElems(); j++ )
494 {
495 if ( lastNode.getKey( j ) == null )
496 {
497 int n = j;
498 lastNode.setNbElems( n );
499 KeyHolder<K>[] keys = lastNode.getKeys();
500
501 lastNode.setKeys( ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n ) );
502 System.arraycopy( keys, 0, lastNode.getKeys(), 0, n );
503
504 break;
505 }
506 }
507
508 return attachNodes( lstNodes, btree );
509 }
510 }