View Javadoc

1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *  
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *  
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License. 
18   *  
19   */
20  package org.apache.directory.server.core.partition.impl.btree.jdbm;
21  
22  
23  import jdbm.RecordManager;
24  import jdbm.helper.MRU;
25  import jdbm.recman.BaseRecordManager;
26  import jdbm.recman.CacheRecordManager;
27  import org.apache.directory.server.core.partition.impl.btree.*;
28  import org.apache.directory.server.core.cursor.Cursor;
29  import org.apache.directory.server.schema.SerializableComparator;
30  import org.apache.directory.server.xdbm.Index;
31  import org.apache.directory.server.xdbm.Tuple;
32  import org.apache.directory.server.xdbm.IndexCursor;
33  import org.apache.directory.shared.ldap.schema.AttributeType;
34  import org.apache.directory.shared.ldap.util.SynchronizedLRUMap;
35  
36  import javax.naming.NamingException;
37  import java.io.File;
38  import java.io.IOException;
39  
40  
41  /** 
42   * A Jdbm based index implementation.
43   *
44   * @org.apache.xbean.XBean
45   * 
46   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
47   * @version $Rev: 689396 $
48   */
49  public class JdbmIndex<K,O> implements Index<K,O>
50  {
51      /**
52       * default duplicate limit before duplicate keys switch to using a btree for values
53       */
54      public static final int DEFAULT_DUPLICATE_LIMIT = 512;
55  
56      /**  the key used for the forward btree name */
57      public static final String FORWARD_BTREE = "_forward";
58      /**  the key used for the reverse btree name */
59      public static final String REVERSE_BTREE = "_reverse";
60  
61      /** the attribute type resolved for this JdbmIndex */
62      private AttributeType attribute;
63      /**
64       * the forward btree where the btree key is the value of the indexed attribute and
65       * the value of the btree is the entry id of the entry containing an attribute with
66       * that value
67       */
68      protected JdbmTable<K, Long> forward;
69      /**
70       * the reverse btree where the btree key is the entry id of the entry containing a
71       * value for the indexed attribute, and the btree value is the value of the indexed
72       * attribute
73       */
74      protected JdbmTable<Long,K> reverse;
75      /**
76       * the JDBM record manager for the file containing this index
77       */
78      protected RecordManager recMan;
79      /**
80       * the normalized value cache for this index
81       * @todo I don't think the keyCache is required anymore since the normalizer
82       * will cache values for us.
83       */
84      protected SynchronizedLRUMap keyCache;
85      /** the size (number of index entries) for the cache */
86      protected int cacheSize = DEFAULT_INDEX_CACHE_SIZE;
87      /**
88       * duplicate limit before duplicate keys switch to using a btree for values
89       */
90      protected int numDupLimit = DEFAULT_DUPLICATE_LIMIT;
91      /**
92       * the attribute identifier set at configuration time for this index which may not
93       * be the OID but an alias name for the attributeType associated with this Index
94       */
95      private String attributeId;
96      /** whether or not this index has been initialized */
97      protected boolean initialized;
98      /** a customm working directory path when specified in configuration */
99      protected File wkDirPath;
100 
101 
102     /*
103      * NOTE: Duplicate Key Limit
104      *
105      * Jdbm cannot store duplicate keys: meaning it cannot have more than one value
106      * for the same key in the btree.  Thus as a workaround we stuff values for the
107      * same key into a TreeSet.  This is only effective up to some threshold after
108      * which we run into problems with serialization on and off disk.  A threshold
109      * is used to determine when to switch from using a TreeSet to start using another
110      * btree in the same index file just for the values.  This value only btree just
111      * has keys populated without a value for it's btree entries. When the switch
112      * occurs the value for the key in the index btree contains a pointer to the
113      * btree containing it's values.
114      *
115      * This numDupLimit is the threshold at which we switch from using in memory
116      * containers for values of the same key to using a btree for those values
117      * instead with indirection.
118      */
119 
120     // ------------------------------------------------------------------------
121     // C O N S T R U C T O R S
122     // ----------------------------------------------------------------------
123 
124     public JdbmIndex()
125     {
126         initialized = false;
127     }
128 
129 
130     public JdbmIndex( String attributeId )
131     {
132         initialized = false;
133         setAttributeId( attributeId );
134     }
135 
136 
137     public void init( AttributeType attributeType, File wkDirPath ) throws IOException
138     {
139         this.keyCache = new SynchronizedLRUMap( cacheSize );
140         this.attribute = attributeType;
141 
142         if ( attributeId == null )
143         {
144             setAttributeId( attribute.getName() );
145         }
146 
147         if ( this.wkDirPath == null )
148         {
149             this.wkDirPath = wkDirPath;
150         }
151 
152         File file = new File( this.wkDirPath.getPath() + File.separator + attribute.getName() );
153         String path = file.getAbsolutePath();
154         BaseRecordManager base = new BaseRecordManager( path );
155         base.disableTransactions();
156         this.recMan = new CacheRecordManager( base, new MRU( cacheSize ) );
157 
158         initTables();
159         initialized = true;
160     }
161 
162     
163     /**
164      * Initializes the forward and reverse tables used by this Index.
165      * 
166      * @throws IOException if we cannot initialize the forward and reverse
167      * tables
168      */
169     private void initTables() throws IOException
170     {
171         SerializableComparator<K> comp;
172 
173         try
174         {
175             comp = new SerializableComparator<K>( attribute.getEquality().getOid() );
176         }
177         catch ( NamingException e )
178         {
179             IOException ioe = new IOException( "Failed to find an equality matching rule for attribute type" );
180             ioe.initCause( e );
181             throw ioe;
182         }
183 
184         /*
185          * The forward key/value map stores attribute values to master table 
186          * primary keys.  A value for an attribute can occur several times in
187          * different entries so the forward map can have more than one value.
188          */
189         forward = new JdbmTable<K, Long>(
190             attribute.getName() + FORWARD_BTREE, 
191             numDupLimit,
192             recMan, 
193             comp, LongComparator.INSTANCE,
194             null, LongSerializer.INSTANCE );
195 
196         /*
197          * Now the reverse map stores the primary key into the master table as
198          * the key and the values of attributes as the value.  If an attribute
199          * is single valued according to its specification based on a schema 
200          * then duplicate keys should not be allowed within the reverse table.
201          */
202         if ( attribute.isSingleValue() )
203         {
204             reverse = new JdbmTable<Long,K>(
205                 attribute.getName() + REVERSE_BTREE,
206                 recMan,
207                 LongComparator.INSTANCE,
208                 LongSerializer.INSTANCE,
209                 null );
210         }
211         else
212         {
213             reverse = new JdbmTable<Long,K>(
214                 attribute.getName() + REVERSE_BTREE,
215                 numDupLimit,
216                 recMan,
217                 LongComparator.INSTANCE, comp,
218                 LongSerializer.INSTANCE, null );
219         }
220     }
221 
222 
223     /**
224      * @see org.apache.directory.server.xdbm.Index#getAttribute()
225      */
226     public AttributeType getAttribute()
227     {
228         return attribute;
229     }
230 
231 
232     // ------------------------------------------------------------------------
233     // C O N F I G U R A T I O N   M E T H O D S
234     // ------------------------------------------------------------------------
235 
236     /**
237      * Protects configuration properties from being set after initialization.
238      *
239      * @param property the property to protect
240      */
241     private void protect( String property )
242     {
243         if ( initialized )
244         {
245             throw new IllegalStateException( "The " + property
246                 + " property for an index cannot be set after it has been initialized." );
247         }
248     }
249 
250 
251     public boolean isCountExact()
252     {
253         return false;
254     }
255     
256 
257     /**
258      * Gets the attribute identifier set at configuration time for this index which may not
259      * be the OID but an alias name for the attributeType associated with this Index
260      *
261      * @return configured attribute oid or alias name
262      */
263     public String getAttributeId()
264     {
265         return attributeId;
266     }
267 
268 
269     /**
270      * Sets the attribute identifier set at configuration time for this index which may not
271      * be the OID but an alias name for the attributeType associated with this Index
272      *
273      * @param attributeId configured attribute oid or alias name
274      */
275     public void setAttributeId( String attributeId )
276     {
277         protect( "attributeId" );
278         this.attributeId = attributeId;
279     }
280 
281 
282     /**
283      * Gets the threshold at which point duplicate keys use btree indirection to store
284      * their values.
285      *
286      * @return the threshold for storing a keys values in another btree
287      */
288     public int getNumDupLimit()
289     {
290         return numDupLimit;
291     }
292 
293 
294     /**
295      * Sets the threshold at which point duplicate keys use btree indirection to store
296      * their values.
297      *
298      * @param numDupLimit the threshold for storing a keys values in another btree
299      */
300     public void setNumDupLimit( int numDupLimit )
301     {
302         protect( "numDupLimit" );
303         this.numDupLimit = numDupLimit;
304     }
305 
306 
307     /**
308      * Gets the size of the index cache in terms of the number of index entries to be cached.
309      *
310      * @return the size of the index cache
311      */
312     public int getCacheSize()
313     {
314         return cacheSize;
315     }
316 
317 
318     /**
319      * Sets the size of the index cache in terms of the number of index entries to be cached.
320      *
321      * @param cacheSize the size of the index cache
322      */
323     public void setCacheSize( int cacheSize )
324     {
325         protect( "cacheSize" );
326         this.cacheSize = cacheSize;
327     }
328 
329 
330     /**
331      * Sets the working directory path to something other than the default. Sometimes more
332      * performance is gained by locating indices on separate disk spindles.
333      *
334      * @param wkDirPath optional working directory path
335      */
336     public void setWkDirPath( File wkDirPath )
337     {
338         protect( "wkDirPath" );
339         this.wkDirPath = wkDirPath;
340     }
341 
342 
343     /**
344      * Gets the working directory path to something other than the default. Sometimes more
345      * performance is gained by locating indices on separate disk spindles.
346      *
347      * @return optional working directory path 
348      */
349     public File getWkDirPath()
350     {
351         return wkDirPath;
352     }
353 
354 
355     // ------------------------------------------------------------------------
356     // Scan Count Methods
357     // ------------------------------------------------------------------------
358 
359 
360     /**
361      * @see org.apache.directory.server.xdbm.Index#count()
362      */
363     public int count() throws IOException
364     {
365         return forward.count();
366     }
367 
368 
369     /**
370      * @see Index#count(java.lang.Object)
371      */
372     public int count( K attrVal ) throws Exception
373     {
374         return forward.count( getNormalized( attrVal ) );
375     }
376 
377 
378     public int greaterThanCount( K attrVal ) throws Exception
379     {
380         return forward.greaterThanCount( getNormalized( attrVal ) );
381     }
382     
383     
384     /**
385      * @see org.apache.directory.server.xdbm.Index#lessThanCount(java.lang.Object)
386      */
387     public int lessThanCount( K attrVal ) throws Exception
388     {
389         return forward.lessThanCount( getNormalized( attrVal ) );
390     }
391 
392 
393     // ------------------------------------------------------------------------
394     // Forward and Reverse Lookups
395     // ------------------------------------------------------------------------
396 
397 
398     /**
399      * @see Index#forwardLookup(java.lang.Object)
400      */
401     public Long forwardLookup( K attrVal ) throws Exception
402     {
403         return forward.get( getNormalized( attrVal ) );
404     }
405 
406 
407     /**
408      * @see org.apache.directory.server.xdbm.Index#reverseLookup(Long)
409      */
410     public K reverseLookup( Long id ) throws Exception
411     {
412         return reverse.get( id );
413     }
414 
415 
416     // ------------------------------------------------------------------------
417     // Add/Drop Methods
418     // ------------------------------------------------------------------------
419 
420 
421     /**
422      * @see Index#add(Object, Long)
423      */
424     public synchronized void add( K attrVal, Long id ) throws Exception
425     {
426         forward.put( getNormalized( attrVal ), id );
427         reverse.put( id, getNormalized( attrVal ) );
428     }
429 
430 
431     /**
432      * @see Index#drop(Object,Long)
433      */
434     public synchronized void drop( K attrVal, Long id ) throws Exception
435     {
436         forward.remove( getNormalized( attrVal ), id );
437         reverse.remove( id, getNormalized( attrVal ) );
438     }
439 
440 
441     /**
442      * @see Index#drop(Long)
443      */
444     public void drop( Long id ) throws Exception
445     {
446         Cursor<Tuple<Long,K>> values = reverse.cursor();
447         Tuple<Long,K> tuple = new Tuple<Long,K>( id, null );
448         values.before( tuple );
449 
450         while ( values.next() )
451         {
452             forward.remove( values.get().getValue(), id );
453         }
454 
455         reverse.remove( id );
456     }
457 
458 
459     // ------------------------------------------------------------------------
460     // Index Cursor Operations
461     // ------------------------------------------------------------------------
462 
463 
464     @SuppressWarnings("unchecked")
465     public IndexCursor<K, O> reverseCursor() throws Exception
466     {
467         return new IndexCursorAdaptor<K, O>( ( Cursor ) reverse.cursor(), false );
468     }
469 
470 
471     @SuppressWarnings("unchecked")
472     public IndexCursor<K, O> forwardCursor() throws Exception
473     {
474         return new IndexCursorAdaptor<K, O>( ( Cursor ) forward.cursor(), true );
475     }
476 
477 
478     @SuppressWarnings("unchecked")
479     public IndexCursor<K, O> reverseCursor( Long id ) throws Exception
480     {
481         return new IndexCursorAdaptor<K, O>( ( Cursor ) reverse.cursor( id ), false );
482     }
483 
484 
485     @SuppressWarnings("unchecked")
486     public IndexCursor<K, O> forwardCursor( K key ) throws Exception
487     {
488         return new IndexCursorAdaptor<K, O>( ( Cursor ) forward.cursor( key ), true );
489     }
490 
491 
492     public Cursor<K> reverseValueCursor( Long id ) throws Exception
493     {
494         return reverse.valueCursor( id );
495     }
496 
497 
498     public Cursor<Long> forwardValueCursor( K key ) throws Exception
499     {
500         return forward.valueCursor( key );
501     }
502 
503 
504     // ------------------------------------------------------------------------
505     // Value Assertion (a.k.a Index Lookup) Methods //
506     // ------------------------------------------------------------------------
507 
508     
509     /**
510      * @see Index#forward(Object)
511      */
512     public boolean forward( K attrVal ) throws Exception
513     {
514         return forward.has( getNormalized( attrVal ) );
515     }
516 
517 
518     /**
519      * @see Index#forward(Object,Long)
520      */
521     public boolean forward( K attrVal, Long id ) throws Exception
522     {
523         return forward.has( getNormalized( attrVal ), id );
524     }
525 
526     /**
527      * @see Index#reverse(Long)
528      */
529     public boolean reverse( Long id ) throws Exception
530     {
531         return reverse.has( id );
532     }
533 
534 
535     /**
536      * @see Index#reverse(Long,Object)
537      */
538     public boolean reverse( Long id, K attrVal ) throws Exception
539     {
540         return forward.has( getNormalized( attrVal ), id );
541     }
542 
543 
544     /**
545      * @see org.apache.directory.server.xdbm.Index#forwardGreaterOrEq(Object)
546      */
547     public boolean forwardGreaterOrEq( K attrVal ) throws Exception
548     {
549         return forward.hasGreaterOrEqual( getNormalized( attrVal ) );
550     }
551 
552 
553     /**
554      * @see org.apache.directory.server.xdbm.Index#forwardGreaterOrEq(Object, Long)
555      */
556     public boolean forwardGreaterOrEq( K attrVal, Long id ) throws Exception
557     {
558         return forward.hasGreaterOrEqual( getNormalized( attrVal ), id );
559     }
560 
561 
562     /**
563      * @see org.apache.directory.server.xdbm.Index#forwardLessOrEq(Object)
564      */
565     public boolean forwardLessOrEq( K attrVal ) throws Exception
566     {
567         return forward.hasLessOrEqual( getNormalized( attrVal ) );
568     }
569 
570 
571     /**
572      * @see org.apache.directory.server.xdbm.Index#forwardLessOrEq(Object, Long)
573      */
574     public boolean forwardLessOrEq( K attrVal, Long id ) throws Exception
575     {
576         return forward.hasLessOrEqual( getNormalized( attrVal ), id );
577     }
578 
579 
580     /**
581      * @see org.apache.directory.server.xdbm.Index#reverseGreaterOrEq(Long)
582      */
583     public boolean reverseGreaterOrEq( Long id ) throws Exception
584     {
585         return reverse.hasGreaterOrEqual( id );
586     }
587 
588 
589     /**
590      * @see org.apache.directory.server.xdbm.Index#reverseGreaterOrEq(Long,Object)
591      */
592     public boolean reverseGreaterOrEq( Long id, K attrVal ) throws Exception
593     {
594         return reverse.hasGreaterOrEqual( id, getNormalized( attrVal ) );
595     }
596 
597 
598     /**
599      * @see org.apache.directory.server.xdbm.Index#reverseLessOrEq(Long)
600      */
601     public boolean reverseLessOrEq( Long id ) throws Exception
602     {
603         return reverse.hasLessOrEqual( id );
604     }
605 
606 
607     /**
608      * @see org.apache.directory.server.xdbm.Index#reverseLessOrEq(Long,Object)
609      */
610     public boolean reverseLessOrEq( Long id, K attrVal ) throws Exception
611     {
612         return reverse.hasLessOrEqual( id, getNormalized( attrVal ) );
613     }
614 
615 
616     // ------------------------------------------------------------------------
617     // Maintenance Methods 
618     // ------------------------------------------------------------------------
619 
620 
621     /**
622      * @see org.apache.directory.server.xdbm.Index#close()
623      */
624     public synchronized void close() throws IOException
625     {
626         forward.close();
627         reverse.close();
628         recMan.commit();
629         recMan.close();
630     }
631 
632 
633     /**
634      * @see Index#sync()
635      */
636     public synchronized void sync() throws IOException
637     {
638         recMan.commit();
639     }
640 
641 
642     /**
643      * TODO I don't think the keyCache is required anymore since the normalizer
644      * will cache values for us.
645      */
646     @SuppressWarnings("unchecked")
647     public K getNormalized( K attrVal ) throws Exception
648     {
649         if ( attrVal instanceof Long )
650         {
651             return attrVal;
652         }
653 
654         K normalized = ( K ) keyCache.get( attrVal );
655 
656         if ( null == normalized )
657         {
658             normalized = ( K ) attribute.getEquality().getNormalizer().normalize( attrVal );
659 
660             // Double map it so if we use an already normalized
661             // value we can get back the same normalized value.
662             // and not have to regenerate a second time.
663             keyCache.put( attrVal, normalized );
664             keyCache.put( normalized, normalized );
665         }
666 
667         return normalized;
668     }
669     
670     
671     /**
672      * @see Object#toString()
673      */
674     public String toString()
675     {
676         return "Index<" + attributeId +">";
677     }
678 }