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 27EDC815A for ; Tue, 16 Aug 2011 19:56:41 +0000 (UTC) Received: (qmail 12227 invoked by uid 500); 16 Aug 2011 19:56:41 -0000 Delivered-To: apmail-directory-commits-archive@directory.apache.org Received: (qmail 12151 invoked by uid 500); 16 Aug 2011 19:56:40 -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 12138 invoked by uid 99); 16 Aug 2011 19:56:40 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 16 Aug 2011 19:56:40 +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; Tue, 16 Aug 2011 19:56:28 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id 91D2623889DD for ; Tue, 16 Aug 2011 19:56:06 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r1158430 [1/2] - in /directory/apacheds/branches/one-sub-level-index-removal: core-constants/src/main/java/org/apache/directory/server/constants/ jdbm-partition/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/ ldif-... Date: Tue, 16 Aug 2011 19:56:05 -0000 To: commits@directory.apache.org From: seelmann@apache.org X-Mailer: svnmailer-1.0.8 Message-Id: <20110816195606.91D2623889DD@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org Author: seelmann Date: Tue Aug 16 19:56:04 2011 New Revision: 1158430 URL: http://svn.apache.org/viewvc?rev=1158430&view=rev Log: First version of one-level and sub-level index removal: * added one-level and sub-level counters to ParentIdAndRdn * changed compare order in ParentIdAndRdn (parentId is compared before RDN) to ensure proper order in RdnIndexTreeCursor * introduced RdnIndexTreeCursor and RdnIndexHelper * removed one-level index and sub-level index from AbstractBTreePartiton * fixes in tests due to changed order in index since RDN index is ordered by parentId and RDN instead of ID * simplified write-out of partiton data in SingleFileLdifPartiton by using the RDN index based cursor * introduced abstract TestBase for XDBM tests * removed constants for one-level and sub-level index Added: directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/RdnIndexHelper.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/RdnIndexTreeCursor.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/RdnIndexHelperTest.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/RdnIndexTreeCursorTest.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/TestBase.java Modified: directory/apacheds/branches/one-sub-level-index-removal/core-constants/src/main/java/org/apache/directory/server/constants/ApacheSchemaConstants.java directory/apacheds/branches/one-sub-level-index-removal/jdbm-partition/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmStoreTest.java directory/apacheds/branches/one-sub-level-index-removal/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/LdifPartition.java directory/apacheds/branches/one-sub-level-index-removal/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/SingleFileLdifPartition.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ParentIdAndRdn.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/Store.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/DefaultOptimizer.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/OneLevelScopeCursor.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/OneLevelScopeEvaluator.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/SubtreeScopeCursor.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/SubtreeScopeEvaluator.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/PartitionTest.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/impl/avl/AvlPartitionTest.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/AndCursorTest.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/GreaterEqTest.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/LessEqTest.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/NotCursorTest.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/OneLevelScopeTest.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/OrCursorTest.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/PresenceTest.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/SubstringTest.java directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/SubtreeScopeTest.java Modified: directory/apacheds/branches/one-sub-level-index-removal/core-constants/src/main/java/org/apache/directory/server/constants/ApacheSchemaConstants.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/one-sub-level-index-removal/core-constants/src/main/java/org/apache/directory/server/constants/ApacheSchemaConstants.java?rev=1158430&r1=1158429&r2=1158430&view=diff ============================================================================== --- directory/apacheds/branches/one-sub-level-index-removal/core-constants/src/main/java/org/apache/directory/server/constants/ApacheSchemaConstants.java (original) +++ directory/apacheds/branches/one-sub-level-index-removal/core-constants/src/main/java/org/apache/directory/server/constants/ApacheSchemaConstants.java Tue Aug 16 19:56:04 2011 @@ -106,10 +106,6 @@ public final class ApacheSchemaConstants public final static String APACHE_PRESENCE_AT = "ApachePresence"; public final static String APACHE_PRESENCE_AT_OID = "1.3.6.1.4.1.18060.0.4.1.2.3"; - // ApacheOneLevel - public final static String APACHE_ONE_LEVEL_AT = "apacheOneLevel"; - public final static String APACHE_ONE_LEVEL_AT_OID = "1.3.6.1.4.1.18060.0.4.1.2.4"; - // ApacheOneAlias public final static String APACHE_ONE_ALIAS_AT = "apacheOneAlias"; public final static String APACHE_ONE_ALIAS_AT_OID = "1.3.6.1.4.1.18060.0.4.1.2.5"; @@ -157,10 +153,6 @@ public final class ApacheSchemaConstants public final static String SUBSCHEMA_SUBENTRY_NAME_AT = "subschemaSubentryName"; public final static String SUBSCHEMA_SUBENTRY_NAME_AT_OID = "1.3.6.1.4.1.18060.0.4.1.2.37"; - // apacheSubLevel - public final static String APACHE_SUB_LEVEL_AT = "apacheSubLevel"; - public final static String APACHE_SUB_LEVEL_AT_OID = "1.3.6.1.4.1.18060.0.4.1.2.43"; - // apacheRdn public final static String APACHE_RDN_AT = "apacheRdn"; public final static String APACHE_RDN_AT_OID = "1.3.6.1.4.1.18060.0.4.1.2.50"; Modified: directory/apacheds/branches/one-sub-level-index-removal/jdbm-partition/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmStoreTest.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/one-sub-level-index-removal/jdbm-partition/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmStoreTest.java?rev=1158430&r1=1158429&r2=1158430&view=diff ============================================================================== --- directory/apacheds/branches/one-sub-level-index-removal/jdbm-partition/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmStoreTest.java (original) +++ directory/apacheds/branches/one-sub-level-index-removal/jdbm-partition/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmStoreTest.java Tue Aug 16 19:56:04 2011 @@ -249,14 +249,6 @@ public class JdbmStoreTest jdbmPartition.addIndex( new JdbmIndex( ApacheSchemaConstants.APACHE_PRESENCE_AT_OID ) ); assertNotNull( jdbmPartition.getPresenceIndex() ); - assertNull( jdbmPartition.getOneLevelIndex() ); - ((Store)jdbmPartition).addIndex( new JdbmIndex( ApacheSchemaConstants.APACHE_ONE_LEVEL_AT_OID ) ); - assertNotNull( jdbmPartition.getOneLevelIndex() ); - - assertNull( jdbmPartition.getSubLevelIndex() ); - ((Store)jdbmPartition).addIndex( new JdbmIndex( ApacheSchemaConstants.APACHE_SUB_LEVEL_AT_OID ) ); - assertNotNull( jdbmPartition.getSubLevelIndex() ); - assertNull( jdbmPartition.getId() ); jdbmPartition.setId( "foo" ); assertEquals( "foo", jdbmPartition.getId() ); @@ -330,26 +322,6 @@ public class JdbmStoreTest { } - assertNotNull( store.getOneLevelIndex() ); - try - { - store.addIndex( new JdbmIndex( ApacheSchemaConstants.APACHE_ONE_LEVEL_AT_OID ) ); - fail(); - } - catch ( IllegalStateException e ) - { - } - - assertNotNull( store.getSubLevelIndex() ); - try - { - store.addIndex( new JdbmIndex( ApacheSchemaConstants.APACHE_SUB_LEVEL_AT_OID ) ); - fail(); - } - catch ( IllegalStateException e ) - { - } - assertNotNull( store.getId() ); try { @@ -404,7 +376,7 @@ public class JdbmStoreTest Iterator systemIndices = store.getSystemIndices(); - for ( int ii = 0; ii < 10; ii++ ) + for ( int ii = 0; ii < 8; ii++ ) { assertTrue( systemIndices.hasNext() ); assertNotNull( systemIndices.next() ); @@ -514,8 +486,12 @@ public class JdbmStoreTest assertNotNull( cursor ); cursor.beforeFirst(); assertTrue( cursor.next() ); - assertEquals( 2L, ( long ) cursor.get().getId() ); + assertEquals( 3L, ( long ) cursor.get().getId() ); assertTrue( cursor.next() ); + assertEquals( 4L, ( long ) cursor.get().getId() ); + assertTrue( cursor.next() ); + assertEquals( 2L, ( long ) cursor.get().getId() ); + assertFalse( cursor.next() ); assertEquals( 3, store.getChildCount( 1L ) ); store.delete( 2L ); @@ -541,117 +517,6 @@ public class JdbmStoreTest @Test - public void testSubLevelIndex() throws Exception - { - Index idx = store.getSubLevelIndex(); - - assertEquals( 19, idx.count() ); - - Cursor> cursor = idx.forwardCursor( 2L ); - - assertTrue( cursor.next() ); - assertEquals( 2, ( long ) cursor.get().getId() ); - - assertTrue( cursor.next() ); - assertEquals( 5, ( long ) cursor.get().getId() ); - - assertTrue( cursor.next() ); - assertEquals( 6, ( long ) cursor.get().getId() ); - - assertFalse( cursor.next() ); - - idx.drop( 5L ); - - cursor = idx.forwardCursor( 2L ); - - assertTrue( cursor.next() ); - assertEquals( 2, ( long ) cursor.get().getId() ); - - assertTrue( cursor.next() ); - assertEquals( 6, ( long ) cursor.get().getId() ); - - assertFalse( cursor.next() ); - - // dn id 12 - Dn martinDn = new Dn( schemaManager, "cn=Marting King,ou=Sales,o=Good Times Co." ); - Entry entry = new DefaultEntry( schemaManager, martinDn ); - entry.add( "objectClass", "top", "person", "organizationalPerson" ); - entry.add( "ou", "Sales" ); - entry.add( "cn", "Martin King" ); - entry.add( "entryCSN", new CsnFactory( 1 ).newInstance().toString() ); - entry.add( "entryUUID", UUID.randomUUID().toString() ); - AddOperationContext addContext = new AddOperationContext( null, entry ); - store.add( addContext ); - - cursor = idx.forwardCursor( 2L ); - cursor.afterLast(); - assertTrue( cursor.previous() ); - assertEquals( 12, ( long ) cursor.get().getId() ); - - Dn newParentDn = new Dn( schemaManager, "ou=Board of Directors,o=Good Times Co." ); - - Dn newDn = newParentDn.add( martinDn.getRdn() ); - - store.move( martinDn, newParentDn, newDn, entry ); - cursor = idx.forwardCursor( 3L ); - cursor.afterLast(); - assertTrue( cursor.previous() ); - assertEquals( 12, ( long ) cursor.get().getId() ); - - // dn id 13 - Dn marketingDn = new Dn( schemaManager, "ou=Marketing,ou=Sales,o=Good Times Co." ); - entry = new DefaultEntry( schemaManager, marketingDn ); - entry.add( "objectClass", "top", "organizationalUnit" ); - entry.add( "ou", "Marketing" ); - entry.add( "entryCSN", new CsnFactory( 1 ).newInstance().toString() ); - entry.add( "entryUUID", UUID.randomUUID().toString() ); - addContext = new AddOperationContext( null, entry ); - store.add( addContext ); - - // dn id 14 - Dn jimmyDn = new Dn( schemaManager, "cn=Jimmy Wales,ou=Marketing, ou=Sales,o=Good Times Co." ); - entry = new DefaultEntry( schemaManager, jimmyDn ); - entry.add( "objectClass", "top", "person", "organizationalPerson" ); - entry.add( "ou", "Marketing" ); - entry.add( "cn", "Jimmy Wales" ); - entry.add( "entryCSN", new CsnFactory( 1 ).newInstance().toString() ); - entry.add( "entryUUID", UUID.randomUUID().toString() ); - addContext = new AddOperationContext( null, entry ); - store.add( addContext ); - - newDn = newParentDn.add( marketingDn.getRdn() ); - - store.move( marketingDn, newParentDn, newDn, entry ); - - cursor = idx.forwardCursor( 3L ); - cursor.afterLast(); - - assertTrue( cursor.previous() ); - assertEquals( 14, ( long ) cursor.get().getId() ); - - assertTrue( cursor.previous() ); - assertEquals( 13, ( long ) cursor.get().getId() ); - - assertTrue( cursor.previous() ); - assertEquals( 12, ( long ) cursor.get().getId() ); - - assertTrue( cursor.previous() ); - assertEquals( 10, ( long ) cursor.get().getId() ); - - assertTrue( cursor.previous() ); - assertEquals( 9, ( long ) cursor.get().getId() ); - - assertTrue( cursor.previous() ); - assertEquals( 7, ( long ) cursor.get().getId() ); - - assertTrue( cursor.previous() ); - assertEquals( 3, ( long ) cursor.get().getId() ); - - assertFalse( cursor.previous() ); - } - - - @Test public void testConvertIndex() throws Exception { // just create the new directory under working directory Modified: directory/apacheds/branches/one-sub-level-index-removal/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/LdifPartition.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/one-sub-level-index-removal/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/LdifPartition.java?rev=1158430&r1=1158429&r2=1158430&view=diff ============================================================================== --- directory/apacheds/branches/one-sub-level-index-removal/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/LdifPartition.java (original) +++ directory/apacheds/branches/one-sub-level-index-removal/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/LdifPartition.java Tue Aug 16 19:56:04 2011 @@ -359,7 +359,7 @@ public class LdifPartition extends Abstr // Then, if there are some children, move then to the new place try { - IndexCursor cursor = getSubLevelIndex().forwardCursor( entryIdOld ); + IndexCursor cursor = getRdnIndexHelper().getSubLevelScopeCursor( entryIdOld ); while ( cursor.next() ) { Modified: directory/apacheds/branches/one-sub-level-index-removal/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/SingleFileLdifPartition.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/one-sub-level-index-removal/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/SingleFileLdifPartition.java?rev=1158430&r1=1158429&r2=1158430&view=diff ============================================================================== --- directory/apacheds/branches/one-sub-level-index-removal/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/SingleFileLdifPartition.java (original) +++ directory/apacheds/branches/one-sub-level-index-removal/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/SingleFileLdifPartition.java Tue Aug 16 19:56:04 2011 @@ -24,9 +24,7 @@ package org.apache.directory.server.core import java.io.File; import java.io.IOException; import java.io.RandomAccessFile; -import java.util.HashMap; import java.util.Iterator; -import java.util.Map; import java.util.UUID; import javax.naming.InvalidNameException; @@ -38,7 +36,6 @@ import org.apache.directory.server.core. import org.apache.directory.server.core.interceptor.context.RenameOperationContext; import org.apache.directory.server.i18n.I18n; import org.apache.directory.server.xdbm.IndexCursor; -import org.apache.directory.server.xdbm.IndexEntry; import org.apache.directory.shared.ldap.model.constants.SchemaConstants; import org.apache.directory.shared.ldap.model.entry.DefaultEntry; import org.apache.directory.shared.ldap.model.entry.Entry; @@ -295,11 +292,8 @@ public class SingleFileLdifPartition ext { return; } - - IndexCursor cursor = getOneLevelIndex().forwardCursor( suffixId ); - - appendLdif( lookup( suffixId ) ); + IndexCursor cursor = getRdnIndexHelper().getSubLevelScopeCursor( suffixId ); while ( cursor.next() ) { @@ -308,8 +302,6 @@ public class SingleFileLdifPartition ext Entry entry = lookup( childId ); appendLdif( entry ); - - appendRecursive( childId, null ); } cursor.close(); @@ -328,59 +320,6 @@ public class SingleFileLdifPartition ext /** - * appends all the entries present under a given entry, recursively - * - * @param entryId the base entry's id - * @param cursorMap the open cursor map - * @throws Exception - */ - private void appendRecursive( Long entryId, Map> cursorMap ) throws Exception - { - synchronized ( lock ) - { - - IndexCursor cursor = null; - if ( cursorMap == null ) - { - cursorMap = new HashMap>(); - } - - cursor = cursorMap.get( entryId ); - - if ( cursor == null ) - { - cursor = getOneLevelIndex().forwardCursor( entryId ); - cursor.beforeFirst(); - cursorMap.put( entryId, cursor ); - } - - if ( !cursor.next() ) // if this is a leaf entry's Dn - { - cursorMap.remove( entryId ); - cursor.close(); - } - else - { - do - { - IndexEntry idxEntry = cursor.get(); - Entry entry = lookup( idxEntry.getId() ); - - Long childId = getEntryId( entry.getDn() ); - - appendLdif( entry ); - - appendRecursive( childId, cursorMap ); - } - while ( cursor.next() ); - cursorMap.remove( entryId ); - cursor.close(); - } - } - } - - - /** * append data to the LDIF file * * @param entry the entry to be written Modified: directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java?rev=1158430&r1=1158429&r2=1158430&view=diff ============================================================================== --- directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java (original) +++ directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java Tue Aug 16 19:56:04 2011 @@ -23,11 +23,9 @@ package org.apache.directory.server.core import java.io.IOException; import java.io.OutputStream; import java.net.URI; -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 java.util.concurrent.atomic.AtomicBoolean; @@ -63,8 +61,8 @@ import org.apache.directory.server.xdbm. import org.apache.directory.server.xdbm.Store; import org.apache.directory.server.xdbm.search.Optimizer; import org.apache.directory.server.xdbm.search.SearchEngine; +import org.apache.directory.server.xdbm.search.impl.RdnIndexHelper; import org.apache.directory.shared.ldap.model.constants.SchemaConstants; -import org.apache.directory.shared.ldap.model.cursor.Cursor; import org.apache.directory.shared.ldap.model.entry.Attribute; import org.apache.directory.shared.ldap.model.entry.Entry; import org.apache.directory.shared.ldap.model.entry.Modification; @@ -143,16 +141,13 @@ public abstract class AbstractBTreeParti /** the relative distinguished name index */ protected Index, Entry, ID> rdnIdx; + + /** the relative distinguished name index helper */ + protected RdnIndexHelper rdnIndexHelper; /** a system index on objectClass attribute*/ protected Index objectClassIdx; - /** the parent child relationship index */ - protected Index oneLevelIdx; - - /** a system index on the entries of descendants of root Dn */ - protected Index subLevelIdx; - /** the attribute presence index */ protected Index presenceIdx; @@ -290,20 +285,6 @@ public abstract class AbstractBTreeParti addIndex( index ); } - if ( getOneLevelIndex() == null ) - { - Index index = new GenericIndex( ApacheSchemaConstants.APACHE_ONE_LEVEL_AT_OID ); - index.setWkDirPath( partitionPath ); - addIndex( index ); - } - - if ( getSubLevelIndex() == null ) - { - Index index = new GenericIndex( ApacheSchemaConstants.APACHE_SUB_LEVEL_AT_OID ); - index.setWkDirPath( partitionPath ); - addIndex( index ); - } - if ( getRdnIndex() == null ) { Index, Entry, ID> index = new GenericIndex, Entry, ID>( ApacheSchemaConstants.APACHE_RDN_AT_OID ); @@ -363,9 +344,8 @@ public abstract class AbstractBTreeParti // set index shortcuts rdnIdx = ( Index, Entry, ID> ) systemIndices.get( ApacheSchemaConstants.APACHE_RDN_AT_OID ); + rdnIndexHelper = new RdnIndexHelper( rdnIdx, getRootId() ); presenceIdx = ( Index ) systemIndices.get( ApacheSchemaConstants.APACHE_PRESENCE_AT_OID ); - oneLevelIdx = ( Index ) systemIndices.get( ApacheSchemaConstants.APACHE_ONE_LEVEL_AT_OID ); - subLevelIdx = ( Index ) systemIndices.get( ApacheSchemaConstants.APACHE_SUB_LEVEL_AT_OID ); aliasIdx = ( Index ) systemIndices.get( ApacheSchemaConstants.APACHE_ALIAS_AT_OID ); oneAliasIdx = ( Index ) systemIndices.get( ApacheSchemaConstants.APACHE_ONE_ALIAS_AT_OID ); subAliasIdx = ( Index ) systemIndices.get( ApacheSchemaConstants.APACHE_SUB_ALIAS_AT_OID ); @@ -581,8 +561,10 @@ public abstract class AbstractBTreeParti // Get a new ID for the added entry ID id = master.getNextId( entry ); - // Update the RDN index + // Update the RDN index including one-level and sub-level counter + // TODO: move logic to RdnIndexHelper rdnIdx.add( key, id ); + updateOneAndSubLevelCounters(parentId, true); // Update the ObjectClass index Attribute objectClass = entry.get( OBJECT_CLASS_AT ); @@ -606,22 +588,7 @@ public abstract class AbstractBTreeParti Attribute aliasAttr = entry.get( ALIASED_OBJECT_NAME_AT ); addAliasIndices( id, entryDn, aliasAttr.getString() ); } - - // Update the OneLevel index - oneLevelIdx.add( parentId, id ); - - // Update the SubLevel index - ID tempId = parentId; - - while ( ( tempId != null ) && ( !tempId.equals( getRootId() ) ) && ( !tempId.equals( getSuffixId() ) ) ) - { - subLevelIdx.add( tempId, id ); - tempId = getParentId( tempId ); - } - - // making entry an ancestor/descendent of itself in sublevel index - subLevelIdx.add( id, id ); - + // Update the EntryCsn index Attribute entryCsn = entry.get( ENTRY_CSN_AT ); @@ -764,10 +731,10 @@ public abstract class AbstractBTreeParti objectClassIdx.drop( value.getString(), id ); } - // Update the rdn, oneLevel, subLevel, entryCsn and entryUuid indexes + // Update the rdn, entryCsn and entryUuid indexes + // TODO: move logic to RdnIndexHelper + updateOneAndSubLevelCounters(getParentId( id ), false); rdnIdx.drop( id ); - oneLevelIdx.drop( id ); - subLevelIdx.drop( id ); entryCsnIdx.drop( id ); entryUuidIdx.drop( id ); @@ -833,10 +800,9 @@ public abstract class AbstractBTreeParti { try { - // We use the OneLevel index to get all the entries from a starting point + // We use the RDN index to get all the entries from a starting point // and below - IndexCursor cursor = oneLevelIdx.forwardCursor( id ); - cursor.beforeValue( id, null ); + IndexCursor cursor = rdnIndexHelper.getOneLevelScopeCursor( id ); return cursor; } @@ -1402,10 +1368,8 @@ public abstract class AbstractBTreeParti * 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, entryId ); - oneLevelIdx.add( newParentId, entryId ); - - updateSubLevelIndex( entryId, oldParentId, newParentId ); + updateOneAndSubLevelCounters( oldParentId, false ); + updateOneAndSubLevelCounters( newParentId, true ); // Update the Rdn index rdnIdx.drop( entryId ); @@ -1572,10 +1536,8 @@ public abstract class AbstractBTreeParti * 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 ); + updateOneAndSubLevelCounters( oldParentId, false ); + updateOneAndSubLevelCounters( newParentId, true ); /* * Update the Rdn index @@ -1827,67 +1789,6 @@ public abstract class AbstractBTreeParti } - /** - * Updates the SubLevel Index as part of a move operation. - * - * @param entryId child id to be moved - * @param oldParentId old parent's id - * @param newParentId new parent's id - * @throws Exception - */ - private void updateSubLevelIndex( ID entryId, ID oldParentId, ID newParentId ) throws Exception - { - ID tempId = oldParentId; - List parentIds = new ArrayList(); - - // find all the parents of the oldParentId - while ( ( tempId != null ) && !tempId.equals( getRootId() ) && !tempId.equals( getSuffixId() ) ) - { - parentIds.add( tempId ); - tempId = getParentId( tempId ); - } - - // find all the children of the childId - Cursor> cursor = subLevelIdx.forwardCursor( entryId ); - - List childIds = new ArrayList(); - childIds.add( entryId ); - - 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 ( ID pid : parentIds ) - { - for ( ID cid : childIds ) - { - subLevelIdx.drop( pid, cid ); - } - } - - parentIds.clear(); - tempId = newParentId; - - // find all the parents of the newParentId - while ( ( tempId != null) && !tempId.equals( getRootId() ) && !tempId.equals( getSuffixId() ) ) - { - parentIds.add( tempId ); - tempId = getParentId( tempId ); - } - - // attach the childId and all its children to newParentId and all it parents excluding the root - for ( ID id : parentIds ) - { - for ( ID cid : childIds ) - { - subLevelIdx.add( id, cid ); - } - } - } - - // ------------------------------------------------------------------------ // Index and master table Operations // ------------------------------------------------------------------------ @@ -1951,7 +1852,9 @@ public abstract class AbstractBTreeParti { try { - return oneLevelIdx.count( id ); + long count = rdnIdx.reverseLookup( id ).getOneLevelCount(); + // TODO: avoid cast + return (int)count; } catch ( Exception e ) { @@ -2192,26 +2095,6 @@ public abstract class AbstractBTreeParti * {@inheritDoc} */ @SuppressWarnings("unchecked") - public Index getOneLevelIndex() - { - return ( Index ) systemIndices.get( ApacheSchemaConstants.APACHE_ONE_LEVEL_AT_OID ); - } - - - /** - * {@inheritDoc} - */ - @SuppressWarnings("unchecked") - public Index getSubLevelIndex() - { - return ( Index ) systemIndices.get( ApacheSchemaConstants.APACHE_SUB_LEVEL_AT_OID ); - } - - - /** - * {@inheritDoc} - */ - @SuppressWarnings("unchecked") public Index getAliasIndex() { return ( Index ) systemIndices.get( ApacheSchemaConstants.APACHE_ALIAS_AT_OID ); @@ -2291,6 +2174,16 @@ public abstract class AbstractBTreeParti /** * {@inheritDoc} */ + @Override + public RdnIndexHelper getRdnIndexHelper() + { + return rdnIndexHelper; + } + + + /** + * {@inheritDoc} + */ public boolean hasUserIndexOn( AttributeType attributeType ) throws LdapException { return userIndices.containsKey( attributeType.getOid() ); @@ -2556,7 +2449,50 @@ public abstract class AbstractBTreeParti } } - + + private void updateOneAndSubLevelCounters( ID parentId, boolean increment ) throws Exception + { + if ( parentId == null ) + { + return; + } + + ID rootId = getRootId(); + + // update parent one-level count + if ( !parentId.equals( rootId ) ) + { + ParentIdAndRdn piar = rdnIdx.reverseLookup( parentId ); + if ( increment ) + { + piar.incrementOneLevelCount(); + } + else + { + piar.decrementOneLevelCount(); + } + rdnIdx.add( piar, parentId ); + } + + // update sub-level count of all parents + while ( !parentId.equals( rootId ) ) + { + ParentIdAndRdn piar = rdnIdx.reverseLookup( parentId ); + if ( increment ) + { + piar.incrementSubLevelCount(); + } + else + { + piar.decrementSubLevelCount(); + } + rdnIdx.add( piar, parentId ); + + parentId = piar.getParentId(); + } + } + + //--------------------------------------------------------------------------------------------- // Debug methods //--------------------------------------------------------------------------------------------- Modified: directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ParentIdAndRdn.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ParentIdAndRdn.java?rev=1158430&r1=1158429&r2=1158430&view=diff ============================================================================== --- directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ParentIdAndRdn.java (original) +++ directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ParentIdAndRdn.java Tue Aug 16 19:56:04 2011 @@ -26,6 +26,7 @@ import java.io.ObjectInput; import java.io.ObjectOutput; import java.util.Arrays; import java.util.List; +import java.util.concurrent.atomic.AtomicLong; import org.apache.directory.shared.ldap.model.name.Rdn; @@ -45,12 +46,16 @@ public class ParentIdAndRdn rdns ) { + this(); this.parentId = parentId; this.rdns = rdns.toArray( new Rdn[rdns.size()] ); } @@ -124,6 +131,54 @@ public class ParentIdAndRdn that = (ParentIdAndRdn) obj; - + + if ( !parentId.equals( that.parentId ) ) + { + return false; + } + if ( rdns == null ) { return that.rdns == null; @@ -183,7 +243,18 @@ public class ParentIdAndRdn that ) { - int val = this.rdns.length - that.rdns.length; + // Compare the parent id first so that all entries with the same parent + // are grouped together in the index. Required for proper function of + // RdnIndexTreeCursor. + int val = this.getParentId().compareTo( that.getParentId() ); + + if ( val != 0 ) + { + return val; + } + + // Now compare the RDNs + val = this.rdns.length - that.rdns.length; if ( val != 0 ) { @@ -199,10 +270,8 @@ public class ParentIdAndRdn getOneLevelIndex(); - - - /** - * @return The SubLevel system index - */ - Index getSubLevelIndex(); - - - /** * @return The Alias system index */ Index getAliasIndex(); @@ -213,6 +200,12 @@ public interface Store, E, ID> getRdnIndex(); + + + /** + * @return The Rdn index helper + */ + RdnIndexHelper getRdnIndexHelper(); /** Modified: directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/DefaultOptimizer.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/DefaultOptimizer.java?rev=1158430&r1=1158429&r2=1158430&view=diff ============================================================================== --- directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/DefaultOptimizer.java (original) +++ directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/DefaultOptimizer.java Tue Aug 16 19:56:04 2011 @@ -388,7 +388,7 @@ public class DefaultOptimizer evaluator; /** A Cursor over the entries in the scope of the search base */ private final IndexCursor scopeCursor; @@ -74,7 +74,7 @@ public class OneLevelScopeCursor candidate ) throws Exception { - boolean isChild = db.getOneLevelIndex().forward( baseId, candidate.getId() ); + boolean isChild = db.getRdnIndexHelper().isDirectDescendantOf( baseId, candidate.getId() ); /* * The candidate id could be any entry in the db. If search Added: directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/RdnIndexHelper.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/RdnIndexHelper.java?rev=1158430&view=auto ============================================================================== --- directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/RdnIndexHelper.java (added) +++ directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/RdnIndexHelper.java Tue Aug 16 19:56:04 2011 @@ -0,0 +1,143 @@ +/* + * 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.server.xdbm.search.impl; + + +import org.apache.directory.server.xdbm.Index; +import org.apache.directory.server.xdbm.IndexCursor; +import org.apache.directory.server.xdbm.ParentIdAndRdn; + + +/** + * Wrapper around the RDN index with helper functions. + * + * @author Apache Directory Project + */ +public class RdnIndexHelper> +{ + private final Index, E, ID> rdnIndex; + private final ID rootId; + + + public RdnIndexHelper( Index, E, ID> rdnIndex, ID rootId ) + { + this.rdnIndex = rdnIndex; + this.rootId = rootId; + } + + + /** + * Checks if the descendantId is a direct descendant + * of the ancestorId. + * + * @param ancestorId the ancestor + * @param descendantId the descendant + * @return true if descendantId is a direct descendant + * of ancestorId + * @throws Exception + */ + public boolean isDirectDescendantOf( ID ancestorId, ID descendantId ) throws Exception + { + if ( descendantId.equals( rootId ) ) + { + return false; + } + + ParentIdAndRdn parentIdAndRdn = rdnIndex.reverseLookup( descendantId ); + + if ( parentIdAndRdn == null ) + { + throw new IllegalArgumentException( "ID " + descendantId + " not found in RDN index." ); + } + + boolean isParent = ancestorId.equals( parentIdAndRdn.getParentId() ); + return isParent; + } + + + /** + * Checks if the descendantId is a descendant of the ancestorId. + * + * @param ancestorId the ancestor + * @param descendantId the descendant + * @return true if descendantId is a descendant + * of ancestorId + * @throws Exception + */ + public boolean isDescendantOf( ID ancestorId, ID descendantId ) throws Exception + { + if ( descendantId.equals( rootId ) ) + { + return false; + } + + ID id = descendantId; + + while ( !id.equals( rootId ) ) + { + ParentIdAndRdn parentIdAndRdn = rdnIndex.reverseLookup( id ); + + if ( parentIdAndRdn == null ) + { + throw new IllegalArgumentException( "ID " + descendantId + " not found in RDN index." ); + } + + boolean isParent = ancestorId.equals( parentIdAndRdn.getParentId() ); + + if ( isParent ) + { + return true; + } + + id = parentIdAndRdn.getParentId(); + } + + return false; + } + + + public long getOneLevelCount( ID id ) throws Exception + { + long count = rdnIndex.reverseLookup( id ).getOneLevelCount(); + return count; + } + + + public long getSubLevelCount( ID id ) throws Exception + { + long count = rdnIndex.reverseLookup( id ).getSubLevelCount(); + return count; + } + + + public IndexCursor getOneLevelScopeCursor( ID id ) throws Exception + { + RdnIndexTreeCursor cursor = new RdnIndexTreeCursor( rdnIndex, id, true ); + return cursor; + } + + + public IndexCursor getSubLevelScopeCursor( ID id ) throws Exception + { + RdnIndexTreeCursor cursor = new RdnIndexTreeCursor( rdnIndex, id, false ); + return cursor; + } + +} Added: directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/RdnIndexTreeCursor.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/RdnIndexTreeCursor.java?rev=1158430&view=auto ============================================================================== --- directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/RdnIndexTreeCursor.java (added) +++ directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/RdnIndexTreeCursor.java Tue Aug 16 19:56:04 2011 @@ -0,0 +1,463 @@ +/* + * 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.server.xdbm.search.impl; + + +import java.util.Deque; +import java.util.LinkedList; + +import org.apache.directory.server.xdbm.AbstractIndexCursor; +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.ParentIdAndRdn; +import org.apache.directory.shared.ldap.model.exception.LdapInvalidDnException; +import org.apache.directory.shared.ldap.model.name.Rdn; + + +/** + * A Cursor that traverses the RDN index as a tree. + * + * @author Apache Directory Project + */ +public class RdnIndexTreeCursor> extends AbstractIndexCursor +{ + + /** Special RDN used as end marker of a tree level. Also used as marker afterLast()/last() operations */ + private static final Rdn STOP_ELEMENT; + static + { + try + { + STOP_ELEMENT = new Rdn( "zzz=zzz" ); + } + catch ( LdapInvalidDnException e ) + { + throw new RuntimeException( "Error initializing stop element", e ); + } + } + + private final Index, E, ID> rdnIndex; + private final ID startId; + private final boolean oneLevel; + + /** + * A stack containing all cursors. On construction the root cursor is added. + * While the tree is traversed in depth-first order more cursors are added and removed. + * The root cursor is never removed. + */ + private final CursorStack cursors; + + /** Whether or not this Cursor is positioned so an entry is available */ + private boolean available; + + + public RdnIndexTreeCursor( Index, E, ID> rdnIndex, ID startId, boolean oneLevel ) + throws Exception + { + this.rdnIndex = rdnIndex; + this.startId = startId; + this.oneLevel = oneLevel; + + this.cursors = new CursorStack(); + + if ( oneLevel ) + { + this.cursors.createChildCursor( startId ); + } + else + { + this.cursors.createChildCursor( rdnIndex.reverseLookup( startId ) ); + } + + beforeFirst(); + } + + + public boolean available() + { + return available; + } + + + public void before( IndexEntry element ) throws Exception + { + throw new UnsupportedOperationException(); + } + + + public void beforeValue( ID id, ID value ) throws Exception + { + throw new UnsupportedOperationException(); + } + + + public void afterValue( ID id, ID value ) throws Exception + { + throw new UnsupportedOperationException(); + } + + + public void after( IndexEntry element ) throws Exception + { + throw new UnsupportedOperationException(); + } + + + public void beforeFirst() throws Exception + { + checkNotClosed( "beforeFirst()" ); + + // remove and close all but the root cursors in the stack + while ( cursors.size() > 1 ) + { + cursors.closeCurrentCursor(); + } + + // position the root cursor + cursors.getCurrentCursor().before( cursors.getCurrentCursorStartElement() ); + available = false; + } + + + public void afterLast() throws Exception + { + checkNotClosed( "afterLast()" ); + + // remove and close all but the root cursors in the stack + while ( cursors.size() > 1 ) + { + cursors.closeCurrentCursor(); + } + + // position the root cursor + cursors.getCurrentCursor().after( cursors.getCurrentCursorStopElement() ); + available = false; + } + + + public boolean first() throws Exception + { + checkNotClosed( "first()" ); + beforeFirst(); + return next(); + } + + + public boolean last() throws Exception + { + checkNotClosed( "last()" ); + afterLast(); + return previous(); + } + + + public boolean previous() throws Exception + { + checkNotClosed( "previous()" ); + if ( oneLevel ) + { + return previousOneLevel(); + } + else + { + return previousSubLevel(); + } + } + + + private boolean previousOneLevel() throws Exception + { + return previousCurrentLevel(); + } + + + private boolean previousSubLevel() throws Exception + { + if ( previousCurrentLevel() ) + { + // depth first traversal: check if previous index entry has children + do + { + ID id = cursors.getCurrentCursor().get().getId(); + cursors.createChildCursor( id ); + cursors.getCurrentCursor().after( cursors.getCurrentCursorStopElement() ); + } + while ( previousCurrentLevel() ); + + cursors.closeCurrentCursor(); + + available = true; + return true; + } + + // back one level + if ( cursors.size() > 1 ) + { + cursors.closeCurrentCursor(); + available = true; + return true; + } + + return false; + } + + + private boolean previousCurrentLevel() throws Exception + { + if ( cursors.getCurrentCursor().previous() ) + { + // Compare the previous index entry's parent with the start element + IndexEntry, E, ID> indexEntry = cursors.getCurrentCursor().get(); + ParentIdAndRdn currentParentIdAndRdn = indexEntry.getValue(); + ParentIdAndRdn startParentIdAndRdn = cursors.getCurrentCursorStartElement().getValue(); + if ( currentParentIdAndRdn.getParentId().equals( startParentIdAndRdn.getParentId() ) + && currentParentIdAndRdn.compareTo( startParentIdAndRdn ) >= 0 ) + { + available = true; + return true; + } + else + { + cursors.getCurrentCursor().next(); + available = false; + return false; + } + } + else + { + available = false; + return false; + } + } + + + public boolean next() throws Exception + { + checkNotClosed( "next()" ); + if ( oneLevel ) + { + return nextOneLevel(); + } + else + { + return nextSubLevel(); + } + } + + + private boolean nextOneLevel() throws Exception + { + return nextCurrentLevel(); + } + + + private boolean nextSubLevel() throws Exception + { + // depth first traversal: check if current index entry has children + // TODO: use one-level count for optimization + if ( available ) + { + ID id = cursors.getCurrentCursor().get().getId(); + cursors.createChildCursor( id ); + cursors.getCurrentCursor().before( cursors.getCurrentCursorStartElement() ); + if ( nextCurrentLevel() ) + { + return true; + } + else + { + cursors.closeCurrentCursor(); + } + } + + // next element at current level + if ( nextCurrentLevel() ) + { + return true; + } + + // back one level + while ( cursors.size() > 1 ) + { + cursors.closeCurrentCursor(); + if ( nextCurrentLevel() ) + { + return true; + } + } + + return false; + } + + + private boolean nextCurrentLevel() throws Exception + { + if ( cursors.getCurrentCursor().next() ) + { + // Compare the next index entry's parent with the stop element + IndexEntry, E, ID> indexEntry = cursors.getCurrentCursor().get(); + ParentIdAndRdn currentParentIdAndRdn = indexEntry.getValue(); + ParentIdAndRdn stopParentIdAndRdn = cursors.getCurrentCursorStopElement().getValue(); + if ( currentParentIdAndRdn.getParentId().equals( stopParentIdAndRdn.getParentId() ) + && currentParentIdAndRdn.compareTo( stopParentIdAndRdn ) <= 0 ) + { + available = true; + return true; + } + else + { + cursors.getCurrentCursor().previous(); + available = false; + return false; + } + } + else + { + available = false; + return false; + } + } + + + @Override + public IndexEntry get() throws Exception + { + IndexEntry, E, ID> wrappedEntry = cursors.getCurrentCursor().get(); + IndexEntry entry = new ForwardIndexEntry(); + entry.setValue( startId ); + //entry.setValue( wrappedEntry.getValue().getParentId() ); + entry.setId( wrappedEntry.getId() ); + return entry; + } + + private class CursorStack + { + private final Deque cursorStack; + + + public CursorStack() + { + this.cursorStack = new LinkedList(); + } + + + public void createChildCursor( ID startId ) throws Exception + { + CursorStackEntry entry = new CursorStackEntry( startId ); + cursorStack.addFirst( entry ); + } + + + public void createChildCursor( ParentIdAndRdn parentIdAndRdn ) throws Exception + { + CursorStackEntry entry = new CursorStackEntry( parentIdAndRdn ); + cursorStack.addFirst( entry ); + } + + + /** + * @return the current cursor from the cursor stack + */ + public IndexCursor, E, ID> getCurrentCursor() + { + IndexCursor, E, ID> cursor = cursorStack.getFirst().cursor; + return cursor; + } + + + /** + * @return the current cursor's start element from the cursor stack + */ + public IndexEntry, E, ID> getCurrentCursorStartElement() + { + IndexEntry, E, ID> startElement = cursorStack.getFirst().startElement; + return startElement; + } + + + /** + * @return the current cursor's stop element from the cursor stack + */ + public IndexEntry, E, ID> getCurrentCursorStopElement() + { + IndexEntry, E, ID> startElement = cursorStack.getFirst().stopElement; + return startElement; + } + + + public void closeCurrentCursor() throws Exception + { + cursorStack.removeFirst().cursor.close(); + } + + + public int size() + { + return cursorStack.size(); + } + + + @Override + public String toString() + { + return "CursorStack [cursorStack=" + cursorStack + "]"; + } + + private class CursorStackEntry + { + private final IndexCursor, E, ID> cursor; + private final IndexEntry, E, ID> startElement; + private final IndexEntry, E, ID> stopElement; + + + public CursorStackEntry( ID startId ) throws Exception + { + this.cursor = rdnIndex.forwardCursor(); + this.startElement = createElement( new ParentIdAndRdn( startId ) ); + this.stopElement = createElement( new ParentIdAndRdn( startId, STOP_ELEMENT ) ); + } + + + public CursorStackEntry( ParentIdAndRdn parentIdAndRdn ) throws Exception + { + this.cursor = rdnIndex.forwardCursor(); + this.startElement = createElement( parentIdAndRdn ); + this.stopElement = createElement( parentIdAndRdn ); + } + + + private IndexEntry, E, ID> createElement( ParentIdAndRdn parentIdAndRdn ) + { + IndexEntry, E, ID> startElement = new ForwardIndexEntry, E, ID>(); + startElement.setValue( parentIdAndRdn ); + return startElement; + } + + + @Override + public String toString() + { + //return "CSE:" + startElement.getValue().getParentId(); + return "CSE:" + startElement; + } + } + } +} Modified: directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/SubtreeScopeCursor.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/SubtreeScopeCursor.java?rev=1158430&r1=1158429&r2=1158430&view=diff ============================================================================== --- directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/SubtreeScopeCursor.java (original) +++ directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/SubtreeScopeCursor.java Tue Aug 16 19:56:04 2011 @@ -80,7 +80,7 @@ public class SubtreeScopeCursor( ApacheSchemaConstants.APACHE_PRESENCE_AT_OID ) ); assertNotNull( avlPartition.getPresenceIndex() ); - assertNull( avlPartition.getOneLevelIndex() ); - avlPartition.addIndex( new AvlIndex( ApacheSchemaConstants.APACHE_ONE_LEVEL_AT_OID ) ); - assertNotNull( avlPartition.getOneLevelIndex() ); - - assertNull( avlPartition.getSubLevelIndex() ); - avlPartition.addIndex( new AvlIndex( ApacheSchemaConstants.APACHE_SUB_LEVEL_AT_OID ) ); - assertNotNull( avlPartition.getSubLevelIndex() ); - assertNull( avlPartition.getId() ); avlPartition.setId( "foo" ); assertEquals( "foo", avlPartition.getId() ); @@ -249,28 +239,6 @@ public class AvlPartitionTest { } - assertNotNull( partition.getOneLevelIndex() ); - - try - { - partition.addIndex( new AvlIndex( ApacheSchemaConstants.APACHE_ONE_LEVEL_AT_OID ) ); - //fail(); - } - catch ( IllegalStateException e ) - { - } - - assertNotNull( partition.getSubLevelIndex() ); - - try - { - partition.addIndex( new AvlIndex( ApacheSchemaConstants.APACHE_SUB_LEVEL_AT_OID ) ); - //fail(); - } - catch ( IllegalStateException e ) - { - } - assertNotNull( partition.getId() ); try @@ -320,7 +288,7 @@ public class AvlPartitionTest Iterator systemIndices = partition.getSystemIndices(); - for ( int i = 0; i < 10; i++ ) + for ( int i = 0; i < 8; i++ ) { assertTrue( systemIndices.hasNext() ); assertNotNull( systemIndices.next() ); @@ -421,8 +389,12 @@ public class AvlPartitionTest assertNotNull( cursor ); cursor.beforeFirst(); assertTrue( cursor.next() ); - assertEquals( 2L, ( long ) cursor.get().getId() ); + assertEquals( 3L, ( long ) cursor.get().getId() ); + assertTrue( cursor.next() ); + assertEquals( 4L, ( long ) cursor.get().getId() ); assertTrue( cursor.next() ); + assertEquals( 2L, ( long ) cursor.get().getId() ); + assertFalse( cursor.next() ); assertEquals( 3, partition.getChildCount( 1L ) ); partition.delete( 2L ); @@ -448,119 +420,6 @@ public class AvlPartitionTest @Test - public void testSubLevelIndex() throws Exception - { - Index idx = partition.getSubLevelIndex(); - - assertEquals( 19, idx.count() ); - - Cursor> cursor = idx.forwardCursor( 2L ); - - assertTrue( cursor.next() ); - assertEquals( 2, ( long ) cursor.get().getId() ); - - assertTrue( cursor.next() ); - assertEquals( 5, ( long ) cursor.get().getId() ); - - assertTrue( cursor.next() ); - assertEquals( 6, ( long ) cursor.get().getId() ); - - assertFalse( cursor.next() ); - - idx.drop( 5L ); - - cursor = idx.forwardCursor( 2L ); - - assertTrue( cursor.next() ); - assertEquals( 2, ( long ) cursor.get().getId() ); - - assertTrue( cursor.next() ); - assertEquals( 6, ( long ) cursor.get().getId() ); - - assertFalse( cursor.next() ); - - // dn id 12 - Dn martinDn = new Dn( schemaManager, "cn=Marting King,ou=Sales,o=Good Times Co." ); - DefaultEntry entry = new DefaultEntry( schemaManager, martinDn ); - entry.add( "objectClass", "top", "person", "organizationalPerson" ); - entry.add( "ou", "Sales" ); - entry.add( "cn", "Martin King" ); - entry.add( "entryCSN", new CsnFactory( 1 ).newInstance().toString() ); - entry.add( "entryUUID", UUID.randomUUID().toString() ); - - AddOperationContext addContext = new AddOperationContext( null, entry ); - partition.add( addContext ); - - cursor = idx.forwardCursor( 2L ); - cursor.afterLast(); - assertTrue( cursor.previous() ); - assertEquals( 12, ( long ) cursor.get().getId() ); - - Dn newParentDn = new Dn( schemaManager, "ou=Board of Directors,o=Good Times Co." ); - - Dn newDn = newParentDn.add( martinDn.getRdn() ); - partition.move( martinDn, newParentDn, newDn, new ClonedServerEntry( entry ) ); - - cursor = idx.forwardCursor( 3L ); - cursor.afterLast(); - assertTrue( cursor.previous() ); - assertEquals( 12, ( long ) cursor.get().getId() ); - - // dn id 13 - Dn marketingDn = new Dn( schemaManager, "ou=Marketing,ou=Sales,o=Good Times Co." ); - entry = new DefaultEntry( schemaManager, marketingDn ); - entry.add( "objectClass", "top", "organizationalUnit" ); - entry.add( "ou", "Marketing" ); - entry.add( "entryCSN", new CsnFactory( 1 ).newInstance().toString() ); - entry.add( "entryUUID", UUID.randomUUID().toString() ); - - addContext = new AddOperationContext( null, entry ); - partition.add( addContext ); - - // dn id 14 - Dn jimmyDn = new Dn( schemaManager, "cn=Jimmy Wales,ou=Marketing, ou=Sales,o=Good Times Co." ); - entry = new DefaultEntry( schemaManager, jimmyDn ); - entry.add( "objectClass", "top", "person", "organizationalPerson" ); - entry.add( "ou", "Marketing" ); - entry.add( "cn", "Jimmy Wales" ); - entry.add( "entryCSN", new CsnFactory( 1 ).newInstance().toString() ); - entry.add( "entryUUID", UUID.randomUUID().toString() ); - - addContext = new AddOperationContext( null, entry ); - partition.add( addContext ); - - newDn = newParentDn.add( marketingDn.getRdn() ); - partition.move( marketingDn, newParentDn, newDn, new ClonedServerEntry( entry ) ); - - cursor = idx.forwardCursor( 3L ); - cursor.afterLast(); - - assertTrue( cursor.previous() ); - assertEquals( 14, ( long ) cursor.get().getId() ); - - assertTrue( cursor.previous() ); - assertEquals( 13, ( long ) cursor.get().getId() ); - - assertTrue( cursor.previous() ); - assertEquals( 12, ( long ) cursor.get().getId() ); - - assertTrue( cursor.previous() ); - assertEquals( 10, ( long ) cursor.get().getId() ); - - assertTrue( cursor.previous() ); - assertEquals( 9, ( long ) cursor.get().getId() ); - - assertTrue( cursor.previous() ); - assertEquals( 7, ( long ) cursor.get().getId() ); - - assertTrue( cursor.previous() ); - assertEquals( 3, ( long ) cursor.get().getId() ); - - assertFalse( cursor.previous() ); - } - - - @Test public void testConvertIndex() throws Exception { Index nonAvlIndex = new GenericIndex( "ou", 10, new File( "." ).toURI() ); Modified: directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/AndCursorTest.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/AndCursorTest.java?rev=1158430&r1=1158429&r2=1158430&view=diff ============================================================================== --- directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/AndCursorTest.java (original) +++ directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/AndCursorTest.java Tue Aug 16 19:56:04 2011 @@ -25,20 +25,12 @@ import static org.junit.Assert.assertFal import static org.junit.Assert.assertTrue; import static org.junit.Assert.fail; -import java.io.File; import java.util.ArrayList; import java.util.List; -import org.apache.commons.io.FileUtils; -import org.apache.directory.server.core.partition.Partition; -import org.apache.directory.server.core.partition.impl.avl.AvlPartition; import org.apache.directory.server.xdbm.ForwardIndexEntry; import org.apache.directory.server.xdbm.IndexCursor; -import org.apache.directory.server.xdbm.Store; -import org.apache.directory.server.xdbm.StoreUtils; -import org.apache.directory.server.xdbm.impl.avl.AvlIndex; import org.apache.directory.server.xdbm.search.Evaluator; -import org.apache.directory.shared.ldap.model.constants.SchemaConstants; import org.apache.directory.shared.ldap.model.cursor.InvalidCursorPositionException; import org.apache.directory.shared.ldap.model.entry.Entry; import org.apache.directory.shared.ldap.model.filter.AndNode; @@ -46,19 +38,8 @@ import org.apache.directory.shared.ldap. import org.apache.directory.shared.ldap.model.filter.FilterParser; import org.apache.directory.shared.ldap.model.filter.PresenceNode; import org.apache.directory.shared.ldap.model.filter.SubstringNode; -import org.apache.directory.shared.ldap.model.name.Dn; -import org.apache.directory.shared.ldap.model.schema.SchemaManager; -import org.apache.directory.shared.ldap.schemaextractor.SchemaLdifExtractor; -import org.apache.directory.shared.ldap.schemaextractor.impl.DefaultSchemaLdifExtractor; -import org.apache.directory.shared.ldap.schemaloader.LdifSchemaLoader; -import org.apache.directory.shared.ldap.schemamanager.impl.DefaultSchemaManager; -import org.apache.directory.shared.util.exception.Exceptions; -import org.junit.After; import org.junit.Before; -import org.junit.BeforeClass; import org.junit.Test; -import org.slf4j.Logger; -import org.slf4j.LoggerFactory; /** @@ -67,104 +48,17 @@ import org.slf4j.LoggerFactory; * * @author Apache Directory Project */ -public class AndCursorTest +public class AndCursorTest extends TestBase { - private static final Logger LOG = LoggerFactory.getLogger( AndCursorTest.class.getSimpleName() ); - - File wkdir; - Store store; - EvaluatorBuilder evaluatorBuilder; - CursorBuilder cursorBuilder; - private static SchemaManager schemaManager; - - - @BeforeClass - public static void setup() throws Exception - { - // setup the standard registries - String workingDirectory = System.getProperty( "workingDirectory" ); - - if ( workingDirectory == null ) - { - String path = AndCursorTest.class.getResource( "" ).getPath(); - int targetPos = path.indexOf( "target" ); - workingDirectory = path.substring( 0, targetPos + 6 ); - } - - File schemaRepository = new File( workingDirectory, "schema" ); - SchemaLdifExtractor extractor = new DefaultSchemaLdifExtractor( new File( workingDirectory ) ); - extractor.extractOrCopy( true ); - LdifSchemaLoader loader = new LdifSchemaLoader( schemaRepository ); - schemaManager = new DefaultSchemaManager( loader ); - - boolean loaded = schemaManager.loadAllEnabled(); - - if ( !loaded ) - { - fail( "Schema load failed : " + Exceptions.printErrors(schemaManager.getErrors()) ); - } - - loaded = schemaManager.loadWithDeps( "collective" ); - - if ( !loaded ) - { - fail( "Schema load failed : " + Exceptions.printErrors(schemaManager.getErrors()) ); - } - } - - - public AndCursorTest() throws Exception - { - } + EvaluatorBuilder evaluatorBuilder; + CursorBuilder cursorBuilder; @Before - public void createStore() throws Exception - { - // setup the working directory for the store - wkdir = File.createTempFile( getClass().getSimpleName(), "db" ); - wkdir.delete(); - wkdir = new File( wkdir.getParentFile(), getClass().getSimpleName() ); - wkdir.mkdirs(); - - // initialize the store - store = new AvlPartition( schemaManager ); - ((Partition)store).setId( "example" ); - store.setCacheSize( 10 ); - store.setPartitionPath( wkdir.toURI() ); - store.setSyncOnWrite( false ); - - store.addIndex( new AvlIndex( SchemaConstants.OU_AT_OID ) ); - store.addIndex( new AvlIndex( SchemaConstants.CN_AT_OID ) ); - ((Partition)store).setSuffixDn( new Dn( schemaManager, "o=Good Times Co." ) ); - ((Partition)store).initialize(); - - ((Partition)store).initialize(); - - StoreUtils.loadExampleData( store, schemaManager ); - - evaluatorBuilder = new EvaluatorBuilder( store, schemaManager ); - cursorBuilder = new CursorBuilder( store, evaluatorBuilder ); - - LOG.debug( "Created new store" ); - } - - - @After - public void destroyStore() throws Exception + public void createBuilder() throws Exception { - if ( store != null ) - { - ((Partition)store).destroy(); - } - - store = null; - if ( wkdir != null ) - { - FileUtils.deleteDirectory( wkdir ); - } - - wkdir = null; + evaluatorBuilder = new EvaluatorBuilder( store, schemaManager ); + cursorBuilder = new CursorBuilder( store, evaluatorBuilder ); } Modified: directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/GreaterEqTest.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/GreaterEqTest.java?rev=1158430&r1=1158429&r2=1158430&view=diff ============================================================================== --- directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/GreaterEqTest.java (original) +++ directory/apacheds/branches/one-sub-level-index-removal/xdbm-partition/src/test/java/org/apache/directory/server/xdbm/search/impl/GreaterEqTest.java Tue Aug 16 19:56:04 2011 @@ -26,21 +26,15 @@ import static org.junit.Assert.assertNot import static org.junit.Assert.assertTrue; import static org.junit.Assert.fail; -import java.io.File; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.UUID; -import org.apache.commons.io.FileUtils; import org.apache.directory.server.core.interceptor.context.AddOperationContext; import org.apache.directory.server.core.partition.Partition; -import org.apache.directory.server.core.partition.impl.avl.AvlPartition; import org.apache.directory.server.xdbm.ForwardIndexEntry; -import org.apache.directory.server.xdbm.Store; -import org.apache.directory.server.xdbm.StoreUtils; -import org.apache.directory.server.xdbm.impl.avl.AvlIndex; import org.apache.directory.shared.ldap.model.constants.SchemaConstants; import org.apache.directory.shared.ldap.model.csn.CsnFactory; import org.apache.directory.shared.ldap.model.cursor.InvalidCursorPositionException; @@ -53,20 +47,9 @@ import org.apache.directory.shared.ldap. import org.apache.directory.shared.ldap.model.schema.AttributeType; import org.apache.directory.shared.ldap.model.schema.LdapSyntax; import org.apache.directory.shared.ldap.model.schema.MatchingRule; -import org.apache.directory.shared.ldap.model.schema.SchemaManager; import org.apache.directory.shared.ldap.model.schema.comparators.StringComparator; import org.apache.directory.shared.ldap.model.schema.parsers.SyntaxCheckerDescription; -import org.apache.directory.shared.ldap.schemaextractor.SchemaLdifExtractor; -import org.apache.directory.shared.ldap.schemaextractor.impl.DefaultSchemaLdifExtractor; -import org.apache.directory.shared.ldap.schemaloader.LdifSchemaLoader; -import org.apache.directory.shared.ldap.schemamanager.impl.DefaultSchemaManager; -import org.apache.directory.shared.util.exception.Exceptions; -import org.junit.After; -import org.junit.Before; -import org.junit.BeforeClass; import org.junit.Test; -import org.slf4j.Logger; -import org.slf4j.LoggerFactory; /** @@ -74,94 +57,8 @@ import org.slf4j.LoggerFactory; * * @author Apache Directory Project */ -public class GreaterEqTest +public class GreaterEqTest extends TestBase { - public static final Logger LOG = LoggerFactory.getLogger( GreaterEqTest.class ); - - File wkdir; - Store store; - static SchemaManager schemaManager = null; - - - @BeforeClass - public static void setup() throws Exception - { - // setup the standard registries - String workingDirectory = System.getProperty( "workingDirectory" ); - - if ( workingDirectory == null ) - { - String path = GreaterEqTest.class.getResource( "" ).getPath(); - int targetPos = path.indexOf( "target" ); - workingDirectory = path.substring( 0, targetPos + 6 ); - } - - File schemaRepository = new File( workingDirectory, "schema" ); - SchemaLdifExtractor extractor = new DefaultSchemaLdifExtractor( new File( workingDirectory ) ); - extractor.extractOrCopy( true ); - LdifSchemaLoader loader = new LdifSchemaLoader( schemaRepository ); - schemaManager = new DefaultSchemaManager( loader ); - - boolean loaded = schemaManager.loadAllEnabled(); - - if ( !loaded ) - { - fail( "Schema load failed : " + Exceptions.printErrors(schemaManager.getErrors()) ); - } - - loaded = schemaManager.loadWithDeps( loader.getSchema( "collective" ) ); - - if ( !loaded ) - { - fail( "Schema load failed : " + Exceptions.printErrors(schemaManager.getErrors()) ); - } - } - - - @Before - public void createStore() throws Exception - { - // setup the working directory for the store - wkdir = File.createTempFile( getClass().getSimpleName(), "db" ); - wkdir.delete(); - wkdir = new File( wkdir.getParentFile(), getClass().getSimpleName() ); - wkdir.mkdirs(); - - // initialize the store - store = new AvlPartition( schemaManager ); - ((Partition)store).setId( "example" ); - store.setCacheSize( 10 ); - store.setPartitionPath( wkdir.toURI() ); - store.setSyncOnWrite( false ); - - store.addIndex( new AvlIndex( SchemaConstants.OU_AT_OID ) ); - store.addIndex( new AvlIndex( SchemaConstants.CN_AT_OID ) ); - store.addIndex( new AvlIndex( SchemaConstants.POSTALCODE_AT_OID ) ); - ((Partition)store).setSuffixDn( new Dn( schemaManager, "o=Good Times Co." ) ); - ((Partition)store).initialize(); - - StoreUtils.loadExampleData( store, schemaManager ); - LOG.debug( "Created new store" ); - } - - - @After - public void destroyStore() throws Exception - { - if ( store != null ) - { - ((Partition)store).destroy(); - } - - store = null; - if ( wkdir != null ) - { - FileUtils.deleteDirectory( wkdir ); - } - - wkdir = null; - } - @Test public void testCursorIndexed() throws Exception