From commits-return-31821-apmail-directory-commits-archive=directory.apache.org@directory.apache.org Wed May 18 15:34:12 2011 Return-Path: X-Original-To: apmail-directory-commits-archive@www.apache.org Delivered-To: apmail-directory-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id D89036C8A for ; Wed, 18 May 2011 15:34:12 +0000 (UTC) Received: (qmail 16202 invoked by uid 500); 18 May 2011 15:34:12 -0000 Delivered-To: apmail-directory-commits-archive@directory.apache.org Received: (qmail 16155 invoked by uid 500); 18 May 2011 15:34:12 -0000 Mailing-List: contact commits-help@directory.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@directory.apache.org Delivered-To: mailing list commits@directory.apache.org Received: (qmail 16148 invoked by uid 99); 18 May 2011 15:34:12 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Wed, 18 May 2011 15:34:12 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Wed, 18 May 2011 15:34:07 +0000 Received: by eris.apache.org (Postfix, from userid 65534) id 4DB7823889E2; Wed, 18 May 2011 15:33:46 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r1124303 - in /directory/shared/trunk/ldap/extras/util/src: main/java/org/apache/directory/shared/ldap/util/tree/DnNode.java test/java/org/apache/directory/shared/ldap/util/tree/TestDnNode.java Date: Wed, 18 May 2011 15:33:46 -0000 To: commits@directory.apache.org From: kayyagari@apache.org X-Mailer: svnmailer-1.0.8 Message-Id: <20110518153346.4DB7823889E2@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org Author: kayyagari Date: Wed May 18 15:33:45 2011 New Revision: 1124303 URL: http://svn.apache.org/viewvc?rev=1124303&view=rev Log: reapplying all the commits from rev. 1051869, 1051970, 1053085, 1054545, 1055045, 1055125 and 1054996 all these are missing (probably due to a mistake while merging) o Added a method and a test to get the closest parent in a DnNode which has an element from a starting point. o The getParentWithElement should return the element, not the DN o Modified the getParentWithElement() method to return the node contaning an element instead of just returning the element. o added rename operation and a test o added move operation and tests and the latest change besides the above merge o replaced the ConcurrentHashmap to HashMap (DIRSHARED-73) Modified: directory/shared/trunk/ldap/extras/util/src/main/java/org/apache/directory/shared/ldap/util/tree/DnNode.java directory/shared/trunk/ldap/extras/util/src/test/java/org/apache/directory/shared/ldap/util/tree/TestDnNode.java Modified: directory/shared/trunk/ldap/extras/util/src/main/java/org/apache/directory/shared/ldap/util/tree/DnNode.java URL: http://svn.apache.org/viewvc/directory/shared/trunk/ldap/extras/util/src/main/java/org/apache/directory/shared/ldap/util/tree/DnNode.java?rev=1124303&r1=1124302&r2=1124303&view=diff ============================================================================== --- directory/shared/trunk/ldap/extras/util/src/main/java/org/apache/directory/shared/ldap/util/tree/DnNode.java (original) +++ directory/shared/trunk/ldap/extras/util/src/main/java/org/apache/directory/shared/ldap/util/tree/DnNode.java Wed May 18 15:33:45 2011 @@ -20,11 +20,12 @@ package org.apache.directory.shared.ldap.util.tree; import java.util.ArrayList; +import java.util.HashMap; import java.util.List; import java.util.Map; -import java.util.concurrent.ConcurrentHashMap; import org.apache.directory.shared.ldap.model.exception.LdapException; +import org.apache.directory.shared.ldap.model.exception.LdapInvalidDnException; import org.apache.directory.shared.ldap.model.exception.LdapUnwillingToPerformException; import org.apache.directory.shared.ldap.model.message.ResultCodeEnum; import org.apache.directory.shared.ldap.model.name.Dn; @@ -34,13 +35,13 @@ import org.slf4j.LoggerFactory; /** - * An class storing nodes in a tree designed to map DNs.
+ * A class storing nodes in a tree designed to map DNs.
* Branch nodes in this tree refers to child nodes. Leaf nodes in the tree * don't have any children.
* A node may contain a reference to an object whose suffix is the path through the * nodes of the tree from the root.
* A node may also have no attached element.
- * Each node is referenced by a Rdn, and holds the full Dn corresponding to its position
+ * Each child node is referenced by a Rdn, and holds the full Dn corresponding to its position
* * @author Apache Directory Project * @param The type of node we store @@ -132,7 +133,7 @@ public class DnNode implements Clonea /** * Store the given element into the node */ - private void setElement( N element ) + private synchronized void setElement( N element ) { this.nodeElement = element; } @@ -146,7 +147,7 @@ public class DnNode implements Clonea */ public DnNode() { - children = new ConcurrentHashMap>(); + children = new HashMap>(); nodeDn = Dn.EMPTY_DN; nodeRdn = Rdn.EMPTY_RDN; } @@ -160,7 +161,7 @@ public class DnNode implements Clonea public DnNode( N element ) { this.nodeElement = element; - children = new ConcurrentHashMap>(); + children = new HashMap>(); } @@ -174,7 +175,7 @@ public class DnNode implements Clonea { if ( ( dn == null ) || ( dn.isEmpty() ) ) { - children = new ConcurrentHashMap>(); + children = new HashMap>(); this.nodeDn = Dn.EMPTY_DN; return; @@ -206,7 +207,7 @@ public class DnNode implements Clonea * * @return true if the class is a leaf node, false otherwise. */ - public boolean isLeaf() + public synchronized boolean isLeaf() { return !hasChildren(); } @@ -219,7 +220,7 @@ public class DnNode implements Clonea * @param dn The Dn we want to check * @return true if this is a leaf node, false otherwise. */ - public boolean isLeaf( Dn dn ) + public synchronized boolean isLeaf( Dn dn ) { DnNode node = getNode( dn ); @@ -238,7 +239,7 @@ public class DnNode implements Clonea * * @return The number of descendents */ - public int size() + public synchronized int size() { // The node itself int size = 1; @@ -259,7 +260,7 @@ public class DnNode implements Clonea /** * @return Return the stored element, if any */ - public N getElement() + public synchronized N getElement() { return nodeElement; } @@ -269,7 +270,7 @@ public class DnNode implements Clonea * @return Return the stored element, if any * @param dn The Dn we want to get the element for */ - public N getElement( Dn dn ) + public synchronized N getElement( Dn dn ) { DnNode node = getNode( dn ); @@ -286,7 +287,7 @@ public class DnNode implements Clonea * @return True if the Node stores an element. BranchNode may not hold any * element. */ - public boolean hasElement() + public synchronized boolean hasElement() { return nodeElement != null; } @@ -297,7 +298,7 @@ public class DnNode implements Clonea * element. * @param dn The Dn we want to get the element for */ - public boolean hasElement( Dn dn ) + public synchronized boolean hasElement( Dn dn ) { DnNode node = getNode( dn ); @@ -313,7 +314,7 @@ public class DnNode implements Clonea /** * recursively check if the node has a descendant having an element */ - private boolean hasDescendantElement( DnNode node ) + private synchronized boolean hasDescendantElement( DnNode node ) { if ( node == null ) { @@ -343,7 +344,7 @@ public class DnNode implements Clonea * False otherwise * @param dn The Dn we want to get the element for */ - public boolean hasDescendantElement( Dn dn ) + public synchronized boolean hasDescendantElement( Dn dn ) { DnNode node = getNode( dn ); @@ -376,7 +377,7 @@ public class DnNode implements Clonea /** * recursively get all the elements from nodes having an element */ - private void getDescendantElements( DnNode node, List descendants ) + private synchronized void getDescendantElements( DnNode node, List descendants ) { if ( node == null ) { @@ -403,7 +404,7 @@ public class DnNode implements Clonea * False otherwise * @param dn The Dn we want to get the element for */ - public List getDescendantElements( Dn dn ) + public synchronized List getDescendantElements( Dn dn ) { List descendants = new ArrayList(); @@ -437,7 +438,7 @@ public class DnNode implements Clonea * * @return true if the node has some children */ - public boolean hasChildren() + public synchronized boolean hasChildren() { return ( children != null ) && children.size() != 0; } @@ -450,7 +451,7 @@ public class DnNode implements Clonea * @return true if the node has some children * @throws LdapException if the Dn is null or empty */ - public boolean hasChildren( Dn dn ) throws LdapException + public synchronized boolean hasChildren( Dn dn ) throws LdapException { checkDn( dn ); @@ -463,7 +464,7 @@ public class DnNode implements Clonea /** * @return The list of DnNode */ - public Map> getChildren() + public synchronized Map> getChildren() { return children; } @@ -472,7 +473,7 @@ public class DnNode implements Clonea /** * @return The parent DnNode, if any */ - public DnNode getParent() + public synchronized DnNode getParent() { return parent; } @@ -481,7 +482,7 @@ public class DnNode implements Clonea /** * @return True if the current DnNode has a parent */ - public boolean hasParent() + public synchronized boolean hasParent() { return parent != null; } @@ -497,14 +498,14 @@ public class DnNode implements Clonea * @param dn the normalized distinguished name to resolve to a parent * @return true if there is a parent associated with the normalized dn */ - public boolean hasParent( Dn dn ) + public synchronized boolean hasParent( Dn dn ) { List rdns = dn.getRdns(); DnNode currentNode = this; DnNode parentNode = null; - // Iterate through all the Rdn until we find the associated partition + // Iterate through all the Rdn until we find the associated element for ( int i = rdns.size() - 1; i >= 0; i-- ) { Rdn rdn = rdns.get( i ); @@ -540,7 +541,7 @@ public class DnNode implements Clonea * @param dn The node's Dn * @throws LdapException if the Dn is null or empty */ - public void add( Dn dn ) throws LdapException + public synchronized void add( Dn dn ) throws LdapException { add( dn, null ); } @@ -554,7 +555,7 @@ public class DnNode implements Clonea * @param element The element to associate with this Node. Can be null. * @throws LdapException if the Dn is null or empty */ - public void add( Dn dn, N element ) throws LdapException + public synchronized void add( Dn dn, N element ) throws LdapException { checkDn( dn ); @@ -613,7 +614,7 @@ public class DnNode implements Clonea * @param dn the node's Dn * @throws LdapException if the Dn is null or empty */ - public void remove( Dn dn ) throws LdapException + public synchronized void remove( Dn dn ) throws LdapException { checkDn( dn ); @@ -658,7 +659,7 @@ public class DnNode implements Clonea * @param rdn The name we are looking for * @return true if the tree instance contains this name */ - public boolean contains( Rdn rdn ) + public synchronized boolean contains( Rdn rdn ) { return children.containsKey( rdn ); } @@ -670,7 +671,7 @@ public class DnNode implements Clonea * @param rdn the rdn to use as the node key * @return the child node corresponding to the rdn. */ - public DnNode getChild( Rdn rdn ) + public synchronized DnNode getChild( Rdn rdn ) { if ( children.containsKey( rdn ) ) { @@ -684,7 +685,7 @@ public class DnNode implements Clonea /** * @return The Node's Rdn */ - public Rdn getRdn() + public synchronized Rdn getRdn() { return nodeRdn; } @@ -700,7 +701,7 @@ public class DnNode implements Clonea * @param dn the normalized distinguished name to resolve to a parent * @return the Node associated with the normalized dn */ - public DnNode getNode( Dn dn ) + public synchronized DnNode getNode( Dn dn ) { List rdns = dn.getRdns(); @@ -743,7 +744,7 @@ public class DnNode implements Clonea * @param dn the normalized distinguished name to resolve to a parent * @return the Node associated with the normalized dn */ - public boolean hasParentElement( Dn dn ) + public synchronized boolean hasParentElement( Dn dn ) { List rdns = dn.getRdns(); @@ -780,11 +781,189 @@ public class DnNode implements Clonea return hasElement; } + + /** + * Get the closest Node for a given Dn which has an element, if present in the tree.
+ * For instance, if we have stored dc=acme, dc=org into the tree, + * the Dn: ou=example, dc=acme, dc=org will have a parent, and + * dc=acme, dc=org will be returned if it has an associated element. + *
For the Dn ou=apache, dc=org, there is no parent, so null will be returned. + * + * @param dn the normalized distinguished name to resolve to a parent + * @return the Node associated with the normalized dn + */ + public synchronized DnNode getParentWithElement( Dn dn ) + { + List rdns = dn.getRdns(); + + DnNode currentNode = this; + DnNode element = null; + + // Iterate through all the Rdn until we find the associated partition + for ( int i = rdns.size() - 1; i >= 1; i-- ) + { + Rdn rdn = rdns.get( i ); + + if ( currentNode.hasChildren() ) + { + currentNode = currentNode.children.get( rdn ); + + if ( currentNode == null ) + { + break; + } + + if ( currentNode.hasElement() ) + { + element = currentNode; + } + + parent = currentNode; + } + else + { + break; + } + } + + return element; + } + + + /** + * Get the closest Node for a given Dn which has an element, if present in the tree.
+ * For instance, if we have stored dc=acme, dc=org into the tree, + * the Dn: ou=example, dc=acme, dc=org will have a parent, and + * dc=acme, dc=org will be returned if it has an associated element. + *
For the Dn ou=apache, dc=org, there is no parent, so null will be returned. + * + * @param dn the normalized distinguished name to resolve to a parent + * @return the Node associated with the normalized dn + */ + public synchronized DnNode getParentWithElement() + { + DnNode currentNode = parent; + + while ( currentNode != null ) + { + if ( currentNode.nodeElement != null ) + { + return currentNode; + } + + currentNode = currentNode.parent; + } + + return null; + } + + + /** + * rename the DnNode's Dn + * + * @param newRdn the new Rdn of this node + * @throws LdapException + */ + public synchronized void rename( Rdn newRdn ) throws LdapException + { + Dn temp = nodeDn.getParent(); + temp = temp.add( newRdn ); + + Rdn oldRdn = nodeRdn; + + nodeRdn = temp.getRdn(); + nodeDn = temp; + + if ( parent != null ) + { + parent.children.remove( oldRdn ); + parent.children.put( nodeRdn, this ); + } + + updateAfterModDn( nodeDn ); + } + + + /** + * move the DnNode's Dn + * + * @param newParent the new parent Dn + * @throws LdapException + */ + public synchronized void move( Dn newParent ) throws LdapException + { + DnNode tmp = null; + + Dn tmpDn = null; + + // check if the new parent Dn is child of the parent + if( newParent.isDescendantOf( parent.nodeDn ) ) + { + tmp = parent; + tmpDn = parent.nodeDn; + } + + // if yes, then drill for the new parent node + if ( tmpDn != null ) + { + int parentNodeSize = tmpDn.size(); + int count = newParent.size() - parentNodeSize; + + while( count-- > 0 ) + { + tmp = tmp.getChild( newParent.getRdn( parentNodeSize++ ) ); + } + } + + // if not, we have to traverse all the way up to the + // root node and then find the new parent node + if ( tmp == null ) + { + tmp = this; + while( tmp.parent != null ) + { + tmp = tmp.parent; + } + + tmp = tmp.getNode( newParent ); + } + + nodeDn = newParent.add( nodeRdn ); + updateAfterModDn( nodeDn ); + + if( parent != null ) + { + parent.children.remove( nodeRdn ); + } + + parent = tmp; + parent.children.put( nodeRdn, this ); + } + + + /** + * update the children's Dn based on the new parent Dn created + * after a rename or move operation + * + * @param newParentDn + */ + private synchronized void updateAfterModDn( Dn newParentDn ) throws LdapInvalidDnException + { + if ( children != null ) + { + for( DnNode child : children.values() ) + { + child.nodeDn = newParentDn.add( child.nodeRdn ); + child.updateAfterModDn( child.nodeDn ); + } + } + } + /** * {@inheritDoc} */ - public DnNode clone() + public synchronized DnNode clone() { DnNode clonedDnNode = new DnNode(); @@ -868,7 +1047,7 @@ public class DnNode implements Clonea /** * @return the dn */ - public Dn getDn() + public synchronized Dn getDn() { return nodeDn; } Modified: directory/shared/trunk/ldap/extras/util/src/test/java/org/apache/directory/shared/ldap/util/tree/TestDnNode.java URL: http://svn.apache.org/viewvc/directory/shared/trunk/ldap/extras/util/src/test/java/org/apache/directory/shared/ldap/util/tree/TestDnNode.java?rev=1124303&r1=1124302&r2=1124303&view=diff ============================================================================== --- directory/shared/trunk/ldap/extras/util/src/test/java/org/apache/directory/shared/ldap/util/tree/TestDnNode.java (original) +++ directory/shared/trunk/ldap/extras/util/src/test/java/org/apache/directory/shared/ldap/util/tree/TestDnNode.java Wed May 18 15:33:45 2011 @@ -802,4 +802,131 @@ public class TestDnNode dns = dnLookupTree.getDescendantElements( dn6 ); assertEquals( 0, dns.size() ); } + + //--------------------------------------------------------------------------- + // Test the getParentElement(DN) method + //--------------------------------------------------------------------------- + @Test + public void testGetParentElement() throws Exception + { + DnNode dnLookupTree = new DnNode(); + Dn dn1 = new Dn( "dc=directory,dc=apache,dc=org" ); + Dn dn2 = new Dn( "dc=mina,dc=apache,dc=org" ); + Dn dn3 = new Dn( "dc=test,dc=com" ); + Dn dn4 = new Dn( "dc=acme,dc=com" ); + Dn dn5 = new Dn( "dc=acme,c=us,dc=com" ); + Dn dn6 = new Dn( "dc=empty" ); + + Dn org = new Dn( "dc=org" ); + Dn apache = new Dn( "dc=apache,dc=org" ); + Dn test = new Dn( "dc=test,dc=directory,dc=apache,dc=org" ); + + dnLookupTree.add( dn1, dn1 ); + dnLookupTree.add( dn2, dn2 ); + dnLookupTree.add( dn3, dn3 ); + dnLookupTree.add( dn4, dn4 ); + dnLookupTree.add( dn5 ); + dnLookupTree.add( dn6, dn6 ); + + // Inject some intermediary nodes + dnLookupTree.add( org, org ); + + assertTrue( dnLookupTree.hasParentElement( apache ) ); + assertEquals( org, dnLookupTree.getParentWithElement( dn1 ).getElement() ); + assertEquals( org, dnLookupTree.getParentWithElement( apache ).getElement() ); + assertEquals( dn1, dnLookupTree.getParentWithElement( test ).getElement() ); + assertNull( dnLookupTree.getParentWithElement( org ) ); + } + + + @Test + public void testRename() throws Exception + { + DnNode rootNode = new DnNode(); + Dn dn = new Dn( "dc=directory,dc=apache,dc=org" ); + rootNode.add( dn ); + + Rdn childRdn = new Rdn( "dc=org" ); + + DnNode child = rootNode.getChild( childRdn ); + assertNotNull( child ); + + Rdn newChildRdn = new Rdn( "dc=neworg" ); + + child.rename( newChildRdn ); + assertNull( rootNode.getChild( childRdn ) ); + assertEquals( new Dn( "dc=neworg" ), child.getDn() ); + + DnNode child2 = child.getChild( new Rdn( "dc=apache" ) ); + assertEquals( new Dn( "dc=apache,dc=neworg" ), child2.getDn() ); + + assertEquals( new Dn( "dc=directory,dc=apache,dc=neworg" ), child2.getChild( new Rdn( "dc=directory" ) ).getDn() ); + + assertNotNull( rootNode.getChild( newChildRdn ) ); + } + + + @Test + public void testMoveToAnAncestor() throws Exception + { + DnNode rootNode = new DnNode(); + Dn dn = new Dn( "dc=vysper,dc=mina,dc=directory,dc=apache,dc=org" ); + + rootNode.add( dn ); + + Rdn minaRdn = new Rdn( "dc=mina" ); + DnNode apacheNode = rootNode.getChild( new Rdn( "dc=org" ) ).getChild( new Rdn( "dc=apache" ) ); + DnNode directoryNode = apacheNode.getChild( new Rdn( "dc=directory" ) ); + DnNode minaNode = directoryNode.getChild( minaRdn ); + assertNotNull( minaNode ); + assertEquals( directoryNode, minaNode.getParent() ); + assertTrue( directoryNode.contains( minaRdn ) ); + + Dn newParent = new Dn( "dc=apache,dc=org" ); + minaNode.move( newParent ); + + minaNode = apacheNode.getChild( minaRdn ); + assertNotNull( minaNode ); + assertNull( directoryNode.getChild( minaRdn ) ); + assertNotNull( apacheNode.getChild( minaRdn ) ); + assertFalse( directoryNode.contains( minaRdn ) ); + assertTrue( apacheNode.contains( minaRdn ) ); + + assertEquals( new Dn( "dc=mina,dc=apache,dc=org" ), minaNode.getDn() ); + assertEquals( new Dn( "dc=vysper,dc=mina,dc=apache,dc=org" ), minaNode.getChild( new Rdn( "dc=vysper" ) ).getDn()); + } + + + @Test + public void testMoveToSiblingBranch() throws Exception + { + DnNode rootNode = new DnNode(); + Dn dn1 = new Dn( "dc=vysper,dc=mina,dc=directory,dc=apache,dc=org" ); + + Dn dn2 = new Dn( "dc=kayyagari,dc=apache,dc=org" ); + rootNode.add( dn1 ); + rootNode.add( dn2 ); + + Rdn directoryRdn = new Rdn( "dc=directory" ); + + DnNode apacheNode = rootNode.getChild( new Rdn( "dc=org" ) ).getChild( new Rdn( "dc=apache" ) ); + DnNode directoryNode = apacheNode.getChild( new Rdn( "dc=directory" ) ); + assertNotNull( directoryNode ); + assertEquals( apacheNode, directoryNode.getParent() ); + assertTrue( apacheNode.contains( directoryRdn ) ); + + directoryNode.move( dn2 ); + + DnNode newParentNode = rootNode.getChild( new Rdn( "dc=org" ) ).getChild( new Rdn( "dc=apache" ) ).getChild( new Rdn( "dc=kayyagari" ) ); + directoryNode = newParentNode.getChild( directoryRdn ); + assertNotNull( directoryNode ); + assertNull( apacheNode.getChild( directoryRdn ) ); + assertNotNull( newParentNode.getChild( directoryRdn ) ); + assertFalse( apacheNode.contains( directoryRdn ) ); + assertTrue( newParentNode.contains( directoryRdn ) ); + + assertEquals( new Dn( "dc=directory,dc=kayyagari,dc=apache,dc=org" ), directoryNode.getDn() ); + assertEquals( new Dn( "dc=mina,dc=directory,dc=kayyagari,dc=apache,dc=org" ), directoryNode.getChild( new Rdn( "dc=mina" ) ).getDn()); + assertEquals( new Dn( "dc=vysper,dc=mina,dc=directory,dc=kayyagari,dc=apache,dc=org" ), directoryNode.getChild( new Rdn( "dc=mina" ) ).getChild( new Rdn( "dc=vysper" ) ).getDn()); + } }