You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by el...@apache.org on 2008/05/01 02:06:46 UTC
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...
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;
+
+}