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.btree.BTree;
24  
25  import org.apache.directory.server.core.avltree.AvlTree;
26  import org.apache.directory.server.core.avltree.AvlTreeCursor;
27  import org.apache.directory.server.core.cursor.Cursor;
28  import org.apache.directory.server.core.cursor.InvalidCursorPositionException;
29  import org.apache.directory.server.xdbm.Tuple;
30  import org.apache.directory.server.xdbm.AbstractTupleCursor;
31  import org.slf4j.Logger;
32  import org.slf4j.LoggerFactory;
33  
34  
35  /**
36   * A Cursor over a BTree which manages duplicate keys.
37   *
38   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
39   * @version $Rev$
40   */
41  class DupsCursor<K,V> extends AbstractTupleCursor<K,V>
42  {
43      private static final Logger LOG = LoggerFactory.getLogger( DupsCursor.class.getSimpleName() );
44      
45      /**
46       * The JDBM backed table this Cursor traverses over.
47       */
48      private final JdbmTable<K,V> table;
49  
50      /**
51       * An wrappedCursor Cursor which returns Tuples whose values are
52       * DupsContainer objects representing either AvlTrees or BTreeRedirect
53       * objects used to store the values of duplicate keys.  It does not return
54       * different values for the same key.
55       */
56      private final DupsContainerCursor<K,V> containerCursor;
57  
58      /**
59       * The current Tuple returned from the wrappedCursor DupsContainerCursor.
60       */
61      private final Tuple<K,DupsContainer<V>> containerTuple = new Tuple<K, DupsContainer<V>>();
62  
63      /**
64       * A Cursor over a set of value objects for the current key held in the
65       * containerTuple.  A new Cursor will be set for each new key as we
66       * traverse.  The Cursor traverses over either a AvlTree object full
67       * of values in a multi-valued key or it traverses over a BTree which
68       * contains the values in the key field of it's Tuples.
69       */
70      private Cursor<V> dupsCursor;
71  
72      /**
73       * The Tuple that is used to return values via the get() method. This
74       * same Tuple instance will be returned every time.  At different
75       * positions it may return different values for the same key.
76       */
77      private final Tuple<K,V> returnedTuple = new Tuple<K,V>();
78  
79      /**
80       * Whether or not a value is available when get() is called.
81       */
82      private boolean valueAvailable;
83  
84  
85      public DupsCursor( JdbmTable<K,V> table ) throws Exception
86      {
87          this.table = table;
88          this.containerCursor = new DupsContainerCursor<K,V>( table );
89          LOG.debug( "Created on table {}", table );
90      }
91  
92  
93      public boolean available()
94      {
95          return valueAvailable;
96      }
97  
98  
99      public void beforeKey( K key ) throws Exception
100     {
101         beforeValue( key, null );
102     }
103 
104 
105     public void beforeValue( K key, V value ) throws Exception
106     {
107         checkNotClosed( "beforeValue()" );
108         containerCursor.before( new Tuple<K,DupsContainer<V>>( key, null ) );
109 
110         if ( containerCursor.next() )
111         {
112             containerTuple.setBoth( containerCursor.get() );
113             DupsContainer<V> values = containerTuple.getValue();
114 
115             if ( values.isAvlTree() )
116             {
117                 AvlTree<V> set = values.getAvlTree();
118                 dupsCursor = new AvlTreeCursor<V>( set );
119             }
120             else
121             {
122                 BTree tree = table.getBTree( values.getBTreeRedirect() );
123                 dupsCursor = new KeyBTreeCursor<V>( tree, table.getValueComparator() );
124             }
125 
126             if ( value == null )
127             {
128                 return;
129             }
130 
131             // advance the dupsCursor only if we're on same key
132             if ( table.getKeyComparator().compare( containerTuple.getKey(), key ) == 0 )
133             {
134                 dupsCursor.before( value );
135             }
136 
137             return;
138         }
139 
140         clearValue();
141         containerTuple.setKey( null );
142         containerTuple.setValue( null );
143     }
144 
145 
146     public void afterKey( K key ) throws Exception
147     {
148         afterValue( key, null );
149     }
150 
151 
152     public void afterValue( K key, V value ) throws Exception
153     {
154         checkNotClosed( "afterValue()" );
155         /*
156          * There is a subtle difference between after and before handling
157          * with dupicate key values.  Say we have the following tuples:
158          *
159          * (0, 0)
160          * (1, 1)
161          * (1, 2)
162          * (1, 3)
163          * (2, 2)
164          *
165          * If we request an after cursor on (1, 2).  We must make sure that
166          * the container cursor does not advance after the entry with key 1
167          * since this would result in us skip returning (1. 3) on the call to
168          * next which will incorrectly return (2, 2) instead.
169          *
170          * So if the value is null in the element then we don't care about
171          * this obviously since we just want to advance past the duplicate key
172          * values all together.  But when it is not null, then we want to
173          * go right before this key instead of after it.
174          */
175 
176         if ( value == null )
177         {
178             containerCursor.after( new Tuple<K,DupsContainer<V>>( key, null ) );
179         }
180         else
181         {
182             containerCursor.before( new Tuple<K,DupsContainer<V>>( key, null ) );
183         }
184 
185         if ( containerCursor.next() )
186         {
187             containerTuple.setBoth( containerCursor.get() );
188             DupsContainer<V> values = containerTuple.getValue();
189 
190             if ( values.isAvlTree() )
191             {
192                 AvlTree<V> set = values.getAvlTree();
193                 dupsCursor = new AvlTreeCursor<V>( set );
194             }
195             else
196             {
197                 BTree tree = table.getBTree( values.getBTreeRedirect() );
198                 dupsCursor = new KeyBTreeCursor<V>( tree, table.getValueComparator() );
199             }
200 
201             if ( value == null )
202             {
203                 return;
204             }
205 
206             // only advance the dupsCursor if we're on same key
207             if ( table.getKeyComparator().compare( containerTuple.getKey(), key ) == 0 )
208             {
209                 dupsCursor.after( value );
210             }
211 
212             return;
213         }
214 
215         clearValue();
216         containerTuple.setKey( null );
217         containerTuple.setValue( null );
218     }
219 
220 
221     public void before( Tuple<K,V> element ) throws Exception
222     {
223         beforeValue( element.getKey(), element.getValue() );
224     }
225 
226 
227     public void after( Tuple<K,V> element ) throws Exception
228     {
229         afterValue( element.getKey(), element.getValue() );
230     }
231 
232 
233     public void beforeFirst() throws Exception
234     {
235         checkNotClosed( "beforeFirst()" );
236         clearValue();
237         containerCursor.beforeFirst();
238         containerTuple.setKey( null );
239         containerTuple.setValue( null );
240         dupsCursor = null;
241     }
242 
243 
244     public void afterLast() throws Exception
245     {
246         checkNotClosed( "afterLast()" );
247         clearValue();
248         containerCursor.afterLast();
249         containerTuple.setKey( null );
250         containerTuple.setValue( null );
251         dupsCursor = null;
252     }
253 
254 
255     public boolean first() throws Exception
256     {
257         checkNotClosed( "first()" );
258         clearValue();
259         dupsCursor = null;
260 
261         if ( containerCursor.first() )
262         {
263             containerTuple.setBoth( containerCursor.get() );
264             DupsContainer<V> values = containerTuple.getValue();
265 
266             if ( containerTuple.getValue().isAvlTree() )
267             {
268                 dupsCursor = new AvlTreeCursor<V>( values.getAvlTree() );
269             }
270             else
271             {
272                 BTree bt = table.getBTree( values.getBTreeRedirect() );
273                 dupsCursor = new KeyBTreeCursor<V>( bt, table.getValueComparator() );
274             }
275 
276             /*
277              * Since only tables with duplicate keys enabled use this
278              * cursor, entries must have at least one value, and therefore
279              * call to last() will always return true.
280              */
281             dupsCursor.first();
282             valueAvailable =  true;
283             returnedTuple.setKey( containerTuple.getKey() );
284             returnedTuple.setValue( dupsCursor.get() );
285             return true;
286         }
287 
288         return false;
289     }
290 
291 
292     public boolean last() throws Exception
293     {
294         checkNotClosed( "last()" );
295         clearValue();
296         dupsCursor = null;
297 
298         if ( containerCursor.last() )
299         {
300             containerTuple.setBoth( containerCursor.get() );
301             DupsContainer<V> values = containerTuple.getValue();
302 
303             if ( values.isAvlTree() )
304             {
305                 AvlTree<V> set = values.getAvlTree();
306                 dupsCursor = new AvlTreeCursor<V>( set );
307             }
308             else
309             {
310                 BTree tree = table.getBTree( values.getBTreeRedirect() );
311                 dupsCursor = new KeyBTreeCursor<V>( tree, table.getValueComparator() );
312             }
313 
314             /*
315              * Since only tables with duplicate keys enabled use this
316              * cursor, entries must have at least one value, and therefore
317              * call to last() will always return true.
318              */
319             dupsCursor.last();
320             valueAvailable = true;
321             returnedTuple.setKey( containerTuple.getKey() );
322             returnedTuple.setValue( dupsCursor.get() );
323             return true;
324         }
325 
326         return false;
327     }
328 
329 
330 
331     private void clearValue()
332     {
333         returnedTuple.setKey( null );
334         returnedTuple.setValue( null );
335         valueAvailable = false;
336     }
337 
338 
339     public boolean previous() throws Exception
340     {
341         checkNotClosed( "previous()" );
342         /*
343          * If the iterator over the values of the current key is null or is
344          * extinguished then we need to advance to the previous key.
345          */
346         if ( null == dupsCursor || ! dupsCursor.previous() )
347         {
348             /*
349              * If the wrappedCursor cursor has more elements we get the previous
350              * key/AvlTree Tuple to work with and get a cursor over it's
351              * values.
352              */
353             if ( containerCursor.previous() )
354             {
355                 containerTuple.setBoth( containerCursor.get() );
356                 DupsContainer<V> values = containerTuple.getValue();
357 
358                 if ( values.isAvlTree() )
359                 {
360                     AvlTree<V> set = values.getAvlTree();
361                     dupsCursor = new AvlTreeCursor<V>( set );
362                 }
363                 else
364                 {
365                     BTree tree = table.getBTree( values.getBTreeRedirect() );
366                     dupsCursor = new KeyBTreeCursor<V>( tree, table.getValueComparator() );
367                 }
368 
369                 /*
370                  * Since only tables with duplicate keys enabled use this
371                  * cursor, entries must have at least one value, and therefore
372                  * call to previous() after bringing the cursor to afterLast()
373                  * will always return true.
374                  */
375                 dupsCursor.afterLast();
376                 dupsCursor.previous();
377             }
378             else
379             {
380                 dupsCursor = null;
381                 return false;
382             }
383         }
384 
385         returnedTuple.setKey( containerTuple.getKey() );
386         returnedTuple.setValue( dupsCursor.get() );
387         return valueAvailable = true;
388     }
389 
390 
391     public boolean next() throws Exception
392     {
393         checkNotClosed( "next()" );
394         /*
395          * If the iterator over the values of the current key is null or is
396          * extinguished then we need to advance to the next key.
397          */
398         if ( null == dupsCursor || ! dupsCursor.next() )
399         {
400             /*
401              * If the wrappedCursor cursor has more elements we get the next
402              * key/AvlTree Tuple to work with and get a cursor over it.
403              */
404             if ( containerCursor.next() )
405             {
406                 containerTuple.setBoth( containerCursor.get() );
407                 DupsContainer<V> values = containerTuple.getValue();
408 
409                 if ( values.isAvlTree() )
410                 {
411                     AvlTree<V> set = values.getAvlTree();
412                     dupsCursor = new AvlTreeCursor<V>( set );
413                 }
414                 else
415                 {
416                     BTree tree = table.getBTree( values.getBTreeRedirect() );
417                     dupsCursor = new KeyBTreeCursor<V>( tree, table.getValueComparator() );
418                 }
419 
420                 /*
421                  * Since only tables with duplicate keys enabled use this
422                  * cursor, entries must have at least one value, and therefore
423                  * call to next() after bringing the cursor to beforeFirst()
424                  * will always return true.
425                  */
426                 dupsCursor.beforeFirst();
427                 dupsCursor.next();
428             }
429             else
430             {
431                 dupsCursor = null;
432                 return false;
433             }
434         }
435 
436         /*
437          * If we get to this point then cursor has more elements and
438          * containerTuple holds the Tuple containing the key and the btree or
439          * AvlTree of values for that key which the Cursor traverses.  All we
440          * need to do is populate our tuple object with the key and the value
441          * in the cursor.
442          */
443         returnedTuple.setKey( containerTuple.getKey() );
444         returnedTuple.setValue( dupsCursor.get() );
445         return valueAvailable = true;
446     }
447 
448 
449     public Tuple<K,V> get() throws Exception
450     {
451         checkNotClosed( "get()" );
452 
453         if ( ! valueAvailable )
454         {
455             throw new InvalidCursorPositionException();
456         }
457 
458         return returnedTuple;
459     }
460 
461 
462     public boolean isElementReused()
463     {
464         return true;
465     }
466 }