directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r652410 [2/14] - in /directory: apacheds/branches/bigbang/ apacheds/branches/bigbang/apacheds-jdbm/ apacheds/branches/bigbang/apacheds-jdbm/src/ apacheds/branches/bigbang/apacheds-jdbm/src/etc/ apacheds/branches/bigbang/apacheds-jdbm/src/ex...
Date Thu, 01 May 2008 00:06:46 GMT
Added: directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/btree/BPage.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/btree/BPage.java?rev=652410&view=auto
==============================================================================
--- directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/btree/BPage.java (added)
+++ directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/btree/BPage.java Wed Apr 30 17:06:41 2008
@@ -0,0 +1,1197 @@
+/**
+ * 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 jdbm.helper.Serializer;
+import jdbm.helper.Tuple;
+import jdbm.helper.TupleBrowser;
+
+import java.io.IOException;
+import java.io.ByteArrayOutputStream;
+import java.io.ByteArrayInputStream;
+import java.io.ObjectInput;
+import java.io.ObjectOutput;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+
+/**
+ * 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>
+ * @version $Id: BPage.java,v 1.6 2003/09/21 15:46:59 boisvert Exp $
+ */
+public final class BPage
+    implements Serializer
+{
+
+    private static final boolean DEBUG = false;
+
+
+    /**
+     * Version id for serialization.
+     */
+    final static long serialVersionUID = 1L;
+
+
+    /**
+     * Parent B+Tree.
+     */
+    transient BTree _btree;
+
+
+    /**
+     * This BPage's record ID in the PageManager.
+     */
+    protected transient long _recid;
+
+
+    /**
+     * Flag indicating if this is a leaf BPage.
+     */
+    protected boolean _isLeaf;
+
+
+    /**
+     * Keys of children nodes
+     */
+    protected Object[] _keys;
+
+
+    /**
+     * Values associated with keys.  (Only valid if leaf BPage)
+     */
+    protected Object[] _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
+     */
+    BPage( BTree btree, BPage root, BPage overflow )
+        throws IOException
+    {
+        _btree = btree;
+
+        _isLeaf = false;
+
+        _first = _btree._pageSize-2;
+
+        _keys = 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._recid;
+        _children[ _btree._pageSize-1 ] = root._recid;
+
+        _recid = _btree._recman.insert( this, this );
+    }
+
+
+    /**
+     * Root page (first insert) constructor.
+     */
+    BPage( BTree btree, Object key, Object value )
+        throws IOException
+    {
+        _btree = btree;
+
+        _isLeaf = true;
+
+        _first = btree._pageSize-2;
+
+        _keys = new Object[ _btree._pageSize ];
+        _keys[ _btree._pageSize-2 ] = key;
+        _keys[ _btree._pageSize-1 ] = null;  // I am the root BPage for now
+
+        _values = new Object[ _btree._pageSize ];
+        _values[ _btree._pageSize-2 ] = value;
+        _values[ _btree._pageSize-1 ] = null;  // I am the root BPage for now
+
+        _recid = _btree._recman.insert( this, this );
+    }
+
+
+    /**
+     * Overflow page constructor.  Creates an empty BPage.
+     */
+    BPage( BTree btree, boolean isLeaf )
+        throws IOException
+    {
+        _btree = btree;
+
+        _isLeaf = isLeaf;
+
+        // page will initially be half-full
+        _first = _btree._pageSize/2;
+
+        _keys = new Object[ _btree._pageSize ];
+        if ( isLeaf ) {
+            _values = new Object[ _btree._pageSize ];
+        } else {
+            _children = new long[ _btree._pageSize ];
+        }
+
+        _recid = _btree._recman.insert( this, this );
+    }
+
+
+    /**
+     * Get largest key under this BPage.  Null is considered to be the
+     * greatest possible key.
+     */
+    Object getLargestKey()
+    {
+        return _keys[ _btree._pageSize-1 ];
+    }
+
+
+    /**
+     * 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 find( int height, Object key )
+        throws IOException
+    {
+        int index = findChildren( key );
+
+        /*
+        if ( DEBUG ) {
+            System.out.println( "BPage.find() current: " + this
+                                + " height: " + height);
+        }
+        */
+
+        height -= 1;
+
+        if ( height == 0 ) {
+            // leaf BPage
+            return new Browser( this, index );
+        } else {
+            // non-leaf BPage
+            BPage child = childBPage( index );
+            return child.find( height, key );
+        }
+    }
+
+
+    /**
+     * Find first entry and return a browser positioned before it.
+     *
+     * @return TupleBrowser positionned just before the first entry.
+     */
+    TupleBrowser findFirst()
+        throws IOException
+    {
+        if ( _isLeaf ) {
+            return new Browser( this, _first );
+        } else {
+            BPage 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 insert( int height, Object key, Object value, boolean replace )
+        throws IOException
+    {
+        InsertResult  result;
+        long          overflow;
+
+        int index = findChildren( key );
+
+        height -= 1;
+        if ( height == 0 )  {
+
+            result = new InsertResult();
+
+            // inserting on a leaf BPage
+            overflow = -1;
+            if ( DEBUG ) {
+                System.out.println( "Bpage.insert() Insert on leaf Bpage key=" + key
+                                    + " value=" + value + " index="+index);
+            }
+            if ( compare( key, _keys[ index ] ) == 0 ) {
+                // key already exists
+                if ( DEBUG ) {
+                    System.out.println( "Bpage.insert() Key already exists." ) ;
+                }
+                result._existing = _values[ index ];
+                if ( replace ) {
+                    _values [ index ] = value;
+                    _btree._recman.update( _recid, this, this );
+                }
+                // return the existing key
+                return result;
+            }
+        } else {
+            // non-leaf BPage
+            BPage 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._recid );
+            }
+            key = result._overflow.getLargestKey();
+            overflow = result._overflow._recid;
+
+            // 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._recman.update( _recid, this, this );
+            return result;
+        }
+
+        // page is full, we must divide the page
+        int half = _btree._pageSize >> 1;
+        BPage newPage = new BPage( _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 = _recid;
+            if ( _previous != 0 ) {
+                BPage previous = loadBPage( _previous );
+                previous._next = newPage._recid;
+                _btree._recman.update( _previous, previous, this );
+            }
+            _previous = newPage._recid;
+        }
+
+        _btree._recman.update( _recid, this, this );
+        _btree._recman.update( newPage._recid, 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 remove( int height, Object key )
+        throws IOException
+    {
+        RemoveResult result;
+
+        int half = _btree._pageSize / 2;
+        int index = findChildren( key );
+
+        height -= 1;
+        if ( height == 0 ) {
+            // remove leaf entry
+            if ( compare( _keys[ index ], key ) != 0 ) {
+                throw new IllegalArgumentException( "Key not found: " + key );
+            }
+            result = new RemoveResult();
+            result._value = _values[ index ];
+            removeEntry( this, index );
+
+            // update this BPage
+            _btree._recman.update( _recid, this, this );
+
+        } else {
+            // recurse into Btree to remove entry on a children page
+            BPage child = childBPage( index );
+            result = child.remove( height, key );
+
+            // update children
+            _keys[ index ] = child.getLargestKey();
+            _btree._recman.update( _recid, this, this );
+
+            if ( result._underflow ) {
+                // underflow occured
+                if ( child._first != half+1 ) {
+                    throw new IllegalStateException( "Error during underflow [1]" );
+                }
+                if ( index < _children.length-1 ) {
+                    // exists greater brother page
+                    BPage 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._recman.update( _recid, this, this );
+                        _btree._recman.update( brother._recid, brother, this );
+                        _btree._recman.update( child._recid, child, this );
+
+                    } else {
+                        // move all entries from page "child" to "brother"
+                        if ( brother._first != half ) {
+                            throw new IllegalStateException( "Error during underflow [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._recman.update( brother._recid, 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._recman.update( _recid, this, this );
+
+                        // re-link previous and next BPages
+                        if ( child._previous != 0 ) {
+                            BPage prev = loadBPage( child._previous );
+                            prev._next = child._next;
+                            _btree._recman.update( prev._recid, prev, this );
+                        }
+                        if ( child._next != 0 ) {
+                            BPage next = loadBPage( child._next );
+                            next._previous = child._previous;
+                            _btree._recman.update( next._recid, next, this );
+                        }
+
+                        // delete "child" BPage
+                        _btree._recman.delete( child._recid );
+                    }
+                } else {
+                    // page "brother" is before "child"
+                    BPage 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._recman.update( _recid, this, this );
+                        _btree._recman.update( brother._recid, brother, this );
+                        _btree._recman.update( child._recid, child, this );
+
+                    } else {
+                        // move all entries from page "brother" to "child"
+                        if ( brother._first != half ) {
+                            throw new IllegalStateException( "Error during underflow [3]" );
+                        }
+
+                        child._first = 1;
+                        if ( child._isLeaf ) {
+                            copyEntries( brother, half, child, 1, half );
+                        } else {
+                            copyChildren( brother, half, child, 1, half );
+                        }
+                        _btree._recman.update( child._recid, 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._recman.update( _recid, this, this );
+
+                        // re-link previous and next BPages
+                        if ( brother._previous != 0 ) {
+                            BPage prev = loadBPage( brother._previous );
+                            prev._next = brother._next;
+                            _btree._recman.update( prev._recid, prev, this );
+                        }
+                        if ( brother._next != 0 ) {
+                            BPage next = loadBPage( brother._next );
+                            next._previous = brother._previous;
+                            _btree._recman.update( next._recid, next, this );
+                        }
+
+                        // delete "brother" BPage
+                        _btree._recman.delete( brother._recid );
+                    }
+                }
+            }
+        }
+
+        // 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.
+     */
+    private int findChildren( Object key )
+    {
+        int left = _first;
+        int right = _btree._pageSize-1;
+
+        // binary search
+        while ( left < right )  {
+            int middle = ( left + right ) / 2;
+            if ( compare( _keys[ middle ], key ) < 0 ) {
+                left = middle+1;
+            } else {
+                right = middle;
+            }
+        }
+        return right;
+    }
+
+
+    /**
+     * Insert entry at given position.
+     */
+    private static void insertEntry( BPage page, int index,
+                                     Object key, Object value )
+    {
+        Object[] keys = page._keys;
+        Object[] 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 static void insertChild( BPage page, int index,
+                                     Object key, long child )
+    {
+        Object[] 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 static void removeEntry( BPage page, int index )
+    {
+        Object[] keys = page._keys;
+        Object[] 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++;
+    }
+
+
+    /**
+     * Remove child at given position.
+     */
+/*    
+    private static void removeChild( BPage page, int index )
+    {
+        Object[] keys = page._keys;
+        long[] children = page._children;
+        int start = page._first;
+        int count = index-page._first;
+
+        System.arraycopy( keys, start, keys, start+1, count );
+        keys[ start ] = null;
+        System.arraycopy( children, start, children, start+1, count );
+        children[ start ] = (long) -1;
+        page._first++;
+    }
+*/
+    
+    /**
+     * Set the entry at the given index.
+     */
+    private static void setEntry( BPage page, int index, Object key, Object value )
+    {
+        page._keys[ index ] = key;
+        page._values[ index ] = value;
+    }
+
+
+    /**
+     * Set the child BPage recid at the given index.
+     */
+    private static void setChild( BPage page, int index, Object key, long recid )
+    {
+        page._keys[ index ] = key;
+        page._children[ index ] = recid;
+    }
+    
+    
+    /**
+     * Copy entries between two BPages
+     */
+    private static void copyEntries( BPage source, int indexSource,
+                                     BPage 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 static void copyChildren( BPage source, int indexSource,
+                                      BPage 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.
+     */
+    BPage childBPage( int index )
+        throws IOException
+    {
+        return loadBPage( _children[ index ] );
+    }
+
+
+    /**
+     * Load the BPage at the given recid.
+     */
+    private BPage loadBPage( long recid )
+        throws IOException
+    {
+        BPage child = (BPage) _btree._recman.fetch( recid, this );
+        child._recid = recid;
+        child._btree = _btree;
+        return child;
+    }
+
+    
+    private final int compare( Object value1, Object value2 )
+    {
+        if ( value1 == null ) {
+            return 1;
+        }
+        if ( value2 == null ) {
+            return -1;
+        }
+        return _btree._comparator.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 recid=" + _recid);
+        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 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( (byte[]) _keys[ i ], (byte[]) _keys[ i+1 ] ) >= 0 ) {
+                dump( 0 );
+                throw new Error( "BPage not ordered" );
+            }
+        }
+    }
+
+
+    /**
+     * 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 child = childBPage( i );
+                if ( compare( (byte[]) _keys[ i ], child.getLargestKey() ) != 0 ) {
+                    dump( 0 );
+                    child.dump( 0 );
+                    throw new Error( "Invalid child subordinate key" );
+                }
+                child.assertConsistencyRecursive( height );
+            }
+        }
+    }
+
+
+    /**
+     * 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
+    {
+        ByteArrayInputStream  bais;
+        ObjectInputStream     ois;
+        BPage                 bpage;
+
+        bpage = new BPage();
+        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 = new Object[ _btree._pageSize ];
+        try {
+            for ( int i=bpage._first; i<_btree._pageSize; i++ ) {
+                if ( _btree._keySerializer == null ) {
+                    bpage._keys[ i ] = ois.readObject();
+                } else {
+                    serialized = readByteArray( ois );
+                    if ( serialized != null ) {
+                        bpage._keys[ i ] = _btree._keySerializer.deserialize( serialized );
+                    }
+                }
+            }
+        } catch ( ClassNotFoundException except ) {
+            throw new IOException( except.getMessage() );
+        }
+        
+        if ( bpage._isLeaf ) {
+            bpage._values = new Object[ _btree._pageSize ];
+            try {
+                for ( int i=bpage._first; i<_btree._pageSize; i++ ) {
+                    if ( _btree._valueSerializer == null ) {
+                        bpage._values[ i ] = ois.readObject();
+                    } else {
+                        serialized = readByteArray( ois );
+                        if ( serialized != null ) {
+                            bpage._values[ i ] = _btree._valueSerializer.deserialize( serialized );
+                        }
+                    }
+                }
+            } catch ( ClassNotFoundException except ) {
+                throw new IOException( except.getMessage() );
+            }
+        } 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
+     *
+     */
+    public byte[] serialize( Object obj ) 
+        throws IOException
+    {
+        byte[]                 serialized;
+        ByteArrayOutputStream  baos;
+        ObjectOutputStream     oos;
+        BPage                  bpage;
+        byte[]                 data;
+        
+        // note:  It is assumed that BPage instance doing the serialization is the parent
+        // of the BPage object being serialized.
+        
+        bpage = (BPage) 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
+     */
+    static class InsertResult {
+
+        /**
+         * Overflow page.
+         */
+        BPage _overflow;
+
+        /**
+         * Existing value for the insertion key.
+         */
+        Object _existing;
+
+    }
+
+    /** STATIC INNER CLASS
+     *  Result from remove() method call
+     */
+    static class RemoveResult {
+
+        /**
+         * Set to true if underlying pages underflowed
+         */
+        boolean _underflow;
+
+        /**
+         * Removed entry value
+         */
+        Object _value;
+    }
+
+
+    /** PRIVATE INNER CLASS
+     * Browser to traverse leaf BPages.
+     */
+    static class Browser
+        extends TupleBrowser
+    {
+
+        /**
+         * Current page.
+         */
+        private BPage _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 page, int index )
+        {
+            _page = page;
+            _index = index;
+        }
+
+        public boolean getNext( Tuple tuple )
+            throws IOException
+        {
+            if ( _index < _page._btree._pageSize ) {
+                if ( _page._keys[ _index ] == null ) {
+                    // reached end of the tree.
+                    return false;
+                }
+            } 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 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;
+
+        }
+    }
+
+}

Added: directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/btree/BTree.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/btree/BTree.java?rev=652410&view=auto
==============================================================================
--- directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/btree/BTree.java (added)
+++ directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/btree/BTree.java Wed Apr 30 17:06:41 2008
@@ -0,0 +1,609 @@
+/**
+ * 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 jdbm.RecordManager;
+
+import jdbm.helper.Serializer;
+import jdbm.helper.Tuple;
+import jdbm.helper.TupleBrowser;
+
+import java.io.Externalizable;
+import java.io.IOException;
+import java.io.ObjectInput;
+import java.io.ObjectOutput;
+import java.io.Serializable;
+
+import java.util.Comparator;
+
+/**
+ * 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>
+ * @version $Id: BTree.java,v 1.6 2005/06/25 23:12:31 doomdark Exp $
+ */
+public class BTree
+    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 _recman;
+
+
+    /**
+     * This BTree's record ID in the PageManager.
+     */
+    private transient long _recid;
+
+
+    /**
+     * Comparator used to index entries.
+     */
+    protected Comparator _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 _height;
+
+
+    /**
+     * Recid of the root BPage
+     */
+    private transient long _root;
+
+
+    /**
+     * Number of entries in each BPage.
+     */
+    protected int _pageSize;
+
+
+    /**
+     * Total number of entries in the BTree
+     */
+    protected int _entries;
+
+    
+    /**
+     * Serializer used for BPages of this tree
+     */
+    private transient BPage _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 static BTree createInstance( RecordManager recman,
+                                        Comparator comparator )
+        throws IOException
+    {
+        return 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 static BTree createInstance( RecordManager recman,
+                                        Comparator comparator,
+                                        Serializer keySerializer,
+                                        Serializer valueSerializer )
+        throws IOException
+    {
+        return 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 static BTree createInstance( RecordManager recman,
+                                        Comparator comparator,
+                                        Serializer keySerializer,
+                                        Serializer valueSerializer,
+                                        int pageSize )
+        throws IOException
+    {
+        BTree btree;
+
+        if ( recman == null ) {
+            throw new IllegalArgumentException( "Argument 'recman' is null" );
+        }
+
+        if ( comparator == null ) {
+            throw new IllegalArgumentException( "Argument 'comparator' is null" );
+        }
+
+        if ( ! ( comparator instanceof Serializable ) ) {
+            throw new IllegalArgumentException( "Argument 'comparator' must be serializable" );
+        }
+
+        if ( keySerializer != null && ! ( keySerializer instanceof Serializable ) ) {
+            throw new IllegalArgumentException( "Argument 'keySerializer' must be serializable" );
+        }
+
+        if ( valueSerializer != null && ! ( valueSerializer instanceof Serializable ) ) {
+            throw new IllegalArgumentException( "Argument 'valueSerializer' must be serializable" );
+        }
+
+        // make sure there's an even number of entries per BPage
+        if ( ( pageSize & 1 ) != 0 ) {
+            throw new IllegalArgumentException( "Argument 'pageSize' must be even" );
+        }
+
+        btree = new BTree();
+        btree._recman = recman;
+        btree._comparator = comparator;
+        btree._keySerializer = keySerializer;
+        btree._valueSerializer = valueSerializer;
+        btree._pageSize = pageSize;
+        btree._bpageSerializer = new BPage();
+        btree._bpageSerializer._btree = btree;
+        btree._recid = recman.insert( btree );
+        return btree;
+    }
+
+
+    /**
+     * Load a persistent BTree.
+     *
+     * @param recman RecordManager used to store the persistent btree
+     * @param recid Record id of the BTree
+     */
+    public static BTree load( RecordManager recman, long recid )
+        throws IOException
+    {
+        BTree btree = (BTree) recman.fetch( recid );
+        btree._recid = recid;
+        btree._recman = recman;
+        btree._bpageSerializer = new BPage();
+        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( Object key, Object value,
+                                       boolean replace )
+        throws IOException
+    {
+        if ( key == null ) {
+            throw new IllegalArgumentException( "Argument 'key' is null" );
+        }
+        if ( value == null ) {
+            throw new IllegalArgumentException( "Argument 'value' is null" );
+        }
+
+        BPage 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( this, key, value );
+            _root = rootPage._recid;
+            _height = 1;
+            _entries = 1;
+            _recman.update( _recid, this );
+            return null;
+        } else {
+            BPage.InsertResult insert = rootPage.insert( _height, 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( this, rootPage, insert._overflow );
+                _root = rootPage._recid;
+                _height += 1;
+                dirty = true;
+            }
+            if ( insert._existing == null ) {
+                _entries++;
+                dirty = true;
+            }
+            if ( dirty ) {
+                _recman.update( _recid, 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 Object remove( Object key )
+        throws IOException
+    {
+        if ( key == null ) {
+            throw new IllegalArgumentException( "Argument 'key' is null" );
+        }
+
+        BPage rootPage = getRoot();
+        if ( rootPage == null ) {
+            return null;
+        }
+        boolean dirty = false;
+        BPage.RemoveResult remove = rootPage.remove( _height, key );
+        if ( remove._underflow && rootPage.isEmpty() ) {
+            _height -= 1;
+            dirty = true;
+
+            // TODO:  check contract for BPages to be removed from recman.
+            if ( _height == 0 ) {
+                _root = 0;
+            } else {
+                _root = rootPage.childBPage( _pageSize-1 )._recid;
+            }
+        }
+        if ( remove._value != null ) {
+            _entries--;
+            dirty = true;
+        }
+        if ( dirty ) {
+            _recman.update( _recid, 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 Object find( Object key )
+        throws IOException
+    {
+        if ( key == null ) {
+            throw new IllegalArgumentException( "Argument 'key' is null" );
+        }
+        BPage rootPage = getRoot();
+        if ( rootPage == null ) {
+            return null;
+        }
+
+        Tuple tuple = new Tuple( null, null );
+        TupleBrowser browser = rootPage.find( _height, 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 findGreaterOrEqual( Object key )
+        throws IOException
+    {
+        Tuple         tuple;
+        TupleBrowser  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( 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 browse()
+        throws IOException
+    {
+        BPage rootPage = getRoot();
+        if ( rootPage == null ) {
+            return EmptyBrowser.INSTANCE;
+        }
+        TupleBrowser 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 browing results.
+     * </b>
+     *
+     * @param key Key used to position the browser.  If null, the browser
+     *            will be positionned after the last entry of the BTree.
+     *            (Null is considered to be an "infinite" key)
+     * @return Browser positionned just before the given key.
+     */
+    public synchronized TupleBrowser browse( Object key )
+        throws IOException
+    {
+        BPage rootPage = getRoot();
+        if ( rootPage == null ) {
+            return EmptyBrowser.INSTANCE;
+        }
+        TupleBrowser browser = rootPage.find( _height, key );
+        return browser;
+    }
+
+
+    /**
+     * Return the number of entries (size) of the BTree.
+     */
+    public synchronized int size()
+    {
+        return _entries;
+    }
+
+
+    /**
+     * Return the persistent record identifier of the BTree.
+     */
+    public long getRecid()
+    {
+        return _recid;
+    }
+
+
+    /**
+     * Return the root BPage, or null if it doesn't exist.
+     */
+    private BPage getRoot()
+        throws IOException
+    {
+        if ( _root == 0 ) {
+            return null;
+        }
+        BPage root = (BPage) _recman.fetch( _root, _bpageSerializer );
+        root._recid = _root;
+        root._btree = this;
+        return root;
+    }
+
+    /**
+     * Implement Externalizable interface.
+     */
+    public void readExternal( ObjectInput in )
+        throws IOException, ClassNotFoundException
+    {
+        _comparator = (Comparator) in.readObject();
+        _keySerializer = (Serializer) in.readObject();
+        _valueSerializer = (Serializer) in.readObject();
+        _height = in.readInt();
+        _root = in.readLong();
+        _pageSize = in.readInt();
+        _entries = in.readInt();
+    }
+
+
+    /**
+     * Implement Externalizable interface.
+     */
+    public void writeExternal( ObjectOutput out )
+        throws IOException
+    {
+        out.writeObject( _comparator );
+        out.writeObject( _keySerializer );
+        out.writeObject( _valueSerializer );
+        out.writeInt( _height );
+        out.writeLong( _root );
+        out.writeInt( _pageSize );
+        out.writeInt( _entries );
+    }
+
+
+    public void setValueSerializer( Serializer valueSerializer )
+    {
+    	_valueSerializer = valueSerializer;
+    }
+    
+    
+    /*
+    public void assert() throws IOException {
+        BPage root = getRoot();
+        if ( root != null ) {
+            root.assertRecursive( _height );
+        }
+    }
+    */
+
+
+    /*
+    public void dump() throws IOException {
+        BPage root = getRoot();
+        if ( root != null ) {
+            root.dumpRecursive( _height, 0 );
+        }
+    }
+    */
+
+
+    /** PRIVATE INNER CLASS
+     *  Browser returning no element.
+     */
+    static class EmptyBrowser
+        extends TupleBrowser
+    {
+
+        static TupleBrowser INSTANCE = new EmptyBrowser();
+
+        public boolean getNext( Tuple tuple )
+        {
+            return false;
+        }
+
+        public boolean getPrevious( Tuple tuple )
+        {
+            return false;
+        }
+    }
+}
+

Added: directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/btree/package.html
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/btree/package.html?rev=652410&view=auto
==============================================================================
--- directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/btree/package.html (added)
+++ directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/btree/package.html Wed Apr 30 17:06:41 2008
@@ -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/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/ByteArrayComparator.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/ByteArrayComparator.java?rev=652410&view=auto
==============================================================================
--- directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/ByteArrayComparator.java (added)
+++ directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/ByteArrayComparator.java Wed Apr 30 17:06:41 2008
@@ -0,0 +1,134 @@
+/**
+ * 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.util.Comparator;
+import java.io.Serializable;
+
+/**
+ * Comparator for byte arrays.
+ *
+ * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
+ * @version $Id: ByteArrayComparator.java,v 1.4 2002/05/31 06:33:20 boisvert Exp $
+ */
+public final class ByteArrayComparator
+    implements Comparator, 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( Object obj1, Object obj2 )
+     {
+        if ( obj1 == null ) {
+            throw new IllegalArgumentException( "Argument 'obj1' is null" );
+        }
+
+        if ( obj2 == null ) {
+            throw new IllegalArgumentException( "Argument 'obj2' is null" );
+        }
+
+        return compareByteArray( (byte[]) obj1, (byte[]) 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/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/ByteArraySerializer.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/ByteArraySerializer.java?rev=652410&view=auto
==============================================================================
--- directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/ByteArraySerializer.java (added)
+++ directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/ByteArraySerializer.java Wed Apr 30 17:06:41 2008
@@ -0,0 +1,102 @@
+/**
+ * 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>
+ * @version $Id: ByteArraySerializer.java,v 1.1 2003/03/21 02:48:42 boisvert Exp $
+ */
+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/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/CacheEvictionException.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/CacheEvictionException.java?rev=652410&view=auto
==============================================================================
--- directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/CacheEvictionException.java (added)
+++ directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/CacheEvictionException.java Wed Apr 30 17:06:41 2008
@@ -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: 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>
+ *  @version $Id: CacheEvictionException.java,v 1.4 2003/10/21 15:43:20 boisvert Exp $
+ */
+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/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/CachePolicy.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/CachePolicy.java?rev=652410&view=auto
==============================================================================
--- directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/CachePolicy.java (added)
+++ directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/CachePolicy.java Wed Apr 30 17:06:41 2008
@@ -0,0 +1,143 @@
+/**
+ * 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>
+ * @version $Id: CachePolicy.java,v 1.5 2003/11/01 13:25:02 dranatunga Exp $
+ */
+public interface CachePolicy
+{
+
+    /**
+     * 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( Object key, Object 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 Object get( Object 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( Object 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 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 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 listener );
+
+}

Added: directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/CachePolicyListener.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/CachePolicyListener.java?rev=652410&view=auto
==============================================================================
--- directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/CachePolicyListener.java (added)
+++ directory/apacheds/branches/bigbang/apacheds-jdbm/src/main/java/jdbm/helper/CachePolicyListener.java Wed Apr 30 17:06:41 2008
@@ -0,0 +1,77 @@
+/**
+ * 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>
+ * @version $Id: CachePolicyListener.java,v 1.3 2003/11/01 13:25:41 dranatunga Exp $
+ */
+public interface CachePolicyListener {
+
+    /**
+     * Notification that the cache this listener is attached to is evicting
+     * the object indicated.
+     *
+     * @param obj object being evited 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(Object obj) throws CacheEvictionException;
+
+}



Mime
View raw message