View Javadoc

1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *  
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *  
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License. 
18   *  
19   */
20  package org.apache.directory.server.core.partition.impl.btree.jdbm;
21  
22  
23  import java.io.File;
24  import java.util.ArrayList;
25  import java.util.HashMap;
26  import java.util.HashSet;
27  import java.util.Iterator;
28  import java.util.List;
29  import java.util.Map;
30  import java.util.Set;
31  
32  import javax.naming.NamingException;
33  
34  import jdbm.RecordManager;
35  import jdbm.helper.MRU;
36  import jdbm.recman.BaseRecordManager;
37  import jdbm.recman.CacheRecordManager;
38  
39  import org.apache.directory.server.core.cursor.Cursor;
40  import org.apache.directory.server.core.entry.ClonedServerEntry;
41  import org.apache.directory.server.core.entry.ServerAttribute;
42  import org.apache.directory.server.core.entry.ServerBinaryValue;
43  import org.apache.directory.server.core.entry.ServerEntry;
44  import org.apache.directory.server.core.entry.ServerStringValue;
45  import org.apache.directory.server.schema.registries.AttributeTypeRegistry;
46  import org.apache.directory.server.schema.registries.OidRegistry;
47  import org.apache.directory.server.schema.registries.Registries;
48  import org.apache.directory.server.xdbm.Index;
49  import org.apache.directory.server.xdbm.IndexCursor;
50  import org.apache.directory.server.xdbm.IndexEntry;
51  import org.apache.directory.server.xdbm.IndexNotFoundException;
52  import org.apache.directory.server.xdbm.Store;
53  import org.apache.directory.shared.ldap.MultiException;
54  import org.apache.directory.shared.ldap.constants.SchemaConstants;
55  import org.apache.directory.shared.ldap.entry.EntryAttribute;
56  import org.apache.directory.shared.ldap.entry.Modification;
57  import org.apache.directory.shared.ldap.entry.ModificationOperation;
58  import org.apache.directory.shared.ldap.entry.Value;
59  import org.apache.directory.shared.ldap.exception.LdapNameNotFoundException;
60  import org.apache.directory.shared.ldap.exception.LdapSchemaViolationException;
61  import org.apache.directory.shared.ldap.message.ResultCodeEnum;
62  import org.apache.directory.shared.ldap.name.AttributeTypeAndValue;
63  import org.apache.directory.shared.ldap.name.LdapDN;
64  import org.apache.directory.shared.ldap.name.Rdn;
65  import org.apache.directory.shared.ldap.schema.AttributeType;
66  import org.apache.directory.shared.ldap.util.NamespaceTools;
67  import org.slf4j.Logger;
68  import org.slf4j.LoggerFactory;
69  
70  
71  public class JdbmStore<E> implements Store<E>
72  {
73      /** static logger */
74      private static final Logger LOG = LoggerFactory.getLogger( JdbmStore.class );
75      /** The default cache size is set to 10 000 objects */
76      static final int DEFAULT_CACHE_SIZE = 10000;
77  
78      /** the JDBM record manager used by this database */
79      private RecordManager recMan;
80      /** the normalized suffix DN of this backend database */
81      private LdapDN normSuffix;
82      /** the user provided suffix DN of this backend database */
83      private LdapDN upSuffix;
84      /** the working directory to use for files */
85      private File workingDirectory;
86      /** the master table storing entries by primary key */
87      private JdbmMasterTable<ServerEntry> master;
88      
89      /** a map of attributeType numeric ID to user userIndices */
90      private Map<String, Index<?,E>> userIndices = new HashMap<String, Index<?,E>>();
91      
92      /** a map of attributeType numeric ID to system userIndices */
93      private Map<String, Index<?,E>> systemIndices = new HashMap<String, Index<?,E>>();
94      
95      /** true if initialized */
96      private boolean initialized;
97      /** true if we sync disks on every write operation */
98      private boolean isSyncOnWrite = true;
99  
100     /** the normalized distinguished name index */
101     private JdbmIndex<String,E> ndnIdx;
102     /** the user provided distinguished name index */
103     private JdbmIndex<String,E> updnIdx;
104     /** the attribute existence index */
105     private JdbmIndex<String,E> existenceIdx;
106     /** a system index on aliasedObjectName attribute */
107     private JdbmIndex<String,E> aliasIdx;
108 
109     /** a system index on the entries of descendants of root DN*/
110     private JdbmIndex<Long,E> subLevelIdx;
111     /** the parent child relationship index */
112     private JdbmIndex<Long,E> oneLevelIdx;
113     /** the one level scope alias index */
114     private JdbmIndex<Long,E> oneAliasIdx;
115     /** the subtree scope alias index */
116     private JdbmIndex<Long,E> subAliasIdx;
117     
118     /** Two static declaration to avoid lookup all over the code */
119     private static AttributeType OBJECT_CLASS_AT;
120     private static AttributeType ALIASED_OBJECT_NAME_AT;
121 
122     /** A pointer on the AT registry */
123     private AttributeTypeRegistry attributeTypeRegistry;
124 
125     /** A pointer on the OID registry */
126     private OidRegistry oidRegistry;
127 
128 
129     // ------------------------------------------------------------------------
130     // C O N S T R U C T O R S
131     // ------------------------------------------------------------------------
132 
133 
134     /**
135      * Creates a store based on JDBM B+Trees.
136      */
137     public JdbmStore()
138     {
139     }
140 
141 
142     // -----------------------------------------------------------------------
143     // C O N F I G U R A T I O N   M E T H O D S
144     // -----------------------------------------------------------------------
145 
146 
147     private String suffixDn;
148     private int cacheSize = DEFAULT_CACHE_SIZE;
149     private String name;
150 
151 
152     private void protect( String property )
153     {
154         if ( initialized )
155         {
156             throw new IllegalStateException( "Cannot set jdbm store property " + property + " after initialization." );
157         }
158     }
159 
160 
161     public void setWorkingDirectory( File workingDirectory )
162     {
163         protect( "workingDirectory" );
164         this.workingDirectory = workingDirectory;
165     }
166 
167 
168     public File getWorkingDirectory()
169     {
170         return workingDirectory;
171     }
172 
173 
174     public void setSuffixDn( String suffixDn )
175     {
176         protect( "suffixDn" );
177         this.suffixDn = suffixDn;
178     }
179 
180 
181     public String getSuffixDn()
182     {
183         return suffixDn;
184     }
185 
186 
187     public void setSyncOnWrite( boolean isSyncOnWrite )
188     {
189         protect( "syncOnWrite" );
190         this.isSyncOnWrite = isSyncOnWrite;
191     }
192 
193 
194     public boolean isSyncOnWrite()
195     {
196         return isSyncOnWrite;
197     }
198 
199 
200     public void setCacheSize( int cacheSize )
201     {
202         protect( "cacheSize" );
203         this.cacheSize = cacheSize;
204     }
205 
206 
207     public int getCacheSize()
208     {
209         return cacheSize;
210     }
211 
212 
213     public void setName( String name )
214     {
215         protect( "name" );
216         this.name = name;
217     }
218 
219 
220     public String getName()
221     {
222         return name;
223     }
224 
225 
226     // -----------------------------------------------------------------------
227     // E N D   C O N F I G U R A T I O N   M E T H O D S
228     // -----------------------------------------------------------------------
229 
230 
231     /**
232      * Initialize the JDBM storage system.
233      *
234      * @param registries the schema registries
235      * @throws Exception on failure to lookup elements in registries or create database files
236      */
237     public synchronized void init( Registries registries ) throws Exception
238     {
239         this.oidRegistry = registries.getOidRegistry();
240         this.attributeTypeRegistry = registries.getAttributeTypeRegistry();
241 
242         OBJECT_CLASS_AT = attributeTypeRegistry.lookup( SchemaConstants.OBJECT_CLASS_AT );
243         ALIASED_OBJECT_NAME_AT = attributeTypeRegistry.lookup( SchemaConstants.ALIASED_OBJECT_NAME_AT );
244 
245         this.upSuffix = new LdapDN( suffixDn );
246         this.normSuffix = LdapDN.normalize( upSuffix, attributeTypeRegistry.getNormalizerMapping() );
247         workingDirectory.mkdirs();
248 
249         // First, check if the file storing the data exists
250         String path = workingDirectory.getPath() + File.separator + "master";
251         BaseRecordManager base = new BaseRecordManager( path );
252         base.disableTransactions();
253 
254         if ( cacheSize < 0 )
255         {
256             cacheSize = DEFAULT_CACHE_SIZE;
257             LOG.debug( "Using the default entry cache size of {} for {} partition", cacheSize, name );
258         }
259         else
260         {
261             LOG.debug( "Using the custom configured cache size of {} for {} partition", cacheSize, name );
262         }
263 
264         // Now, create the entry cache for this partition
265         recMan = new CacheRecordManager( base, new MRU( cacheSize ) );
266 
267         // Create the master table (the table containing all the entries)
268         master = new JdbmMasterTable<ServerEntry>( recMan, registries );
269 
270         // -------------------------------------------------------------------
271         // Initializes the user and system indices
272         // -------------------------------------------------------------------
273 
274         setupSystemIndices();
275         setupUserIndices();
276         
277         // We are done !
278         initialized = true;
279     }
280 
281 
282     @SuppressWarnings("unchecked")
283     private void setupSystemIndices() throws Exception
284     {
285         if ( systemIndices.size() > 0 )
286         {
287             HashMap<String, Index<?,E>> tmp = new HashMap<String, Index<?,E>>();
288             
289             for ( Index<?,E> index : systemIndices.values() )
290             {
291                 String oid = oidRegistry.getOid( index.getAttributeId() );
292                 tmp.put( oid, index );
293                 ( ( JdbmIndex ) index ).init( attributeTypeRegistry.lookup( oid ), workingDirectory );
294             }
295             systemIndices = tmp;
296         }
297 
298         if ( ndnIdx == null )
299         {
300             ndnIdx = new JdbmIndex<String,E>();
301             ndnIdx.setAttributeId( NDN );
302             systemIndices.put( NDN, ndnIdx );
303             ndnIdx.init( attributeTypeRegistry.lookup( NDN ), workingDirectory );
304         }
305 
306         if ( updnIdx == null )
307         {
308             updnIdx = new JdbmIndex<String,E>();
309             updnIdx.setAttributeId( UPDN );
310             systemIndices.put( UPDN, updnIdx );
311             updnIdx.init( attributeTypeRegistry.lookup( UPDN ), workingDirectory );
312         }
313 
314         if ( existenceIdx == null )
315         {
316             existenceIdx = new JdbmIndex<String,E>();
317             existenceIdx.setAttributeId( PRESENCE );
318             systemIndices.put( PRESENCE, existenceIdx );
319             existenceIdx.init( attributeTypeRegistry.lookup( PRESENCE ), workingDirectory );
320         }
321 
322         if ( oneLevelIdx == null )
323         {
324             oneLevelIdx = new JdbmIndex<Long,E>();
325             oneLevelIdx.setAttributeId( ONELEVEL );
326             systemIndices.put( ONELEVEL, oneLevelIdx );
327             oneLevelIdx.init( attributeTypeRegistry.lookup( ONELEVEL ), workingDirectory );
328         }
329 
330         if ( oneAliasIdx == null )
331         {
332             oneAliasIdx = new JdbmIndex<Long,E>();
333             oneAliasIdx.setAttributeId( ONEALIAS );
334             systemIndices.put( ONEALIAS, oneAliasIdx );
335             oneAliasIdx.init( attributeTypeRegistry.lookup( ONEALIAS ), workingDirectory );
336         }
337 
338         if ( subAliasIdx == null )
339         {
340             subAliasIdx = new JdbmIndex<Long,E>();
341             subAliasIdx.setAttributeId( SUBALIAS );
342             systemIndices.put( SUBALIAS, subAliasIdx );
343             subAliasIdx.init( attributeTypeRegistry.lookup( SUBALIAS ), workingDirectory );
344         }
345 
346         if ( aliasIdx == null )
347         {
348             aliasIdx = new JdbmIndex<String,E>();
349             aliasIdx.setAttributeId( ALIAS );
350             systemIndices.put( ALIAS, aliasIdx );
351             aliasIdx.init( attributeTypeRegistry.lookup( ALIAS ), workingDirectory );
352         }
353         
354         if ( subLevelIdx == null )
355         {
356             subLevelIdx = new JdbmIndex<Long, E>();
357             subLevelIdx.setAttributeId( SUBLEVEL );
358             systemIndices.put( SUBLEVEL, subLevelIdx );
359             subLevelIdx.init( attributeTypeRegistry.lookup( SUBLEVEL ), workingDirectory );
360         }
361     }
362 
363 
364     @SuppressWarnings("unchecked")
365     private void setupUserIndices() throws Exception
366     {
367         if ( userIndices != null && userIndices.size() > 0 )
368         {
369             Map<String, Index<?,E>> tmp = new HashMap<String, Index<?,E>>();
370             
371             for ( Index<?,E> index : userIndices.values() )
372             {
373                 String oid = oidRegistry.getOid( index.getAttributeId() );
374                 tmp.put( oid, index );
375                 ( ( JdbmIndex ) index ).init( attributeTypeRegistry.lookup( oid ), workingDirectory );
376             }
377             userIndices = tmp;
378         }
379         else
380         {
381             userIndices = new HashMap<String, Index<?,E>>();
382         }
383     }
384 
385 
386     /**
387      * Close the parttion : we have to close all the userIndices and the master table.
388      * 
389      * @throws Exception lazily thrown on any closer failures to avoid leaving
390      * open files
391      */
392     public synchronized void destroy() throws Exception
393     {
394         LOG.debug( "destroy() called on store for {}", this.suffixDn );
395 
396         if ( !initialized )
397         {
398             return;
399         }
400 
401         List<Index<?,E>> array = new ArrayList<Index<?,E>>();
402         array.addAll( userIndices.values() );
403         array.addAll( systemIndices.values() );
404         MultiException errors = new MultiException( "Errors encountered on destroy()" );
405 
406         for ( Index<?,E> index : array )
407         {
408             try
409             {
410                 index.close();
411                 LOG.debug( "Closed {} index for {} partition.", index.getAttributeId(), suffixDn );
412             }
413             catch ( Throwable t )
414             {
415                 LOG.error( "Failed to close an index.", t );
416                 errors.addThrowable( t );
417             }
418         }
419 
420         try
421         {
422             master.close();
423             LOG.debug( "Closed master table for {} partition.", suffixDn );
424         }
425         catch ( Throwable t )
426         {
427             LOG.error( "Failed to close the master.", t );
428             errors.addThrowable( t );
429         }
430 
431         try
432         {
433             recMan.close();
434             LOG.debug( "Closed record manager for {} partition.", suffixDn );
435         }
436         catch ( Throwable t )
437         {
438             LOG.error( "Failed to close the record manager", t );
439             errors.addThrowable( t );
440         }
441 
442         if ( errors.size() > 0 )
443         {
444             throw errors;
445         }
446 
447         initialized = false;
448     }
449 
450 
451     /**
452      * Gets whether the store is initialized.
453      *
454      * @return true if the partition store is initialized
455      */
456     public boolean isInitialized()
457     {
458         return initialized;
459     }
460 
461 
462     /**
463      * This method is called when the synch thread is waking up, to write
464      * the modified data.
465      * 
466      * @throws Exception on failures to sync database files to disk
467      */
468     public synchronized void sync() throws Exception
469     {
470         if ( !initialized )
471         {
472             return;
473         }
474 
475         List<Index<?,E>> array = new ArrayList<Index<?,E>>();
476         array.addAll( userIndices.values() );
477         array.add( ndnIdx );
478         array.add( updnIdx );
479         array.add( aliasIdx );
480         array.add( oneAliasIdx );
481         array.add( subAliasIdx );
482         array.add( oneLevelIdx );
483         array.add( existenceIdx );
484         array.add( subLevelIdx );
485         
486         // Sync all user defined userIndices
487         for ( Index<?,E> idx : array )
488         {
489             idx.sync();
490         }
491 
492         master.sync();
493         recMan.commit();
494     }
495 
496 
497     // ------------------------------------------------------------------------
498     // I N D E X   M E T H O D S
499     // ------------------------------------------------------------------------
500 
501 
502     private<K> JdbmIndex<K, E> convertIndex( Index<K,E> index )
503     {
504         if ( index instanceof JdbmIndex )
505         {
506             return ( JdbmIndex<K,E> ) index;
507         }
508 
509         LOG.warn( "Supplied index {} is not a JdbmIndex.  " +
510             "Will create new JdbmIndex using copied configuration parameters.", index );
511         JdbmIndex<K,E> jdbmIndex = new JdbmIndex<K, E>( index.getAttributeId() );
512         jdbmIndex.setCacheSize( index.getCacheSize() );
513         jdbmIndex.setNumDupLimit( JdbmIndex.DEFAULT_DUPLICATE_LIMIT );
514         jdbmIndex.setWkDirPath( index.getWkDirPath() );
515         return jdbmIndex;
516     }
517 
518 
519     public void setUserIndices( Set<Index<?,E>> userIndices )
520     {
521         protect( "userIndices" );
522         for ( Index<?,E> index : userIndices )
523         {
524             this.userIndices.put( index.getAttributeId(), convertIndex( index ) );
525         }
526     }
527 
528 
529     public Set<Index<?,E>> getUserIndices()
530     {
531         return new HashSet<Index<?,E>>( userIndices.values() );
532     }
533 
534     public void addIndex( Index<?,E> index ) throws Exception
535     {
536         userIndices.put( index.getAttributeId(), convertIndex( index ) );
537     }
538 
539 
540     public Index<String,E> getPresenceIndex()
541     {
542         return existenceIdx;
543     }
544 
545 
546     public void setPresenceIndex( Index<String,E> index ) throws Exception
547     {
548         protect( "existanceIndex" );
549         existenceIdx = convertIndex( index );
550         systemIndices.put( index.getAttributeId(), existenceIdx );
551     }
552 
553 
554     public Index<Long,E> getOneLevelIndex()
555     {
556         return oneLevelIdx;
557     }
558 
559 
560     public void setOneLevelIndex( Index<Long,E> index ) throws Exception
561     {
562         protect( "hierarchyIndex" );
563         oneLevelIdx = convertIndex( index );
564         systemIndices.put( index.getAttributeId(), oneLevelIdx );
565     }
566 
567 
568     public Index<String,E> getAliasIndex()
569     {
570         return aliasIdx;
571     }
572 
573 
574     public void setAliasIndex( Index<String,E> index ) throws NamingException
575     {
576         protect( "aliasIndex" );
577         aliasIdx = convertIndex( index );
578         systemIndices.put( index.getAttributeId(), aliasIdx );
579     }
580 
581 
582     public Index<Long,E> getOneAliasIndex()
583     {
584         return oneAliasIdx;
585     }
586 
587 
588     public void setOneAliasIndex( Index<Long,E> index ) throws NamingException
589     {
590         protect( "oneAliasIndex" );
591         oneAliasIdx = convertIndex( index );
592         systemIndices.put( index.getAttributeId(), oneAliasIdx );
593     }
594 
595 
596     public Index<Long,E> getSubAliasIndex()
597     {
598         return subAliasIdx;
599     }
600 
601 
602     public void setSubAliasIndex( Index<Long,E> index ) throws NamingException
603     {
604         protect( "subAliasIndex" );
605         subAliasIdx = convertIndex( index );
606         systemIndices.put( index.getAttributeId(), subAliasIdx );
607     }
608 
609 
610     public Index<String,E> getUpdnIndex()
611     {
612         return updnIdx;
613     }
614 
615 
616     public void setUpdnIndex( Index<String,E> index ) throws NamingException
617     {
618         protect( "updnIndex" );
619         updnIdx = convertIndex( index );
620         systemIndices.put( index.getAttributeId(), updnIdx );
621     }
622 
623 
624     public Index<String,E> getNdnIndex()
625     {
626         return ndnIdx;
627     }
628 
629 
630     public void setNdnIndex( Index<String,E> index ) throws NamingException
631     {
632         protect( "ndnIndex" );
633         ndnIdx = convertIndex( index );
634         systemIndices.put( index.getAttributeId(), ndnIdx );
635     }
636 
637 
638     public Index<Long,E> getSubLevelIndex()
639     {
640         return subLevelIdx;
641     }
642 
643 
644     public void setSubLevelIndex( Index<Long,E> index ) throws NamingException
645     {
646         protect( "subLevelIndex" );
647         subLevelIdx = convertIndex( index );
648         systemIndices.put( index.getAttributeId(), subLevelIdx );
649     }
650     
651     
652     public Iterator<String> userIndices()
653     {
654         return userIndices.keySet().iterator();
655     }
656 
657 
658     public Iterator<String> systemIndices()
659     {
660         return systemIndices.keySet().iterator();
661     }
662 
663 
664     public boolean hasUserIndexOn( String id ) throws NamingException
665     {
666         return userIndices.containsKey( oidRegistry.getOid( id ) );
667     }
668 
669 
670     public boolean hasSystemIndexOn( String id ) throws NamingException
671     {
672         return systemIndices.containsKey( oidRegistry.getOid( id ) );
673     }
674 
675 
676     public Index<?,E> getUserIndex( String id ) throws IndexNotFoundException
677     {
678         try
679         {
680             id = oidRegistry.getOid( id );
681         }
682         catch ( NamingException e )
683         {
684             LOG.error( "Failed to identify OID for: " + id, e );
685             throw new IndexNotFoundException( "Failed to identify OID for: " + id, id, e );
686         }
687 
688         if ( userIndices.containsKey( id ) )
689         {
690             return userIndices.get( id );
691         }
692 
693         throw new IndexNotFoundException( "A user index on attribute " + id + " ("
694             + name + ") does not exist!" );
695     }
696 
697 
698     public Index<?,E> getSystemIndex( String id ) throws IndexNotFoundException
699     {
700         try
701         {
702             id = oidRegistry.getOid( id );
703         }
704         catch ( NamingException e )
705         {
706             LOG.error( "Failed to identify OID for: " + id, e );
707             throw new IndexNotFoundException( "Failed to identify OID for: " + id, id, e );
708         }
709 
710         if ( systemIndices.containsKey( id ) )
711         {
712             return systemIndices.get( id );
713         }
714 
715         throw new IndexNotFoundException( "A system index on attribute " + id + " ("
716             + name + ") does not exist!" );
717     }
718 
719 
720     public Long getEntryId( String dn ) throws Exception
721     {
722         return ndnIdx.forwardLookup( dn );
723     }
724 
725 
726     public String getEntryDn( Long id ) throws Exception
727     {
728         return ndnIdx.reverseLookup( id );
729     }
730 
731 
732     /**
733      * Gets the Long id of an entry's parent using the child entry's
734      * normalized DN. Note that the suffix entry returns 0, which does not
735      * map to any entry.
736      *
737      * @param dn the normalized distinguished name of the child
738      * @return the id of the parent entry or zero if the suffix entry the
739      * normalized suffix DN string is used
740      * @throws Exception on failures to access the underlying store
741      */
742     public Long getParentId( String dn ) throws Exception
743     {
744         Long childId = ndnIdx.forwardLookup( dn );
745         return oneLevelIdx.reverseLookup( childId );
746     }
747 
748 
749     public Long getParentId( Long childId ) throws Exception
750     {
751         return oneLevelIdx.reverseLookup( childId );
752     }
753 
754 
755     public String getEntryUpdn( Long id ) throws Exception
756     {
757         return updnIdx.reverseLookup( id );
758     }
759 
760 
761     public String getEntryUpdn( String dn ) throws Exception
762     {
763         Long id = ndnIdx.forwardLookup( dn );
764         return updnIdx.reverseLookup( id );
765     }
766 
767 
768     public int count() throws Exception
769     {
770         return master.count();
771     }
772 
773 
774     /**
775      * Removes the index entries for an alias before the entry is deleted from
776      * the master table.
777      * 
778      * @todo Optimize this by walking the hierarchy index instead of the name 
779      * @param aliasId the id of the alias entry in the master table
780      * @throws NamingException if we cannot parse ldap names
781      * @throws Exception if we cannot delete index values in the database
782      */
783     private void dropAliasIndices( Long aliasId ) throws Exception
784     {
785         String targetDn = aliasIdx.reverseLookup( aliasId );
786         Long targetId = getEntryId( targetDn );
787         String aliasDn = getEntryDn( aliasId );
788         LdapDN ancestorDn = ( LdapDN ) new LdapDN( aliasDn ).getPrefix( 1 );
789         Long ancestorId = getEntryId( ancestorDn.toString() );
790 
791         /*
792          * We cannot just drop all tuples in the one level and subtree userIndices
793          * linking baseIds to the targetId.  If more than one alias refers to
794          * the target then droping all tuples with a value of targetId would
795          * make all other aliases to the target inconsistent.
796          * 
797          * We need to walk up the path of alias ancestors until we reach the 
798          * upSuffix, deleting each ( ancestorId, targetId ) tuple in the
799          * subtree scope alias.  We only need to do this for the direct parent
800          * of the alias on the one level subtree.
801          */
802         oneAliasIdx.drop( ancestorId, targetId );
803         subAliasIdx.drop( ancestorId, targetId );
804 
805         while ( !ancestorDn.equals( normSuffix ) )
806         {
807             ancestorDn = ( LdapDN ) ancestorDn.getPrefix( 1 );
808             ancestorId = getEntryId( ancestorDn.toString() );
809 
810             subAliasIdx.drop( ancestorId, targetId );
811         }
812 
813         // Drops all alias tuples pointing to the id of the alias to be deleted
814         aliasIdx.drop( aliasId );
815     }
816 
817 
818     /**
819      * Adds userIndices for an aliasEntry to be added to the database while checking
820      * for constrained alias constructs like alias cycles and chaining.
821      * 
822      * @param aliasDn normalized distinguished name for the alias entry
823      * @param aliasTarget the user provided aliased entry dn as a string
824      * @param aliasId the id of alias entry to add
825      * @throws NamingException if index addition fails, and if the alias is
826      * not allowed due to chaining or cycle formation.
827      * @throws Exception if the wrappedCursor btrees cannot be altered
828      */
829     private void addAliasIndices( Long aliasId, LdapDN aliasDn, String aliasTarget ) throws Exception
830     {
831         LdapDN normalizedAliasTargetDn; // Name value of aliasedObjectName
832         Long targetId; // Id of the aliasedObjectName
833         LdapDN ancestorDn; // Name of an alias entry relative
834         Long ancestorId; // Id of an alias entry relative
835 
836         // Access aliasedObjectName, normalize it and generate the Name 
837         normalizedAliasTargetDn = new LdapDN( aliasTarget );
838         normalizedAliasTargetDn.normalize( attributeTypeRegistry.getNormalizerMapping() );
839 
840         /*
841          * Check For Cycles
842          * 
843          * Before wasting time to lookup more values we check using the target
844          * dn to see if we have the possible formation of an alias cycle.  This
845          * happens when the alias refers back to a target that is also a 
846          * relative of the alias entry.  For detection we test if the aliased
847          * entry Dn starts with the target Dn.  If it does then we know the 
848          * aliased target is a relative and we have a perspecitive cycle.
849          */
850         if ( aliasDn.startsWith( normalizedAliasTargetDn ) )
851         {
852             if ( aliasDn.equals( normalizedAliasTargetDn ) )
853             {
854                 throw new NamingException( "[36] aliasDereferencingProblem - " + "attempt to create alias to itself." );
855             }
856 
857             throw new NamingException( "[36] aliasDereferencingProblem - "
858                 + "attempt to create alias with cycle to relative " + aliasTarget
859                 + " not allowed from descendent alias " + aliasDn );
860         }
861 
862         /*
863          * Check For Aliases External To Naming Context
864          * 
865          * id may be null but the alias may be to a valid entry in 
866          * another namingContext.  Such aliases are not allowed and we
867          * need to point it out to the user instead of saying the target
868          * does not exist when it potentially could outside of this upSuffix.
869          */
870         if ( !normalizedAliasTargetDn.startsWith( normSuffix ) )
871         {
872             // Complain specifically about aliases to outside naming contexts
873             throw new NamingException( "[36] aliasDereferencingProblem -"
874                 + " the alias points to an entry outside of the " + upSuffix.getUpName()
875                 + " namingContext to an object whose existance cannot be" + " determined." );
876         }
877 
878         // L O O K U P   T A R G E T   I D
879         targetId = ndnIdx.forwardLookup( normalizedAliasTargetDn.toNormName() );
880 
881         /*
882          * Check For Target Existance
883          * 
884          * We do not allow the creation of inconsistant aliases.  Aliases should
885          * not be broken links.  If the target does not exist we start screaming
886          */
887         if ( null == targetId )
888         {
889             // Complain about target not existing
890             throw new NamingException( "[33] aliasProblem - "
891                 + "the alias when dereferenced would not name a known object "
892                 + "the aliasedObjectName must be set to a valid existing " + "entry." );
893         }
894 
895         /*
896          * Detect Direct Alias Chain Creation
897          * 
898          * Rather than resusitate the target to test if it is an alias and fail
899          * due to chaing creation we use the alias index to determine if the
900          * target is an alias.  Hence if the alias we are about to create points
901          * to another alias as its target in the aliasedObjectName attribute, 
902          * then we have a situation where an alias chain is being created.  
903          * Alias chaining is not allowed so we throw and exception. 
904          */
905         if ( null != aliasIdx.reverseLookup( targetId ) )
906         {
907             // Complain about illegal alias chain
908             throw new NamingException( "[36] aliasDereferencingProblem -"
909                 + " the alias points to another alias.  Alias chaining is" + " not supported by this backend." );
910         }
911 
912         // Add the alias to the simple alias index
913         aliasIdx.add( normalizedAliasTargetDn.getNormName(), aliasId );
914 
915         /*
916          * Handle One Level Scope Alias Index
917          * 
918          * The first relative is special with respect to the one level alias
919          * index.  If the target is not a sibling of the alias then we add the
920          * index entry maping the parent's id to the aliased target id.
921          */
922         ancestorDn = ( LdapDN ) aliasDn.clone();
923         ancestorDn.remove( aliasDn.size() - 1 );
924         ancestorId = getEntryId( ancestorDn.toNormName() );
925 
926         // check if alias parent and aliased entry are the same
927         LdapDN normalizedAliasTargetParentDn = ( LdapDN ) normalizedAliasTargetDn.clone();
928         normalizedAliasTargetParentDn.remove( normalizedAliasTargetDn.size() - 1 );
929         if ( ! aliasDn.startsWith( normalizedAliasTargetParentDn ) )
930         {
931             oneAliasIdx.add( ancestorId, targetId );
932         }
933 
934         /*
935          * Handle Sub Level Scope Alias Index
936          * 
937          * Walk the list of relatives from the parents up to the upSuffix, testing
938          * to see if the alias' target is a descendant of the relative.  If the
939          * alias target is not a descentant of the relative it extends the scope
940          * and is added to the sub tree scope alias index.  The upSuffix node is
941          * ignored since everything is under its scope.  The first loop 
942          * iteration shall handle the parents.
943          */
944         while ( !ancestorDn.equals( normSuffix ) && null != ancestorId )
945         {
946             if ( !NamespaceTools.isDescendant( ancestorDn, normalizedAliasTargetDn ) )
947             {
948                 subAliasIdx.add( ancestorId, targetId );
949             }
950 
951             ancestorDn.remove( ancestorDn.size() - 1 );
952             ancestorId = getEntryId( ancestorDn.toNormName() );
953         }
954     }
955 
956 
957     // TODO Change signature to not require the DN parameter since it is now
958     // in the ServerEntry  !!!
959     @SuppressWarnings("unchecked")
960     public void add( LdapDN normName, ServerEntry entry ) throws Exception
961     {
962         if ( entry instanceof ClonedServerEntry )
963         {
964             throw new Exception( "Cannot store a ClonedServerEntry" );
965         }
966         
967         Long id;
968         Long parentId;
969 
970         id = master.getNextId();
971 
972         //
973         // Suffix entry cannot have a parent since it is the root so it is 
974         // capped off using the zero value which no entry can have since 
975         // entry sequences start at 1.
976         //
977 
978         LdapDN parentDn = null;
979 
980         if ( normName.getNormName().equals( normSuffix.getNormName() ) )
981         {
982             parentId = 0L;
983         }
984         else
985         {
986             parentDn = ( LdapDN ) normName.clone();
987             parentDn.remove( parentDn.size() - 1 );
988             parentId = getEntryId( parentDn.toString() );
989         }
990 
991         // don't keep going if we cannot find the parent Id
992         if ( parentId == null )
993         {
994             throw new LdapNameNotFoundException( "Id for parent '" + parentDn + "' not found!" );
995         }
996 
997         EntryAttribute objectClass = entry.get( OBJECT_CLASS_AT );
998 
999         if ( objectClass == null )
1000         {
1001             String msg = "Entry " + normName.getUpName() + " contains no objectClass attribute: " + entry;
1002             throw new LdapSchemaViolationException( msg, ResultCodeEnum.OBJECT_CLASS_VIOLATION );
1003         }
1004 
1005         // Start adding the system userIndices
1006         // Why bother doing a lookup if this is not an alias.
1007 
1008         if ( objectClass.contains( SchemaConstants.ALIAS_OC ) )
1009         {
1010             EntryAttribute aliasAttr = entry.get( ALIASED_OBJECT_NAME_AT );
1011             addAliasIndices( id, normName, aliasAttr.getString() );
1012         }
1013 
1014         if ( !Character.isDigit( normName.toNormName().charAt( 0 ) ) )
1015         {
1016             throw new IllegalStateException( "Not a normalized name: " + normName.toNormName() );
1017         }
1018 
1019         ndnIdx.add( normName.toNormName(), id );
1020         updnIdx.add( normName.getUpName(), id );
1021         oneLevelIdx.add( parentId, id );
1022         
1023         Long tempId = parentId;
1024         while( tempId != null && tempId != 0 && tempId != 1 )
1025         {
1026             subLevelIdx.add( tempId, id );
1027             tempId = getParentId( tempId );
1028         }
1029         subLevelIdx.add( id, id );
1030         
1031         // Now work on the user defined userIndices
1032         for ( EntryAttribute attribute : entry )
1033         {
1034             String attributeOid = ( ( ServerAttribute ) attribute ).getAttributeType().getOid();
1035 
1036             if ( hasUserIndexOn( attributeOid ) )
1037             {
1038                 Index<Object,E> idx = ( Index<Object,E> ) getUserIndex( attributeOid );
1039 
1040                 // here lookup by attributeId is OK since we got attributeId from 
1041                 // the entry via the enumeration - it's in there as is for sure
1042 
1043                 for ( Value<?> value : attribute )
1044                 {
1045                     idx.add( value.get(), id );
1046                 }
1047 
1048                 // Adds only those attributes that are indexed
1049                 existenceIdx.add( attributeOid, id );
1050             }
1051         }
1052 
1053         master.put( id, entry );
1054 
1055         if ( isSyncOnWrite )
1056         {
1057             sync();
1058         }
1059     }
1060 
1061 
1062     public ServerEntry lookup( Long id ) throws Exception
1063     {
1064         return ( ServerEntry ) master.get( id );
1065     }
1066 
1067 
1068     @SuppressWarnings("unchecked")
1069     public void delete( Long id ) throws Exception
1070     {
1071         ServerEntry entry = lookup( id );
1072         Long parentId = getParentId( id );
1073 
1074         EntryAttribute objectClass = entry.get( OBJECT_CLASS_AT );
1075 
1076         if ( objectClass.contains( SchemaConstants.ALIAS_OC ) )
1077         {
1078             dropAliasIndices( id );
1079         }
1080 
1081         ndnIdx.drop( id );
1082         updnIdx.drop( id );
1083         oneLevelIdx.drop( id );
1084 
1085         if( parentId != 1 )// should not use getParentId() to compare, onelevel index drops the 'id'
1086         {
1087             subLevelIdx.drop( id );
1088         }
1089         
1090         // Remove parent's reference to entry only if entry is not the upSuffix
1091         if ( !parentId.equals( 0L ) )
1092         {
1093             oneLevelIdx.drop( parentId, id );
1094         }
1095 
1096         for ( EntryAttribute attribute : entry )
1097         {
1098             String attributeOid = ( ( ServerAttribute ) attribute ).getAttributeType().getOid();
1099 
1100             if ( hasUserIndexOn( attributeOid ) )
1101             {
1102                 Index<?,E> index = getUserIndex( attributeOid );
1103 
1104                 // here lookup by attributeId is ok since we got attributeId from 
1105                 // the entry via the enumeration - it's in there as is for sure
1106                 for ( Value<?> value : attribute )
1107                 {
1108                     ( ( JdbmIndex ) index ).drop( value.get(), id );
1109                 }
1110 
1111                 existenceIdx.drop( attributeOid, id );
1112             }
1113         }
1114 
1115         master.delete( id );
1116 
1117         if ( isSyncOnWrite )
1118         {
1119             sync();
1120         }
1121     }
1122 
1123 
1124     /**
1125      * Gets an IndexEntry Cursor over the child nodes of an entry.
1126      *
1127      * @param id the id of the parent entry
1128      * @return an IndexEntry Cursor over the child entries
1129      * @throws Exception on failures to access the underlying store
1130      */
1131     public IndexCursor<Long,E> list( Long id ) throws Exception
1132     {
1133         IndexCursor<Long,E> cursor = oneLevelIdx.forwardCursor( id );
1134         cursor.beforeValue( id, null );
1135         return cursor;
1136     }
1137 
1138 
1139     public int getChildCount( Long id ) throws Exception
1140     {
1141         return oneLevelIdx.count( id );
1142     }
1143 
1144 
1145     public LdapDN getSuffix()
1146     {
1147         return normSuffix;
1148     }
1149 
1150 
1151     public LdapDN getUpSuffix()
1152     {
1153         return upSuffix;
1154     }
1155 
1156 
1157     public void setProperty( String propertyName, String propertyValue ) throws Exception
1158     {
1159         master.setProperty( propertyName, propertyValue );
1160     }
1161 
1162 
1163     public String getProperty( String propertyName ) throws Exception
1164     {
1165         return master.getProperty( propertyName );
1166     }
1167 
1168 
1169     /**
1170      * Adds a set of attribute values while affecting the appropriate userIndices.
1171      * The entry is not persisted: it is only changed in anticipation for a put 
1172      * into the master table.
1173      *
1174      * @param id the primary key of the entry
1175      * @param entry the entry to alter
1176      * @param mods the attribute and values to add 
1177      * @throws Exception if index alteration or attribute addition fails
1178      */
1179     @SuppressWarnings("unchecked")
1180     private void add( Long id, ServerEntry entry, EntryAttribute mods ) throws Exception
1181     {
1182         if ( entry instanceof ClonedServerEntry )
1183         {
1184             throw new Exception( "Cannot store a ClonedServerEntry" );
1185         }
1186         
1187         String modsOid = oidRegistry.getOid( mods.getId() );
1188 
1189         if ( hasUserIndexOn( modsOid ) )
1190         {
1191             Index<?,E> index = getUserIndex( modsOid );
1192 
1193             for ( Value<?> value : mods )
1194             {
1195                 ( ( JdbmIndex ) index ).add( value.get(), id );
1196             }
1197 
1198             // If the attr didn't exist for this id add it to existence index
1199             if ( !existenceIdx.forward( modsOid, id ) )
1200             {
1201                 existenceIdx.add( modsOid, id );
1202             }
1203         }
1204 
1205         // add all the values in mods to the same attribute in the entry
1206         AttributeType type = attributeTypeRegistry.lookup( modsOid );
1207 
1208         for ( Value<?> value : mods )
1209         {
1210             entry.add( type, value );
1211         }
1212 
1213         if ( modsOid.equals( oidRegistry.getOid( SchemaConstants.ALIASED_OBJECT_NAME_AT ) ) )
1214         {
1215             String ndnStr = ndnIdx.reverseLookup( id );
1216             addAliasIndices( id, new LdapDN( ndnStr ), mods.getString() );
1217         }
1218     }
1219 
1220 
1221     /**
1222      * Completely removes the set of values for an attribute having the values 
1223      * supplied while affecting the appropriate userIndices.  The entry is not
1224      * persisted: it is only changed in anticipation for a put into the master 
1225      * table.  Note that an empty attribute w/o values will remove all the 
1226      * values within the entry where as an attribute w/ values will remove those
1227      * attribute values it contains.
1228      *
1229      * @param id the primary key of the entry
1230      * @param entry the entry to alter
1231      * @param mods the attribute and its values to delete
1232      * @throws Exception if index alteration or attribute modification fails.
1233      */
1234     @SuppressWarnings("unchecked")
1235     private void remove( Long id, ServerEntry entry, EntryAttribute mods ) throws Exception
1236     {
1237         if ( entry instanceof ClonedServerEntry )
1238         {
1239             throw new Exception( "Cannot store a ClonedServerEntry" );
1240         }
1241         
1242         String modsOid = oidRegistry.getOid( mods.getId() );
1243 
1244         if ( hasUserIndexOn( modsOid ) )
1245         {
1246             Index<?,E> index = getUserIndex( modsOid );
1247             
1248             for ( Value<?> value : mods )
1249             {
1250                 ( ( JdbmIndex ) index ).drop( value.get(), id );
1251             }
1252 
1253             /* 
1254              * If no attribute values exist for this entryId in the index then
1255              * we remove the existance index entry for the removed attribute.
1256              */
1257             if ( null == index.reverseLookup( id ) )
1258             {
1259                 existenceIdx.drop( modsOid, id );
1260             }
1261         }
1262 
1263         AttributeType attrType = attributeTypeRegistry.lookup( modsOid );
1264         /*
1265          * If there are no attribute values in the modifications then this 
1266          * implies the compelete removal of the attribute from the entry. Else
1267          * we remove individual attribute values from the entry in mods one 
1268          * at a time.
1269          */
1270         if ( mods.size() == 0 )
1271         {
1272             entry.removeAttributes( attrType );
1273         }
1274         else
1275         {
1276             EntryAttribute entryAttr = entry.get( attrType );
1277 
1278             for ( Value<?> value : mods )
1279             {
1280                 if ( value instanceof ServerStringValue )
1281                 {
1282                     entryAttr.remove( ( String ) value.get() );
1283                 }
1284                 else
1285                 {
1286                     entryAttr.remove( ( byte[] ) value.get() );
1287                 }
1288             }
1289 
1290             // if nothing is left just remove empty attribute
1291             if ( entryAttr.size() == 0 )
1292             {
1293                 entry.removeAttributes( entryAttr.getId() );
1294             }
1295         }
1296 
1297         // Aliases->single valued comp/partial attr removal is not relevant here
1298         if ( modsOid.equals( oidRegistry.getOid( SchemaConstants.ALIASED_OBJECT_NAME_AT ) ) )
1299         {
1300             dropAliasIndices( id );
1301         }
1302     }
1303 
1304 
1305     /**
1306      * Completely replaces the existing set of values for an attribute with the
1307      * modified values supplied affecting the appropriate userIndices.  The entry
1308      * is not persisted: it is only changed in anticipation for a put into the
1309      * master table.
1310      *
1311      * @param id the primary key of the entry
1312      * @param entry the entry to alter
1313      * @param mods the replacement attribute and values
1314      * @throws Exception if index alteration or attribute modification 
1315      * fails.
1316      */
1317     @SuppressWarnings("unchecked")
1318     private void replace( Long id, ServerEntry entry, EntryAttribute mods ) throws Exception
1319     {
1320         if ( entry instanceof ClonedServerEntry )
1321         {
1322             throw new Exception( "Cannot store a ClonedServerEntry" );
1323         }
1324         
1325         String modsOid = oidRegistry.getOid( mods.getId() );
1326 
1327         if ( hasUserIndexOn( modsOid ) )
1328         {
1329             Index<?,E> index = getUserIndex( modsOid );
1330 
1331             // if the id exists in the index drop all existing attribute value index entries and add new ones
1332             if( index.reverse( id ) )
1333             {
1334                 ( ( JdbmIndex<?,E> ) index ).drop( id );
1335             }
1336             
1337             for ( Value<?> value : mods )
1338             {
1339                 ( ( JdbmIndex<Object,E> ) index ).add( value.get(), id );
1340             }
1341 
1342             /* 
1343              * If no attribute values exist for this entryId in the index then
1344              * we remove the existance index entry for the removed attribute.
1345              */
1346             if ( null == index.reverseLookup( id ) )
1347             {
1348                 existenceIdx.drop( modsOid, id );
1349             }
1350         }
1351 
1352         String aliasAttributeOid = oidRegistry.getOid( SchemaConstants.ALIASED_OBJECT_NAME_AT );
1353 
1354         if ( modsOid.equals( aliasAttributeOid ) )
1355         {
1356             dropAliasIndices( id );
1357         }
1358 
1359         // replaces old attributes with new modified ones if they exist
1360         if ( mods.size() > 0 )
1361         {
1362             entry.put( mods );
1363         }
1364         else
1365         // removes old attributes if new replacements do not exist
1366         {
1367             entry.remove( mods );
1368         }
1369 
1370         if ( modsOid.equals( aliasAttributeOid ) && mods.size() > 0 )
1371         {
1372             String ndnStr = ndnIdx.reverseLookup( id );
1373             addAliasIndices( id, new LdapDN( ndnStr ), mods.getString() );
1374         }
1375     }
1376 
1377 
1378     public void modify( LdapDN dn, ModificationOperation modOp, ServerEntry mods ) throws Exception
1379     {
1380         if ( mods instanceof ClonedServerEntry )
1381         {
1382             throw new Exception( "Cannot store a ClonedServerEntry" );
1383         }
1384         
1385         Long id = getEntryId( dn.toString() );
1386         ServerEntry entry = ( ServerEntry ) master.get( id );
1387 
1388         for ( AttributeType attributeType : mods.getAttributeTypes() )
1389         {
1390             EntryAttribute attr = mods.get( attributeType );
1391 
1392             switch ( modOp )
1393             {
1394                 case ADD_ATTRIBUTE:
1395                     add( id, entry, attr );
1396                     break;
1397 
1398                 case REMOVE_ATTRIBUTE:
1399                     remove( id, entry, attr );
1400                     break;
1401 
1402                 case REPLACE_ATTRIBUTE:
1403                     replace( id, entry, attr );
1404 
1405                     break;
1406 
1407                 default:
1408                     throw new NamingException( "Unidentified modification operation" );
1409             }
1410         }
1411 
1412         master.put( id, entry );
1413 
1414         if ( isSyncOnWrite )
1415         {
1416             sync();
1417         }
1418     }
1419 
1420 
1421     public void modify( LdapDN dn, List<Modification> mods ) throws Exception
1422     {
1423         Long id = getEntryId( dn.toString() );
1424         ServerEntry entry = ( ServerEntry ) master.get( id );
1425 
1426         for ( Modification mod : mods )
1427         {
1428             ServerAttribute attrMods = ( ServerAttribute ) mod.getAttribute();
1429 
1430             switch ( mod.getOperation() )
1431             {
1432                 case ADD_ATTRIBUTE:
1433                     add( id, entry, attrMods );
1434                     break;
1435 
1436                 case REMOVE_ATTRIBUTE:
1437                     remove( id, entry, attrMods );
1438                     break;
1439 
1440                 case REPLACE_ATTRIBUTE:
1441                     replace( id, entry, attrMods );
1442                     break;
1443 
1444                 default:
1445                     throw new NamingException( "Unidentified modification operation" );
1446             }
1447         }
1448 
1449         master.put( id, entry );
1450 
1451         if ( isSyncOnWrite )
1452         {
1453             sync();
1454         }
1455     }
1456 
1457 
1458     /**
1459      * Changes the relative distinguished name of an entry specified by a 
1460      * distinguished name with the optional removal of the old Rdn attribute
1461      * value from the entry.  Name changes propagate down as dn changes to the 
1462      * descendants of the entry where the Rdn changed. 
1463      * 
1464      * An Rdn change operation does not change parent child relationships.  It 
1465      * merely propagates a name change at a point in the DIT where the Rdn is 
1466      * changed. The change propagates down the subtree rooted at the 
1467      * distinguished name specified.
1468      *
1469      * @param dn the normalized distinguished name of the entry to alter
1470      * @param newRdn the new Rdn to set
1471      * @param deleteOldRdn whether or not to remove the old Rdn attr/val
1472      * @throws Exception if there are any errors propagating the name changes
1473      */
1474     @SuppressWarnings("unchecked")
1475     public void rename( LdapDN dn, Rdn newRdn, boolean deleteOldRdn ) throws Exception
1476     {
1477         Long id = getEntryId( dn.getNormName() );
1478         ServerEntry entry = lookup( id );
1479         LdapDN updn = entry.getDn();
1480 
1481         /* 
1482          * H A N D L E   N E W   R D N
1483          * ====================================================================
1484          * Add the new Rdn attribute to the entry.  If an index exists on the 
1485          * new Rdn attribute we add the index for this attribute value pair.
1486          * Also we make sure that the existance index shows the existance of the
1487          * new Rdn attribute within this entry.
1488          */
1489 
1490         for ( AttributeTypeAndValue newAtav : newRdn )
1491         {
1492             String newNormType = newAtav.getNormType();
1493             String newNormValue = ( String ) newAtav.getNormValue();
1494             AttributeType newRdnAttrType = attributeTypeRegistry.lookup( newNormType );
1495             
1496             Object unEscapedRdn = Rdn.unescapeValue( (String)newAtav.getUpValue() );
1497             
1498             Value<?> value = null;
1499             
1500             if ( unEscapedRdn instanceof String )
1501             {
1502                 value = new ServerStringValue( newRdnAttrType, (String)unEscapedRdn );
1503             }
1504             else
1505             {
1506                 value = new ServerBinaryValue( newRdnAttrType, (byte[])unEscapedRdn );
1507             }
1508             
1509             value.normalize();
1510             
1511             entry.add( newRdnAttrType, value );
1512 
1513             if ( hasUserIndexOn( newNormType ) )
1514             {
1515                 Index<?, E> index = getUserIndex( newNormType );
1516                 ( ( JdbmIndex ) index ).add( newNormValue, id );
1517 
1518                 // Make sure the altered entry shows the existence of the new attrib
1519                 if ( !existenceIdx.forward( newNormType, id ) )
1520                 {
1521                     existenceIdx.add( newNormType, id );
1522                 }
1523             }
1524         }
1525 
1526         /*
1527          * H A N D L E   O L D   R D N
1528          * ====================================================================
1529          * If the old Rdn is to be removed we need to get the attribute and 
1530          * value for it.  Keep in mind the old Rdn need not be based on the 
1531          * same attr as the new one.  We remove the Rdn value from the entry
1532          * and remove the value/id tuple from the index on the old Rdn attr
1533          * if any.  We also test if the delete of the old Rdn index tuple 
1534          * removed all the attribute values of the old Rdn using a reverse
1535          * lookup.  If so that means we blew away the last value of the old 
1536          * Rdn attribute.  In this case we need to remove the attrName/id 
1537          * tuple from the existance index.
1538          * 
1539          * We only remove an ATAV of the old Rdn if it is not included in the
1540          * new Rdn.
1541          */
1542 
1543         if ( deleteOldRdn )
1544         {
1545             Rdn oldRdn = updn.getRdn();
1546             for ( AttributeTypeAndValue oldAtav : oldRdn )
1547             {
1548                 // check if the new ATAV is part of the old Rdn
1549                 // if that is the case we do not remove the ATAV
1550                 boolean mustRemove = true;
1551                 for ( AttributeTypeAndValue newAtav : newRdn )
1552                 {
1553                     if ( oldAtav.equals( newAtav ) )
1554                     {
1555                         mustRemove = false;
1556                         break;
1557                     }
1558                 }
1559 
1560                 if ( mustRemove )
1561                 {
1562                     String oldNormType = oldAtav.getNormType();
1563                     String oldNormValue = ( String ) oldAtav.getNormValue();
1564                     AttributeType oldRdnAttrType = attributeTypeRegistry.lookup( oldNormType );
1565                     entry.remove( oldRdnAttrType, oldNormValue );
1566 
1567                     if ( hasUserIndexOn( oldNormType ) )
1568                     {
1569                         Index<?, E> index = getUserIndex( oldNormType );
1570                         ( ( JdbmIndex ) index ).drop( oldNormValue, id );
1571 
1572                         /*
1573                          * If there is no value for id in this index due to our
1574                          * drop above we remove the oldRdnAttr from the existance idx
1575                          */
1576                         if ( null == index.reverseLookup( id ) )
1577                         {
1578                             existenceIdx.drop( oldNormType, id );
1579                         }
1580                     }
1581                 }
1582             }
1583         }
1584 
1585         /*
1586          * H A N D L E   D N   C H A N G E
1587          * ====================================================================
1588          * 1) Build the new user defined distinguished name
1589          *      - clone / copy old updn
1590          *      - remove old upRdn from copy
1591          *      - add the new upRdn to the copy
1592          * 2) Make call to recursive modifyDn method to change the names of the
1593          *    entry and its descendants
1594          */
1595 
1596         LdapDN newUpdn = ( LdapDN ) updn.clone(); // copy da old updn
1597         newUpdn.remove( newUpdn.size() - 1 ); // remove old upRdn
1598         newUpdn.add( newRdn.getUpName() ); // add da new upRdn
1599 
1600         // gotta normalize cuz this thang is cloned and not normalized by default
1601         newUpdn.normalize( attributeTypeRegistry.getNormalizerMapping() );
1602 
1603         modifyDn( id, newUpdn, false ); // propagate dn changes
1604 
1605         // Update the current entry
1606         entry.setDn( newUpdn );
1607         master.put( id, entry );
1608 
1609         if ( isSyncOnWrite )
1610         {
1611             sync();
1612         }
1613     }
1614 
1615 
1616     /*
1617      * The move operation severs a child from a parent creating a new parent
1618      * child relationship.  As a consequence the relationships between the 
1619      * old ancestors of the child and its descendants change.  A descendant is
1620      *   
1621      */
1622 
1623     /**
1624      * Recursively modifies the distinguished name of an entry and the names of
1625      * its descendants calling itself in the recursion.
1626      *
1627      * @param id the primary key of the entry
1628      * @param updn User provided distinguished name to set as the new DN
1629      * @param isMove whether or not the name change is due to a move operation
1630      * which affects alias userIndices.
1631      * @throws NamingException if something goes wrong
1632      */
1633     private void modifyDn( Long id, LdapDN updn, boolean isMove ) throws Exception
1634     {
1635         String aliasTarget;
1636 
1637         // update normalized DN index
1638         ndnIdx.drop( id );
1639         if ( !updn.isNormalized() )
1640         {
1641             updn.normalize( attributeTypeRegistry.getNormalizerMapping() );
1642         }
1643         ndnIdx.add( updn.toNormName(), id );
1644         
1645         // update user provided DN index
1646         updnIdx.drop( id );
1647         updnIdx.add( updn.getUpName(), id );
1648 
1649         /* 
1650          * Read Alias Index Tuples
1651          * 
1652          * If this is a name change due to a move operation then the one and
1653          * subtree userIndices for aliases were purged before the aliases were
1654          * moved.  Now we must add them for each alias entry we have moved.  
1655          * 
1656          * aliasTarget is used as a marker to tell us if we're moving an 
1657          * alias.  If it is null then the moved entry is not an alias.
1658          */
1659         if ( isMove )
1660         {
1661             aliasTarget = aliasIdx.reverseLookup( id );
1662 
1663             if ( null != aliasTarget )
1664             {
1665                 addAliasIndices( id, new LdapDN( getEntryDn( id ) ), aliasTarget );
1666             }
1667         }
1668 
1669         Cursor<IndexEntry<Long,E>> children = list( id );
1670         while ( children.next() )
1671         {
1672             // Get the child and its id
1673             IndexEntry<Long,E> rec = children.get();
1674             Long childId = rec.getId();
1675 
1676             /* 
1677              * Calculate the DN for the child's new name by copying the parents
1678              * new name and adding the child's old upRdn to new name as its Rdn
1679              */
1680             LdapDN childUpdn = ( LdapDN ) updn.clone();
1681             LdapDN oldUpdn = new LdapDN( getEntryUpdn( childId ) );
1682 
1683             String rdn = oldUpdn.get( oldUpdn.size() - 1 );
1684             LdapDN rdnDN = new LdapDN( rdn );
1685             rdnDN.normalize( attributeTypeRegistry.getNormalizerMapping() );
1686             childUpdn.add( rdnDN.getRdn() );
1687 
1688             // Modify the child
1689             ServerEntry entry = lookup( childId );
1690             entry.setDn( childUpdn );
1691             master.put( childId, entry );
1692 
1693             // Recursively change the names of the children below
1694             modifyDn( childId, childUpdn, isMove );
1695         }
1696         
1697         children.close();
1698     }
1699 
1700 
1701     public void move( LdapDN oldChildDn, LdapDN newParentDn, Rdn newRdn, boolean deleteOldRdn ) throws Exception
1702     {
1703         Long childId = getEntryId( oldChildDn.toString() );
1704         rename( oldChildDn, newRdn, deleteOldRdn );
1705         LdapDN newUpdn = move( oldChildDn, childId, newParentDn );
1706 
1707         // Update the current entry
1708         ServerEntry entry = lookup( childId );
1709         entry.setDn( newUpdn );
1710         master.put( childId, entry );
1711 
1712         if ( isSyncOnWrite )
1713         {
1714             sync();
1715         }
1716     }
1717 
1718 
1719     public void move( LdapDN oldChildDn, LdapDN newParentDn ) throws Exception
1720     {
1721         Long childId = getEntryId( oldChildDn.toString() );
1722         LdapDN newUpdn = move( oldChildDn, childId, newParentDn );
1723 
1724         // Update the current entry
1725         ServerEntry entry = lookup( childId );
1726         entry.setDn( newUpdn );
1727         master.put( childId, entry );
1728 
1729         if ( isSyncOnWrite )
1730         {
1731             sync();
1732         }
1733     }
1734 
1735 
1736     /**
1737      * Moves an entry under a new parent.  The operation causes a shift in the
1738      * parent child relationships between the old parent, new parent and the 
1739      * child moved.  All other descendant entries under the child never change
1740      * their direct parent child relationships.  Hence after the parent child
1741      * relationship changes are broken at the old parent and set at the new
1742      * parent a modifyDn operation is conducted to handle name changes 
1743      * propagating down through the moved child and its descendants.
1744      * 
1745      * @param oldChildDn the normalized dn of the child to be moved
1746      * @param childId the id of the child being moved
1747      * @param newParentDn the normalized dn of the new parent for the child
1748      * @throws NamingException if something goes wrong
1749      */
1750     private LdapDN move( LdapDN oldChildDn, Long childId, LdapDN newParentDn ) throws Exception
1751     {
1752         // Get the child and the new parent to be entries and Ids
1753         Long newParentId = getEntryId( newParentDn.toString() );
1754         Long oldParentId = getParentId( childId );
1755 
1756         /*
1757          * All aliases including and below oldChildDn, will be affected by
1758          * the move operation with respect to one and subtree userIndices since
1759          * their relationship to ancestors above oldChildDn will be 
1760          * destroyed.  For each alias below and including oldChildDn we will
1761          * drop the index tuples mapping ancestor ids above oldChildDn to the
1762          * respective target ids of the aliases.
1763          */
1764         dropMovedAliasIndices( oldChildDn );
1765 
1766         /*
1767          * Drop the old parent child relationship and add the new one
1768          * Set the new parent id for the child replacing the old parent id
1769          */
1770         oneLevelIdx.drop( oldParentId, childId );
1771         oneLevelIdx.add( newParentId, childId );
1772 
1773         updateSubLevelIndex( childId, oldParentId, newParentId );
1774         
1775         /*
1776          * Build the new user provided DN (updn) for the child using the child's
1777          * user provided RDN & the new parent's UPDN.  Basically add the child's
1778          * UpRdn String to the tail of the new parent's Updn Name.
1779          */
1780         LdapDN childUpdn = new LdapDN( getEntryUpdn( childId ) );
1781         String childRdn = childUpdn.get( childUpdn.size() - 1 );
1782         LdapDN newUpdn = new LdapDN( getEntryUpdn( newParentId ) );
1783         newUpdn.add( newUpdn.size(), childRdn );
1784 
1785         // Call the modifyDn operation with the new updn
1786         modifyDn( childId, newUpdn, true );
1787         
1788         return newUpdn;
1789     }
1790 
1791 
1792     /**
1793      * 
1794      * updates the SubLevel Index as part of a move operation.
1795      *
1796      * @param childId child id to be moved
1797      * @param oldParentId old parent's id
1798      * @param newParentId new parent's id
1799      * @throws Exception
1800      */
1801     private void updateSubLevelIndex( Long childId, Long oldParentId, Long newParentId ) throws Exception
1802     {
1803         Long tempId = oldParentId;
1804         List<Long> parentIds = new ArrayList<Long>();
1805 
1806         // find all the parents of the oldParentId
1807         while( tempId != 0 && tempId != 1 && tempId != null )
1808         {
1809           parentIds.add( tempId );
1810           tempId = getParentId( tempId );
1811         }
1812 
1813         // find all the children of the childId
1814         Cursor<IndexEntry<Long,E>> cursor = subLevelIdx.forwardCursor( childId );
1815         
1816         List<Long> childIds = new ArrayList<Long>();
1817         childIds.add( childId );
1818         
1819         while( cursor.next() )
1820         {
1821             childIds.add( cursor.get().getId() );
1822         }
1823         
1824         // detach the childId and all its children from oldParentId and all it parents excluding the root
1825         for( Long pid : parentIds )
1826         {
1827             for( Long cid: childIds )
1828             {
1829                 subLevelIdx.drop( pid, cid );
1830             }
1831         }
1832         
1833         parentIds.clear();
1834         tempId = newParentId;
1835 
1836         // find all the parents of the newParentId
1837         while( tempId != 0 && tempId != 1 && tempId != null )
1838         {
1839           parentIds.add( tempId );
1840           tempId = getParentId( tempId );
1841         }
1842         
1843         // attach the childId and all its children to newParentId and all it parents excluding the root
1844         for( Long id : parentIds )
1845         {
1846             for( Long cid: childIds )
1847             {
1848                 subLevelIdx.add( id, cid );
1849             }
1850         }
1851     }
1852     
1853     
1854     /**
1855      * For all aliases including and under the moved base, this method removes
1856      * one and subtree alias index tuples for old ancestors above the moved base
1857      * that will no longer be ancestors after the move.
1858      * 
1859      * @param movedBase the base at which the move occured - the moved node
1860      * @throws NamingException if system userIndices fail
1861      */
1862     private void dropMovedAliasIndices( final LdapDN movedBase ) throws Exception
1863     {
1864 //        // Find all the aliases from movedBase down
1865 //        IndexAssertion<Object,E> isBaseDescendant = new IndexAssertion<Object,E>()
1866 //        {
1867 //            public boolean assertCandidate( IndexEntry<Object,E> rec ) throws Exception
1868 //            {
1869 //                String dn = getEntryDn( rec.getId() );
1870 //                return dn.endsWith( movedBase.toString() );
1871 //            }
1872 //        };
1873 
1874         Long movedBaseId = getEntryId( movedBase.toString() );
1875 
1876         if ( aliasIdx.reverseLookup( movedBaseId ) != null )
1877         {
1878             dropAliasIndices( movedBaseId, movedBase );
1879         }
1880 
1881 //        throw new NotImplementedException( "Fix the code below this line" );
1882 
1883 //        NamingEnumeration<ForwardIndexEntry> aliases =
1884 //                new IndexAssertionEnumeration( aliasIdx.listIndices( movedBase.toString(), true ), isBaseDescendant );
1885 //
1886 //        while ( aliases.hasMore() )
1887 //        {
1888 //            ForwardIndexEntry entry = aliases.next();
1889 //            dropAliasIndices( (Long)entry.getId(), movedBase );
1890 //        }
1891     }
1892 
1893 
1894     /**
1895      * For the alias id all ancestor one and subtree alias tuples are moved 
1896      * above the moved base.
1897      * 
1898      * @param aliasId the id of the alias 
1899      * @param movedBase the base where the move occured
1900      * @throws Exception if userIndices fail
1901      */
1902     private void dropAliasIndices( Long aliasId, LdapDN movedBase ) throws Exception
1903     {
1904         String targetDn = aliasIdx.reverseLookup( aliasId );
1905         Long targetId = getEntryId( targetDn );
1906         String aliasDn = getEntryDn( aliasId );
1907 
1908         /*
1909          * Start droping index tuples with the first ancestor right above the 
1910          * moved base.  This is the first ancestor effected by the move.
1911          */
1912         LdapDN ancestorDn = ( LdapDN ) movedBase.getPrefix( 1 );
1913         Long ancestorId = getEntryId( ancestorDn.toString() );
1914 
1915         /*
1916          * We cannot just drop all tuples in the one level and subtree userIndices
1917          * linking baseIds to the targetId.  If more than one alias refers to
1918          * the target then droping all tuples with a value of targetId would
1919          * make all other aliases to the target inconsistent.
1920          * 
1921          * We need to walk up the path of alias ancestors right above the moved 
1922          * base until we reach the upSuffix, deleting each ( ancestorId,
1923          * targetId ) tuple in the subtree scope alias.  We only need to do 
1924          * this for the direct parent of the alias on the one level subtree if
1925          * the moved base is the alias.
1926          */
1927         if ( aliasDn.equals( movedBase.toString() ) )
1928         {
1929             oneAliasIdx.drop( ancestorId, targetId );
1930         }
1931 
1932         subAliasIdx.drop( ancestorId, targetId );
1933 
1934         while ( !ancestorDn.equals( upSuffix ) )
1935         {
1936             ancestorDn = ( LdapDN ) ancestorDn.getPrefix( 1 );
1937             ancestorId = getEntryId( ancestorDn.toString() );
1938 
1939             subAliasIdx.drop( ancestorId, targetId );
1940         }
1941     }
1942 
1943 
1944     public void initRegistries( Registries registries )
1945     {
1946         this.attributeTypeRegistry = registries.getAttributeTypeRegistry();
1947         this.oidRegistry = registries.getOidRegistry();
1948     }
1949 }