BlockIterator


1   /*-
2    * See the file LICENSE for redistribution information.
3    *
4    * Copyright (c) 2000,2006 Oracle.  All rights reserved.
5    *
6    * $Id: BlockIterator.java,v 1.6 2006/10/30 21:14:10 bostic Exp $
7    */
8   
9   package com.sleepycat.collections;
10  
11  import java.util.ListIterator  ;
12  import java.util.NoSuchElementException  ;
13  
14  import com.sleepycat.compat.DbCompat;
15  import com.sleepycat.je.DatabaseEntry;
16  import com.sleepycat.je.DatabaseException;
17  import com.sleepycat.je.OperationStatus;
18  import com.sleepycat.util.keyrange.KeyRange;
19  
20  /**
21   * An iterator that does need closing because a cursor is not kept open across
22   * method calls.  A cursor is opened to read a block of records at a time and
23   * then closed before the method returns.
24   *
25   * @author Mark Hayes
26   */
27  class BlockIterator implements BaseIterator {
28  
29      private StoredCollection coll;
30      private boolean writeAllowed;
31  
32      /**
33       * Slots for a block of record keys and values.  The priKeys array is only
34       * used for secondary databases; otherwise it is set to the keys array.
35       */
36      private byte[][] keys;
37      private byte[][] priKeys;
38      private byte[][] values;
39  
40      /**
41       * The slot index of the record that would be returned by next().
42       * nextIndex is always greater or equal to zero.  If the next record is not
43       * available, then nextIndex is equal to keys.length or keys[nextIndex] is
44       * null.
45       */
46      private int nextIndex;
47  
48      /**
49       * The slot index of the record last returned by next() or previous(), or
50       * the record inserted by add().  dataIndex is -1 if the data record is not
51       * available.  If greater or equal to zero, the slot at dataIndex is always
52       * non-null.
53       */
54      private int dataIndex;
55  
56      /**
57       * The iterator data last returned by next() or previous().  This value is
58       * set to null if dataIndex is -1, or if the state of the iterator is such
59       * that set() or remove() cannot be called.  For example, after add() this
60       * field is set to null, even though the dataIndex is still valid.
61       */
62      private Object   dataObject;
63  
64      /**
65       * Creates an iterator.
66       */
67      BlockIterator(StoredCollection coll, boolean writeAllowed, int blockSize) {
68  
69          this.coll = coll;
70          this.writeAllowed = writeAllowed;
71  
72          keys = new byte[blockSize][];
73          priKeys = coll.isSecondary() ? (new byte[blockSize][]) : keys;
74          values = new byte[blockSize][];
75  
76          nextIndex = blockSize;
77          dataIndex = -1;
78          dataObject = null;
79      }
80  
81      /**
82       * Copy constructor.
83       */
84      private BlockIterator(BlockIterator o) {
85  
86          coll = o.coll;
87          writeAllowed = o.writeAllowed;
88  
89          keys = copyArray(o.keys);
90          priKeys = coll.isSecondary() ? copyArray(o.priKeys) : keys;
91          values = copyArray(o.values);
92  
93          nextIndex = o.nextIndex;
94          dataIndex = o.dataIndex;
95          dataObject = o.dataObject;
96      }
97  
98      /**
99       * Copies an array of byte arrays.
100      */
101     private byte[][] copyArray(byte[][] a) {
102 
103         byte[][] b = new byte[a.length][];
104         for (int i = 0; i < b.length; i += 1) {
105             if (a[i] != null) {
106                 b[i] = KeyRange.copyBytes(a[i]);
107             }
108         }
109         return b;
110     }
111 
112     /**
113      * Returns whether the element at nextIndex is available.
114      */
115     private boolean isNextAvailable() {
116 
117         return (nextIndex < keys.length) &&
118                (keys[nextIndex] != null);
119     }
120 
121     /**
122      * Returns whether the element at nextIndex-1 is available.
123      */
124     private boolean isPrevAvailable() {
125 
126         return (nextIndex > 0) &&
127                (keys[nextIndex - 1] != null);
128     }
129 
130     /**
131      * Returns the record number at the given slot position.
132      */
133     private int getRecordNumber(int i) {
134 
135         if (coll.view.btreeRecNumDb) {
136             DataCursor cursor = null;
137             try {
138                 cursor = new DataCursor(coll.view, false);
139                 if (moveCursor(i, cursor)) {
140                     return cursor.getCurrentRecordNumber();
141                 } else {
142                     throw new IllegalStateException  ();
143                 }
144             } catch (DatabaseException e) {
145                 throw StoredContainer.convertException(e);
146             } finally {
147                 closeCursor(cursor);
148             }
149         } else {
150             DatabaseEntry entry = new DatabaseEntry(keys[i]);
151             return DbCompat.getRecordNumber(entry);
152         }
153     }
154 
155     /**
156      * Sets dataObject to the iterator data for the element at dataIndex.
157      */
158     private void makeDataObject() {
159 
160         int i = dataIndex;
161         DatabaseEntry keyEntry = new DatabaseEntry(keys[i]);
162         DatabaseEntry priKeyEntry = (keys != priKeys)
163                                     ? (new DatabaseEntry(priKeys[i]))
164                                     : keyEntry;
165         DatabaseEntry valuesEntry = new DatabaseEntry(values[i]);
166 
167         dataObject = coll.makeIteratorData(this, keyEntry, priKeyEntry,
168                                            valuesEntry);
169     }
170 
171     /**
172      * Sets all slots to null.
173      */
174     private void clearSlots() {
175 
176         for (int i = 0; i < keys.length; i += 1) {
177             keys[i] = null;
178             priKeys[i] = null;
179             values[i] = null;
180         }
181     }
182 
183     /**
184      * Sets a given slot using the data in the given cursor.
185      */
186     private void setSlot(int i, DataCursor cursor) {
187 
188         keys[i] = KeyRange.getByteArray(cursor.getKeyThang());
189 
190         if (keys != priKeys) {
191             priKeys[i] = KeyRange.getByteArray
192                 (cursor.getPrimaryKeyThang());
193         }
194 
195         values[i] = KeyRange.getByteArray(cursor.getValueThang());
196     }
197 
198     /**
199      * Inserts an added record at a given slot position and shifts other slots
200      * accordingly.  Also adjusts nextIndex and sets dataIndex to -1.
201      */
202     private void insertSlot(int i, DataCursor cursor) {
203 
204         if (i < keys.length) {
205             for (int j = keys.length - 1; j > i; j -= 1) {
206 
207                 /* Shift right. */
208                 keys[j] = keys[j - 1];
209                 priKeys[j] = priKeys[j - 1];
210                 values[j] = values[j - 1];
211 
212                 /* Bump key in recno-renumber database. */
213                 if (coll.view.recNumRenumber && keys[j] != null) {
214                     bumpRecordNumber(j);
215                 }
216             }
217             nextIndex += 1;
218         } else {
219             if (i != keys.length) {
220                 throw new IllegalStateException  ();
221             }
222             i -= 1;
223             for (int j = 0; j < i; j += 1) {
224                 /* Shift left. */
225                 keys[j] = keys[j + 1];
226                 priKeys[j] = priKeys[j + 1];
227                 values[j] = values[j + 1];
228             }
229         }
230         setSlot(i, cursor);
231         dataIndex = -1;
232     }
233 
234     /**
235      * Increments the record number key at the given slot.
236      */
237     private void bumpRecordNumber(int i) {
238 
239         DatabaseEntry entry = new DatabaseEntry(keys[i]);
240         DbCompat.setRecordNumber(entry,
241                                  DbCompat.getRecordNumber(entry) + 1);
242         keys[i] = entry.getData();
243     }
244 
245     /**
246      * Deletes the given slot, adjusts nextIndex and sets dataIndex to -1.
247      */
248     private void deleteSlot(int i) {
249 
250         for (int j = i + 1; j < keys.length; j += 1) {
251             keys[j - 1] = keys[j];
252             priKeys[j - 1] = priKeys[j];
253             values[j - 1] = values[j];
254         }
255         int last = keys.length - 1;
256         keys[last] = null;
257         priKeys[last] = null;
258         values[last] = null;
259 
260         if (nextIndex > i) {
261             nextIndex -= 1;
262         }
263         dataIndex = -1;
264     }
265 
266     /**
267      * Moves the cursor to the key/data at the given slot, and returns false 
268      * if the reposition (search) fails.
269      */
270     private boolean moveCursor(int i, DataCursor cursor)
271         throws DatabaseException {
272 
273         return cursor.repositionExact(keys[i], priKeys[i], values[i], false);
274     }
275 
276     /**
277      * Closes the given cursor if non-null.
278      */
279     private void closeCursor(DataCursor cursor) {
280 
281         if (cursor != null) {
282             try {
283                 cursor.close();
284             } catch (DatabaseException e) {
285                 throw StoredContainer.convertException(e);
286             }
287         }
288     }
289 
290     // --- begin Iterator/ListIterator methods ---
291 
292     public boolean hasNext() {
293 
294         if (isNextAvailable()) {
295             return true;
296         }
297         DataCursor cursor = null;
298         try {
299             cursor = new DataCursor(coll.view, writeAllowed);
300             int prev = nextIndex - 1;
301             boolean found = false;
302 
303             if (keys[prev] == null) {
304                 /* Get the first record for an uninitialized iterator. */
305                 OperationStatus status = cursor.getFirst(false);
306                 if (status == OperationStatus.SUCCESS) {
307                     found = true;
308                     nextIndex = 0;
309                 }
310             } else {
311                 /* Reposition to the last known key/data pair. */
312                 int repos = cursor.repositionRange
313                     (keys[prev], priKeys[prev], values[prev], false);
314 
315                 if (repos == DataCursor.REPOS_EXACT) {
316 
317                     /*
318                      * The last known key/data pair was found and will now be
319                      * in slot zero.
320                      */
321                     found = true;
322                     nextIndex = 1;
323 
324                     /* The data object is now in slot zero or not available. */
325                     if (dataIndex == prev) {
326                         dataIndex = 0;
327                     } else {
328                         dataIndex = -1;
329                         dataObject = null;
330                     }
331                 } else if (repos == DataCursor.REPOS_NEXT) {
332 
333                     /*
334                      * The last known key/data pair was not found, but the
335                      * following record was found and it will be in slot zero.
336                      */
337                     found = true;
338                     nextIndex = 0;
339 
340                     /* The data object is no longer available. */
341                     dataIndex = -1;
342                     dataObject = null;
343                 } else {
344                     if (repos != DataCursor.REPOS_EOF) {
345                         throw new IllegalStateException  ();
346                     }
347                 }
348             }
349 
350             if (found) {
351                 /* Clear all slots first in case an exception occurs below. */
352                 clearSlots();
353 
354                 /* Attempt to fill all slots with records. */
355                 int i = 0;
356                 boolean done = false;
357                 while (!done) {
358                     setSlot(i, cursor);
359                     i += 1;
360                     if (i < keys.length) {
361                         OperationStatus status = coll.iterateDuplicates() ?
362                                                  cursor.getNext(false) :
363                                                  cursor.getNextNoDup(false);
364                         if (status != OperationStatus.SUCCESS) {
365                             done = true;
366                         }
367                     } else {
368                         done = true;
369                     }
370                 }
371 
372             }
373 
374             /*
375              * If REPOS_EXACT was returned above, make sure we retrieved
376              * the following record.
377              */
378             return isNextAvailable();
379         } catch (DatabaseException e) {
380             throw StoredContainer.convertException(e);
381         } finally {
382             closeCursor(cursor);
383         }
384     }
385 
386     public boolean hasPrevious() {
387 
388         if (isPrevAvailable()) {
389             return true;
390         }
391         if (!isNextAvailable()) {
392             return false;
393         }
394         DataCursor cursor = null;
395         try {
396             cursor = new DataCursor(coll.view, writeAllowed);
397             int last = keys.length - 1;
398             int next = nextIndex;
399             boolean found = false;
400         
401             /* Reposition to the last known key/data pair. */
402             int repos = cursor.repositionRange
403                 (keys[next], priKeys[next], values[next], false);
404 
405             if (repos == DataCursor.REPOS_EXACT ||
406                 repos == DataCursor.REPOS_NEXT) {
407 
408                 /*
409                  * The last known key/data pair, or the record following it,
410                  * was found and will now be in the last slot.
411                  */
412                 found = true;
413                 nextIndex = last;
414 
415                 /* The data object is now in the last slot or not available. */
416                 if (dataIndex == next && repos == DataCursor.REPOS_EXACT) {
417                     dataIndex = last;
418                 } else {
419                     dataIndex = -1;
420                     dataObject = null;
421                 }
422             } else {
423                 if (repos != DataCursor.REPOS_EOF) {
424                     throw new IllegalStateException  ();
425                 }
426             }
427 
428             if (found) {
429                 /* Clear all slots first in case an exception occurs below. */
430                 clearSlots();
431 
432                 /* Attempt to fill all slots with records. */
433                 int i = last;
434                 boolean done = false;
435                 while (!done) {
436                     setSlot(i, cursor);
437                     i -= 1;
438                     if (i >= 0) {
439                         OperationStatus status = coll.iterateDuplicates() ?
440                                                  cursor.getPrev(false) :
441                                                  cursor.getPrevNoDup(false);
442                         if (status != OperationStatus.SUCCESS) {
443                             done = true;
444                         }
445                     } else {
446                         done = true;
447                     }
448                 }
449             }
450 
451             /*
452              * Make sure we retrieved the preceding record after the reposition
453              * above.
454              */
455             return isPrevAvailable();
456         } catch (DatabaseException e) {
457             throw StoredContainer.convertException(e);
458         } finally {
459             closeCursor(cursor);
460         }
461     }
462 
463     public Object   next() {
464 
465         if (hasNext()) {
466             dataIndex = nextIndex;
467             nextIndex += 1;
468             makeDataObject();
469             return dataObject;
470         } else {
471             throw new NoSuchElementException  ();
472         }
473     }
474 
475     public Object   previous() {
476 
477         if (hasPrevious()) {
478             nextIndex -= 1;
479             dataIndex = nextIndex;
480             makeDataObject();
481             return dataObject;
482         } else {
483             throw new NoSuchElementException  ();
484         }
485     }
486 
487     public int nextIndex() {
488 
489         if (!coll.view.recNumAccess) {
490             throw new UnsupportedOperationException  (
491                 "Record number access not supported");
492         }
493 
494         return hasNext() ? (getRecordNumber(nextIndex) -
495                             coll.getIndexOffset())
496                          : Integer.MAX_VALUE;
497     }
498 
499     public int previousIndex() {
500 
501         if (!coll.view.recNumAccess) {
502             throw new UnsupportedOperationException  (
503                 "Record number access not supported");
504         }
505 
506         return hasPrevious() ? (getRecordNumber(nextIndex - 1) -
507                                 coll.getIndexOffset())
508                              : (-1);
509     }
510 
511     public void set(Object   value) {
512 
513         if (dataObject == null) {
514             throw new IllegalStateException  ();
515         }
516         if (!coll.hasValues()) {
517             throw new UnsupportedOperationException  ();
518         }
519         DataCursor cursor = null;
520         try {
521             cursor = new DataCursor(coll.view, writeAllowed);
522             if (moveCursor(dataIndex, cursor)) {
523                 cursor.putCurrent(value);
524                 setSlot(dataIndex, cursor);
525             } else {
526                 throw new IllegalStateException  ();
527             }
528         } catch (DatabaseException e) {
529             throw StoredContainer.convertException(e);
530         } finally {
531             closeCursor(cursor);
532         }
533     }
534 
535     public void remove() {
536 
537         if (dataObject == null) {
538             throw new IllegalStateException  ();
539         }
540         DataCursor cursor = null;
541         try {
542             cursor = new DataCursor(coll.view, writeAllowed);
543             if (moveCursor(dataIndex, cursor)) {
544                 cursor.delete();
545                 deleteSlot(dataIndex);
546                 dataObject = null;
547             } else {
548                 throw new IllegalStateException  ();
549             }
550         } catch (DatabaseException e) {
551             throw StoredContainer.convertException(e);
552         } finally {
553             closeCursor(cursor);
554         }
555     }
556 
557     public void add(Object   value) {
558 
559         /*
560          * The checkIterAddAllowed method ensures that one of the following two
561          * conditions holds and throws UnsupportedOperationException otherwise:
562          * 1- This is a list iterator for a recno-renumber database.
563          * 2- This is a collection iterator for a duplicates database.
564          */
565         coll.checkIterAddAllowed();
566         OperationStatus status = OperationStatus.SUCCESS;
567         DataCursor cursor = null;
568         try {
569             if (coll.view.keysRenumbered || !coll.areDuplicatesOrdered()) {
570 
571                 /*
572                  * This is a recno-renumber database or a btree/hash database
573                  * with unordered duplicates.
574                  */
575                 boolean hasPrev = hasPrevious();
576                 if (!hasPrev && !hasNext()) {
577 
578                     /* The collection is empty. */
579                     if (coll.view.keysRenumbered) {
580 
581                         /* Append to an empty recno-renumber database. */
582                         status = coll.view.append(value, null, null);
583 
584                     } else if (coll.view.dupsAllowed &&
585                                coll.view.range.isSingleKey()) {
586 
587                         /*
588                          * When inserting a duplicate into a single-key range,
589                          * the main key is fixed, so we can always insert into
590                          * an empty collection.
591                          */
592                         cursor = new DataCursor(coll.view, writeAllowed);
593                         cursor.useRangeKey();
594                         status = cursor.putNoDupData(null, value, null, true);
595                         cursor.close();
596                         cursor = null;
597                     } else {
598                         throw new IllegalStateException  
599                             ("Collection is empty, cannot add() duplicate");
600                     }
601 
602                     /*
603                      * Move past the record just inserted (the cursor should be
604                      * closed above to prevent multiple open cursors in certain
605                      * DB core modes).
606                      */
607                     if (status == OperationStatus.SUCCESS) {
608                         next();
609                         dataIndex = nextIndex - 1;
610                     }
611                 } else {
612 
613                     /*
614                      * The collection is non-empty.  If hasPrev is true then
615                      * the element at (nextIndex - 1) is available; otherwise
616                      * the element at nextIndex is available.
617                      */
618                     cursor = new DataCursor(coll.view, writeAllowed);
619                     int insertIndex = hasPrev ? (nextIndex - 1) : nextIndex;
620 
621                     if (!moveCursor(insertIndex, cursor)) {
622                         throw new IllegalStateException  ();
623                     }
624                     
625                     /*
626                      * For a recno-renumber database or a database with
627                      * unsorted duplicates, insert before the iterator 'next'
628                      * position, or after the 'prev' position.  Then adjust
629                      * the slots to account for the inserted record.
630                      */
631                     status = hasPrev ? cursor.putAfter(value)
632                                      : cursor.putBefore(value);
633                     if (status == OperationStatus.SUCCESS) {
634                         insertSlot(nextIndex, cursor);
635                     }
636                 }
637             } else {
638                 /* This is a btree/hash database with ordered duplicates. */
639                 cursor = new DataCursor(coll.view, writeAllowed);
640 
641                 if (coll.view.range.isSingleKey()) {
642 
643                     /*
644                      * When inserting a duplicate into a single-key range,
645                      * the main key is fixed.
646                      */
647                     cursor.useRangeKey();
648                 } else {
649 
650                     /*
651                      * When inserting into a multi-key range, the main key
652                      * is the last dataIndex accessed by next(), previous()
653                      * or add().
654                      */
655                     if (dataIndex < 0 || !moveCursor(dataIndex, cursor)) {
656                         throw new IllegalStateException  ();
657                     }
658                 }
659 
660                 /*
661                  * For a hash/btree with duplicates, insert the duplicate,
662                  * put the new record in slot zero, and set the next index
663                  * to slot one (past the new record).
664                  */
665                 status = cursor.putNoDupData(null, value, null, true);
666                 if (status == OperationStatus.SUCCESS) {
667                     clearSlots();
668                     setSlot(0, cursor);
669                     dataIndex = 0;
670                     nextIndex = 1;
671                 }
672             }
673 
674             if (status == OperationStatus.KEYEXIST) {
675                 throw new IllegalArgumentException  ("Duplicate value");
676             } else if (status != OperationStatus.SUCCESS) {
677                 throw new IllegalArgumentException  ("Could not insert: " +
678                                                     status);
679             }
680 
681             /* Prevent subsequent set() or remove() call. */
682             dataObject = null;
683         } catch (DatabaseException e) {
684             throw StoredContainer.convertException(e);
685         } finally {
686             closeCursor(cursor);
687         }
688     }
689 
690     // --- end Iterator/ListIterator methods ---
691 
692     // --- begin BaseIterator methods ---
693 
694     public final ListIterator   dup() {
695 
696         return new BlockIterator(this);
697     }
698 
699     public final boolean isCurrentData(Object   currentData) {
700 
701         return (dataObject == currentData);
702     }
703 
704     public final boolean moveToIndex(int index) {
705 
706         DataCursor cursor = null;
707         try {
708             cursor = new DataCursor(coll.view, writeAllowed);
709             OperationStatus status =
710                 cursor.getSearchKey(new Integer  (index), null, false);
711             if (status == OperationStatus.SUCCESS) {
712                 clearSlots();
713                 setSlot(0, cursor);
714                 nextIndex = 0;
715                 return true;
716             } else {
717                 return false;
718             }
719         } catch (DatabaseException e) {
720             throw StoredContainer.convertException(e);
721         } finally {
722             closeCursor(cursor);
723         }
724     }
725 
726     // --- end BaseIterator methods ---
727 }
728
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags