001    /*
002     *  Licensed to the Apache Software Foundation (ASF) under one
003     *  or more contributor license agreements.  See the NOTICE file
004     *  distributed with this work for additional information
005     *  regarding copyright ownership.  The ASF licenses this file
006     *  to you under the Apache License, Version 2.0 (the
007     *  "License"); you may not use this file except in compliance
008     *  with the License.  You may obtain a copy of the License at
009     *  
010     *    http://www.apache.org/licenses/LICENSE-2.0
011     *  
012     *  Unless required by applicable law or agreed to in writing,
013     *  software distributed under the License is distributed on an
014     *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015     *  KIND, either express or implied.  See the License for the
016     *  specific language governing permissions and limitations
017     *  under the License. 
018     *  
019     */
020    package org.apache.directory.server.core.partition.impl.btree.jdbm;
021    
022    
023    import java.io.File;
024    import java.io.IOException;
025    
026    import javax.naming.NamingException;
027    
028    import jdbm.RecordManager;
029    import jdbm.helper.MRU;
030    import jdbm.recman.BaseRecordManager;
031    import jdbm.recman.CacheRecordManager;
032    
033    import org.apache.directory.server.core.partition.impl.btree.IndexCursorAdaptor;
034    import org.apache.directory.server.core.partition.impl.btree.LongComparator;
035    import org.apache.directory.server.i18n.I18n;
036    import org.apache.directory.server.xdbm.Index;
037    import org.apache.directory.server.xdbm.IndexCursor;
038    import org.apache.directory.server.xdbm.Tuple;
039    import org.apache.directory.shared.ldap.cursor.Cursor;
040    import org.apache.directory.shared.ldap.entry.BinaryValue;
041    import org.apache.directory.shared.ldap.schema.AttributeType;
042    import org.apache.directory.shared.ldap.schema.MatchingRule;
043    import org.apache.directory.shared.ldap.schema.SchemaManager;
044    import org.apache.directory.shared.ldap.schema.comparators.SerializableComparator;
045    import org.apache.directory.shared.ldap.util.SynchronizedLRUMap;
046    import org.slf4j.Logger;
047    import org.slf4j.LoggerFactory;
048    
049    
050    /** 
051     * A Jdbm based index implementation.
052     *
053     * @org.apache.xbean.XBean
054     * 
055     * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
056     * @version $Rev: 928296 $
057     */
058    public class JdbmIndex<K, O> implements Index<K, O, Long>
059    {
060        /** A logger for this class */
061        private static final Logger LOG = LoggerFactory.getLogger( JdbmIndex.class.getSimpleName() );
062    
063        /**
064         * default duplicate limit before duplicate keys switch to using a btree for values
065         */
066        public static final int DEFAULT_DUPLICATE_LIMIT = 512;
067    
068        /**  the key used for the forward btree name */
069        public static final String FORWARD_BTREE = "_forward";
070    
071        /**  the key used for the reverse btree name */
072        public static final String REVERSE_BTREE = "_reverse";
073    
074        /** the attribute type resolved for this JdbmIndex */
075        private AttributeType attribute;
076    
077        /**
078         * the forward btree where the btree key is the value of the indexed attribute and
079         * the value of the btree is the entry id of the entry containing an attribute with
080         * that value
081         */
082        protected JdbmTable<K, Long> forward;
083    
084        /**
085         * the reverse btree where the btree key is the entry id of the entry containing a
086         * value for the indexed attribute, and the btree value is the value of the indexed
087         * attribute
088         */
089        protected JdbmTable<Long, K> reverse;
090    
091        /**
092         * the JDBM record manager for the file containing this index
093         */
094        protected RecordManager recMan;
095    
096        /**
097         * the normalized value cache for this index
098         * @todo I don't think the keyCache is required anymore since the normalizer
099         * will cache values for us.
100         */
101        protected SynchronizedLRUMap keyCache;
102    
103        /** the size (number of index entries) for the cache */
104        protected int cacheSize = DEFAULT_INDEX_CACHE_SIZE;
105    
106        /**
107         * duplicate limit before duplicate keys switch to using a btree for values
108         */
109        protected int numDupLimit = DEFAULT_DUPLICATE_LIMIT;
110    
111        /**
112         * the attribute identifier set at configuration time for this index which may not
113         * be the OID but an alias name for the attributeType associated with this Index
114         */
115        private String attributeId;
116    
117        /** whether or not this index has been initialized */
118        protected boolean initialized;
119    
120        /** a custom working directory path when specified in configuration */
121        protected File wkDirPath;
122    
123    
124        /*
125         * NOTE: Duplicate Key Limit
126         *
127         * Jdbm cannot store duplicate keys: meaning it cannot have more than one value
128         * for the same key in the btree.  Thus as a workaround we stuff values for the
129         * same key into a TreeSet.  This is only effective up to some threshold after
130         * which we run into problems with serialization on and off disk.  A threshold
131         * is used to determine when to switch from using a TreeSet to start using another
132         * btree in the same index file just for the values.  This value only btree just
133         * has keys populated without a value for it's btree entries. When the switch
134         * occurs the value for the key in the index btree contains a pointer to the
135         * btree containing it's values.
136         *
137         * This numDupLimit is the threshold at which we switch from using in memory
138         * containers for values of the same key to using a btree for those values
139         * instead with indirection.
140         */
141    
142        // ------------------------------------------------------------------------
143        // C O N S T R U C T O R S
144        // ----------------------------------------------------------------------
145    
146        public JdbmIndex()
147        {
148            initialized = false;
149        }
150    
151    
152        public JdbmIndex( String attributeId )
153        {
154            initialized = false;
155            setAttributeId( attributeId );
156        }
157    
158    
159        public void init( SchemaManager schemaManager, AttributeType attributeType, File wkDirPath ) throws IOException
160        {
161            LOG.debug( "Initializing an Index for attribute '{}'", attributeType.getName() );
162    
163            keyCache = new SynchronizedLRUMap( cacheSize );
164            attribute = attributeType;
165    
166            if ( attributeId == null )
167            {
168                setAttributeId( attribute.getName() );
169            }
170    
171            if ( this.wkDirPath == null )
172            {
173                this.wkDirPath = wkDirPath;
174            }
175    
176            File file = new File( this.wkDirPath.getPath() + File.separator + attribute.getName() );
177            String path = file.getAbsolutePath();
178            BaseRecordManager base = new BaseRecordManager( path );
179            base.disableTransactions();
180            this.recMan = new CacheRecordManager( base, new MRU( cacheSize ) );
181    
182            try
183            {
184                initTables( schemaManager );
185            }
186            catch ( IOException e )
187            {
188                // clean up
189                close();
190                throw e;
191            }
192    
193            initialized = true;
194        }
195    
196    
197        /**
198         * Initializes the forward and reverse tables used by this Index.
199         * 
200         * @throws IOException if we cannot initialize the forward and reverse
201         * tables
202         * @throws NamingException 
203         */
204        private void initTables( SchemaManager schemaManager ) throws IOException
205        {
206            SerializableComparator<K> comp;
207    
208            MatchingRule mr = attribute.getEquality();
209    
210            if ( mr == null )
211            {
212                throw new IOException( I18n.err( I18n.ERR_574, attribute.getName() ) );
213            }
214    
215            comp = new SerializableComparator<K>( mr.getOid() );
216    
217            /*
218             * The forward key/value map stores attribute values to master table 
219             * primary keys.  A value for an attribute can occur several times in
220             * different entries so the forward map can have more than one value.
221             */
222            LongComparator.INSTANCE.setSchemaManager( schemaManager );
223            comp.setSchemaManager( schemaManager );
224    
225            forward = new JdbmTable<K, Long>( schemaManager, attribute.getName() + FORWARD_BTREE, numDupLimit, recMan,
226                comp, LongComparator.INSTANCE, null, LongSerializer.INSTANCE );
227    
228            /*
229             * Now the reverse map stores the primary key into the master table as
230             * the key and the values of attributes as the value.  If an attribute
231             * is single valued according to its specification based on a schema 
232             * then duplicate keys should not be allowed within the reverse table.
233             */
234            if ( attribute.isSingleValued() )
235            {
236                reverse = new JdbmTable<Long, K>( schemaManager, attribute.getName() + REVERSE_BTREE, recMan,
237                    LongComparator.INSTANCE, LongSerializer.INSTANCE, null );
238            }
239            else
240            {
241                reverse = new JdbmTable<Long, K>( schemaManager, attribute.getName() + REVERSE_BTREE, numDupLimit, recMan,
242                    LongComparator.INSTANCE, comp, LongSerializer.INSTANCE, null );
243            }
244        }
245    
246    
247        /**
248         * @see org.apache.directory.server.xdbm.Index#getAttribute()
249         */
250        public AttributeType getAttribute()
251        {
252            return attribute;
253        }
254    
255    
256        // ------------------------------------------------------------------------
257        // C O N F I G U R A T I O N   M E T H O D S
258        // ------------------------------------------------------------------------
259    
260        /**
261         * Protects configuration properties from being set after initialization.
262         *
263         * @param property the property to protect
264         */
265        private void protect( String property )
266        {
267            if ( initialized )
268            {
269                throw new IllegalStateException( I18n.err( I18n.ERR_575, property ) );
270            }
271        }
272    
273    
274        public boolean isCountExact()
275        {
276            return false;
277        }
278    
279    
280        /**
281         * Gets the attribute identifier set at configuration time for this index which may not
282         * be the OID but an alias name for the attributeType associated with this Index
283         *
284         * @return configured attribute oid or alias name
285         */
286        public String getAttributeId()
287        {
288            return attributeId;
289        }
290    
291    
292        /**
293         * Sets the attribute identifier set at configuration time for this index which may not
294         * be the OID but an alias name for the attributeType associated with this Index
295         *
296         * @param attributeId configured attribute oid or alias name
297         */
298        public void setAttributeId( String attributeId )
299        {
300            protect( "attributeId" );
301            this.attributeId = attributeId;
302        }
303    
304    
305        /**
306         * Gets the threshold at which point duplicate keys use btree indirection to store
307         * their values.
308         *
309         * @return the threshold for storing a keys values in another btree
310         */
311        public int getNumDupLimit()
312        {
313            return numDupLimit;
314        }
315    
316    
317        /**
318         * Sets the threshold at which point duplicate keys use btree indirection to store
319         * their values.
320         *
321         * @param numDupLimit the threshold for storing a keys values in another btree
322         */
323        public void setNumDupLimit( int numDupLimit )
324        {
325            protect( "numDupLimit" );
326            this.numDupLimit = numDupLimit;
327        }
328    
329    
330        /**
331         * Gets the size of the index cache in terms of the number of index entries to be cached.
332         *
333         * @return the size of the index cache
334         */
335        public int getCacheSize()
336        {
337            return cacheSize;
338        }
339    
340    
341        /**
342         * Sets the size of the index cache in terms of the number of index entries to be cached.
343         *
344         * @param cacheSize the size of the index cache
345         */
346        public void setCacheSize( int cacheSize )
347        {
348            protect( "cacheSize" );
349            this.cacheSize = cacheSize;
350        }
351    
352    
353        /**
354         * Sets the working directory path to something other than the default. Sometimes more
355         * performance is gained by locating indices on separate disk spindles.
356         *
357         * @param wkDirPath optional working directory path
358         */
359        public void setWkDirPath( File wkDirPath )
360        {
361            protect( "wkDirPath" );
362            this.wkDirPath = wkDirPath;
363        }
364    
365    
366        /**
367         * Gets the working directory path to something other than the default. Sometimes more
368         * performance is gained by locating indices on separate disk spindles.
369         *
370         * @return optional working directory path 
371         */
372        public File getWkDirPath()
373        {
374            return wkDirPath;
375        }
376    
377    
378        // ------------------------------------------------------------------------
379        // Scan Count Methods
380        // ------------------------------------------------------------------------
381    
382        /**
383         * @see org.apache.directory.server.xdbm.Index#count()
384         */
385        public int count() throws IOException
386        {
387            return forward.count();
388        }
389    
390    
391        /**
392         * @see Index#count(java.lang.Object)
393         */
394        public int count( K attrVal ) throws Exception
395        {
396            return forward.count( getNormalized( attrVal ) );
397        }
398    
399    
400        public int greaterThanCount( K attrVal ) throws Exception
401        {
402            return forward.greaterThanCount( getNormalized( attrVal ) );
403        }
404    
405    
406        /**
407         * @see org.apache.directory.server.xdbm.Index#lessThanCount(java.lang.Object)
408         */
409        public int lessThanCount( K attrVal ) throws Exception
410        {
411            return forward.lessThanCount( getNormalized( attrVal ) );
412        }
413    
414    
415        // ------------------------------------------------------------------------
416        // Forward and Reverse Lookups
417        // ------------------------------------------------------------------------
418    
419        /**
420         * @see Index#forwardLookup(java.lang.Object)
421         */
422        public Long forwardLookup( K attrVal ) throws Exception
423        {
424            return forward.get( getNormalized( attrVal ) );
425        }
426    
427    
428        /**
429         * @see org.apache.directory.server.xdbm.Index#reverseLookup(Long)
430         */
431        public K reverseLookup( Long id ) throws Exception
432        {
433            return reverse.get( id );
434        }
435    
436    
437        // ------------------------------------------------------------------------
438        // Add/Drop Methods
439        // ------------------------------------------------------------------------
440    
441        /**
442         * @see Index#add(Object, Long)
443         */
444        public synchronized void add( K attrVal, Long id ) throws Exception
445        {
446            forward.put( getNormalized( attrVal ), id );
447            reverse.put( id, getNormalized( attrVal ) );
448        }
449    
450    
451        /**
452         * @see Index#drop(Object,Long)
453         */
454        public synchronized void drop( K attrVal, Long id ) throws Exception
455        {
456            forward.remove( getNormalized( attrVal ), id );
457            reverse.remove( id, getNormalized( attrVal ) );
458        }
459    
460    
461        /**
462         * {@inheritDoc}
463         */
464        public void drop( Long entryId ) throws Exception
465        {
466            // Build a cursor to iterate on all the keys referencing
467            // this entryId
468            Cursor<Tuple<Long, K>> values = reverse.cursor( entryId );
469    
470            while ( values.next() )
471            {
472                // Remove the Key -> entryId from the index
473                forward.remove( values.get().getValue(), entryId );
474            }
475    
476            // Remove the id -> key from the reverse index
477            reverse.remove( entryId );
478        }
479    
480    
481        // ------------------------------------------------------------------------
482        // Index Cursor Operations
483        // ------------------------------------------------------------------------
484        @SuppressWarnings("unchecked")
485        public IndexCursor<K, O, Long> reverseCursor() throws Exception
486        {
487            return new IndexCursorAdaptor<K, O, Long>( ( Cursor ) reverse.cursor(), false );
488        }
489    
490    
491        @SuppressWarnings("unchecked")
492        public IndexCursor<K, O, Long> forwardCursor() throws Exception
493        {
494            return new IndexCursorAdaptor<K, O, Long>( ( Cursor ) forward.cursor(), true );
495        }
496    
497    
498        @SuppressWarnings("unchecked")
499        public IndexCursor<K, O, Long> reverseCursor( Long id ) throws Exception
500        {
501            return new IndexCursorAdaptor<K, O, Long>( ( Cursor ) reverse.cursor( id ), false );
502        }
503    
504    
505        @SuppressWarnings("unchecked")
506        public IndexCursor<K, O, Long> forwardCursor( K key ) throws Exception
507        {
508            return new IndexCursorAdaptor<K, O, Long>( ( Cursor ) forward.cursor( key ), true );
509        }
510    
511    
512        public Cursor<K> reverseValueCursor( Long id ) throws Exception
513        {
514            return reverse.valueCursor( id );
515        }
516    
517    
518        public Cursor<Long> forwardValueCursor( K key ) throws Exception
519        {
520            return forward.valueCursor( key );
521        }
522    
523    
524        // ------------------------------------------------------------------------
525        // Value Assertion (a.k.a Index Lookup) Methods //
526        // ------------------------------------------------------------------------
527        /**
528         * @see Index#forward(Object)
529         */
530        public boolean forward( K attrVal ) throws Exception
531        {
532            return forward.has( getNormalized( attrVal ) );
533        }
534    
535    
536        /**
537         * @see Index#forward(Object,Long)
538         */
539        public boolean forward( K attrVal, Long id ) throws Exception
540        {
541            return forward.has( getNormalized( attrVal ), id );
542        }
543    
544    
545        /**
546         * @see Index#reverse(Long)
547         */
548        public boolean reverse( Long id ) throws Exception
549        {
550            return reverse.has( id );
551        }
552    
553    
554        /**
555         * @see Index#reverse(Long,Object)
556         */
557        public boolean reverse( Long id, K attrVal ) throws Exception
558        {
559            return forward.has( getNormalized( attrVal ), id );
560        }
561    
562    
563        /**
564         * @see org.apache.directory.server.xdbm.Index#forwardGreaterOrEq(Object)
565         */
566        public boolean forwardGreaterOrEq( K attrVal ) throws Exception
567        {
568            return forward.hasGreaterOrEqual( getNormalized( attrVal ) );
569        }
570    
571    
572        /**
573         * @see org.apache.directory.server.xdbm.Index#forwardGreaterOrEq(Object, Long)
574         */
575        public boolean forwardGreaterOrEq( K attrVal, Long id ) throws Exception
576        {
577            return forward.hasGreaterOrEqual( getNormalized( attrVal ), id );
578        }
579    
580    
581        /**
582         * @see org.apache.directory.server.xdbm.Index#forwardLessOrEq(Object)
583         */
584        public boolean forwardLessOrEq( K attrVal ) throws Exception
585        {
586            return forward.hasLessOrEqual( getNormalized( attrVal ) );
587        }
588    
589    
590        /**
591         * @see org.apache.directory.server.xdbm.Index#forwardLessOrEq(Object, Long)
592         */
593        public boolean forwardLessOrEq( K attrVal, Long id ) throws Exception
594        {
595            return forward.hasLessOrEqual( getNormalized( attrVal ), id );
596        }
597    
598    
599        /**
600         * @see org.apache.directory.server.xdbm.Index#reverseGreaterOrEq(Long)
601         */
602        public boolean reverseGreaterOrEq( Long id ) throws Exception
603        {
604            return reverse.hasGreaterOrEqual( id );
605        }
606    
607    
608        /**
609         * @see org.apache.directory.server.xdbm.Index#reverseGreaterOrEq(Long,Object)
610         */
611        public boolean reverseGreaterOrEq( Long id, K attrVal ) throws Exception
612        {
613            return reverse.hasGreaterOrEqual( id, getNormalized( attrVal ) );
614        }
615    
616    
617        /**
618         * @see org.apache.directory.server.xdbm.Index#reverseLessOrEq(Long)
619         */
620        public boolean reverseLessOrEq( Long id ) throws Exception
621        {
622            return reverse.hasLessOrEqual( id );
623        }
624    
625    
626        /**
627         * @see org.apache.directory.server.xdbm.Index#reverseLessOrEq(Long,Object)
628         */
629        public boolean reverseLessOrEq( Long id, K attrVal ) throws Exception
630        {
631            return reverse.hasLessOrEqual( id, getNormalized( attrVal ) );
632        }
633    
634    
635        // ------------------------------------------------------------------------
636        // Maintenance Methods 
637        // ------------------------------------------------------------------------
638        /**
639         * @see org.apache.directory.server.xdbm.Index#close()
640         */
641        public synchronized void close() throws IOException
642        {
643            if ( forward != null )
644            {
645                forward.close();
646            }
647    
648            if ( reverse != null )
649            {
650                reverse.close();
651            }
652    
653            recMan.commit();
654            recMan.close();
655        }
656    
657    
658        /**
659         * @see Index#sync()
660         */
661        public synchronized void sync() throws IOException
662        {
663            recMan.commit();
664        }
665    
666    
667        /**
668         * TODO I don't think the keyCache is required anymore since the normalizer
669         * will cache values for us.
670         */
671        @SuppressWarnings("unchecked")
672        public K getNormalized( K attrVal ) throws Exception
673        {
674            if ( attrVal instanceof Long )
675            {
676                return attrVal;
677            }
678    
679            K normalized = ( K ) keyCache.get( attrVal );
680    
681            if ( null == normalized )
682            {
683                if ( attrVal instanceof String )
684                {
685                    normalized = ( K ) attribute.getEquality().getNormalizer().normalize( ( String ) attrVal );
686                }
687                else
688                {
689                    normalized = ( K ) attribute.getEquality().getNormalizer().normalize(
690                        new BinaryValue( ( byte[] ) attrVal ) ).get();
691                }
692    
693                // Double map it so if we use an already normalized
694                // value we can get back the same normalized value.
695                // and not have to regenerate a second time.
696                keyCache.put( attrVal, normalized );
697                keyCache.put( normalized, normalized );
698            }
699    
700            return normalized;
701        }
702    
703    
704        /**
705         * @see Object#toString()
706         */
707        public String toString()
708        {
709            return "Index<" + attributeId + ">";
710        }
711    }