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 2008/09/22 16:25:45 UTC
svn commit: r697846 - in /directory:
apacheds/trunk/core/src/main/java/org/apache/directory/server/core/partition/
apacheds/trunk/core/src/test/java/org/apache/directory/server/core/partition/tree/
shared/trunk/ldap/src/main/java/org/apache/directory/s...
Author: elecharny
Date: Mon Sep 22 07:25:44 2008
New Revision: 697846
URL: http://svn.apache.org/viewvc?rev=697846&view=rev
Log:
o Added a remove() method
o replaced the recursiveAddElement by the most simplest add() method
o Added some tests
Added:
directory/shared/trunk/ldap/src/test/java/org/apache/directory/shared/ldap/util/tree/
directory/shared/trunk/ldap/src/test/java/org/apache/directory/shared/ldap/util/tree/TestDnNode.java
Modified:
directory/apacheds/trunk/core/src/main/java/org/apache/directory/server/core/partition/DefaultPartitionNexus.java
directory/apacheds/trunk/core/src/test/java/org/apache/directory/server/core/partition/tree/PartitionTreeTest.java
directory/shared/trunk/ldap/src/main/java/org/apache/directory/shared/ldap/util/tree/DnBranchNode.java
Modified: directory/apacheds/trunk/core/src/main/java/org/apache/directory/server/core/partition/DefaultPartitionNexus.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core/src/main/java/org/apache/directory/server/core/partition/DefaultPartitionNexus.java?rev=697846&r1=697845&r2=697846&view=diff
==============================================================================
--- directory/apacheds/trunk/core/src/main/java/org/apache/directory/server/core/partition/DefaultPartitionNexus.java (original)
+++ directory/apacheds/trunk/core/src/main/java/org/apache/directory/server/core/partition/DefaultPartitionNexus.java Mon Sep 22 07:25:44 2008
@@ -428,7 +428,7 @@
synchronized ( partitionLookupTree )
{
partitions.put( key, system );
- partitionLookupTree.recursivelyAddElement( partitionLookupTree, system.getSuffixDn(), 0, system );
+ partitionLookupTree.add( system.getSuffixDn(), system );
EntryAttribute namingContexts = rootDSE.get( SchemaConstants.NAMING_CONTEXTS_AT );
if ( namingContexts == null )
@@ -618,7 +618,7 @@
}
partitions.put( partitionSuffix.toString(), partition );
- partitionLookupTree.recursivelyAddElement( partitionLookupTree, partition.getSuffixDn(), 0, partition );
+ partitionLookupTree.add( partition.getSuffixDn(), partition );
EntryAttribute namingContexts = rootDSE.get( SchemaConstants.NAMING_CONTEXTS_AT );
@@ -660,23 +660,9 @@
namingContexts.remove( partition.getUpSuffixDn().getUpName() );
}
- // Create a new partition list.
- // This is easier to create a new structure from scratch than to reorganize
- // the current structure. As this structure is not modified often
- // this is an acceptable solution.
- synchronized ( partitionLookupTree )
- {
- partitions.remove( key );
- partitionLookupTree = new DnBranchNode<Partition>();
-
- for ( Partition part : partitions.values() )
- {
- partitionLookupTree.recursivelyAddElement( partitionLookupTree, part.getSuffixDn(), 0, partition );
- }
-
- partition.sync();
- partition.destroy();
- }
+ // Update the partition tree
+ partitionLookupTree.remove( partition );
+ partitions.remove( key );
}
Modified: directory/apacheds/trunk/core/src/test/java/org/apache/directory/server/core/partition/tree/PartitionTreeTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core/src/test/java/org/apache/directory/server/core/partition/tree/PartitionTreeTest.java?rev=697846&r1=697845&r2=697846&view=diff
==============================================================================
--- directory/apacheds/trunk/core/src/test/java/org/apache/directory/server/core/partition/tree/PartitionTreeTest.java (original)
+++ directory/apacheds/trunk/core/src/test/java/org/apache/directory/server/core/partition/tree/PartitionTreeTest.java Mon Sep 22 07:25:44 2008
@@ -56,13 +56,13 @@
Partition partition = new JdbmPartition();
partition.setSuffix( suffix.getUpName() );
- DnNode<Partition> node = partitionLookupTree.recursivelyAddElement( partitionLookupTree, suffix, 0, partition );
+ partitionLookupTree.add( suffix, partition );
- assertNotNull( node );
- assertTrue( node instanceof DnBranchNode );
- assertTrue( ((DnBranchNode<Partition>)node).contains( "dc=com" ) );
+ assertNotNull( partitionLookupTree );
+ assertTrue( partitionLookupTree instanceof DnBranchNode );
+ assertTrue( ((DnBranchNode<Partition>)partitionLookupTree).contains( "dc=com" ) );
- DnNode<Partition> child = ((DnBranchNode<Partition>)node).getChild( "dc=com" );
+ DnNode<Partition> child = ((DnBranchNode<Partition>)partitionLookupTree).getChild( "dc=com" );
assertTrue( child instanceof DnBranchNode );
assertTrue( ((DnBranchNode<Partition>)child).contains( "dc=example" ) );
@@ -83,24 +83,24 @@
Partition partition1 = new JdbmPartition();
partition1.setSuffix( suffix1.getUpName() );
- DnNode<Partition> node = partitionLookupTree.recursivelyAddElement( partitionLookupTree, suffix1, 0, partition1 );
+ partitionLookupTree.add( suffix1, partition1 );
LdapDN suffix2 = new LdapDN( "ou=system" );
Partition partition2 = new JdbmPartition();
partition2.setSuffix( suffix2.getUpName() );
- node = partitionLookupTree.recursivelyAddElement( partitionLookupTree, suffix2, 0, partition2 );
+ partitionLookupTree.add( suffix2, partition2 );
- assertNotNull( node );
- assertTrue( node instanceof DnBranchNode );
- assertTrue( ((DnBranchNode<Partition>)node).contains( "ou=system" ) );
- assertTrue( ((DnBranchNode<Partition>)node).contains( "dc=com" ) );
+ assertNotNull( partitionLookupTree );
+ assertTrue( partitionLookupTree instanceof DnBranchNode );
+ assertTrue( ((DnBranchNode<Partition>)partitionLookupTree).contains( "ou=system" ) );
+ assertTrue( ((DnBranchNode<Partition>)partitionLookupTree).contains( "dc=com" ) );
- DnNode<Partition> child = ((DnBranchNode<Partition>)node).getChild( "ou=system" );
+ DnNode<Partition> child = ((DnBranchNode<Partition>)partitionLookupTree).getChild( "ou=system" );
assertTrue( child instanceof DnLeafNode );
assertEquals( "ou=system", ((DnLeafNode<Partition>)child).getElement().getSuffix() );
- child = ((DnBranchNode<Partition>)node).getChild( "dc=com" );
+ child = ((DnBranchNode<Partition>)partitionLookupTree).getChild( "dc=com" );
assertTrue( child instanceof DnBranchNode );
assertTrue( ((DnBranchNode<Partition>)child).contains( "dc=example" ) );
@@ -122,7 +122,7 @@
Partition partition1 = new JdbmPartition();
partition1.setSuffix( suffix1.getUpName() );
- partitionLookupTree.recursivelyAddElement( partitionLookupTree, suffix1, 0, partition1 );
+ partitionLookupTree.add( suffix1, partition1 );
LdapDN suffix2 = new LdapDN( "dc=example, dc=com" );
Partition partition2 = new JdbmPartition();
@@ -130,7 +130,7 @@
try
{
- partitionLookupTree.recursivelyAddElement( partitionLookupTree, suffix2, 0, partition2 );
+ partitionLookupTree.add( suffix2, partition2 );
fail();
}
catch ( NamingException ne )
@@ -152,23 +152,23 @@
Partition partition1 = new JdbmPartition();
partition1.setSuffix( suffix1.getUpName() );
- partitionLookupTree.recursivelyAddElement( partitionLookupTree, suffix1, 0, partition1 );
+ partitionLookupTree.add( suffix1, partition1 );
LdapDN suffix2 = new LdapDN( "dc=example2, dc=com" );
Partition partition2 = new JdbmPartition();
partition2.setSuffix( suffix2.getUpName() );
- DnNode<Partition> node = partitionLookupTree.recursivelyAddElement( partitionLookupTree, suffix2, 0, partition2 );
+ partitionLookupTree.add( suffix2, partition2 );
- assertNotNull( node );
+ assertNotNull( partitionLookupTree );
- assertTrue( node instanceof DnBranchNode );
- assertTrue( ((DnBranchNode<Partition>)node).contains( "dc=com" ) );
+ assertTrue( partitionLookupTree instanceof DnBranchNode );
+ assertTrue( ((DnBranchNode<Partition>)partitionLookupTree).contains( "dc=com" ) );
- DnNode<Partition> child = ((DnBranchNode<Partition>)node).getChild( "dc=com" );
+ DnNode<Partition> child = ((DnBranchNode<Partition>)partitionLookupTree).getChild( "dc=com" );
assertTrue( child instanceof DnBranchNode );
- child = ((DnBranchNode<Partition>)node).getChild( "dc=com" );
+ child = ((DnBranchNode<Partition>)partitionLookupTree).getChild( "dc=com" );
assertTrue( child instanceof DnBranchNode );
assertTrue( ((DnBranchNode<Partition>)child).contains( "dc=example1" ) );
assertTrue( ((DnBranchNode<Partition>)child).contains( "dc=example2" ) );
Modified: directory/shared/trunk/ldap/src/main/java/org/apache/directory/shared/ldap/util/tree/DnBranchNode.java
URL: http://svn.apache.org/viewvc/directory/shared/trunk/ldap/src/main/java/org/apache/directory/shared/ldap/util/tree/DnBranchNode.java?rev=697846&r1=697845&r2=697846&view=diff
==============================================================================
--- directory/shared/trunk/ldap/src/main/java/org/apache/directory/shared/ldap/util/tree/DnBranchNode.java (original)
+++ directory/shared/trunk/ldap/src/main/java/org/apache/directory/shared/ldap/util/tree/DnBranchNode.java Mon Sep 22 07:25:44 2008
@@ -77,7 +77,7 @@
* @param element The associated element to add as a tree node
* @return The modified tree structure.
*/
- public DnNode<N> recursivelyAddElement( DnBranchNode<N> current, LdapDN dn, int index, N element ) throws NamingException
+ private DnNode<N> recursivelyAddElement( DnBranchNode<N> current, LdapDN dn, int index, N element ) throws NamingException
{
String rdnAtIndex = dn.getRdn( index ).toString();
@@ -152,41 +152,6 @@
/**
- * @see Object#toString()
- */
- public String toString()
- {
- StringBuilder sb = new StringBuilder();
- sb.append( "{" );
- boolean isFirst = true;
-
- for ( DnNode<N> child:children.values() )
- {
- if ( isFirst )
- {
- isFirst = false;
- }
- else
- {
- sb.append( ", " );
- }
-
- if ( child instanceof DnBranchNode )
- {
- sb.append( "Branch: ").append( child.toString() );
- }
- else
- {
- sb.append( "Leaf: " ).append( "'" ).append( child.toString() ).append( "'" );
- }
- }
-
- sb.append( "}" );
- return sb.toString();
- }
-
-
- /**
* Get the parent of a given DN, if present in the tree. This parent should be a
* subset of the given dn.<br>
* For instance, if we have stored dc=acme, dc=org into the tree,
@@ -291,4 +256,126 @@
return false;
}
+
+
+ /**
+ * Tells if a branchNode has some children or not
+ *
+ * @return <code>true</code> if the node has some children
+ */
+ public boolean hasChildren()
+ {
+ return children.size() != 0;
+ }
+
+
+ /**
+ * Removes an element from the tree.
+ *
+ * @param element The element to remove
+ */
+ private boolean recursivelyRemoveElement( DnBranchNode<N> currentNode, N element )
+ {
+ // It might be a leaf
+ for ( String key: currentNode.children.keySet() )
+ {
+ DnNode<N> child = currentNode.children.get( key );
+
+ if ( child instanceof DnLeafNode )
+ {
+ if ( ((DnLeafNode<N>)child).getElement().equals( element ) )
+ {
+ // found ! Remove it from the children
+ currentNode.children.remove( key );
+ return true;
+ }
+ }
+ else
+ {
+ if ( recursivelyRemoveElement( (DnBranchNode<N>)child, element ) )
+ {
+ if ( ((DnBranchNode<N>)child).children.size() == 0 )
+ {
+ // If there are no more children, we can remove the node
+ currentNode.children.remove( key );
+ return true;
+ }
+ }
+ }
+ }
+
+
+ return false;
+ }
+
+
+ /**
+ *
+ * TODO add.
+ *
+ * @param dn
+ * @param element
+ * @throws NamingException
+ */
+ public void add( LdapDN dn, N element ) throws NamingException
+ {
+ recursivelyAddElement( this, dn, 0, element );
+ }
+
+
+ /**
+ * Removes an element from the tree.
+ *
+ * @param element The element to remove
+ */
+ public void remove( N element )
+ {
+ DnBranchNode<N> currentNode = this;
+
+ if ( currentNode.hasChildren() )
+ {
+ recursivelyRemoveElement( currentNode, element );
+ }
+ else
+ {
+
+ }
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+ sb.append( "{" );
+ boolean isFirst = true;
+
+ for ( String key:children.keySet() )
+ {
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ sb.append( ", " );
+ }
+
+ DnNode<N> child = children.get( key );
+
+ if ( child instanceof DnBranchNode )
+ {
+ sb.append( "Branch[" ).append( key ).append( "]: ").append( child );
+ }
+ else
+ {
+ sb.append( "Leaf: " ).append( "'" ).append( child ).append( "'" );
+ }
+ }
+
+ sb.append( "}" );
+ return sb.toString();
+ }
}
Added: directory/shared/trunk/ldap/src/test/java/org/apache/directory/shared/ldap/util/tree/TestDnNode.java
URL: http://svn.apache.org/viewvc/directory/shared/trunk/ldap/src/test/java/org/apache/directory/shared/ldap/util/tree/TestDnNode.java?rev=697846&view=auto
==============================================================================
--- directory/shared/trunk/ldap/src/test/java/org/apache/directory/shared/ldap/util/tree/TestDnNode.java (added)
+++ directory/shared/trunk/ldap/src/test/java/org/apache/directory/shared/ldap/util/tree/TestDnNode.java Mon Sep 22 07:25:44 2008
@@ -0,0 +1,182 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.shared.ldap.util.tree;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.assertFalse;
+
+import javax.naming.NamingException;
+
+import org.apache.directory.shared.ldap.name.LdapDN;
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+
+
+/**
+ * Test the Dn Nodes
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class TestDnNode
+{
+ /** A structure to hold all the DNs */
+ DnBranchNode<LdapDN> dnLookupTree;
+ LdapDN dn1;
+ LdapDN dn2;
+ LdapDN dn3;
+ LdapDN dn4;
+ LdapDN dn5;
+ LdapDN dn6;
+
+ /**
+ * Create the elements we will test
+ */
+ @Before
+ public void setUp() throws Exception
+ {
+ dnLookupTree = new DnBranchNode<LdapDN>();
+
+ dn1 = new LdapDN( "dc=directory,dc=apache,dc=org" );
+ dn2 = new LdapDN( "dc=mina,dc=apache,dc=org" );
+ dn3 = new LdapDN( "dc=test,dc=com" );
+ dn4 = new LdapDN( "dc=acme,dc=com" );
+ dn5 = new LdapDN( "dc=acme,c=us,dc=com" );
+ dn6 = new LdapDN( "dc=empty" );
+
+ dnLookupTree.add( dn1, dn1 );
+ dnLookupTree.add( dn2, dn2 );
+ dnLookupTree.add( dn3, dn3 );
+ dnLookupTree.add( dn4, dn4 );
+ dnLookupTree.add( dn5, dn5 );
+ dnLookupTree.add( dn6, dn6 );
+ }
+
+
+ /**
+ * Clean the tree
+ *
+ */
+ @After
+ public void tearDown()
+ {
+ dnLookupTree = null;
+ }
+
+
+ /**
+ * Test the addition of a single DN
+ */
+ @Test public void testNewTree() throws NamingException
+ {
+ /** A structure to hold all the DNs */
+ DnBranchNode<LdapDN> dnLookupTree = new DnBranchNode<LdapDN>();
+
+ LdapDN suffix = new LdapDN( "dc=example, dc=com" );
+
+ dnLookupTree.add( suffix, suffix );
+
+ assertNotNull( dnLookupTree );
+ assertTrue( dnLookupTree instanceof DnBranchNode );
+ assertTrue( ((DnBranchNode<LdapDN>)dnLookupTree).contains( "dc=com" ) );
+
+ DnNode<LdapDN> child = ((DnBranchNode<LdapDN>)dnLookupTree).getChild( "dc=com" );
+ assertTrue( child instanceof DnBranchNode );
+ assertTrue( ((DnBranchNode<LdapDN>)child).contains( "dc=example" ) );
+
+ child = ((DnBranchNode<LdapDN>)child).getChild( "dc=example" );
+ assertEquals( suffix, ((DnLeafNode<LdapDN>)child).getElement() );
+ }
+
+
+ /**
+ * Test additions in a tree
+ */
+ @Test
+ public void testComplexTreeCreation() throws NamingException
+ {
+
+ assertTrue( dnLookupTree.hasParentElement( dn1 ) );
+ assertTrue( dnLookupTree.hasParentElement( dn2 ) );
+ assertTrue( dnLookupTree.hasParentElement( dn3 ) );
+ assertTrue( dnLookupTree.hasParentElement( dn4 ) );
+ assertTrue( dnLookupTree.hasParentElement( dn5 ) );
+ assertTrue( dnLookupTree.hasParentElement( dn6 ) );
+ assertTrue( dnLookupTree.hasParentElement( new LdapDN( "dc=nothing,dc=empty" ) ) );
+ assertFalse( dnLookupTree.hasParentElement( new LdapDN( "dc=directory,dc=apache,dc=root" ) ) );
+ }
+
+ /**
+ * test the deletion of elements in a tree
+ */
+ @Test
+ public void testComplexTreeDeletion() throws NamingException
+ {
+ dnLookupTree.remove( dn3 );
+ assertTrue( dnLookupTree.hasParentElement( dn1 ) );
+ assertTrue( dnLookupTree.hasParentElement( dn2 ) );
+ assertTrue( dnLookupTree.hasParentElement( dn4 ) );
+ assertTrue( dnLookupTree.hasParentElement( dn5 ) );
+ assertTrue( dnLookupTree.hasParentElement( dn6 ) );
+ assertTrue( dnLookupTree.hasParentElement( new LdapDN( "dc=nothing,dc=empty" ) ) );
+ assertFalse( dnLookupTree.hasParentElement( new LdapDN( "dc=directory,dc=apache,dc=root" ) ) );
+
+ dnLookupTree.remove( dn6 );
+ assertTrue( dnLookupTree.hasParentElement( dn1 ) );
+ assertTrue( dnLookupTree.hasParentElement( dn2 ) );
+ assertTrue( dnLookupTree.hasParentElement( dn4 ) );
+ assertTrue( dnLookupTree.hasParentElement( dn5 ) );
+ assertFalse( dnLookupTree.hasParentElement( new LdapDN( "dc=nothing,dc=empty" ) ) );
+ assertFalse( dnLookupTree.hasParentElement( new LdapDN( "dc=directory,dc=apache,dc=root" ) ) );
+
+ dnLookupTree.remove( dn1 );
+ assertTrue( dnLookupTree.hasParentElement( dn2 ) );
+ assertTrue( dnLookupTree.hasParentElement( dn4 ) );
+ assertTrue( dnLookupTree.hasParentElement( dn5 ) );
+ assertFalse( dnLookupTree.hasParentElement( new LdapDN( "dc=nothing,dc=empty" ) ) );
+ assertFalse( dnLookupTree.hasParentElement( new LdapDN( "dc=directory,dc=apache,dc=root" ) ) );
+
+ // Should not change anything
+ dnLookupTree.remove( dn3 );
+ assertTrue( dnLookupTree.hasParentElement( dn2 ) );
+ assertTrue( dnLookupTree.hasParentElement( dn4 ) );
+ assertTrue( dnLookupTree.hasParentElement( dn5 ) );
+ assertFalse( dnLookupTree.hasParentElement( new LdapDN( "dc=nothing,dc=empty" ) ) );
+ assertFalse( dnLookupTree.hasParentElement( new LdapDN( "dc=directory,dc=apache,dc=root" ) ) );
+
+ dnLookupTree.remove( dn5 );
+ assertTrue( dnLookupTree.hasParentElement( dn2 ) );
+ assertTrue( dnLookupTree.hasParentElement( dn4 ) );
+ assertFalse( dnLookupTree.hasParentElement( new LdapDN( "dc=nothing,dc=empty" ) ) );
+ assertFalse( dnLookupTree.hasParentElement( new LdapDN( "dc=directory,dc=apache,dc=root" ) ) );
+
+ dnLookupTree.remove( dn2 );
+ assertTrue( dnLookupTree.hasParentElement( dn4 ) );
+ assertFalse( dnLookupTree.hasParentElement( new LdapDN( "dc=nothing,dc=empty" ) ) );
+ assertFalse( dnLookupTree.hasParentElement( new LdapDN( "dc=directory,dc=apache,dc=root" ) ) );
+
+ dnLookupTree.remove( dn4 );
+ assertFalse( dnLookupTree.hasParentElement( new LdapDN( "dc=nothing,dc=empty" ) ) );
+ assertFalse( dnLookupTree.hasParentElement( new LdapDN( "dc=directory,dc=apache,dc=root" ) ) );
+ }
+}