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.memory;
22
23
24 import static org.apache.directory.mavibot.btree.memory.BTreeFactory.createLeaf;
25 import static org.apache.directory.mavibot.btree.memory.BTreeFactory.createNode;
26 import static org.apache.directory.mavibot.btree.memory.BTreeFactory.setKey;
27 import static org.apache.directory.mavibot.btree.memory.BTreeFactory.setValue;
28
29 import java.io.IOException;
30 import java.lang.reflect.Array;
31 import java.util.ArrayList;
32 import java.util.Iterator;
33 import java.util.List;
34
35 import org.apache.directory.mavibot.btree.Tuple;
36 import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
37
38
39
40
41
42
43
44 public class BTreeBuilder<K, V>
45 {
46 private String name;
47
48 private int numKeysInNode;
49
50 private ElementSerializer<K> keySerializer;
51
52 private ElementSerializer<V> valueSerializer;
53
54
55 public BTreeBuilder( String name, int numKeysInNode, ElementSerializer<K> keySerializer,
56 ElementSerializer<V> valueSerializer )
57 {
58 this.name = name;
59 this.numKeysInNode = numKeysInNode;
60 this.keySerializer = keySerializer;
61 this.valueSerializer = valueSerializer;
62 }
63
64
65 @SuppressWarnings("unchecked")
66 public BTree<K, V> build( Iterator<Tuple<K, V>> sortedTupleItr ) throws IOException
67 {
68 BTree<K, V> btree = new BTree<K, V>( name, keySerializer, valueSerializer );
69 btree.init();
70
71 List<Page<K, V>> lstLeaves = new ArrayList<Page<K, V>>();
72
73 int totalTupleCount = 0;
74
75 Leaf<K, V> leaf1 = createLeaf( btree, 0, numKeysInNode );
76 lstLeaves.add( leaf1 );
77
78 int leafIndex = 0;
79 while ( sortedTupleItr.hasNext() )
80 {
81 Tuple<K, V> tuple = sortedTupleItr.next();
82
83 setKey( leaf1, leafIndex, tuple.getKey() );
84
85 MemoryHolder<K, V> eh = new MemoryHolder<K, V>( btree, tuple.getValue() );
86
87 setValue( leaf1, leafIndex, eh );
88
89 leafIndex++;
90 totalTupleCount++;
91 if ( ( totalTupleCount % numKeysInNode ) == 0 )
92 {
93 leafIndex = 0;
94 leaf1 = createLeaf( btree, 0, numKeysInNode );
95 lstLeaves.add( leaf1 );
96 }
97 }
98
99 if ( lstLeaves.isEmpty() )
100 {
101 return btree;
102 }
103
104
105 Leaf<K, V> lastLeaf = ( Leaf<K, V> ) lstLeaves.get( lstLeaves.size() - 1 );
106 for ( int i = 0; i < lastLeaf.nbElems; i++ )
107 {
108 if ( lastLeaf.keys[i] == null )
109 {
110 int n = i;
111 lastLeaf.nbElems = n;
112 K[] keys = lastLeaf.keys;
113
114 Class<?> keyType = btree.getKeyType();
115 lastLeaf.keys = ( K[] ) Array.newInstance( keyType, n );
116 System.arraycopy( keys, 0, lastLeaf.keys, 0, n );
117
118 ElementHolder<V, K, V>[] values = lastLeaf.values;
119 lastLeaf.values = ( MemoryHolder<K, V>[] ) Array.newInstance( MemoryHolder.class, n );
120 System.arraycopy( values, 0, lastLeaf.values, 0, n );
121
122 break;
123 }
124 }
125
126 Page<K, V> rootPage = attachNodes( lstLeaves, btree );
127
128 btree.rootPage = rootPage;
129
130 return btree;
131 }
132
133
134 @SuppressWarnings("unchecked")
135 private Page<K, V> attachNodes( List<Page<K, V>> children, BTree<K, V> btree ) throws IOException
136 {
137 if ( children.size() == 1 )
138 {
139 return children.get( 0 );
140 }
141
142 List<Page<K, V>> lstNodes = new ArrayList<Page<K, V>>();
143
144 int numChildren = numKeysInNode + 1;
145
146 Node<K, V> node = createNode( btree, 0, numKeysInNode );
147 lstNodes.add( node );
148 int i = 0;
149 int totalNodes = 0;
150
151 for ( Page<K, V> p : children )
152 {
153 if ( i != 0 )
154 {
155 setKey( node, i - 1, p.getLeftMostKey() );
156 }
157
158 node.children[i] = btree.createPageHolder( p );
159
160 i++;
161 totalNodes++;
162
163 if ( ( totalNodes % numChildren ) == 0 )
164 {
165 i = 0;
166 node = createNode( btree, 0, numKeysInNode );
167 lstNodes.add( node );
168 }
169 }
170
171
172 AbstractPage<K, V> lastNode = ( AbstractPage<K, V> ) lstNodes.get( lstNodes.size() - 1 );
173
174 for ( int j = 0; j < lastNode.nbElems; j++ )
175 {
176 if ( lastNode.keys[j] == null )
177 {
178 int n = j;
179 lastNode.nbElems = n;
180 K[] keys = lastNode.keys;
181
182 Class<?> keyType = btree.getKeyType();
183 lastNode.keys = ( K[] ) Array.newInstance( keyType, n );
184 System.arraycopy( keys, 0, lastNode.keys, 0, n );
185
186 break;
187 }
188 }
189
190 return attachNodes( lstNodes, btree );
191 }
192 }