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.mavibot.btree.managed;
21  
22  
23  import static org.apache.directory.mavibot.btree.managed.InternalUtil.changeNextDupsContainer;
24  import static org.apache.directory.mavibot.btree.managed.InternalUtil.changePrevDupsContainer;
25  
26  import java.io.IOException;
27  import java.util.LinkedList;
28  import java.util.NoSuchElementException;
29  
30  import org.apache.directory.mavibot.btree.Tuple;
31  import org.apache.directory.mavibot.btree.TupleCursor;
32  import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
33  
34  
35  /**
36   * A Cursor is used to fetch elements in a BTree and is returned by the
37   * @see BTree#browse method. The cursor <strng>must</strong> be closed
38   * when the user is done with it.
39   * <p>
40   *
41   * @param <K> The type for the Key
42   * @param <V> The type for the stored value
43   * 
44   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
45   */
46  public class CursorImpl<K, V> implements TupleCursor<K, V>
47  {
48      /** The transaction used for this cursor */
49      private Transaction<K, V> transaction;
50  
51      /** The Tuple used to return the results */
52      private Tuple<K, V> tuple = new Tuple<K, V>();
53  
54      /** The stack of pages from the root down to the leaf */
55      private LinkedList<ParentPos<K, V>> stack;
56  
57      /** The BTree we are walking */
58      private BTree<K, V> btree;
59  
60      private boolean allowDuplicates;
61  
62      /** a copy of the stack given at the time of initializing the cursor. This is used for moving the cursor to start position */
63      private LinkedList<ParentPos<K, V>> _initialStack;
64  
65  
66      /**
67       * Creates a new instance of Cursor, starting on a page at a given position.
68       * 
69       * @param transaction The transaction this operation is protected by
70       * @param stack The stack of parent's from root to this page
71       */
72      CursorImpl( BTree<K, V> btree, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
73      {
74          this.transaction = transaction;
75          this.stack = stack;
76          this.btree = btree;
77          this.allowDuplicates = btree.isAllowDuplicates();
78  
79          _initialStack = new LinkedList<ParentPos<K, V>>();
80  
81          cloneStack( stack, _initialStack );
82      }
83  
84  
85      /**
86       * Find the next key/value
87       * 
88       * @return A Tuple containing the found key and value
89       * @throws IOException 
90       * @throws EndOfFileExceededException 
91       */
92      public Tuple<K, V> next() throws EndOfFileExceededException, IOException
93      {
94          ParentPos<K, V> parentPos = stack.getFirst();
95  
96          if ( parentPos.page == null )
97          {
98              // This is the end : no more value
99              throw new NoSuchElementException( "No more tuples present" );
100         }
101 
102         if ( parentPos.pos == parentPos.page.getNbElems() )
103         {
104             // End of the leaf. We have to go back into the stack up to the
105             // parent, and down to the leaf
106             parentPos = findNextParentPos();
107 
108             // we also need to check for the type of page cause
109             // findNextParentPos will never return a null ParentPos
110             if ( parentPos.page == null || ( parentPos.page instanceof Node ) )
111             {
112                 // This is the end : no more value
113                 throw new NoSuchElementException( "No more tuples present" );
114             }
115         }
116 
117         // can happen if next() is called after prev()
118         if ( parentPos.pos < 0 )
119         {
120             parentPos.pos = 0;
121         }
122 
123         Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
124         tuple.setKey( leaf.keys[parentPos.pos].getKey() );
125 
126         ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
127         tuple.setValue( valueHolder.getCursor().next() );
128         parentPos.pos++;
129 
130         return tuple;
131     }
132 
133 
134     /**
135      * Find the leaf containing the following elements.
136      * 
137      * @return the new ParentPos instance, or null if we have no following leaf
138      * @throws IOException 
139      * @throws EndOfFileExceededException 
140      */
141     private ParentPos<K, V> findNextParentPos() throws EndOfFileExceededException, IOException
142     {
143         ParentPos<K, V> lastParentPos = null;
144 
145         while ( true )
146         {
147             // We first go up the tree, until we reach a page whose current position
148             // is not the last one
149             ParentPos<K, V> parentPos = stack.peek();
150 
151             if ( parentPos == null )
152             {
153                 stack.push( lastParentPos );
154                 return lastParentPos;
155             }
156 
157             if ( parentPos.pos == parentPos.page.getNbElems() )
158             {
159                 lastParentPos = stack.pop();
160                 continue;
161             }
162             else
163             {
164                 // Then we go down the tree until we find a leaf which position is not the last one.
165                 int newPos = ++parentPos.pos;
166                 ParentPos<K, V> newParentPos = parentPos;
167 
168                 while ( newParentPos.page instanceof Node )
169                 {
170                     Node<K, V> node = ( Node<K, V> ) newParentPos.page;
171 
172                     newParentPos = new ParentPos<K, V>( node.children[newPos].getValue( btree ), 0 );
173 
174                     stack.push( newParentPos );
175 
176                     newPos = 0;
177                 }
178 
179                 if ( allowDuplicates )
180                 {
181                     changeNextDupsContainer( newParentPos, btree );
182                 }
183 
184                 return newParentPos;
185             }
186         }
187     }
188 
189 
190     /**
191      * Find the leaf containing the previous elements.
192      * 
193      * @return the new ParentPos instance, or null if we have no previous leaf
194      * @throws IOException 
195      * @throws EndOfFileExceededException 
196      */
197     private ParentPos<K, V> findPreviousParentPos() throws EndOfFileExceededException, IOException
198     {
199         ParentPos<K, V> lastParentPos = null;
200 
201         while ( true )
202         {
203             // We first go up the tree, until we reach a page which current position
204             // is not the first one
205             ParentPos<K, V> parentPos = stack.peek();
206 
207             if ( parentPos == null )
208             {
209                 stack.push( lastParentPos );
210                 return lastParentPos;
211             }
212 
213             if ( parentPos.pos == 0 )
214             {
215                 lastParentPos = stack.pop();
216                 continue;
217             }
218             else
219             {
220                 // Then we go down the tree until we find a leaf which position is not the first one.
221                 int newPos = --parentPos.pos;
222                 ParentPos<K, V> newParentPos = parentPos;
223 
224                 while ( newParentPos.page instanceof Node )
225                 {
226                     Node<K, V> node = ( Node<K, V> ) newParentPos.page;
227 
228                     newParentPos = new ParentPos<K, V>( node.children[newPos].getValue( btree ), node.children[newPos]
229                         .getValue( btree ).getNbElems() );
230 
231                     stack.push( newParentPos );
232 
233                     newPos = node.getNbElems();
234                 }
235 
236                 if ( allowDuplicates )
237                 {
238                     changePrevDupsContainer( newParentPos, btree );
239                 }
240 
241                 return newParentPos;
242             }
243         }
244     }
245 
246 
247     /**
248      * Find the previous key/value
249      * 
250      * @return A Tuple containing the found key and value
251      * @throws IOException 
252      * @throws EndOfFileExceededException 
253      */
254     public Tuple<K, V> prev() throws EndOfFileExceededException, IOException
255     {
256         ParentPos<K, V> parentPos = stack.peek();
257 
258         if ( parentPos.page == null )
259         {
260             // This is the end : no more value
261             throw new NoSuchElementException( "No more tuples present" );
262         }
263 
264         if ( parentPos.pos == 0 && parentPos.dupPos == 0 )
265         {
266             // End of the leaf. We have to go back into the stack up to the
267             // parent, and down to the leaf
268             parentPos = findPreviousParentPos();
269 
270             // we also need to check for the type of page cause
271             // findPrevParentPos will never return a null ParentPos
272             if ( parentPos.page == null || ( parentPos.page instanceof Node ) )
273             {
274                 // This is the end : no more value
275                 throw new NoSuchElementException( "No more tuples present" );
276             }
277         }
278 
279         Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
280         ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
281         tuple.setKey( leaf.keys[parentPos.pos].getKey() );
282         tuple.setValue( valueHolder.getCursor().next() );
283 
284         return tuple;
285     }
286 
287 
288     /**
289      * Tells if the cursor can return a next element
290      * @return true if there are some more elements
291      * @throws IOException 
292      * @throws EndOfFileExceededException 
293      */
294     public boolean hasNext() throws EndOfFileExceededException, IOException
295     {
296         ParentPos<K, V> parentPos = stack.peek();
297 
298         if ( parentPos.page == null )
299         {
300             return false;
301         }
302 
303         for ( ParentPos<K, V> p : stack )
304         {
305             if ( allowDuplicates && ( p.page instanceof Leaf ) )
306             {
307                 if ( ( p.dupsContainer == null ) && ( p.pos != p.page.getNbElems() ) )
308                 {
309                     return true;
310                 }
311                 else if ( ( p.dupsContainer != null ) && ( p.dupPos != p.dupsContainer.getNbElems() )
312                     && ( p.pos != p.page.getNbElems() ) )
313                 {
314                     return true;
315                 }
316             }
317             else if ( p.pos != p.page.getNbElems() )
318             {
319                 return true;
320             }
321         }
322 
323         return false;
324     }
325 
326 
327     /**
328      * Tells if the cursor can return a previous element
329      * @return true if there are some more elements
330      * @throws IOException 
331      * @throws EndOfFileExceededException 
332      */
333     public boolean hasPrev() throws EndOfFileExceededException, IOException
334     {
335         ParentPos<K, V> parentPos = stack.peek();
336 
337         if ( parentPos.page == null )
338         {
339             return false;
340         }
341 
342         for ( ParentPos<K, V> p : stack )
343         {
344             if ( allowDuplicates && ( p.page instanceof Leaf ) )
345             {
346                 if ( ( p.dupsContainer == null ) && ( p.pos != 0 ) )
347                 {
348                     return true;
349                 }
350                 else if ( ( p.dupsContainer != null ) &&
351                     ( ( p.dupPos != 0 ) || ( p.pos != 0 ) ) )
352                 {
353                     return true;
354                 }
355             }
356             else if ( p.pos != 0 )
357             {
358                 return true;
359             }
360         }
361 
362         return false;
363     }
364 
365 
366     /**
367      * Closes the cursor, thus releases the associated transaction
368      */
369     public void close()
370     {
371         transaction.close();
372     }
373 
374 
375     /**
376      * @return The revision this cursor is based on
377      */
378     public long getRevision()
379     {
380         return transaction.getRevision();
381     }
382 
383 
384     /**
385      * @return The creation date for this cursor
386      */
387     public long getCreationDate()
388     {
389         return transaction.getCreationDate();
390     }
391 
392 
393     /**
394      * Moves the cursor to the next non-duplicate key.
395 
396      * If the BTree contains 
397      * 
398      *  <ul>
399      *    <li><1,0></li>
400      *    <li><1,1></li>
401      *    <li><2,0></li>
402      *    <li><2,1></li>
403      *  </ul>
404      *   
405      *  and cursor is present at <1,0> then the cursor will move to <2,0>
406      *  
407      * @throws EndOfFileExceededException
408      * @throws IOException
409      */
410     public void moveToNextNonDuplicateKey() throws EndOfFileExceededException, IOException
411     {
412         ParentPos<K, V> parentPos = stack.getFirst();
413 
414         if ( parentPos.page == null )
415         {
416             return;
417         }
418 
419         if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
420         {
421             // End of the leaf. We have to go back into the stack up to the
422             // parent, and down to the leaf
423             // increment the position cause findNextParentPos checks "parentPos.pos == parentPos.page.getNbElems()"
424             parentPos.pos++;
425             ParentPos<K, V> nextPos = findNextParentPos();
426 
427             // if the returned value is a Node OR if it is same as the parentPos
428             // that means cursor is already at the last position
429             // call afterLast() to restore the stack with the path to the right most element
430             if ( ( nextPos.page instanceof Node ) || ( nextPos == parentPos ) )
431             {
432                 afterLast();
433             }
434             else
435             {
436                 parentPos = nextPos;
437             }
438         }
439         else
440         {
441             parentPos.pos++;
442             changeNextDupsContainer( parentPos, btree );
443         }
444     }
445 
446 
447     /**
448      * Moves the cursor to the previous non-duplicate key
449      * If the BTree contains 
450      * 
451      *  <ul>
452      *    <li><1,0></li>
453      *    <li><1,1></li>
454      *    <li><2,0></li>
455      *    <li><2,1></li>
456      *  </ul>
457      *   
458      *  and cursor is present at <2,1> then the cursor will move to <1,1>
459      * 
460      * @throws EndOfFileExceededException
461      * @throws IOException
462      */
463     public void moveToPrevNonDuplicateKey() throws EndOfFileExceededException, IOException
464     {
465         ParentPos<K, V> parentPos = stack.peek();
466 
467         if ( parentPos.page == null )
468         {
469             // This is the end : no more value
470             return;
471         }
472 
473         if ( parentPos.pos == 0 )
474         {
475             // End of the leaf. We have to go back into the stack up to the
476             // parent, and down to the leaf
477             parentPos = findPreviousParentPos();
478 
479             // if the returned value is a Node that means cursor is already at the first position
480             // call beforeFirst() to restore the stack to the initial state
481             if ( parentPos.page instanceof Node )
482             {
483                 beforeFirst();
484             }
485         }
486         else
487         {
488             changePrevDupsContainer( parentPos, btree );
489             parentPos.pos--;
490         }
491     }
492 
493 
494     /**
495      * moves the cursor to the same position that was given at the time of instantiating the cursor.
496      * 
497      *  For example, if the cursor was created using browse() method, then beforeFirst() will
498      *  place the cursor before the 0th position.
499      *  
500      *  If the cursor was created using browseFrom(K), then calling beforeFirst() will reset the position
501      *  to the just before the position where K is present.
502      */
503     public void beforeFirst() throws IOException
504     {
505         cloneStack( _initialStack, stack );
506     }
507 
508 
509     /**
510      * Places the cursor at the end of the last position
511      * 
512      * @throws IOException
513      */
514     public void afterLast() throws IOException
515     {
516         stack.clear();
517         stack = BTreeFactory.getPathToRightMostLeaf( btree );
518     }
519 
520 
521     /**
522      * clones the original stack of ParentPos objects
523      * 
524      * @param original the original stack
525      * @param clone the stack where the cloned ParentPos objects to be copied
526      */
527     private void cloneStack( LinkedList<ParentPos<K, V>> original, LinkedList<ParentPos<K, V>> clone )
528     {
529         clone.clear();
530 
531         // preserve the first position
532         for ( ParentPos<K, V> o : original )
533         {
534             ParentPos<K, V> tmp = new ParentPos<K, V>( o.page, o.pos );
535             tmp.dupPos = o.dupPos;
536             tmp.dupsContainer = o.dupsContainer;
537             clone.add( tmp );
538         }
539     }
540 
541 }