directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1239581 [5/9] - in /directory/apacheds/trunk/jdbm2: ./ src/ src/etc/ src/examples/ src/main/ src/main/java/ src/main/java/jdbm/ src/main/java/jdbm/btree/ src/main/java/jdbm/helper/ src/main/java/jdbm/htree/ src/main/java/jdbm/recman/ src/s...
Date Thu, 02 Feb 2012 12:38:42 GMT
Added: directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/SoftCache.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/SoftCache.java?rev=1239581&view=auto
==============================================================================
--- directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/SoftCache.java (added)
+++ directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/SoftCache.java Thu Feb  2 12:38:39 2012
@@ -0,0 +1,346 @@
+/**
+ * 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
+ */
+package jdbm.helper;
+
+
+import java.lang.ref.Reference;
+import java.lang.ref.ReferenceQueue;
+import java.lang.ref.SoftReference;
+import java.util.Enumeration;
+import java.util.HashMap;
+import java.util.Map;
+
+import org.apache.directory.server.i18n.I18n;
+
+
+/**
+ * Wraps a deterministic cache policy with a <q>Level-2</q> cache based on
+ * J2SE's {@link SoftReference soft references}. Soft references allow
+ * this cache to keep references to objects until the memory they occupy
+ * is required elsewhere.
+ * <p>
+ * Since the {@link CachePolicy} interface requires an event be fired
+ * when an object is evicted, and the event contains the actual object,
+ * this class cannot be a stand-alone implementation of
+ * <code>CachePolicy</code>. This limitation arises because Java References
+ * does not support notification before references are cleared; nor do
+ * they support reaching soft referents. Therefore, this wrapper cache
+ * aggressively notifies evictions: events are fired when the objects are
+ * evicted from the internal cache. Consequently, the soft cache may return
+ * a non-null object when <code>get( )</code> is called, even if that
+ * object was said to have been evicted.
+ * <p>
+ * The current implementation uses a hash structure for its internal key
+ * to value mappings.
+ * <p>
+ * Note: this component's publicly exposed methods are not threadsafe;
+ * potentially concurrent code should synchronize on the cache instance.
+ *
+ * @author <a href="mailto:dranatunga@users.sourceforge.net">Dilum Ranatunga</a>
+ */
+public class SoftCache implements CachePolicy
+{
+    private static final int INITIAL_CAPACITY = 128;
+    private static final float DEFAULT_LOAD_FACTOR = 1.5f;
+
+    private final ReferenceQueue clearQueue = new ReferenceQueue();
+    private final CachePolicy internal;
+    private final Map map;
+
+
+    /**
+     * Creates a soft-reference based L2 cache with a {@link MRU} cache as
+     * the internal (L1) cache. The soft reference cache uses the
+     * default load capacity of 1.5f, which is intended to sacrifice some
+     * performance for space. This compromise is reasonable, since all
+     * {@link #get(Object) get( )s} first try the L1 cache anyway. The
+     * internal MRU is given a capacity of 128 elements.
+     */
+    public SoftCache()
+    {
+        this( new MRU( INITIAL_CAPACITY ) );
+    }
+
+
+    /**
+     * Creates a soft-reference based L2 cache wrapping the specified
+     * L1 cache.
+     *
+     * @param internal non null internal cache.
+     * @throws NullPointerException if the internal cache is null.
+     */
+    public SoftCache( CachePolicy internal ) throws NullPointerException
+    {
+        this( DEFAULT_LOAD_FACTOR, internal );
+    }
+
+
+    /**
+     * Creates a soft-reference based L2 cache wrapping the specified
+     * L1 cache. This constructor is somewhat implementation-specific,
+     * so users are encouraged to use {@link #SoftCache(CachePolicy)}
+     * instead.
+     *
+     * @param loadFactor load factor that the soft cache's hash structure
+     *        should use.
+     * @param internal non null internal cache.
+     * @throws IllegalArgumentException if the load factor is nonpositive.
+     * @throws NullPointerException if the internal cache is null.
+     */
+    public SoftCache( float loadFactor, CachePolicy internal ) throws IllegalArgumentException, NullPointerException
+    {
+        if ( internal == null )
+        {
+            throw new IllegalArgumentException( I18n.err( I18n.ERR_531 ) );
+        }
+        
+        this.internal = internal;
+        map = new HashMap( INITIAL_CAPACITY, loadFactor );
+    }
+
+
+    /**
+     * Adds the specified value to the cache under the specified key. Note
+     * that the object is added to both this and the internal cache.
+     * @param key the (non-null) key to store the object under
+     * @param value the (non-null) object to place in the cache
+     * @throws CacheEvictionException exception that the internal cache
+     *         would have experienced while evicting an object it currently
+     *         cached.
+     */
+    public void put( Object key, Object value ) throws CacheEvictionException
+    {
+        if ( key == null )
+        {
+            throw new IllegalArgumentException( I18n.err( I18n.ERR_532 ) );
+        }
+        else if ( value == null )
+        {
+            throw new IllegalArgumentException( I18n.err( I18n.ERR_533 ) );
+        }
+        
+        internal.put( key, value );
+        removeClearedEntries();
+        map.put( key, new Entry( key, value, clearQueue ) );
+    }
+
+
+    /**
+     * Gets the object cached under the specified key.
+     * <p>
+     * The cache is looked up in the following manner:
+     * <ol>
+     * <li>The internal (L1) cache is checked. If the object is found, it is
+     *     returned.</li>
+     * <li>This (L2) cache is checked. If the object is not found, then
+     *     the caller is informed that the object is inaccessible.</li>
+     * <li>Since the object exists in L2, but not in L1, the object is
+     *     readded to L1 using {@link CachePolicy#put(Object, Object)}.</li>
+     * <li>If the readding succeeds, the value is returned to caller.</li>
+     * <li>If a cache eviction exception is encountered instead, we
+     *     remove the object from L2 and behave as if the object was
+     *     inaccessible.</li>
+     * </ol>
+     * @param key the key that the object was stored under.
+     * @return the object stored under the key specified; null if the
+     *         object is not (nolonger) accessible via this cache.
+     */
+    public Object get( Object key )
+    {
+        // first try the internal cache.
+        Object value = internal.get( key );
+        
+        if ( value != null )
+        {
+            return value;
+        }
+        
+        // poll and remove cleared references.
+        removeClearedEntries();
+        Entry entry = ( Entry ) map.get( key );
+        
+        if ( entry == null )
+        { // object is not in cache.
+            return null;
+        }
+        
+        value = entry.getValue();
+        
+        if ( value == null )
+        { // object was in cache, but it was cleared.
+            return null;
+        }
+        
+        // we have the object. so we try to re-insert it into internal cache
+        try
+        {
+            internal.put( key, value );
+        }
+        catch ( CacheEvictionException e )
+        {
+            // if the internal cache causes a fuss, we kick the object out.
+            map.remove( key );
+            return null;
+        }
+        
+        return value;
+    }
+
+
+    /**
+     * Removes any object stored under the key specified. Note that the
+     * object is removed from both this (L2) and the internal (L1)
+     * cache.
+     * @param key the key whose object should be removed
+     */
+    public void remove( Object key )
+    {
+        map.remove( key );
+        internal.remove( key );
+    }
+
+
+    /**
+     * Removes all objects in this (L2) and its internal (L1) cache.
+     */
+    public void removeAll()
+    {
+        map.clear();
+        internal.removeAll();
+    }
+
+
+    /**
+     * Gets all the objects stored by the internal (L1) cache.
+     * @return an enumeration of objects in internal cache.
+     */
+    public Enumeration elements()
+    {
+        return internal.elements();
+    }
+
+
+    /**
+     * Adds the specified listener to this cache. Note that the events
+     * fired by this correspond to the <em>internal</em> cache's events.
+     * @param listener the (non-null) listener to add to this policy
+     * @throws IllegalArgumentException if listener is null.
+     */
+    public void addListener( CachePolicyListener listener ) throws IllegalArgumentException
+    {
+        internal.addListener( listener );
+    }
+
+
+    /**
+     * Removes a listener that was added earlier.
+     * @param listener the listener to remove.
+     */
+    public void removeListener( CachePolicyListener listener )
+    {
+        internal.removeListener( listener );
+    }
+
+
+    /**
+     * Cleans the mapping structure of any obsolete entries. This is usually
+     * called before insertions and lookups on the mapping structure. The
+     * runtime of this is usually very small, but it can be as expensive as
+     * n * log(n) if a large number of soft references were recently cleared.
+     */
+    private final void removeClearedEntries()
+    {
+        for ( Reference r = clearQueue.poll(); r != null; r = clearQueue.poll() )
+        {
+            Object key = ( ( Entry ) r ).getKey();
+            map.remove( key );
+        }
+    }
+
+    /**
+     * Value objects we keep in the internal map. This contains the key in
+     * addition to the value, because polling for cleared references
+     * returns these instances, and having access to their corresponding
+     * keys drastically improves the performance of removing the pair
+     * from the map (see {@link SoftCache#removeClearedEntries()}.)
+     */
+    private static class Entry extends SoftReference
+    {
+        private final Object key;
+
+
+        /**
+         * Constructor that uses <code>value</code> as the soft
+         * reference's referent.
+         */
+        public Entry( Object key, Object value, ReferenceQueue queue )
+        {
+            super( value, queue );
+            this.key = key;
+        }
+
+
+        /**
+         * Gets the key
+         * @return the key associated with this value.
+         */
+        final Object getKey()
+        {
+            return key;
+        }
+
+
+        /**
+         * Gets the value
+         * @return the value; null if it is no longer accessible
+         */
+        final Object getValue()
+        {
+            return this.get();
+        }
+    }
+}

Added: directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/StringComparator.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/StringComparator.java?rev=1239581&view=auto
==============================================================================
--- directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/StringComparator.java (added)
+++ directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/StringComparator.java Thu Feb  2 12:38:39 2012
@@ -0,0 +1,90 @@
+/**
+ * JDBM LICENSE v1.00
+ *
+ * Redistribution and use of this software and associated documentation
+ * ("Software"), with or without modification, are permitted provided
+ * that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain copyright
+ *    statements and notices.  Redistributions must also contain a
+ *    copy of this document.
+ *
+ * 2. Redistributions in binary form must reproduce the
+ *    above copyright notice, this list of conditions and the
+ *    following disclaimer in the documentation and/or other
+ *    materials provided with the distribution.
+ *
+ * 3. The name "JDBM" must not be used to endorse or promote
+ *    products derived from this Software without prior written
+ *    permission of Cees de Groot.  For written permission,
+ *    please contact cg@cdegroot.com.
+ *
+ * 4. Products derived from this Software may not be called "JDBM"
+ *    nor may "JDBM" appear in their names without prior written
+ *    permission of Cees de Groot.
+ *
+ * 5. Due credit should be given to the JDBM Project
+ *    (http://jdbm.sourceforge.net/).
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE JDBM PROJECT AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
+ * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
+ * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
+ * CEES DE GROOT OR ANY CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Copyright 2001 (C) Alex Boisvert. All Rights Reserved.
+ * Contributions are Copyright (C) 2001 by their associated contributors.
+ *
+ */
+
+package jdbm.helper;
+
+import java.io.Serializable;
+import java.util.Comparator;
+
+import org.apache.directory.server.i18n.I18n;
+
+/**
+ * Comparator for String objects.  Delegates to String.compareTo().
+ *
+ * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
+ */
+public final class StringComparator
+    implements Comparator<String>, 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( String obj1, String obj2 )
+     {
+        if ( obj1 == null ) {
+            throw new IllegalArgumentException( I18n.err( I18n.ERR_525 ) );
+        }
+
+        if ( obj2 == null ) {
+            throw new IllegalArgumentException( I18n.err( I18n.ERR_526 ) );
+        }
+
+        return obj1.compareTo( obj2 );
+     }
+
+}

Added: directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/Tuple.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/Tuple.java?rev=1239581&view=auto
==============================================================================
--- directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/Tuple.java (added)
+++ directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/Tuple.java Thu Feb  2 12:38:39 2012
@@ -0,0 +1,126 @@
+/**
+ * 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;
+
+
+/**
+ * Tuple consisting of a key-value pair.
+ *
+ * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
+ */
+public final class Tuple<K, V> {
+
+    /** Key */
+    private K key;
+
+    /** Value */
+    private V value;
+
+
+    /**
+     * Construct an empty Tuple.
+     */
+    public Tuple() 
+    {
+        // empty
+    }
+
+
+    /**
+     * Construct a Tuple.
+     *
+     * @param key The key.
+     * @param value The value.
+     */
+    public Tuple( K key, V value ) 
+    {
+        this.key = key;
+        this.value = value;
+    }
+
+
+    /**
+     * Get the key.
+     */
+    public K getKey() 
+    {
+        return this.key;
+    }
+
+
+    /**
+     * Set the key.
+     */
+    public void setKey( K key ) 
+    {
+        this.key = key;
+    }
+
+
+    /**
+     * Get the value.
+     */
+    public V getValue() 
+    {
+        return value;
+    }
+
+
+    /**
+     * Set the value.
+     */
+    public void setValue( V value ) 
+    {
+        this.value = value;
+    }
+    
+    
+    public String toString()
+    {
+        return "<" + key + "," + value + ">";
+    }
+}

Added: directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/TupleBrowser.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/TupleBrowser.java?rev=1239581&view=auto
==============================================================================
--- directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/TupleBrowser.java (added)
+++ directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/TupleBrowser.java Thu Feb  2 12:38:39 2012
@@ -0,0 +1,83 @@
+/**
+ * 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;
+
+/**
+ * Browser to traverse a collection of tuples.  The browser allows for
+ * forward and reverse order traversal.
+ *
+ * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
+ */
+public abstract class TupleBrowser<K, V> {
+    /**
+     * Get the next tuple.
+     *
+     * @param tuple Tuple into which values are copied.
+     * @return True if values have been copied in tuple, or false if there is
+     *         no next tuple.
+     */
+    public abstract boolean getNext( Tuple<K, V> tuple ) throws IOException;
+
+
+    /**
+     * Get the previous tuple.
+     *
+     * @param tuple Tuple into which values are copied.
+     * @return True if values have been copied in tuple, or false if there is
+     *         no previous tuple.
+     */
+    public abstract boolean getPrevious( Tuple<K, V> tuple ) throws IOException;
+    
+    
+    /**
+     * Closes the browser and deallocates any resources it might have allocated.
+     * Repeated calls of close are OK.
+     */
+    public void close() {}
+}

Added: directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/WrappedRuntimeException.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/WrappedRuntimeException.java?rev=1239581&view=auto
==============================================================================
--- directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/WrappedRuntimeException.java (added)
+++ directory/apacheds/trunk/jdbm2/src/main/java/jdbm/helper/WrappedRuntimeException.java Thu Feb  2 12:38:39 2012
@@ -0,0 +1,150 @@
+/**
+ * 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.PrintStream;
+import java.io.PrintWriter;
+
+/**
+ * A run-time exception that wraps another exception. The printed stack
+ * trace will be that of the wrapped exception.
+ *
+ * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
+ */
+public class WrappedRuntimeException
+    extends RuntimeException
+{
+
+
+    /**
+     * The underlying exception.
+     */
+    private final Exception _except;
+
+
+    /**
+     * Constructs a new runtime exception based on a checked exception.
+     *
+     * @param message The error message
+     * @param except The checked exception
+     */
+    public WrappedRuntimeException( String message, Exception except )
+    {
+        super( message == null ? "No message available" : message );
+
+        if ( except instanceof WrappedRuntimeException &&
+             ( (WrappedRuntimeException) except )._except != null )
+        {
+            _except = ( (WrappedRuntimeException) except )._except;
+        } else {
+            _except = except;
+        }
+    }
+
+
+    /**
+     * Constructs a new runtime exception based on a checked exception.
+     *
+     * @param except The checked exception
+     */
+    public WrappedRuntimeException( Exception except )
+    {
+        super( except == null || except.getLocalizedMessage() == null ? "No message available" : except.getLocalizedMessage() );
+
+        if ( except instanceof WrappedRuntimeException &&
+             ( (WrappedRuntimeException) except )._except != null )
+        {
+            _except = ( (WrappedRuntimeException) except )._except;
+        } else {
+            _except = except;
+        }
+    }
+
+
+    /**
+     * Returns the exception wrapped by this runtime exception.
+     *
+     * @return The exception wrapped by this runtime exception
+     */
+    public Exception getException()
+    {
+        return _except;
+    }
+
+
+    public void printStackTrace()
+    {
+        if ( _except == null ) {
+            super.printStackTrace();
+        } else {
+            _except.printStackTrace();
+        }
+    }
+
+
+    public void printStackTrace( PrintStream stream )
+    {
+        if ( _except == null ) {
+            super.printStackTrace( stream );
+        } else {
+            _except.printStackTrace( stream );
+        }
+    }
+
+
+    public void printStackTrace( PrintWriter writer )
+    {
+        if ( _except == null ) {
+            super.printStackTrace( writer );
+        } else {
+            _except.printStackTrace( writer );
+        }
+    }
+
+}
+
+

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

Added: directory/apacheds/trunk/jdbm2/src/main/java/jdbm/htree/HTree.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm2/src/main/java/jdbm/htree/HTree.java?rev=1239581&view=auto
==============================================================================
--- directory/apacheds/trunk/jdbm2/src/main/java/jdbm/htree/HTree.java (added)
+++ directory/apacheds/trunk/jdbm2/src/main/java/jdbm/htree/HTree.java Thu Feb  2 12:38:39 2012
@@ -0,0 +1,187 @@
+/**
+ * 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 (C) Copyright 2000 by their associated contributors.
+ *
+ */
+
+package jdbm.htree;
+
+import jdbm.RecordManager;
+import jdbm.helper.FastIterator;
+import java.io.IOException;
+
+/**
+ *  Persistent hashtable implementation for PageManager.
+ *  Implemented as an H*Tree structure.
+ *
+ *  WARNING!  If this instance is used in a transactional context, it
+ *            *must* be discarded after a rollback.
+ *
+ *  @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
+ */
+public class HTree
+{
+
+    /**
+     * Root hash directory.
+     */
+    private HashDirectory _root;
+
+
+    /**
+     * Private constructor
+     *
+     * @param root Root hash directory.
+     */
+    private HTree( HashDirectory root ) {
+        _root = root;
+    }
+
+
+    /**
+     * Create a persistent hashtable.
+     *
+     * @param recman Record manager used for persistence.
+     */
+    public static HTree createInstance( RecordManager recman )
+        throws IOException
+    {
+        HashDirectory  root;
+        long           recid;
+
+        root = new HashDirectory( (byte) 0 );
+        recid = recman.insert( root );
+        root.setPersistenceContext( recman, recid );
+
+        return new HTree( root );
+    }
+
+
+    /**
+     * Load a persistent hashtable
+     *
+     * @param recman RecordManager used to store the persistent hashtable
+     * @param root_recid Record id of the root directory of the HTree
+     */
+    public static HTree load( RecordManager recman, long root_recid )
+        throws IOException
+    {
+        HTree tree;
+        HashDirectory root;
+
+        root = (HashDirectory) recman.fetch( root_recid );
+        root.setPersistenceContext( recman, root_recid );
+        tree = new HTree( root );
+        return tree;
+    }
+
+
+    /**
+     * Associates the specified value with the specified key.
+     *
+     * @param key key with which the specified value is to be assocated.
+     * @param value value to be associated with the specified key.
+     */
+    public synchronized void put(Object key, Object value)
+        throws IOException
+    {
+        _root.put(key, value);
+    }
+
+
+    /**
+     * Returns the value which is associated with the given key. Returns
+     * <code>null</code> if there is not association for this key.
+     *
+     * @param key key whose associated value is to be returned
+     */
+    public synchronized Object get(Object key)
+        throws IOException
+    {
+        return _root.get(key);
+    }
+
+
+    /**
+     * Remove the value which is associated with the given key.  If the
+     * key does not exist, this method simply ignores the operation.
+     *
+     * @param key key whose associated value is to be removed
+     */
+    public synchronized void remove(Object key)
+        throws IOException
+    {
+        _root.remove(key);
+    }
+
+
+    /**
+     * Returns an enumeration of the keys contained in this
+     */
+    public synchronized FastIterator keys()
+        throws IOException
+    {
+        return _root.keys();
+    }
+
+
+    /**
+     * Returns an enumeration of the values contained in this
+     */
+    public synchronized FastIterator values()
+        throws IOException
+    {
+        return _root.values();
+    }
+
+
+    /**
+     * Get the record identifier used to load this hashtable.
+     */
+    public long getRecid()
+    {
+        return _root.getRecid();
+    }
+
+}
+

Added: directory/apacheds/trunk/jdbm2/src/main/java/jdbm/htree/HashBucket.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm2/src/main/java/jdbm/htree/HashBucket.java?rev=1239581&view=auto
==============================================================================
--- directory/apacheds/trunk/jdbm2/src/main/java/jdbm/htree/HashBucket.java (added)
+++ directory/apacheds/trunk/jdbm2/src/main/java/jdbm/htree/HashBucket.java Thu Feb  2 12:38:39 2012
@@ -0,0 +1,313 @@
+/**
+ * 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.
+ *
+ */
+
+package jdbm.htree;
+
+import java.io.Externalizable;
+import java.io.IOException;
+import java.io.ObjectInput;
+import java.io.ObjectOutput;
+
+import java.util.ArrayList;
+
+import org.apache.directory.server.i18n.I18n;
+
+/**
+ * A bucket is a placeholder for multiple (key, value) pairs.  Buckets
+ * are used to store collisions (same hash value) at all levels of an
+ * H*tree.
+ *
+ * There are two types of buckets: leaf and non-leaf.
+ *
+ * Non-leaf buckets are buckets which hold collisions which happen
+ * when the H*tree is not fully expanded.   Keys in a non-leaf buckets
+ * can have different hash codes.  Non-leaf buckets are limited to an
+ * arbitrary size.  When this limit is reached, the H*tree should create
+ * a new Directory page and distribute keys of the non-leaf buckets into
+ * the newly created Directory.
+ *
+ * A leaf bucket is a bucket which contains keys which all have
+ * the same <code>hashCode()</code>.  Leaf buckets stand at the
+ * bottom of an H*tree because the hashing algorithm cannot further
+ * discriminate between different keys based on their hash code.
+ *
+ *  @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
+ */
+final class HashBucket
+    extends HashNode
+    implements Externalizable
+{
+
+    final static long serialVersionUID = 1L;
+
+    /**
+     * The maximum number of elements (key, value) a non-leaf bucket
+     * can contain.
+     */
+    public static final int OVERFLOW_SIZE = 8;
+
+
+    /**
+     * Depth of this bucket.
+     */
+    private int _depth;
+
+
+    /**
+     * Keys in this bucket.  Keys are ordered to match their respective
+     * value in <code>_values</code>.
+     */
+    private ArrayList _keys;
+
+
+    /**
+     * Values in this bucket.  Values are ordered to match their respective
+     * key in <code>_keys</code>.
+     */
+    private ArrayList _values;
+
+
+    /**
+     * Public constructor for serialization.
+     */
+    public HashBucket() {
+        // empty
+    }
+
+
+    /**
+     * Construct a bucket with a given depth level.  Depth level is the
+     * number of <code>HashDirectory</code> above this bucket.
+     */
+    public HashBucket( int level )
+    {
+        if ( level > HashDirectory.MAX_DEPTH+1 ) {
+            throw new IllegalArgumentException( I18n.err( I18n.ERR_534, level ) );
+        }
+        _depth = level;
+        _keys = new ArrayList( OVERFLOW_SIZE );
+        _values = new ArrayList( OVERFLOW_SIZE );
+    }
+
+
+    /**
+     * Returns the number of elements contained in this bucket.
+     */
+    public int getElementCount()
+    {
+        return _keys.size();
+    }
+
+
+    /**
+     * Returns whether or not this bucket is a "leaf bucket".
+     */
+    public boolean isLeaf()
+    {
+        return ( _depth > HashDirectory.MAX_DEPTH );
+    }
+
+
+    /**
+     * Returns true if bucket can accept at least one more element.
+     */
+    public boolean hasRoom()
+    {
+        if ( isLeaf() ) {
+            return true;  // leaf buckets are never full
+        } else {
+            // non-leaf bucket
+            return ( _keys.size() < OVERFLOW_SIZE );
+        }
+    }
+
+
+    /**
+     * Add an element (key, value) to this bucket.  If an existing element
+     * has the same key, it is replaced silently.
+     *
+     * @return Object which was previously associated with the given key
+     *          or <code>null</code> if no association existed.
+     */
+    public Object addElement( Object key, Object value )
+    {
+        int existing = _keys.indexOf(key);
+        if ( existing != -1 ) {
+            // replace existing element
+            Object before = _values.get( existing );
+            _values.set( existing, value );
+            return before;
+        } else {
+            // add new (key, value) pair
+            _keys.add( key );
+            _values.add( value );
+            return null;
+        }
+    }
+
+
+    /**
+     * Remove an element, given a specific key.
+     *
+     * @param key Key of the element to remove
+     *
+     * @return Removed element value, or <code>null</code> if not found
+     */
+    public Object removeElement( Object key )
+    {
+        int existing = _keys.indexOf(key);
+        if ( existing != -1 ) {
+            Object obj = _values.get( existing );
+            _keys.remove( existing );
+            _values.remove( existing );
+            return obj;
+        } else {
+            // not found
+            return null;
+        }
+    }
+
+
+    /**
+     * Returns the value associated with a given key.  If the given key
+     * is not found in this bucket, returns <code>null</code>.
+     */
+    public Object getValue( Object key )
+    {
+        int existing = _keys.indexOf(key);
+        if ( existing != -1 ) {
+            return _values.get( existing );
+        } else {
+            // key not found
+            return null;
+        }
+    }
+
+
+    /**
+     * Obtain keys contained in this buckets.  Keys are ordered to match
+     * their values, which be be obtained by calling <code>getValues()</code>.
+     *
+     * As an optimization, the Vector returned is the instance member
+     * of this class.  Please don't modify outside the scope of this class.
+     */
+    ArrayList getKeys()
+    {
+        return this._keys;
+    }
+
+
+    /**
+     * Obtain values contained in this buckets.  Values are ordered to match
+     * their keys, which be be obtained by calling <code>getKeys()</code>.
+     *
+     * As an optimization, the Vector returned is the instance member
+     * of this class.  Please don't modify outside the scope of this class.
+     */
+    ArrayList getValues()
+    {
+        return this._values;
+    }
+
+
+    /**
+     * Implement Externalizable interface.
+     */
+    public void writeExternal( ObjectOutput out )
+        throws IOException
+    {
+        out.writeInt( _depth );
+
+        int entries = _keys.size();
+        out.writeInt( entries );
+
+        // write keys
+        for (int i=0; i<entries; i++) {
+            out.writeObject( _keys.get( i ) );
+        }
+        // write values
+        for (int i=0; i<entries; i++) {
+            out.writeObject( _values.get( i ) );
+        }
+    }
+
+
+    /**
+     * Implement Externalizable interface.
+     */
+    public void readExternal(ObjectInput in)
+    throws IOException, ClassNotFoundException {
+        _depth = in.readInt();
+
+        int entries = in.readInt();
+
+        // prepare array lists
+        int size = Math.max( entries, OVERFLOW_SIZE );
+        _keys = new ArrayList( size );
+        _values = new ArrayList( size );
+
+        // read keys
+        for ( int i=0; i<entries; i++ ) {
+            _keys.add( in.readObject() );
+        }
+        // read values
+        for ( int i=0; i<entries; i++ ) {
+            _values.add( in.readObject() );
+        }
+    }
+
+    public String toString() {
+        StringBuffer buf = new StringBuffer();
+        buf.append("HashBucket {depth=");
+        buf.append(_depth);
+        buf.append(", keys=");
+        buf.append(_keys);
+        buf.append(", values=");
+        buf.append(_values);
+        buf.append("}");
+        return buf.toString();
+    }
+}

Added: directory/apacheds/trunk/jdbm2/src/main/java/jdbm/htree/HashDirectory.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm2/src/main/java/jdbm/htree/HashDirectory.java?rev=1239581&view=auto
==============================================================================
--- directory/apacheds/trunk/jdbm2/src/main/java/jdbm/htree/HashDirectory.java (added)
+++ directory/apacheds/trunk/jdbm2/src/main/java/jdbm/htree/HashDirectory.java Thu Feb  2 12:38:39 2012
@@ -0,0 +1,544 @@
+/**
+ * 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.
+ *
+ */
+
+package jdbm.htree;
+
+import java.io.Externalizable;
+import java.io.IOException;
+import java.io.ObjectInput;
+import java.io.ObjectOutput;
+import java.util.ArrayList;
+import java.util.Iterator;
+
+import jdbm.RecordManager;
+import jdbm.helper.FastIterator;
+import jdbm.helper.IterationException;
+
+import org.apache.directory.server.i18n.I18n;
+
+/**
+ *  Hashtable directory page.
+ *
+ *  @author <a href="mailto:boisvert@exoffice.com">Alex Boisvert</a>
+ */
+final class HashDirectory
+    extends HashNode
+    implements Externalizable
+{
+
+    static final long serialVersionUID = 1L;
+
+
+    /**
+     * Maximum number of children in a directory.
+     *
+     * (Must be a power of 2 -- if you update this value, you must also
+     *  update BIT_SIZE and MAX_DEPTH.)
+     */
+    static final int MAX_CHILDREN = 256;
+
+
+    /**
+     * Number of significant bits per directory level.
+     */
+    static final int BIT_SIZE = 8; // log2(256) = 8
+
+
+    /**
+     * Maximum number of levels (zero-based)
+     *
+     * (4 * 8 bits = 32 bits, which is the size of an "int", and as
+     *  you know, hashcodes in Java are "ints")
+     */
+    static final int MAX_DEPTH = 3; // 4 levels
+
+
+    /**
+     * Record ids of children pages.
+     */
+    private long[] _children;
+
+
+    /**
+     * Depth of this directory page, zero-based
+     */
+    private byte _depth;
+
+
+    /**
+     * PageManager used to persist changes in directory and buckets
+     */
+    private transient RecordManager _recman;
+
+
+    /**
+     * This directory's record ID in the PageManager.  (transient)
+     */
+    private transient long _recid;
+
+
+    /**
+     * Public constructor used by serialization
+     */
+    public HashDirectory() {
+        // empty
+    }
+
+    /**
+     * Construct a HashDirectory
+     *
+     * @param depth Depth of this directory page.
+     */
+    HashDirectory(byte depth) {
+        _depth = depth;
+        _children = new long[MAX_CHILDREN];
+    }
+
+
+    /**
+     * Sets persistence context.  This method must be called before any
+     * persistence-related operation.
+     *
+     * @param recman RecordManager which stores this directory
+     * @param recid Record id of this directory.
+     */
+    void setPersistenceContext( RecordManager recman, long recid )
+    {
+        this._recman = recman;
+        this._recid = recid;
+    }
+
+
+    /**
+     * Get the record identifier used to load this hashtable.
+     */
+    long getRecid() {
+        return _recid;
+    }
+
+
+    /**
+     * Returns whether or not this directory is empty.  A directory
+     * is empty when it no longer contains buckets or sub-directories.
+     */
+    boolean isEmpty() {
+        for (int i=0; i<_children.length; i++) {
+            if (_children[i] != 0) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    /**
+     * Returns the value which is associated with the given key. Returns
+     * <code>null</code> if there is not association for this key.
+     *
+     * @param key key whose associated value is to be returned
+     */
+    Object get(Object key)
+        throws IOException
+    {
+        int hash = hashCode( key );
+        long child_recid = _children[ hash ];
+        if ( child_recid == 0 ) {
+            // not bucket/page --> not found
+            return null;
+        } else {
+            HashNode node = (HashNode) _recman.fetch( child_recid );
+            // System.out.println("HashDirectory.get() child is : "+node);
+
+            if ( node instanceof HashDirectory ) {
+                // recurse into next directory level
+                HashDirectory dir = (HashDirectory) node;
+                dir.setPersistenceContext( _recman, child_recid );
+                return dir.get( key );
+            } else {
+                // node is a bucket
+                HashBucket bucket = (HashBucket) node;
+                return bucket.getValue( key );
+            }
+        }
+    }
+
+
+    /**
+     * Associates the specified value with the specified key.
+     *
+     * @param key key with which the specified value is to be assocated.
+     * @param value value to be associated with the specified key.
+     * @return object which was previously associated with the given key,
+     *          or <code>null</code> if no association existed.
+     */
+    Object put(Object key, Object value)
+    throws IOException {
+        if (value == null) {
+            return remove(key);
+        }
+        int hash = hashCode(key);
+        long child_recid = _children[hash];
+        if (child_recid == 0) {
+            // no bucket/page here yet, let's create a bucket
+            HashBucket bucket = new HashBucket(_depth+1);
+
+            // insert (key,value) pair in bucket
+            Object existing = bucket.addElement(key, value);
+
+            long b_recid = _recman.insert(bucket);
+            _children[hash] = b_recid;
+
+            _recman.update(_recid, this);
+
+            // System.out.println("Added: "+bucket);
+            return existing;
+        } else {
+            HashNode node = (HashNode) _recman.fetch( child_recid );
+
+            if ( node instanceof HashDirectory ) {
+                // recursive insert in next directory level
+                HashDirectory dir = (HashDirectory) node;
+                dir.setPersistenceContext( _recman, child_recid );
+                return dir.put( key, value );
+            } else {
+                // node is a bucket
+                HashBucket bucket = (HashBucket)node;
+                if (bucket.hasRoom()) {
+                    Object existing = bucket.addElement(key, value);
+                    _recman.update(child_recid, bucket);
+                    // System.out.println("Added: "+bucket);
+                    return existing;
+                } else {
+                    // overflow, so create a new directory
+                    if (_depth == MAX_DEPTH) {
+                        throw new RuntimeException( I18n.err( I18n.ERR_535, _depth ) );
+                    }
+                    HashDirectory dir = new HashDirectory( (byte) (_depth+1) );
+                    long dir_recid = _recman.insert( dir );
+                    dir.setPersistenceContext( _recman, dir_recid );
+
+                    _children[hash] = dir_recid;
+                    _recman.update( _recid, this );
+
+                    // discard overflown bucket
+                    _recman.delete( child_recid );
+
+                    // migrate existing bucket elements
+                    ArrayList keys = bucket.getKeys();
+                    ArrayList values = bucket.getValues();
+                    int entries = keys.size();
+                    for ( int i=0; i<entries; i++ ) {
+                        dir.put( keys.get( i ), values.get( i ) );
+                    }
+
+                    // (finally!) insert new element
+                    return dir.put( key, value );
+                }
+            }
+        }
+    }
+
+
+    /**
+     * Remove the value which is associated with the given key.  If the
+     * key does not exist, this method simply ignores the operation.
+     *
+     * @param key key whose associated value is to be removed
+     * @return object which was associated with the given key, or
+     *          <code>null</code> if no association existed with given key.
+     */
+    Object remove(Object key) throws IOException {
+        int hash = hashCode(key);
+        long child_recid = _children[hash];
+        if (child_recid == 0) {
+            // not bucket/page --> not found
+            return null;
+        } else {
+            HashNode node = (HashNode) _recman.fetch( child_recid );
+            // System.out.println("HashDirectory.remove() child is : "+node);
+
+            if (node instanceof HashDirectory) {
+                // recurse into next directory level
+                HashDirectory dir = (HashDirectory)node;
+                dir.setPersistenceContext( _recman, child_recid );
+                Object existing = dir.remove(key);
+                if (existing != null && dir.isEmpty()) {
+                    // delete empty directory
+                    _recman.delete(child_recid);
+                    _children[hash] = 0;
+                    _recman.update(_recid, this);
+                }
+                return existing;
+            } else {
+                // node is a bucket
+                HashBucket bucket = (HashBucket)node;
+                Object existing = bucket.removeElement(key);
+                if (existing != null) {
+                    if (bucket.getElementCount() >= 1) {
+                        _recman.update(child_recid, bucket);
+                    } else {
+                        // delete bucket, it's empty
+                        _recman.delete(child_recid);
+                        _children[hash] = 0;
+                        _recman.update(_recid, this);
+                    }
+                }
+                return existing;
+            }
+        }
+    }
+
+    /**
+     * Calculates the hashcode of a key, based on the current directory
+     * depth.
+     */
+    private int hashCode(Object key) {
+        int hashMask = hashMask();
+        int hash = key.hashCode();
+        hash = hash & hashMask;
+        hash = hash >>> ((MAX_DEPTH - _depth) * BIT_SIZE);
+        hash = hash % MAX_CHILDREN;
+        /*
+        System.out.println("HashDirectory.hashCode() is: 0x"
+                           +Integer.toHexString(hash)
+                           +" for object hashCode() 0x"
+                           +Integer.toHexString(key.hashCode()));
+        */
+        return hash;
+    }
+
+    /**
+     * Calculates the hashmask of this directory.  The hashmask is the
+     * bit mask applied to a hashcode to retain only bits that are
+     * relevant to this directory level.
+     */
+    int hashMask() {
+        int bits = MAX_CHILDREN-1;
+        int hashMask = bits << ((MAX_DEPTH - _depth) * BIT_SIZE);
+        /*
+        System.out.println("HashDirectory.hashMask() is: 0x"
+                           +Integer.toHexString(hashMask));
+        */
+        return hashMask;
+    }
+
+    /**
+     * Returns an enumeration of the keys contained in this
+     */
+    FastIterator keys()
+        throws IOException
+    {
+        return new HDIterator( true );
+    }
+
+    /**
+     * Returns an enumeration of the values contained in this
+     */
+    FastIterator values()
+        throws IOException
+    {
+        return new HDIterator( false );
+    }
+
+
+    /**
+     * Implement Externalizable interface
+     */
+    public void writeExternal(ObjectOutput out)
+    throws IOException {
+        out.writeByte(_depth);
+        out.writeObject(_children);
+    }
+
+
+    /**
+     * Implement Externalizable interface
+     */
+    public synchronized void readExternal(ObjectInput in)
+    throws IOException, ClassNotFoundException {
+        _depth = in.readByte();
+        _children = (long[])in.readObject();
+    }
+
+
+    ////////////////////////////////////////////////////////////////////////
+    // INNER CLASS
+    ////////////////////////////////////////////////////////////////////////
+
+    /**
+     * Utility class to enumerate keys/values in a HTree
+     */
+    public class HDIterator
+        extends FastIterator
+    {
+
+        /**
+         * True if we're iterating on keys, False if enumerating on values.
+         */
+        private boolean _iterateKeys;
+
+        /**
+         * Stacks of directories & last enumerated child position
+         */
+        private ArrayList _dirStack;
+        private ArrayList _childStack;
+
+        /**
+         * Current HashDirectory in the hierarchy
+         */
+        private HashDirectory _dir;
+
+        /**
+         * Current child position
+         */
+        private int _child;
+
+        /**
+         * Current bucket iterator
+         */
+        private Iterator _iter;
+
+
+        /**
+         * Construct an iterator on this directory.
+         *
+         * @param iterateKeys True if iteration supplies keys, False
+         *                  if iterateKeys supplies values.
+         */
+        HDIterator( boolean iterateKeys )
+            throws IOException
+        {
+            _dirStack = new ArrayList();
+            _childStack = new ArrayList();
+            _dir = HashDirectory.this;
+            _child = -1;
+            _iterateKeys = iterateKeys;
+
+            prepareNext();
+        }
+
+
+        /**
+         * Returns the next object.
+         */
+        public Object next()
+        {   
+            Object next = null;      
+            if( _iter != null && _iter.hasNext() ) {
+              next = _iter.next();
+            } else {
+              try {
+                prepareNext();
+              } catch ( IOException except ) {
+                throw new IterationException( except );
+              }
+              if ( _iter != null && _iter.hasNext() ) {
+                return next();
+              }
+            }
+            return next;         
+        }
+
+
+        /**
+         * Prepare internal state so we can answer <code>hasMoreElements</code>
+         *
+         * Actually, this code prepares an Enumeration on the next
+         * Bucket to enumerate.   If no following bucket is found,
+         * the next Enumeration is set to <code>null</code>.
+         */
+        private void prepareNext() throws IOException {
+            long child_recid = 0;
+
+            // find next bucket/directory to enumerate
+            do {
+                _child++;
+                if (_child >= MAX_CHILDREN) {
+
+                    if (_dirStack.isEmpty()) {
+                        // no more directory in the stack, we're finished
+                        return;
+                    }
+
+                    // try next page
+                    _dir = (HashDirectory) _dirStack.remove( _dirStack.size()-1 );
+                    _child = ( (Integer) _childStack.remove( _childStack.size()-1 ) ).intValue();
+                    continue;
+                }
+                child_recid = _dir._children[_child];
+            } while (child_recid == 0);
+
+            if (child_recid == 0) {
+                throw new Error("child_recid cannot be 0");
+            }
+
+            HashNode node = (HashNode) _recman.fetch( child_recid );
+            // System.out.println("HDEnumeration.get() child is : "+node);
+ 
+            if ( node instanceof HashDirectory ) {
+                // save current position
+                _dirStack.add( _dir );
+                _childStack.add( Integer.valueOf( _child ) );
+
+                _dir = (HashDirectory)node;
+                _child = -1;
+
+                // recurse into
+                _dir.setPersistenceContext( _recman, child_recid );
+                prepareNext();
+            } else {
+                // node is a bucket
+                HashBucket bucket = (HashBucket)node;
+                if ( _iterateKeys ) {
+                    _iter = bucket.getKeys().iterator();
+                } else {
+                    _iter = bucket.getValues().iterator();
+                }
+            }
+        }
+    }
+
+}
+

Added: directory/apacheds/trunk/jdbm2/src/main/java/jdbm/htree/HashNode.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm2/src/main/java/jdbm/htree/HashNode.java?rev=1239581&view=auto
==============================================================================
--- directory/apacheds/trunk/jdbm2/src/main/java/jdbm/htree/HashNode.java (added)
+++ directory/apacheds/trunk/jdbm2/src/main/java/jdbm/htree/HashNode.java Thu Feb  2 12:38:39 2012
@@ -0,0 +1,56 @@
+/**

+ * 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.

+ *

+ */

+

+package jdbm.htree;

+

+import java.io.Serializable;

+

+/**
 *  Abstract class for Hashtable directory nodes
 *
 *  @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
 */
class HashNode implements Serializable {

+

+    // Empty, there's no common functionality.  We use this abstract

+    // class for typing only.

+

+}


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

Added: directory/apacheds/trunk/jdbm2/src/main/java/jdbm/package.html
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm2/src/main/java/jdbm/package.html?rev=1239581&view=auto
==============================================================================
--- directory/apacheds/trunk/jdbm2/src/main/java/jdbm/package.html (added)
+++ directory/apacheds/trunk/jdbm2/src/main/java/jdbm/package.html Thu Feb  2 12:38:39 2012
@@ -0,0 +1,21 @@
+<!-- $Id: package.html,v 1.1 2001/05/19 16:01:32 boisvert Exp $ -->
+<html>
+  <body>
+    <p>Simplified public API corresponding to GDBM APIs.</p>
+    
+    <h1><b>JDBM</b></h1>
+
+    <p>JDBM is a simple transactional persistent engine for Java.
+       It aims to be for Java what GDBM is for C/C++, Perl, Python, etc: 
+       a fast, simple persistence engine. </p>
+
+    <p>You can use it to store a mix of hashtables and blobs, and all updates are 
+       done in a transactionally safe manner.</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>



Mime
View raw message