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