directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1306997 - in /directory/apacheds/branches/index-work/xdbm-partition/src: main/java/org/apache/directory/server/core/partition/impl/btree/ main/java/org/apache/directory/server/xdbm/ main/java/org/apache/directory/server/xdbm/impl/avl/ test...
Date Thu, 29 Mar 2012 17:08:44 GMT
Author: elecharny
Date: Thu Mar 29 17:08:44 2012
New Revision: 1306997

URL: http://svn.apache.org/viewvc?rev=1306997&view=rev
Log:
o Added the nbChildren and nbDescendant values in the ParentIdAndRdn classes
o Updated the ParentIdAndRdn instances when adding/moving/removing entries to get the correct
number of children and descendants
o Added a dumpRdnIdx() method to dump the modified RdnIdx in debug mode
o Changed the ParentIdAndRdn.compareTo() method to get a way to find all the children of a
parent while browsing a tree
o Added the allowsDuplicates field in the AvlTable (should be moved to the AbstractTable class)

Modified:
    directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java
    directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ParentIdAndRdn.java
    directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlRdnIndex.java
    directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlTable.java
    directory/apacheds/branches/index-work/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/ParentIdAndRdnTest.java

Modified: directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java?rev=1306997&r1=1306996&r2=1306997&view=diff
==============================================================================
--- directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java
(original)
+++ directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java
Thu Mar 29 17:08:44 2012
@@ -52,12 +52,14 @@ import org.apache.directory.server.core.
 import org.apache.directory.server.core.api.partition.AbstractPartition;
 import org.apache.directory.server.core.api.partition.Partition;
 import org.apache.directory.server.i18n.I18n;
+import org.apache.directory.server.xdbm.ForwardIndexEntry;
 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.MasterTable;
 import org.apache.directory.server.xdbm.ParentIdAndRdn;
+import org.apache.directory.server.xdbm.ReverseIndexEntry;
 import org.apache.directory.server.xdbm.Store;
 import org.apache.directory.server.xdbm.search.Optimizer;
 import org.apache.directory.server.xdbm.search.SearchEngine;
@@ -177,6 +179,9 @@ public abstract class AbstractBTreeParti
 
     private static final boolean NO_REVERSE = Boolean.FALSE;
     private static final boolean WITH_REVERSE = Boolean.TRUE;
+    
+    private static final int ADD_CHILD = 1;
+    private static final int REMOVE_CHILD = -1;
 
     // ------------------------------------------------------------------------
     // C O N S T R U C T O R S
@@ -531,6 +536,45 @@ public abstract class AbstractBTreeParti
         
     }
 
+   
+    private void dumpRdnIdx() throws Exception
+    {
+        if ( LOG.isDebugEnabled() )
+        {
+            dumpRdnIdx( getRootId(), 1, "" );
+            System.out.println( "-----------------------------" );
+        }
+    }
+    
+    
+    private void dumpRdnIdx( ID id, int nbSibbling, String tabs ) throws Exception
+    {
+        // Start with the root
+        IndexCursor<ParentIdAndRdn<ID>,Entry,ID> cursor = rdnIdx.forwardCursor();
+        
+        IndexEntry<ParentIdAndRdn<ID>, ID> startingPos = new ForwardIndexEntry<ParentIdAndRdn<ID>,
ID>();
+        startingPos.setValue( new ParentIdAndRdn( id, (Rdn[]) null ) );
+        cursor.before( startingPos );
+        int countChildren = 0;
+        
+        while ( cursor.next() && ( countChildren < nbSibbling ) )
+        {
+            IndexEntry<ParentIdAndRdn<ID>, ID> entry = cursor.get();
+            System.out.println( tabs + entry.getValue() );
+            countChildren++;
+            
+            // And now, the children
+            int nbChildren = entry.getValue().getNbChildren();
+            
+            if ( nbChildren > 0 )
+            {
+                dumpRdnIdx( entry.getId(), nbChildren, tabs + "  " );
+            }
+        }
+        
+        cursor.close();
+    }
+
 
     //---------------------------------------------------------------------------------------------
     // The Add operation
@@ -587,6 +631,9 @@ public abstract class AbstractBTreeParti
 
             // Update the RDN index
             rdnIdx.add( key, id );
+            
+            // Update the parent's nbChildren and nbDescendants values
+            updateRdnIdx( parentId, ADD_CHILD );
 
             // Update the ObjectClass index
             Attribute objectClass = entry.get( OBJECT_CLASS_AT );
@@ -676,6 +723,8 @@ public abstract class AbstractBTreeParti
 
             // And finally add the entry into the master table
             master.put( id, entry );
+            
+            dumpRdnIdx();
 
             if ( isSyncOnWrite.get() )
             {
@@ -721,6 +770,38 @@ public abstract class AbstractBTreeParti
         // We now defer the deletion to the implementing class
         delete( id );
     }
+    
+    
+    private void updateRdnIdx( ID id, int addRemove ) throws Exception
+    {
+        ID tmpId = id;
+
+        if ( addRemove == REMOVE_CHILD )
+        {
+            ParentIdAndRdn<ID> entry = rdnIdx.reverseLookup( id );
+            tmpId = entry.getParentId();
+        }
+        
+        boolean isFirst = true;
+        
+        while ( !tmpId.equals( getRootId() ) )
+        {
+            ParentIdAndRdn<ID> parent = rdnIdx.reverseLookup( tmpId );
+        
+            if ( isFirst )
+            {
+                parent.setNbChildren( parent.getNbChildren() + addRemove );
+                isFirst = false;
+            }
+            
+            parent.setNbDescendants( parent.getNbDescendants() + addRemove );
+
+            // Inject the modified element into the index
+            rdnIdx.add( parent, tmpId );
+            
+            tmpId = parent.getParentId();
+        }
+    }
 
 
     /**
@@ -754,8 +835,14 @@ public abstract class AbstractBTreeParti
                 objectClassIdx.drop( value.getString(), id );
             }
 
+            // Update the parent's nbChildren and nbDescendants values
+            updateRdnIdx( id, REMOVE_CHILD );
+
             // Update the rdn, oneLevel, subLevel, entryCsn and entryUuid indexes
             rdnIdx.drop( id );
+            
+            dumpRdnIdx();
+
             oneLevelIdx.drop( id );
             subLevelIdx.drop( id );
             entryCsnIdx.drop( entry.get( ENTRY_CSN_AT ).getString(), id );
@@ -1409,9 +1496,13 @@ public abstract class AbstractBTreeParti
         updateSubLevelIndex( entryId, oldParentId, newParentId );
 
         // Update the Rdn index
+        updateRdnIdx( entryId, REMOVE_CHILD );
         rdnIdx.drop( entryId );
         ParentIdAndRdn<ID> key = new ParentIdAndRdn<ID>( newParentId, oldDn.getRdn()
);
         rdnIdx.add( key, entryId );
+        updateRdnIdx( newParentId, ADD_CHILD );
+
+        dumpRdnIdx();
 
         /*
          * Read Alias Index Tuples
@@ -1582,9 +1673,13 @@ public abstract class AbstractBTreeParti
         /*
          * Update the Rdn index
          */
+        updateRdnIdx( childId, REMOVE_CHILD );
         rdnIdx.drop( childId );
         ParentIdAndRdn<ID> key = new ParentIdAndRdn<ID>( newParentId, newRdn
);
         rdnIdx.add( key, childId );
+        updateRdnIdx( newParentId, ADD_CHILD );
+
+        dumpRdnIdx();
 
         /*
          * Read Alias Index Tuples

Modified: directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ParentIdAndRdn.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ParentIdAndRdn.java?rev=1306997&r1=1306996&r2=1306997&view=diff
==============================================================================
--- directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ParentIdAndRdn.java
(original)
+++ directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ParentIdAndRdn.java
Thu Mar 29 17:08:44 2012
@@ -45,6 +45,11 @@ public class ParentIdAndRdn<ID extends C
     /** The list of Rdn for this instance */
     protected Rdn[] rdns;
 
+    /** Number of direct children */
+    protected int nbChildren;
+
+    /** Number of global descendant */
+    protected int nbDescendants;
 
     /**
      * Serializable constructor.
@@ -77,6 +82,8 @@ public class ParentIdAndRdn<ID extends C
     {
         this.parentId = parentId;
         this.rdns = rdns.toArray( new Rdn[rdns.size()] );
+        nbChildren = 0;
+        nbDescendants = 0;
     }
 
 
@@ -183,13 +190,40 @@ public class ParentIdAndRdn<ID extends C
      */
     public int compareTo( ParentIdAndRdn<ID> that )
     {
-        int val = rdns.length - that.rdns.length;
+        // Special case when that.rdns = null : we are searching for oneLevel or subLevel
scope
+        if ( that.rdns == null )
+        {
+            return parentId.compareTo( that.parentId );
+        }
+
+        if ( rdns == null )
+        {
+            int res = parentId.compareTo( that.parentId );
+            
+            if ( res == 0 )
+            {
+                return -1;
+            }
+            else
+            {
+                return res;
+            }
+        }
+        
+        int val = parentId.compareTo( that.getParentId() );
 
         if ( val != 0 )
         {
             return val;
         }
 
+        val = rdns.length - that.rdns.length;
+
+        if ( val != 0 )
+        {
+            return val;
+        }
+        
         StringBuilder sb = new StringBuilder();
         boolean isFirst = true;
         
@@ -230,11 +264,6 @@ public class ParentIdAndRdn<ID extends C
         
         val = ( thisString.compareTo( thatString ) );
         
-        if ( val == 0 )
-        {
-            val = this.getParentId().compareTo( that.getParentId() );
-        }
-
         return val;
     }
 
@@ -242,6 +271,8 @@ public class ParentIdAndRdn<ID extends C
     public void writeExternal( ObjectOutput out ) throws IOException
     {
         out.writeObject( parentId );
+        out.writeInt( nbChildren );
+        out.writeInt( nbDescendants );
         out.writeInt( rdns.length );
 
         for ( Rdn rdn : rdns )
@@ -255,6 +286,8 @@ public class ParentIdAndRdn<ID extends C
     public void readExternal( ObjectInput in ) throws IOException, ClassNotFoundException
     {
         parentId = ( ID ) in.readObject();
+        nbChildren = in.readInt();
+        nbDescendants = in.readInt();
         int size = in.readInt();
         rdns = new Rdn[size];
 
@@ -268,6 +301,46 @@ public class ParentIdAndRdn<ID extends C
 
 
     /**
+     * @return The number of children this entry has
+     */
+    public int getNbChildren()
+    {
+        return nbChildren;
+    }
+
+
+    /**
+     * Sets the number of children this entry has
+     * @param nbChildren The number of children
+     */
+    public void setNbChildren( int nbChildren )
+    {
+        this.nbChildren = nbChildren;
+    }
+
+
+    /**
+     * @return The number of descendants this entry has
+     */
+    public int getNbDescendants()
+    {
+        return nbDescendants;
+    }
+
+
+    /**
+     * Sets the number of descendants this entry has
+     * @param nbChildren The number of descendants
+     */
+    public void setNbDescendants( int nbDescendants )
+    {
+        this.nbDescendants = nbDescendants;
+    }
+
+
+
+
+    /**
      * {@inheritDoc}
      */
     public String toString()
@@ -277,23 +350,33 @@ public class ParentIdAndRdn<ID extends C
         sb.append( "ParentIdAndRdn<" );
         sb.append( parentId ).append( ", '" );
 
-        boolean isFirst = true;
-
-        for ( Rdn rdn : rdns )
+        if ( rdns == null )
         {
-            if ( isFirst )
-            {
-                isFirst = false;
-            }
-            else
+            sb.append( "*'>" );
+        }
+        else
+        {
+            boolean isFirst = true;
+    
+            for ( Rdn rdn : rdns )
             {
-                sb.append( "," );
+                if ( isFirst )
+                {
+                    isFirst = false;
+                }
+                else
+                {
+                    sb.append( "," );
+                }
+    
+                sb.append( rdn );
             }
 
-            sb.append( rdn );
+            sb.append( "'>" );
+            
+            sb.append( "[nbC:" ).append( nbChildren ).append( ", nbD:" ).append( nbDescendants
).append( "]" );
         }
 
-        sb.append( "'>" );
 
         return sb.toString();
     }

Modified: directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlRdnIndex.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlRdnIndex.java?rev=1306997&r1=1306996&r2=1306997&view=diff
==============================================================================
--- directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlRdnIndex.java
(original)
+++ directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlRdnIndex.java
Thu Mar 29 17:08:44 2012
@@ -37,7 +37,6 @@ import org.apache.directory.shared.ldap.
  */
 public class AvlRdnIndex<E> extends AvlIndex<ParentIdAndRdn<Long>, E>
 {
-
     public AvlRdnIndex()
     {
         super();
@@ -107,6 +106,7 @@ public class AvlRdnIndex<E> extends AvlI
     public void drop( ParentIdAndRdn<Long> rdn, Long id ) throws Exception
     {
         long val = forward.get( rdn );
+        
         if ( val == id )
         {
             forward.remove( rdn );

Modified: directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlTable.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlTable.java?rev=1306997&r1=1306996&r2=1306997&view=diff
==============================================================================
--- directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlTable.java
(original)
+++ directory/apacheds/branches/index-work/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/impl/avl/AvlTable.java
Thu Mar 29 17:08:44 2012
@@ -48,12 +48,15 @@ public class AvlTable<K, V> extends Abst
     private final AvlTreeMap<K, V> avl;
     private final Comparator<Tuple<K, V>> keyOnlytupleComparator;
 
+    /** whether or not this table allows for duplicates */
+    private final boolean allowsDuplicates;
 
     public AvlTable( String name, final Comparator<K> keyComparator, final Comparator<V>
valueComparator,
         boolean dupsEnabled )
     {
         super( null, name, keyComparator, valueComparator );
         this.avl = new AvlTreeMapImpl<K, V>( keyComparator, valueComparator, dupsEnabled
);
+        allowsDuplicates = this.avl.isDupsAllowed();
         this.keyOnlytupleComparator = new Comparator<Tuple<K, V>>()
         {
             public int compare( Tuple<K, V> t0, Tuple<K, V> t1 )
@@ -253,7 +256,7 @@ public class AvlTable<K, V> extends Abst
      */
     public boolean isDupsEnabled()
     {
-        return avl.isDupsAllowed();
+        return allowsDuplicates;
     }
 
 
@@ -271,7 +274,7 @@ public class AvlTable<K, V> extends Abst
      */
     public void put( K key, V value ) throws Exception
     {
-        if ( key == null || value == null )
+        if ( ( key == null ) || ( value == null ) )
         {
             return;
         }
@@ -328,9 +331,10 @@ public class AvlTable<K, V> extends Abst
      */
     public Cursor<Tuple<K, V>> cursor() throws Exception
     {
-        if ( !avl.isDupsAllowed() )
+        if ( !allowsDuplicates )
         {
-            return new AvlTreeMapNoDupsWrapperCursor<K, V>( new AvlSingletonOrOrderedSetCursor<K,
V>( avl ) );
+            return new AvlTreeMapNoDupsWrapperCursor<K, V>( 
+                new AvlSingletonOrOrderedSetCursor<K, V>( avl ) );
         }
 
         return new AvlTableDupsCursor<K, V>( this );

Modified: directory/apacheds/branches/index-work/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/ParentIdAndRdnTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/index-work/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/ParentIdAndRdnTest.java?rev=1306997&r1=1306996&r2=1306997&view=diff
==============================================================================
--- directory/apacheds/branches/index-work/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/ParentIdAndRdnTest.java
(original)
+++ directory/apacheds/branches/index-work/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/ParentIdAndRdnTest.java
Thu Mar 29 17:08:44 2012
@@ -109,20 +109,20 @@ public class ParentIdAndRdnTest
         assertEquals( -2, rdn3.compareTo( rdn2 ) );
         assertEquals( 0, rdn3.compareTo( rdn3 ) );
         assertEquals( -1, rdn3.compareTo( rdn4 ) );
-        assertEquals( -2, rdn3.compareTo( rdn5 ) );
+        assertEquals( 1, rdn3.compareTo( rdn5 ) );
         
         // Forth rdn
         assertEquals( -2, rdn4.compareTo( rdn1 ) );
         assertEquals( -2, rdn4.compareTo( rdn2 ) );
         assertEquals( 1, rdn4.compareTo( rdn3 ) );
         assertEquals( 0, rdn4.compareTo( rdn4 ) );
-        assertEquals( -2, rdn4.compareTo( rdn5 ) );
+        assertEquals( 1, rdn4.compareTo( rdn5 ) );
         
         // Fifth rdn
         assertEquals( -1, rdn5.compareTo( rdn1 ) );
         assertEquals( -1, rdn5.compareTo( rdn2 ) );
-        assertEquals( 2, rdn5.compareTo( rdn3 ) );
-        assertEquals( 2, rdn5.compareTo( rdn4 ) );
+        assertEquals( -1, rdn5.compareTo( rdn3 ) );
+        assertEquals( -1, rdn5.compareTo( rdn4 ) );
         assertEquals( 0, rdn5.compareTo( rdn5 ) );
 
         // Sixth rdn



Mime
View raw message