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.avl;
021    
022    
023    import java.io.File;
024    
025    import org.apache.directory.server.core.partition.impl.btree.IndexCursorAdaptor;
026    import org.apache.directory.server.core.partition.impl.btree.LongComparator;
027    import org.apache.directory.server.i18n.I18n;
028    import org.apache.directory.server.xdbm.Index;
029    import org.apache.directory.server.xdbm.IndexCursor;
030    import org.apache.directory.server.xdbm.Tuple;
031    import org.apache.directory.shared.ldap.cursor.Cursor;
032    import org.apache.directory.shared.ldap.entry.BinaryValue;
033    import org.apache.directory.shared.ldap.schema.AttributeType;
034    import org.apache.directory.shared.ldap.schema.LdapComparator;
035    import org.apache.directory.shared.ldap.schema.MatchingRule;
036    import org.apache.directory.shared.ldap.schema.Normalizer;
037    
038    
039    /**
040     * An Index backed by an AVL Tree.
041     *
042     * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
043     * @version $Rev$, $Date$
044     */
045    public class AvlIndex<K, O> implements Index<K, O, Long>
046    {
047        private Normalizer normalizer;
048        private AttributeType attributeType;
049        private AvlTable<K, Long> forward;
050        private AvlTable<Long, K> reverse;
051        private String attributeId;
052    
053    
054        public AvlIndex()
055        {
056        }
057    
058    
059        public AvlIndex( String attributeId )
060        {
061            setAttributeId( attributeId );
062        }
063    
064    
065        void initialize( AttributeType attributeType ) throws Exception
066        {
067            this.attributeType = attributeType;
068    
069            MatchingRule mr = attributeType.getEquality();
070    
071            if ( mr == null )
072            {
073                mr = attributeType.getOrdering();
074            }
075    
076            if ( mr == null )
077            {
078                mr = attributeType.getSubstring();
079            }
080    
081            normalizer = mr.getNormalizer();
082    
083            if ( normalizer == null )
084            {
085                throw new Exception( I18n.err( I18n.ERR_212, attributeType ) );
086            }
087    
088            LdapComparator<K> comp = ( LdapComparator<K> ) mr.getLdapComparator();
089    
090            /*
091             * The forward key/value map stores attribute values to master table 
092             * primary keys.  A value for an attribute can occur several times in
093             * different entries so the forward map can have more than one value.
094             */
095            forward = new AvlTable<K, Long>( attributeType.getName(), comp, LongComparator.INSTANCE, true );
096    
097            /*
098             * Now the reverse map stores the primary key into the master table as
099             * the key and the values of attributes as the value.  If an attribute
100             * is single valued according to its specification based on a schema 
101             * then duplicate keys should not be allowed within the reverse table.
102             */
103            if ( attributeType.isSingleValued() )
104            {
105                reverse = new AvlTable<Long, K>( attributeType.getName(), LongComparator.INSTANCE, comp, false );
106            }
107            else
108            {
109                reverse = new AvlTable<Long, K>( attributeType.getName(), LongComparator.INSTANCE, comp, true );
110            }
111        }
112    
113    
114        public void add( K attrVal, Long id ) throws Exception
115        {
116            forward.put( getNormalized( attrVal ), id );
117            reverse.put( id, getNormalized( attrVal ) );
118        }
119    
120    
121        /**
122         * {@inheritDoc}
123         */
124        public void close() throws Exception
125        {
126            forward.close();
127            reverse.close();
128        }
129    
130    
131        /**
132         * {@inheritDoc}
133         */
134        public int count() throws Exception
135        {
136            return forward.count();
137        }
138    
139    
140        /**
141         * {@inheritDoc}
142         */
143        public int count( K attrVal ) throws Exception
144        {
145            return forward.count( getNormalized( attrVal ) );
146        }
147    
148    
149        /**
150         * {@inheritDoc}
151         */
152        public void drop( Long id ) throws Exception
153        {
154            Cursor<Tuple<Long, K>> cursor = reverse.cursor( id );
155    
156            while ( cursor.next() )
157            {
158                Tuple<Long, K> tuple = cursor.get();
159                forward.remove( tuple.getValue(), id );
160            }
161    
162            reverse.remove( id );
163        }
164    
165    
166        /**
167         * {@inheritDoc}
168         */
169        public void drop( K attrVal, Long id ) throws Exception
170        {
171            forward.remove( getNormalized( attrVal ), id );
172            reverse.remove( id, getNormalized( attrVal ) );
173        }
174    
175    
176        /**
177         * {@inheritDoc}
178         */
179        public boolean forward( K attrVal ) throws Exception
180        {
181            return forward.has( getNormalized( attrVal ) );
182        }
183    
184    
185        /**
186         * {@inheritDoc}
187         */
188        public boolean forward( K attrVal, Long id ) throws Exception
189        {
190            return forward.has( getNormalized( attrVal ), id );
191        }
192    
193    
194        /**
195         * {@inheritDoc}
196         */
197        @SuppressWarnings("unchecked")
198        public IndexCursor<K, O, Long> forwardCursor() throws Exception
199        {
200            return new IndexCursorAdaptor( forward.cursor(), true );
201        }
202    
203    
204        /**
205         * {@inheritDoc}
206         */
207        @SuppressWarnings("unchecked")
208        public IndexCursor<K, O, Long> forwardCursor( K key ) throws Exception
209        {
210            return new IndexCursorAdaptor( forward.cursor( key ), true );
211        }
212    
213    
214        /**
215         * {@inheritDoc}
216         */
217        public boolean forwardGreaterOrEq( K attrVal ) throws Exception
218        {
219            return forward.hasGreaterOrEqual( getNormalized( attrVal ) );
220        }
221    
222    
223        /**
224         * {@inheritDoc}
225         */
226        public boolean forwardGreaterOrEq( K attrVal, Long id ) throws Exception
227        {
228            return forward.hasGreaterOrEqual( getNormalized( attrVal ), id );
229        }
230    
231    
232        /**
233         * {@inheritDoc}
234         */
235        public boolean forwardLessOrEq( K attrVal ) throws Exception
236        {
237            return forward.hasLessOrEqual( getNormalized( attrVal ) );
238        }
239    
240    
241        /**
242         * {@inheritDoc}
243         */
244        public boolean forwardLessOrEq( K attrVal, Long id ) throws Exception
245        {
246            return forward.hasLessOrEqual( getNormalized( attrVal ), id );
247        }
248    
249    
250        /**
251         * {@inheritDoc}
252         */
253        public Long forwardLookup( K attrVal ) throws Exception
254        {
255            return forward.get( getNormalized( attrVal ) );
256        }
257    
258    
259        /**
260         * {@inheritDoc}
261         */
262        public Cursor<Long> forwardValueCursor( K key ) throws Exception
263        {
264            return forward.valueCursor( key );
265        }
266    
267    
268        /**
269         * {@inheritDoc}
270         */
271        public AttributeType getAttribute()
272        {
273            return attributeType;
274        }
275    
276    
277        /**
278         * {@inheritDoc}
279         */
280        public String getAttributeId()
281        {
282            return attributeId;
283        }
284    
285    
286        /**
287         * {@inheritDoc}
288         */
289        @SuppressWarnings("unchecked")
290        public K getNormalized( K attrVal ) throws Exception
291        {
292            if ( attrVal instanceof Long )
293            {
294                return attrVal;
295            }
296    
297            if ( attrVal instanceof String )
298            {
299                return ( K ) normalizer.normalize( ( String ) attrVal );
300            }
301            else
302            {
303                return ( K ) normalizer.normalize( new BinaryValue( ( byte[] ) attrVal ) ).get();
304            }
305        }
306    
307    
308        /**
309         * {@inheritDoc}
310         */
311        public int greaterThanCount( K attrVal ) throws Exception
312        {
313            return forward.greaterThanCount( getNormalized( attrVal ) );
314        }
315    
316    
317        /**
318         * {@inheritDoc}
319         */
320        public boolean isCountExact()
321        {
322            return false;
323        }
324    
325    
326        /**
327         * {@inheritDoc}
328         */
329        public int lessThanCount( K attrVal ) throws Exception
330        {
331            return forward.lessThanCount( getNormalized( attrVal ) );
332        }
333    
334    
335        /**
336         * {@inheritDoc}
337         */
338        public boolean reverse( Long id ) throws Exception
339        {
340            return reverse.has( id );
341        }
342    
343    
344        /**
345         * {@inheritDoc}
346         */
347        public boolean reverse( Long id, K attrVal ) throws Exception
348        {
349            return reverse.has( id, getNormalized( attrVal ) );
350        }
351    
352    
353        /**
354         * {@inheritDoc}
355         */
356        @SuppressWarnings("unchecked")
357        public IndexCursor<K, O, Long> reverseCursor() throws Exception
358        {
359            return new IndexCursorAdaptor( reverse.cursor(), false );
360        }
361    
362    
363        /**
364         * {@inheritDoc}
365         */
366        @SuppressWarnings("unchecked")
367        public IndexCursor<K, O, Long> reverseCursor( Long id ) throws Exception
368        {
369            return new IndexCursorAdaptor( reverse.cursor( id ), false );
370        }
371    
372    
373        /**
374         * {@inheritDoc}
375         */
376        public boolean reverseGreaterOrEq( Long id ) throws Exception
377        {
378            return reverse.hasGreaterOrEqual( id );
379        }
380    
381    
382        /**
383         * {@inheritDoc}
384         */
385        public boolean reverseGreaterOrEq( Long id, K attrVal ) throws Exception
386        {
387            return reverse.hasGreaterOrEqual( id, getNormalized( attrVal ) );
388        }
389    
390    
391        /**
392         * {@inheritDoc}
393         */
394        public boolean reverseLessOrEq( Long id ) throws Exception
395        {
396            return reverse.hasLessOrEqual( id );
397        }
398    
399    
400        /**
401         * {@inheritDoc}
402         */
403        public boolean reverseLessOrEq( Long id, K attrVal ) throws Exception
404        {
405            return reverse.hasLessOrEqual( id, getNormalized( attrVal ) );
406        }
407    
408    
409        /**
410         * {@inheritDoc}
411         */
412        public K reverseLookup( Long id ) throws Exception
413        {
414            return reverse.get( id );
415        }
416    
417    
418        /**
419         * {@inheritDoc}
420         */
421        public Cursor<K> reverseValueCursor( Long id ) throws Exception
422        {
423            return reverse.valueCursor( id );
424        }
425    
426    
427        /**
428         * {@inheritDoc}
429         */
430        public void setAttributeId( String attributeId )
431        {
432            this.attributeId = attributeId;
433        }
434    
435    
436        /**
437         * throws UnsupportedOperationException cause it is a in-memory index
438         */
439        public void setWkDirPath( File wkDirPath )
440        {
441            throw new UnsupportedOperationException( I18n.err( I18n.ERR_213 ) );
442        }
443    
444    
445        /**
446         * this method always returns null for AvlIndex cause this is a in-memory index.
447         */
448        public File getWkDirPath()
449        {
450            return null;
451        }
452    
453    
454        /**
455         * throws UnsupportedOperationException cause it is a in-memory index
456         */
457        public void setCacheSize( int cacheSize )
458        {
459            throw new UnsupportedOperationException( I18n.err( I18n.ERR_214 ) );
460        }
461    
462    
463        public int getCacheSize()
464        {
465            return 0;
466        }
467    
468    
469        /**
470         * {@inheritDoc}
471         */
472        public void sync() throws Exception
473        {
474        }
475    }