directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1239581 [2/9] - in /directory/apacheds/trunk/jdbm2: ./ src/ src/etc/ src/examples/ src/main/ src/main/java/ src/main/java/jdbm/ src/main/java/jdbm/btree/ src/main/java/jdbm/helper/ src/main/java/jdbm/htree/ src/main/java/jdbm/recman/ src/s...
Date Thu, 02 Feb 2012 12:38:42 GMT
Added: directory/apacheds/trunk/jdbm2/src/main/java/jdbm/btree/BPage.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm2/src/main/java/jdbm/btree/BPage.java?rev=1239581&view=auto
==============================================================================
--- directory/apacheds/trunk/jdbm2/src/main/java/jdbm/btree/BPage.java (added)
+++ directory/apacheds/trunk/jdbm2/src/main/java/jdbm/btree/BPage.java Thu Feb  2 12:38:39 2012
@@ -0,0 +1,1639 @@
+/**
+ * JDBM LICENSE v1.00
+ *
+ * Redistribution and use of this software and associated documentation
+ * ("Software"), with or without modification, are permitted provided
+ * that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain copyright
+ *    statements and notices.  Redistributions must also contain a
+ *    copy of this document.
+ *
+ * 2. Redistributions in binary form must reproduce the
+ *    above copyright notice, this list of conditions and the
+ *    following disclaimer in the documentation and/or other
+ *    materials provided with the distribution.
+ *
+ * 3. The name "JDBM" must not be used to endorse or promote
+ *    products derived from this Software without prior written
+ *    permission of Cees de Groot.  For written permission,
+ *    please contact cg@cdegroot.com.
+ *
+ * 4. Products derived from this Software may not be called "JDBM"
+ *    nor may "JDBM" appear in their names without prior written
+ *    permission of Cees de Groot.
+ *
+ * 5. Due credit should be given to the JDBM Project
+ *    (http://jdbm.sourceforge.net/).
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE JDBM PROJECT AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
+ * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
+ * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
+ * CEES DE GROOT OR ANY CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Copyright 2001 (C) Alex Boisvert. All Rights Reserved.
+ * Contributions are Copyright (C) 2001 by their associated contributors.
+ *
+ */
+
+package jdbm.btree;
+
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+import java.io.ObjectInput;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutput;
+import java.io.ObjectOutputStream;
+import java.util.concurrent.atomic.AtomicInteger;
+
+import jdbm.helper.ActionContext;
+import jdbm.helper.Serializer;
+import jdbm.helper.Tuple;
+import jdbm.helper.TupleBrowser;
+
+import org.apache.directory.server.i18n.I18n;
+
+
+/**
+ * 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 BPage<K, V> implements Serializer
+{ 
+    private static final boolean DEBUG = false;
+
+    /** Version id for serialization. */
+    final static long serialVersionUID = 1L;
+
+    /** Parent B+Tree. */
+    transient BTree<K, V> btree;
+
+    /** This BPage's record ID in the PageManager. */
+    protected transient long recordId;
+
+    /** Flag indicating if this is a leaf BPage. */
+    protected boolean isLeaf;
+
+    /** Keys of children nodes */
+    protected K[] keys;
+
+    /** Values associated with keys.  (Only valid if leaf BPage) */
+    protected V[] values;
+
+    /** Children pages (recids) associated with keys.  (Only valid if non-leaf BPage) */
+    protected long[] children;
+
+    /** Index of first used item at the page */
+    protected int first;
+
+    /** Previous leaf BPage (only if this BPage is a leaf) */
+    protected long previous;
+
+    /** Next leaf BPage (only if this BPage is a leaf) */
+    protected long next;
+    
+    public static AtomicInteger outstandingBrowsers = new AtomicInteger(0);
+
+
+    /**
+     * No-argument constructor used by serialization.
+     */
+    public BPage()
+    {
+        // empty
+    }
+
+
+    /**
+     * Root page overflow constructor
+     */
+    @SuppressWarnings("unchecked")
+    BPage( BTree<K, V> btree, BPage<K, V> root, BPage<K, V> overflow ) throws IOException
+    {
+        this.btree = btree;
+
+        isLeaf = false;
+
+        first = btree.pageSize - 2;
+
+        keys = (K[])new Object[btree.pageSize];
+        keys[btree.pageSize - 2] = overflow.getLargestKey();
+        keys[btree.pageSize - 1] = root.getLargestKey();
+
+        children = new long[btree.pageSize];
+        children[btree.pageSize - 2] = overflow.recordId;
+        children[btree.pageSize - 1] = root.recordId;
+
+        recordId = btree.recordManager.insert( this, this );
+    }
+
+
+    /**
+     * Root page (first insert) constructor.
+     */
+    @SuppressWarnings("unchecked") // Cannot create an array of generic objects
+    BPage( BTree<K,V> btree, K key, V value ) throws IOException
+    {
+        this.btree = btree;
+
+        isLeaf = true;
+
+        first = btree.pageSize - 2;
+
+        keys = (K[])new Object[btree.pageSize];
+        keys[btree.pageSize - 2] = key;
+        keys[btree.pageSize - 1] = null; // I am the root BPage for now
+
+        values = (V[])new Object[btree.pageSize];
+        values[btree.pageSize - 2] = value;
+        values[btree.pageSize - 1] = null; // I am the root BPage for now
+
+        recordId = btree.recordManager.insert( this, this );
+    }
+
+
+    /**
+     * Overflow page constructor.  Creates an empty BPage.
+     */
+    @SuppressWarnings("unchecked") // Cannot create an array of generic objects
+    BPage( BTree btree, boolean isLeaf ) throws IOException
+    {
+        this.btree = btree;
+
+        this.isLeaf = isLeaf;
+
+        // page will initially be half-full
+        first = btree.pageSize / 2;
+
+        keys = (K[])new Object[btree.pageSize];
+        
+        if ( isLeaf )
+        {
+            values = (V[])new Object[btree.pageSize];
+        }
+        else
+        {
+            children = new long[btree.pageSize];
+        }
+
+        recordId = btree.recordManager.insert( this, this );
+    }
+    
+    @SuppressWarnings("unchecked") // Cannot create an array of generic objects
+    BPage<K,V> copyOnWrite()
+    {
+        BPage<K, V> newPage = new BPage<K,V>();
+        
+        newPage.btree = this.btree;
+        newPage.isLeaf = this.isLeaf;
+        
+        newPage.first = this.first;
+        newPage.previous = this.previous;
+        newPage.next = this.next;
+        
+        newPage.keys = (K[])new Object[btree.pageSize];
+        newPage.values = (V[])new Object[btree.pageSize];
+        newPage.children = new long[btree.pageSize];
+        
+        newPage.recordId = this.recordId;
+        
+        if ( this.children != null )
+        {
+            this.copyChildren( this, 0, newPage, 0, btree.pageSize ); // this copies keys as well
+        }
+        
+        if (this.values != null )
+        {
+            this.copyEntries( this, 0, newPage, 0, btree.pageSize ); // this copies keys as well
+        }
+        
+        return newPage;
+    }
+
+
+    /**
+     * Get largest key under this BPage.  Null is considered to be the
+     * greatest possible key.
+     */
+    K getLargestKey()
+    {
+        return keys[btree.pageSize - 1];
+    }
+    
+    
+    /**
+     * @return The record ID
+     */
+    public long getRecordId()
+    {
+        return recordId;
+    }
+    
+    
+    /**
+     * Set the recordId
+     *
+     * @param recordId The recordId
+     */
+    public void setRecordId( long recordId )
+    {
+        this.recordId = recordId;
+    }
+
+
+    /**
+     * Return true if BPage is empty.
+     */
+    boolean isEmpty()
+    {
+        if ( isLeaf )
+        {
+            return ( first == values.length - 1 );
+        }
+        else
+        {
+            return ( first == children.length - 1 );
+        }
+    }
+
+
+    /**
+     * Return true if BPage is full.
+     */
+    boolean isFull()
+    {
+        return ( first == 0 );
+    }
+
+
+    /**
+     * Find the object associated with the given key.
+     *
+     * @param height Height of the current BPage (zero is leaf page)
+     * @param key The key
+     * @param context action context in case of action capable record manager
+     * @return TupleBrowser positionned just before the given key, or before
+     *                      next greater key if key isn't found.
+     */
+    TupleBrowser<K, V> find( int height, K key, ActionContext context) throws IOException
+    {
+        int index = this.findChildren( key );
+        
+        if ( index < 0 )
+        {
+            index = -( index + 1 );
+        }
+
+        BPage<K, V> child = this;
+
+        while ( !child.isLeaf )
+        {
+            // non-leaf BPage
+            child = child.loadBPage( child.children[index] );
+            index = child.findChildren( key );
+            
+            if ( index < 0 )
+            {
+                index = -( index + 1 );
+            }
+        }
+
+        return new Browser( child, index, context);
+    }
+
+
+    /**
+     * Find first entry and return a browser positioned before it.
+     *@param context Action Context in case of 
+     * @return TupleBrowser positionned just before the first entry.
+     */
+    TupleBrowser<K, V> findFirst( ActionContext context ) throws IOException
+    {
+        if ( isLeaf )
+        {
+            return new Browser( this, first, context );
+        }
+        else
+        {
+            BPage<K, V> child = childBPage( first );
+            
+            return child.findFirst( context );
+        }
+    }
+
+
+    /**
+     * Insert the given key and value.
+     * <p>
+     * Since the Btree does not support duplicate entries, the caller must
+     * specify whether to replace the existing value.
+     *
+     * @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.
+     */
+    InsertResult<K, V> insert( int height, K key, V value, boolean replace ) throws IOException
+    {
+        InsertResult<K, V> result;
+        long overflow;
+
+        int index = findChildren( key );
+        boolean keyExists = index < 0;
+        
+        if ( index < 0 )
+        {
+            index = -( index + 1 );
+        }
+
+        height -= 1;
+        
+        BPage<K,V> pageNewCopy = null;
+        
+        if ( height == 0 )
+        {
+            pageNewCopy = btree.copyOnWrite( this );
+            result = new InsertResult<K, V>();
+            result.pageNewCopy = pageNewCopy;
+
+            // inserting on a leaf BPage
+            overflow = -1;
+            
+            if ( DEBUG )
+            {
+                System.out.println( "Bpage.insert() Insert on leaf Bpage key=" + key + " value=" + value + " index="
+                    + index );
+            }
+
+            // This is to deal with the special case where the key already exists.
+            // In this case, the index will contain the key's position, but as a 
+            // negative number
+            if ( keyExists )
+            {
+                // key already exists
+                if ( DEBUG )
+                {
+                    System.out.println( "Bpage.insert() Key already exists." );
+                }
+                
+                result.existing = values[index];
+                
+                if ( replace )
+                {
+                    pageNewCopy.values[index] = value;
+                    btree.recordManager.update( recordId, pageNewCopy, this );
+                }
+                
+                // return the existing key
+                return result;
+            }
+        }
+        else
+        {
+            // non-leaf BPage
+            BPage<K, V> child = childBPage( index );
+            result = child.insert( height, key, value, replace );
+            
+            if( result.pageNewCopy != null)
+            {
+                child = result.pageNewCopy;
+                result.pageNewCopy = null;
+            }
+
+            if ( result.existing != null )
+            {
+                // return existing key, if any.
+                return result;
+            }
+
+            if ( result.overflow == null )
+            {
+                // no overflow means we're done with insertion
+                return result;
+            }
+
+            // there was an overflow, we need to insert the overflow page
+            // on this BPage
+            pageNewCopy = btree.copyOnWrite( this );
+            result.pageNewCopy = pageNewCopy;
+            
+            if ( DEBUG )
+            {
+                System.out.println( "BPage.insert() Overflow page: " + result.overflow.recordId );
+            }
+            
+            key = result.overflow.getLargestKey();
+            overflow = result.overflow.recordId;
+
+            // update child's largest key
+            pageNewCopy.keys[index] = child.getLargestKey();
+
+            // clean result so we can reuse it
+            result.overflow = null;
+        }
+
+        // if we get here, we need to insert a new entry on the BPage
+        // before children[ index ]
+        if ( !pageNewCopy.isFull() )
+        {            
+            if ( height == 0 )
+            {
+                insertEntry( pageNewCopy, index - 1, key, value );
+            }
+            else
+            {
+                insertChild( pageNewCopy, index - 1, key, overflow );
+            }
+            
+            btree.recordManager.update( recordId, pageNewCopy, this );
+            
+            return result;
+        }
+
+        // page is full, we must divide the page
+        int half = btree.pageSize >> 1;
+        BPage<K, V> newPage = new BPage<K, V>( btree, pageNewCopy.isLeaf );
+        
+        if ( index < half )
+        {
+            // move lower-half of entries to overflow BPage,
+            // including new entry
+            if ( DEBUG )
+            {
+                System.out
+                    .println( "Bpage.insert() move lower-half of entries to overflow BPage, including new entry." );
+            }
+            
+            if ( height == 0 )
+            {
+                copyEntries( pageNewCopy, 0, newPage, half, index );
+                setEntry( newPage, half + index, key, value );
+                copyEntries( pageNewCopy, index, newPage, half + index + 1, half - index - 1 );
+            }
+            else
+            {
+                copyChildren( pageNewCopy, 0, newPage, half, index );
+                setChild( newPage, half + index, key, overflow );
+                copyChildren( pageNewCopy, index, newPage, half + index + 1, half - index - 1 );
+            }
+        }
+        else
+        {
+            // move lower-half of entries to overflow BPage,
+            // new entry stays on this BPage
+            if ( DEBUG )
+            {
+                System.out.println( "Bpage.insert() move lower-half of entries to overflow BPage. New entry stays" );
+            }
+            
+            if ( height == 0 )
+            {
+                copyEntries( pageNewCopy, 0, newPage, half, half );
+                copyEntries( pageNewCopy, half, pageNewCopy, half - 1, index - half );
+                setEntry( pageNewCopy, index - 1, key, value );
+            }
+            else
+            {
+                copyChildren( pageNewCopy, 0, newPage, half, half );
+                copyChildren( pageNewCopy, half, pageNewCopy, half - 1, index - half );
+                setChild( pageNewCopy, index - 1, key, overflow );
+            }
+        }
+
+        pageNewCopy.first = half - 1;
+
+        // nullify lower half of entries
+        for ( int i = 0; i < pageNewCopy.first; i++ )
+        {
+            if ( height == 0 )
+            {
+                setEntry( pageNewCopy, i, null, null );
+            }
+            else
+            {
+                setChild( pageNewCopy, i, null, -1 );
+            }
+        }
+
+        if ( pageNewCopy.isLeaf )
+        {
+            // link newly created BPage
+            newPage.previous = pageNewCopy.previous;
+            newPage.next = pageNewCopy.recordId;
+            
+            if ( pageNewCopy.previous != 0 )
+            {
+                BPage<K, V> previousBPage = loadBPage( pageNewCopy.previous );
+                previousBPage = btree.copyOnWrite( previousBPage );
+                previousBPage.next = newPage.recordId;
+                btree.recordManager.update( pageNewCopy.previous, previousBPage, this );
+            }
+            
+            pageNewCopy.previous = newPage.recordId;
+        }
+
+        btree.recordManager.update( recordId, pageNewCopy, this );
+        btree.recordManager.update( newPage.recordId, newPage, this );
+
+        result.overflow = newPage;
+        return result;
+    }
+
+
+    /**
+     * Remove the entry associated with the given key.
+     *
+     * @param height Height of the current BPage (zero is leaf page)
+     * @param key Removal key
+     * @return Remove result object
+     */
+    RemoveResult<K, V> remove( int height, K key ) throws IOException
+    {
+        RemoveResult<K, V> result;
+
+        int half = btree.pageSize / 2;
+        int index = findChildren( key );
+        boolean keyExists = index < 0;
+        
+        if ( index < 0 )
+        {
+            index = -( index + 1 );
+        }
+
+        height -= 1;
+        
+        BPage<K,V> pageNewCopy = btree.copyOnWrite( this );
+        
+        if ( height == 0 )
+        {
+            // remove leaf entry
+            if ( !keyExists )
+            {
+                throw new IllegalArgumentException( I18n.err( I18n.ERR_514, key ) );
+            }
+            
+            result = new RemoveResult<K, V>();
+            result.value = pageNewCopy.values[index];
+            removeEntry( pageNewCopy, index );
+
+            // update this BPage
+            btree.recordManager.update( recordId, pageNewCopy, this );
+        }
+        else
+        {
+            // recurse into Btree to remove entry on a children page
+            BPage<K, V> child = childBPage( index );
+            result = child.remove( height, key );
+            
+            if ( result.pageNewCopy != null )
+            {
+                child = result.pageNewCopy;
+                result.pageNewCopy = null;
+            }
+            else
+            {
+                child = btree.copyOnWrite( child );
+            }
+
+            // update children
+            pageNewCopy.keys[index] = child.getLargestKey();
+            btree.recordManager.update( recordId, pageNewCopy, this );
+
+            if ( result.underflow )
+            {
+                // underflow occured
+                if ( child.first != half + 1 )
+                {
+                    throw new IllegalStateException( I18n.err( I18n.ERR_513, "1" ) );
+                }
+                
+                if ( index < pageNewCopy.children.length - 1 )
+                {
+                    // exists greater brother page
+                    BPage<K, V> brother = pageNewCopy.childBPage( index + 1 );
+                    brother = btree.copyOnWrite( brother );
+                    int bfirst = brother.first;
+                    
+                    if ( bfirst < half )
+                    {
+                        // steal entries from "brother" page
+                        int steal = ( half - bfirst + 1 ) / 2;
+                        brother.first += steal;
+                        child.first -= steal;
+                        
+                        if ( child.isLeaf )
+                        {
+                            copyEntries( child, half + 1, child, half + 1 - steal, half - 1 );
+                            copyEntries( brother, bfirst, child, 2 * half - steal, steal );
+                        }
+                        else
+                        {
+                            copyChildren( child, half + 1, child, half + 1 - steal, half - 1 );
+                            copyChildren( brother, bfirst, child, 2 * half - steal, steal );
+                        }
+
+                        for ( int i = bfirst; i < bfirst + steal; i++ )
+                        {
+                            if ( brother.isLeaf )
+                            {
+                                setEntry( brother, i, null, null );
+                            }
+                            else
+                            {
+                                setChild( brother, i, null, -1 );
+                            }
+                        }
+
+                        // update child's largest key
+                        pageNewCopy.keys[index] = child.getLargestKey();
+
+                        // no change in previous/next BPage
+
+                        // update BPages
+                        btree.recordManager.update( recordId, pageNewCopy, this );
+                        btree.recordManager.update( brother.recordId, brother, this );
+                        btree.recordManager.update( child.recordId, child, this );
+
+                    }
+                    else
+                    {
+                        // move all entries from page "child" to "brother"
+                        if ( brother.first != half )
+                        {
+                            throw new IllegalStateException( I18n.err( I18n.ERR_513, "2" ) );
+                        }
+
+                        brother.first = 1;
+                        
+                        if ( child.isLeaf )
+                        {
+                            copyEntries( child, half + 1, brother, 1, half - 1 );
+                        }
+                        else
+                        {
+                            copyChildren( child, half + 1, brother, 1, half - 1 );
+                        }
+                        
+                        btree.recordManager.update( brother.recordId, brother, this );
+
+                        // remove "child" from current BPage
+                        if ( pageNewCopy.isLeaf )
+                        {
+                            copyEntries( pageNewCopy, pageNewCopy.first, pageNewCopy, pageNewCopy.first + 1, index - pageNewCopy.first );
+                            setEntry( pageNewCopy, pageNewCopy.first, null, null );
+                        }
+                        else
+                        {
+                            copyChildren( pageNewCopy, pageNewCopy.first, pageNewCopy, pageNewCopy.first + 1, index - pageNewCopy.first );
+                            setChild( pageNewCopy, pageNewCopy.first, null, -1 );
+                        }
+                        
+                        pageNewCopy.first += 1;
+                        btree.recordManager.update( recordId, pageNewCopy, this );
+
+                        // re-link previous and next BPages
+                        if ( child.previous != 0 )
+                        {
+                            BPage<K, V> prev = loadBPage( child.previous );
+                            prev = btree.copyOnWrite( prev );
+                            prev.next = child.next;
+                            btree.recordManager.update( prev.recordId, prev, this );
+                        }
+                        
+                        if ( child.next != 0 )
+                        {
+                            BPage<K, V> next = loadBPage( child.next );
+                            next = btree.copyOnWrite( next );
+                            next.previous = child.previous;
+                            btree.recordManager.update( next.recordId, next, this );
+                        }
+
+                        // delete "child" BPage
+                        btree.recordManager.delete( child.recordId );
+                    }
+                }
+                else
+                {
+                    // page "brother" is before "child"
+                    BPage<K, V> brother = pageNewCopy.childBPage( index - 1 );
+                    brother = btree.copyOnWrite( brother );
+                    int bfirst = brother.first;
+                    
+                    if ( bfirst < half )
+                    {
+                        // steal entries from "brother" page
+                        int steal = ( half - bfirst + 1 ) / 2;
+                        brother.first += steal;
+                        child.first -= steal;
+                        
+                        if ( child.isLeaf )
+                        {
+                            copyEntries( brother, 2 * half - steal, child, half + 1 - steal, steal );
+                            copyEntries( brother, bfirst, brother, bfirst + steal, 2 * half - bfirst - steal );
+                        }
+                        else
+                        {
+                            copyChildren( brother, 2 * half - steal, child, half + 1 - steal, steal );
+                            copyChildren( brother, bfirst, brother, bfirst + steal, 2 * half - bfirst - steal );
+                        }
+
+                        for ( int i = bfirst; i < bfirst + steal; i++ )
+                        {
+                            if ( brother.isLeaf )
+                            {
+                                setEntry( brother, i, null, null );
+                            }
+                            else
+                            {
+                                setChild( brother, i, null, -1 );
+                            }
+                        }
+
+                        // update brother's largest key
+                        pageNewCopy.keys[index - 1] = brother.getLargestKey();
+
+                        // no change in previous/next BPage
+
+                        // update BPages
+                        btree.recordManager.update( recordId, pageNewCopy, this );
+                        btree.recordManager.update( brother.recordId, brother, this );
+                        btree.recordManager.update( child.recordId, child, this );
+
+                    }
+                    else
+                    {
+                        // move all entries from page "brother" to "child"
+                        if ( brother.first != half )
+                        {
+                            throw new IllegalStateException( I18n.err( I18n.ERR_513, "3" ) );
+                        }
+
+                        child.first = 1;
+                        
+                        if ( child.isLeaf )
+                        {
+                            copyEntries( brother, half, child, 1, half );
+                        }
+                        else
+                        {
+                            copyChildren( brother, half, child, 1, half );
+                        }
+                        
+                        btree.recordManager.update( child.recordId, child, this );
+
+                        // remove "brother" from current BPage
+                        if ( pageNewCopy.isLeaf )
+                        {
+                            copyEntries( pageNewCopy, pageNewCopy.first, pageNewCopy, pageNewCopy.first + 1, index - 1 - pageNewCopy.first );
+                            setEntry( pageNewCopy, pageNewCopy.first, null, null );
+                        }
+                        else
+                        {
+                            copyChildren( pageNewCopy, pageNewCopy.first, pageNewCopy, pageNewCopy.first + 1, index - 1 - pageNewCopy.first );
+                            setChild( pageNewCopy, pageNewCopy.first, null, -1 );
+                        }
+                        
+                        pageNewCopy.first += 1;
+                        btree.recordManager.update( recordId, pageNewCopy, this );
+
+                        // re-link previous and next BPages
+                        if ( brother.previous != 0 )
+                        {
+                            BPage<K, V> prev = loadBPage( brother.previous );
+                            prev = btree.copyOnWrite( prev );
+                            prev.next = brother.next;
+                            btree.recordManager.update( prev.recordId, prev, this );
+                        }
+                        
+                        if ( brother.next != 0 )
+                        {
+                            BPage<K, V> next = loadBPage( brother.next );
+                            next = btree.copyOnWrite( next );
+                            next.previous = brother.previous;
+                            btree.recordManager.update( next.recordId, next, this );
+                        }
+
+                        // delete "brother" BPage
+                        btree.recordManager.delete( brother.recordId );
+                    }
+                }
+            }
+        }
+
+        // underflow if page is more than half-empty
+        result.underflow = pageNewCopy.first > half;
+        result.pageNewCopy = pageNewCopy;
+
+        return result;
+    }
+
+
+    /**
+     * Find the first children node with a key equal or greater than the given
+     * key.
+     *
+     * @return index of first children with equal or greater key. If the 
+     * key already exists, the index value will be negative
+     */
+    private int findChildren( K key )
+    {
+        int left = first;
+        int right = btree.pageSize - 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 )
+            {
+                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( keys[left], key ) ==0 )
+            {
+                return -right - 1;
+            }
+        }
+        
+        return right;
+    }
+
+
+    /**
+     * Insert entry at given position.
+     */
+    private void insertEntry( BPage<K, V> page, int index, K key, V value ) throws IOException
+    {
+        K[] keys = page.keys;
+        V[] values = page.values;
+        int start = page.first;
+        int count = index - page.first + 1;
+
+        // shift entries to the left
+        System.arraycopy( keys, start, keys, start - 1, count );
+        System.arraycopy( values, start, values, start - 1, count );
+        page.first -= 1;
+        keys[index] = key;
+        values[index] = value;
+    }
+
+
+    /**
+     * Insert child at given position.
+     */
+    private void insertChild( BPage<K, V> page, int index, K key, long child )
+    {
+        K[] keys = page.keys;
+        long[] children = page.children;
+        int start = page.first;
+        int count = index - page.first + 1;
+
+        // shift entries to the left
+        System.arraycopy( keys, start, keys, start - 1, count );
+        System.arraycopy( children, start, children, start - 1, count );
+        page.first -= 1;
+        keys[index] = key;
+        children[index] = child;
+    }
+
+
+    /**
+     * Remove entry at given position.
+     */
+    private void removeEntry( BPage<K, V> page, int index )
+    {
+        K[] keys = page.keys;
+        V[] values = page.values;
+        int start = page.first;
+        int count = index - page.first;
+
+        System.arraycopy( keys, start, keys, start + 1, count );
+        keys[start] = null;
+        System.arraycopy( values, start, values, start + 1, count );
+        values[start] = null;
+        page.first++;
+    }
+
+
+    /**
+     * Set the entry at the given index.
+     */
+    private void setEntry( BPage<K, V> page, int index, K key, V value ) throws IOException
+    {
+        page.keys[index] = key;
+        page.values[index] = value;
+    }
+
+
+    /**
+     * Set the child BPage recordId at the given index.
+     */
+    private void setChild( BPage<K, V> page, int index, K key, long recid )
+    {
+        page.keys[index] = key;
+        page.children[index] = recid;
+    }
+
+
+    /**
+     * Copy entries between two BPages
+     */
+    private void copyEntries( BPage<K, V> source, int indexSource, BPage<K, V> dest, int indexDest, int count )
+    {
+        System.arraycopy( source.keys, indexSource, dest.keys, indexDest, count );
+        System.arraycopy( source.values, indexSource, dest.values, indexDest, count );
+    }
+
+
+    /**
+     * Copy child BPage recids between two BPages
+     */
+    private void copyChildren( BPage<K, V> source, int indexSource, BPage<K, V> dest, int indexDest, int count )
+    {
+        System.arraycopy( source.keys, indexSource, dest.keys, indexDest, count );
+        System.arraycopy( source.children, indexSource, dest.children, indexDest, count );
+    }
+
+
+    /**
+     * Return the child BPage at given index.
+     */
+    // False positive
+    @SuppressWarnings("PMD.UnnecessaryFinalModifier")
+    BPage<K, V> childBPage( int index ) throws IOException
+    {
+        return loadBPage( children[index] );
+    }
+
+
+    /**
+     * Load the BPage at the given recordId.
+     */
+    @SuppressWarnings("unchecked") // The fetch method returns an Object
+    private BPage<K, V> loadBPage( long recid ) throws IOException
+    {
+        BPage<K, V> child = ( BPage<K, V> ) btree.recordManager.fetch( recid, this );
+        child.recordId = recid;
+        child.btree = btree;
+        
+        return child;
+    }
+
+
+    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 byte[] readByteArray( ObjectInput in ) throws IOException
+    {
+        int len = in.readInt();
+        
+        if ( len < 0 )
+        {
+            return null;
+        }
+        
+        byte[] buf = new byte[len];
+        in.readFully( buf );
+        
+        return buf;
+    }
+
+
+    static void writeByteArray( ObjectOutput out, byte[] buf ) throws IOException
+    {
+        if ( buf == null )
+        {
+            out.writeInt( -1 );
+        }
+        else
+        {
+            out.writeInt( buf.length );
+            out.write( buf );
+        }
+    }
+
+
+    /**
+     * Dump the structure of the tree on the screen.  This is used for debugging
+     * purposes only.
+     */
+    private void dump( int height )
+    {
+        StringBuffer prefix = new StringBuffer();
+        
+        for ( int i = 0; i < height; i++ )
+        {
+            prefix.append( "    " );
+        }
+        
+        System.out.println( prefix + "-------------------------------------- BPage recordId=" + recordId );
+        System.out.println( prefix + "first=" + first );
+        
+        for ( int i = 0; i < btree.pageSize; i++ )
+        {
+            if ( isLeaf )
+            {
+                System.out.println( prefix + "BPage [" + i + "] " + keys[i] + " " + values[i] );
+            }
+            else
+            {
+                System.out.println( prefix + "BPage [" + i + "] " + keys[i] + " " + children[i] );
+            }
+        }
+        
+        System.out.println( prefix + "--------------------------------------" );
+    }
+
+
+    /**
+     * Recursively dump the state of the BTree on screen.  This is used for
+     * debugging purposes only.
+     */
+    void dumpRecursive( int height, int level ) throws IOException
+    {
+        height -= 1;
+        level += 1;
+        
+        if ( height > 0 )
+        {
+            for ( int i = first; i < btree.pageSize; i++ )
+            {
+                if ( keys[i] == null )
+                { 
+                    break;
+                }
+                
+                BPage<K, V> child = childBPage( i );
+                child.dump( level );
+                child.dumpRecursive( height, level );
+            }
+        }
+    }
+
+
+    /**
+     * Assert the ordering of the keys on the BPage. This is used for testing
+     * purposes only.
+     */
+    private void assertConsistency()
+    {
+        for ( int i = first; i < btree.pageSize - 1; i++ )
+        {
+            if ( compare( keys[i], keys[i + 1] ) >= 0 )
+            {
+                dump( 0 );
+                throw new Error( I18n.err( I18n.ERR_515 ) );
+            }
+        }
+    }
+
+
+    /**
+     * Recursively assert the ordering of the BPage entries on this page
+     * and sub-pages.  This is used for testing purposes only.
+     */
+    void assertConsistencyRecursive( int height ) throws IOException
+    {
+        assertConsistency();
+        
+        if ( --height > 0 )
+        {
+            for ( int i = first; i < btree.pageSize; i++ )
+            {
+                if ( keys[i] == null )
+                {
+                    break;
+                }
+                
+                BPage<K, V> child = childBPage( i );
+                
+                if ( compare( keys[i], child.getLargestKey() ) != 0 )
+                {
+                    dump( 0 );
+                    child.dump( 0 );
+                    throw new Error( I18n.err( I18n.ERR_516 ) );
+                }
+                
+                child.assertConsistencyRecursive( height );
+            }
+        }
+    }
+
+
+    /**
+     * Deserialize the content of an object from a byte array.
+     *
+     * @param serialized Byte array representation of the object
+     * @return deserialized object
+     *
+     */
+    @SuppressWarnings("unchecked") // Cannot create an array of generic objects
+    public BPage<K, V> deserialize( byte[] serialized ) throws IOException
+    {
+        ByteArrayInputStream bais;
+        ObjectInputStream ois;
+        BPage<K, V> bpage;
+
+        bpage = new BPage<K, V>();
+        bais = new ByteArrayInputStream( serialized );
+        ois = new ObjectInputStream( bais );
+
+        bpage.isLeaf = ois.readBoolean();
+        
+        if ( bpage.isLeaf )
+        {
+            bpage.previous = ois.readLong();
+            bpage.next = ois.readLong();
+        }
+
+        bpage.first = ois.readInt();
+
+        bpage.keys = (K[])new Object[btree.pageSize];
+        
+        try
+        {
+            for ( int i = bpage.first; i < btree.pageSize; i++ )
+            {
+                if ( btree.keySerializer == null )
+                {
+                    bpage.keys[i] = (K)ois.readObject();
+                }
+                else
+                {
+                    serialized = readByteArray( ois );
+                    
+                    if ( serialized != null )
+                    {
+                        bpage.keys[i] = (K)btree.keySerializer.deserialize( serialized );
+                    }
+                }
+            }
+        }
+        catch ( ClassNotFoundException except )
+        {
+            throw new IOException( except.getLocalizedMessage() );
+        }
+
+        if ( bpage.isLeaf )
+        {
+            bpage.values = (V[])new Object[btree.pageSize];
+            
+            try
+            {
+                for ( int i = bpage.first; i < btree.pageSize; i++ )
+                {
+                    if ( btree.valueSerializer == null )
+                    {
+                        bpage.values[i] =(V) ois.readObject();
+                    }
+                    else
+                    {
+                        serialized = readByteArray( ois );
+                        
+                        if ( serialized != null )
+                        {
+                            bpage.values[i] = (V)btree.valueSerializer.deserialize( serialized );
+                        }
+                    }
+                }
+            }
+            catch ( ClassNotFoundException except )
+            {
+                throw new IOException( except.getLocalizedMessage() );
+            }
+        }
+        else
+        {
+            bpage.children = new long[btree.pageSize];
+            
+            for ( int i = bpage.first; i < btree.pageSize; i++ )
+            {
+                bpage.children[i] = ois.readLong();
+            }
+        }
+        
+        ois.close();
+        bais.close();
+
+        return bpage;
+    }
+
+
+    /** 
+     * Serialize the content of an object into a byte array.
+     *
+     * @param obj Object to serialize
+     * @return a byte array representing the object's state
+     *
+     */
+    @SuppressWarnings("unchecked") // The serialize signature requires an Object, so we have to cast
+    public byte[] serialize( Object obj ) throws IOException
+    {
+        byte[] serialized;
+        ByteArrayOutputStream baos;
+        ObjectOutputStream oos;
+        BPage<K, V> bpage;
+        byte[] data;
+
+        // note:  It is assumed that BPage instance doing the serialization is the parent
+        // of the BPage object being serialized.
+        bpage = ( BPage<K, V> ) obj;
+        baos = new ByteArrayOutputStream();
+        oos = new ObjectOutputStream( baos );
+
+        oos.writeBoolean( bpage.isLeaf );
+        
+        if ( bpage.isLeaf )
+        {
+            oos.writeLong( bpage.previous );
+            oos.writeLong( bpage.next );
+        }
+
+        oos.writeInt( bpage.first );
+
+        for ( int i = bpage.first; i < btree.pageSize; i++ )
+        {
+            if ( btree.keySerializer == null )
+            {
+                oos.writeObject( bpage.keys[i] );
+            }
+            else
+            {
+                if ( bpage.keys[i] != null )
+                {
+                    serialized = btree.keySerializer.serialize( bpage.keys[i] );
+                    writeByteArray( oos, serialized );
+                }
+                else
+                {
+                    writeByteArray( oos, null );
+                }
+            }
+        }
+
+        if ( bpage.isLeaf )
+        {
+            for ( int i = bpage.first; i < btree.pageSize; i++ )
+            {
+                if ( btree.valueSerializer == null )
+                {
+                    oos.writeObject( bpage.values[i] );
+                }
+                else
+                {
+                    if ( bpage.values[i] != null )
+                    {
+                        serialized = btree.valueSerializer.serialize( bpage.values[i] );
+                        writeByteArray( oos, serialized );
+                    }
+                    else
+                    {
+                        writeByteArray( oos, null );
+                    }
+                }
+            }
+        }
+        else
+        {
+            for ( int i = bpage.first; i < btree.pageSize; i++ )
+            {
+                oos.writeLong( bpage.children[i] );
+            }
+        }
+
+        oos.flush();
+        data = baos.toByteArray();
+        oos.close();
+        baos.close();
+        
+        return data;
+    }
+
+    /** 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.
+     */
+    static class InsertResult<K, V>
+    {
+
+        /**
+         * Overflow page.
+         */
+        BPage<K, V> overflow;
+
+        /**
+         * Existing value for the insertion key.
+         */
+        V existing;
+        
+        /**
+         * New version of the page doing the insert
+         */
+        BPage<K, V> pageNewCopy;
+    }
+
+    /** STATIC INNER CLASS
+     *  Result from remove() method call. If we had to removed a BPage,
+     *  it will be stored into the underflow field.
+     */
+    static class RemoveResult<K, V>
+    {
+        /**
+         * Set to true if underlying pages underflowed
+         */
+        boolean underflow;
+
+        /**
+         * Removed entry value
+         */
+        V value;
+        
+        /**
+         * New version of the page doing the remove
+         */
+        BPage<K, V> pageNewCopy;   
+        
+    }
+
+    /** PRIVATE INNER CLASS
+     * Browser to traverse leaf BPages.
+     */
+    class Browser extends TupleBrowser<K, V>
+    {
+        /** Current page. */
+        private BPage<K, V> page;
+        
+        /** context used to track browsing action */
+        ActionContext context;
+        
+        /**
+         * Current index in the page.  The index positionned on the next
+         * tuple to return.
+         */
+        private int index;
+
+
+        /**
+         * Create a browser.
+         *
+         * @param page Current page
+         * @param context context in case of action capable record manager 
+         * @param index Position of the next tuple to return.
+         */
+        Browser( BPage<K, V> page, int index, ActionContext context)
+        {
+            this.page = page;
+            this.index = index;
+            this.context = context;
+            
+            outstandingBrowsers.incrementAndGet();
+        }
+
+
+        /**
+         * Get the next Tuple in the current BTree. We have 3 cases to deal with :
+         * 1) we are at the end of the btree. We will return false, the tuple won't be set.
+         * 2) we are in the middle of a page : grab the values and store them into the tuple
+         * 3) we are at the end of the page : grab the next page, and get the tuple from it.
+         * 
+         * @return true if we have found a tumple, false otherwise.
+         */
+        public boolean getNext( Tuple<K, V> tuple ) throws IOException
+        {
+            btree.setAsCurrentAction( context ); 
+            try
+            {
+                // First, check that we are within a page                                                            
+                if ( index < page.btree.pageSize )
+                {
+                    // We are. Now check that we have a Tuple                                                        
+                    if ( page.keys[index] == null )
+                    {
+                        // no : reached end of the tree.                                                             
+                        return false;
+                    }
+                }
+                // all the tuple for this page has been read. Move to the                                            
+                // next page, if we have one.                                                                        
+                else if ( page.next != 0 )
+                {
+                    // move to next page                                                                             
+                    page = page.loadBPage( page.next );
+                    index = page.first;
+                }
+    
+                tuple.setKey( page.keys[index] );
+                tuple.setValue( page.values[index] );
+                index++;
+            }
+            catch( IOException e )
+            {
+                btree.abortAction( context );
+                context = null;
+                this.close();
+                throw e;
+            }
+            finally
+            {
+                if ( context != null )
+                {
+                    btree.unsetAsCurrentAction( context );
+                }
+            }
+          
+            return true;
+        }
+
+        public boolean getPrevious( Tuple<K, V> tuple ) throws IOException
+        {
+            btree.setAsCurrentAction( context );
+            
+            try
+            {
+                if ( index == page.first )
+                {
+                    if ( page.previous != 0 )
+                    {
+                        page = page.loadBPage( page.previous );
+                        index = page.btree.pageSize;
+                    }
+                    else
+                    {
+                        // reached beginning of the tree
+                        return false;
+                    }
+                }
+    
+                index--;
+                tuple.setKey( page.keys[index] );
+                tuple.setValue( page.values[index] );
+            }
+            catch( IOException e )
+            {
+                btree.abortAction( context );
+                context = null;
+                this.close();
+                throw e;
+            }
+            finally
+            {
+                if ( context != null )
+                {
+                    btree.unsetAsCurrentAction( context );
+                }
+            }
+
+            return true;
+        }
+        
+        @Override
+        public void close()
+        {
+            super.close();
+            
+            if ( context!= null )
+            {
+                btree.setAsCurrentAction( context );
+                btree.endAction( context );
+                context = null;
+            }
+            
+            int browserCount = outstandingBrowsers.decrementAndGet();
+            
+            if ( browserCount > 0 )
+            {
+                //System.out.println( "JDBM btree browsers are outstanding after close: " + browserCount );
+            }
+        }
+
+    }
+    
+    
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+        
+        if ( isLeaf )
+        {
+            sb.append( "Leaf(" );
+        }
+        else
+        {
+            sb.append( "Node(" );
+        }
+        
+        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 ( K key : keys )
+            {
+                if ( isFirst )
+                {
+                    isFirst = false;
+                }
+                else
+                {
+                    sb.append( ", " );
+                }
+
+                sb.append( "<" );
+                sb.append( key );
+                sb.append( ">" );
+            }
+        }
+
+        sb.append( "]\n" );
+        return sb.toString();
+    }
+}

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

Added: directory/apacheds/trunk/jdbm2/src/main/java/jdbm/btree/package.html
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm2/src/main/java/jdbm/btree/package.html?rev=1239581&view=auto
==============================================================================
--- directory/apacheds/trunk/jdbm2/src/main/java/jdbm/btree/package.html (added)
+++ directory/apacheds/trunk/jdbm2/src/main/java/jdbm/btree/package.html Thu Feb  2 12:38:39 2012
@@ -0,0 +1,12 @@
+<!-- $Id: package.html,v 1.1 2001/05/19 16:01:32 boisvert Exp $ -->
+<html>
+  <body>
+    <p>B+Tree (scalable persistent tree) data structure implementation.</p>
+
+    <dl>
+      <dt><b>Version: </b></dt><dd>$Revision: 1.1 $ $Date: 2001/05/19 16:01:32 $</dd>
+      <dt><b>Author: </b></dt><dd><a href="mailto:boisvert@intalio.com">Alex Boisvert</a></dd>
+    </dl>
+
+  </body>
+</html>

Added: directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/ActionContext.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/ActionContext.java?rev=1239581&view=auto
==============================================================================
--- directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/ActionContext.java (added)
+++ directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/ActionContext.java Thu Feb  2 12:38:39 2012
@@ -0,0 +1,98 @@
+/*
+ *  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. 
+ *  
+ */
+package jdbm.helper;
+
+/**
+ * Used to store Action specific context.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class ActionContext
+{
+    /** track whether action is read only */ 
+    boolean readOnly;
+    
+    /** Version associated with the context */
+    ActionVersioning.Version version;
+    
+    /** Who started the action. Usefule for debugging */
+    String whoStarted;
+    
+    public void beginAction( boolean readOnly, ActionVersioning.Version version, String whoStarted )
+    {
+        this.readOnly = readOnly;
+        this.version = version;
+        this.whoStarted = whoStarted;
+    }
+    
+    
+    public void endAction()
+    {
+        if ( version == null )
+        {
+            throw new IllegalStateException( "Unexpected action state during endAction: " + this );
+        }
+        
+        version = null;
+    }
+    
+    
+    public boolean isReadOnlyAction()
+    {
+        return ( readOnly && ( version != null ) );
+    }
+    
+    
+    public boolean isWriteAction()
+    {
+        return ( !readOnly && ( version != null ) );
+    }
+    
+    
+    public boolean isActive()
+    {
+        return ( version != null );
+    }
+    
+    
+    public ActionVersioning.Version getVersion()
+    {
+        return version;
+    }
+    
+    
+    public String getWhoStarted()
+    {
+        return whoStarted;
+    }
+    
+    @Override
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+        sb.append( "ActionContext: " );
+        sb.append( "(readOnly: " ).append( readOnly );
+        sb.append( ", version: " ).append( version );
+        sb.append( ", whoStarted: " ).append( whoStarted );
+        sb.append( ")\n" );
+        
+        return sb.toString();
+    }
+}



Mime
View raw message