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