You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by el...@apache.org on 2012/03/29 19:08:44 UTC
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...
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