View Javadoc

1   /*
2    *   Copyright 2004 The Apache Software Foundation
3    *
4    *   Licensed under the Apache License, Version 2.0 (the "License");
5    *   you may not use this file except in compliance with the License.
6    *   You may obtain a copy of the License at
7    *
8    *       http://www.apache.org/licenses/LICENSE-2.0
9    *
10   *   Unless required by applicable law or agreed to in writing, software
11   *   distributed under the License is distributed on an "AS IS" BASIS,
12   *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   *   See the License for the specific language governing permissions and
14   *   limitations under the License.
15   *
16   */
17  package org.apache.ldap.server.db.jdbm;
18  
19  
20  import jdbm.RecordManager;
21  import jdbm.helper.MRU;
22  import jdbm.recman.BaseRecordManager;
23  import jdbm.recman.CacheRecordManager;
24  import org.apache.ldap.common.MultiException;
25  import org.apache.ldap.common.exception.LdapNameNotFoundException;
26  import org.apache.ldap.common.exception.LdapSchemaViolationException;
27  import org.apache.ldap.common.message.LockableAttributesImpl;
28  import org.apache.ldap.common.message.ResultCodeEnum;
29  import org.apache.ldap.common.name.LdapName;
30  import org.apache.ldap.common.schema.AttributeType;
31  import org.apache.ldap.common.schema.Normalizer;
32  import org.apache.ldap.common.util.NamespaceTools;
33  import org.apache.ldap.server.db.*;
34  
35  import javax.naming.Name;
36  import javax.naming.NamingEnumeration;
37  import javax.naming.NamingException;
38  import javax.naming.directory.Attribute;
39  import javax.naming.directory.Attributes;
40  import javax.naming.directory.DirContext;
41  import javax.naming.directory.ModificationItem;
42  import java.io.File;
43  import java.io.IOException;
44  import java.math.BigInteger;
45  import java.util.ArrayList;
46  import java.util.HashMap;
47  import java.util.Iterator;
48  import java.util.Map;
49  
50  
51  /***
52   * A Database implementation based on JDBM B+Tree implementation.
53   *
54   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
55   * @version $Rev: 164286 $
56   */
57  public class JdbmDatabase implements Database
58  {
59      /*** the JDBM record manager used by this database */
60      private final RecordManager recMan;
61      /*** the user provided suffix of this backend database */
62      private final Name upSuffix;
63      /*** the normalized suffix of this backend database */
64      private final Name normSuffix;
65      /*** the working directory to use for files */
66      private final String wkdir;
67      /*** the master table storing entries by primary key */
68      private final JdbmMasterTable master;
69      /*** a map of attribute names to user indices */
70      private final Map indices;
71      /*** a map of index names to system indices */
72      private final Map sysIndices;
73  
74      /*** the closed state of this Database */
75      private boolean closed = false;
76  
77      /*** the normalized distinguished name index */
78      private Index ndnIdx;
79      /*** the user provided distinguished name index */
80      private Index updnIdx;
81      /*** the attribute existance index */
82      private Index existanceIdx;
83      /*** the parent child relationship index */
84      private Index hierarchyIdx;
85      /*** the one level scope alias index */
86      private Index oneAliasIdx;
87      /*** the subtree scope alias index */
88      private Index subAliasIdx;
89      /*** a system index on aliasedObjectName attribute */
90      private Index aliasIdx;
91  
92  
93      // ------------------------------------------------------------------------
94      // C O N S T R U C T O R S
95      // ------------------------------------------------------------------------
96  
97  
98      /***
99       * Creates a Databased based on JDBM B+Trees.
100      *
101      * @param upSuffix the user provided suffix name
102      * @param normSuffix the normalized suffix name
103      * @param wkdirPath the path to the working directory where the db resides
104      * @throws NamingException if db cannot be created
105      */
106     public JdbmDatabase ( final Name upSuffix, final Name normSuffix, final String wkdirPath )
107         throws NamingException
108     {
109         this.upSuffix = upSuffix;
110         this.normSuffix = normSuffix;
111         this.wkdir = wkdirPath;
112 
113         try 
114         {
115             String path = wkdirPath + File.separator + "master";
116             BaseRecordManager base = new BaseRecordManager( path );
117             base.disableTransactions();
118             recMan = new CacheRecordManager( base, new MRU( 1000 ) );
119         } 
120         catch ( IOException e )
121         {
122             NamingException ne = new NamingException( 
123                 "Could not initialize RecordManager" );
124             ne.setRootCause( e );
125             throw ne;
126         }
127 
128         master = new JdbmMasterTable( recMan );
129         indices = new HashMap();
130         sysIndices = new HashMap();
131     }
132 
133 
134     // ------------------------------------------------------------------------
135     // I N D E X   M E T H O D S
136     // ------------------------------------------------------------------------
137 
138 
139     /***
140      * @see Database#addIndexOn(AttributeType)
141      */
142     public void addIndexOn( AttributeType spec ) throws NamingException
143     {
144         Index idx = new JdbmIndex( spec, wkdir );
145         indices.put( spec.getName().toLowerCase(), idx );
146     }
147 
148     
149     /***
150      * @see Database#getExistanceIndex()
151      */
152     public Index getExistanceIndex() 
153     {
154         return existanceIdx;
155     }
156     
157 
158     /***
159      * @see Database#setExistanceIndexOn(AttributeType)
160      */    
161     public void setExistanceIndexOn( AttributeType attrType ) throws NamingException
162     {
163         if ( existanceIdx != null )
164         {
165             NamingException e = new NamingException( "Index already set!" );
166             throw e;
167         }
168 
169         existanceIdx = new JdbmIndex( attrType, wkdir );
170         sysIndices.put( attrType.getName().toLowerCase(), existanceIdx );
171     }
172 
173     
174     /***
175      * @see org.apache.ldap.server.db.Database#getHierarchyIndex()
176      */
177     public Index getHierarchyIndex() 
178     {
179         return hierarchyIdx;
180     }
181     
182 
183     /***
184      * @see Database#setExistanceIndexOn(AttributeType)
185      */
186     public void setHierarchyIndexOn( AttributeType attrType ) throws NamingException
187     {
188         if ( hierarchyIdx != null )
189         {
190             NamingException e = new NamingException( "Index already set!" );
191             throw e;
192         }
193 
194         hierarchyIdx = new JdbmIndex( attrType, wkdir );
195         sysIndices.put( attrType.getName().toLowerCase(), hierarchyIdx );
196     }
197 
198     
199     /***
200      * @see Database#getAliasIndex()
201      */
202     public Index getAliasIndex()
203     {
204         return aliasIdx;    
205     }
206 
207 
208     /***
209      * @see Database#setAliasIndexOn(AttributeType)
210      */
211     public void setAliasIndexOn( AttributeType attrType ) throws NamingException
212     {
213         if ( aliasIdx != null )
214         {
215             NamingException e = new NamingException( "Index already set!" );
216             throw e;
217         }
218 
219         aliasIdx = new JdbmIndex( attrType, wkdir );
220         sysIndices.put( attrType.getName().toLowerCase(), aliasIdx );
221     }    
222     
223 
224     /***
225      * @see Database#getOneAliasIndex()
226      */
227     public Index getOneAliasIndex()
228     {
229         return oneAliasIdx;
230     }
231 
232 
233     /***
234      * @see org.apache.ldap.server.db.Database#setOneAliasIndexOn(AttributeType)
235      */
236     public void setOneAliasIndexOn( AttributeType attrType ) throws NamingException
237     {
238         if ( oneAliasIdx != null )
239         {
240             NamingException e = new NamingException( "Index already set!" );
241             throw e;
242         }
243 
244         oneAliasIdx = new JdbmIndex( attrType, wkdir );
245         sysIndices.put( attrType.getName().toLowerCase(), oneAliasIdx );
246     }
247 
248 
249     /***
250      * @see Database#getSubAliasIndex()
251      */
252     public Index getSubAliasIndex()
253     {
254         return subAliasIdx;
255     }
256 
257 
258     /***
259      * @see org.apache.ldap.server.db.Database#setSubAliasIndexOn(AttributeType)
260      */
261     public void setSubAliasIndexOn( AttributeType attrType ) throws NamingException
262     {
263         if ( subAliasIdx != null )
264         {
265             NamingException e = new NamingException( "Index already set!" );
266             throw e;
267         }
268 
269         subAliasIdx = new JdbmIndex( attrType, wkdir );
270         sysIndices.put( attrType.getName().toLowerCase(), subAliasIdx );
271     }
272 
273 
274     /***
275      * @see Database#getUpdnIndex()
276      */
277     public Index getUpdnIndex()
278     {
279         return updnIdx;
280     }
281 
282 
283     /***
284      * @see org.apache.ldap.server.db.Database#setUpdnIndexOn(AttributeType)
285      */
286     public void setUpdnIndexOn( AttributeType attrType ) throws NamingException
287     {
288         if ( updnIdx != null )
289         {
290             NamingException e = new NamingException( "Index already set!" );
291             throw e;
292         }
293 
294         updnIdx = new JdbmIndex( attrType, wkdir );
295         sysIndices.put( attrType.getName().toLowerCase(), updnIdx );
296     }
297 
298     
299     /***
300      * @see org.apache.ldap.server.db.Database#getNdnIndex()
301      */
302     public Index getNdnIndex() 
303     {
304         return ndnIdx;
305     }
306     
307 
308     /***
309      * @see org.apache.ldap.server.db.Database#setNdnIndexOn(AttributeType)
310      */
311     public void setNdnIndexOn( AttributeType attrType ) throws NamingException
312     {
313         if ( ndnIdx != null )
314         {
315             NamingException e = new NamingException( "Index already set!" );
316             throw e;
317         }
318 
319         ndnIdx = new JdbmIndex( attrType, wkdir );
320         sysIndices.put( attrType.getName().toLowerCase(), ndnIdx );
321     }
322 
323     
324     /***
325      * @see org.apache.ldap.server.db.Database#getUserIndices()
326      */
327     public Iterator getUserIndices()
328     {
329         return indices.keySet().iterator();
330     }
331 
332 
333     /***
334      * @see Database#getSystemIndices()
335      */
336     public Iterator getSystemIndices()
337     {
338         return sysIndices.keySet().iterator();
339     }
340 
341 
342     /***
343      * @see org.apache.ldap.server.db.Database#hasUserIndexOn(String)
344      */
345     public boolean hasUserIndexOn( String attribute )
346     {
347         return indices.containsKey( attribute ) ||
348             indices.containsKey( attribute.toLowerCase() );
349     }
350 
351 
352     /***
353      * @see org.apache.ldap.server.db.Database#hasSystemIndexOn(String)
354      */
355     public boolean hasSystemIndexOn( String attribute )
356     {
357         return sysIndices.containsKey( attribute ) ||
358             sysIndices.containsKey( attribute.toLowerCase() );
359     }
360 
361 
362     /***
363      * @todo replace lookups to use the OID instead of the name.  Also note
364      * that the OID registry can be used to go between names and oids.
365      * 
366      * @see org.apache.ldap.server.db.Database#getUserIndex(String)
367      */
368     public Index getUserIndex( String attribute ) throws IndexNotFoundException
369     {
370         String lowerCased = attribute.toLowerCase();
371 
372         if ( indices.containsKey( attribute ) ) 
373         {
374             return ( Index ) indices.get( attribute );
375         } 
376         else if ( indices.containsKey( lowerCased ) ) 
377         {
378             return ( Index ) indices.get( lowerCased );
379         } 
380         else 
381         {
382             throw new IndexNotFoundException( "An index on attribute " +
383                 attribute + " does not exist!" );
384         }
385     }
386     
387     
388     /***
389      * @todo replace lookups to use the OID instead of the name.  Also note
390      * that the OID registry can be used to go between names and oids.
391      * 
392      * @see Database#getEntryId(String)
393      */
394     public Index getSystemIndex( String indexName ) throws IndexNotFoundException
395     {
396         String lowerCased = indexName.toLowerCase();
397 
398         if ( sysIndices.containsKey( indexName ) ) 
399         {
400             return ( Index ) sysIndices.get( indexName );
401         } 
402         else if ( sysIndices.containsKey( lowerCased ) ) 
403         {
404             return ( Index ) sysIndices.get( lowerCased );
405         } 
406         else 
407         {
408             throw new IndexNotFoundException( "A system index by the name of " +
409                 indexName + " does not exist!" );
410         }
411     }
412 
413 
414     /***
415      * @see org.apache.ldap.server.db.Database#getEntryId(String)
416      */
417     public BigInteger getEntryId( String dn ) throws NamingException
418     {
419         return ndnIdx.forwardLookup( dn );
420     }
421 
422 
423     /***
424      * @see org.apache.ldap.server.db.Database#getEntryDn(java.math.BigInteger)
425      */
426     public String getEntryDn( BigInteger id ) throws NamingException
427     {
428         return ( String ) ndnIdx.reverseLookup( id );
429     }
430 
431 
432     /***
433      * @see Database#getParentId(String)
434      */
435     public BigInteger getParentId( String dn ) throws NamingException
436     {
437         BigInteger childId = ndnIdx.forwardLookup( dn );
438         return ( BigInteger ) hierarchyIdx.reverseLookup( childId );
439     }
440 
441 
442     /***
443      * @see Database#getParentId(BigInteger)
444      */
445     public BigInteger getParentId( BigInteger childId ) throws NamingException
446     {
447         return ( BigInteger ) hierarchyIdx.reverseLookup( childId );
448     }
449     
450     
451     /***
452      * @see org.apache.ldap.server.db.Database#getEntryUpdn(BigInteger)
453      */
454     public String getEntryUpdn( BigInteger id ) throws NamingException
455     {
456         return ( String ) updnIdx.reverseLookup( id );
457     }
458 
459 
460     /***
461      * @see org.apache.ldap.server.db.Database#getEntryUpdn(String)
462      */
463     public String getEntryUpdn( String dn ) throws NamingException
464     {
465         BigInteger id = ndnIdx.forwardLookup( dn );
466         return ( String ) updnIdx.reverseLookup( id );
467     }
468 
469 
470     /***
471      * @see org.apache.ldap.server.db.Database#count()
472      */
473     public int count() throws NamingException
474     {
475         return master.count();
476     }
477     
478     
479     /***
480      * Removes the index entries for an alias before the entry is deleted from
481      * the master table.
482      * 
483      * @todo Optimize this by walking the hierarchy index instead of the name 
484      * @param aliasId the id of the alias entry in the master table
485      * @throws NamingException if we cannot delete the indices
486      */
487     private void dropAliasIndices( BigInteger aliasId ) throws NamingException
488     {
489         String targetDn = ( String ) aliasIdx.reverseLookup( aliasId );
490         BigInteger targetId = getEntryId( targetDn );
491         String aliasDn = getEntryDn( aliasId );
492         Name ancestorDn = new LdapName( aliasDn ).getSuffix( 1 );
493         BigInteger ancestorId = getEntryId( ancestorDn.toString() );
494         
495         /*
496          * We cannot just drop all tuples in the one level and subtree indices
497          * linking baseIds to the targetId.  If more than one alias refers to
498          * the target then droping all tuples with a value of targetId would
499          * make all other aliases to the target inconsistent.
500          * 
501          * We need to walk up the path of alias ancestors until we reach the 
502          * upSuffix, deleting each ( ancestorId, targetId ) tuple in the
503          * subtree scope alias.  We only need to do this for the direct parent
504          * of the alias on the one level subtree.
505          */
506         oneAliasIdx.drop( ancestorId, targetId );
507         subAliasIdx.drop( ancestorId, targetId );
508         
509         while ( ! ancestorDn.equals( upSuffix ) )
510         {
511             ancestorDn = ancestorDn.getSuffix( 1 );
512             ancestorId = getEntryId( ancestorDn.toString() );
513             
514             subAliasIdx.drop( ancestorId, targetId );
515         }    
516 
517         // Drops all alias tuples pointing to the id of the alias to be deleted
518         aliasIdx.drop( aliasId );
519     }
520     
521     
522     /***
523      * Adds indices for an aliasEntry to be added to the database while checking
524      * for constrained alias constructs like alias cycles and chaining.
525      * 
526      * @param aliasDn normalized distinguished name for the alias entry
527      * @param aliasTarget the user provided aliased entry dn as a string
528      * @param aliasId the id of alias entry to add
529      * @throws NamingException if index addition fails, of the alias is not 
530      * allowed due to chaining or cycle formation.
531      */
532     private void addAliasIndices( BigInteger aliasId, Name aliasDn, 
533         String aliasTarget ) throws NamingException
534     {
535         Name targetDn = null;            // Name value of aliasedObjectName
536         BigInteger targetId = null;      // Id of the aliasedObjectName
537         Normalizer normalizer = null;    // Temporary handle for Dn's
538         Name ancestorDn = null;          // Name of an alias entry relative
539         BigInteger ancestorId = null;    // Id of an alias entry relative
540 
541         // Access aliasedObjectName, normalize it and generate the Name 
542         normalizer = oneAliasIdx.getAttribute().getEquality().getNormalizer();
543         targetDn = new LdapName( ( String ) normalizer.normalize( aliasTarget ) );
544            
545         /*
546          * Check For Cycles
547          * 
548          * Before wasting time to lookup more values we check using the target
549          * dn to see if we have the possible formation of an alias cycle.  This
550          * happens when the alias refers back to a target that is also a 
551          * relative of the alias entry.  For detection we test if the aliased
552          * entry Dn starts with the target Dn.  If it does then we know the 
553          * aliased target is a relative and we have a perspecitive cycle.
554          */ 
555         if ( aliasDn.startsWith( targetDn ) )
556         {
557             if ( aliasDn.equals( targetDn ) )
558             {
559                 throw new NamingException( "[36] aliasDereferencingProblem - " 
560                     + "attempt to create alias to itself." );
561             }
562             
563             throw new NamingException( "[36] aliasDereferencingProblem - " 
564                 + "attempt to create alias with cycle to relative " 
565                 + aliasTarget + " not allowed from descendent alias " 
566                 + aliasDn );
567         }
568             
569         /*
570          * Check For Aliases External To Naming Context
571          * 
572          * id may be null but the alias may be to a valid entry in 
573          * another namingContext.  Such aliases are not allowed and we
574          * need to point it out to the user instead of saying the target
575          * does not exist when it potentially could outside of this upSuffix.
576          */
577         if ( ! targetDn.startsWith( upSuffix ) )
578         {
579             // Complain specifically about aliases to outside naming contexts
580             throw new NamingException( "[36] aliasDereferencingProblem -"
581                 + " the alias points to an entry outside of the " + upSuffix
582                 + " namingContext to an object whose existance cannot be"
583                 + " determined." );
584         }
585 
586         // L O O K U P   T A R G E T   I D
587         targetId = ndnIdx.forwardLookup( targetDn.toString() );
588 
589         /*
590          * Check For Target Existance
591          * 
592          * We do not allow the creation of inconsistant aliases.  Aliases should
593          * not be broken links.  If the target does not exist we start screaming
594          */
595         if ( null == targetId )
596         {
597             // Complain about target not existing
598             throw new NamingException( "[33] aliasProblem - " 
599                 + "the alias when dereferenced would not name a known object "
600                 + "the aliasedObjectName must be set to a valid existing "
601                 + "entry." );
602         }
603         
604         /*
605          * Detect Direct Alias Chain Creation
606          * 
607          * Rather than resusitate the target to test if it is an alias and fail
608          * due to chaing creation we use the alias index to determine if the
609          * target is an alias.  Hence if the alias we are about to create points
610          * to another alias as its target in the aliasedObjectName attribute, 
611          * then we have a situation where an alias chain is being created.  
612          * Alias chaining is not allowed so we throw and exception. 
613          */
614         if ( null != aliasIdx.reverseLookup( targetId ) )
615         {
616             // Complain about illegal alias chain
617             throw new NamingException( "[36] aliasDereferencingProblem -" 
618                 + " the alias points to another alias.  Alias chaining is" 
619                 + " not supported by this backend." );
620         }
621         
622         // Add the alias to the simple alias index
623         aliasIdx.add( aliasTarget, aliasId );
624         
625         /*
626          * Handle One Level Scope Alias Index
627          * 
628          * The first relative is special with respect to the one level alias
629          * index.  If the target is not a sibling of the alias then we add the
630          * index entry maping the parent's id to the aliased target id.
631          */
632         ancestorDn = aliasDn.getSuffix( 1 );
633         ancestorId = getEntryId( ancestorDn.toString() );
634         
635         if ( ! NamespaceTools.isSibling( targetDn, aliasDn ) )
636         {
637             oneAliasIdx.add( ancestorId, targetId );
638         }
639 
640         /*
641          * Handle Sub Level Scope Alias Index
642          * 
643          * Walk the list of relatives from the parents up to the upSuffix, testing
644          * to see if the alias' target is a descendant of the relative.  If the
645          * alias target is not a descentant of the relative it extends the scope
646          * and is added to the sub tree scope alias index.  The upSuffix node is
647          * ignored since everything is under its scope.  The first loop 
648          * iteration shall handle the parents.
649          */
650         while ( ! ancestorDn.equals( upSuffix ) && null != ancestorId )
651         {
652             if ( ! NamespaceTools.isDescendant( ancestorDn, targetDn ) )
653             {
654                 subAliasIdx.add( ancestorId, targetId );
655             }
656             
657             ancestorDn = ancestorDn.getSuffix( 1 );
658             ancestorId = getEntryId( ancestorDn.toString() );
659         }        
660     }
661 
662 
663     /***
664      * @see Database#add(String,Name,Attributes)
665      */
666     public void add( String updn, Name dn, Attributes entry ) throws NamingException
667     {
668         BigInteger id;
669         BigInteger parentId = null;
670 
671         id = master.getNextId();
672 
673         //
674         // Suffix entry cannot have a parent since it is the root so it is 
675         // capped off using the zero value which no entry can have since 
676         // entry sequences start at 1.
677         //
678         
679         if ( dn.equals( normSuffix ) )
680         {
681             parentId = BigInteger.ZERO;
682         }
683         else 
684         {
685             parentId = getEntryId( dn.getSuffix( 1 ).toString() );
686         }
687 
688         // don't keep going if we cannot find the parent Id
689         if ( parentId == null )
690         {
691             throw new LdapNameNotFoundException( "Id for parent '" + dn.getSuffix( 1 ).toString() + "' not found!" );
692         }
693 
694         Attribute objectClass = entry.get( "objectClass" );
695 
696         if ( objectClass == null )
697         {
698             String msg = "Entry " + updn + " contains no objectClass attribute: " + entry;
699 
700             throw new LdapSchemaViolationException( msg, ResultCodeEnum.OBJECTCLASSVIOLATION );
701         }
702 
703         // Start adding the system indices
704         // Why bother doing a lookup if this is not an alias.
705 
706         if ( entry.get( "objectClass" ).contains( ALIAS_OBJECT ) )
707         {
708             addAliasIndices( id, dn, ( String ) entry.get( ALIAS_ATTRIBUTE ).get() );
709         }
710         
711         ndnIdx.add( dn.toString(), id );
712         updnIdx.add( updn, id );
713         hierarchyIdx.add( parentId, id );
714         
715         // Now work on the user defined indices
716         NamingEnumeration list = entry.getIDs();
717         while ( list.hasMore() ) 
718         {
719             String attribute = ( String ) list.next();
720             
721             if ( hasUserIndexOn( attribute ) ) 
722             {
723                 Index idx = getUserIndex( attribute );
724                 NamingEnumeration values = entry.get( attribute ).getAll();
725                 
726                 while ( values.hasMore() ) 
727                 {
728                     idx.add( values.next(), id );
729                 }
730 
731                 // Adds only those attributes that are indexed
732                 existanceIdx.add( attribute.toLowerCase(), id );
733             }
734         }
735 
736         master.put( entry, id );
737     }
738 
739 
740     /***
741      * @see Database#lookup(BigInteger)
742      */
743     public Attributes lookup( BigInteger id ) throws NamingException
744     {
745         return master.get( id );
746     }
747 
748 
749     /***
750      * @see org.apache.ldap.server.db.Database#delete(BigInteger)
751      */
752     public void delete( BigInteger id ) throws  NamingException
753     {
754         Attributes entry = lookup( id );
755         BigInteger parentId = getParentId( id );
756         NamingEnumeration attrs = entry.getIDs();
757         
758         if ( entry.get( "objectClass" ).contains( ALIAS_OBJECT ) )
759         {
760             dropAliasIndices( id );
761         }
762 
763         ndnIdx.drop( id );
764         updnIdx.drop( id );
765         hierarchyIdx.drop( id );
766         
767         // Remove parent's reference to entry only if entry is not the upSuffix
768         if ( ! parentId.equals( BigInteger.ZERO ) )
769         {
770             hierarchyIdx.drop( parentId, id );
771         }
772         
773         while ( attrs.hasMore() ) 
774         {
775             String attr = ( ( String ) attrs.next() );
776 
777             if ( hasUserIndexOn( attr ) )
778             {
779                 Index index = getUserIndex( attr );
780                 NamingEnumeration values = entry.get( attr ).getAll();
781                 
782                 while ( values.hasMore() )
783                 {
784                     index.drop( values.next(), id );
785                 }
786 
787                 existanceIdx.drop( attr.toLowerCase(), id );
788             }
789         }
790 
791         master.delete( id );
792     }
793 
794 
795     /***
796      * @see Database#list(java.math.BigInteger)
797      */
798     public NamingEnumeration list( BigInteger id ) throws  NamingException
799     {
800         return hierarchyIdx.listIndices( id );
801     }
802 
803 
804     /***
805      * @see org.apache.ldap.server.db.Database#getChildCount(java.math.BigInteger)
806      */
807     public int getChildCount( BigInteger id ) throws NamingException
808     {
809         return hierarchyIdx.count( id );
810     }
811 
812 
813     /***
814      * @see org.apache.ldap.server.db.Database#getSuffix()
815      */
816     public Name getSuffix()
817     {
818         return upSuffix;
819     }
820 
821 
822     /***
823      * @see org.apache.ldap.server.db.Database#getSuffixEntry()
824      */
825     public Attributes getSuffixEntry() throws NamingException
826     {
827         BigInteger id = getEntryId( upSuffix.toString() );
828 
829         if ( null == id )
830         {
831             return null;
832         }
833 
834         return lookup( id );
835     }
836 
837 
838     /***
839      * @see org.apache.ldap.server.db.Database#sync()
840      */
841     public void sync() throws NamingException
842     {
843         ArrayList array = new ArrayList();
844         array.addAll( indices.values() );
845         array.add( ndnIdx );
846         array.add( updnIdx );
847         array.add( aliasIdx );
848         array.add( oneAliasIdx );
849         array.add( subAliasIdx );
850         array.add( hierarchyIdx );
851         array.add( existanceIdx );
852         
853         Iterator list = array.iterator();
854         MultiException rootCause = null;
855 
856         // Sync all user defined indices
857         while ( list.hasNext() ) 
858         {
859             Index idx = ( Index ) list.next();
860 
861             try 
862             {
863                 idx.sync();
864             } 
865             catch ( Throwable t ) 
866             {
867                 t.printStackTrace();
868                 if ( null == rootCause ) 
869                 {
870                     rootCause = new MultiException();
871                 }
872                 
873                 rootCause.addThrowable( t );
874             }
875         }
876         
877         try 
878         {
879             master.sync();
880             recMan.commit();
881         }
882         catch ( Throwable t ) 
883         {
884             t.printStackTrace();
885             if ( null == rootCause ) 
886             {
887                 rootCause = new MultiException();
888             }
889                 
890             rootCause.addThrowable( t );
891         }
892 
893         if ( null != rootCause )
894         {
895             NamingException ne = new NamingException( "Failed to sync all" );
896             ne.setRootCause( rootCause );
897             throw ne;
898         }        
899     }
900 
901 
902     /***
903      * @see org.apache.ldap.server.db.Database#close()
904      */
905     public synchronized void close() throws NamingException
906     {
907         if ( closed )
908         {
909             return;
910         }
911 
912         ArrayList array = new ArrayList();
913         array.addAll( indices.values() );
914         
915         if ( null != ndnIdx )
916         {
917             array.add( ndnIdx );
918         }
919         
920         if ( null != updnIdx )
921         {
922             array.add( updnIdx );
923         }
924 
925         if ( null != aliasIdx )
926         {
927             array.add( aliasIdx );
928         }
929 
930         if ( null != oneAliasIdx )
931         {
932             array.add( oneAliasIdx );
933         }
934 
935         if ( null != subAliasIdx )
936         {
937             array.add( subAliasIdx );
938         }
939 
940         if ( null != hierarchyIdx )
941         {
942             array.add( hierarchyIdx );
943         }
944 
945         if ( null != existanceIdx )
946         {
947             array.add( existanceIdx );
948         }
949         
950         Iterator list = array.iterator();
951         MultiException rootCause = null;
952         
953         while ( list.hasNext() ) 
954         {
955             Index index = ( Index ) list.next();
956 
957             try 
958             {
959                index.close();
960             } 
961             catch ( Throwable t ) 
962             {
963                 if ( null == rootCause ) 
964                 {
965                     rootCause = new MultiException();
966                 }
967                 
968                 rootCause.addThrowable( t );
969             }
970         }
971 
972         try 
973         {
974             master.close();
975         } 
976         catch ( Throwable t ) 
977         {
978             if ( null == rootCause ) 
979             {
980                 rootCause = new MultiException();
981             }
982                 
983             rootCause.addThrowable( t );
984         }
985 
986         try 
987         {
988             recMan.close();
989         } 
990         catch ( Throwable t ) 
991         {
992             if ( null == rootCause ) 
993             {
994                 rootCause = new MultiException();
995             }
996                 
997             rootCause.addThrowable( t );
998         }
999 
1000         closed = true;
1001 
1002         if ( null != rootCause )
1003         {
1004             NamingException ne = new NamingException( "Failed to close all" );
1005             ne.setRootCause( rootCause );
1006             throw ne;
1007         }        
1008     }
1009 
1010 
1011     /***
1012      * @see org.apache.ldap.server.db.Database#isClosed()
1013      */
1014     public boolean isClosed()
1015     {
1016         return closed;
1017     }
1018 
1019 
1020     /***
1021      * @see org.apache.ldap.server.db.Database#setProperty(String, String)
1022      */
1023     public void setProperty( String propertyName, String propertyValue )
1024         throws NamingException
1025     {
1026         master.setProperty( propertyName, propertyValue );
1027     }
1028 
1029 
1030     /***
1031      * @see org.apache.ldap.server.db.Database#getProperty(String)
1032      */
1033     public String getProperty( String propertyName ) throws NamingException
1034     {
1035         return master.getProperty( propertyName );
1036     }
1037 
1038 
1039     /***
1040      * @see Database#getIndices(java.math.BigInteger)
1041      */
1042     public Attributes getIndices( BigInteger id ) throws  NamingException
1043     {
1044         Attributes attributes = new LockableAttributesImpl();
1045 
1046         // Get the distinguishedName to id mapping
1047         attributes.put( "_nDn", getEntryDn( id ) );
1048         attributes.put( "_upDn", getEntryUpdn( id ) );
1049         attributes.put( "_parent", getParentId( id ) );
1050 
1051         // Get all standard index attribute to value mappings
1052         Iterator idxList = this.indices.values().iterator();
1053         while ( idxList.hasNext() )
1054         {
1055             Index index = ( Index ) idxList.next();
1056             NamingEnumeration list = index.listReverseIndices( id );
1057             while ( list.hasMore() ) 
1058             {
1059                 IndexRecord rec = ( IndexRecord ) list.next();
1060                 Object val = rec.getIndexKey();
1061                 attributes.put( index.getAttribute().getName(), val );
1062             }
1063         }
1064 
1065         // Get all existance mappings for this id creating a special key
1066         // that looks like so 'existance[attribute]' and the value is set to id
1067         NamingEnumeration list = existanceIdx.listReverseIndices( id );
1068         StringBuffer val = new StringBuffer();
1069         while ( list.hasMore() ) 
1070         {
1071             IndexRecord rec = ( IndexRecord ) list.next();
1072             val.append( "_existance[" ); 
1073             val.append( rec.getIndexKey() );
1074             val.append( "]" );
1075             attributes.put( val.toString(), rec.getEntryId() );
1076             val.setLength( 0 );
1077         }
1078 
1079         // Get all parent child mappings for this entry as the parent using the
1080         // key 'child' with many entries following it.
1081         list = hierarchyIdx.listIndices( id );
1082         while ( list.hasMore() ) 
1083         {
1084             IndexRecord rec = ( IndexRecord ) list.next();
1085             attributes.put( "_child", rec.getEntryId() );
1086         }
1087 
1088         return attributes;
1089     }
1090 
1091 
1092     /***
1093      * Adds a set of attribute values while affecting the appropriate indices. 
1094      * The entry is not persisted: it is only changed in anticipation for a put 
1095      * into the master table.
1096      *
1097      * @param id the primary key of the entry
1098      * @param entry the entry to alter
1099      * @param mods the attribute and values to add 
1100      * @throws NamingException if index alteration or attribute addition
1101      * fails.
1102      */
1103     private void add( BigInteger id, Attributes entry, Attribute mods )
1104         throws NamingException 
1105     {
1106         if ( hasUserIndexOn( mods.getID() ) )
1107         {
1108             Index idx = getUserIndex( mods.getID() );
1109             idx.add( mods, id );
1110 
1111             // If the attr didn't exist for this id add it to existance index
1112             if ( ! existanceIdx.hasValue( mods.getID(), id ) )
1113             {
1114                 idx.add( mods.getID(), id );
1115             }
1116         }
1117         
1118         entry.put( mods );
1119 
1120         if ( mods.getID().equals( ALIAS_ATTRIBUTE ) )
1121         {
1122             String ndnStr = ( String ) ndnIdx.reverseLookup( id );
1123             addAliasIndices( id, new LdapName( ndnStr ), 
1124                 ( String ) mods.get() );
1125         }
1126     }
1127     
1128     
1129     /***
1130      * Completely removes the set of values for an attribute having the values 
1131      * supplied while affecting the appropriate indices.  The entry is not 
1132      * persisted: it is only changed in anticipation for a put into the master 
1133      * table.  Note that an empty attribute w/o values will remove all the 
1134      * values within the entry where as an attribute w/ values will remove those
1135      * attribute values it contains.
1136      *
1137      * @param id the primary key of the entry
1138      * @param entry the entry to alter
1139      * @param mods the attribute and its values to delete
1140      * @throws NamingException if index alteration or attribute modification 
1141      * fails.
1142      */
1143     private void remove( BigInteger id, Attributes entry, Attribute mods )
1144         throws NamingException
1145     {
1146         if ( hasUserIndexOn( mods.getID() ) )
1147         {
1148             Index idx = getUserIndex( mods.getID() );
1149             idx.drop( mods, id );
1150     
1151             /* 
1152              * If no attribute values exist for this entryId in the index then
1153              * we remove the existance index entry for the removed attribute.
1154              */
1155             if ( null == idx.reverseLookup( id ) )
1156             {
1157                 existanceIdx.drop( mods.getID(), id );
1158             }
1159         }
1160 
1161         /*
1162          * If there are no attribute values in the modifications then this 
1163          * implies the compelete removal of the attribute from the entry. Else
1164          * we remove individual attribute values from the entry in mods one 
1165          * at a time.
1166          */
1167         if ( mods.size() == 0 )
1168         {
1169             entry.remove( mods.getID() );
1170         }
1171         else
1172         {
1173             Attribute entryAttr = entry.get( mods.getID() );
1174             NamingEnumeration values = mods.getAll();
1175             while ( values.hasMore() ) 
1176             {
1177                 entryAttr.remove( values.next() );
1178             }
1179         }
1180 
1181         // Aliases->single valued comp/partial attr removal is not relevant here
1182         if ( mods.getID().equals( ALIAS_ATTRIBUTE ) )
1183         {
1184             dropAliasIndices( id );
1185         }
1186     }
1187 
1188 
1189     /***
1190      * Completely replaces the existing set of values for an attribute with the
1191      * modified values supplied affecting the appropriate indices.  The entry
1192      * is not persisted: it is only changed in anticipation for a put into the
1193      * master table.
1194      *
1195      * @param id the primary key of the entry
1196      * @param entry the entry to alter
1197      * @param mods the replacement attribute and values
1198      * @throws NamingException if index alteration or attribute modification 
1199      * fails.
1200      */
1201     private void replace( BigInteger id, Attributes entry, Attribute mods )
1202         throws NamingException
1203     {
1204         if ( hasUserIndexOn( mods.getID() ) )
1205         {
1206             Index idx = getUserIndex( mods.getID() );
1207             
1208             // Drop all existing attribute value index entries and add new ones
1209             idx.drop( id );
1210             idx.add( mods, id );
1211     
1212             /* 
1213              * If no attribute values exist for this entryId in the index then
1214              * we remove the existance index entry for the removed attribute.
1215              */
1216             if ( null == idx.reverseLookup( id ) )
1217             {
1218                 existanceIdx.drop( mods.getID(), id );
1219             }
1220         }
1221 
1222         if ( mods.getID().equals( ALIAS_ATTRIBUTE ) )
1223         {
1224             dropAliasIndices( id );
1225         }
1226         
1227         // Automatically replaces old attributes with new modified ones
1228         entry.put( mods );
1229         
1230         if ( mods.getID().equals( ALIAS_ATTRIBUTE ) )
1231         {
1232             String ndnStr = ( String ) ndnIdx.reverseLookup( id );
1233             addAliasIndices( id, new LdapName( ndnStr ), 
1234                 ( String ) mods.get() );
1235         }
1236     }
1237 
1238 
1239     /***
1240      * @see org.apache.ldap.server.db.Database#modify(javax.naming.Name, int,
1241      * javax.naming.directory.Attributes)
1242      */
1243     public void modify( Name dn, int modOp, Attributes mods ) throws NamingException
1244     {
1245         NamingEnumeration attrs = null;
1246         BigInteger id = getEntryId( dn.toString() );
1247         Attributes entry = master.get( id );
1248         
1249         switch ( modOp )
1250         {
1251             case( DirContext.ADD_ATTRIBUTE ):
1252                 attrs = mods.getIDs();
1253                 
1254                 while ( attrs.hasMore() )
1255                 {
1256                     String attrId = ( String ) attrs.next();
1257                     Attribute attr = mods.get( attrId );
1258                     add( id, entry, attr );
1259                 }
1260                 
1261                 break;
1262             case( DirContext.REMOVE_ATTRIBUTE ):
1263                 attrs = mods.getIDs();
1264                 
1265                 while ( attrs.hasMore() )
1266                 {
1267                     String attrId = ( String ) attrs.next();
1268                     Attribute attr = mods.get( attrId );
1269                     remove( id, entry, attr );
1270                 }
1271                 
1272                 break;
1273             case( DirContext.REPLACE_ATTRIBUTE ):
1274                 attrs = mods.getIDs();
1275                 
1276                 while ( attrs.hasMore() )
1277                 {
1278                     String attrId = ( String ) attrs.next();
1279                     Attribute attr = mods.get( attrId );
1280                     replace( id, entry, attr );
1281                 }
1282                 
1283                 break;
1284             default:
1285                 throw new NamingException( 
1286                     "Unidentified modification operation" );
1287         }
1288         
1289         master.put( entry, id );
1290     }
1291     
1292 
1293     /***
1294      * @see Database#modify(javax.naming.Name,
1295      * javax.naming.directory.ModificationItem[])
1296      */
1297     public void modify( Name dn, ModificationItem [] mods ) throws NamingException
1298     {
1299         BigInteger id = getEntryId( dn.toString() );
1300         Attributes entry = master.get( id );
1301         
1302         for ( int ii = 0; ii < mods.length; ii++ )
1303         {
1304             Attribute attrMods = mods[ii].getAttribute();
1305 
1306             switch ( mods[ ii ].getModificationOp() )
1307             {
1308                 case( DirContext.ADD_ATTRIBUTE ):
1309                     add( id, entry, attrMods );
1310                     break;
1311                 case( DirContext.REMOVE_ATTRIBUTE ):
1312                     remove( id, entry, attrMods );
1313                     break;
1314                 case( DirContext.REPLACE_ATTRIBUTE ):
1315                     replace( id, entry, attrMods );
1316                     break;
1317                 default:
1318                     throw new NamingException( 
1319                         "Unidentified modification operation" );
1320             }
1321         }
1322         
1323         master.put( entry, id );
1324     }
1325 
1326 
1327     /***
1328      * Changes the relative distinuished name of an entry specified by a 
1329      * distinguished name with the optional removal of the old Rdn attribute
1330      * value from the entry.  Name changes propagate down as dn changes to the 
1331      * descendants of the entry where the Rdn changed. 
1332      * 
1333      * An Rdn change operation does not change parent child relationships.  It 
1334      * merely propagates a name change at a point in the DIT where the Rdn is 
1335      * changed. The change propagates down the subtree rooted at the 
1336      * distinguished name specified.
1337      *
1338      * @param dn the normalized distinguished name of the entry to alter
1339      * @param newRdn the new Rdn to set
1340      * @param deleteOldRdn whether or not to remove the old Rdn attr/val
1341      * @throws NamingException if there are any errors propagating the name 
1342      *        changes.
1343      * @see org.apache.ldap.server.db.Database#modifyRdn(javax.naming.Name,
1344      * String, boolean)
1345      */
1346     public void modifyRdn( Name dn, String newRdn, boolean deleteOldRdn )
1347         throws NamingException
1348     {
1349         String newRdnAttr = NamespaceTools.getRdnAttribute( newRdn );
1350         String newRdnValue = NamespaceTools.getRdnValue( newRdn );
1351         BigInteger id = getEntryId( dn.toString() );
1352         Attributes entry = lookup( id );
1353         Name updn = new LdapName( getEntryUpdn( id ) );
1354 
1355         /* 
1356          * H A N D L E   N E W   R D N
1357          * ====================================================================
1358          * Add the new Rdn attribute to the entry.  If an index exists on the 
1359          * new Rdn attribute we add the index for this attribute value pair.
1360          * Also we make sure that the existance index shows the existance of the
1361          * new Rdn attribute within this entry.
1362          */
1363         
1364         entry.put( newRdnAttr, newRdnValue );
1365         
1366         if ( hasUserIndexOn( newRdnAttr ) )
1367         {
1368             Index idx = getUserIndex( newRdnAttr );
1369             idx.add( newRdnValue, id );
1370             
1371             // Make sure the altered entry shows the existance of the new attrib
1372             if ( ! existanceIdx.hasValue( newRdnAttr, id ) )
1373             {
1374                 existanceIdx.add( newRdnAttr, id );
1375             }
1376         }
1377 
1378         /*
1379          * H A N D L E   O L D   R D N
1380          * ====================================================================
1381          * If the old Rdn is to be removed we need to get the attribute and 
1382          * value for it.  Keep in mind the old Rdn need not be based on the 
1383          * same Rdn as the new one.  We remove the Rdn value from the entry
1384          * and remove the value/id tuple from the index on the old Rdn attr
1385          * if any.  We also test if the delete of the old Rdn index tuple 
1386          * removed all the attribute values of the old Rdn using a reverse
1387          * lookup.  If so that means we blew away the last value of the old 
1388          * Rdn attribute.  In this case we need to remove the attrName/id 
1389          * tuple from the existance index.
1390          */
1391 
1392         if ( deleteOldRdn )
1393         {
1394             String oldRdn = updn.get( updn.size() - 1 );
1395             String oldRdnAttr = NamespaceTools.getRdnAttribute( oldRdn );
1396             String oldRdnValue = NamespaceTools.getRdnValue( oldRdn );
1397             
1398             entry.get( oldRdnAttr ).remove( oldRdnValue );
1399 
1400             if ( hasUserIndexOn( oldRdnAttr ) )
1401             {
1402                 Index idx = getUserIndex( oldRdnAttr );
1403                 idx.drop( oldRdnValue, id );
1404                 
1405                 /*
1406                  * If there is no value for id in this index due to our
1407                  * drop above we remove the oldRdnAttr from the existance idx
1408                  */
1409                 if ( null == idx.reverseLookup( id ) )
1410                 {
1411                     existanceIdx.drop( oldRdnAttr, id );
1412                 }
1413             }
1414         }
1415         
1416         /*
1417          * H A N D L E   D N   C H A N G E
1418          * ====================================================================
1419          * 1) Build the new user defined distinguished name
1420          *      - clone / copy old updn
1421          *      - remove old upRdn from copy
1422          *      - add the new upRdn to the copy
1423          * 2) Make call to recursive modifyDn method to change the names of the
1424          *    entry and its descendants
1425          */
1426 
1427         Name newUpdn = ( Name ) updn.clone();      // copy da old updn
1428         newUpdn.remove( newUpdn.size() - 1 );      // remove old upRdn
1429         newUpdn.add( newUpdn.size(), newRdn );   // add da new upRdn
1430         modifyDn( id, newUpdn, false );            // propagate dn changes
1431     }
1432     
1433     
1434     /*
1435      * The move operation severs a child from a parent creating a new parent
1436      * child relationship.  As a consequence the relationships between the 
1437      * old ancestors of the child and its descendants change.  A descendant is
1438      *   
1439      */
1440 
1441     /***
1442      * Recursively modifies the distinguished name of an entry and the names of
1443      * its descendants calling itself in the recursion.
1444      *
1445      * @param id the primary key of the entry
1446      * @param updn User provided distinguished name to set as the new DN
1447      * @param isMove whether or not the name change is due to a move operation
1448      * which affects alias indices.
1449      * @throws NamingException if something goes wrong
1450      */
1451     private void modifyDn( BigInteger id, Name updn, boolean isMove )
1452         throws  NamingException
1453     {
1454         String aliasTarget = null;
1455 
1456         // Now we can handle the appropriate name indices for all cases
1457         ndnIdx.drop( id );
1458         ndnIdx.add( ndnIdx.getNormalized( updn.toString() ), id );
1459         
1460         updnIdx.drop( id );
1461         updnIdx.add( updn.toString(), id );
1462         
1463         /* 
1464          * Read Alias Index Tuples
1465          * 
1466          * If this is a name change due to a move operation then the one and
1467          * subtree indices for aliases were purged before the aliases were 
1468          * moved.  Now we must add them for each alias entry we have moved.  
1469          * 
1470          * aliasTarget is used as a marker to tell us if we're moving an 
1471          * alias.  If it is null then the moved entry is not an alias.
1472          */
1473         if ( isMove ) 
1474         {
1475             aliasTarget = ( String ) aliasIdx.reverseLookup( id );
1476     
1477             if ( null != aliasTarget )
1478             {
1479                 addAliasIndices( id, new LdapName( getEntryDn( id ) ), 
1480                     aliasTarget );
1481             }
1482         }
1483         
1484         NamingEnumeration children = list( id );
1485         while ( children.hasMore() ) 
1486         {
1487             // Get the child and its id
1488             IndexRecord rec = ( IndexRecord ) children.next();
1489             BigInteger childId = rec.getEntryId();
1490             
1491             /* 
1492              * Calculate the Dn for the child's new name by copying the parents
1493              * new name and adding the child's old upRdn to new name as its Rdn
1494              */
1495             Name childUpdn = ( Name ) updn.clone();
1496             Name oldUpdn = new LdapName( getEntryUpdn( childId ) );
1497             String rdn = LdapName.getRdn( oldUpdn ); 
1498             childUpdn.add( childUpdn.size(),  rdn );
1499 
1500             // Recursively change the names of the children below
1501             modifyDn( childId, childUpdn, isMove );
1502         }
1503     }
1504 
1505 
1506     /***
1507      * @see org.apache.ldap.server.db.Database#move(javax.naming.Name,
1508      * javax.naming.Name, String, boolean)
1509      */
1510     public void move( Name oldChildDn, Name newParentDn, String newRdn,
1511         boolean deleteOldRdn ) throws NamingException
1512     {
1513         modifyRdn( oldChildDn, newRdn, deleteOldRdn );
1514         move( oldChildDn, newParentDn );
1515     }
1516 
1517 
1518     /***
1519      * Moves an entry under a new parent.  The operation causes a shift in the
1520      * parent child relationships between the old parent, new parent and the 
1521      * child moved.  All other descendant entries under the child never change
1522      * their direct parent child relationships.  Hence after the parent child
1523      * relationship changes are broken at the old parent and set at the new
1524      * parent a modifyDn operation is conducted to handle name changes 
1525      * propagating down through the moved child and its descendants.
1526      * 
1527      * @param oldChildDn the normalized dn of the child to be moved
1528      * @param newParentDn the normalized dn of the new parent for the child
1529      * @throws NamingException if something goes wrong
1530      *
1531      * @see Database#move(javax.naming.Name,
1532      * javax.naming.Name)
1533      */
1534     public void move( Name oldChildDn, Name newParentDn ) throws NamingException
1535     {
1536         // Get the child and the new parent to be entries and Ids
1537         BigInteger childId = getEntryId( oldChildDn.toString() );
1538         BigInteger newParentId = getEntryId( newParentDn.toString() );
1539         BigInteger oldParentId = getParentId( childId );
1540         
1541         /*
1542          * All aliases including and below oldChildDn, will be affected by
1543          * the move operation with respect to one and subtree indices since 
1544          * their relationship to ancestors above oldChildDn will be 
1545          * destroyed.  For each alias below and including oldChildDn we will
1546          * drop the index tuples mapping ancestor ids above oldChildDn to the
1547          * respective target ids of the aliases.
1548          */
1549         dropMovedAliasIndices( oldChildDn );
1550         
1551         /*
1552          * Drop the old parent child relationship and add the new one
1553          * Set the new parent id for the child replacing the old parent id
1554          */
1555         hierarchyIdx.drop( oldParentId, childId );
1556         hierarchyIdx.add( newParentId, childId );
1557 
1558         /*
1559          * Build the new user provided DN (updn) for the child using the child's
1560          * user provided RDN & the new parent's UPDN.  Basically add the child's
1561          * UpRdn String to the tail of the new parent's Updn Name.
1562          */
1563         Name childUpdn = new LdapName( getEntryUpdn( childId ) );
1564         String childRdn = childUpdn.get( childUpdn.size() - 1 ); 
1565         Name newUpdn = new LdapName( getEntryUpdn( newParentId ) );
1566         newUpdn.add( newUpdn.size(), childRdn );
1567 
1568         // Call the modifyDn operation with the new updn
1569         modifyDn( childId, newUpdn, true );
1570     }
1571 
1572 
1573     /***
1574      * For all aliases including and under the moved base, this method removes
1575      * one and subtree alias index tuples for old ancestors above the moved base
1576      * that will no longer be ancestors after the move.
1577      * 
1578      * @param movedBase the base at which the move occured - the moved node
1579      * @throws NamingException if system indices fail
1580      */
1581     private void dropMovedAliasIndices( final Name movedBase ) throws NamingException
1582     {
1583         // Find all the aliases from movedBase down
1584         IndexAssertion isBaseDescendant = new IndexAssertion()
1585         {
1586             public boolean assertCandidate( IndexRecord rec )
1587                 throws NamingException
1588             {
1589                 String dn = getEntryDn( rec.getEntryId() );
1590                 if ( dn.endsWith( movedBase.toString() ) )
1591                 {
1592                     return true;
1593                 }
1594                 
1595                 return false;
1596             }
1597         };
1598         
1599         BigInteger movedBaseId = getEntryId( movedBase.toString() );
1600         if ( aliasIdx.reverseLookup( movedBaseId ) != null ) 
1601         {
1602             dropAliasIndices( movedBaseId, movedBase );
1603         }
1604         
1605         NamingEnumeration aliases = new IndexAssertionEnumeration(
1606             aliasIdx.listIndices( movedBase.toString(), true ), 
1607             isBaseDescendant );
1608         while ( aliases.hasMore() )
1609         {
1610             IndexRecord entry = ( IndexRecord ) aliases.next();
1611             dropAliasIndices( entry.getEntryId(), movedBase );
1612         }
1613     }
1614     
1615     
1616     /***
1617      * For the alias id all ancestor one and subtree alias tuples are moved 
1618      * above the moved base.
1619      * 
1620      * @param aliasId the id of the alias 
1621      * @param movedBase the base where the move occured
1622      * @throws NamingException if indices fail
1623      */
1624     private void dropAliasIndices( BigInteger aliasId, Name movedBase )
1625         throws NamingException
1626     {
1627         String targetDn = ( String ) aliasIdx.reverseLookup( aliasId );
1628         BigInteger targetId = getEntryId( targetDn );
1629         String aliasDn = getEntryDn( aliasId );
1630         
1631         /*
1632          * Start droping index tuples with the first ancestor right above the 
1633          * moved base.  This is the first ancestor effected by the move.
1634          */
1635         Name ancestorDn = movedBase.getSuffix( 1 );
1636         BigInteger ancestorId = getEntryId( ancestorDn.toString() );
1637         
1638         /*
1639          * We cannot just drop all tuples in the one level and subtree indices
1640          * linking baseIds to the targetId.  If more than one alias refers to
1641          * the target then droping all tuples with a value of targetId would
1642          * make all other aliases to the target inconsistent.
1643          * 
1644          * We need to walk up the path of alias ancestors right above the moved 
1645          * base until we reach the upSuffix, deleting each ( ancestorId,
1646          * targetId ) tuple in the subtree scope alias.  We only need to do 
1647          * this for the direct parent of the alias on the one level subtree if
1648          * the moved base is the alias.
1649          */
1650         if ( aliasDn.equals( movedBase.toString() ) )
1651         {
1652             oneAliasIdx.drop( ancestorId, targetId );
1653         }
1654         
1655         subAliasIdx.drop( ancestorId, targetId );
1656         
1657         while ( ! ancestorDn.equals( upSuffix ) )
1658         {
1659             ancestorDn = ancestorDn.getSuffix( 1 );
1660             ancestorId = getEntryId( ancestorDn.toString() );
1661             
1662             subAliasIdx.drop( ancestorId, targetId );
1663         }    
1664     }
1665 }
1666