Mailing-List: contact commits-help@directory.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@directory.apache.org
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r1435064 [2/7] - in /directory/jdbm/trunk/jdbm1: ./ 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/main/...
Date: Fri, 18 Jan 2013 10:10:57 -0000
To: commits@directory.apache.org
From: elecharny@apache.org
Message-Id: <20130118101102.75F7423889F7@eris.apache.org>

Added: directory/jdbm/trunk/jdbm1/src/main/java/jdbm/btree/BPage.java
URL: http://svn.apache.org/viewvc/directory/jdbm/trunk/jdbm1/src/main/java/jdbm/btree/BPage.java?rev=1435064&view=auto
==============================================================================
--- directory/jdbm/trunk/jdbm1/src/main/java/jdbm/btree/BPage.java (added)
+++ directory/jdbm/trunk/jdbm1/src/main/java/jdbm/btree/BPage.java Fri Jan 18 10:10:55 2013
@@ -0,0 +1,1500 @@
+/**
+ * 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 jdbm.I18n;
+import jdbm.helper.Serializer;
+import jdbm.helper.Tuple;
+import jdbm.helper.TupleBrowser;
+
+
+/**
+ * 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;
+
+
+    /**
+     * No-argument constructor used by serialization.
+     */
+    public BPage()
+    {
+        // empty
+    }
+
+
+    /**
+     * Root page overflow constructor
+     */
+    @SuppressWarnings("unchecked")
+    BPage( BTree 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 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 );
+    }
+
+
+    /**
+     * 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
+     * @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 ) 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 );
+    }
+
+
+    /**
+     * Find first entry and return a browser positioned before it.
+     *
+     * @return TupleBrowser positionned just before the first entry.
+     */
+    TupleBrowser<K, V> findFirst() throws IOException
+    {
+        if ( isLeaf )
+        {
+            return new Browser( this, first );
+        }
+        else
+        {
+            BPage<K, V> child = childBPage( first );
+
+            return child.findFirst();
+        }
+    }
+
+
+    /**
+     * 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;
+
+        if ( height == 0 )
+        {
+            result = new InsertResult<K, V>();
+
+            // 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 )
+                {
+                    values[index] = value;
+                    btree.recordManager.update( recordId, this, 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.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
+            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
+            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 ( !isFull() )
+        {
+            if ( height == 0 )
+            {
+                insertEntry( this, index - 1, key, value );
+            }
+            else
+            {
+                insertChild( this, index - 1, key, overflow );
+            }
+
+            btree.recordManager.update( recordId, this, 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, 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( this, 0, newPage, half, index );
+                setEntry( newPage, half + index, key, value );
+                copyEntries( this, index, newPage, half + index + 1, half - index - 1 );
+            }
+            else
+            {
+                copyChildren( this, 0, newPage, half, index );
+                setChild( newPage, half + index, key, overflow );
+                copyChildren( this, 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( this, 0, newPage, half, half );
+                copyEntries( this, half, this, half - 1, index - half );
+                setEntry( this, index - 1, key, value );
+            }
+            else
+            {
+                copyChildren( this, 0, newPage, half, half );
+                copyChildren( this, half, this, half - 1, index - half );
+                setChild( this, index - 1, key, overflow );
+            }
+        }
+
+        first = half - 1;
+
+        // nullify lower half of entries
+        for ( int i = 0; i < first; i++ )
+        {
+            if ( height == 0 )
+            {
+                setEntry( this, i, null, null );
+            }
+            else
+            {
+                setChild( this, i, null, -1 );
+            }
+        }
+
+        if ( isLeaf )
+        {
+            // link newly created BPage
+            newPage.previous = previous;
+            newPage.next = recordId;
+
+            if ( previous != 0 )
+            {
+                BPage<K, V> previousBPage = loadBPage( previous );
+                previousBPage.next = newPage.recordId;
+                btree.recordManager.update( previous, previousBPage, this );
+            }
+
+            previous = newPage.recordId;
+        }
+
+        btree.recordManager.update( recordId, this, 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<V> remove( int height, K key ) throws IOException
+    {
+        RemoveResult<V> result;
+
+        int half = btree.pageSize / 2;
+        int index = findChildren( key );
+        boolean keyExists = index < 0;
+
+        if ( index < 0 )
+        {
+            index = -( index + 1 );
+        }
+
+        height -= 1;
+
+        if ( height == 0 )
+        {
+            // remove leaf entry
+            if ( !keyExists )
+            {
+                throw new IllegalArgumentException( I18n.err( I18n.ERR_514, key ) );
+            }
+
+            result = new RemoveResult<V>();
+            result.value = values[index];
+            removeEntry( this, index );
+
+            // update this BPage
+            btree.recordManager.update( recordId, this, this );
+        }
+        else
+        {
+            // recurse into Btree to remove entry on a children page
+            BPage<K, V> child = childBPage( index );
+            result = child.remove( height, key );
+
+            // update children
+            keys[index] = child.getLargestKey();
+            btree.recordManager.update( recordId, this, this );
+
+            if ( result.underflow )
+            {
+                // underflow occured
+                if ( child.first != half + 1 )
+                {
+                    throw new IllegalStateException( I18n.err( I18n.ERR_513, "1" ) );
+                }
+
+                if ( index < children.length - 1 )
+                {
+                    // exists greater brother page
+                    BPage<K, V> brother = childBPage( index + 1 );
+                    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
+                        keys[index] = child.getLargestKey();
+
+                        // no change in previous/next BPage
+
+                        // update BPages
+                        btree.recordManager.update( recordId, this, 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 ( isLeaf )
+                        {
+                            copyEntries( this, first, this, first + 1, index - first );
+                            setEntry( this, first, null, null );
+                        }
+                        else
+                        {
+                            copyChildren( this, first, this, first + 1, index - first );
+                            setChild( this, first, null, -1 );
+                        }
+
+                        first += 1;
+                        btree.recordManager.update( recordId, this, this );
+
+                        // re-link previous and next BPages
+                        if ( child.previous != 0 )
+                        {
+                            BPage<K, V> prev = loadBPage( child.previous );
+                            prev.next = child.next;
+                            btree.recordManager.update( prev.recordId, prev, this );
+                        }
+
+                        if ( child.next != 0 )
+                        {
+                            BPage<K, V> next = loadBPage( child.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 = childBPage( index - 1 );
+                    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
+                        keys[index - 1] = brother.getLargestKey();
+
+                        // no change in previous/next BPage
+
+                        // update BPages
+                        btree.recordManager.update( recordId, this, 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 ( isLeaf )
+                        {
+                            copyEntries( this, first, this, first + 1, index - 1 - first );
+                            setEntry( this, first, null, null );
+                        }
+                        else
+                        {
+                            copyChildren( this, first, this, first + 1, index - 1 - first );
+                            setChild( this, first, null, -1 );
+                        }
+
+                        first += 1;
+                        btree.recordManager.update( recordId, this, this );
+
+                        // re-link previous and next BPages
+                        if ( brother.previous != 0 )
+                        {
+                            BPage<K, V> prev = loadBPage( brother.previous );
+                            prev.next = brother.next;
+                            btree.recordManager.update( prev.recordId, prev, this );
+                        }
+
+                        if ( brother.next != 0 )
+                        {
+                            BPage<K, V> next = loadBPage( brother.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 = first > half;
+
+        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 )
+    {
+        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 )
+    {
+        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 )
+    {
+        String prefix = "";
+
+        for ( int i = 0; i < height; i++ )
+        {
+            prefix += "    ";
+        }
+
+        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;
+    }
+
+    /** 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<V>
+    {
+        /**
+         * Set to true if underlying pages underflowed
+         */
+        boolean underflow;
+
+        /**
+         * Removed entry value
+         */
+        V value;
+    }
+
+    /** PRIVATE INNER CLASS
+     * Browser to traverse leaf BPages.
+     */
+    class Browser extends TupleBrowser<K, V>
+    {
+        /** Current page. */
+        private BPage<K, V> page;
+
+        /**
+         * 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 index Position of the next tuple to return.
+         */
+        Browser( BPage<K, V> page, int index )
+        {
+            this.page = page;
+            this.index = index;
+        }
+
+
+        /**
+         * 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
+        {
+            // 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++;
+
+            return true;
+        }
+
+
+        public boolean getPrevious( Tuple<K, V> tuple ) throws IOException
+        {
+            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] );
+
+            return true;
+        }
+    }
+
+
+    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;
+            //int index = 0;
+
+            for ( K key : keys )
+            {
+                if ( isFirst )
+                {
+                    isFirst = false;
+                }
+                else
+                {
+                    sb.append( ", " );
+                }
+
+                sb.append( "<" );
+                sb.append( key );
+                //sb.append( "/" );
+                //sb.append( values[index] );
+                sb.append( ">" );
+            }
+        }
+
+        sb.append( "]\n" );
+        return sb.toString();
+    }
+}

Added: directory/jdbm/trunk/jdbm1/src/main/java/jdbm/btree/BTree.java
URL: http://svn.apache.org/viewvc/directory/jdbm/trunk/jdbm1/src/main/java/jdbm/btree/BTree.java?rev=1435064&view=auto
==============================================================================
--- directory/jdbm/trunk/jdbm1/src/main/java/jdbm/btree/BTree.java (added)
+++ directory/jdbm/trunk/jdbm1/src/main/java/jdbm/btree/BTree.java Fri Jan 18 10:10:55 2013
@@ -0,0 +1,668 @@
+/**
+ * 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 jdbm.I18n;
+import jdbm.RecordManager;
+import jdbm.helper.Serializer;
+import jdbm.helper.Tuple;
+import jdbm.helper.TupleBrowser;
+
+
+/**
+ * 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
+ * TupleBrowser obtained from the browse() methods.
+ * <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. */
+    private 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.
+     */
+    private int bTreeHeight;
+
+    /** Record id of the root BPage */
+    private transient long rootId;
+
+    /** Number of entries in each BPage. */
+    protected int pageSize;
+
+    /** Total number of entries in the BTree */
+    protected AtomicInteger nbEntries;
+
+    /** Serializer used for BPages of this tree */
+    private transient BPage<K, V> bpageSerializer;
+
+
+    /**
+     * 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.recordId = recordManager.insert( this );
+    }
+
+
+    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 = ( BTree<K, V> ) recman.fetch( recid );
+        btree.recordId = recid;
+        btree.recordManager = recman;
+        btree.bpageSerializer = new BPage<K, V>();
+        btree.bpageSerializer.btree = btree;
+
+        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 synchronized 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 ) );
+        }
+
+        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 );
+
+            return null;
+        }
+        else
+        {
+            BPage.InsertResult<K, V> insert = rootPage.insert( bTreeHeight, key, value, replace );
+            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;
+            }
+
+            if ( insert.existing == null )
+            {
+                nbEntries.getAndIncrement();
+                dirty = true;
+            }
+
+            if ( dirty )
+            {
+                recordManager.update( recordId, this );
+            }
+
+            // insert might have returned an existing value
+            return insert.existing;
+        }
+    }
+
+
+    /**
+     * 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 synchronized V remove( K key ) throws IOException
+    {
+        if ( key == null )
+        {
+            throw new IllegalArgumentException( I18n.err( I18n.ERR_523 ) );
+        }
+
+        BPage<K, V> rootPage = getRoot();
+
+        if ( rootPage == null )
+        {
+            return null;
+        }
+
+        boolean dirty = false;
+        BPage.RemoveResult<V> remove = rootPage.remove( bTreeHeight, key );
+
+        if ( remove.underflow && rootPage.isEmpty() )
+        {
+            bTreeHeight -= 1;
+            dirty = true;
+
+            recordManager.delete( rootId );
+
+            if ( bTreeHeight == 0 )
+            {
+                rootId = 0;
+            }
+            else
+            {
+                rootId = rootPage.childBPage( pageSize - 1 ).getRecordId();
+            }
+        }
+
+        if ( remove.value != null )
+        {
+            nbEntries.getAndDecrement();
+            dirty = true;
+        }
+
+        if ( dirty )
+        {
+            recordManager.update( recordId, this );
+        }
+
+        return remove.value;
+    }
+
+
+    /**
+     * Find the value associated with the given key.
+     *
+     * @param key Lookup key.
+     * @return Value associated with the key, or null if not found.
+     */
+    public synchronized V find( K key ) throws IOException
+    {
+        if ( key == null )
+        {
+            throw new IllegalArgumentException( I18n.err( I18n.ERR_523 ) );
+        }
+
+        BPage<K, V> rootPage = getRoot();
+
+        if ( rootPage == null )
+        {
+            return null;
+        }
+
+        Tuple<K, V> tuple = new Tuple<K, V>( null, null );
+        TupleBrowser<K, V> browser = rootPage.find( bTreeHeight, 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;
+        }
+    }
+
+
+    /**
+     * 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 synchronized Tuple<K, V> findGreaterOrEqual( K key ) throws IOException
+    {
+        Tuple<K, V> tuple;
+        TupleBrowser<K, V> browser;
+
+        if ( key == null )
+        {
+            // there can't be a key greater than or equal to "null"
+            // because null is considered an infinite key.
+            return null;
+        }
+
+        tuple = new Tuple<K, V>( null, null );
+        browser = browse( key );
+
+        if ( browser.getNext( tuple ) )
+        {
+            return tuple;
+        }
+        else
+        {
+            return null;
+        }
+    }
+
+
+    /**
+     * 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 synchronized TupleBrowser<K, V> browse() throws IOException
+    {
+        BPage<K, V> rootPage = getRoot();
+
+        if ( rootPage == null )
+        {
+            return new EmptyBrowser()
+            {
+            };
+        }
+
+        TupleBrowser<K, V> browser = rootPage.findFirst();
+
+        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 synchronized TupleBrowser<K, V> browse( K key ) throws IOException
+    {
+        BPage<K, V> rootPage = getRoot();
+
+        if ( rootPage == null )
+        {
+            return new EmptyBrowser()
+            {
+            };
+        }
+
+        TupleBrowser<K, V> browser = rootPage.find( bTreeHeight, key );
+
+        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.
+     */
+    private BPage<K, V> getRoot() throws IOException
+    {
+        if ( rootId == 0 )
+        {
+            return null;
+        }
+
+        BPage<K, V> root = ( BPage<K, V> ) recordManager.fetch( rootId, bpageSerializer );
+        root.setRecordId( rootId );
+        root.btree = this;
+
+        return root;
+    }
+
+
+    /**
+     * 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;
+    }
+
+
+    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();
+    }
+}

Added: directory/jdbm/trunk/jdbm1/src/main/java/jdbm/btree/package.html
URL: http://svn.apache.org/viewvc/directory/jdbm/trunk/jdbm1/src/main/java/jdbm/btree/package.html?rev=1435064&view=auto
==============================================================================
--- directory/jdbm/trunk/jdbm1/src/main/java/jdbm/btree/package.html (added)
+++ directory/jdbm/trunk/jdbm1/src/main/java/jdbm/btree/package.html Fri Jan 18 10:10:55 2013
@@ -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/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/ByteArrayComparator.java
URL: http://svn.apache.org/viewvc/directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/ByteArrayComparator.java?rev=1435064&view=auto
==============================================================================
--- directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/ByteArrayComparator.java (added)
+++ directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/ByteArrayComparator.java Fri Jan 18 10:10:55 2013
@@ -0,0 +1,157 @@
+/**
+ * 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.helper;
+
+
+import java.io.Serializable;
+import java.util.Comparator;
+
+import jdbm.I18n;
+
+
+/**
+ * Comparator for byte arrays.
+ *
+ * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
+ */
+public final class ByteArrayComparator
+    implements Comparator<byte[]>, 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( byte[] obj1, byte[] obj2 )
+    {
+        if ( obj1 == null )
+        {
+            throw new IllegalArgumentException( I18n.err( I18n.ERR_525 ) );
+        }
+
+        if ( obj2 == null )
+        {
+            throw new IllegalArgumentException( I18n.err( I18n.ERR_526 ) );
+        }
+
+        return compareByteArray( obj1, obj2 );
+    }
+
+
+    /**
+     * Compare two byte arrays.
+     */
+    public static int compareByteArray( byte[] thisKey, byte[] otherKey )
+    {
+        int len = Math.min( thisKey.length, otherKey.length );
+
+        // compare the byte arrays
+        for ( int i = 0; i < len; i++ )
+        {
+            if ( thisKey[i] >= 0 )
+            {
+                if ( otherKey[i] >= 0 )
+                {
+                    // both positive
+                    if ( thisKey[i] < otherKey[i] )
+                    {
+                        return -1;
+                    }
+                    else if ( thisKey[i] > otherKey[i] )
+                    {
+                        return 1;
+                    }
+                }
+                else
+                {
+                    // otherKey is negative => greater (because MSB is 1)
+                    return -1;
+                }
+            }
+            else
+            {
+                if ( otherKey[i] >= 0 )
+                {
+                    // thisKey is negative => greater (because MSB is 1)
+                    return 1;
+                }
+                else
+                {
+                    // both negative
+                    if ( thisKey[i] < otherKey[i] )
+                    {
+                        return -1;
+                    }
+                    else if ( thisKey[i] > otherKey[i] )
+                    {
+                        return 1;
+                    }
+                }
+            }
+        }
+        if ( thisKey.length == otherKey.length )
+        {
+            return 0;
+        }
+        if ( thisKey.length < otherKey.length )
+        {
+            return -1;
+        }
+        return 1;
+    }
+
+}

Added: directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/ByteArraySerializer.java
URL: http://svn.apache.org/viewvc/directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/ByteArraySerializer.java?rev=1435064&view=auto
==============================================================================
--- directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/ByteArraySerializer.java (added)
+++ directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/ByteArraySerializer.java Fri Jan 18 10:10:55 2013
@@ -0,0 +1,101 @@
+/**
+ * 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.helper;
+
+import java.io.IOException;
+
+
+/**
+ * Serializer for byte arrays -- simple returns the byte array itself.  No actual
+ * serialization is performed.
+ *
+ * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
+ */
+public final class ByteArraySerializer
+    implements Serializer
+{
+
+    /**
+     * Version id for serialization.
+     */
+    final static long serialVersionUID = 1L;
+
+
+    /**
+     * Static instance.
+     */
+    public static final ByteArraySerializer INSTANCE = new ByteArraySerializer();
+    
+    
+    /** 
+     * 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
+    {
+        return (byte[]) obj;
+    }
+
+    
+    /**
+     * 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
+    {
+        return serialized;
+    }    
+
+}

Added: directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/CacheEvictionException.java
URL: http://svn.apache.org/viewvc/directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/CacheEvictionException.java?rev=1435064&view=auto
==============================================================================
--- directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/CacheEvictionException.java (added)
+++ directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/CacheEvictionException.java Fri Jan 18 10:10:55 2013
@@ -0,0 +1,74 @@
+/**
+ * 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 2000 (C) Cees de Groot. All Rights Reserved.
+ * Contributions are Copyright (C) 2000 by their associated contributors.
+ *
+ * $Id: CacheEvictionException.java,v 1.4 2003/10/21 15:43:20 boisvert Exp $
+ */
+
+package jdbm.helper;
+
+/**
+ *  Exception that occurs during eviction of an object in the cache.
+ *
+ *  @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
+ */
+public class CacheEvictionException
+    extends Exception
+{
+
+    /**
+     * Nested exception -- the original exception that occured, if any.
+     */
+    protected Exception _nested;
+
+
+    public CacheEvictionException( Exception nested )
+    {
+        _nested = nested;
+    }
+
+    public Exception getNestedException()
+    {
+        return _nested;
+    }
+}

Added: directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/CachePolicy.java
URL: http://svn.apache.org/viewvc/directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/CachePolicy.java?rev=1435064&view=auto
==============================================================================
--- directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/CachePolicy.java (added)
+++ directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/CachePolicy.java Fri Jan 18 10:10:55 2013
@@ -0,0 +1,139 @@
+/**
+ * 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 2000 (C) Cees de Groot. All Rights Reserved.
+ * Contributions are Copyright (C) 2000 by their associated contributors.
+ *
+ * $Id: CachePolicy.java,v 1.5 2003/11/01 13:25:02 dranatunga Exp $
+ */
+package jdbm.helper;
+
+
+import java.util.Enumeration;
+
+
+/**
+ *  CachePolicity is an abstraction for different cache policies.
+ *  (ie. MRU, time-based, soft-refs, ...)
+ *
+ * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
+ * @author <a href="mailto:dranatunga@users.sourceforge.net">Dilum Ranatunga</a>
+ */
+public interface CachePolicy<K,V>
+{
+    /**
+     * Place an object in the cache. If the cache does not currently contain
+     * an object for the key specified, this mapping is added. If an object
+     * currently exists under the specified key, the current object is
+     * replaced with the new object.
+     * <p>
+     * If the changes to the cache cause the eviction of any objects
+     * <strong>stored under other key(s)</strong>, events corresponding to
+     * the evictions are fired for each object. If an event listener is
+     * unable to handle the eviction, and throws a cache eviction exception,
+     * that exception is propagated to the caller. If such an exception is
+     * thrown, the cache itself should be left as it was before the
+     * <code>put()</code> operation was invoked: the the object whose
+     * eviction failed is still in the cache, and the new insertion or
+     * modification is reverted.
+     *
+     * @param key key for the cached object
+     * @param value the cached object
+     * @throws CacheEvictionException propagated if, while evicting objects
+     *     to make room for new object, an eviction listener encountered
+     *     this problem.
+     */
+    public void put( K key, V value ) throws CacheEvictionException;
+
+
+    /**
+     * Obtain the object stored under the key specified.
+     *
+     * @param key key the object was cached under
+     * @return the object if it is still in the cache, null otherwise.
+     */
+    public V get( K key );
+
+
+    /**
+     * Remove the object stored under the key specified. Note that since
+     * eviction notices are only fired when objects under <strong>different
+     * keys</strong> are evicted, no event is fired for any object stored
+     * under this key (see {@link #put(Object, Object) put( )}).
+     *
+     * @param key key the object was stored in the cache under.
+     */
+    public void remove( K key );
+
+
+    /**
+     * Remove all objects from the cache. Consistent with
+     * {@link #remove(Object) remove( )}, no eviction notices are fired.
+     */
+    public void removeAll();
+
+
+    /**
+     * Enumerate through the objects currently in the cache.
+     */
+    public Enumeration<V> elements();
+
+
+    /**
+     * Add a listener to this cache policy.
+     * <p>
+     * If this cache policy already contains a listener that is equal to
+     * the one being added, this call has no effect.
+     *
+     * @param listener the (non-null) listener to add to this policy
+     * @throws IllegalArgumentException if listener is null.
+     */
+    public void addListener( CachePolicyListener<V> listener ) throws IllegalArgumentException;
+
+    
+    /**
+     * Remove a listener from this cache policy. The listener is found
+     * using object equality, not identity.
+     *
+     * @param listener the listener to remove from this policy
+     */
+    public void removeListener( CachePolicyListener<V> listener );
+}

Added: directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/CachePolicyListener.java
URL: http://svn.apache.org/viewvc/directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/CachePolicyListener.java?rev=1435064&view=auto
==============================================================================
--- directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/CachePolicyListener.java (added)
+++ directory/jdbm/trunk/jdbm1/src/main/java/jdbm/helper/CachePolicyListener.java Fri Jan 18 10:10:55 2013
@@ -0,0 +1,75 @@
+/**
+ * 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 2000 (C) Cees de Groot. All Rights Reserved.
+ * Contributions are Copyright (C) 2000 by their associated contributors.
+ *
+ * $Id: CachePolicyListener.java,v 1.3 2003/11/01 13:25:41 dranatunga Exp $
+ */
+
+package jdbm.helper;
+
+/**
+ * Callback interface between {@link CachePolicy} and a Cache implementation
+ * to notify about cached object eviction.
+ * <p>
+ * Note that <code>CachePolicy</code> implementations typically use
+ * <em>object equality</em> when removing listeners, so concrete
+ * implementations of this interface should also pay attention to
+ * their {@link Object#equals(Object)} and {@link Object#hashCode()}
+ * methods.
+ *
+ * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
+ */
+public interface CachePolicyListener<T> 
+{
+    /**
+     * Notification that the cache this listener is attached to is evicting
+     * the object indicated.
+     *
+     * @param obj object being evicted from cache
+     * @throws CacheEvictionException if this listener encountered problems
+     *     while preparing for the specified object's eviction. For example,
+     *     a listener may try to persist the object to disk, and encounter
+     *     an <code>IOException</code>.
+     */
+    public void cacheObjectEvicted( T obj ) throws CacheEvictionException;
+}