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.Arrays; 028import java.util.Iterator; 029import java.util.List; 030 031import org.apache.directory.mavibot.btree.serializer.ElementSerializer; 032 033 034/** 035 * A B-tree builder that builds a tree from the bottom. 036 * 037 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 038 */ 039public class PersistedBTreeBuilder<K, V> 040{ 041 private String name; 042 043 private int numKeysInNode; 044 045 private ElementSerializer<K> keySerializer; 046 047 private ElementSerializer<V> valueSerializer; 048 049 private RecordManager rm; 050 051 052 public PersistedBTreeBuilder( RecordManager rm, String name, int numKeysInNode, ElementSerializer<K> keySerializer, 053 ElementSerializer<V> valueSerializer ) 054 { 055 this.rm = rm; 056 this.name = name; 057 this.numKeysInNode = numKeysInNode; 058 this.keySerializer = keySerializer; 059 this.valueSerializer = valueSerializer; 060 } 061 062 063 @SuppressWarnings("unchecked") 064 public BTree<K, V> build( Iterator<Tuple<K, V>> sortedTupleItr ) throws Exception 065 { 066 BTree<K, V> btree = BTreeFactory.createPersistedBTree( name, keySerializer, valueSerializer ); 067 068 rm.manage( btree ); 069 070 List<Page<K, V>> lstLeaves = new ArrayList<Page<K, V>>(); 071 072 int totalTupleCount = 0; 073 074 PersistedLeaf<K, V> leaf1 = ( PersistedLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0, numKeysInNode ); 075 lstLeaves.add( leaf1 ); 076 077 int leafIndex = 0; 078 079 while ( sortedTupleItr.hasNext() ) 080 { 081 Tuple<K, V> tuple = sortedTupleItr.next(); 082 083 BTreeFactory.setKey( btree, leaf1, leafIndex, tuple.getKey() ); 084 085 PersistedValueHolder<V> eh = new PersistedValueHolder<V>( btree, tuple.getValue() ); 086 087 BTreeFactory.setValue( btree, leaf1, leafIndex, eh ); 088 089 leafIndex++; 090 totalTupleCount++; 091 if ( ( totalTupleCount % numKeysInNode ) == 0 ) 092 { 093 leafIndex = 0; 094 095 PageHolder<K, V> pageHolder = rm.writePage( btree, leaf1, 1 ); 096 097 leaf1 = ( PersistedLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0, numKeysInNode ); 098 lstLeaves.add( leaf1 ); 099 } 100 101 //TODO build the whole tree in chunks rather than processing *all* leaves at first 102 } 103 104 if ( lstLeaves.isEmpty() ) 105 { 106 return btree; 107 } 108 109 // remove null keys and values from the last leaf and resize 110 PersistedLeaf<K, V> lastLeaf = ( PersistedLeaf<K, V> ) lstLeaves.get( lstLeaves.size() - 1 ); 111 for ( int i = 0; i < lastLeaf.getNbElems(); i++ ) 112 { 113 if ( lastLeaf.getKey( i ) == null ) 114 { 115 int n = i; 116 lastLeaf.setNbElems( n ); 117 KeyHolder<K>[] keys = lastLeaf.getKeys(); 118 119 lastLeaf.setKeys( ( KeyHolder[] ) Array.newInstance( PersistedKeyHolder.class, n ) ); 120 System.arraycopy( keys, 0, lastLeaf.getKeys(), 0, n ); 121 122 ValueHolder<V>[] values = lastLeaf.values; 123 lastLeaf.values = ( PersistedValueHolder<V>[] ) Array.newInstance( PersistedValueHolder.class, n ); 124 System.arraycopy( values, 0, lastLeaf.values, 0, n ); 125 126 PageHolder<K, V> pageHolder = rm.writePage( btree, lastLeaf, 1 ); 127 128 break; 129 } 130 } 131 132 // make sure either one of the root pages is reclaimed, cause when we call rm.manage() 133 // there is already a root page created 134 Page<K, V> rootPage = attachNodes( lstLeaves, btree ); 135 136 //System.out.println("built rootpage : " + rootPage); 137 ( ( PersistedBTree<K, V> ) btree ).setNbElems( totalTupleCount ); 138 139 rm.updateBtreeHeader( btree, ( ( AbstractPage<K, V> ) rootPage ).getOffset() ); 140 141 rm.freePages( btree, btree.getRootPage().getRevision(), Arrays.asList( btree.getRootPage() ) ); 142 143 ( ( AbstractBTree<K, V> ) btree ).setRootPage( rootPage ); 144 145 return btree; 146 } 147 148 149 @SuppressWarnings("unchecked") 150 private Page<K, V> attachNodes( List<Page<K, V>> children, BTree<K, V> btree ) throws IOException 151 { 152 if ( children.size() == 1 ) 153 { 154 return children.get( 0 ); 155 } 156 157 List<Page<K, V>> lstNodes = new ArrayList<Page<K, V>>(); 158 159 int numChildren = numKeysInNode + 1; 160 161 PersistedNode<K, V> node = ( PersistedNode<K, V> ) BTreeFactory.createNode( btree, 0, numKeysInNode ); 162 lstNodes.add( node ); 163 int i = 0; 164 int totalNodes = 0; 165 166 for ( Page<K, V> page : children ) 167 { 168 if ( i != 0 ) 169 { 170 BTreeFactory.setKey( btree, node, i - 1, page.getLeftMostKey() ); 171 } 172 173 BTreeFactory.setPage( btree, node, i, page ); 174 175 i++; 176 totalNodes++; 177 178 if ( ( totalNodes % numChildren ) == 0 ) 179 { 180 i = 0; 181 182 rm.writePage( btree, node, 1 ); 183 184 node = ( PersistedNode<K, V> ) BTreeFactory.createNode( btree, 0, numKeysInNode ); 185 lstNodes.add( node ); 186 } 187 } 188 189 // remove null keys and values from the last node and resize 190 AbstractPage<K, V> lastNode = ( AbstractPage<K, V> ) lstNodes.get( lstNodes.size() - 1 ); 191 192 for ( int j = 0; j < lastNode.getNbElems(); j++ ) 193 { 194 if ( lastNode.getKey( j ) == null ) 195 { 196 int n = j; 197 lastNode.setNbElems( n ); 198 KeyHolder<K>[] keys = lastNode.getKeys(); 199 200 lastNode.setKeys( ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n ) ); 201 System.arraycopy( keys, 0, lastNode.getKeys(), 0, n ); 202 203 rm.writePage( btree, lastNode, 1 ); 204 205 break; 206 } 207 } 208 209 return attachNodes( lstNodes, btree ); 210 } 211}