felix-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
Subject svn commit: r500151 [2/2] - in /incubator/felix/sandbox/akarasulu/bundledb/src/main/java/org/apache/felix/bundledb/btree: ./ jdbm/
Date Fri, 26 Jan 2007 06:20:19 GMT
Added: incubator/felix/sandbox/akarasulu/bundledb/src/main/java/org/apache/felix/bundledb/btree/jdbm/JdbmTable.java
URL: http://svn.apache.org/viewvc/incubator/felix/sandbox/akarasulu/bundledb/src/main/java/org/apache/felix/bundledb/btree/jdbm/JdbmTable.java?view=auto&rev=500151
==============================================================================
--- incubator/felix/sandbox/akarasulu/bundledb/src/main/java/org/apache/felix/bundledb/btree/jdbm/JdbmTable.java (added)
+++ incubator/felix/sandbox/akarasulu/bundledb/src/main/java/org/apache/felix/bundledb/btree/jdbm/JdbmTable.java Thu Jan 25 22:20:18 2007
@@ -0,0 +1,1406 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *  
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *  
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License. 
+ *  
+ */
+package org.apache.felix.bundledb.btree.jdbm;
+
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Enumeration;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Set;
+import java.util.Map;
+import java.util.SortedSet;
+import java.util.TreeSet;
+
+import jdbm.RecordManager;
+import jdbm.btree.BTree;
+import jdbm.helper.TupleBrowser;
+
+import org.apache.felix.bundledb.btree.IndexConfiguration;
+import org.apache.felix.bundledb.btree.IteratorTupleCursor;
+import org.apache.felix.bundledb.btree.KeyOnlyComparator;
+import org.apache.felix.bundledb.btree.NoDupsTupleCursor;
+import org.apache.felix.bundledb.btree.Table;
+import org.apache.felix.bundledb.btree.Tuple;
+import org.apache.felix.bundledb.btree.TupleComparator;
+import org.apache.felix.bundledb.btree.TupleCursor;
+import org.apache.felix.bundledb.btree.TupleRenderer;
+
+
+/**
+ * A jdbm Btree wrapper that enables duplicate sorted keys using collections.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev: 491471 $
+ */
+public class JdbmTable implements Table
+{
+    /**  */
+    private static final String SZSUFFIX = "_btree_sz";
+
+    /** */
+    private final String name;
+    /** */
+    private final RecordManager recMan;
+    /** */
+    private final boolean allowsDuplicates;
+    /** */
+    private final TupleComparator comparator;
+
+    /** */
+    private int count = 0;
+    /** */
+    private BTree bt;
+    /** */
+    private TupleRenderer renderer;
+
+    private int numDupLimit = IndexConfiguration.DEFAULT_DUPLICATE_LIMIT;
+
+    private Map<Long, BTree> duplicateBtrees = new HashMap<Long, BTree>();
+    
+    
+    // ------------------------------------------------------------------------
+    // C O N S T R U C T O R
+    // ------------------------------------------------------------------------
+
+    /**
+     * Creates a Jdbm BTree based tuple Table abstraction that enables 
+     * duplicates.
+     *
+     * @param name the name of the table
+     * @param allowsDuplicates whether or not duplicates are enabled 
+     * @param manager the record manager to be used for this table
+     * @param comparator a tuple comparator
+     * @throws IOException if the table's file cannot be created
+     */
+    public JdbmTable( String name, boolean allowsDuplicates, int numDupLimit, RecordManager manager, 
+        TupleComparator comparator ) throws IOException
+    {
+        this.numDupLimit = numDupLimit;
+        this.name = name;
+        this.recMan = manager;
+        this.comparator = comparator;
+        this.allowsDuplicates = allowsDuplicates;
+
+        long recId = recMan.getNamedObject( name );
+
+        //            
+        // Load existing BTree
+        //
+
+        if ( recId != 0 )
+        {
+            bt = BTree.load( recMan, recId );
+            recId = recMan.getNamedObject( name + SZSUFFIX );
+            count = ( ( Integer ) recMan.fetch( recId ) ).intValue();
+        }
+        else
+        {
+            bt = BTree.createInstance( recMan, comparator.getKeyComparator() );
+            recId = bt.getRecid();
+            recMan.setNamedObject( name, recId );
+            recId = recMan.insert( new Integer( 0 ) );
+            recMan.setNamedObject( name + SZSUFFIX, recId );
+        }
+    }
+
+
+    /**
+     * Creates a Jdbm BTree based tuple Table abstraction without duplicates 
+     * enabled using a simple key comparator.
+     *
+     * @param name the name of the table
+     * @param manager the record manager to be used for this table
+     * @param keyComparator a tuple comparator
+     * @throws IOException if the table's file cannot be created
+     */
+    public JdbmTable( String name, RecordManager manager, Comparator keyComparator ) throws IOException
+    {
+        this( name, false, Integer.MAX_VALUE, manager, new KeyOnlyComparator( keyComparator ) );
+    }
+
+
+    // ------------------------------------------------------------------------
+    // Simple Table Properties
+    // ------------------------------------------------------------------------
+
+    /**
+     * @see org.apache.directory.server.core.partition.impl.btree.Table#getComparator()
+     */
+    public TupleComparator getComparator()
+    {
+        return comparator;
+    }
+
+
+    /**
+     * @see org.apache.directory.server.core.partition.impl.btree.Table#isDupsEnabled()
+     */
+    public boolean isDupsEnabled()
+    {
+        return allowsDuplicates;
+    }
+
+
+    /**
+     * @see org.apache.directory.server.core.partition.impl.btree.Table#getName()
+     */
+    public String getName()
+    {
+        return name;
+    }
+
+
+    /**
+     * @see org.apache.directory.server.core.partition.impl.btree.Table#getRenderer()
+     */
+    public TupleRenderer getRenderer()
+    {
+        return renderer;
+    }
+
+
+    /**
+     * @see Table#setRenderer(
+     * TupleRenderer)
+     */
+    public void setRenderer( TupleRenderer renderer )
+    {
+        this.renderer = renderer;
+    }
+
+
+    /**
+     * @see Table#isSortedDupsEnabled()
+     */
+    public boolean isSortedDupsEnabled()
+    {
+        // If duplicates are enabled than duplicates will be maintained in
+        // sorted order.
+        return allowsDuplicates;
+    }
+
+
+    // ------------------------------------------------------------------------
+    // Count Overloads
+    // ------------------------------------------------------------------------
+
+    /**
+     * @see Table#count(java.lang.Object, boolean)
+     */
+    public int count( Object key, boolean isGreaterThan )
+    {
+        // take a best guess
+        return count;
+    }
+
+
+    /**
+     * @see Table#count(java.lang.Object)
+     */
+    public int count( Object key ) throws IOException
+    {
+        if ( !allowsDuplicates )
+        {
+            if ( null == getRaw( key ) )
+            {
+                return 0;
+            }
+            else
+            {
+                return 1;
+            }
+        }
+
+        Object values = getRaw( key );
+        
+        if ( values == null )
+        {
+            return 0;
+        }
+        
+        // -------------------------------------------------------------------
+        // Handle the use of a TreeSet for storing duplicates
+        // -------------------------------------------------------------------
+
+        if ( values instanceof TreeSet )
+        {
+            return ( ( TreeSet ) values ).size();
+        }
+
+        // -------------------------------------------------------------------
+        // Handle the use of a BTree for storing duplicates
+        // -------------------------------------------------------------------
+
+        if ( values instanceof BTreeRedirect )
+        {
+            return getBTree( ( BTreeRedirect ) values ).size();
+        }
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
+    }
+
+
+    public int count() throws IOException
+    {
+        return count;
+    }
+
+    
+    // ------------------------------------------------------------------------
+    // get/has/put/remove Methods and Overloads
+    // ------------------------------------------------------------------------
+
+    /**
+     * @see Table#get(java.lang.Object)
+     */
+    public Object get( Object key ) throws IOException
+    {
+        if ( ! allowsDuplicates )
+        {
+            return getRaw( key );
+        }
+
+        Object values = getRaw( key );
+        
+        if ( values == null )
+        {
+            return null;
+        }
+        
+        if ( values instanceof TreeSet )
+        {
+            TreeSet set = ( TreeSet ) values;
+            
+            if ( set.size() == 0 )
+            {
+                return null;
+            }
+            else
+            {
+                return set.first();
+            }
+        }
+
+        if ( values instanceof BTreeRedirect )
+        {
+            BTree tree = getBTree( ( BTreeRedirect ) values );
+            
+            if ( tree.size() == 0 )
+            {
+                return null;
+            }
+            else
+            {
+                return firstKey( tree );
+            }
+        }
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
+    }
+
+    
+    /**
+     * @see Table#has(java.lang.Object,
+     * java.lang.Object, boolean)
+     */
+    @SuppressWarnings("unchecked")
+    public boolean has( Object key, Object val, boolean isGreaterThan ) throws IOException
+    {
+        if ( !allowsDuplicates )
+        {
+            Object rval = getRaw( key );
+
+            // key does not exist so return nothing
+            if ( null == rval )
+            {
+                return false;
+            }
+            // val == val return true
+            else if ( val.equals( rval ) )
+            {
+                return true;
+            }
+            // val >= val and test is for greater then return true
+            else if ( comparator.compareValue( rval, val ) >= 1 && isGreaterThan )
+            {
+                return true;
+            }
+            // val <= val and test is for lesser then return true
+            else if ( comparator.compareValue( rval, val ) <= 1 && !isGreaterThan )
+            {
+                return true;
+            }
+
+            return false;
+        }
+
+        Object values = getRaw( key );
+        
+        if ( values == null )
+        {
+            return false;
+        }
+        
+        if ( values instanceof TreeSet )
+        {
+            TreeSet set = ( TreeSet ) values;
+            SortedSet subset = null;
+    
+            if ( set.size() == 0 )
+            {
+                return false;
+            }
+    
+            if ( isGreaterThan )
+            {
+                subset = set.tailSet( val );
+            }
+            else
+            {
+                subset = set.headSet( val );
+            }
+    
+            if ( subset.size() > 0 || set.contains( val ) )
+            {
+                return true;
+            }
+    
+            return false;
+        }
+        
+        if ( values instanceof BTreeRedirect )
+        {
+            BTree tree = getBTree( ( BTreeRedirect ) values );
+            if ( tree.size() == 0 )
+            {
+                return false;
+            }
+
+            return btreeHas( tree, val, isGreaterThan );
+        }
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
+    }
+    
+
+    /**
+     * @see Table#has(java.lang.Object, boolean)
+     */
+    public boolean has( Object key, boolean isGreaterThan ) throws IOException
+    {
+        // See if we can find the border between keys greater than and less
+        // than in the set of keys.  This will be the spot we search from.
+        jdbm.helper.Tuple tuple = bt.findGreaterOrEqual( key );
+
+        // Test for equality first since it satisfies both greater/less than
+        if ( null != tuple && comparator.compareKey( tuple.getKey(), key ) == 0 )
+        {
+            return true;
+        }
+
+        // Greater searches are easy and quick thanks to findGreaterOrEqual
+        if ( isGreaterThan )
+        {
+            // A null return above means there were no equal or greater keys
+            if ( null == tuple )
+            {
+                return false;
+            }
+
+            // Not Null! - we found a tuple with equal or greater key value
+            return true;
+        }
+
+        // Less than searches occur below and are not as efficient or easy.
+        // We need to scan up from the begining if findGreaterOrEqual failed
+        // or scan down if findGreaterOrEqual succeed.
+        TupleBrowser browser = null;
+        if ( null == tuple )
+        {
+            // findGreaterOrEqual failed so we create a tuple and scan from
+            // the lowest values up via getNext comparing each key to key
+            tuple = new jdbm.helper.Tuple();
+            browser = bt.browse();
+
+            // We should at most have to read one key.  If 1st key is not
+            // less than or equal to key then all keys are > key
+            // since the keys are assorted in ascending order based on the
+            // comparator.
+            while ( browser.getNext( tuple ) )
+            {
+                if ( comparator.compareKey( tuple.getKey(), key ) <= 0 )
+                {
+                    return true;
+                }
+
+                return false;
+            }
+        }
+        else
+        {
+            // findGreaterOrEqual succeeded so use the existing tuple and
+            // scan the down from the highest key less than key via
+            // getPrevious while comparing each key to key.
+            browser = bt.browse( tuple.getKey() );
+
+            // The above call positions the browser just before the given
+            // key so we need to step forward once then back.  Remember this
+            // key represents a key greater than or equal to key.
+            if ( comparator.compareKey( tuple.getKey(), key ) <= 0 )
+            {
+                return true;
+            }
+
+            browser.getNext( tuple );
+
+            // We should at most have to read one key, but we don't short
+            // the search as in the search above first because the chance of
+            // unneccessarily looping is nil since values get smaller.
+            while ( browser.getPrevious( tuple ) )
+            {
+                if ( comparator.compareKey( tuple.getKey(), key ) <= 0 )
+                {
+                    return true;
+                }
+            }
+        }
+
+        return false;
+    }
+
+
+    /**
+     * @see org.apache.directory.server.core.partition.impl.btree.Table#has(java.lang.Object,
+     * java.lang.Object)
+     */
+    public boolean has( Object key, Object value ) throws IOException
+    {
+        if ( ! allowsDuplicates )
+        {
+            Object obj = getRaw( key );
+
+            if ( null == obj )
+            {
+                return false;
+            }
+
+            return obj.equals( value );
+        }
+        
+        Object values = getRaw( key );
+        
+        if ( values == null )
+        {
+            return false;
+        }
+        
+        if ( values instanceof TreeSet )
+        {
+            return ( ( TreeSet ) values ).contains( value );
+        }
+        
+        if ( values instanceof BTreeRedirect )
+        {
+            return btreeHas( getBTree( ( BTreeRedirect ) values ), value );
+        }
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
+    }
+    
+
+    /**
+     * @see Table#has(java.lang.Object)
+     */
+    public boolean has( Object key ) throws IOException
+    {
+        return getRaw( key ) != null;
+    }
+
+
+    /**
+     * @see org.apache.directory.server.core.partition.impl.btree.Table#put(java.lang.Object,
+     * java.lang.Object)
+     */
+    @SuppressWarnings("unchecked")
+    public Object put( Object key, Object value ) throws IOException
+    {
+        Object replaced = null;
+
+        if ( ! allowsDuplicates )
+        {
+            replaced = putRaw( key, value, true );
+
+            if ( null == replaced )
+            {
+                count++;
+            }
+
+            return replaced;
+        }
+        
+        Object values = getRaw( key );
+        
+        if ( values == null )
+        {
+            values = new TreeSet( comparator.getValueComparator() );
+        }
+        
+        if ( values instanceof TreeSet )
+        {
+            TreeSet set = ( TreeSet ) values;
+            
+            if ( set.contains( value ) )
+            {
+                return value;
+            }
+            
+            boolean addSuccessful = set.add( value );
+            
+            if ( set.size() > numDupLimit )
+            {
+                BTree tree = convertToBTree( set );
+                BTreeRedirect redirect = new BTreeRedirect( tree.getRecid() );
+                replaced = putRaw( key, redirect, true );
+            }
+            else
+            {
+                replaced = putRaw( key, set, true );
+            }
+            
+            if ( addSuccessful )
+            {
+                count++;
+                return replaced;
+            }
+            return null;
+        }
+        
+        if ( values instanceof BTreeRedirect )
+        {
+            BTree tree = getBTree( ( BTreeRedirect ) values );
+            if ( insertDupIntoBTree( tree, value ) )
+            {
+                count++;
+                return values;
+            }
+            return null;
+        }
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
+    }
+    
+
+    /**
+     * @see Table#put(java.lang.Object,
+     * javax.naming.NamingEnumeration)
+     */
+    @SuppressWarnings("unchecked")
+    public Object put( Object key, Enumeration values ) throws IOException
+    {
+        /*
+         * If we do not allow duplicates call the single add put using the
+         * first value in the enumeration if it exists.  If it does not we
+         * just return null without doing anything.  If more than one value
+         * is in the enumeration than we blow a UnsupportedOperationException.
+         */
+        if ( !allowsDuplicates )
+        {
+            if ( values.hasMoreElements() )
+            {
+                Object value = values.nextElement();
+
+                if ( values.hasMoreElements() )
+                {
+                    throw new UnsupportedOperationException( "Attempting to put duplicate keys into table " + name
+                        + " which does not support duplicates" );
+                }
+
+                return put( key, value );
+            }
+
+            return null;
+        }
+
+        Object storedValues = getRaw( key );
+        
+        if ( storedValues == null )
+        {
+            storedValues = new TreeSet( comparator.getValueComparator() );
+        }
+        
+        if ( storedValues instanceof TreeSet )
+        {
+            /*
+             * Here the table allows duplicates so we get the TreeSet from the 
+             * Table holding all the duplicate key values or create one if it
+             * does not exist for key.  We check if the value is present and
+             * if it is we add it and increment the table entry counter.
+             */
+            TreeSet set = ( TreeSet ) storedValues;
+            while ( values.hasMoreElements() )
+            {
+                Object val = values.nextElement();
+    
+                if ( !set.contains( val ) )
+                {
+                    boolean isAddSuccessful = set.add( val );
+                    if ( isAddSuccessful )
+                    {
+                        count++;
+                    }
+                }
+            }
+    
+            if ( set.size() > numDupLimit )
+            {
+                BTree tree = convertToBTree( set );
+                BTreeRedirect redirect = new BTreeRedirect( tree.getRecid() );
+                return putRaw( key, redirect, true );
+            }
+            else
+            {
+                return putRaw( key, set, true );
+            }
+        }
+        
+        if ( storedValues instanceof BTreeRedirect )
+        {
+            BTree tree = getBTree( ( BTreeRedirect ) storedValues );
+            while ( values.hasMoreElements() )
+            {
+                Object val = values.nextElement();
+                
+                if ( insertDupIntoBTree( tree, val ) )
+                {
+                    count++;
+                }
+            }
+
+            return storedValues;
+        }
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
+    }
+
+
+    /**
+     * @see Table#remove(java.lang.Object,
+     * java.lang.Object)
+     */
+    public Object remove( Object key, Object value ) throws IOException
+    {
+        if ( ! allowsDuplicates )
+        {
+            Object oldValue = getRaw( key );
+        
+            // Remove the value only if it is the same as value.
+            if ( oldValue != null && oldValue.equals( value ) )
+            {
+                removeRaw( key );
+                count--;
+                return oldValue;
+            }
+
+            return null;
+        }
+
+        Object values = getRaw( key );
+        
+        if ( values == null )
+        {
+            return null;
+        }
+        
+        if ( values instanceof TreeSet )
+        {
+            TreeSet set = ( TreeSet ) values;
+
+            // If removal succeeds then remove if set is empty else replace it
+            if ( set.remove( value ) )
+            {
+                if ( set.isEmpty() )
+                {
+                    removeRaw( key );
+                }
+                else
+                {
+                    putRaw( key, set, true );
+                }
+
+                // Decrement counter if removal occurs.
+                count--;
+                return value;
+            }
+
+            return null;
+        }
+
+        // TODO might be nice to add code here that reverts to a TreeSet
+        // if the number of duplicates falls below the numDupLimit value
+        if ( values instanceof BTreeRedirect )
+        {
+            BTree tree = getBTree( ( BTreeRedirect ) values );
+            
+            if ( removeDupFromBTree( tree, value ) )
+            {
+                if ( tree.size() == 0 )
+                {
+                    removeRaw( key );
+                }
+                
+                count--;
+                return value;
+            }
+            
+            return null;
+        }
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
+    }
+
+
+    /**
+     * @see Table#remove(java.lang.Object,
+     * javax.naming.NamingEnumeration)
+     */
+    public Object remove( Object key, Enumeration values ) throws IOException
+    {
+        /*
+         * If we do not allow dupliicates call the single remove using the
+         * first value in the enumeration if it exists.  If it does not we
+         * just return null without doing anything.  If more than one value
+         * is in the enumeration than we blow a UnsupportedOperationException.
+         */
+        if ( !allowsDuplicates )
+        {
+            if ( values.hasMoreElements() )
+            {
+                Object value = values.nextElement();
+
+                if ( values.hasMoreElements() )
+                {
+                    throw new UnsupportedOperationException( "Attempting to remove duplicate keys from table " + name
+                        + " which does not support duplicates" );
+                }
+
+                return remove( key, value );
+            }
+
+            return null;
+        }
+
+        Object storedValues = getRaw( key );
+        
+        if ( storedValues == null )
+        {
+            return null;
+        }
+        
+        if ( storedValues instanceof TreeSet )
+        {
+            /*
+             * Here the table allows duplicates so we get the TreeSet from the 
+             * Table holding all the duplicate key values or return null if it
+             * does not exist for key - nothing to do here.
+             */
+            TreeSet set = ( TreeSet ) storedValues;
+    
+            /*
+             * So we have a valid TreeSet with values in it.  We check if each value
+             * is in the set and remove it if it is present.  We decrement the 
+             * counter while doing so.
+             */
+            Object firstValue = null;
+            while ( values.hasMoreElements() )
+            {
+                Object val = values.nextElement();
+    
+                // get the first value
+                if ( firstValue == null )
+                {
+                    firstValue = val;
+                }
+
+                if ( set.contains( val ) )
+                {
+                    set.remove( val );
+                    count--;
+                }
+            }
+    
+            // Return the raw TreeSet and put the changed one back.
+            putRaw( key, set, true );
+            return firstValue;
+        }
+        
+        // TODO might be nice to add code here that reverts to a TreeSet
+        // if the number of duplicates falls below the numDupLimit value
+        if ( storedValues instanceof BTreeRedirect )
+        {
+            BTree tree = getBTree( ( BTreeRedirect ) storedValues );
+            Object first = null;
+            while ( values.hasMoreElements() )
+            {
+                Object val = values.nextElement();
+                
+                if ( removeDupFromBTree( tree, val ) )
+                {
+                    count--;
+                    
+                    if ( first == null )
+                    {
+                        first = val;
+                    }
+                }
+            }
+            
+            return first;
+        }
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
+    }
+
+
+    /**
+     * @see Table#remove(java.lang.Object)
+     */
+    public Object remove( Object key ) throws IOException
+    {
+        Object returned = removeRaw( key );
+
+        if ( null == returned )
+        {
+            return null;
+        }
+
+        if ( ! allowsDuplicates )
+        {
+            this.count--;
+            return returned;
+        }
+
+        if ( returned instanceof TreeSet )
+        {
+            TreeSet set = ( TreeSet ) returned;
+            this.count -= set.size();
+            return set.first();
+        }
+        
+        if ( returned instanceof BTreeRedirect )
+        {
+            BTree tree = getBTree( ( BTreeRedirect ) returned );
+            this.count -= tree.size();
+            return removeAll( tree );
+        }
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
+    }
+
+
+    /**
+     * @see Table#listValues(java.lang.Object)
+     */
+    public Enumeration listValues( Object key ) throws IOException
+    {
+        if ( !allowsDuplicates )
+        {
+            Object value = get( key );
+
+            if ( null == value )
+            {
+                return new EmptyEnumeration();
+            }
+            else
+            {
+                Tuple tuple = new Tuple( key, value );
+                return new SingletonEnumeration( tuple );
+            }
+        }
+
+        Object values = getRaw( key );
+        
+        if ( values == null )
+        {
+            return new EmptyEnumeration();
+        }
+        
+        if ( values instanceof TreeSet )
+        {
+            TreeSet set = ( TreeSet ) values;
+            final Iterator list = set.iterator();
+            return new Enumeration()
+            {
+                public Object nextElement()
+                {
+                    return list.next();
+                }
+
+                public boolean hasMoreElements()
+                {
+                    return list.hasNext();
+                }
+            };
+        }
+        
+        if ( values instanceof BTreeRedirect )
+        {
+            BTree tree = getBTree( ( BTreeRedirect ) values );
+            return new BTreeEnumeration( tree );
+        }
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
+    }
+
+
+    // ------------------------------------------------------------------------
+    // listTuple Overloads 
+    // ------------------------------------------------------------------------
+
+    /**
+     * @see org.apache.directory.server.core.partition.impl.btree.Table#listTuples()
+     */
+    public TupleCursor listTuples() throws IOException
+    {
+        JdbmTupleBrowser browser = new JdbmTupleBrowser( bt.browse() );
+        TupleCursor list = new NoDupsTupleCursor( browser, true );
+
+        if ( allowsDuplicates )
+        {
+            return new DupsEnumeration( this, ( NoDupsTupleCursor ) list );
+        }
+
+        return list;
+    }
+
+
+    /**
+     * @see org.apache.directory.server.core.partition.impl.btree.Table#listTuples(java.lang.Object)
+     */
+    @SuppressWarnings("unchecked")
+    public TupleCursor listTuples( Object key ) throws IOException
+    {
+        // Handle single and zero value returns without duplicates enabled
+        if ( !allowsDuplicates )
+        {
+            Object val = getRaw( key );
+
+            if ( null == val )
+            {
+                return new EmptyTupleCursor();
+            }
+            else
+            {
+                return new SingletonTupleCursor( new Tuple( key, getRaw( key ) ) );
+            }
+        }
+
+        Object values = getRaw( key );
+
+        if ( values == null )
+        {
+            return new EmptyTupleCursor();
+        }
+        
+        if ( values instanceof TreeSet )
+        {
+            TreeSet set = ( TreeSet ) values;
+            Object[] objs = new Object[set.size()];
+            objs = set.toArray( objs );
+            ArrayIterator iterator = new ArrayIterator( objs );
+            return new IteratorTupleCursor( key, iterator );
+        }
+        
+        if ( values instanceof BTreeRedirect )
+        {
+            return new BTreeTupleEnumeration( getBTree( ( BTreeRedirect ) values ), key );
+        }
+
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
+    }
+
+
+    /**
+     * @see Table#listTuples(java.lang.Object,
+     * boolean)
+     */
+    public TupleCursor listTuples( Object key, boolean isGreaterThan ) throws IOException
+    {
+        TupleCursor list = null;
+
+        if ( isGreaterThan )
+        {
+            JdbmTupleBrowser browser = new JdbmTupleBrowser( bt.browse( key ) );
+            list = new NoDupsTupleCursor( browser, isGreaterThan );
+        }
+        else
+        {
+            /* According to the jdbm docs a browser is positioned right
+             * before a key greater than or equal to key.  getNext() will
+             * return the next tuple with a key greater than or equal to
+             * key.  getPrevious() used in descending scans for less than
+             * for equal to comparisions will not.  We need to advance
+             * forward once and check if the returned Tuple key equals
+             * key.  If it does then we do nothing feeding in the browser
+             * to the NoDupsCursor.  If it does not we call getPrevious and
+             * pass it into the NoDupsCursor constructor.
+             */
+            jdbm.helper.Tuple tuple = new jdbm.helper.Tuple();
+            TupleBrowser browser = bt.browse( key );
+
+            if ( browser.getNext( tuple ) )
+            {
+                Object greaterKey = tuple.getKey();
+
+                if ( 0 != comparator.compareKey( key, greaterKey ) )
+                {
+                    // Make sure we don't return greaterKey in cursor
+                    browser.getPrevious( tuple );
+                }
+            }
+
+            // If greaterKey != key above then it will not be returned.
+            list = new NoDupsTupleCursor( new JdbmTupleBrowser( browser ), isGreaterThan );
+        }
+
+        if ( allowsDuplicates )
+        {
+            list = new DupsEnumeration( this, ( NoDupsTupleCursor ) list );
+        }
+
+        return list;
+    }
+
+
+    /**
+     * @see org.apache.directory.server.core.partition.impl.btree.Table#listTuples(java.lang.Object,
+     * java.lang.Object, boolean)
+     */
+    @SuppressWarnings("unchecked")
+    public TupleCursor listTuples( Object key, Object val, boolean isGreaterThan ) throws IOException
+    {
+        if ( !allowsDuplicates )
+        {
+            throw new UnsupportedOperationException( "Cannot list tuples over duplicates on table that " +
+                    "does not support duplicates." );
+        }
+
+        Object values = getRaw( key );
+        
+        if ( values == null )
+        {
+            return new EmptyTupleCursor();
+        }
+
+        if ( values instanceof TreeSet )
+        {
+            TreeSet set = ( TreeSet ) values;
+    
+            if ( isGreaterThan )
+            {
+                Set tailSet = set.tailSet( val );
+                
+                if ( tailSet.isEmpty() )
+                {
+                    return new EmptyTupleCursor();
+                }
+                
+                Object[] objs = new Object[tailSet.size()];
+                objs = tailSet.toArray( objs );
+                ArrayIterator iterator = new ArrayIterator( objs );
+                return new IteratorTupleCursor( key, iterator );
+            }
+            else
+            {
+                // Get all values from the smallest upto val and put them into
+                // a list.  They will be in ascending order so we need to reverse
+                // the list after adding val which is not included in headSet.
+                SortedSet headset = set.headSet( val );
+                ArrayList list = new ArrayList( headset.size() + 1 );
+                list.addAll( headset );
+    
+                // Add largest value (val) if it is in the set.  TreeSet.headSet
+                // does not get val if val is in the set.  So we add it now to
+                // the end of the list.  List is now ascending from smallest to
+                // val
+                if ( set.contains( val ) )
+                {
+                    list.add( val );
+                }
+    
+                // Reverse the list now we have descending values from val to the
+                // smallest value that key has.  Return tuple cursor over list.
+                Collections.reverse( list );
+                return new IteratorTupleCursor( key, list.iterator() );
+            }
+        }
+        
+        if ( values instanceof BTreeRedirect )
+        {
+            return new BTreeTupleEnumeration( getBTree( ( BTreeRedirect ) values ), 
+                comparator.getValueComparator(), key, val, isGreaterThan );
+        }
+
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
+    }
+    
+
+    // ------------------------------------------------------------------------
+    // Maintenance Operations 
+    // ------------------------------------------------------------------------
+
+    /**
+     * @see Table#close()
+     */
+    public synchronized void close() throws IOException
+    {
+        sync();
+    }
+
+
+    /**
+     * Synchronizes the buffers with disk.
+     *
+     * @throws IOException if errors are encountered on the flush
+     */
+    public void sync() throws IOException
+    {
+        long recId = recMan.getNamedObject( name + SZSUFFIX );
+
+        if ( 0 == recId )
+        {
+            recId = recMan.insert( new Integer( count ) );
+        }
+        else
+        {
+            recMan.update( recId, new Integer( count ) );
+        }
+    }
+
+
+    // ------------------------------------------------------------------------
+    // Private Utility Methods 
+    // ------------------------------------------------------------------------
+
+    
+    /**
+     * Gets a Tuple value from the btree while wrapping any IOExceptions with a 
+     * IOException.
+     *
+     * @param key the key of the Tuple to get the value of 
+     * @return the raw value object from the btree
+     * @throws IOException if there are any problems accessing the btree.
+     */
+    private Object getRaw( Object key ) throws IOException
+    {
+        Object val = null;
+
+        if ( null == key )
+        {
+            return null;
+        }
+
+        if ( !allowsDuplicates )
+        {
+            val = bt.find( key );
+        }
+        else
+        {
+            val = bt.find( key );
+        }
+
+        return val;
+    }
+
+
+    /**
+     * Puts a Tuple into the btree while wrapping any IOExceptions with a 
+     * IOException.
+     *
+     * @param key the key of the Tuple to put
+     * @param value the value of the Tuple to put
+     * @param doReplace whether or not to replace the object if it exists
+     * @return the raw value object removed from the btree on replacement
+     * @throws IOException if there are any problems accessing the btree.
+     */
+    private Object putRaw( Object key, Object value, boolean doReplace ) throws IOException
+    {
+        return bt.insert( key, value, doReplace );
+    }
+
+
+    /**
+     * Removes a entry from the btree while wrapping any IOExceptions with a 
+     * IOException.
+     *
+     * @param key the key of the Tuple to remove
+     * @return the raw value object removed from the btree
+     * @throws IOException if there are any problems accessing the btree.
+     */
+    private Object removeRaw( Object key ) throws IOException
+    {
+        return bt.remove( key );
+    }
+
+
+    BTree getBTree( BTreeRedirect redirect ) throws IOException
+    {
+        if ( duplicateBtrees.containsKey( redirect.getRecId() ) )
+        {
+            return ( BTree ) duplicateBtrees.get( redirect.getRecId() );
+        }
+        
+        BTree tree = BTree.load( recMan, redirect.getRecId().longValue() );
+        duplicateBtrees.put( redirect.getRecId(), tree );
+        return tree;
+    }
+
+
+    private Object firstKey ( BTree tree ) throws IOException
+    {
+        jdbm.helper.Tuple tuple = new jdbm.helper.Tuple();
+        boolean success = tree.browse().getNext( tuple );
+        
+        if ( success )
+        {
+            return tuple.getKey();
+        }
+        else 
+        {
+            return null;
+        }
+    }
+
+    
+    private boolean btreeHas( BTree tree, Object key, boolean isGreaterThan ) throws IOException
+    {
+        jdbm.helper.Tuple tuple = new jdbm.helper.Tuple();
+        TupleBrowser browser = tree.browse( key );
+        if ( isGreaterThan )
+        {
+            boolean success = browser.getNext( tuple );
+            if ( success )
+            {
+                return true;
+            }
+            else
+            {
+                return false;
+            }
+        }
+        else
+        {
+            boolean success = browser.getPrevious( tuple );
+            if ( success )
+            {
+                return true;
+            }
+            else
+            {
+                /*
+                 * Calls to getPrevious() will return a lower key even
+                 * if there exists a key equal to the one searched
+                 * for.  Since isGreaterThan when false really means
+                 * 'less than or equal to' we must check to see if 
+                 * the key in front is equal to the key argument provided.
+                 */
+                success = browser.getNext( tuple );
+                if ( success )
+                {
+                    Object biggerKey = tuple.getKey();
+                    if ( comparator.compareValue( key, biggerKey ) == 0 )
+                    {
+                        return true;
+                    }
+                }
+                return false;
+            }
+        }
+    }
+
+
+    private boolean btreeHas( BTree tree, Object key ) throws IOException
+    {
+        jdbm.helper.Tuple tuple = new jdbm.helper.Tuple();
+        TupleBrowser browser = tree.browse( key );
+        boolean success = browser.getNext( tuple );
+        if ( success )
+        {
+            if ( comparator.compareValue( key, tuple.getKey() ) == 0 )
+            {
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+    
+    private boolean insertDupIntoBTree( BTree tree, Object value ) throws IOException
+    {
+        Object replaced = tree.insert( value, EMPTY_BYTES, true );
+        return null == replaced;
+    }
+    
+
+    private boolean removeDupFromBTree( BTree tree, Object value ) throws IOException
+    {
+        Object removed = null;
+        if ( tree.find( value ) != null )
+        {
+            removed = tree.remove( value );
+        }
+        return null != removed;
+    }
+    
+
+    private static final byte[] EMPTY_BYTES = new byte[0];
+    private BTree convertToBTree( TreeSet set ) throws IOException
+    {
+        BTree tree = BTree.createInstance( recMan, comparator.getValueComparator() );
+        for ( Iterator ii = set.iterator(); ii.hasNext(); /**/ )
+        {
+            tree.insert( ii.next(), EMPTY_BYTES, true );
+        }
+        return tree;
+    }
+    
+    
+    private Object removeAll( BTree tree ) throws IOException
+    {
+        Object first = null;
+        jdbm.helper.Tuple jdbmTuple = new jdbm.helper.Tuple();
+        TupleBrowser browser;
+        browser = tree.browse();
+        while( browser.getNext( jdbmTuple ) )
+        {
+            tree.remove( jdbmTuple.getKey() );
+            if ( first == null )
+            {
+                first = jdbmTuple.getKey();
+            }
+        }
+        return first;
+    }
+}
+

Added: incubator/felix/sandbox/akarasulu/bundledb/src/main/java/org/apache/felix/bundledb/btree/jdbm/JdbmTupleBrowser.java
URL: http://svn.apache.org/viewvc/incubator/felix/sandbox/akarasulu/bundledb/src/main/java/org/apache/felix/bundledb/btree/jdbm/JdbmTupleBrowser.java?view=auto&rev=500151
==============================================================================
--- incubator/felix/sandbox/akarasulu/bundledb/src/main/java/org/apache/felix/bundledb/btree/jdbm/JdbmTupleBrowser.java (added)
+++ incubator/felix/sandbox/akarasulu/bundledb/src/main/java/org/apache/felix/bundledb/btree/jdbm/JdbmTupleBrowser.java Thu Jan 25 22:20:18 2007
@@ -0,0 +1,94 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *  
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *  
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License. 
+ *  
+ */
+package org.apache.felix.bundledb.btree.jdbm;
+
+
+import java.io.IOException;
+
+import org.apache.felix.bundledb.btree.Tuple;
+import org.apache.felix.bundledb.btree.TupleBrowser;
+
+
+/**
+ * TupleBrowser wrapper for Jdbm based TupleBrowsers.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev: 491471 $
+ */
+public class JdbmTupleBrowser implements TupleBrowser
+{
+    /** underlying wrapped jdbm.helper.TupleBrowser */
+    private jdbm.helper.TupleBrowser jdbmBrowser;
+    /** safe temp jdbm.helper.Tuple used to store next/previous tuples */
+    private jdbm.helper.Tuple jdbmTuple = new jdbm.helper.Tuple();
+
+
+    /**
+     * Creates a JdbmTupleBrowser.
+     *
+     * @param jdbmBrowser JDBM browser to wrap.
+     */
+    public JdbmTupleBrowser(jdbm.helper.TupleBrowser jdbmBrowser)
+    {
+        this.jdbmBrowser = jdbmBrowser;
+    }
+
+
+    /**
+     * @see TupleBrowser#getNext(Tuple)
+     */
+    public boolean getNext( Tuple tuple ) throws IOException
+    {
+        synchronized ( jdbmTuple )
+        {
+            if ( jdbmBrowser.getNext( jdbmTuple ) )
+            {
+                tuple.setKey( jdbmTuple.getKey() );
+                tuple.setValue( jdbmTuple.getValue() );
+                return true;
+            }
+            else
+            {
+                return false;
+            }
+        }
+    }
+
+
+    /**
+     * @see TupleBrowser#getPrevious(Tuple)
+     */
+    public boolean getPrevious( Tuple tuple ) throws IOException
+    {
+        synchronized ( jdbmTuple )
+        {
+            if ( jdbmBrowser.getPrevious( jdbmTuple ) )
+            {
+                tuple.setKey( jdbmTuple.getKey() );
+                tuple.setValue( jdbmTuple.getValue() );
+                return true;
+            }
+            else
+            {
+                return false;
+            }
+        }
+    }
+}

Added: incubator/felix/sandbox/akarasulu/bundledb/src/main/java/org/apache/felix/bundledb/btree/jdbm/SingletonEnumeration.java
URL: http://svn.apache.org/viewvc/incubator/felix/sandbox/akarasulu/bundledb/src/main/java/org/apache/felix/bundledb/btree/jdbm/SingletonEnumeration.java?view=auto&rev=500151
==============================================================================
--- incubator/felix/sandbox/akarasulu/bundledb/src/main/java/org/apache/felix/bundledb/btree/jdbm/SingletonEnumeration.java (added)
+++ incubator/felix/sandbox/akarasulu/bundledb/src/main/java/org/apache/felix/bundledb/btree/jdbm/SingletonEnumeration.java Thu Jan 25 22:20:18 2007
@@ -0,0 +1,74 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *  
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *  
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License. 
+ *  
+ */
+package org.apache.felix.bundledb.btree.jdbm;
+
+
+import java.util.Enumeration;
+
+import java.util.NoSuchElementException;
+
+
+/**
+ * A Enumeration over a single element.
+ * 
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Revision: 437007 $
+ */
+public class SingletonEnumeration implements Enumeration
+{
+    /** The singleton element to return */
+    private final Object element;
+
+    /** Can we return a element */
+    private boolean hasMore = true;
+
+
+    /**
+     * Creates a Enumeration over a single element.
+     */
+    public SingletonEnumeration( final Object element )
+    {
+        this.element = element;
+    }
+
+
+    /**
+     * @see java.util.Enumeration#hasMoreElements()
+     */
+    public boolean hasMoreElements()
+    {
+        return hasMore;
+    }
+
+
+    /**
+     * @see java.util.Enumeration#nextElement()
+     */
+    public Object nextElement()
+    {
+        if ( hasMore )
+        {
+            hasMore = false;
+            return element;
+        }
+
+        throw new NoSuchElementException();
+    }
+}

Added: incubator/felix/sandbox/akarasulu/bundledb/src/main/java/org/apache/felix/bundledb/btree/jdbm/SingletonTupleCursor.java
URL: http://svn.apache.org/viewvc/incubator/felix/sandbox/akarasulu/bundledb/src/main/java/org/apache/felix/bundledb/btree/jdbm/SingletonTupleCursor.java?view=auto&rev=500151
==============================================================================
--- incubator/felix/sandbox/akarasulu/bundledb/src/main/java/org/apache/felix/bundledb/btree/jdbm/SingletonTupleCursor.java (added)
+++ incubator/felix/sandbox/akarasulu/bundledb/src/main/java/org/apache/felix/bundledb/btree/jdbm/SingletonTupleCursor.java Thu Jan 25 22:20:18 2007
@@ -0,0 +1,78 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *  
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *  
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License. 
+ *  
+ */
+package org.apache.felix.bundledb.btree.jdbm;
+
+
+import org.apache.felix.bundledb.btree.Tuple;
+import org.apache.felix.bundledb.btree.TupleCursor;
+
+import java.util.NoSuchElementException;
+
+
+/**
+ * A TupleCursor over a single element.
+ * 
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Revision: 437007 $
+ */
+public class SingletonTupleCursor implements TupleCursor
+{
+    /** The singleton element to return */
+    private final Tuple tuple;
+
+    /** Can we return a element */
+    private boolean hasMore = true;
+
+
+    /**
+     * Creates a TupleCursor over a single element.
+     */
+    public SingletonTupleCursor( final Tuple tuple )
+    {
+        this.tuple = tuple;
+    }
+
+
+    /**
+     * Makes calls to hasMore to false even if we had more.
+     */
+    public void close()
+    {
+        hasMore = false;
+    }
+
+
+    public boolean hasMore()
+    {
+        return hasMore;
+    }
+
+
+    public Tuple next()
+    {
+        if ( hasMore )
+        {
+            hasMore = false;
+            return tuple;
+        }
+
+        throw new NoSuchElementException();
+    }
+}



Mime
View raw message