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 */
020package org.apache.directory.server.xdbm.impl.avl;
021
022
023import java.util.Comparator;
024
025import org.apache.directory.api.ldap.model.cursor.Cursor;
026import org.apache.directory.api.ldap.model.cursor.EmptyCursor;
027import org.apache.directory.api.ldap.model.cursor.SingletonCursor;
028import org.apache.directory.api.ldap.model.cursor.Tuple;
029import org.apache.directory.api.ldap.model.exception.LdapException;
030import org.apache.directory.server.core.api.partition.PartitionTxn;
031import org.apache.directory.server.core.avltree.AvlSingletonOrOrderedSetCursor;
032import org.apache.directory.server.core.avltree.AvlTree;
033import org.apache.directory.server.core.avltree.AvlTreeCursor;
034import org.apache.directory.server.core.avltree.AvlTreeMap;
035import org.apache.directory.server.core.avltree.AvlTreeMapImpl;
036import org.apache.directory.server.core.avltree.AvlTreeMapNoDupsWrapperCursor;
037import org.apache.directory.server.core.avltree.KeyTupleAvlCursor;
038import org.apache.directory.server.core.avltree.LinkedAvlMapNode;
039import org.apache.directory.server.core.avltree.SingletonOrOrderedSet;
040import org.apache.directory.server.xdbm.AbstractTable;
041
042
043/**
044 * A Table implementation backed by in memory AVL tree.
045 *
046 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
047 */
048public class AvlTable<K, V> extends AbstractTable<K, V>
049{
050    private final AvlTreeMap<K, V> avl;
051    private final Comparator<Tuple<K, V>> keyOnlytupleComparator;
052
053
054    public AvlTable( String name, final Comparator<K> keyComparator, final Comparator<V> valueComparator,
055        boolean dupsEnabled )
056    {
057        super( null, name, keyComparator, valueComparator );
058        this.avl = new AvlTreeMapImpl<>( keyComparator, valueComparator, dupsEnabled );
059        allowsDuplicates = this.avl.isDupsAllowed();
060        this.keyOnlytupleComparator = new Comparator<Tuple<K, V>>()
061        {
062            public int compare( Tuple<K, V> t0, Tuple<K, V> t1 )
063            {
064                return keyComparator.compare( t0.getKey(), t1.getKey() );
065            }
066        };
067    }
068
069
070    /**
071     * {@inheritDoc}
072     */
073    @Override
074    public void close( PartitionTxn transaction ) throws LdapException
075    {
076        ( ( AvlTreeMapImpl<K, V> ) avl ).removeAll();
077    }
078
079
080    /**
081     * {@inheritDoc}
082     */
083    @Override
084    public long count( PartitionTxn transaction, K key ) throws LdapException
085    {
086        if ( key == null )
087        {
088            return 0L;
089        }
090
091        LinkedAvlMapNode<K, V> node = avl.find( key );
092
093        if ( node == null )
094        {
095            return 0L;
096        }
097
098        SingletonOrOrderedSet<V> val = node.getValue();
099
100        if ( val.isOrderedSet() )
101        {
102            return val.getOrderedSet().getSize();
103        }
104
105        return 1L;
106    }
107
108
109    /**
110     * {@inheritDoc}
111     */
112    @Override
113    public V get( PartitionTxn transaction, K key ) throws LdapException
114    {
115        if ( key == null )
116        {
117            return null;
118        }
119
120        LinkedAvlMapNode<K, V> node = avl.find( key );
121
122        if ( node == null )
123        {
124            return null;
125        }
126
127        SingletonOrOrderedSet<V> val = node.getValue();
128
129        if ( val.isOrderedSet() )
130        {
131            return val.getOrderedSet().getFirst().getKey();
132        }
133
134        return val.getSingleton();
135    }
136
137
138    /**
139     * {@inheritDoc}
140     */
141    @Override
142    public long greaterThanCount( PartitionTxn transaction, K key ) throws LdapException
143    {
144        return avl.getSize();
145    }
146
147
148    /**
149     * {@inheritDoc}
150     */
151    @Override
152    public boolean has( PartitionTxn transaction, K key ) throws LdapException
153    {
154        if ( key == null )
155        {
156            return false;
157        }
158
159        return avl.find( key ) != null;
160    }
161
162
163    /**
164     * {@inheritDoc}
165     */
166    @Override
167    public boolean has( PartitionTxn transaction, K key, V value ) throws LdapException
168    {
169        if ( key == null )
170        {
171            return false;
172        }
173
174        return avl.find( key, value ) != null;
175    }
176
177
178    /**
179     * {@inheritDoc}
180     */
181    @Override
182    public boolean hasGreaterOrEqual( PartitionTxn transaction, K key ) throws LdapException
183    {
184        if ( key == null )
185        {
186            return false;
187        }
188
189        return avl.findGreaterOrEqual( key ) != null;
190    }
191
192
193    /**
194     * {@inheritDoc}
195     */
196    @Override
197    public boolean hasGreaterOrEqual( PartitionTxn transaction, K key, V val ) throws LdapException
198    {
199        if ( key == null )
200        {
201            return false;
202        }
203
204        LinkedAvlMapNode<K, V> node = avl.findGreaterOrEqual( key );
205
206        if ( node == null )
207        {
208            return false;
209        }
210
211        if ( node.getValue().isOrderedSet() )
212        {
213            AvlTree<V> values = node.getValue().getOrderedSet();
214            return values.findGreaterOrEqual( val ) != null;
215        }
216
217        return valueComparator.compare( node.getValue().getSingleton(), val ) >= 0;
218    }
219
220
221    /**
222     * {@inheritDoc}
223     */
224    @Override
225    public boolean hasLessOrEqual( PartitionTxn transaction, K key ) throws LdapException
226    {
227        if ( key == null )
228        {
229            return false;
230        }
231
232        return avl.findLessOrEqual( key ) != null;
233    }
234
235
236    /**
237     * {@inheritDoc}
238     */
239    @Override
240    public boolean hasLessOrEqual( PartitionTxn transaction, K key, V val ) throws LdapException
241    {
242        if ( key == null )
243        {
244            return false;
245        }
246
247        LinkedAvlMapNode<K, V> node = avl.findLessOrEqual( key );
248
249        if ( node == null )
250        {
251            return false;
252        }
253
254        if ( node.getValue().isOrderedSet() )
255        {
256            AvlTree<V> values = node.getValue().getOrderedSet();
257            return values.findLessOrEqual( val ) != null;
258        }
259
260        return valueComparator.compare( node.getValue().getSingleton(), val ) <= 0;
261    }
262
263
264    /**
265     * {@inheritDoc}
266     */
267    @Override
268    public long lessThanCount( PartitionTxn transaction, K key ) throws LdapException
269    {
270        return count;
271    }
272
273
274    /**
275     * {@inheritDoc}
276     */
277    @Override
278    public void put( PartitionTxn partitionTxn, K key, V value ) throws LdapException
279    {
280        if ( ( key == null ) || ( value == null ) )
281        {
282            return;
283        }
284
285        if ( avl.insert( key, value ) == null )
286        {
287            count++;
288        }
289    }
290
291
292    /**
293     * {@inheritDoc}
294     */
295    @Override
296    public void remove( PartitionTxn partitionTxn, K key ) throws LdapException
297    {
298        if ( key == null )
299        {
300            return;
301        }
302
303        SingletonOrOrderedSet<V> value = avl.remove( key );
304
305        if ( value == null )
306        {
307            return;
308        }
309
310        if ( value.isOrderedSet() )
311        {
312            count -= value.getOrderedSet().getSize();
313        }
314        else
315        {
316            count--;
317        }
318    }
319
320
321    /**
322     * {@inheritDoc}
323     */
324    @Override
325    public void remove( PartitionTxn partitionTxn, K key, V value ) throws LdapException
326    {
327        if ( avl.remove( key, value ) != null )
328        {
329            count--;
330        }
331    }
332
333
334    /**
335     * {@inheritDoc}
336     */
337    @Override
338    public Cursor<Tuple<K, V>> cursor()
339    {
340        if ( !allowsDuplicates )
341        {
342            return new AvlTreeMapNoDupsWrapperCursor<>(
343                new AvlSingletonOrOrderedSetCursor<K, V>( avl ) );
344        }
345
346        return new AvlTableDupsCursor<>( this );
347    }
348
349
350    /**
351     * {@inheritDoc}
352     */
353    @Override
354    public Cursor<Tuple<K, V>> cursor( PartitionTxn partitionTxn,  K key ) throws LdapException
355    {
356        if ( key == null )
357        {
358            return new EmptyCursor<>();
359        }
360
361        LinkedAvlMapNode<K, V> node = avl.find( key );
362
363        if ( node == null )
364        {
365            return new EmptyCursor<>();
366        }
367
368        if ( node.getValue().isOrderedSet() )
369        {
370            return new KeyTupleAvlCursor<>( node.getValue().getOrderedSet(), key );
371        }
372
373        return new SingletonCursor<>( new Tuple<K, V>( key, node.getValue().getSingleton() ),
374            keyOnlytupleComparator );
375    }
376
377
378    /**
379     * {@inheritDoc}
380     */
381    @Override
382    public Cursor<V> valueCursor( PartitionTxn transaction, K key ) throws LdapException
383    {
384        if ( key == null )
385        {
386            return new EmptyCursor<>();
387        }
388
389        LinkedAvlMapNode<K, V> node = avl.find( key );
390
391        if ( node == null )
392        {
393            return new EmptyCursor<>();
394        }
395
396        if ( node.getValue().isOrderedSet() )
397        {
398            return new AvlTreeCursor<>( node.getValue().getOrderedSet() );
399        }
400
401        return new SingletonCursor<>( node.getValue().getSingleton(), valueComparator );
402    }
403
404
405    /**
406     * Returns the internal AvlTreeMap so other classes like Cursors
407     * in the same package can access it.
408     *
409     * @return AvlTreeMap used to store Tuples
410     */
411    AvlTreeMap<K, V> getAvlTreeMap()
412    {
413        return avl;
414    }
415}