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