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.partition.impl.btree.jdbm;
18  
19  
20  import java.io.File;
21  import java.io.IOException;
22  import java.math.BigInteger;
23  
24  import javax.naming.NamingEnumeration;
25  import javax.naming.NamingException;
26  import javax.naming.directory.Attribute;
27  import javax.naming.directory.Attributes;
28  
29  import jdbm.RecordManager;
30  import jdbm.helper.MRU;
31  import jdbm.recman.BaseRecordManager;
32  import jdbm.recman.CacheRecordManager;
33  
34  import org.apache.ldap.common.schema.AttributeType;
35  import org.apache.ldap.common.util.LRUMap;
36  import org.apache.ldap.server.partition.impl.btree.Index;
37  import org.apache.ldap.server.partition.impl.btree.IndexComparator;
38  import org.apache.ldap.server.partition.impl.btree.IndexEnumeration;
39  import org.apache.ldap.server.schema.SerializableComparator;
40  import org.apache.regexp.RE;
41  
42  
43  /***
44   * A Jdbm based index implementation.
45   *
46   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
47   * @version $Rev: 264732 $
48   */
49  public class JdbmIndex implements Index
50  {
51      /***  */
52      public static final String FORWARD_BTREE = "_forward";
53      /*** */
54      public static final String REVERSE_BTREE = "_reverse";
55  
56      /*** */
57      private AttributeType attribute;
58      /*** */
59      private JdbmTable forward = null;
60      /*** */
61      private JdbmTable reverse = null;
62      /*** */
63      private RecordManager recMan = null;
64      /*** 
65       * @todo I don't think the keyCache is required anymore since the normalizer
66       * will cache values for us.
67       */
68      private LRUMap keyCache = null;
69  
70  
71      // ------------------------------------------------------------------------
72      // C O N S T R U C T O R S
73      // ------------------------------------------------------------------------
74  
75  
76      /***
77       * Creates an Index using an existing record manager based on a file.  The
78       * index table B+Tree are created and saved within this file rather than 
79       * creating a new file.
80       *
81       * @param attribute the attribute specification to base this index on
82       * @param recMan the record manager
83       * @throws NamingException if we fail to create B+Trees using recMan
84       */
85      public JdbmIndex( AttributeType attribute, RecordManager recMan )
86          throws NamingException
87      {
88          this.attribute = attribute;
89          keyCache = new LRUMap( 1000 );
90          this.recMan = recMan;
91          initTables();
92      }
93      
94  
95      public JdbmIndex( AttributeType attribute, File wkDirPath )
96          throws NamingException
97      {
98          File file = new File( wkDirPath.getPath() + File.separator 
99              + attribute.getName() );
100         this.attribute = attribute;
101         keyCache = new LRUMap( 1000 );
102 
103         try 
104         {
105             String path = file.getAbsolutePath();
106             BaseRecordManager base = new BaseRecordManager( path );
107             base.disableTransactions();
108             recMan = new CacheRecordManager( base , new MRU( 1000 ) );
109         } 
110         catch ( IOException e ) 
111         {
112             NamingException ne = new NamingException(
113                 "Could not initialize the record manager" );
114             ne.setRootCause( e );
115             throw ne;
116         }
117 
118         initTables();
119     }
120     
121 
122     /***
123      * Initializes the forward and reverse tables used by this Index.
124      * 
125      * @throws NamingException if we cannot initialize the forward and reverse 
126      * tables
127      */    
128     private void initTables() throws NamingException
129     {
130         SerializableComparator comp;
131         comp = new SerializableComparator( attribute.getEquality().getOid() );
132         
133         /*
134          * The forward key/value map stores attribute values to master table 
135          * primary keys.  A value for an attribute can occur several times in
136          * different entries so the forward map can have more than one value.
137          */
138         forward = new JdbmTable( attribute.getName() + FORWARD_BTREE,
139             true, recMan, new IndexComparator( comp, true ) );
140         
141         /*
142          * Now the reverse map stores the primary key into the master table as
143          * the key and the values of attributes as the value.  If an attribute
144          * is single valued according to its specification based on a schema 
145          * then duplicate keys should not be allowed within the reverse table.
146          */
147         reverse = new JdbmTable( attribute.getName() + REVERSE_BTREE,
148             ! attribute.isSingleValue(), recMan, 
149             new IndexComparator( comp, false ) );
150     }
151 
152 
153     /***
154      * @see org.apache.ldap.server.partition.impl.btree.Index#getAttribute()
155      */
156     public AttributeType getAttribute()
157     {
158         return attribute;
159     }
160 
161 
162     // ------------------------------------------------------------------------
163     // Scan Count Methods
164     // ------------------------------------------------------------------------
165 
166 
167     /***
168      * @see Index#count()
169      */
170     public int count()
171         throws NamingException
172     {
173         return forward.count();
174     }
175 
176 
177     /***
178      * @see Index#count(java.lang.Object)
179      */
180     public int count( Object attrVal )
181         throws NamingException
182     {
183         return forward.count( getNormalized( attrVal ) );
184     }
185 
186 
187     /***
188      * @see org.apache.ldap.server.partition.impl.btree.Index#count(java.lang.Object, boolean)
189      */
190     public int count( Object attrVal, boolean isGreaterThan )
191         throws NamingException
192     {
193         return forward.count( getNormalized( attrVal ), isGreaterThan );
194     }
195 
196 
197     // ------------------------------------------------------------------------
198     // Forward and Reverse Lookups
199     // ------------------------------------------------------------------------
200 
201 
202     /***
203      * @see Index#forwardLookup(java.lang.Object)
204      */
205     public BigInteger forwardLookup( Object attrVal )
206         throws NamingException
207     {
208         return ( BigInteger ) forward.get( getNormalized( attrVal ) );
209     }
210 
211 
212     /***
213      * @see Index#reverseLookup(java.math.BigInteger)
214      */
215     public Object reverseLookup( BigInteger id )
216         throws NamingException
217     {
218         return reverse.get( id );
219     }
220 
221 
222     // ------------------------------------------------------------------------
223     // Add/Drop Methods
224     // ------------------------------------------------------------------------
225 
226 
227     /***
228      * @see org.apache.ldap.server.partition.impl.btree.Index#add(java.lang.Object,
229      * java.math.BigInteger)
230      */
231     public synchronized void add( Object attrVal, BigInteger id )
232         throws NamingException
233     {
234         forward.put( getNormalized( attrVal ), id );
235         reverse.put( id, getNormalized( attrVal ) );
236     }
237 
238 
239     /***
240      * @see org.apache.ldap.server.partition.impl.btree.Index#add(
241      * javax.naming.directory.Attribute, java.math.BigInteger)
242      */
243     public synchronized void add( Attribute attr, BigInteger id ) 
244         throws NamingException 
245     {
246         // Can efficiently batch add to the reverse table 
247         NamingEnumeration values = attr.getAll();
248         reverse.put( id, values );
249         
250         // Have no choice but to add each value individually to forward table
251         values = attr.getAll();
252         while ( values.hasMore() )
253         {
254             forward.put( values.next(), id );
255         }
256     }
257 
258 
259     /***
260      * @see Index#add(
261      * javax.naming.directory.Attributes, java.math.BigInteger)
262      */
263     public synchronized void add( Attributes attrs, BigInteger id ) 
264         throws NamingException
265     {
266         add( attrs.get( attribute.getName() ), id );
267     }
268 
269 
270     /***
271      * @see org.apache.ldap.server.partition.impl.btree.Index#drop(java.lang.Object,
272      * java.math.BigInteger)
273      */
274     public synchronized void drop( Object attrVal, BigInteger id )
275         throws NamingException
276     {
277         forward.remove( getNormalized( attrVal ), id );
278         reverse.remove( id, getNormalized( attrVal ) );
279     }
280 
281 
282     /***
283      * @see Index#drop(java.math.BigInteger)
284      */
285     public void drop( BigInteger entryId ) 
286         throws NamingException 
287     {
288         NamingEnumeration values = reverse.listValues( entryId );
289         
290         while ( values.hasMore() )
291         {
292             forward.remove( values.next(), entryId );
293         }
294         
295         reverse.remove( entryId );
296     }
297 
298 
299     /***
300      * @see Index#drop(
301      * javax.naming.directory.Attribute, java.math.BigInteger)
302      */
303     public void drop( Attribute attr, BigInteger id )
304         throws NamingException 
305     {
306         // Can efficiently batch remove from the reverse table 
307         NamingEnumeration values = attr.getAll();
308         
309         // If their are no values in attr this is a request to drop all
310         if ( ! values.hasMore() )
311         {
312             drop( id );
313             return;
314         }
315         
316         reverse.remove( id, values );
317         
318         // Have no choice but to remove values individually from forward table
319         values = attr.getAll();
320         while ( values.hasMore() )
321         {
322             forward.remove( values.next(), id );
323         }
324     }
325         
326     
327     /***
328      * @see org.apache.ldap.server.partition.impl.btree.Index#drop(
329      * javax.naming.directory.Attributes, java.math.BigInteger)
330      */
331     public void drop( Attributes attrs, BigInteger id )
332         throws NamingException 
333     {
334         drop( attrs.get( attribute.getName() ), id );
335     }
336         
337     
338     // ------------------------------------------------------------------------
339     // Index Listing Operations
340     // ------------------------------------------------------------------------
341 
342 
343     /***
344      * @see Index#listReverseIndices(BigInteger)
345      */
346     public IndexEnumeration listReverseIndices( BigInteger id )
347         throws NamingException
348     {
349         return new IndexEnumeration( reverse.listTuples( id ), true );
350     }
351 
352 
353     /***
354      * @see Index#listIndices()
355      */
356     public IndexEnumeration listIndices()
357         throws NamingException
358     {
359         return new IndexEnumeration( forward.listTuples() );
360     }
361 
362 
363     /***
364      * @see org.apache.ldap.server.partition.impl.btree.Index#listIndices(java.lang.Object)
365      */
366     public IndexEnumeration listIndices( Object attrVal ) 
367         throws NamingException
368     {
369         return new IndexEnumeration( forward.listTuples( 
370             getNormalized( attrVal ) ) );
371     }
372 
373 
374     /***
375      * @see org.apache.ldap.server.partition.impl.btree.Index#listIndices(java.lang.Object,
376      * boolean)
377      */
378     public IndexEnumeration listIndices( Object attrVal, 
379         boolean isGreaterThan ) throws NamingException
380     {
381         return new IndexEnumeration( forward.listTuples( 
382             getNormalized( attrVal ), isGreaterThan ) );
383     }
384 
385 
386     /***
387      * @see Index#listIndices(org.apache.regexp.RE)
388      */
389     public IndexEnumeration listIndices( RE regex )
390         throws NamingException
391     {
392         return new IndexEnumeration( forward.listTuples(), false, regex );
393     }
394 
395 
396     /***
397      * @see Index#listIndices(org.apache.regexp.RE,
398      * java.lang.String)
399      */
400     public IndexEnumeration listIndices( RE regex, String prefix )
401         throws NamingException
402     {
403         return new IndexEnumeration( forward.listTuples(
404             getNormalized( prefix ), true ), false, regex );
405     }
406 
407 
408     // ------------------------------------------------------------------------
409     // Value Assertion (a.k.a Index Lookup) Methods //
410     // ------------------------------------------------------------------------
411 
412 
413     /***
414      * @see Index#hasValue(java.lang.Object,
415      * java.math.BigInteger)
416      */
417     public boolean hasValue( Object attrVal, BigInteger id )
418         throws NamingException
419     {
420         return forward.has( getNormalized( attrVal ), id );
421     }
422 
423 
424     /***
425      * @see Index#hasValue(java.lang.Object,
426      * java.math.BigInteger, boolean)
427      */
428     public boolean hasValue( Object attrVal, BigInteger id,
429         boolean isGreaterThan )
430         throws NamingException
431     {
432         return forward.has( getNormalized( attrVal ), 
433             id, isGreaterThan );
434     }
435 
436 
437     /***
438      * @see Index#hasValue(org.apache.regexp.RE,
439      * java.math.BigInteger)
440      */
441     public boolean hasValue( RE regex, BigInteger id )
442         throws NamingException
443     {
444         IndexEnumeration list = new IndexEnumeration( 
445             reverse.listTuples( id ), true, regex );
446         boolean hasValue = list.hasMore();
447         list.close();
448         return hasValue;
449     }
450 
451 
452     // ------------------------------------------------------------------------
453     // Maintenance Methods 
454     // ------------------------------------------------------------------------
455 
456 
457     /***
458      * @see Index#close()
459      */
460     public synchronized void close()
461         throws NamingException
462     {
463         try 
464         {
465             forward.close();
466             reverse.close();
467             recMan.commit();
468             recMan.close();
469         } 
470         catch ( IOException e ) 
471         {
472             NamingException ne = new NamingException( 
473                 "Exception while closing backend index file for attribute " 
474                 + attribute.getName() );
475             ne.setRootCause( e );
476             throw ne;
477         }
478     }
479 
480 
481     /***
482      * @see Index#sync()
483      */
484     public synchronized void sync()
485         throws NamingException
486     {
487         try 
488         {
489             recMan.commit();
490         } 
491         catch ( IOException e ) 
492         {
493             NamingException ne = new NamingException( 
494                 "Exception while syncing backend index file for attribute " 
495                 + attribute.getName() );
496             ne.setRootCause( e );
497             throw ne;
498         }
499     }
500 
501 
502     /***
503      * TODO I don't think the keyCache is required anymore since the normalizer
504      * will cache values for us.
505      */
506     public Object getNormalized( Object attrVal )
507         throws NamingException
508     {
509         Object normalized = keyCache.get( attrVal );
510 
511         if ( null == normalized ) 
512         {
513             normalized = attribute.getEquality().getNormalizer().normalize( attrVal );
514 
515             // Double map it so if we use an already normalized
516             // value we can get back the same normalized value.
517             // and not have to regenerate a second time.
518             keyCache.put( attrVal, normalized );
519             keyCache.put( normalized, normalized );
520         }
521 
522         return normalized;
523     }
524 }