You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by el...@apache.org on 2012/01/19 14:47:39 UTC
svn commit: r1233376 - in /directory/sandbox/elecharny/shared-mvbt: ./ src/
src/main/ src/main/java/ src/main/java/org/ src/main/java/org/apache/
src/main/java/org/apache/directory/
src/main/java/org/apache/directory/btree/ src/main/java/org/apache/dir...
Author: elecharny
Date: Thu Jan 19 13:47:38 2012
New Revision: 1233376
URL: http://svn.apache.org/viewvc?rev=1233376&view=rev
Log:
Added a first drop of the MVCC-BTree code
Added:
directory/sandbox/elecharny/shared-mvbt/ (with props)
directory/sandbox/elecharny/shared-mvbt/pom.xml
directory/sandbox/elecharny/shared-mvbt/src/
directory/sandbox/elecharny/shared-mvbt/src/main/
directory/sandbox/elecharny/shared-mvbt/src/main/java/
directory/sandbox/elecharny/shared-mvbt/src/main/java/org/
directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/
directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/
directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/
directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/BTree.java
directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Find.java
directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java
directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/PageInsert.java
directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/helper/
directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/helper/LongComparator.java
directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/helper/Serializer.java
directory/sandbox/elecharny/shared-mvbt/src/test/
directory/sandbox/elecharny/shared-mvbt/src/test/java/
directory/sandbox/elecharny/shared-mvbt/src/test/java/org/
directory/sandbox/elecharny/shared-mvbt/src/test/java/org/apache/
directory/sandbox/elecharny/shared-mvbt/src/test/java/org/apache/directory/
directory/sandbox/elecharny/shared-mvbt/src/test/java/org/apache/directory/btree/
directory/sandbox/elecharny/shared-mvbt/src/test/java/org/apache/directory/btree/PageTest.java
Propchange: directory/sandbox/elecharny/shared-mvbt/
------------------------------------------------------------------------------
--- svn:ignore (added)
+++ svn:ignore Thu Jan 19 13:47:38 2012
@@ -0,0 +1,7 @@
+target
+.classpath
+.project
+.settings
+*.iml
+*.ipr
+*.iws
Added: directory/sandbox/elecharny/shared-mvbt/pom.xml
URL: http://svn.apache.org/viewvc/directory/sandbox/elecharny/shared-mvbt/pom.xml?rev=1233376&view=auto
==============================================================================
--- directory/sandbox/elecharny/shared-mvbt/pom.xml (added)
+++ directory/sandbox/elecharny/shared-mvbt/pom.xml Thu Jan 19 13:47:38 2012
@@ -0,0 +1,87 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!--
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing,
+ software distributed under the License is distributed on an
+ "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ KIND, either express or implied. See the License for the
+ specific language governing permissions and limitations
+ under the License.
+-->
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <parent>
+ <groupId>org.apache.directory.project</groupId>
+ <artifactId>project</artifactId>
+ <version>26</version>
+ <relativePath></relativePath>
+ </parent>
+
+ <groupId>org.apache.directory.db</groupId>
+ <artifactId>apache-mvbt</artifactId>
+ <name>ApacheDS MVCC BTree implementation</name>
+ <packaging>bundle</packaging>
+
+ <description>A MVCC BTree Implementation</description>
+
+ <!-- dependencies>
+ <dependency>
+ <groupId>${project.groupId}</groupId>
+ <artifactId>apacheds-i18n</artifactId>
+ </dependency>
+ </dependencies -->
+
+ <build>
+ <pluginManagement>
+ <plugins>
+ <plugin>
+ <groupId>org.apache.rat</groupId>
+ <artifactId>apache-rat-plugin</artifactId>
+ <configuration>
+ <excludeSubProjects>false</excludeSubProjects>
+ <excludes>
+ <exclude>**/*</exclude>
+ </excludes>
+ </configuration>
+ </plugin>
+ </plugins>
+ </pluginManagement>
+ <plugins>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-jar-plugin</artifactId>
+ <configuration>
+ <archive>
+ <manifestFile>META-INF/MANIFEST.MF</manifestFile>
+ <addMavenDescriptor>false</addMavenDescriptor>
+ </archive>
+ </configuration>
+ </plugin>
+
+ <plugin>
+ <groupId>org.apache.felix</groupId>
+ <artifactId>maven-bundle-plugin</artifactId>
+ <inherited>true</inherited>
+ <extensions>true</extensions>
+ <configuration>
+ <manifestLocation>META-INF</manifestLocation>
+ <instructions>
+ <Bundle-SymbolicName>${project.groupId}.db</Bundle-SymbolicName>
+ <Export-Package>
+ {local-packages};version=${project.version};-noimport:=true
+ </Export-Package>
+ </instructions>
+ </configuration>
+ </plugin>
+ </plugins>
+ </build>
+</project>
Added: directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/BTree.java
URL: http://svn.apache.org/viewvc/directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/BTree.java?rev=1233376&view=auto
==============================================================================
--- directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/BTree.java (added)
+++ directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/BTree.java Thu Jan 19 13:47:38 2012
@@ -0,0 +1,400 @@
+/**
+ * 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 org.apache.directory.btree;
+
+
+import java.io.IOException;
+import java.io.Serializable;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.concurrent.atomic.AtomicLong;
+import org.apache.directory.btree.Page.OverflowResult;
+import org.apache.directory.btree.Page.PageResult;
+import org.apache.directory.btree.helper.Serializer;
+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>Page</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>Page</code> objects.
+ *
+ * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
+ */
+public class BTree<K, V>
+{
+ 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;
+
+ /** This BTree's record ID in the PageManager. */
+ private transient long recordId;
+
+ private transient AtomicLong pageRecordIdGenerator;
+
+ /** 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;
+
+ protected Page<K, V> rootPage;
+
+ private Map<Long, Page<K, V>> roots = new HashMap<Long, Page<K, V>>();
+
+ /**
+ * Height of the B+Tree. This is the number of BPages you have to traverse
+ * to get to a leaf Page, starting from the root.
+ */
+ int bTreeHeight;
+
+ /** Revision */
+ private AtomicLong revision = new AtomicLong(0);
+
+ /** Number of entries in each Page. */
+ protected int pageSize;
+
+ /**
+ * 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( Comparator<K> comparator ) throws IOException
+ {
+ createInstance( 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( Comparator<K> comparator, Serializer keySerializer, Serializer valueSerializer ) throws IOException
+ {
+ createInstance( 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( Comparator<K> comparator, Serializer keySerializer,
+ Serializer valueSerializer, int pageSize ) throws IOException
+ {
+ createInstance( comparator, keySerializer, valueSerializer, pageSize );
+ }
+
+
+ /**
+ * The real BTree constructor.
+ */
+ private void createInstance( Comparator<K> comparator, Serializer keySerializer,
+ Serializer valueSerializer, int pageSize) throws IOException
+ {
+ 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 Page
+ if ( ( pageSize & 1 ) != 0 )
+ {
+ throw new IllegalArgumentException( I18n.err( I18n.ERR_522 ) );
+ }
+
+ this.comparator = comparator;
+ this.keySerializer = keySerializer;
+ this.valueSerializer = valueSerializer;
+ this.pageSize = pageSize;
+
+ // Now create the MetaRoot and store it into the map with a first revision
+ //roots = new HashMap<Long, BTree<K,V>.MetaRoot>();
+ pageRecordIdGenerator = new AtomicLong(0);
+ }
+
+
+ public void setPageSize( int pageSize )
+ {
+ this.pageSize = pageSize;
+
+ if ( pageSize <= 0 )
+ {
+ this.pageSize = DEFAULT_SIZE;
+ }
+ }
+
+
+ /**
+ * 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 void insert( K key, V value ) throws IOException
+ {
+ if ( key == null )
+ {
+ throw new IllegalArgumentException( I18n.err( I18n.ERR_523 ) );
+ }
+
+ if ( value == null )
+ {
+ throw new IllegalArgumentException( I18n.err( I18n.ERR_524 ) );
+ }
+
+ //acquireWriteLock();
+
+ try
+ {
+ if ( rootPage == null )
+ {
+ // BTree is currently empty, create a new root Page with one value
+ if ( DEBUG )
+ {
+ System.out.println( "BTree.insert() new root Page" );
+ }
+
+ rootPage = new Page<K, V>( this, key, value );
+ bTreeHeight = 1;
+ roots.put( rootPage.getRevision(), rootPage );
+
+ return;
+ }
+ else
+ {
+ // We have a rootPage. Try to insert the the value in the tree at the right place,
+ // starting from the root page
+ long revision = generateRevision();
+
+ Page.InsertResult<K, V> insert = rootPage.insert( revision, key, value );
+
+ if ( insert == null )
+ {
+ System.out.println( "------------> NULL" );
+ }
+
+ if ( insert instanceof PageResult )
+ {
+ rootPage = ( ( PageResult<K, V> ) insert ).page;
+ roots.put( revision, rootPage );
+ }
+ else
+ {
+ // We have to create a new rootPage
+ rootPage = new Page<K, V>( revision, this, (OverflowResult<K, V>)insert );
+ roots.put( revision, rootPage );
+ }
+ }
+ }
+ finally
+ {
+ //releaseWriteLock()
+ }
+ }
+ /**
+ * 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
+ {
+ if ( key == null )
+ {
+ throw new IllegalArgumentException( I18n.err( I18n.ERR_523 ) );
+ }
+
+ if ( rootPage == null )
+ {
+ return null;
+ }
+
+ return rootPage.find( key );
+ }
+
+
+ /**
+ * Return the persistent record identifier of the BTree.
+ */
+ public long getRecordId()
+ {
+ return recordId;
+ }
+
+
+ public void setValueSerializer( Serializer valueSerializer )
+ {
+ this.valueSerializer = valueSerializer;
+ }
+
+
+ /**
+ * @return the comparator
+ */
+ public Comparator<K> getComparator()
+ {
+ return comparator;
+ }
+
+
+ /** No qualifier */ long generateRecordId()
+ {
+ return pageRecordIdGenerator.getAndIncrement();
+ }
+
+
+ /** No qualifier */ long generateRevision()
+ {
+ return revision.getAndIncrement();
+ }
+
+
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "BTree" );
+ sb.append( "(height:" ).append(bTreeHeight );
+ sb.append( ", pageSize:" ).append( pageSize );
+ sb.append( ", nbEntries:" ).append( rootPage.getNbElems() );
+ //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( ") : " );
+ sb.append( rootPage );
+
+ return sb.toString();
+ }
+}
Added: directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Find.java
URL: http://svn.apache.org/viewvc/directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Find.java?rev=1233376&view=auto
==============================================================================
--- directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Find.java (added)
+++ directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Find.java Thu Jan 19 13:47:38 2012
@@ -0,0 +1,186 @@
+package org.apache.directory.btree;
+
+public class Find
+{
+ private static int nbCompare = 0;
+
+ private static int compare( int val1, int val2 )
+ {
+ nbCompare++;
+
+ if ( val1 < val2 )
+ {
+ return -1;
+ }
+ else
+ {
+ if ( val1 > val2 )
+ {
+ return 1;
+ }
+ else
+ {
+ return 0;
+ }
+ }
+ }
+
+ public static int findIndex( int[] array, int value )
+ {
+ int left = 0;
+ int right = array.length - 1;
+
+ // binary search
+ while ( left < right )
+ {
+ int middle = ( left + right ) >>> 1;
+
+ int comp = compare( array[middle], value );
+
+ if ( comp < 0 )
+ {
+ left = middle + 1;
+ }
+ else if ( comp > 0 )
+ {
+ right = middle - 1;
+ }
+ else
+ {
+ // Special case : the key already exists,
+ // we can return immediately. The value will be
+ // negative, and as the index may be 0, we subtract 1
+ return -middle - 1;
+ }
+ }
+
+ // Special case : we don't know if the key is present
+ int res = compare( array[left], value );
+
+ if ( res == 0 )
+ {
+ return - ( left + 1 );
+ }
+ else
+ {
+ if ( res < 0 )
+ {
+ return left + 1;
+ }
+ else
+ {
+ return left;
+ }
+ }
+ }
+
+
+ public static void dumpArray( int[] array )
+ {
+ boolean isFirst = true;
+ System.out.print( "[" );
+
+ for ( int i = 0; i < array.length; i++ )
+ {
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ System.out.print( ", " );
+ }
+
+ System.out.print( array[i] );
+ }
+
+ System.out.println( "]" );
+ }
+
+
+ private static int findChildren( int[] array, int key )
+ {
+ int left = 0;
+ int right = array.length - 1;
+
+ // binary search
+ while ( left < right )
+ {
+ int middle = ( left + right ) >>> 1;
+
+ int comp = compare( array[middle], key );
+
+ if ( comp < 0 )
+ {
+ left = middle + 1;
+ }
+ else if ( comp > 0 )
+ {
+ right = middle;
+ }
+ else
+ {
+ // Special case : the key already exists,
+ // we can return immediately
+ return -middle - 1;
+ }
+ }
+
+ if ( left == right )
+ {
+ // Special case : we don't know if the key is present
+ if ( compare( array[left], key ) == 0 )
+ {
+ return -right - 1;
+ }
+ }
+
+ return right;
+ }
+
+
+ public static void main( String[] args )
+ {
+ for ( int i = 15; i < 16; i++ )
+ {
+ int[] array = new int[i];
+
+ for ( int j = 0; j < i; j++ )
+ {
+ array[j] = j << 1;
+ }
+
+ System.out.println( "\nProcessing array size " + i + ": " );
+
+ dumpArray( array );
+
+ boolean isFirst = true;
+
+ for ( int j = -1; j < i*2+1; j++ )
+ {
+ int index = findChildren( array, j );
+ //int index = findIndex( array, j );
+
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ System.out.print( ", " );
+ }
+
+ if ( index < 0 )
+ {
+ System.out.print( j + "=" + ( - ( index + 1 ) ) );
+ }
+ else
+ {
+ System.out.print( j + "~" + index );
+ }
+ }
+ }
+
+ System.out.println( "\n\nNbCompare = " + nbCompare );
+ }
+}
Added: directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java
URL: http://svn.apache.org/viewvc/directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java?rev=1233376&view=auto
==============================================================================
--- directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java (added)
+++ directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java Thu Jan 19 13:47:38 2012
@@ -0,0 +1,803 @@
+/**
+ * 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 org.apache.directory.btree;
+
+
+/**
+ * Page of a Btree.
+ * <p>
+ * The page contains a number of key-value pairs. Keys are ordered to allow
+ * dichotomic search.
+ * <p>
+ * If the page is a leaf page, the keys and values are user-defined and
+ * represent entries inserted by the user.
+ * <p>
+ * If the page is non-leaf, each key represents the greatest key in the
+ * underlying BPages and the values are recids pointing to the children BPages.
+ * The only exception is the rightmost BPage, which is considered to have an
+ * "infinite" key value, meaning that any insert will be to the left of this
+ * pseudo-key
+ *
+ * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
+ */
+public class Page<K, V> implements Cloneable
+{
+ private static final boolean DEBUG = false;
+
+ /** Parent B+Tree. */
+ private transient BTree<K, V> btree;
+
+ /** This BPage's revision */
+ private long revision;
+
+ /** This BPage's record ID in the PageManager. */
+ private long recordId;
+
+ /** Flag indicating if this is a leaf BPage. */
+ private boolean isLeaf;
+
+ /** Keys of children nodes */
+ private K[] keys;
+
+ /** Values associated with keys */
+ private V[] values;
+
+ /** Children pages (recids) associated with keys. (Only valid if non-leaf BPage) */
+ private Page<K, V>[] children;
+
+ /** The number of elements in each child */
+ //private long[] nbChildren;
+
+ /** The number of descendant, including this page */
+ //private long nbDescendants = 0;
+
+ /** The number of current values in the Page */
+ private int nbElems;
+
+
+ /**
+ * No-argument constructor used by serialization.
+ */
+ public Page()
+ {
+ // empty
+ }
+
+
+ /**
+ * Page constructor, for newly created pages.
+ *
+ * @param btree The parent B+tree
+ * @param K the added key
+ * @param V value the added value
+ * @param revisio the current revision
+ */
+ @SuppressWarnings("unchecked") // Cannot create an array of generic objects
+ /** No qualifier */ Page( BTree<K,V> btree, K key, V value )
+ {
+ this.btree = btree;
+ this.revision = btree.generateRevision();
+ this.recordId = btree.generateRecordId();
+
+ // Newly created pages are leaves
+ isLeaf = true;
+
+ // Create an array for the keys
+ keys = (K[])new Object[1];
+ keys[0] = key;
+
+ // Create an array for the values
+ values = (V[])new Object[1];
+ values[0] = value;
+ nbElems = 1;
+
+ // We don't create an array for children as we don't have any yet
+ //nbDescendants = 1;
+ }
+
+
+ @SuppressWarnings("unchecked")
+ /** No qualifier */ Page( long revision, BTree<K, V> btree, OverflowResult<K, V> result )
+ {
+ this.revision = revision;
+ this.btree = btree;
+ this.recordId = btree.generateRecordId();
+ isLeaf = false;
+ nbElems = 1;
+ keys = (K[])new Object[nbElems];
+ keys[0] = result.pivotKey;
+ values = (V[])new Object[nbElems];
+ values[0] = result.pivotValue;
+ children = new Page[nbElems + 1];
+ children[0] = result.leftPage;
+ children[1] = result.rightPage;
+ }
+
+
+ /** No qualifier */ V find( K key )
+ {
+ int index = findIndex( key );
+
+ if ( index < 0 )
+ {
+ return values[- ( index + 1 )];
+ }
+
+ else
+ {
+ if ( isLeaf )
+ {
+ return null;
+ }
+ else
+ {
+ return children[index].find( key );
+ }
+ }
+ }
+
+
+ /**
+ * Get largest key under this BPage. Null is considered to be the
+ * greatest possible key.
+ */
+ /** No qualifier */ K getLargestKey()
+ {
+ return keys[btree.pageSize - 1];
+ }
+
+
+ /**
+ * @return The record ID
+ */
+ /** No qualifier */ long getRecordId()
+ {
+ return recordId;
+ }
+
+
+ /**
+ * @return The revision
+ */
+ /** No qualifier */ long getRevision()
+ {
+ return revision;
+ }
+
+
+ /**
+ * @return The number of elements
+ */
+ /** No qualifier */ long getNbElems()
+ {
+ return nbElems;
+ }
+
+
+ /** No qualifier */ boolean isLeaf()
+ {
+ return isLeaf;
+ }
+
+
+ /**
+ * Find the position in the current page where we will insert
+ * the new key
+ * @param array
+ * @param value
+ * @return
+ */
+ private int findIndex( K key )
+ {
+ int left = 0;
+ int right = nbElems - 1;
+
+ // binary search
+ while ( left < right )
+ {
+ int middle = ( left + right ) >>> 1;
+
+ int comp = compare( keys[middle], key );
+
+ if ( comp < 0 )
+ {
+ left = middle + 1;
+ }
+ else if ( comp > 0 )
+ {
+ if ( middle == left )
+ {
+ return left;
+ }
+
+ right = middle - 1;
+ }
+ else
+ {
+ // Special case : the key already exists,
+ // we can return immediately. The value will be
+ // negative, and as the index may be 0, we subtract 1
+ return - ( middle + 1 );
+ }
+ }
+
+ // Special case : we don't know if the key is present
+ int comp = compare( keys[left], key );
+
+ if ( comp == 0 )
+ {
+ return - ( left + 1 );
+ }
+ else
+ {
+ if ( comp < 0 )
+ {
+ return left + 1;
+ }
+ else
+ {
+ return left;
+ }
+ }
+ }
+
+
+ /**
+ * Insert the given key and value into this page.
+ * <p>
+ *
+ * @param height Height of the current BPage (zero is leaf page)
+ * @param key Insert key
+ * @param value Insert value
+ * @param replace Set to true to replace the existing value, if one exists.
+ * @return Insertion result containing existing value OR a BPage if the key
+ * was inserted and provoked a BPage overflow.
+ */
+ /** No qualifier */ InsertResult<K, V> insert( long revision, K key, V value )
+ {
+ if ( isLeaf )
+ {
+ return insertPage( revision, key, value );
+ }
+ else
+ {
+ // Find the position in the page we will add this value, or get the
+ // index of the children to update
+ int index = findIndex( key );
+
+ if ( index < 0 )
+ {
+ index = - ( index + 1 );
+
+ return replaceValue( revision, index, value );
+ }
+ else
+ {
+ InsertResult<K, V> result = children[index].insert( revision, key, value );
+
+ if ( result instanceof PageResult )
+ {
+ return replaceChild( revision, (PageResult<K, V>)result, index );
+ }
+ else
+ {
+ if ( nbElems < btree.pageSize )
+ {
+ return insert( revision, (OverflowResult<K, V>)result, index );
+ }
+ else
+ {
+ return split( revision, (OverflowResult<K, V>)result, index );
+ }
+ }
+ }
+ }
+ }
+
+
+ private InsertResult<K, V> insertPage( long revision, K key, V value )
+ {
+ int index = findIndex( key );
+
+ if ( index < 0 )
+ {
+ index = - ( index + 1 );
+ Page<K, V> newPage = copy( revision );
+ newPage.values[index] = value;
+
+ return new PageResult<K, V>( newPage );
+ }
+
+ if ( nbElems < btree.pageSize )
+ {
+ if ( index < 0 )
+ {
+ index = - ( index + 1 );
+ return replaceValue( revision, index, value );
+ }
+ else
+ {
+ return insert( revision, index, key, value );
+ }
+ }
+ else
+ {
+ return splitLeaf( revision, index, key, value, null, null );
+ }
+ }
+
+
+ private InsertResult<K, V> replaceChild( long revision, PageResult<K, V> pageResult, int index )
+ {
+ Page<K, V> newPage = copy( revision );
+ newPage.children[index] = pageResult.page;
+
+ return new PageResult<K, V>( newPage );
+ }
+
+
+ @SuppressWarnings("unchecked")
+ private InsertResult<K, V> insert( long revision, OverflowResult<K, V> result, int index )
+ {
+ Page<K, V> newPage = new Page<K, V>();
+ newPage.btree = btree;
+ newPage.revision = revision;
+ newPage.isLeaf = false;
+ newPage.recordId = btree.generateRecordId();
+ newPage.nbElems = nbElems + 1;
+
+ newPage.keys = (K[])new Object[newPage.nbElems];
+ System.arraycopy( keys, 0, newPage.keys, 0, index );
+ newPage.keys[index] = result.pivotKey;
+ System.arraycopy( keys, index, newPage.keys, index + 1, newPage.nbElems - ( index + 1 ) );
+
+ newPage.values = (V[])new Object[newPage.nbElems];
+ System.arraycopy( values, 0, newPage.values, 0, index );
+ newPage.values[index] = result.pivotValue;
+ System.arraycopy( values, index, newPage.values, index + 1, newPage.nbElems - ( index + 1 ) );
+
+ if ( ! isLeaf )
+ {
+ newPage.children = new Page[newPage.nbElems + 1];
+ System.arraycopy( children, 0, newPage.children, 0, index );
+ newPage.children[index] = result.leftPage;
+ newPage.children[index + 1] = result.rightPage;
+ System.arraycopy( children, index + 1, newPage.children, index + 2, newPage.nbElems + 1 - ( index + 2 ) );
+ }
+
+ return new PageResult<K, V>( newPage );
+ }
+
+
+ private InsertResult<K, V> splitLeaf( long revision, int index, K key, V value, Page<K, V> left, Page<K, V> right )
+ {
+ OverflowResult<K, V> result = new OverflowResult<K, V>();
+
+ int pivot = ( nbElems + 1 ) / 2;
+
+ // i == P -> left = a[0..P-1], median = X, right = a[P..N-1]
+ if ( index == pivot )
+ {
+ result.pivotKey = key;
+ result.pivotValue = value;
+ result.leftPage = copy( revision, 0, pivot - 1 );
+ result.rightPage = copy( revision, pivot, nbElems - 1 );
+
+ return result;
+ }
+
+ // i < P -> left = a[0..index, X, index+1..P - 2], median = a[P-1], right = a[P..N-1]
+ if ( index < pivot )
+ {
+ result.pivotKey = keys[pivot - 1];
+ result.pivotValue = values[pivot - 1];
+ result.leftPage = copyAndInsert( revision, key, value, left, right, index, 0, pivot - 1 );
+ result.rightPage = copy( revision, pivot, nbElems - 1 );
+
+ return result;
+ }
+ else
+ {
+ // i < P -> left = a[0..P - 1], median = a[P], right = a[P+1..N-1]
+ result.pivotKey = keys[pivot];
+ result.pivotValue = values[pivot];
+ result.leftPage = copy( revision, 0, pivot - 1);
+ result.rightPage = copyAndInsert( revision, key, value, left, right, index, pivot + 1, nbElems );
+
+ return result;
+ }
+ }
+
+
+ private InsertResult<K, V> split( long revision, OverflowResult<K, V> overflow, int index )
+ {
+ OverflowResult<K, V> result = new OverflowResult<K, V>();
+
+ int pivot = ( nbElems + 1 ) / 2;
+
+ // i == P -> left = a[0..P-1], median = X, right = a[P..N-1]
+ if ( index == pivot )
+ {
+ result.pivotKey = overflow.pivotKey;
+ result.pivotValue = overflow.pivotValue;
+ result.leftPage = copy( revision, 0, pivot - 1 );
+ result.rightPage = copy( revision, pivot, nbElems - 1 );
+
+ return result;
+ }
+
+ // i < P -> left = a[0..index, X, index+1..P - 2], median = a[P-1], right = a[P..N-1]
+ if ( index < pivot )
+ {
+ result.pivotKey = keys[pivot - 1];
+ result.pivotValue = values[pivot - 1];
+ result.leftPage = copyAndInsert( revision, key, value, index, 0, pivot - 1 );
+ result.rightPage = copy( revision, pivot, nbElems - 1 );
+
+ return result;
+ }
+ else
+ {
+ // i < P -> left = a[0..P - 1], median = a[P], right = a[P+1..N-1]
+ result.pivotKey = keys[pivot];
+ result.pivotValue = values[pivot];
+ result.leftPage = copy( revision, 0, pivot - 1);
+ result.rightPage = copyAndInsert( revision, key, value, index, pivot + 1, nbElems );
+
+ return result;
+ }
+ }
+
+
+ @SuppressWarnings("unchecked")
+ private Page<K, V> copy( long revision, int start, int end )
+ {
+ Page<K, V> newPage = new Page<K, V>();
+ newPage.btree = btree;
+ newPage.revision = revision;
+ newPage.isLeaf = isLeaf;
+ newPage.recordId = btree.generateRecordId();
+ newPage.nbElems = end - start + 1;
+ newPage.keys = (K[])new Object[newPage.nbElems];
+ System.arraycopy( keys, start, newPage.keys, 0, newPage.nbElems );
+ newPage.values = (V[])new Object[newPage.nbElems];
+ System.arraycopy( values, start, newPage.values, 0, newPage.nbElems );
+
+ if ( ! isLeaf )
+ {
+ newPage.children = new Page[newPage.nbElems + 1];
+ System.arraycopy( children, start, newPage.children, 0, newPage.nbElems );
+ }
+
+ return newPage;
+ }
+
+ private void dump( Object[] array )
+ {
+ boolean isFirst = true;
+
+ System.out.print( "Array : [" );
+
+ for ( Object object : array )
+ {
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ System.out.print( ", " );
+ }
+
+ System.out.print( object );
+ }
+
+ System.out.println( "]" );
+ }
+
+
+ void arrayCopy( Object[] src, int srcPos, Object[] dest, int destPos, int length )
+ {
+ try
+ {
+ System.arraycopy( src, srcPos, dest, destPos, length );
+ }
+ catch ( ArrayIndexOutOfBoundsException aioobe )
+ {
+ System.out.println( "src: " + srcPos + ", destPos : " + destPos + ", length : " + length );
+ dump( src );
+ dump( dest );
+
+ throw aioobe;
+ }
+ }
+
+
+ @SuppressWarnings("unchecked")
+ private Page<K, V> copyAndInsert( long revision, K key, V value, Page<K, V> left, Page<K, V> right, int index, int start, int end )
+ {
+ Page<K, V> newPage = new Page<K, V>();
+ newPage.btree = btree;
+ newPage.revision = revision;
+ newPage.isLeaf = isLeaf;
+ newPage.recordId = btree.generateRecordId();
+ newPage.nbElems = end - start + 1;
+
+ int middle = index - start;
+
+ newPage.keys = (K[])new Object[newPage.nbElems];
+ arrayCopy( keys, start, newPage.keys, 0, middle );
+ newPage.keys[middle] = key;
+ System.arraycopy( keys, index, newPage.keys, middle + 1, newPage.nbElems - ( middle + 1 ) );
+
+ newPage.values = (V[])new Object[newPage.nbElems];
+ System.arraycopy( values, start, newPage.values, 0, middle );
+ newPage.values[middle] = value;
+ System.arraycopy( values, index, newPage.values, middle + 1, newPage.nbElems - ( middle + 1 ) );
+
+ if ( ! isLeaf )
+ {
+ newPage.children = (Page<K, V>[])new Object[newPage.nbElems + 1];
+ System.arraycopy( children, start, newPage.children, 0, middle );
+ newPage.children[middle] = this;
+ System.arraycopy( children, index, newPage.children, middle + 1, newPage.nbElems - middle );
+ }
+
+ return newPage;
+ }
+
+
+ private InsertResult<K, V> replaceValue( long revision, int index, V value )
+ {
+ Page<K, V> newPage = copy( revision );
+ newPage.values[index] = value;
+
+ return new PageResult<K, V>( newPage );
+ }
+
+
+ @SuppressWarnings("unchecked")
+ private InsertResult<K, V> insert( long revision, int index, K key, V value )
+ {
+ Page<K, V> newPage = new Page<K, V>();
+ newPage.btree = btree;
+ newPage.revision = revision;
+ newPage.isLeaf = isLeaf;
+ newPage.recordId = btree.generateRecordId();
+ newPage.nbElems = nbElems + 1;
+ newPage.keys = (K[])new Object[newPage.nbElems];
+ copyArray( keys, newPage.keys, key, index );
+ newPage.values = (V[])new Object[newPage.nbElems];
+ copyArray( values, newPage.values, value, index );
+
+ return new PageResult<K, V>( newPage );
+ }
+
+
+ private void copyArray( Object[] src, Object[] dest, Object object, int index )
+ {
+ int length = dest.length;
+ System.arraycopy( src, 0, dest, 0, index );
+ dest[index] = object;
+ System.arraycopy( src, index, dest, index+1, length - ( index + 1 ) );
+ }
+
+
+ @SuppressWarnings("unchecked")
+ private Page<K, V> copy( long revision )
+ {
+ Page<K, V> newPage = new Page<K, V>();
+ newPage.btree = btree;
+ newPage.revision = revision;
+ newPage.isLeaf = isLeaf;
+ newPage.recordId = btree.generateRecordId();
+ newPage.nbElems = nbElems;
+ newPage.keys = (K[])new Object[newPage.nbElems];
+ System.arraycopy( keys, 0, newPage.keys, 0, newPage.nbElems );
+ newPage.values = (V[])new Object[newPage.nbElems];
+ System.arraycopy( values, 0, newPage.values, 0, newPage.nbElems );
+
+ if ( ! newPage.isLeaf )
+ {
+ newPage.children = new Page[newPage.nbElems + 1];
+ System.arraycopy( children, 0, newPage.children, 0, newPage.nbElems + 1 );
+ }
+
+ return newPage;
+ }
+
+
+ private final int compare( K value1, K value2 )
+ {
+ if ( value1 == value2 )
+ {
+ return 0;
+ }
+
+ if ( value1 == null )
+ {
+ return 1;
+ }
+
+ if ( value2 == null )
+ {
+ return -1;
+ }
+
+ return btree.getComparator().compare( value1, value2 );
+ }
+
+
+ /** STATIC INNER CLASS
+ * Result from insert() method call. If the insertion has created
+ * a new page, it will be contained in the overflow field.
+ * If the inserted element already exist, then we will store
+ * the existing element.
+ */
+ interface InsertResult<K, V>
+ {
+ }
+
+ static class OverflowResult<K, V> implements InsertResult<K, V>
+ {
+ /** The Left page if it has been split, or the new page containing the new value */
+ Page<K, V> leftPage;
+
+ /** The right page if it has been split, null otherwise*/
+ Page<K, V> rightPage;
+
+ /** The Key that must be copied in the parent page if the page was full */
+ K pivotKey;
+
+ /** The Value that must be copied in the parent page if the page was full */
+ V pivotValue;
+
+ public String toString()
+ {
+ // This is a split page
+ return "Split Page [" + leftPage.recordId + ", r" + leftPage.revision + "], [" +
+ rightPage.recordId + ", r" + rightPage.revision + "], <" + pivotKey + "/" + pivotValue + ">";
+ }
+ }
+
+ static class PageResult<K, V> implements InsertResult<K, V>
+ {
+ Page<K, V> page;
+
+ private PageResult( Page<K, V> page )
+ {
+ this.page = page;
+ }
+
+ public String toString()
+ {
+ return "Modified Page [" + page.recordId + ", r" + page.revision + "]";
+ }
+ }
+
+
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ if ( isLeaf )
+ {
+ sb.append( "Leaf(" );
+ }
+ else
+ {
+ sb.append( "Node(" );
+ }
+
+ // The revision
+ sb.append( "r" ).append( revision ).append( ", " );
+
+ // The recordId
+ sb.append( "id" ).append( recordId ).append( ", " );
+
+ // The page length
+ sb.append( keys.length );
+ sb.append( ") : [" );
+
+ if ( isLeaf )
+ {
+ boolean isFirst = true;
+ int index = 0;
+
+ for ( K key : keys )
+ {
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ sb.append( ", " );
+ }
+
+ sb.append( "<" );
+ sb.append( String.valueOf( key ) );
+ sb.append( "/" );
+ sb.append( values[index] );
+ sb.append( ">" );
+
+ index++;
+ }
+ }
+ else
+ {
+ boolean isFirst = true;
+
+ for ( int i = 0; i < nbElems; i++ )
+ {
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ sb.append( ", " );
+ }
+
+ // Left child
+ sb.append( "[" ).append( children[i] ).append( "], " );
+
+ // Key, value
+ sb.append( "<" );
+ sb.append( keys[i] ).append( "/" ).append( values[i] );
+ sb.append( ">" );
+ }
+
+ // right child
+ sb.append( ", [" ).append( children[nbElems] ).append( "]" );
+
+ }
+
+ sb.append( "]\n" );
+ return sb.toString();
+ }
+}
Added: directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/PageInsert.java
URL: http://svn.apache.org/viewvc/directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/PageInsert.java?rev=1233376&view=auto
==============================================================================
--- directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/PageInsert.java (added)
+++ directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/PageInsert.java Thu Jan 19 13:47:38 2012
@@ -0,0 +1,216 @@
+package org.apache.directory.btree;
+
+import java.util.Random;
+
+public class PageInsert
+{
+ private static int nbCompare = 0;
+
+ private static int nbElems = 0;
+
+ private static int[] array;
+
+
+ private static int compare( int val1, int val2 )
+ {
+ nbCompare++;
+
+ if ( val1 < val2 )
+ {
+ return -1;
+ }
+ else
+ {
+ if ( val1 > val2 )
+ {
+ return 1;
+ }
+ else
+ {
+ return 0;
+ }
+ }
+ }
+
+ public static int findIndex( int[] array, int value )
+ {
+ if ( nbElems == 0 )
+ {
+ return 0;
+ }
+
+ int left = 0;
+ int right = array.length - 1;
+
+ // binary search
+ while ( left < right )
+ {
+ int middle = ( left + right ) >>> 1;
+
+ int comp = compare( array[middle], value );
+
+ if ( comp < 0 )
+ {
+ left = middle + 1;
+ }
+ else if ( comp > 0 )
+ {
+ right = middle - 1;
+ }
+ else
+ {
+ // Special case : the key already exists,
+ // we can return immediately. The value will be
+ // negative, and as the index may be 0, we subtract 1
+ return -middle - 1;
+ }
+ }
+
+ // Special case : we don't know if the key is present
+ int res = compare( array[left], value );
+
+ if ( res == 0 )
+ {
+ return - ( left + 1 );
+ }
+ else
+ {
+ if ( res < 0 )
+ {
+ return left + 1;
+ }
+ else
+ {
+ return left;
+ }
+ }
+ }
+
+
+ public static void dumpArray( int[] array )
+ {
+ boolean isFirst = true;
+ System.out.print( "[" );
+
+ for ( int i = 0; i < array.length; i++ )
+ {
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ System.out.print( ", " );
+ }
+
+ System.out.print( array[i] );
+ }
+
+ System.out.println( "]" );
+ }
+
+
+ private static int findChildren( int[] array, int key )
+ {
+ int left = 0;
+ int right = array.length - 1;
+
+ // binary search
+ while ( left < right )
+ {
+ int middle = ( left + right ) >>> 1;
+
+ int comp = compare( array[middle], key );
+
+ if ( comp < 0 )
+ {
+ left = middle + 1;
+ }
+ else if ( comp > 0 )
+ {
+ right = middle;
+ }
+ else
+ {
+ // Special case : the key already exists,
+ // we can return immediately
+ return -middle - 1;
+ }
+ }
+
+ if ( left == right )
+ {
+ // Special case : we don't know if the key is present
+ if ( compare( array[left], key ) == 0 )
+ {
+ return -right - 1;
+ }
+ }
+
+ return right;
+ }
+
+
+ private static void insert( int value, int index )
+ {
+ if ( index < 0 )
+ {
+ index = - ( index + 1 );
+ }
+ else
+ {
+ int[] newArray = new int[nbElems + 1];
+
+ if ( index > 0 )
+ {
+ System.arraycopy( array, 0, newArray, 0, index );
+ }
+
+ newArray[index] = value;
+ System.arraycopy( array, index, newArray, index + 1, nbElems - index );
+
+ array = newArray;
+ nbElems++;
+ }
+ }
+
+
+ public static void main( String[] args )
+ {
+ Random random = new Random( System.nanoTime() );
+
+ for ( int i = 1; i < 64; i++ )
+ {
+ array = new int[i];
+ nbElems = 0;
+
+ System.out.println( "\nProcessing array size " + i + ": " );
+
+ for ( int j = 0; j < i; j++ )
+ {
+ int value = random.nextInt( 1024 );
+
+ int index = findIndex( array, value );
+
+ boolean isFirst = true;
+
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ System.out.print( ", " );
+ }
+
+ System.out.print( "<" + value + "/" + index + ">" );
+
+ insert( value, index );
+ }
+
+ System.out.println();
+
+ dumpArray( array );
+ }
+ }
+}
Added: directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/helper/LongComparator.java
URL: http://svn.apache.org/viewvc/directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/helper/LongComparator.java?rev=1233376&view=auto
==============================================================================
--- directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/helper/LongComparator.java (added)
+++ directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/helper/LongComparator.java Thu Jan 19 13:47:38 2012
@@ -0,0 +1,99 @@
+/**
+ * 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 org.apache.directory.btree.helper;
+
+import java.io.Serializable;
+import java.util.Comparator;
+
+import org.apache.directory.server.i18n.I18n;
+
+/**
+ * Comparator for java.lang.Long objects.
+ *
+ * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
+ */
+public final class LongComparator
+ implements Comparator<Long>, Serializable
+{
+
+ /**
+ * Version id for serialization.
+ */
+ final static long serialVersionUID = 1L;
+
+
+ /**
+ * Compare two objects.
+ *
+ * @param obj1 First object
+ * @param obj2 Second object
+ * @return a positive integer if obj1 > obj2, 0 if obj1 == obj2,
+ * and a negative integer if obj1 < obj2
+ */
+ public int compare( Long obj1, Long obj2 )
+ {
+ if ( obj1 == null ) {
+ throw new IllegalArgumentException( I18n.err( I18n.ERR_525 ) );
+ }
+
+ if ( obj2 == null ) {
+ throw new IllegalArgumentException( I18n.err( I18n.ERR_526 ) );
+ }
+
+ long l1 = obj1.longValue();
+ long l2 = obj2.longValue();
+
+ if ( l1 > l2 ) {
+ return 1;
+ } else if ( l1 == l2 ) {
+ return 0;
+ } else {
+ return -1;
+ }
+ }
+
+}
Added: directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/helper/Serializer.java
URL: http://svn.apache.org/viewvc/directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/helper/Serializer.java?rev=1233376&view=auto
==============================================================================
--- directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/helper/Serializer.java (added)
+++ directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/helper/Serializer.java Thu Jan 19 13:47:38 2012
@@ -0,0 +1,76 @@
+/**
+ * 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 org.apache.directory.btree.helper;
+
+import java.io.IOException;
+import java.io.Serializable;
+
+/**
+ * Interface used to provide a serialization mechanism other than a class' normal
+ * serialization.
+ *
+ * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
+ */
+public interface Serializer extends Serializable
+{
+ /**
+ * Serialize the content of an object into a byte array.
+ *
+ * @param obj Object to serialize
+ * @return a byte array representing the object's state
+ */
+ public byte[] serialize( Object obj ) throws IOException;
+
+
+ /**
+ * Deserialize the content of an object from a byte array.
+ *
+ * @param serialized Byte array representation of the object
+ * @return deserialized object
+ */
+ public Object deserialize( byte[] serialized ) throws IOException;
+}
Added: directory/sandbox/elecharny/shared-mvbt/src/test/java/org/apache/directory/btree/PageTest.java
URL: http://svn.apache.org/viewvc/directory/sandbox/elecharny/shared-mvbt/src/test/java/org/apache/directory/btree/PageTest.java?rev=1233376&view=auto
==============================================================================
--- directory/sandbox/elecharny/shared-mvbt/src/test/java/org/apache/directory/btree/PageTest.java (added)
+++ directory/sandbox/elecharny/shared-mvbt/src/test/java/org/apache/directory/btree/PageTest.java Thu Jan 19 13:47:38 2012
@@ -0,0 +1,166 @@
+package org.apache.directory.btree;
+
+import java.io.IOException;
+import java.util.HashSet;
+import java.util.Random;
+import java.util.Set;
+
+import org.apache.directory.btree.helper.LongComparator;
+import org.junit.Test;
+import static org.junit.Assert.assertTrue;
+
+public class PageTest
+{
+ private boolean checkTree( Set<Long> expected, BTree<Long, String> btree ) throws IOException
+ {
+ for ( Long key : expected )
+ {
+ String value = btree.find( key );
+
+ if ( value == null )
+ {
+ return false;
+ }
+
+ //System.out.println( "found : " + value );
+ }
+
+ return true;
+ }
+
+
+ private BTree<Long, String> loadTree( Long[] keys, String[] values ) throws IOException
+ {
+ BTree<Long, String> btree = new BTree<Long, String>( new LongComparator() );
+ btree.setPageSize( 4 );
+
+ for ( int i = 0; i < keys.length; i++ )
+ {
+ btree.insert( keys[i], values[i] );
+ }
+
+ return btree;
+ }
+
+
+ @Test
+ public void testPageInsert1() throws Exception
+ {
+ BTree<Long, String> btree = new BTree<Long, String>( new LongComparator() );
+
+ Long key = Long.valueOf( 10 );
+ String value = "V10";
+ btree.insert( key, value );
+
+ key = Long.valueOf( 5 );
+ value = "V5";
+ btree.insert( key, value );
+
+ key = Long.valueOf( 15 );
+ value = "V15";
+ btree.insert( key, value );
+
+ System.out.println( btree );
+ }
+
+
+ @Test
+ public void testPageInsert() throws Exception
+ {
+ Set<Long> expected = new HashSet<Long>();
+
+ Random random = new Random( System.nanoTime() );
+
+ int nbError = 0;
+
+ long l1 = System.currentTimeMillis();
+
+ for ( int j = 0; j < 10000000; j++ )
+ {
+ BTree<Long, String> btree = new BTree<Long, String>( new LongComparator() );
+ btree.setPageSize( 4 );
+
+ for ( int i = 0; i < 16; i++ )
+ {
+ Long key = (long)random.nextInt( 256 );
+ String value = "V" + key;
+ expected.add( key );
+
+ try
+ {
+ btree.insert( key, value );
+ }
+ catch ( Exception e)
+ {
+ e.printStackTrace();
+ nbError++;
+ }
+
+ //System.out.println( btree );
+ }
+
+ assertTrue( checkTree( expected, btree ) );
+
+ expected.clear();
+ }
+
+ long l2 = System.currentTimeMillis();
+
+ System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError );
+ }
+
+
+ @Test
+ public void testPageInsertEven() throws Exception
+ {
+ Long[] keys = new Long[]{ 2L, 4L, 6L, 8L };
+ String[] values = new String[]{ "V2", "V4", "V6", "V8" };
+
+ BTree<Long, String> btree = loadTree( keys, values );
+
+ // Insert 1L
+ btree.insert( 1L, "V1" );
+
+ System.out.println( btree );
+
+ btree = loadTree( keys, values );
+
+ // Insert 3L
+ btree.insert( 3L, "V3" );
+
+ System.out.println( btree );
+
+ btree = loadTree( keys, values );
+
+ // Insert 5L
+ btree.insert( 5L, "V5" );
+
+ System.out.println( btree );
+
+ btree = loadTree( keys, values );
+
+ // Insert 7L
+ btree.insert( 7L, "V7" );
+
+ System.out.println( btree );
+
+ btree = loadTree( keys, values );
+
+ // Insert 9L
+ btree.insert( 9L, "V9" );
+
+ System.out.println( btree );
+ }
+
+
+ @Test
+ public void testPageInsert2() throws Exception
+ {
+ Long[] keys = new Long[]{ 128L, 241L, 58L };
+ String[] values = new String[]{ "V128", "V241", "V58" };
+
+ BTree<Long, String> btree = loadTree( keys, values );
+
+ System.out.println( btree );
+ }
+}