001: /*-
002: * See the file LICENSE for redistribution information.
003: *
004: * Copyright (c) 2000,2008 Oracle. All rights reserved.
005: *
006: * $Id: BlockIterator.java,v 1.6.2.5 2008/01/07 15:14:06 cwl Exp $
007: */
008:
009: package com.sleepycat.collections;
010:
011: import java.util.ListIterator;
012: import java.util.NoSuchElementException;
013:
014: import com.sleepycat.compat.DbCompat;
015: import com.sleepycat.je.DatabaseEntry;
016: import com.sleepycat.je.DatabaseException;
017: import com.sleepycat.je.OperationStatus;
018: import com.sleepycat.util.keyrange.KeyRange;
019:
020: /**
021: * An iterator that does not need closing because a cursor is not kept open
022: * across method calls. A cursor is opened to read a block of records at a
023: * time and then closed before the method returns.
024: *
025: * @author Mark Hayes
026: */
027: class BlockIterator implements BaseIterator {
028:
029: private StoredCollection coll;
030: private boolean writeAllowed;
031:
032: /**
033: * Slots for a block of record keys and values. The priKeys array is only
034: * used for secondary databases; otherwise it is set to the keys array.
035: */
036: private byte[][] keys;
037: private byte[][] priKeys;
038: private byte[][] values;
039:
040: /**
041: * The slot index of the record that would be returned by next().
042: * nextIndex is always greater or equal to zero. If the next record is not
043: * available, then nextIndex is equal to keys.length or keys[nextIndex] is
044: * null.
045: *
046: * If the block is empty, then either the iterator is uninitialized or the
047: * key range is empty. Either way, nextIndex will be the array length and
048: * all array values will be null. This is the initial state set by the
049: * constructor. If remove() is used to delete all records in the key
050: * range, it will restore the iterator to this initial state. The block
051: * must never be allowed to become empty when the key range is non-empty,
052: * since then the iterator's position would be lost. [#15858]
053: */
054: private int nextIndex;
055:
056: /**
057: * The slot index of the record last returned by next() or previous(), or
058: * the record inserted by add(). dataIndex is -1 if the data record is not
059: * available. If greater or equal to zero, the slot at dataIndex is always
060: * non-null.
061: */
062: private int dataIndex;
063:
064: /**
065: * The iterator data last returned by next() or previous(). This value is
066: * set to null if dataIndex is -1, or if the state of the iterator is such
067: * that set() or remove() cannot be called. For example, after add() this
068: * field is set to null, even though the dataIndex is still valid.
069: */
070: private Object dataObject;
071:
072: /**
073: * Creates an iterator.
074: */
075: BlockIterator(StoredCollection coll, boolean writeAllowed,
076: int blockSize) {
077:
078: this .coll = coll;
079: this .writeAllowed = writeAllowed;
080:
081: keys = new byte[blockSize][];
082: priKeys = coll.isSecondary() ? (new byte[blockSize][]) : keys;
083: values = new byte[blockSize][];
084:
085: nextIndex = blockSize;
086: dataIndex = -1;
087: dataObject = null;
088: }
089:
090: /**
091: * Copy constructor.
092: */
093: private BlockIterator(BlockIterator o) {
094:
095: coll = o.coll;
096: writeAllowed = o.writeAllowed;
097:
098: keys = copyArray(o.keys);
099: priKeys = coll.isSecondary() ? copyArray(o.priKeys) : keys;
100: values = copyArray(o.values);
101:
102: nextIndex = o.nextIndex;
103: dataIndex = o.dataIndex;
104: dataObject = o.dataObject;
105: }
106:
107: /**
108: * Copies an array of byte arrays.
109: */
110: private byte[][] copyArray(byte[][] a) {
111:
112: byte[][] b = new byte[a.length][];
113: for (int i = 0; i < b.length; i += 1) {
114: if (a[i] != null) {
115: b[i] = KeyRange.copyBytes(a[i]);
116: }
117: }
118: return b;
119: }
120:
121: /**
122: * Returns whether the element at nextIndex is available.
123: */
124: private boolean isNextAvailable() {
125:
126: return (nextIndex < keys.length) && (keys[nextIndex] != null);
127: }
128:
129: /**
130: * Returns whether the element at nextIndex-1 is available.
131: */
132: private boolean isPrevAvailable() {
133:
134: return (nextIndex > 0) && (keys[nextIndex - 1] != null);
135: }
136:
137: /**
138: * Returns the record number at the given slot position.
139: */
140: private int getRecordNumber(int i) {
141:
142: if (coll.view.btreeRecNumDb) {
143: DataCursor cursor = null;
144: try {
145: cursor = new DataCursor(coll.view, false);
146: if (moveCursor(i, cursor)) {
147: return cursor.getCurrentRecordNumber();
148: } else {
149: throw new IllegalStateException();
150: }
151: } catch (DatabaseException e) {
152: throw StoredContainer.convertException(e);
153: } finally {
154: closeCursor(cursor);
155: }
156: } else {
157: DatabaseEntry entry = new DatabaseEntry(keys[i]);
158: return DbCompat.getRecordNumber(entry);
159: }
160: }
161:
162: /**
163: * Sets dataObject to the iterator data for the element at dataIndex.
164: */
165: private void makeDataObject() {
166:
167: int i = dataIndex;
168: DatabaseEntry keyEntry = new DatabaseEntry(keys[i]);
169: DatabaseEntry priKeyEntry = (keys != priKeys) ? (new DatabaseEntry(
170: priKeys[i]))
171: : keyEntry;
172: DatabaseEntry valuesEntry = new DatabaseEntry(values[i]);
173:
174: dataObject = coll.makeIteratorData(this , keyEntry, priKeyEntry,
175: valuesEntry);
176: }
177:
178: /**
179: * Sets all slots to null.
180: */
181: private void clearSlots() {
182:
183: for (int i = 0; i < keys.length; i += 1) {
184: keys[i] = null;
185: priKeys[i] = null;
186: values[i] = null;
187: }
188: }
189:
190: /**
191: * Sets a given slot using the data in the given cursor.
192: */
193: private void setSlot(int i, DataCursor cursor) {
194:
195: keys[i] = KeyRange.getByteArray(cursor.getKeyThang());
196:
197: if (keys != priKeys) {
198: priKeys[i] = KeyRange.getByteArray(cursor
199: .getPrimaryKeyThang());
200: }
201:
202: values[i] = KeyRange.getByteArray(cursor.getValueThang());
203: }
204:
205: /**
206: * Inserts an added record at a given slot position and shifts other slots
207: * accordingly. Also adjusts nextIndex and sets dataIndex to -1.
208: */
209: private void insertSlot(int i, DataCursor cursor) {
210:
211: if (i < keys.length) {
212: for (int j = keys.length - 1; j > i; j -= 1) {
213:
214: /* Shift right. */
215: keys[j] = keys[j - 1];
216: priKeys[j] = priKeys[j - 1];
217: values[j] = values[j - 1];
218:
219: /* Bump key in recno-renumber database. */
220: if (coll.view.recNumRenumber && keys[j] != null) {
221: bumpRecordNumber(j);
222: }
223: }
224: nextIndex += 1;
225: } else {
226: if (i != keys.length) {
227: throw new IllegalStateException();
228: }
229: i -= 1;
230: for (int j = 0; j < i; j += 1) {
231: /* Shift left. */
232: keys[j] = keys[j + 1];
233: priKeys[j] = priKeys[j + 1];
234: values[j] = values[j + 1];
235: }
236: }
237: setSlot(i, cursor);
238: dataIndex = -1;
239: }
240:
241: /**
242: * Increments the record number key at the given slot.
243: */
244: private void bumpRecordNumber(int i) {
245:
246: DatabaseEntry entry = new DatabaseEntry(keys[i]);
247: DbCompat.setRecordNumber(entry,
248: DbCompat.getRecordNumber(entry) + 1);
249: keys[i] = entry.getData();
250: }
251:
252: /**
253: * Deletes the given slot, adjusts nextIndex and sets dataIndex to -1.
254: */
255: private void deleteSlot(int i) {
256:
257: for (int j = i + 1; j < keys.length; j += 1) {
258: keys[j - 1] = keys[j];
259: priKeys[j - 1] = priKeys[j];
260: values[j - 1] = values[j];
261: }
262: int last = keys.length - 1;
263: keys[last] = null;
264: priKeys[last] = null;
265: values[last] = null;
266:
267: if (nextIndex > i) {
268: nextIndex -= 1;
269: }
270: dataIndex = -1;
271: }
272:
273: /**
274: * Moves the cursor to the key/data at the given slot, and returns false
275: * if the reposition (search) fails.
276: */
277: private boolean moveCursor(int i, DataCursor cursor)
278: throws DatabaseException {
279:
280: return cursor.repositionExact(keys[i], priKeys[i], values[i],
281: false);
282: }
283:
284: /**
285: * Closes the given cursor if non-null.
286: */
287: private void closeCursor(DataCursor cursor) {
288:
289: if (cursor != null) {
290: try {
291: cursor.close();
292: } catch (DatabaseException e) {
293: throw StoredContainer.convertException(e);
294: }
295: }
296: }
297:
298: // --- begin Iterator/ListIterator methods ---
299:
300: public boolean hasNext() {
301:
302: if (isNextAvailable()) {
303: return true;
304: }
305: DataCursor cursor = null;
306: try {
307: cursor = new DataCursor(coll.view, writeAllowed);
308: int prev = nextIndex - 1;
309: boolean found = false;
310:
311: if (keys[prev] == null) {
312: /* Get the first record for an uninitialized iterator. */
313: OperationStatus status = cursor.getFirst(false);
314: if (status == OperationStatus.SUCCESS) {
315: found = true;
316: nextIndex = 0;
317: }
318: } else {
319: /* Reposition to the last known key/data pair. */
320: int repos = cursor.repositionRange(keys[prev],
321: priKeys[prev], values[prev], false);
322:
323: if (repos == DataCursor.REPOS_EXACT) {
324:
325: /*
326: * The last known key/data pair was found and will now be
327: * in slot zero.
328: */
329: found = true;
330: nextIndex = 1;
331:
332: /* The data object is now in slot zero or not available. */
333: if (dataIndex == prev) {
334: dataIndex = 0;
335: } else {
336: dataIndex = -1;
337: dataObject = null;
338: }
339: } else if (repos == DataCursor.REPOS_NEXT) {
340:
341: /*
342: * The last known key/data pair was not found, but the
343: * following record was found and it will be in slot zero.
344: */
345: found = true;
346: nextIndex = 0;
347:
348: /* The data object is no longer available. */
349: dataIndex = -1;
350: dataObject = null;
351: } else {
352: if (repos != DataCursor.REPOS_EOF) {
353: throw new IllegalStateException();
354: }
355: }
356: }
357:
358: if (found) {
359: /* Clear all slots first in case an exception occurs below. */
360: clearSlots();
361:
362: /* Attempt to fill all slots with records. */
363: int i = 0;
364: boolean done = false;
365: while (!done) {
366: setSlot(i, cursor);
367: i += 1;
368: if (i < keys.length) {
369: OperationStatus status = coll
370: .iterateDuplicates() ? cursor
371: .getNext(false) : cursor
372: .getNextNoDup(false);
373: if (status != OperationStatus.SUCCESS) {
374: done = true;
375: }
376: } else {
377: done = true;
378: }
379: }
380:
381: }
382:
383: /*
384: * If REPOS_EXACT was returned above, make sure we retrieved
385: * the following record.
386: */
387: return isNextAvailable();
388: } catch (DatabaseException e) {
389: throw StoredContainer.convertException(e);
390: } finally {
391: closeCursor(cursor);
392: }
393: }
394:
395: public boolean hasPrevious() {
396:
397: if (isPrevAvailable()) {
398: return true;
399: }
400: if (!isNextAvailable()) {
401: return false;
402: }
403: DataCursor cursor = null;
404: try {
405: cursor = new DataCursor(coll.view, writeAllowed);
406: int last = keys.length - 1;
407: int next = nextIndex;
408: boolean found = false;
409:
410: /* Reposition to the last known key/data pair. */
411: int repos = cursor.repositionRange(keys[next],
412: priKeys[next], values[next], false);
413:
414: if (repos == DataCursor.REPOS_EXACT
415: || repos == DataCursor.REPOS_NEXT) {
416:
417: /*
418: * The last known key/data pair, or the record following it,
419: * was found and will now be in the last slot.
420: */
421: found = true;
422: nextIndex = last;
423:
424: /* The data object is now in the last slot or not available. */
425: if (dataIndex == next
426: && repos == DataCursor.REPOS_EXACT) {
427: dataIndex = last;
428: } else {
429: dataIndex = -1;
430: dataObject = null;
431: }
432: } else {
433: if (repos != DataCursor.REPOS_EOF) {
434: throw new IllegalStateException();
435: }
436: }
437:
438: if (found) {
439: /* Clear all slots first in case an exception occurs below. */
440: clearSlots();
441:
442: /* Attempt to fill all slots with records. */
443: int i = last;
444: boolean done = false;
445: while (!done) {
446: setSlot(i, cursor);
447: i -= 1;
448: if (i >= 0) {
449: OperationStatus status = coll
450: .iterateDuplicates() ? cursor
451: .getPrev(false) : cursor
452: .getPrevNoDup(false);
453: if (status != OperationStatus.SUCCESS) {
454: done = true;
455: }
456: } else {
457: done = true;
458: }
459: }
460: }
461:
462: /*
463: * Make sure we retrieved the preceding record after the reposition
464: * above.
465: */
466: return isPrevAvailable();
467: } catch (DatabaseException e) {
468: throw StoredContainer.convertException(e);
469: } finally {
470: closeCursor(cursor);
471: }
472: }
473:
474: public Object next() {
475:
476: if (hasNext()) {
477: dataIndex = nextIndex;
478: nextIndex += 1;
479: makeDataObject();
480: return dataObject;
481: } else {
482: throw new NoSuchElementException();
483: }
484: }
485:
486: public Object previous() {
487:
488: if (hasPrevious()) {
489: nextIndex -= 1;
490: dataIndex = nextIndex;
491: makeDataObject();
492: return dataObject;
493: } else {
494: throw new NoSuchElementException();
495: }
496: }
497:
498: public int nextIndex() {
499:
500: if (!coll.view.recNumAccess) {
501: throw new UnsupportedOperationException(
502: "Record number access not supported");
503: }
504:
505: return hasNext() ? (getRecordNumber(nextIndex) - coll
506: .getIndexOffset()) : Integer.MAX_VALUE;
507: }
508:
509: public int previousIndex() {
510:
511: if (!coll.view.recNumAccess) {
512: throw new UnsupportedOperationException(
513: "Record number access not supported");
514: }
515:
516: return hasPrevious() ? (getRecordNumber(nextIndex - 1) - coll
517: .getIndexOffset()) : (-1);
518: }
519:
520: public void set(Object value) {
521:
522: if (dataObject == null) {
523: throw new IllegalStateException();
524: }
525: if (!coll.hasValues()) {
526: throw new UnsupportedOperationException();
527: }
528: DataCursor cursor = null;
529: boolean doAutoCommit = coll.beginAutoCommit();
530: try {
531: cursor = new DataCursor(coll.view, writeAllowed);
532: if (moveCursor(dataIndex, cursor)) {
533: cursor.putCurrent(value);
534: setSlot(dataIndex, cursor);
535: coll.closeCursor(cursor);
536: coll.commitAutoCommit(doAutoCommit);
537: } else {
538: throw new IllegalStateException();
539: }
540: } catch (Exception e) {
541: coll.closeCursor(cursor);
542: throw coll.handleException(e, doAutoCommit);
543: }
544: }
545:
546: public void remove() {
547:
548: if (dataObject == null) {
549: throw new IllegalStateException();
550: }
551: DataCursor cursor = null;
552: boolean doAutoCommit = coll.beginAutoCommit();
553: try {
554: cursor = new DataCursor(coll.view, writeAllowed);
555: if (moveCursor(dataIndex, cursor)) {
556: cursor.delete();
557: deleteSlot(dataIndex);
558: dataObject = null;
559:
560: /*
561: * Repopulate the block after removing all records, using the
562: * cursor position of the deleted record as a starting point.
563: * First try moving forward, since the user was moving forward.
564: * (It is possible to delete all records in the block only by
565: * moving forward, i.e, when nextIndex is greater than
566: * dataIndex.)
567: */
568: if (nextIndex == 0 && keys[0] == null) {
569: OperationStatus status;
570: for (int i = 0; i < keys.length; i += 1) {
571: status = coll.iterateDuplicates() ? cursor
572: .getNext(false) : cursor
573: .getNextNoDup(false);
574: if (status == OperationStatus.SUCCESS) {
575: setSlot(i, cursor);
576: } else {
577: break;
578: }
579: }
580:
581: /*
582: * If no records are found past the cursor position, try
583: * moving backward. If no records are found before the
584: * cursor position, leave nextIndex set to keys.length,
585: * which is the same as the initial iterator state and is
586: * appropriate for an empty key range.
587: */
588: if (keys[0] == null) {
589: nextIndex = keys.length;
590: for (int i = nextIndex - 1; i >= 0; i -= 1) {
591: status = coll.iterateDuplicates() ? cursor
592: .getPrev(false) : cursor
593: .getPrevNoDup(false);
594: if (status == OperationStatus.SUCCESS) {
595: setSlot(i, cursor);
596: } else {
597: break;
598: }
599: }
600: }
601: }
602: coll.closeCursor(cursor);
603: coll.commitAutoCommit(doAutoCommit);
604: } else {
605: throw new IllegalStateException();
606: }
607: } catch (Exception e) {
608: coll.closeCursor(cursor);
609: throw coll.handleException(e, doAutoCommit);
610: }
611: }
612:
613: public void add(Object value) {
614:
615: /*
616: * The checkIterAddAllowed method ensures that one of the following two
617: * conditions holds and throws UnsupportedOperationException otherwise:
618: * 1- This is a list iterator for a recno-renumber database.
619: * 2- This is a collection iterator for a duplicates database.
620: */
621: coll.checkIterAddAllowed();
622: OperationStatus status = OperationStatus.SUCCESS;
623: DataCursor cursor = null;
624: boolean doAutoCommit = coll.beginAutoCommit();
625: try {
626: if (coll.view.keysRenumbered
627: || !coll.areDuplicatesOrdered()) {
628:
629: /*
630: * This is a recno-renumber database or a btree/hash database
631: * with unordered duplicates.
632: */
633: boolean hasPrev = hasPrevious();
634: if (!hasPrev && !hasNext()) {
635:
636: /* The collection is empty. */
637: if (coll.view.keysRenumbered) {
638:
639: /* Append to an empty recno-renumber database. */
640: status = coll.view.append(value, null, null);
641:
642: } else if (coll.view.dupsAllowed
643: && coll.view.range.isSingleKey()) {
644:
645: /*
646: * When inserting a duplicate into a single-key range,
647: * the main key is fixed, so we can always insert into
648: * an empty collection.
649: */
650: cursor = new DataCursor(coll.view, writeAllowed);
651: cursor.useRangeKey();
652: status = cursor.putNoDupData(null, value, null,
653: true);
654: coll.closeCursor(cursor);
655: cursor = null;
656: } else {
657: throw new IllegalStateException(
658: "Collection is empty, cannot add() duplicate");
659: }
660:
661: /*
662: * Move past the record just inserted (the cursor should be
663: * closed above to prevent multiple open cursors in certain
664: * DB core modes).
665: */
666: if (status == OperationStatus.SUCCESS) {
667: next();
668: dataIndex = nextIndex - 1;
669: }
670: } else {
671:
672: /*
673: * The collection is non-empty. If hasPrev is true then
674: * the element at (nextIndex - 1) is available; otherwise
675: * the element at nextIndex is available.
676: */
677: cursor = new DataCursor(coll.view, writeAllowed);
678: int insertIndex = hasPrev ? (nextIndex - 1)
679: : nextIndex;
680:
681: if (!moveCursor(insertIndex, cursor)) {
682: throw new IllegalStateException();
683: }
684:
685: /*
686: * For a recno-renumber database or a database with
687: * unsorted duplicates, insert before the iterator 'next'
688: * position, or after the 'prev' position. Then adjust
689: * the slots to account for the inserted record.
690: */
691: status = hasPrev ? cursor.putAfter(value) : cursor
692: .putBefore(value);
693: if (status == OperationStatus.SUCCESS) {
694: insertSlot(nextIndex, cursor);
695: }
696: }
697: } else {
698: /* This is a btree/hash database with ordered duplicates. */
699: cursor = new DataCursor(coll.view, writeAllowed);
700:
701: if (coll.view.range.isSingleKey()) {
702:
703: /*
704: * When inserting a duplicate into a single-key range,
705: * the main key is fixed.
706: */
707: cursor.useRangeKey();
708: } else {
709:
710: /*
711: * When inserting into a multi-key range, the main key
712: * is the last dataIndex accessed by next(), previous()
713: * or add().
714: */
715: if (dataIndex < 0 || !moveCursor(dataIndex, cursor)) {
716: throw new IllegalStateException();
717: }
718: }
719:
720: /*
721: * For a hash/btree with duplicates, insert the duplicate,
722: * put the new record in slot zero, and set the next index
723: * to slot one (past the new record).
724: */
725: status = cursor.putNoDupData(null, value, null, true);
726: if (status == OperationStatus.SUCCESS) {
727: clearSlots();
728: setSlot(0, cursor);
729: dataIndex = 0;
730: nextIndex = 1;
731: }
732: }
733:
734: if (status == OperationStatus.KEYEXIST) {
735: throw new IllegalArgumentException("Duplicate value");
736: } else if (status != OperationStatus.SUCCESS) {
737: throw new IllegalArgumentException("Could not insert: "
738: + status);
739: }
740:
741: /* Prevent subsequent set() or remove() call. */
742: dataObject = null;
743:
744: coll.closeCursor(cursor);
745: coll.commitAutoCommit(doAutoCommit);
746: } catch (Exception e) {
747: coll.closeCursor(cursor);
748: throw coll.handleException(e, doAutoCommit);
749: }
750: }
751:
752: // --- end Iterator/ListIterator methods ---
753:
754: // --- begin BaseIterator methods ---
755:
756: public final ListIterator dup() {
757:
758: return new BlockIterator(this );
759: }
760:
761: public final boolean isCurrentData(Object currentData) {
762:
763: return (dataObject == currentData);
764: }
765:
766: public final boolean moveToIndex(int index) {
767:
768: DataCursor cursor = null;
769: try {
770: cursor = new DataCursor(coll.view, writeAllowed);
771: OperationStatus status = cursor.getSearchKey(new Integer(
772: index), null, false);
773: if (status == OperationStatus.SUCCESS) {
774: clearSlots();
775: setSlot(0, cursor);
776: nextIndex = 0;
777: return true;
778: } else {
779: return false;
780: }
781: } catch (DatabaseException e) {
782: throw StoredContainer.convertException(e);
783: } finally {
784: closeCursor(cursor);
785: }
786: }
787:
788: // --- end BaseIterator methods ---
789: }
|