directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
Subject svn commit: r762544 - in /directory/apacheds/branches/ldif-partition/avl-partition/src/main/java/org/apache/directory/server/core/partition/avl: AvlIndex.java AvlStore.java
Date Mon, 06 Apr 2009 22:34:32 GMT
Author: akarasulu
Date: Mon Apr  6 22:34:31 2009
New Revision: 762544

URL: http://svn.apache.org/viewvc?rev=762544&view=rev
Log:
Finishing off implementation for Avl tree - testing still needed

Modified:
    directory/apacheds/branches/ldif-partition/avl-partition/src/main/java/org/apache/directory/server/core/partition/avl/AvlIndex.java
    directory/apacheds/branches/ldif-partition/avl-partition/src/main/java/org/apache/directory/server/core/partition/avl/AvlStore.java

Modified: directory/apacheds/branches/ldif-partition/avl-partition/src/main/java/org/apache/directory/server/core/partition/avl/AvlIndex.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/ldif-partition/avl-partition/src/main/java/org/apache/directory/server/core/partition/avl/AvlIndex.java?rev=762544&r1=762543&r2=762544&view=diff
==============================================================================
--- directory/apacheds/branches/ldif-partition/avl-partition/src/main/java/org/apache/directory/server/core/partition/avl/AvlIndex.java (original)
+++ directory/apacheds/branches/ldif-partition/avl-partition/src/main/java/org/apache/directory/server/core/partition/avl/AvlIndex.java Mon Apr  6 22:34:31 2009
@@ -32,24 +32,29 @@
 
 
 /**
- * TODO AvlIndex.
+ * An Index backed by an AVL Tree.
  *
  * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
  * @version $Rev$, $Date$
  */
 public class AvlIndex<K,O> implements Index<K, O>
 {
-    private final Normalizer normalizer;
+    private Normalizer normalizer;
     private AttributeType attributeType;
     private AvlTable<K,Long> forward;
     private AvlTable<Long,K> reverse;
     private String attributeId;
     
     
-    public AvlIndex( String attributeId, AttributeType attributeType ) throws Exception
+    public AvlIndex( String attributeId ) throws Exception
     {
-        this.attributeType = attributeType;
         this.attributeId = attributeId;
+    }
+    
+    
+    void initialize( AttributeType attributeType ) throws Exception
+    {
+        this.attributeType = attributeType;
 
         MatchingRule mr = attributeType.getEquality();
         

Modified: directory/apacheds/branches/ldif-partition/avl-partition/src/main/java/org/apache/directory/server/core/partition/avl/AvlStore.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/ldif-partition/avl-partition/src/main/java/org/apache/directory/server/core/partition/avl/AvlStore.java?rev=762544&r1=762543&r2=762544&view=diff
==============================================================================
--- directory/apacheds/branches/ldif-partition/avl-partition/src/main/java/org/apache/directory/server/core/partition/avl/AvlStore.java (original)
+++ directory/apacheds/branches/ldif-partition/avl-partition/src/main/java/org/apache/directory/server/core/partition/avl/AvlStore.java Mon Apr  6 22:34:31 2009
@@ -17,35 +17,57 @@
  *   under the License.
  *
  */
-
 package org.apache.directory.server.core.partition.avl;
 
-import java.io.File;
+
+import java.util.ArrayList;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 
+import org.apache.directory.server.constants.ApacheSchemaConstants;
+import org.apache.directory.server.core.cursor.Cursor;
+import org.apache.directory.server.core.entry.ClonedServerEntry;
+import org.apache.directory.server.core.entry.ServerAttribute;
+import org.apache.directory.server.core.entry.ServerBinaryValue;
 import org.apache.directory.server.core.entry.ServerEntry;
+import org.apache.directory.server.core.entry.ServerStringValue;
 import org.apache.directory.server.schema.registries.AttributeTypeRegistry;
 import org.apache.directory.server.schema.registries.OidRegistry;
 import org.apache.directory.server.schema.registries.Registries;
 import org.apache.directory.server.xdbm.Index;
 import org.apache.directory.server.xdbm.IndexCursor;
+import org.apache.directory.server.xdbm.IndexEntry;
 import org.apache.directory.server.xdbm.IndexNotFoundException;
+import org.apache.directory.server.xdbm.LongComparator;
 import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.shared.ldap.constants.SchemaConstants;
+import org.apache.directory.shared.ldap.entry.EntryAttribute;
 import org.apache.directory.shared.ldap.entry.Modification;
 import org.apache.directory.shared.ldap.entry.ModificationOperation;
+import org.apache.directory.shared.ldap.entry.Value;
+import org.apache.directory.shared.ldap.exception.LdapNameNotFoundException;
+import org.apache.directory.shared.ldap.exception.LdapSchemaViolationException;
+import org.apache.directory.shared.ldap.message.ResultCodeEnum;
+import org.apache.directory.shared.ldap.name.AttributeTypeAndValue;
 import org.apache.directory.shared.ldap.name.LdapDN;
 import org.apache.directory.shared.ldap.name.Rdn;
 import org.apache.directory.shared.ldap.schema.AttributeType;
+import org.apache.directory.shared.ldap.schema.MatchingRule;
+import org.apache.directory.shared.ldap.util.NamespaceTools;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
 
 /**
  * A Store implementation backed by in memory AVL trees.
+ * 
+ * TODO - this class is extremely like the JdbmStore implementation of the
+ * Store interface which tells us that it's best for us to have some kind 
+ * of abstract class.
  *
  * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
  * @version $Rev$, $Date$
@@ -83,23 +105,126 @@
     private AvlIndex<Long,E> subAliasIdx;
     
     /** a map of attributeType numeric ID to user userIndices */
-    private Map<String, ? extends Index<?,E>> userIndices 
+    private Map<String, AvlIndex<?,E>> userIndices 
         = new HashMap<String, AvlIndex<?,E>>();
     
     /** a map of attributeType numeric ID to system userIndices */
-    private Map<String, ? extends Index<?,E>> systemIndices 
+    private Map<String, AvlIndex<?,E>> systemIndices 
         = new HashMap<String, AvlIndex<?,E>>();
     
     /** true if initialized */
     private boolean initialized;
+    
+    /** 
+     * TODO we need to check out why we have so many suffix 
+     * dn and string accessor/mutators on both Store and Partition
+     * interfaces.  I think a lot of this comes from the fact 
+     * that we implemented LdapDN to have both the up and norm
+     * names.
+     */
+    private LdapDN suffixDn;
+
+    private String name;
 
 
     /**
      * {@inheritDoc}
      */
+    @SuppressWarnings("unchecked")
     public void add( LdapDN normName, ServerEntry entry ) throws Exception
     {
-        // TODO Auto-generated method stub
+        if ( entry instanceof ClonedServerEntry )
+        {
+            throw new Exception( "Cannot store a ClonedServerEntry" );
+        }
+        
+        Long id;
+        Long parentId;
+        
+        id = master.getNextId();
+
+        //
+        // Suffix entry cannot have a parent since it is the root so it is 
+        // capped off using the zero value which no entry can have since 
+        // entry sequences start at 1.
+        //
+
+        LdapDN parentDn = null;
+
+        if ( normName.getNormName().equals( suffixDn.getNormName() ) )
+        {
+            parentId = 0L;
+        }
+        else
+        {
+            parentDn = ( LdapDN ) normName.clone();
+            parentDn.remove( parentDn.size() - 1 );
+            parentId = getEntryId( parentDn.toString() );
+        }
+
+        // don't keep going if we cannot find the parent Id
+        if ( parentId == null )
+        {
+            throw new LdapNameNotFoundException( "Id for parent '" + parentDn + "' not found!" );
+        }
+
+        EntryAttribute objectClass = entry.get( OBJECT_CLASS_AT );
+
+        if ( objectClass == null )
+        {
+            String msg = "Entry " + normName.getUpName() + " contains no objectClass attribute: " + entry;
+            throw new LdapSchemaViolationException( msg, ResultCodeEnum.OBJECT_CLASS_VIOLATION );
+        }
+
+        // Start adding the system userIndices
+        // Why bother doing a lookup if this is not an alias.
+
+        if ( objectClass.contains( SchemaConstants.ALIAS_OC ) )
+        {
+            EntryAttribute aliasAttr = entry.get( ALIASED_OBJECT_NAME_AT );
+            addAliasIndices( id, normName, aliasAttr.getString() );
+        }
+
+        if ( !Character.isDigit( normName.toNormName().charAt( 0 ) ) )
+        {
+            throw new IllegalStateException( "Not a normalized name: " + normName.toNormName() );
+        }
+
+        ndnIdx.add( normName.toNormName(), id );
+        updnIdx.add( normName.getUpName(), id );
+        oneLevelIdx.add( parentId, id );
+        
+        Long tempId = parentId;
+        while( tempId != null && tempId != 0 && tempId != 1 )
+        {
+            subLevelIdx.add( tempId, id );
+            tempId = getParentId( tempId );
+        }
+        subLevelIdx.add( id, id );
+        
+        // Now work on the user defined userIndices
+        for ( EntryAttribute attribute : entry )
+        {
+            String attributeOid = ( ( ServerAttribute ) attribute ).getAttributeType().getOid();
+
+            if ( hasUserIndexOn( attributeOid ) )
+            {
+                Index<Object,E> idx = ( Index<Object,E> ) getUserIndex( attributeOid );
+
+                // here lookup by attributeId is OK since we got attributeId from 
+                // the entry via the enumeration - it's in there as is for sure
+
+                for ( Value<?> value : attribute )
+                {
+                    idx.add( value.get(), id );
+                }
+
+                // Adds only those attributes that are indexed
+                existenceIdx.add( attributeOid, id );
+            }
+        }
+
+        master.put( id, entry );
     }
 
     
@@ -108,7 +233,14 @@
      */
     public void addIndex( Index<?, E> index ) throws Exception
     {
-        // TODO Auto-generated method stub
+        if ( index instanceof AvlIndex )
+        {
+            userIndices.put( index.getAttributeId(), ( AvlIndex<?,E> ) index );
+        }
+        else
+        {
+            userIndices.put( index.getAttributeId(), ( AvlIndex<?,E> ) convert( index ) );
+        }
     }
 
     
@@ -117,17 +249,61 @@
      */
     public int count() throws Exception
     {
-        // TODO Auto-generated method stub
-        return 0;
+        return master.count();
     }
 
 
     /**
      * {@inheritDoc}
      */
+    @SuppressWarnings("unchecked")
     public void delete( Long id ) throws Exception
     {
-        // TODO Auto-generated method stub
+        ServerEntry entry = lookup( id );
+        Long parentId = getParentId( id );
+
+        EntryAttribute objectClass = entry.get( OBJECT_CLASS_AT );
+
+        if ( objectClass.contains( SchemaConstants.ALIAS_OC ) )
+        {
+            dropAliasIndices( id );
+        }
+
+        ndnIdx.drop( id );
+        updnIdx.drop( id );
+        oneLevelIdx.drop( id );
+
+        if( parentId != 1 )// should not use getParentId() to compare, onelevel index drops the 'id'
+        {
+            subLevelIdx.drop( id );
+        }
+        
+        // Remove parent's reference to entry only if entry is not the upSuffix
+        if ( !parentId.equals( 0L ) )
+        {
+            oneLevelIdx.drop( parentId, id );
+        }
+
+        for ( EntryAttribute attribute : entry )
+        {
+            String attributeOid = ( ( ServerAttribute ) attribute ).getAttributeType().getOid();
+
+            if ( hasUserIndexOn( attributeOid ) )
+            {
+                Index<?,E> index = getUserIndex( attributeOid );
+
+                // here lookup by attributeId is ok since we got attributeId from 
+                // the entry via the enumeration - it's in there as is for sure
+                for ( Value<?> value : attribute )
+                {
+                    ( ( AvlIndex ) index ).drop( value.get(), id );
+                }
+
+                existenceIdx.drop( attributeOid, id );
+            }
+        }
+
+        master.delete( id );
     }
 
 
@@ -136,7 +312,6 @@
      */
     public void destroy() throws Exception
     {
-        // TODO Auto-generated method stub
     }
 
     
@@ -145,18 +320,7 @@
      */
     public Index<String, E> getAliasIndex()
     {
-        // TODO Auto-generated method stub
-        return null;
-    }
-
-    
-    /**
-     * {@inheritDoc}
-     */
-    public int getCacheSize()
-    {
-        // TODO Auto-generated method stub
-        return 0;
+        return aliasIdx;
     }
 
     
@@ -165,8 +329,7 @@
      */
     public int getChildCount( Long id ) throws Exception
     {
-        // TODO Auto-generated method stub
-        return 0;
+        return oneLevelIdx.count( id );
     }
 
     
@@ -175,8 +338,7 @@
      */
     public String getEntryDn( Long id ) throws Exception
     {
-        // TODO Auto-generated method stub
-        return null;
+        return ndnIdx.reverseLookup( id );
     }
 
 
@@ -185,8 +347,7 @@
      */
     public Long getEntryId( String dn ) throws Exception
     {
-        // TODO Auto-generated method stub
-        return null;
+        return ndnIdx.forwardLookup( dn );
     }
 
     
@@ -195,8 +356,7 @@
      */
     public String getEntryUpdn( Long id ) throws Exception
     {
-        // TODO Auto-generated method stub
-        return null;
+        return updnIdx.reverseLookup( id );
     }
 
 
@@ -205,8 +365,8 @@
      */
     public String getEntryUpdn( String dn ) throws Exception
     {
-        // TODO Auto-generated method stub
-        return null;
+        Long id = ndnIdx.forwardLookup( dn );
+        return updnIdx.reverseLookup( id );
     }
 
 
@@ -215,8 +375,7 @@
      */
     public String getName()
     {
-        // TODO Auto-generated method stub
-        return null;
+        return name;
     }
 
 
@@ -225,8 +384,7 @@
      */
     public Index<String, E> getNdnIndex()
     {
-        // TODO Auto-generated method stub
-        return null;
+        return ndnIdx;
     }
 
     
@@ -235,8 +393,7 @@
      */
     public Index<Long, E> getOneAliasIndex()
     {
-        // TODO Auto-generated method stub
-        return null;
+        return oneAliasIdx;
     }
 
 
@@ -245,8 +402,7 @@
      */
     public Index<Long, E> getOneLevelIndex()
     {
-        // TODO Auto-generated method stub
-        return null;
+        return oneLevelIdx;
     }
 
     
@@ -255,8 +411,8 @@
      */
     public Long getParentId( String dn ) throws Exception
     {
-        // TODO Auto-generated method stub
-        return null;
+        Long childId = ndnIdx.forwardLookup( dn );
+        return oneLevelIdx.reverseLookup( childId );
     }
 
     
@@ -265,8 +421,7 @@
      */
     public Long getParentId( Long childId ) throws Exception
     {
-        // TODO Auto-generated method stub
-        return null;
+        return oneLevelIdx.reverseLookup( childId );
     }
 
     
@@ -275,8 +430,7 @@
      */
     public Index<String, E> getPresenceIndex()
     {
-        // TODO Auto-generated method stub
-        return null;
+        return existenceIdx;
     }
 
     
@@ -285,8 +439,7 @@
      */
     public String getProperty( String propertyName ) throws Exception
     {
-        // TODO Auto-generated method stub
-        return null;
+        return master.getProperty( propertyName );
     }
 
 
@@ -295,8 +448,7 @@
      */
     public Index<Long, E> getSubAliasIndex()
     {
-        // TODO Auto-generated method stub
-        return null;
+        return subAliasIdx;
     }
 
 
@@ -305,8 +457,7 @@
      */
     public Index<Long, E> getSubLevelIndex()
     {
-        // TODO Auto-generated method stub
-        return null;
+        return subLevelIdx;
     }
 
     
@@ -315,8 +466,7 @@
      */
     public LdapDN getSuffix()
     {
-        // TODO Auto-generated method stub
-        return null;
+        return suffixDn;
     }
 
 
@@ -325,8 +475,7 @@
      */
     public String getSuffixDn()
     {
-        // TODO Auto-generated method stub
-        return null;
+        return suffixDn.getUpName();
     }
 
 
@@ -335,18 +484,17 @@
      */
     public Index<?, E> getSystemIndex( String id ) throws IndexNotFoundException
     {
-        // TODO Auto-generated method stub
-        return null;
+        return systemIndices.get( id );
     }
 
 
     /**
      * {@inheritDoc}
      */
-    public LdapDN getUpSuffix()
+    public LdapDN getUpSuffix() throws Exception
     {
-        // TODO Auto-generated method stub
-        return null;
+        // TODO fix this
+        return new LdapDN( suffixDn.getUpName() );
     }
 
 
@@ -355,8 +503,7 @@
      */
     public Index<String, E> getUpdnIndex()
     {
-        // TODO Auto-generated method stub
-        return null;
+        return updnIdx;
     }
 
 
@@ -365,8 +512,7 @@
      */
     public Index<?, E> getUserIndex( String id ) throws IndexNotFoundException
     {
-        // TODO Auto-generated method stub
-        return null;
+        return userIndices.get( id );
     }
 
 
@@ -375,18 +521,7 @@
      */
     public Set<? extends Index<?, E>> getUserIndices()
     {
-        // TODO Auto-generated method stub
-        return null;
-    }
-
-
-    /**
-     * {@inheritDoc}
-     */
-    public File getWorkingDirectory()
-    {
-        // TODO Auto-generated method stub
-        return null;
+        return new HashSet<Index<?,E>>( userIndices.values() );
     }
 
 
@@ -395,8 +530,7 @@
      */
     public boolean hasSystemIndexOn( String id ) throws Exception
     {
-        // TODO Auto-generated method stub
-        return false;
+        return systemIndices.containsKey( id );
     }
 
 
@@ -405,17 +539,139 @@
      */
     public boolean hasUserIndexOn( String id ) throws Exception
     {
-        // TODO Auto-generated method stub
-        return false;
+        return userIndices.containsKey( id );
     }
 
     
     /**
      * {@inheritDoc}
+     * TODO why this and initRegistries on Store interface ???
      */
     public void init( Registries registries ) throws Exception
     {
-        // TODO Auto-generated method stub
+        initRegistries( registries );
+        
+        OBJECT_CLASS_AT = attributeTypeRegistry.lookup( SchemaConstants.OBJECT_CLASS_AT );
+        ALIASED_OBJECT_NAME_AT = attributeTypeRegistry.lookup( SchemaConstants.ALIASED_OBJECT_NAME_AT );
+
+
+        // Create the master table (the table containing all the entries)
+        master = new AvlMasterTable<ServerEntry>( name, new LongComparator(), null, false );
+
+        // -------------------------------------------------------------------
+        // Initializes the user and system indices
+        // -------------------------------------------------------------------
+
+        setupSystemIndices();
+        setupUserIndices();
+        
+        // We are done !
+        initialized = true;
+    }    
+
+
+    private void setupSystemIndices() throws Exception
+    {
+        // let's check and make sure the supplied indices are OK
+        
+        if ( ndnIdx == null )
+        {
+            AttributeType attributeType = attributeTypeRegistry.lookup( ApacheSchemaConstants.APACHE_N_DN_OID );
+            ndnIdx = new AvlIndex<String,E>( ApacheSchemaConstants.APACHE_N_DN_OID );
+            ndnIdx.initialize( attributeType );
+            systemIndices.put( ApacheSchemaConstants.APACHE_N_DN_OID, ndnIdx );
+        }
+
+        if ( updnIdx == null )
+        {
+            AttributeType attributeType = attributeTypeRegistry.lookup( ApacheSchemaConstants.APACHE_UP_DN_OID );
+            updnIdx = new AvlIndex<String,E>( ApacheSchemaConstants.APACHE_UP_DN_OID );
+            updnIdx.initialize( attributeType );
+            systemIndices.put( ApacheSchemaConstants.APACHE_UP_DN_OID, updnIdx );
+        }
+
+        if ( existenceIdx == null )
+        {
+            AttributeType attributeType = attributeTypeRegistry.lookup( ApacheSchemaConstants.APACHE_EXISTANCE_OID );
+            existenceIdx = new AvlIndex<String,E>( ApacheSchemaConstants.APACHE_EXISTANCE_OID );
+            existenceIdx.initialize( attributeType );
+            systemIndices.put( ApacheSchemaConstants.APACHE_EXISTANCE_OID, existenceIdx );
+        }
+
+        if ( oneLevelIdx == null )
+        {
+            AttributeType attributeType = attributeTypeRegistry.lookup( ApacheSchemaConstants.APACHE_ONE_LEVEL_OID );
+            oneLevelIdx = new AvlIndex<Long,E>( ApacheSchemaConstants.APACHE_ONE_LEVEL_OID );
+            oneLevelIdx.initialize( attributeType );
+            systemIndices.put( ApacheSchemaConstants.APACHE_ONE_LEVEL_OID, oneLevelIdx );
+        }
+
+        if ( oneAliasIdx == null )
+        {
+            AttributeType attributeType = attributeTypeRegistry.lookup( ApacheSchemaConstants.APACHE_ONE_ALIAS_OID );
+            oneAliasIdx = new AvlIndex<Long,E>( ApacheSchemaConstants.APACHE_ONE_ALIAS_OID );
+            oneAliasIdx.initialize( attributeType );
+            systemIndices.put( ApacheSchemaConstants.APACHE_ONE_ALIAS_OID, oneAliasIdx );
+        }
+
+        if ( subAliasIdx == null )
+        {
+            AttributeType attributeType = attributeTypeRegistry.lookup( ApacheSchemaConstants.APACHE_SUB_ALIAS_OID );
+            subAliasIdx = new AvlIndex<Long,E>( ApacheSchemaConstants.APACHE_SUB_ALIAS_OID );
+            subAliasIdx.initialize( attributeType );
+            systemIndices.put( ApacheSchemaConstants.APACHE_SUB_ALIAS_OID, subAliasIdx );
+        }
+
+        if ( aliasIdx == null )
+        {
+            AttributeType attributeType = attributeTypeRegistry.lookup( ApacheSchemaConstants.APACHE_ALIAS_OID );
+            aliasIdx = new AvlIndex<String,E>( ApacheSchemaConstants.APACHE_ALIAS_OID );
+            aliasIdx.initialize( attributeType );
+            systemIndices.put( ApacheSchemaConstants.APACHE_ALIAS_OID, aliasIdx );
+        }
+        
+        if ( subLevelIdx == null )
+        {
+            AttributeType attributeType = attributeTypeRegistry.lookup( SUBLEVEL );
+            subLevelIdx = new AvlIndex<Long, E>( SUBLEVEL ); 
+            subLevelIdx.initialize( attributeType );
+            systemIndices.put( SUBLEVEL, subLevelIdx );
+        }
+    }
+
+
+    private void setupUserIndices() throws Exception
+    {
+        if ( userIndices != null && userIndices.size() > 0 )
+        {
+            Map<String, AvlIndex<?,E>> tmp = new HashMap<String, AvlIndex<?,E>>();
+            
+            for ( AvlIndex<?,E> index : userIndices.values() )
+            {
+                String oid = oidRegistry.getOid( index.getAttributeId() );
+                AttributeType attributeType = attributeTypeRegistry.lookup( oid );
+                
+                // Check that the attributeType has an EQUALITY matchingRule
+                MatchingRule mr = attributeType.getEquality();
+                
+                if ( mr != null )
+                {
+                    index.initialize( attributeTypeRegistry.lookup( oid ) );
+                    tmp.put( oid, index );
+                }
+                else
+                {
+                    LOG.error( "Cannot build an index for attribute '{}', no EQUALITY MatchingRule defined",
+                        attributeType.getName() );
+                }
+            }
+            
+            userIndices = tmp;
+        }
+        else
+        {
+            userIndices = new HashMap<String, AvlIndex<?,E>>();
+        }
     }
 
     
@@ -424,7 +680,8 @@
      */
     public void initRegistries( Registries registries )
     {
-        // TODO Auto-generated method stub
+        this.attributeTypeRegistry = registries.getAttributeTypeRegistry();
+        this.oidRegistry = registries.getOidRegistry();
     }
 
 
@@ -433,18 +690,7 @@
      */
     public boolean isInitialized()
     {
-        // TODO Auto-generated method stub
-        return false;
-    }
-
-    
-    /**
-     * {@inheritDoc}
-     */
-    public boolean isSyncOnWrite()
-    {
-        // TODO Auto-generated method stub
-        return false;
+        return initialized;
     }
 
 
@@ -453,8 +699,9 @@
      */
     public IndexCursor<Long, E> list( Long id ) throws Exception
     {
-        // TODO Auto-generated method stub
-        return null;
+        IndexCursor<Long,E> cursor = oneLevelIdx.forwardCursor( id );
+        cursor.beforeValue( id, null );
+        return cursor;
     }
 
     
@@ -463,71 +710,614 @@
      */
     public ServerEntry lookup( Long id ) throws Exception
     {
-        // TODO Auto-generated method stub
-        return null;
+        return master.get( id );
     }
 
     
     /**
-     * {@inheritDoc}
+     * Recursively modifies the distinguished name of an entry and the names of
+     * its descendants calling itself in the recursion.
+     *
+     * @param id the primary key of the entry
+     * @param updn User provided distinguished name to set as the new DN
+     * @param isMove whether or not the name change is due to a move operation
+     * which affects alias userIndices.
+     * @throws NamingException if something goes wrong
      */
-    public void modify( LdapDN dn, ModificationOperation modOp, ServerEntry mods ) throws Exception
+    private void modifyDn( Long id, LdapDN updn, boolean isMove ) throws Exception
     {
-        // TODO Auto-generated method stub
+        String aliasTarget;
+
+        // update normalized DN index
+        ndnIdx.drop( id );
+        if ( !updn.isNormalized() )
+        {
+            updn.normalize( attributeTypeRegistry.getNormalizerMapping() );
+        }
+        ndnIdx.add( updn.toNormName(), id );
+        
+        // update user provided DN index
+        updnIdx.drop( id );
+        updnIdx.add( updn.getUpName(), id );
+
+        /* 
+         * Read Alias Index Tuples
+         * 
+         * If this is a name change due to a move operation then the one and
+         * subtree userIndices for aliases were purged before the aliases were
+         * moved.  Now we must add them for each alias entry we have moved.  
+         * 
+         * aliasTarget is used as a marker to tell us if we're moving an 
+         * alias.  If it is null then the moved entry is not an alias.
+         */
+        if ( isMove )
+        {
+            aliasTarget = aliasIdx.reverseLookup( id );
+
+            if ( null != aliasTarget )
+            {
+                addAliasIndices( id, new LdapDN( getEntryDn( id ) ), aliasTarget );
+            }
+        }
+
+        Cursor<IndexEntry<Long,E>> children = list( id );
+        while ( children.next() )
+        {
+            // Get the child and its id
+            IndexEntry<Long,E> rec = children.get();
+            Long childId = rec.getId();
+
+            /* 
+             * Calculate the DN for the child's new name by copying the parents
+             * new name and adding the child's old upRdn to new name as its Rdn
+             */
+            LdapDN childUpdn = ( LdapDN ) updn.clone();
+            LdapDN oldUpdn = new LdapDN( getEntryUpdn( childId ) );
+
+            String rdn = oldUpdn.get( oldUpdn.size() - 1 );
+            LdapDN rdnDN = new LdapDN( rdn );
+            rdnDN.normalize( attributeTypeRegistry.getNormalizerMapping() );
+            childUpdn.add( rdnDN.getRdn() );
+
+            // Modify the child
+            ServerEntry entry = lookup( childId );
+            entry.setDn( childUpdn );
+            master.put( childId, entry );
+
+            // Recursively change the names of the children below
+            modifyDn( childId, childUpdn, isMove );
+        }
+        
+        children.close();
     }
 
-    
+
     /**
-     * {@inheritDoc}
+     * Adds a set of attribute values while affecting the appropriate userIndices.
+     * The entry is not persisted: it is only changed in anticipation for a put 
+     * into the master table.
+     *
+     * @param id the primary key of the entry
+     * @param entry the entry to alter
+     * @param mods the attribute and values to add 
+     * @throws Exception if index alteration or attribute addition fails
      */
-    public void modify( LdapDN dn, List<Modification> mods ) throws Exception
+    @SuppressWarnings("unchecked")
+    private void add( Long id, ServerEntry entry, EntryAttribute mods ) throws Exception
     {
-        // TODO Auto-generated method stub
+        if ( entry instanceof ClonedServerEntry )
+        {
+            throw new Exception( "Cannot store a ClonedServerEntry" );
+        }
+        
+        String modsOid = oidRegistry.getOid( mods.getId() );
+
+        if ( hasUserIndexOn( modsOid ) )
+        {
+            Index<?,E> index = getUserIndex( modsOid );
+
+            for ( Value<?> value : mods )
+            {
+                ( ( AvlIndex ) index ).add( value.get(), id );
+            }
+
+            // If the attr didn't exist for this id add it to existence index
+            if ( !existenceIdx.forward( modsOid, id ) )
+            {
+                existenceIdx.add( modsOid, id );
+            }
+        }
+
+        // add all the values in mods to the same attribute in the entry
+        AttributeType type = attributeTypeRegistry.lookup( modsOid );
+
+        for ( Value<?> value : mods )
+        {
+            entry.add( type, value );
+        }
+
+        if ( modsOid.equals( oidRegistry.getOid( SchemaConstants.ALIASED_OBJECT_NAME_AT ) ) )
+        {
+            String ndnStr = ndnIdx.reverseLookup( id );
+            addAliasIndices( id, new LdapDN( ndnStr ), mods.getString() );
+        }
     }
 
-    
+
     /**
-     * {@inheritDoc}
+     * Completely removes the set of values for an attribute having the values 
+     * supplied while affecting the appropriate userIndices.  The entry is not
+     * persisted: it is only changed in anticipation for a put into the master 
+     * table.  Note that an empty attribute w/o values will remove all the 
+     * values within the entry where as an attribute w/ values will remove those
+     * attribute values it contains.
+     *
+     * @param id the primary key of the entry
+     * @param entry the entry to alter
+     * @param mods the attribute and its values to delete
+     * @throws Exception if index alteration or attribute modification fails.
      */
-    public void move( LdapDN oldChildDn, LdapDN newParentDn, Rdn newRdn, boolean deleteOldRdn ) throws Exception
+    @SuppressWarnings("unchecked")
+    private void remove( Long id, ServerEntry entry, EntryAttribute mods ) throws Exception
     {
-        // TODO Auto-generated method stub
+        if ( entry instanceof ClonedServerEntry )
+        {
+            throw new Exception( "Cannot store a ClonedServerEntry" );
+        }
+        
+        String modsOid = oidRegistry.getOid( mods.getId() );
+
+        if ( hasUserIndexOn( modsOid ) )
+        {
+            Index<?,E> index = getUserIndex( modsOid );
+            
+            for ( Value<?> value : mods )
+            {
+                ( ( AvlIndex ) index ).drop( value.get(), id );
+            }
+
+            /* 
+             * If no attribute values exist for this entryId in the index then
+             * we remove the existance index entry for the removed attribute.
+             */
+            if ( null == index.reverseLookup( id ) )
+            {
+                existenceIdx.drop( modsOid, id );
+            }
+        }
+
+        AttributeType attrType = attributeTypeRegistry.lookup( modsOid );
+        /*
+         * If there are no attribute values in the modifications then this 
+         * implies the compelete removal of the attribute from the entry. Else
+         * we remove individual attribute values from the entry in mods one 
+         * at a time.
+         */
+        if ( mods.size() == 0 )
+        {
+            entry.removeAttributes( attrType );
+        }
+        else
+        {
+            EntryAttribute entryAttr = entry.get( attrType );
+
+            for ( Value<?> value : mods )
+            {
+                if ( value instanceof ServerStringValue )
+                {
+                    entryAttr.remove( ( String ) value.get() );
+                }
+                else
+                {
+                    entryAttr.remove( ( byte[] ) value.get() );
+                }
+            }
+
+            // if nothing is left just remove empty attribute
+            if ( entryAttr.size() == 0 )
+            {
+                entry.removeAttributes( entryAttr.getId() );
+            }
+        }
+
+        // Aliases->single valued comp/partial attr removal is not relevant here
+        if ( modsOid.equals( oidRegistry.getOid( SchemaConstants.ALIASED_OBJECT_NAME_AT ) ) )
+        {
+            dropAliasIndices( id );
+        }
     }
 
 
     /**
-     * {@inheritDoc}
+     * Completely replaces the existing set of values for an attribute with the
+     * modified values supplied affecting the appropriate userIndices.  The entry
+     * is not persisted: it is only changed in anticipation for a put into the
+     * master table.
+     *
+     * @param id the primary key of the entry
+     * @param entry the entry to alter
+     * @param mods the replacement attribute and values
+     * @throws Exception if index alteration or attribute modification 
+     * fails.
      */
+    @SuppressWarnings("unchecked")
+    private void replace( Long id, ServerEntry entry, EntryAttribute mods ) throws Exception
+    {
+        if ( entry instanceof ClonedServerEntry )
+        {
+            throw new Exception( "Cannot store a ClonedServerEntry" );
+        }
+        
+        String modsOid = oidRegistry.getOid( mods.getId() );
+
+        if ( hasUserIndexOn( modsOid ) )
+        {
+            Index<?,E> index = getUserIndex( modsOid );
+
+            // if the id exists in the index drop all existing attribute value index entries and add new ones
+            if( index.reverse( id ) )
+            {
+                ( ( AvlIndex<?,E> ) index ).drop( id );
+            }
+            
+            for ( Value<?> value : mods )
+            {
+                ( ( AvlIndex<Object,E> ) index ).add( value.get(), id );
+            }
+
+            /* 
+             * If no attribute values exist for this entryId in the index then
+             * we remove the existance index entry for the removed attribute.
+             */
+            if ( null == index.reverseLookup( id ) )
+            {
+                existenceIdx.drop( modsOid, id );
+            }
+        }
+
+        String aliasAttributeOid = oidRegistry.getOid( SchemaConstants.ALIASED_OBJECT_NAME_AT );
+
+        if ( modsOid.equals( aliasAttributeOid ) )
+        {
+            dropAliasIndices( id );
+        }
+
+        // replaces old attributes with new modified ones if they exist
+        if ( mods.size() > 0 )
+        {
+            entry.put( mods );
+        }
+        else
+        // removes old attributes if new replacements do not exist
+        {
+            entry.remove( mods );
+        }
+
+        if ( modsOid.equals( aliasAttributeOid ) && mods.size() > 0 )
+        {
+            String ndnStr = ndnIdx.reverseLookup( id );
+            addAliasIndices( id, new LdapDN( ndnStr ), mods.getString() );
+        }
+    }
+
+
+    public void modify( LdapDN dn, ModificationOperation modOp, ServerEntry mods ) throws Exception
+    {
+        if ( mods instanceof ClonedServerEntry )
+        {
+            throw new Exception( "Cannot store a ClonedServerEntry" );
+        }
+        
+        Long id = getEntryId( dn.toString() );
+        ServerEntry entry = ( ServerEntry ) master.get( id );
+
+        for ( AttributeType attributeType : mods.getAttributeTypes() )
+        {
+            EntryAttribute attr = mods.get( attributeType );
+
+            switch ( modOp )
+            {
+                case ADD_ATTRIBUTE:
+                    add( id, entry, attr );
+                    break;
+
+                case REMOVE_ATTRIBUTE:
+                    remove( id, entry, attr );
+                    break;
+
+                case REPLACE_ATTRIBUTE:
+                    replace( id, entry, attr );
+
+                    break;
+
+                default:
+                    throw new Exception( "Unidentified modification operation" );
+            }
+        }
+
+        master.put( id, entry );
+    }
+
+
+    public void modify( LdapDN dn, List<Modification> mods ) throws Exception
+    {
+        Long id = getEntryId( dn.toString() );
+        ServerEntry entry = ( ServerEntry ) master.get( id );
+
+        for ( Modification mod : mods )
+        {
+            ServerAttribute attrMods = ( ServerAttribute ) mod.getAttribute();
+
+            switch ( mod.getOperation() )
+            {
+                case ADD_ATTRIBUTE:
+                    add( id, entry, attrMods );
+                    break;
+
+                case REMOVE_ATTRIBUTE:
+                    remove( id, entry, attrMods );
+                    break;
+
+                case REPLACE_ATTRIBUTE:
+                    replace( id, entry, attrMods );
+                    break;
+
+                default:
+                    throw new Exception( "Unidentified modification operation" );
+            }
+        }
+
+        master.put( id, entry );
+    }
+
+
+    public void move( LdapDN oldChildDn, LdapDN newParentDn, Rdn newRdn, boolean deleteOldRdn ) throws Exception
+    {
+        Long childId = getEntryId( oldChildDn.toString() );
+        rename( oldChildDn, newRdn, deleteOldRdn );
+        LdapDN newUpdn = move( oldChildDn, childId, newParentDn );
+
+        // Update the current entry
+        ServerEntry entry = lookup( childId );
+        entry.setDn( newUpdn );
+        master.put( childId, entry );
+    }
+
+
     public void move( LdapDN oldChildDn, LdapDN newParentDn ) throws Exception
     {
-        // TODO Auto-generated method stub
+        Long childId = getEntryId( oldChildDn.toString() );
+        LdapDN newUpdn = move( oldChildDn, childId, newParentDn );
+
+        // Update the current entry
+        ServerEntry entry = lookup( childId );
+        entry.setDn( newUpdn );
+        master.put( childId, entry );
     }
 
-    
+
     /**
-     * {@inheritDoc}
-     */
-    public void rename( LdapDN dn, Rdn newRdn, boolean deleteOldRdn ) throws Exception
-    {
-        // TODO Auto-generated method stub
+     * Moves an entry under a new parent.  The operation causes a shift in the
+     * parent child relationships between the old parent, new parent and the 
+     * child moved.  All other descendant entries under the child never change
+     * their direct parent child relationships.  Hence after the parent child
+     * relationship changes are broken at the old parent and set at the new
+     * parent a modifyDn operation is conducted to handle name changes 
+     * propagating down through the moved child and its descendants.
+     * 
+     * @param oldChildDn the normalized dn of the child to be moved
+     * @param childId the id of the child being moved
+     * @param newParentDn the normalized dn of the new parent for the child
+     * @throws NamingException if something goes wrong
+     */
+    private LdapDN move( LdapDN oldChildDn, Long childId, LdapDN newParentDn ) throws Exception
+    {
+        // Get the child and the new parent to be entries and Ids
+        Long newParentId = getEntryId( newParentDn.toString() );
+        Long oldParentId = getParentId( childId );
+
+        /*
+         * All aliases including and below oldChildDn, will be affected by
+         * the move operation with respect to one and subtree userIndices since
+         * their relationship to ancestors above oldChildDn will be 
+         * destroyed.  For each alias below and including oldChildDn we will
+         * drop the index tuples mapping ancestor ids above oldChildDn to the
+         * respective target ids of the aliases.
+         */
+        dropMovedAliasIndices( oldChildDn );
+
+        /*
+         * Drop the old parent child relationship and add the new one
+         * Set the new parent id for the child replacing the old parent id
+         */
+        oneLevelIdx.drop( oldParentId, childId );
+        oneLevelIdx.add( newParentId, childId );
+
+        updateSubLevelIndex( childId, oldParentId, newParentId );
+        
+        /*
+         * Build the new user provided DN (updn) for the child using the child's
+         * user provided RDN & the new parent's UPDN.  Basically add the child's
+         * UpRdn String to the tail of the new parent's Updn Name.
+         */
+        LdapDN childUpdn = new LdapDN( getEntryUpdn( childId ) );
+        String childRdn = childUpdn.get( childUpdn.size() - 1 );
+        LdapDN newUpdn = new LdapDN( getEntryUpdn( newParentId ) );
+        newUpdn.add( newUpdn.size(), childRdn );
+
+        // Call the modifyDn operation with the new updn
+        modifyDn( childId, newUpdn, true );
+        
+        return newUpdn;
     }
 
 
     /**
-     * {@inheritDoc}
+     * Changes the relative distinguished name of an entry specified by a 
+     * distinguished name with the optional removal of the old Rdn attribute
+     * value from the entry.  Name changes propagate down as dn changes to the 
+     * descendants of the entry where the Rdn changed. 
+     * 
+     * An Rdn change operation does not change parent child relationships.  It 
+     * merely propagates a name change at a point in the DIT where the Rdn is 
+     * changed. The change propagates down the subtree rooted at the 
+     * distinguished name specified.
+     *
+     * @param dn the normalized distinguished name of the entry to alter
+     * @param newRdn the new Rdn to set
+     * @param deleteOldRdn whether or not to remove the old Rdn attr/val
+     * @throws Exception if there are any errors propagating the name changes
      */
-    public void setAliasIndex( Index<String, E> index ) throws Exception
+    @SuppressWarnings("unchecked")
+    public void rename( LdapDN dn, Rdn newRdn, boolean deleteOldRdn ) throws Exception
     {
-        // TODO Auto-generated method stub
+        Long id = getEntryId( dn.getNormName() );
+        ServerEntry entry = lookup( id );
+        LdapDN updn = entry.getDn();
+
+        /* 
+         * H A N D L E   N E W   R D N
+         * ====================================================================
+         * Add the new Rdn attribute to the entry.  If an index exists on the 
+         * new Rdn attribute we add the index for this attribute value pair.
+         * Also we make sure that the existance index shows the existance of the
+         * new Rdn attribute within this entry.
+         */
+
+        for ( AttributeTypeAndValue newAtav : newRdn )
+        {
+            String newNormType = newAtav.getNormType();
+            String newNormValue = ( String ) newAtav.getNormValue();
+            AttributeType newRdnAttrType = attributeTypeRegistry.lookup( newNormType );
+            
+            Object unEscapedRdn = Rdn.unescapeValue( (String)newAtav.getUpValue() );
+            
+            Value<?> value = null;
+            
+            if ( unEscapedRdn instanceof String )
+            {
+                value = new ServerStringValue( newRdnAttrType, (String)unEscapedRdn );
+            }
+            else
+            {
+                value = new ServerBinaryValue( newRdnAttrType, (byte[])unEscapedRdn );
+            }
+            
+            value.normalize();
+            
+            entry.add( newRdnAttrType, value );
+
+            if ( hasUserIndexOn( newNormType ) )
+            {
+                Index<?, E> index = getUserIndex( newNormType );
+                ( ( Index ) index ).add( newNormValue, id );
+
+                // Make sure the altered entry shows the existence of the new attrib
+                if ( !existenceIdx.forward( newNormType, id ) )
+                {
+                    existenceIdx.add( newNormType, id );
+                }
+            }
+        }
+
+        /*
+         * H A N D L E   O L D   R D N
+         * ====================================================================
+         * If the old Rdn is to be removed we need to get the attribute and 
+         * value for it.  Keep in mind the old Rdn need not be based on the 
+         * same attr as the new one.  We remove the Rdn value from the entry
+         * and remove the value/id tuple from the index on the old Rdn attr
+         * if any.  We also test if the delete of the old Rdn index tuple 
+         * removed all the attribute values of the old Rdn using a reverse
+         * lookup.  If so that means we blew away the last value of the old 
+         * Rdn attribute.  In this case we need to remove the attrName/id 
+         * tuple from the existance index.
+         * 
+         * We only remove an ATAV of the old Rdn if it is not included in the
+         * new Rdn.
+         */
+
+        if ( deleteOldRdn )
+        {
+            Rdn oldRdn = updn.getRdn();
+            for ( AttributeTypeAndValue oldAtav : oldRdn )
+            {
+                // check if the new ATAV is part of the old Rdn
+                // if that is the case we do not remove the ATAV
+                boolean mustRemove = true;
+                for ( AttributeTypeAndValue newAtav : newRdn )
+                {
+                    if ( oldAtav.equals( newAtav ) )
+                    {
+                        mustRemove = false;
+                        break;
+                    }
+                }
+
+                if ( mustRemove )
+                {
+                    String oldNormType = oldAtav.getNormType();
+                    String oldNormValue = ( String ) oldAtav.getNormValue();
+                    AttributeType oldRdnAttrType = attributeTypeRegistry.lookup( oldNormType );
+                    entry.remove( oldRdnAttrType, oldNormValue );
+
+                    if ( hasUserIndexOn( oldNormType ) )
+                    {
+                        Index<?, E> index = getUserIndex( oldNormType );
+                        ( ( AvlIndex ) index ).drop( oldNormValue, id );
+
+                        /*
+                         * If there is no value for id in this index due to our
+                         * drop above we remove the oldRdnAttr from the existance idx
+                         */
+                        if ( null == index.reverseLookup( id ) )
+                        {
+                            existenceIdx.drop( oldNormType, id );
+                        }
+                    }
+                }
+            }
+        }
+
+        /*
+         * H A N D L E   D N   C H A N G E
+         * ====================================================================
+         * 1) Build the new user defined distinguished name
+         *      - clone / copy old updn
+         *      - remove old upRdn from copy
+         *      - add the new upRdn to the copy
+         * 2) Make call to recursive modifyDn method to change the names of the
+         *    entry and its descendants
+         */
+
+        LdapDN newUpdn = ( LdapDN ) updn.clone(); // copy da old updn
+        newUpdn.remove( newUpdn.size() - 1 ); // remove old upRdn
+        newUpdn.add( newRdn.getUpName() ); // add da new upRdn
+
+        // gotta normalize cuz this thang is cloned and not normalized by default
+        newUpdn.normalize( attributeTypeRegistry.getNormalizerMapping() );
+
+        modifyDn( id, newUpdn, false ); // propagate dn changes
+
+        // Update the current entry
+        entry.setDn( newUpdn );
+        master.put( id, entry );
     }
 
-    
+
     /**
      * {@inheritDoc}
      */
-    public void setCacheSize( int cacheSize )
+    public void setAliasIndex( Index<String, E> index ) throws Exception
     {
-        // TODO Auto-generated method stub
+        if ( index instanceof AvlIndex )
+        {
+            this.aliasIdx = ( AvlIndex<String, E> ) index;
+        }
+        else
+        {
+            this.aliasIdx = ( AvlIndex<String, E> ) convert( index );
+        }
     }
 
     
@@ -536,7 +1326,7 @@
      */
     public void setName( String name )
     {
-        // TODO Auto-generated method stub
+        this.name = name;
     }
 
     
@@ -545,7 +1335,14 @@
      */
     public void setNdnIndex( Index<String, E> index ) throws Exception
     {
-        // TODO Auto-generated method stub
+        if ( index instanceof AvlIndex )
+        {
+            this.ndnIdx = ( AvlIndex<String, E> ) index;
+        }
+        else
+        {
+            this.ndnIdx = ( AvlIndex<String, E> ) convert( index );
+        }
     }
 
 
@@ -554,7 +1351,14 @@
      */
     public void setOneAliasIndex( Index<Long, E> index ) throws Exception
     {
-        // TODO Auto-generated method stub
+        if ( index instanceof AvlIndex )
+        {
+            this.oneAliasIdx = ( AvlIndex<Long, E> ) index;
+        }
+        else
+        {
+            this.oneAliasIdx = ( AvlIndex<Long, E> ) convert( index );
+        }
     }
 
     
@@ -563,7 +1367,14 @@
      */
     public void setOneLevelIndex( Index<Long, E> index ) throws Exception
     {
-        // TODO Auto-generated method stub
+        if ( index instanceof AvlIndex )
+        {
+            this.oneLevelIdx = ( AvlIndex<Long, E> ) index;
+        }
+        else
+        {
+            this.oneLevelIdx = ( AvlIndex<Long, E> ) convert( index );
+        }
     }
 
     
@@ -572,7 +1383,14 @@
      */
     public void setPresenceIndex( Index<String, E> index ) throws Exception
     {
-        // TODO Auto-generated method stub
+        if ( index instanceof AvlIndex )
+        {
+            this.existenceIdx = ( AvlIndex<String, E> ) index;
+        }
+        else
+        {
+            this.existenceIdx = ( AvlIndex<String, E> ) convert( index );
+        }
     }
 
     
@@ -581,7 +1399,7 @@
      */
     public void setProperty( String propertyName, String propertyValue ) throws Exception
     {
-        // TODO Auto-generated method stub    
+        master.setProperty( propertyName, propertyValue );
     }
 
     
@@ -590,7 +1408,14 @@
      */
     public void setSubAliasIndex( Index<Long, E> index ) throws Exception
     {
-        // TODO Auto-generated method stub    
+        if ( index instanceof AvlIndex )
+        {
+            this.subAliasIdx = ( AvlIndex<Long, E> ) index;
+        }
+        else
+        {
+            this.subAliasIdx = ( AvlIndex<Long, E> ) convert( index );
+        }
     }
 
     
@@ -599,25 +1424,24 @@
      */
     public void setSubLevelIndex( Index<Long, E> index ) throws Exception
     {
-        // TODO Auto-generated method stub    
-    }
-
-    
-    /**
-     * {@inheritDoc}
-     */
-    public void setSuffixDn( String suffixDn )
-    {
-        // TODO Auto-generated method stub    
+        if ( index instanceof AvlIndex )
+        {
+            this.subLevelIdx = ( AvlIndex<Long, E> ) index;
+        }
+        else
+        {
+            this.subLevelIdx = ( AvlIndex<Long, E> ) convert( index ); 
+        }
     }
 
     
     /**
      * {@inheritDoc}
      */
-    public void setSyncOnWrite( boolean isSyncOnWrite )
+    public void setSuffixDn( String suffixDn ) throws Exception
     {
-        // TODO Auto-generated method stub    
+        // TODO fix this
+        this.suffixDn = new LdapDN( suffixDn );
     }
 
     
@@ -626,78 +1450,406 @@
      */
     public void setUpdnIndex( Index<String, E> index ) throws Exception
     {
-        // TODO Auto-generated method stub
+        if ( index instanceof AvlIndex )
+        {
+            this.updnIdx = ( AvlIndex<String, E> ) index;
+        }
+        else
+        {
+            this.updnIdx = ( AvlIndex<String, E> ) convert( index );
+        }
     }
 
     
     /**
      * {@inheritDoc}
      */
-    public void setUserIndices( Set<? extends Index<?, E>> userIndices )
+    public void setUserIndices( Set<? extends Index<?, E>> userIndices ) throws Exception
     {
         protect( "setUserIndices" );
         
         for ( Index<?, E> index : userIndices )
         {
-            //this.userIndices.put( index.getAttributeId(), convertIndex( index ) );
+            if ( index instanceof AvlIndex )
+            {
+                this.userIndices.put( index.getAttribute().getOid(), ( AvlIndex<?,E> ) index );
+                continue;
+            }
+
+            LOG.warn( "Supplied index {} is not a AvlIndex.  " +
+                "Will create new AvlIndex using copied configuration parameters.", index );
+            
+            AvlIndex<?,E> avlIndex = ( AvlIndex<?, E> ) convert( index );
+
+            this.userIndices.put( index.getAttributeId(), avlIndex );
         }
     }
 
     
-    private void protect( String method )
+    private <K> Index<K,E> convert( Index<K,E> index ) throws Exception
     {
-        if ( initialized )
-        {
-            throw new IllegalStateException( "Cannot call store method: " + method );
-        }
+        return new AvlIndex<K, E>( index.getAttributeId() );
     }
     
     
-    private<K> AvlIndex<K, E> convertIndex( Index<K,E> index ) throws Exception
+    private void protect( String method )
     {
-        if ( index instanceof AvlIndex )
+        if ( initialized )
         {
-            return ( AvlIndex<K,E> ) index;
+            throw new IllegalStateException( "Cannot call store method: " + method );
         }
-
-        LOG.warn( "Supplied index {} is not a AvlIndex.  " +
-            "Will create new AvlIndex using copied configuration parameters.", index );
-        AvlIndex<K,E> avlIndex = 
-            new AvlIndex<K, E>( index.getAttributeId(), index.getAttribute() );
-        return avlIndex;
     }
 
-
+    
     /**
      * {@inheritDoc}
      */
-    public void setWorkingDirectory( File workingDirectory )
+    public Iterator<String> systemIndices()
     {
+        return systemIndices.keySet().iterator();
     }
 
     
     /**
      * {@inheritDoc}
      */
-    public void sync() throws Exception
+    public Iterator<String> userIndices()
     {
+        return userIndices.keySet().iterator();
     }
 
-    
+
     /**
-     * {@inheritDoc}
-     */
-    public Iterator<String> systemIndices()
-    {
-        return systemIndices.keySet().iterator();
+     * Adds userIndices for an aliasEntry to be added to the database while checking
+     * for constrained alias constructs like alias cycles and chaining.
+     * 
+     * @param aliasDn normalized distinguished name for the alias entry
+     * @param aliasTarget the user provided aliased entry dn as a string
+     * @param aliasId the id of alias entry to add
+     * @throws NamingException if index addition fails, and if the alias is
+     * not allowed due to chaining or cycle formation.
+     * @throws Exception if the wrappedCursor btrees cannot be altered
+     */
+    private void addAliasIndices( Long aliasId, LdapDN aliasDn, String aliasTarget ) throws Exception
+    {
+        LdapDN normalizedAliasTargetDn; // Name value of aliasedObjectName
+        Long targetId; // Id of the aliasedObjectName
+        LdapDN ancestorDn; // Name of an alias entry relative
+        Long ancestorId; // Id of an alias entry relative
+
+        // Access aliasedObjectName, normalize it and generate the Name 
+        normalizedAliasTargetDn = new LdapDN( aliasTarget );
+        normalizedAliasTargetDn.normalize( attributeTypeRegistry.getNormalizerMapping() );
+
+        /*
+         * Check For Cycles
+         * 
+         * Before wasting time to lookup more values we check using the target
+         * dn to see if we have the possible formation of an alias cycle.  This
+         * happens when the alias refers back to a target that is also a 
+         * relative of the alias entry.  For detection we test if the aliased
+         * entry Dn starts with the target Dn.  If it does then we know the 
+         * aliased target is a relative and we have a perspecitive cycle.
+         */
+        if ( aliasDn.startsWith( normalizedAliasTargetDn ) )
+        {
+            if ( aliasDn.equals( normalizedAliasTargetDn ) )
+            {
+                throw new Exception( "[36] aliasDereferencingProblem - " + "attempt to create alias to itself." );
+            }
+
+            throw new Exception( "[36] aliasDereferencingProblem - "
+                + "attempt to create alias with cycle to relative " + aliasTarget
+                + " not allowed from descendent alias " + aliasDn );
+        }
+
+        /*
+         * Check For Aliases External To Naming Context
+         * 
+         * id may be null but the alias may be to a valid entry in 
+         * another namingContext.  Such aliases are not allowed and we
+         * need to point it out to the user instead of saying the target
+         * does not exist when it potentially could outside of this upSuffix.
+         */
+        if ( !normalizedAliasTargetDn.startsWith( suffixDn ) )
+        {
+            // Complain specifically about aliases to outside naming contexts
+            throw new Exception( "[36] aliasDereferencingProblem -"
+                + " the alias points to an entry outside of the " + suffixDn.getUpName()
+                + " namingContext to an object whose existance cannot be" + " determined." );
+        }
+
+        // L O O K U P   T A R G E T   I D
+        targetId = ndnIdx.forwardLookup( normalizedAliasTargetDn.toNormName() );
+
+        /*
+         * Check For Target Existance
+         * 
+         * We do not allow the creation of inconsistant aliases.  Aliases should
+         * not be broken links.  If the target does not exist we start screaming
+         */
+        if ( null == targetId )
+        {
+            // Complain about target not existing
+            throw new Exception( "[33] aliasProblem - "
+                + "the alias when dereferenced would not name a known object "
+                + "the aliasedObjectName must be set to a valid existing " + "entry." );
+        }
+
+        /*
+         * Detect Direct Alias Chain Creation
+         * 
+         * Rather than resusitate the target to test if it is an alias and fail
+         * due to chaing creation we use the alias index to determine if the
+         * target is an alias.  Hence if the alias we are about to create points
+         * to another alias as its target in the aliasedObjectName attribute, 
+         * then we have a situation where an alias chain is being created.  
+         * Alias chaining is not allowed so we throw and exception. 
+         */
+        if ( null != aliasIdx.reverseLookup( targetId ) )
+        {
+            // Complain about illegal alias chain
+            throw new Exception( "[36] aliasDereferencingProblem -"
+                + " the alias points to another alias.  Alias chaining is" + " not supported by this backend." );
+        }
+
+        // Add the alias to the simple alias index
+        aliasIdx.add( normalizedAliasTargetDn.getNormName(), aliasId );
+
+        /*
+         * Handle One Level Scope Alias Index
+         * 
+         * The first relative is special with respect to the one level alias
+         * index.  If the target is not a sibling of the alias then we add the
+         * index entry maping the parent's id to the aliased target id.
+         */
+        ancestorDn = ( LdapDN ) aliasDn.clone();
+        ancestorDn.remove( aliasDn.size() - 1 );
+        ancestorId = getEntryId( ancestorDn.toNormName() );
+
+        // check if alias parent and aliased entry are the same
+        LdapDN normalizedAliasTargetParentDn = ( LdapDN ) normalizedAliasTargetDn.clone();
+        normalizedAliasTargetParentDn.remove( normalizedAliasTargetDn.size() - 1 );
+        if ( ! aliasDn.startsWith( normalizedAliasTargetParentDn ) )
+        {
+            oneAliasIdx.add( ancestorId, targetId );
+        }
+
+        /*
+         * Handle Sub Level Scope Alias Index
+         * 
+         * Walk the list of relatives from the parents up to the upSuffix, testing
+         * to see if the alias' target is a descendant of the relative.  If the
+         * alias target is not a descentant of the relative it extends the scope
+         * and is added to the sub tree scope alias index.  The upSuffix node is
+         * ignored since everything is under its scope.  The first loop 
+         * iteration shall handle the parents.
+         */
+        while ( !ancestorDn.equals( suffixDn ) && null != ancestorId )
+        {
+            if ( !NamespaceTools.isDescendant( ancestorDn, normalizedAliasTargetDn ) )
+            {
+                subAliasIdx.add( ancestorId, targetId );
+            }
+
+            ancestorDn.remove( ancestorDn.size() - 1 );
+            ancestorId = getEntryId( ancestorDn.toNormName() );
+        }
     }
 
-    
+
     /**
-     * {@inheritDoc}
+     * Removes the index entries for an alias before the entry is deleted from
+     * the master table.
+     * 
+     * @todo Optimize this by walking the hierarchy index instead of the name 
+     * @param aliasId the id of the alias entry in the master table
+     * @throws NamingException if we cannot parse ldap names
+     * @throws Exception if we cannot delete index values in the database
+     */
+    private void dropAliasIndices( Long aliasId ) throws Exception
+    {
+        String targetDn = aliasIdx.reverseLookup( aliasId );
+        Long targetId = getEntryId( targetDn );
+        String aliasDn = getEntryDn( aliasId );
+        LdapDN ancestorDn = ( LdapDN ) new LdapDN( aliasDn ).getPrefix( 1 );
+        Long ancestorId = getEntryId( ancestorDn.toString() );
+
+        /*
+         * We cannot just drop all tuples in the one level and subtree userIndices
+         * linking baseIds to the targetId.  If more than one alias refers to
+         * the target then droping all tuples with a value of targetId would
+         * make all other aliases to the target inconsistent.
+         * 
+         * We need to walk up the path of alias ancestors until we reach the 
+         * upSuffix, deleting each ( ancestorId, targetId ) tuple in the
+         * subtree scope alias.  We only need to do this for the direct parent
+         * of the alias on the one level subtree.
+         */
+        oneAliasIdx.drop( ancestorId, targetId );
+        subAliasIdx.drop( ancestorId, targetId );
+
+        while ( !ancestorDn.equals( suffixDn ) )
+        {
+            ancestorDn = ( LdapDN ) ancestorDn.getPrefix( 1 );
+            ancestorId = getEntryId( ancestorDn.toString() );
+
+            subAliasIdx.drop( ancestorId, targetId );
+        }
+
+        // Drops all alias tuples pointing to the id of the alias to be deleted
+        aliasIdx.drop( aliasId );
+    }
+
+
+    /**
+     * 
+     * updates the SubLevel Index as part of a move operation.
+     *
+     * @param childId child id to be moved
+     * @param oldParentId old parent's id
+     * @param newParentId new parent's id
+     * @throws Exception
      */
-    public Iterator<String> userIndices()
+    private void updateSubLevelIndex( Long childId, Long oldParentId, Long newParentId ) throws Exception
     {
-        return userIndices.keySet().iterator();
+        Long tempId = oldParentId;
+        List<Long> parentIds = new ArrayList<Long>();
+
+        // find all the parents of the oldParentId
+        while( tempId != 0 && tempId != 1 && tempId != null )
+        {
+          parentIds.add( tempId );
+          tempId = getParentId( tempId );
+        }
+
+        // find all the children of the childId
+        Cursor<IndexEntry<Long,E>> cursor = subLevelIdx.forwardCursor( childId );
+        
+        List<Long> childIds = new ArrayList<Long>();
+        childIds.add( childId );
+        
+        while( cursor.next() )
+        {
+            childIds.add( cursor.get().getId() );
+        }
+        
+        // detach the childId and all its children from oldParentId and all it parents excluding the root
+        for( Long pid : parentIds )
+        {
+            for( Long cid: childIds )
+            {
+                subLevelIdx.drop( pid, cid );
+            }
+        }
+        
+        parentIds.clear();
+        tempId = newParentId;
+
+        // find all the parents of the newParentId
+        while( tempId != 0 && tempId != 1 && tempId != null )
+        {
+          parentIds.add( tempId );
+          tempId = getParentId( tempId );
+        }
+        
+        // attach the childId and all its children to newParentId and all it parents excluding the root
+        for( Long id : parentIds )
+        {
+            for( Long cid: childIds )
+            {
+                subLevelIdx.add( id, cid );
+            }
+        }
+    }
+    
+    
+    /**
+     * For all aliases including and under the moved base, this method removes
+     * one and subtree alias index tuples for old ancestors above the moved base
+     * that will no longer be ancestors after the move.
+     * 
+     * @param movedBase the base at which the move occured - the moved node
+     * @throws NamingException if system userIndices fail
+     */
+    private void dropMovedAliasIndices( final LdapDN movedBase ) throws Exception
+    {
+//        // Find all the aliases from movedBase down
+//        IndexAssertion<Object,E> isBaseDescendant = new IndexAssertion<Object,E>()
+//        {
+//            public boolean assertCandidate( IndexEntry<Object,E> rec ) throws Exception
+//            {
+//                String dn = getEntryDn( rec.getId() );
+//                return dn.endsWith( movedBase.toString() );
+//            }
+//        };
+
+        Long movedBaseId = getEntryId( movedBase.toString() );
+
+        if ( aliasIdx.reverseLookup( movedBaseId ) != null )
+        {
+            dropAliasIndices( movedBaseId, movedBase );
+        }
+
+//        throw new NotImplementedException( "Fix the code below this line" );
+
+//        NamingEnumeration<ForwardIndexEntry> aliases =
+//                new IndexAssertionEnumeration( aliasIdx.listIndices( movedBase.toString(), true ), isBaseDescendant );
+//
+//        while ( aliases.hasMore() )
+//        {
+//            ForwardIndexEntry entry = aliases.next();
+//            dropAliasIndices( (Long)entry.getId(), movedBase );
+//        }
+    }
+
+
+    /**
+     * For the alias id all ancestor one and subtree alias tuples are moved 
+     * above the moved base.
+     * 
+     * @param aliasId the id of the alias 
+     * @param movedBase the base where the move occured
+     * @throws Exception if userIndices fail
+     */
+    private void dropAliasIndices( Long aliasId, LdapDN movedBase ) throws Exception
+    {
+        String targetDn = aliasIdx.reverseLookup( aliasId );
+        Long targetId = getEntryId( targetDn );
+        String aliasDn = getEntryDn( aliasId );
+
+        /*
+         * Start droping index tuples with the first ancestor right above the 
+         * moved base.  This is the first ancestor effected by the move.
+         */
+        LdapDN ancestorDn = ( LdapDN ) movedBase.getPrefix( 1 );
+        Long ancestorId = getEntryId( ancestorDn.toString() );
+
+        /*
+         * We cannot just drop all tuples in the one level and subtree userIndices
+         * linking baseIds to the targetId.  If more than one alias refers to
+         * the target then droping all tuples with a value of targetId would
+         * make all other aliases to the target inconsistent.
+         * 
+         * We need to walk up the path of alias ancestors right above the moved 
+         * base until we reach the upSuffix, deleting each ( ancestorId,
+         * targetId ) tuple in the subtree scope alias.  We only need to do 
+         * this for the direct parent of the alias on the one level subtree if
+         * the moved base is the alias.
+         */
+        if ( aliasDn.equals( movedBase.toString() ) )
+        {
+            oneAliasIdx.drop( ancestorId, targetId );
+        }
+
+        subAliasIdx.drop( ancestorId, targetId );
+
+        while ( !ancestorDn.equals( suffixDn ) )
+        {
+            ancestorDn = ( LdapDN ) ancestorDn.getPrefix( 1 );
+            ancestorId = getEntryId( ancestorDn.toString() );
+
+            subAliasIdx.drop( ancestorId, targetId );
+        }
     }
 }



Mime
View raw message