directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject 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...
Date Thu, 19 Jan 2012 13:47:39 GMT
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 );
+    }
+}



Mime
View raw message