| /** |
| * JDBM LICENSE v1.00 |
| * |
| * Redistribution and use of this software and associated documentation |
| * ("Software"), with or without modification, are permitted provided |
| * that the following conditions are met: |
| * |
| * 1. Redistributions of source code must retain copyright |
| * statements and notices. Redistributions must also contain a |
| * copy of this document. |
| * |
| * 2. Redistributions in binary form must reproduce the |
| * above copyright notice, this list of conditions and the |
| * following disclaimer in the documentation and/or other |
| * materials provided with the distribution. |
| * |
| * 3. The name "JDBM" must not be used to endorse or promote |
| * products derived from this Software without prior written |
| * permission of Cees de Groot. For written permission, |
| * please contact cg@cdegroot.com. |
| * |
| * 4. Products derived from this Software may not be called "JDBM" |
| * nor may "JDBM" appear in their names without prior written |
| * permission of Cees de Groot. |
| * |
| * 5. Due credit should be given to the JDBM Project |
| * (http://jdbm.sourceforge.net/). |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE JDBM PROJECT AND CONTRIBUTORS |
| * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT |
| * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND |
| * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL |
| * CEES DE GROOT OR ANY CONTRIBUTORS BE LIABLE FOR ANY DIRECT, |
| * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
| * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR |
| * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
| * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
| * OF THE POSSIBILITY OF SUCH DAMAGE. |
| * |
| * Copyright 2001 (C) Alex Boisvert. All Rights Reserved. |
| * Contributions are Copyright (C) 2001 by their associated contributors. |
| * |
| */ |
| |
| package jdbm.btree; |
| |
| |
| import java.io.Externalizable; |
| import java.io.IOException; |
| import java.io.ObjectInput; |
| import java.io.ObjectOutput; |
| import java.io.Serializable; |
| import java.io.ByteArrayInputStream; |
| import java.io.ByteArrayOutputStream; |
| import java.io.ObjectInputStream; |
| import java.io.ObjectOutputStream; |
| import java.util.Comparator; |
| import java.util.concurrent.atomic.AtomicInteger; |
| |
| import jdbm.RecordManager; |
| import jdbm.ActionRecordManager; |
| import jdbm.helper.Serializer; |
| import jdbm.helper.Tuple; |
| import jdbm.helper.TupleBrowser; |
| import jdbm.helper.WrappedRuntimeException; |
| import jdbm.helper.ActionContext; |
| |
| import java.util.concurrent.locks.Lock; |
| import java.util.concurrent.locks.ReentrantLock; |
| |
| import org.apache.directory.server.i18n.I18n; |
| |
| |
| /** |
| * B+Tree persistent indexing data structure. B+Trees are optimized for |
| * block-based, random I/O storage because they store multiple keys on |
| * one tree node (called <code>BPage</code>). In addition, the leaf nodes |
| * directly contain (inline) the values associated with the keys, allowing a |
| * single (or sequential) disk read of all the values on the page. |
| * <p> |
| * B+Trees are n-airy, yeilding log(N) search cost. They are self-balancing, |
| * preventing search performance degradation when the size of the tree grows. |
| * <p> |
| * Keys and associated values must be <code>Serializable</code> objects. The |
| * user is responsible to supply a serializable <code>Comparator</code> object |
| * to be used for the ordering of entries, which are also called <code>Tuple</code>. |
| * The B+Tree allows traversing the keys in forward and reverse order using a |
| * <p> |
| * This implementation does not directly support duplicate keys, but it is |
| * possible to handle duplicates by inlining or referencing an object collection |
| * as a value. |
| * <p> |
| * There is no limit on key size or value size, but it is recommended to keep |
| * both as small as possible to reduce disk I/O. This is especially true for |
| * the key size, which impacts all non-leaf <code>BPage</code> objects. |
| * |
| * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a> |
| */ |
| public class BTree<K, V> implements Externalizable |
| { |
| private static final boolean DEBUG = false; |
| |
| /** Version id for serialization. */ |
| final static long serialVersionUID = 1L; |
| |
| /** Default page size (number of entries per node) */ |
| public static final int DEFAULT_SIZE = 16; |
| |
| /** Page manager used to persist changes in BPages */ |
| protected transient RecordManager recordManager; |
| |
| /** This BTree's record ID in the PageManager. */ |
| private transient long recordId; |
| |
| /** Comparator used to index entries. */ |
| Comparator<K> comparator; |
| |
| /** Serializer used to serialize index keys (optional) */ |
| protected Serializer keySerializer; |
| |
| /** Serializer used to serialize index values (optional) */ |
| protected Serializer valueSerializer; |
| |
| /** |
| * Height of the B+Tree. This is the number of BPages you have to traverse |
| * to get to a leaf BPage, starting from the root. |
| */ |
| int bTreeHeight; |
| |
| /** Record id of the root BPage */ |
| private transient long rootId; |
| |
| /** Number of entries in each BPage. */ |
| protected int pageSize; |
| |
| /** Total number of entries in the BTree */ |
| protected AtomicInteger nbEntries; |
| |
| /** Serializer used for BPages of this tree */ |
| private transient BPage<K, V> bpageSerializer; |
| |
| /** TRUE if underlying record manager is snapshot capable */ |
| private transient boolean isActionCapable; |
| |
| |
| /** Big lock snychronizing all actions */ |
| private transient Lock bigLock = new ReentrantLock(); |
| |
| /** Meta root used to access versions of Btree root */ |
| private transient MetaRoot metaRoot = new MetaRoot(); |
| |
| /** |
| * No-argument constructor used by serialization. |
| */ |
| public BTree() |
| { |
| // empty |
| } |
| |
| |
| /** |
| * Create a new persistent BTree, with 16 entries per node. |
| * |
| * @param recman Record manager used for persistence. |
| * @param comparator Comparator used to order index entries |
| */ |
| public BTree( RecordManager recman, Comparator<K> comparator ) throws IOException |
| { |
| createInstance( recman, comparator, null, null, DEFAULT_SIZE ); |
| } |
| |
| |
| /** |
| * Create a new persistent BTree, with 16 entries per node. |
| * |
| * @param recman Record manager used for persistence. |
| * @param keySerializer Serializer used to serialize index keys (optional) |
| * @param valueSerializer Serializer used to serialize index values (optional) |
| * @param comparator Comparator used to order index entries |
| */ |
| public BTree( RecordManager recman, Comparator<K> comparator, Serializer keySerializer, |
| Serializer valueSerializer ) throws IOException |
| { |
| createInstance( recman, comparator, keySerializer, valueSerializer, DEFAULT_SIZE ); |
| } |
| |
| |
| /** |
| * Create a new persistent BTree with the given number of entries per node. |
| * |
| * @param recman Record manager used for persistence. |
| * @param comparator Comparator used to order index entries |
| * @param keySerializer Serializer used to serialize index keys (optional) |
| * @param valueSerializer Serializer used to serialize index values (optional) |
| * @param pageSize Number of entries per page (must be even). |
| */ |
| public BTree( RecordManager recman, Comparator<K> comparator, Serializer keySerializer, |
| Serializer valueSerializer, int pageSize ) throws IOException |
| { |
| createInstance( recman, comparator, keySerializer, valueSerializer, pageSize ); |
| } |
| |
| |
| /** |
| * The real BTree constructor. |
| */ |
| private void createInstance(RecordManager recordManager, Comparator<K> comparator, Serializer keySerializer, |
| Serializer valueSerializer, int pageSize) throws IOException |
| { |
| if ( recordManager == null ) |
| { |
| throw new IllegalArgumentException( I18n.err( I18n.ERR_517 ) ); |
| } |
| |
| if ( comparator == null ) |
| { |
| throw new IllegalArgumentException( I18n.err( I18n.ERR_518 ) ); |
| } |
| |
| if ( !( comparator instanceof Serializable ) ) |
| { |
| throw new IllegalArgumentException( I18n.err( I18n.ERR_519 ) ); |
| } |
| |
| // make sure there's an even number of entries per BPage |
| if ( ( pageSize & 1 ) != 0 ) |
| { |
| throw new IllegalArgumentException( I18n.err( I18n.ERR_522 ) ); |
| } |
| |
| this.recordManager = recordManager; |
| this.comparator = comparator; |
| this.keySerializer = keySerializer; |
| this.valueSerializer = valueSerializer; |
| this.pageSize = pageSize; |
| this.bpageSerializer = new BPage<K, V>(); |
| this.bpageSerializer.btree = this; |
| this.nbEntries = new AtomicInteger( 0 ); |
| |
| this.isActionCapable = recordManager instanceof ActionRecordManager; |
| |
| boolean abortedAction = false; |
| ActionContext context = this.beginAction( false, "createInstance" ); |
| try |
| { |
| this.recordId = recordManager.insert( this ); |
| updateMetaRoot( this.rootId, this.bTreeHeight ); |
| } |
| catch ( IOException e ) |
| { |
| abortedAction = true; |
| this.abortAction( context ); |
| throw e; |
| } |
| finally |
| { |
| if ( !abortedAction ) |
| this.endAction( context ); |
| } |
| } |
| |
| |
| public void setPageSize( int pageSize ) |
| { |
| if ( ( pageSize & 0x0001 ) != 0 ) |
| { |
| this.pageSize = DEFAULT_SIZE; |
| } |
| else |
| { |
| this.pageSize = pageSize; |
| } |
| } |
| |
| |
| /** |
| * Load a persistent BTree. |
| * |
| * @param recman RecordManager used to store the persistent btree |
| * @param recid Record id of the BTree |
| */ |
| public BTree<K, V> load( RecordManager recman, long recid ) throws IOException |
| { |
| BTree<K, V> btree = null; |
| boolean abortedAction = false; |
| ActionContext context = this.beginAction( false, "load" ); |
| try |
| { |
| btree = (BTree<K, V>) recman.fetch( recid ); |
| btree.recordId = recid; |
| btree.recordManager = recman; |
| btree.bpageSerializer = new BPage<K, V>(); |
| btree.bpageSerializer.btree = btree; |
| btree.updateMetaRoot( btree.rootId, btree.bTreeHeight ); |
| |
| } |
| catch ( IOException e ) |
| { |
| abortedAction = true; |
| this.abortAction( context ); |
| throw e; |
| } |
| finally |
| { |
| if ( !abortedAction ) |
| this.endAction( context ); |
| } |
| |
| |
| return btree; |
| } |
| |
| |
| /** |
| * Insert an entry in the BTree. |
| * <p> |
| * The BTree cannot store duplicate entries. An existing entry can be |
| * replaced using the <code>replace</code> flag. If an entry with the |
| * same key already exists in the BTree, its value is returned. |
| * |
| * @param key Insert key |
| * @param value Insert value |
| * @param replace Set to true to replace an existing key-value pair. |
| * @return Existing value, if any. |
| */ |
| public Object insert( K key, V value, boolean replace ) throws IOException |
| { |
| if ( key == null ) |
| { |
| throw new IllegalArgumentException( I18n.err( I18n.ERR_523 ) ); |
| } |
| |
| if ( value == null ) |
| { |
| throw new IllegalArgumentException( I18n.err( I18n.ERR_524 ) ); |
| } |
| |
| |
| boolean abortedAction = false; |
| ActionContext context = this.beginAction( false, "insert" ); |
| |
| |
| if ( !isActionCapable ) |
| bigLock.lock(); |
| |
| try |
| { |
| BPage<K, V> rootPage = getRoot(); |
| |
| if ( rootPage == null ) |
| { |
| // BTree is currently empty, create a new root BPage |
| if ( DEBUG ) |
| { |
| System.out.println( "BTree.insert() new root BPage" ); |
| } |
| |
| rootPage = new BPage<K, V>( this, key, value ); |
| rootId = rootPage.getRecordId(); |
| bTreeHeight = 1; |
| nbEntries.set( 1 ); |
| recordManager.update( recordId, this ); |
| updateMetaRoot( this.rootId, this.bTreeHeight ); |
| return null; |
| } |
| else |
| { |
| BPage.InsertResult<K, V> insert = rootPage.insert( bTreeHeight, key, value, replace ); |
| if ( insert.pageNewCopy != null ) |
| rootPage = insert.pageNewCopy; |
| |
| boolean dirty = false; |
| |
| if ( insert.overflow != null ) |
| { |
| // current root page overflowed, we replace with a new root page |
| if ( DEBUG ) |
| { |
| System.out.println( "BTree.insert() replace root BPage due to overflow" ); |
| } |
| |
| rootPage = new BPage<K, V>( this, rootPage, insert.overflow ); |
| rootId = rootPage.getRecordId(); |
| bTreeHeight += 1; |
| dirty = true; |
| updateMetaRoot( this.rootId, this.bTreeHeight ); |
| } |
| |
| if ( insert.existing == null ) |
| { |
| nbEntries.getAndIncrement(); |
| dirty = true; |
| } |
| |
| if ( dirty ) |
| { |
| recordManager.update( recordId, this ); |
| } |
| |
| // insert might have returned an existing value |
| return insert.existing; |
| } |
| } |
| catch ( IOException e ) |
| { |
| abortedAction = true; |
| this.abortAction( context ); |
| throw e; |
| } |
| finally |
| { |
| if ( !abortedAction ) |
| this.endAction( context ); |
| |
| if ( !isActionCapable ) |
| bigLock.unlock(); |
| } |
| |
| } |
| |
| |
| |
| /** |
| * Remove an entry with the given key from the BTree. |
| * |
| * @param key Removal key |
| * @return Value associated with the key, or null if no entry with given |
| * key existed in the BTree. |
| */ |
| public V remove( K key ) throws IOException |
| { |
| if ( key == null ) |
| { |
| throw new IllegalArgumentException( I18n.err( I18n.ERR_523 ) ); |
| } |
| |
| |
| boolean abortedAction = false; |
| ActionContext context = this.beginAction( false, "remove" ); |
| |
| if ( !isActionCapable ) |
| bigLock.lock(); |
| |
| try |
| { |
| |
| BPage<K, V> rootPage = getRoot(); |
| |
| if ( rootPage == null ) |
| { |
| return null; |
| } |
| |
| boolean dirty = false; |
| BPage.RemoveResult<K, V> remove = rootPage.remove( bTreeHeight, key ); |
| if ( remove.pageNewCopy != null ) |
| rootPage = remove.pageNewCopy; |
| |
| if ( remove.underflow && rootPage.isEmpty() ) |
| { |
| bTreeHeight -= 1; |
| dirty = true; |
| |
| recordManager.delete( rootId ); |
| |
| if ( bTreeHeight == 0 ) |
| { |
| rootId = 0; |
| } |
| else |
| { |
| rootId = rootPage.childBPage( pageSize - 1 ).getRecordId(); |
| } |
| updateMetaRoot( this.rootId, this.bTreeHeight ); |
| } |
| |
| if ( remove.value != null ) |
| { |
| nbEntries.getAndDecrement(); |
| dirty = true; |
| } |
| |
| if ( dirty ) |
| { |
| recordManager.update( recordId, this ); |
| } |
| |
| return remove.value; |
| } |
| catch ( IOException e ) |
| { |
| abortedAction = true; |
| this.abortAction( context ); |
| throw e; |
| } |
| finally |
| { |
| if ( !abortedAction ) |
| this.endAction( context ); |
| |
| if ( !isActionCapable ) |
| bigLock.unlock(); |
| } |
| |
| } |
| |
| |
| /** |
| * Find the value associated with the given key. |
| * |
| * @param key Lookup key. |
| * @return Value associated with the key, or null if not found. |
| */ |
| public V find( K key ) throws IOException |
| { |
| TupleBrowser<K, V> browser = null; |
| Tuple<K, V> tuple = null; |
| |
| if ( key == null ) |
| { |
| throw new IllegalArgumentException( I18n.err( I18n.ERR_523 ) ); |
| } |
| |
| if ( !isActionCapable ) |
| bigLock.lock(); |
| |
| try |
| { |
| tuple = new Tuple<K, V>( null, null ); |
| |
| browser = browse( key ); |
| |
| if ( browser.getNext( tuple ) ) |
| { |
| // find returns the matching key or the next ordered key, so we must |
| // check if we have an exact match |
| if ( comparator.compare( key, tuple.getKey() ) != 0 ) |
| { |
| return null; |
| } |
| else |
| { |
| return this.copyValue( tuple.getValue() ); |
| } |
| } |
| else |
| { |
| return null; |
| } |
| } |
| finally |
| { |
| if ( browser != null ) |
| browser.close(); |
| |
| if ( !isActionCapable ) |
| bigLock.unlock(); |
| } |
| |
| } |
| |
| |
| /** |
| * Find the value associated with the given key, or the entry immediately |
| * following this key in the ordered BTree. |
| * |
| * @param key Lookup key. |
| * @return Value associated with the key, or a greater entry, or null if no |
| * greater entry was found. |
| */ |
| public Tuple<K, V> findGreaterOrEqual( K key ) throws IOException |
| { |
| Tuple<K, V> tuple; |
| TupleBrowser<K, V> browser = null; |
| |
| if ( key == null ) |
| { |
| // there can't be a key greater than or equal to "null" |
| // because null is considered an infinite key. |
| return null; |
| } |
| |
| if ( !isActionCapable ) |
| bigLock.lock(); |
| |
| tuple = new Tuple<K, V>( null, null ); |
| try |
| { |
| browser = browse( key ); |
| |
| if ( browser.getNext( tuple ) ) |
| { |
| tuple.setValue( this.copyValue( tuple.getValue() ) ); |
| return tuple; |
| } |
| else |
| { |
| return null; |
| } |
| } |
| finally |
| { |
| if ( browser != null ) |
| browser.close(); |
| |
| if ( !isActionCapable ) |
| bigLock.unlock(); |
| |
| } |
| } |
| |
| |
| /** |
| * Get a browser initially positioned at the beginning of the BTree. |
| * <p><b> |
| * WARNING: If you make structural modifications to the BTree during |
| * browsing, you will get inconsistent browing results. |
| * </b> |
| * |
| * @return Browser positionned at the beginning of the BTree. |
| */ |
| public TupleBrowser<K, V> browse() throws IOException |
| { |
| TupleBrowser<K, V> browser = null; |
| ActionContext context = this.beginAction( true, "browse" ); |
| try |
| { |
| MetaRoot meta = this.getMetaRoot(); |
| BPage<K, V> rootPage = this.getRoot( meta ); |
| |
| if ( rootPage == null ) |
| { |
| this.endAction( context ); |
| return new EmptyBrowser(){}; |
| } |
| browser = rootPage.findFirst( context ); |
| } |
| catch( IOException e ) |
| { |
| this.abortAction( context ); |
| throw e; |
| } |
| |
| this.unsetAsCurrentAction( context ); |
| return browser; |
| } |
| |
| |
| /** |
| * Get a browser initially positioned just before the given key. |
| * <p><b> |
| * WARNING: If you make structural modifications to the BTree during |
| * browsing, you will get inconsistent browsing results. |
| * </b> |
| * |
| * @param key Key used to position the browser. If null, the browser |
| * will be positioned after the last entry of the BTree. |
| * (Null is considered to be an "infinite" key) |
| * @return Browser positioned just before the given key. |
| */ |
| public TupleBrowser<K, V> browse( K key ) throws IOException |
| { |
| TupleBrowser<K, V> browser = null; |
| ActionContext context = this.beginAction( true, "browse key" ); |
| try |
| { |
| MetaRoot meta = this.getMetaRoot(); |
| BPage<K, V> rootPage = this.getRoot( meta ); |
| |
| if ( rootPage == null ) |
| { |
| this.endAction( context ); |
| return new EmptyBrowser(){}; |
| } |
| |
| browser = rootPage.find( meta.treeHeight, key, context ); |
| } |
| catch( IOException e ) |
| { |
| this.abortAction( context ); |
| throw e; |
| } |
| |
| this.unsetAsCurrentAction( context ); |
| return browser; |
| } |
| |
| |
| |
| /** |
| * Return the number of entries (size) of the BTree. |
| */ |
| public int size() |
| { |
| return nbEntries.get(); |
| } |
| |
| |
| /** |
| * Return the persistent record identifier of the BTree. |
| */ |
| public long getRecordId() |
| { |
| return recordId; |
| } |
| |
| |
| /** |
| * Return the root BPage<Object, Object>, or null if it doesn't exist. |
| */ |
| BPage<K, V> getRoot( ) throws IOException |
| { |
| assert( this.rootId == metaRoot.rootID) : "Stale root id " + this.rootId + " "+ metaRoot.rootID; |
| |
| if ( this.rootId == 0 ) |
| { |
| return null; |
| } |
| |
| BPage<K, V> root = ( BPage<K, V> ) recordManager.fetch( this.rootId, bpageSerializer ); |
| root.setRecordId( this.rootId ); |
| root.btree = this; |
| |
| return root; |
| } |
| |
| BPage<K, V> getRoot( MetaRoot meta ) throws IOException |
| { |
| if ( meta.rootID == 0 ) |
| { |
| return null; |
| } |
| |
| BPage<K, V> root = ( BPage<K, V> ) recordManager.fetch( meta.rootID, bpageSerializer ); |
| root.setRecordId( meta.rootID ); |
| root.btree = this; |
| |
| return root; |
| } |
| |
| /** |
| * |
| * Returns the meta root that can be used to fetch the root page |
| * |
| * @return meta root |
| * @throws IOException |
| */ |
| MetaRoot getMetaRoot() throws IOException |
| { |
| if ( isActionCapable ) |
| return ( MetaRoot )recordManager.fetch( -this.recordId ); |
| else |
| return metaRoot; |
| } |
| |
| |
| |
| |
| |
| |
| /** |
| * Implement Externalizable interface. |
| */ |
| public void readExternal( ObjectInput in ) throws IOException, ClassNotFoundException |
| { |
| comparator = ( Comparator<K> ) in.readObject(); |
| keySerializer = ( Serializer ) in.readObject(); |
| valueSerializer = ( Serializer ) in.readObject(); |
| bTreeHeight = in.readInt(); |
| rootId = in.readLong(); |
| pageSize = in.readInt(); |
| nbEntries = new AtomicInteger( in.readInt() ); |
| } |
| |
| |
| /** |
| * Implement Externalizable interface. |
| */ |
| public void writeExternal( ObjectOutput out ) throws IOException |
| { |
| out.writeObject( comparator ); |
| out.writeObject( keySerializer ); |
| out.writeObject( valueSerializer ); |
| out.writeInt( bTreeHeight ); |
| out.writeLong( rootId ); |
| out.writeInt( pageSize ); |
| out.writeInt( nbEntries.get() ); |
| } |
| |
| |
| public void setValueSerializer( Serializer valueSerializer ) |
| { |
| this.valueSerializer = valueSerializer; |
| } |
| |
| |
| /** PRIVATE INNER CLASS |
| * Browser returning no element. |
| */ |
| class EmptyBrowser extends TupleBrowser<K, V> |
| { |
| public boolean getNext( Tuple<K, V> tuple ) |
| { |
| return false; |
| } |
| |
| public boolean getPrevious( Tuple<K, V> tuple ) |
| { |
| return false; |
| } |
| } |
| |
| |
| /** |
| * @return the comparator |
| */ |
| public Comparator<K> getComparator() |
| { |
| return comparator; |
| } |
| |
| |
| |
| void setAsCurrentAction( ActionContext context ) |
| { |
| if ( context != null ) |
| { |
| assert( isActionCapable == true ); |
| ( ( ActionRecordManager )recordManager ).setCurrentActionContext( context ); |
| } |
| } |
| |
| void unsetAsCurrentAction( ActionContext context ) |
| { |
| if ( context != null ) |
| { |
| assert( isActionCapable == true ); |
| ( ( ActionRecordManager )recordManager ).unsetCurrentActionContext( context ); |
| } |
| } |
| |
| |
| ActionContext beginAction( boolean readOnly, String whoStarted ) |
| { |
| ActionContext context = null; |
| if ( isActionCapable ) |
| { |
| context = ( ( ActionRecordManager )recordManager ).beginAction( readOnly, whoStarted ); |
| } |
| return context; |
| } |
| |
| |
| void endAction( ActionContext context ) |
| { |
| if ( context != null ) |
| { |
| assert( isActionCapable ); |
| ( ( ActionRecordManager )recordManager ).endAction( context ); |
| } |
| } |
| |
| void abortAction( ActionContext context ) |
| { |
| if ( context != null ) |
| { |
| assert( isActionCapable ); |
| ( ( ActionRecordManager )recordManager ).abortAction( context ); |
| } |
| |
| } |
| |
| |
| BPage<K,V> copyOnWrite( BPage<K,V> page) throws IOException |
| { |
| return page.copyOnWrite(); |
| |
| } |
| |
| private MetaRoot copyOnWrite( MetaRoot oldMetaRoot ) |
| { |
| MetaRoot newMetaRoot = new MetaRoot(); |
| newMetaRoot.rootID = oldMetaRoot.rootID; |
| newMetaRoot.treeHeight = oldMetaRoot.treeHeight; |
| |
| return newMetaRoot; |
| } |
| |
| private void updateMetaRoot( long newRootId, int newTreeHeight ) throws IOException |
| { |
| metaRoot = this.copyOnWrite( metaRoot ); |
| metaRoot.rootID = newRootId; |
| metaRoot.treeHeight = newTreeHeight; |
| |
| if ( isActionCapable ) |
| recordManager.update( -this.recordId, metaRoot ); |
| } |
| |
| V copyValue( V value) throws IOException |
| { |
| |
| byte[] array; |
| V valueCopy = null; |
| |
| if ( this.valueSerializer != null ) |
| { |
| array = this.valueSerializer.serialize( value ); |
| valueCopy = (V) this.valueSerializer.deserialize( array ); |
| } |
| else |
| { |
| ObjectOutputStream out = null; |
| ObjectInputStream in = null; |
| ByteArrayOutputStream bout = null; |
| ByteArrayInputStream bin = null; |
| |
| try |
| { |
| bout = new ByteArrayOutputStream(); |
| out = new ObjectOutputStream( bout ); |
| out.writeObject( value ); |
| out.flush(); |
| byte[] arr = bout.toByteArray(); |
| bin = new ByteArrayInputStream( arr ); |
| in =new ObjectInputStream( bin ); |
| valueCopy = ( V )in.readObject(); |
| } |
| catch ( ClassNotFoundException e ) |
| { |
| throw new WrappedRuntimeException( e ); |
| } |
| finally |
| { |
| if ( bout != null ) |
| bout.close(); |
| |
| if ( out != null ) |
| out.close(); |
| |
| if ( bin != null ) |
| bin.close(); |
| |
| if ( in != null ) |
| in.close(); |
| } |
| |
| } |
| return valueCopy; |
| } |
| |
| |
| |
| public String toString() |
| { |
| StringBuilder sb = new StringBuilder(); |
| |
| sb.append( "BTree" ); |
| sb.append( "(height:" ).append(bTreeHeight ); |
| sb.append( ", pageSize:" ).append( pageSize ); |
| sb.append( ", nbEntries:" ).append( nbEntries ); |
| sb.append( ", rootId:" ).append( rootId ); |
| sb.append( ", comparator:" ); |
| |
| if ( comparator == null ) |
| { |
| sb.append( "null" ); |
| } |
| else |
| { |
| sb.append( comparator.getClass().getSimpleName() ); |
| } |
| |
| sb.append( ", keySerializer:" ); |
| |
| if ( keySerializer == null ) |
| { |
| sb.append( "null" ); |
| } |
| else |
| { |
| sb.append( keySerializer.getClass().getSimpleName() ); |
| } |
| |
| sb.append( ", valueSerializer:" ); |
| |
| if ( valueSerializer == null ) |
| { |
| sb.append( "null" ); |
| } |
| else |
| { |
| sb.append( valueSerializer.getClass().getSimpleName() ); |
| } |
| |
| sb.append( ")\n" ); |
| |
| return sb.toString(); |
| } |
| |
| /** |
| * Used to poin to the root page that the reader needs based on the reader's |
| * read action context. ReadWrite actions always use the latest root. |
| */ |
| class MetaRoot |
| { |
| long rootID; |
| int treeHeight; |
| } |
| } |
