CursorImpl


1   /*
2    * See the file LICENSE for redistribution information.
3    *
4    * Copyright (c) 2002,2006 Oracle.  All rights reserved.
5    *
6    * $Id: CursorImpl.java,v 1.320 2006/11/28 04:02:55 mark Exp $
7    */
8   
9   package com.sleepycat.je.dbi;
10  
11  import java.util.logging.Level  ;
12  import java.util.logging.Logger  ;
13  
14  import com.sleepycat.je.DatabaseEntry;
15  import com.sleepycat.je.DatabaseException;
16  import com.sleepycat.je.LockNotGrantedException;
17  import com.sleepycat.je.LockStats;
18  import com.sleepycat.je.OperationStatus;
19  import com.sleepycat.je.RunRecoveryException;
20  import com.sleepycat.je.latch.LatchNotHeldException;
21  import com.sleepycat.je.latch.LatchSupport;
22  import com.sleepycat.je.log.LogUtils;
23  import com.sleepycat.je.tree.BIN;
24  import com.sleepycat.je.tree.BINBoundary;
25  import com.sleepycat.je.tree.DBIN;
26  import com.sleepycat.je.tree.DIN;
27  import com.sleepycat.je.tree.DupCountLN;
28  import com.sleepycat.je.tree.IN;
29  import com.sleepycat.je.tree.Key;
30  import com.sleepycat.je.tree.LN;
31  import com.sleepycat.je.tree.Node;
32  import com.sleepycat.je.tree.Tree;
33  import com.sleepycat.je.tree.TreeWalkerStatsAccumulator;
34  import com.sleepycat.je.txn.BasicLocker;
35  import com.sleepycat.je.txn.LockGrantType;
36  import com.sleepycat.je.txn.LockResult;
37  import com.sleepycat.je.txn.LockType;
38  import com.sleepycat.je.txn.Locker;
39  import com.sleepycat.je.txn.ThreadLocker;
40  import com.sleepycat.je.utilint.DbLsn;
41  import com.sleepycat.je.utilint.TestHook;
42  import com.sleepycat.je.utilint.TestHookExecute;
43  
44  /**
45   * A CursorImpl is the internal implementation of the cursor.
46   */
47  public class CursorImpl implements Cloneable   {
48  
49      private static final boolean DEBUG = false;
50  
51      private static final byte CURSOR_NOT_INITIALIZED = 1;
52      private static final byte CURSOR_INITIALIZED = 2;
53      private static final byte CURSOR_CLOSED = 3;
54      private static final String   TRACE_DELETE = "Delete";
55      private static final String   TRACE_MOD = "Mod:";
56  
57      /*
58       * Cursor location in the database, represented by a BIN and an index in
59       * the BIN.  bin/index must have a non-null/non-negative value if dupBin is
60       * set to non-null.
61       */
62      volatile private BIN bin;
63      volatile private int index;
64  
65      /*
66       * Cursor location in a given duplicate set.  If the cursor is not
67       * referencing a duplicate set then these are null.
68       */
69      volatile private DBIN dupBin;
70      volatile private int dupIndex;
71  
72      /*
73       * BIN and DBIN that are no longer referenced by this cursor but have not
74       * yet been removed.  If non-null, the BIN/DBIN will be removed soon.
75       * BIN.adjustCursors should ignore cursors that are to be removed.
76       */
77      volatile private BIN binToBeRemoved;
78      volatile private DBIN dupBinToBeRemoved;
79  
80      /*
81       * The cursor location used for a given operation. 
82       */
83      private BIN targetBin;
84      private int targetIndex;
85      private byte[] dupKey;
86  
87      /* The database behind the handle. */
88      private DatabaseImpl database;
89  
90      /* Owning transaction. */
91      private Locker locker;
92      private CursorImpl lockerPrev; // lockPrev, lockNext used for simple Locker
93      private CursorImpl lockerNext; // chain.
94  
95      /*
96       * Do not release non-transactional locks when cursor is closed.  This flag
97       * is used to support handle locks, which may be non-transactional but must
98       * be retained across cursor operations and cursor close.
99       */
100     private boolean retainNonTxnLocks;
101 
102     /* State of the cursor. See CURSOR_XXX above. */
103     private byte status;
104 
105     private boolean allowEviction;
106     private TestHook testHook;
107 
108     private boolean nonCloning = false;
109 
110     /*
111      * Unique id that we can return as a hashCode to prevent calls to
112      * Object.hashCode(). [#13896]
113      */
114     private int thisId;
115 
116     /*
117      * Allocate hashCode ids from this. [#13896]
118      */
119     private static long lastAllocatedId = 0;
120 
121     private ThreadLocal   treeStatsAccumulatorTL = new ThreadLocal  ();
122 
123     /*
124      * Allocate a new hashCode id.  Doesn't need to be synchronized since it's
125      * ok for two objects to have the same hashcode.
126      */
127     private static long getNextCursorId() {
128         return ++lastAllocatedId;
129     }
130 
131     public int hashCode() {
132     return thisId;
133     }
134 
135     private TreeWalkerStatsAccumulator getTreeStatsAccumulator() {
136     if (EnvironmentImpl.getThreadLocalReferenceCount() > 0) {
137         return (TreeWalkerStatsAccumulator) treeStatsAccumulatorTL.get();
138     } else {
139         return null;
140     }
141     }
142 
143     public void incrementLNCount() {
144         TreeWalkerStatsAccumulator treeStatsAccumulator =
145         getTreeStatsAccumulator();
146     if (treeStatsAccumulator != null) {
147         treeStatsAccumulator.incrementLNCount();
148     }
149     }
150 
151     public void setNonCloning(boolean nonCloning) {
152     this.nonCloning = nonCloning;
153     }
154 
155     /**
156      * public for Cursor et al
157      */
158     public static class SearchMode {
159         public static final SearchMode SET =
160             new SearchMode(true, false, "SET");
161         public static final SearchMode BOTH =
162             new SearchMode(true, true, "BOTH");
163         public static final SearchMode SET_RANGE =
164             new SearchMode(false, false, "SET_RANGE");
165         public static final SearchMode BOTH_RANGE =
166             new SearchMode(false, true, "BOTH_RANGE");
167 
168         private boolean exactSearch;
169         private boolean dataSearch;
170     private String   name;
171 
172         private SearchMode(boolean exactSearch,
173                boolean dataSearch,
174                String   name) {
175             this.exactSearch = exactSearch;
176             this.dataSearch = dataSearch;
177         this.name = "SearchMode." + name;
178         }
179 
180         /**
181          * Returns true when the key or key/data search is exact, i.e., for SET
182          * and BOTH.
183          */
184         public final boolean isExactSearch() {
185             return exactSearch;
186         }
187 
188         /**
189          * Returns true when the data value is included in the search, i.e.,
190          * for BOTH and BOTH_RANGE.
191          */
192         public final boolean isDataSearch() {
193             return dataSearch;
194         }
195 
196     public String   toString() {
197         return name;
198     }
199     }
200 
201     /**
202      * Holder for an OperationStatus and a keyChange flag.  Is used for search
203      * and getNextWithKeyChangeStatus operations.
204      */
205     public static class KeyChangeStatus {
206         
207         /**
208          * Operation status;
209          */
210         public OperationStatus status;
211 
212         /**
213          * Whether the operation moved to a new key.
214          */
215         public boolean keyChange;
216 
217         public KeyChangeStatus(OperationStatus status, boolean keyChange) {
218             this.status = status;
219             this.keyChange = keyChange;
220         }
221     }
222 
223     /**
224      * Creates a cursor with retainNonTxnLocks=true.
225      */
226     public CursorImpl(DatabaseImpl database, Locker locker) 
227         throws DatabaseException {
228 
229         this(database, locker, true);
230     }
231 
232     /**
233      * Creates a cursor.
234      *
235      * @param retainNonTxnLocks is true if non-transactional locks should be
236      * retained (not released automatically) when the cursor is closed.
237      */
238     public CursorImpl(DatabaseImpl database,
239               Locker locker,
240                       boolean retainNonTxnLocks)
241         throws DatabaseException {
242 
243     thisId = (int) getNextCursorId();
244         bin = null;
245         index = -1;
246         dupBin = null;
247         dupIndex = -1;
248 
249         // retainNonTxnLocks=true should not be used with a ThreadLocker
250         assert !(retainNonTxnLocks && (locker instanceof ThreadLocker));
251 
252         // retainNonTxnLocks=false should not be used with a BasicLocker
253         assert !(!retainNonTxnLocks && locker.getClass() == BasicLocker.class);
254 
255         this.retainNonTxnLocks = retainNonTxnLocks;
256 
257         // Associate this cursor with the database
258         this.database = database;
259         this.locker = locker;
260         this.locker.registerCursor(this);
261 
262         status = CURSOR_NOT_INITIALIZED;
263 
264         /*
265          * Do not perform eviction here because we may be synchronized on the
266          * Database instance. For example, this happens when we call
267          * Database.openCursor().  Also eviction may be disabled after the
268          * cursor is constructed.
269          */
270     }
271 
272     /**
273      * Disables or enables eviction during cursor operations.  For example, a
274      * cursor used to implement eviction (e.g., in some UtilizationProfile and
275      * most DbTree methods) should not itself perform eviction, but eviction
276      * should be enabled for user cursors.  Eviction is disabled by default.
277      */
278     public void setAllowEviction(boolean allowed) {
279         allowEviction = allowed;
280     }
281 
282     /**
283      * Shallow copy.  addCursor() is optionally called.
284      */
285     public CursorImpl cloneCursor(boolean addCursor)
286         throws DatabaseException {
287 
288         return cloneCursor(addCursor, null);
289     }
290 
291     /**
292      * Shallow copy.  addCursor() is optionally called.  Allows inheriting the
293      * BIN position from some other cursor.
294      */
295     public CursorImpl cloneCursor(boolean addCursor, CursorImpl usePosition)
296         throws DatabaseException {
297 
298         CursorImpl ret = null;
299     if (nonCloning) {
300         ret = this;
301     } else {
302         try {
303         latchBINs();
304         ret = (CursorImpl) super.clone();
305 
306         if (!retainNonTxnLocks) {
307             ret.locker = locker.newNonTxnLocker();
308         }
309 
310         ret.locker.registerCursor(ret);
311         if (usePosition != null &&
312             usePosition.status == CURSOR_INITIALIZED) {
313             ret.bin = usePosition.bin;
314             ret.index = usePosition.index;
315             ret.dupBin = usePosition.dupBin;
316             ret.dupIndex = usePosition.dupIndex;
317         }
318         if (addCursor) {
319             ret.addCursor();
320         }
321         } catch (CloneNotSupportedException   cannotOccur) {
322         return null;
323         } finally {
324         releaseBINs();
325         }
326     }
327 
328         /* Perform eviction before and after each cursor operation. */
329         if (allowEviction) {
330             database.getDbEnvironment().getEvictor().doCriticalEviction
331                 (false); // backgroundIO
332         }
333         return ret;
334     }
335 
336     public int getIndex() {
337         return index;
338     }
339 
340     public void setIndex(int idx) {
341         index = idx;
342     }
343 
344     public BIN getBIN() {
345         return bin;
346     }
347 
348     public void setBIN(BIN newBin) {
349         bin = newBin;
350     }
351 
352     public BIN getBINToBeRemoved() {
353         return binToBeRemoved;
354     }
355 
356     public int getDupIndex() {
357         return dupIndex;
358     }
359 
360     public void setDupIndex(int dupIdx) {
361         dupIndex = dupIdx;
362     }
363 
364     public DBIN getDupBIN() {
365         return dupBin;
366     }
367 
368     public void setDupBIN(DBIN newDupBin) {
369         dupBin = newDupBin;
370     }
371 
372     public DBIN getDupBINToBeRemoved() {
373         return dupBinToBeRemoved;
374     }
375 
376     public void setTreeStatsAccumulator(TreeWalkerStatsAccumulator tSA) {
377     treeStatsAccumulatorTL.set(tSA);
378     }
379 
380     /**
381      * Figure out which BIN/index set to use.
382      */
383     private boolean setTargetBin() {
384         targetBin = null;
385         targetIndex = 0;
386         boolean isDup = (dupBin != null);
387         dupKey = null;
388         if (isDup) {
389             targetBin = dupBin;
390             targetIndex = dupIndex;
391             dupKey = dupBin.getDupKey();
392         } else {
393             targetBin = bin;
394             targetIndex = index;
395         }
396         return isDup;
397     }
398 
399     /**
400      * Advance a cursor.  Used so that verify can advance a cursor even in the
401      * face of an exception [12932].
402      * @param key on return contains the key if available, or null.
403      * @param data on return contains the data if available, or null.
404      */
405     public boolean advanceCursor(DatabaseEntry key, DatabaseEntry data) {
406 
407         BIN oldBin = bin;
408         BIN oldDupBin = dupBin;
409         int oldIndex = index;
410         int oldDupIndex = dupIndex;
411 
412         key.setData(null);
413         data.setData(null);
414 
415         try {
416             getNext(key, data, LockType.NONE,
417             true /* forward */,
418             false /* alreadyLatched */);
419         } catch (DatabaseException ignored) {
420         /* Klockwork - ok */
421     }
422 
423         /*
424          * If the position changed, regardless of an exception, then we believe
425          * that we have advanced the cursor.
426          */
427         if (bin != oldBin ||
428             dupBin != oldDupBin ||
429             index != oldIndex ||
430             dupIndex != oldDupIndex) {
431 
432             /*
433              * Return the key and data from the BIN entries, if we were not
434              * able to read it above.
435              */
436             if (key.getData() == null &&
437                 bin != null &&
438                 index > 0) {
439                 setDbt(key, bin.getKey(index));
440             }
441             if (data.getData() == null &&
442                 dupBin != null &&
443                 dupIndex > 0) {
444                 setDbt(data, dupBin.getKey(dupIndex));
445             }
446             return true;
447         } else {
448             return false;
449         }
450     }
451 
452     public BIN latchBIN()
453         throws DatabaseException {
454 
455     while (bin != null) {
456         BIN waitingOn = bin;
457         waitingOn.latch();
458         if (bin == waitingOn) {
459         return bin;
460         }
461         waitingOn.releaseLatch();
462     }
463 
464     return null;
465     }
466 
467     public void releaseBIN()
468         throws LatchNotHeldException {
469 
470         if (bin != null) {
471             bin.releaseLatchIfOwner();
472         }
473     }
474 
475     public void latchBINs()
476         throws DatabaseException {
477 
478         latchBIN();
479         latchDBIN();
480     }
481 
482     public void releaseBINs()
483         throws LatchNotHeldException {
484 
485         releaseBIN();
486         releaseDBIN();
487     }
488 
489     public DBIN latchDBIN()
490         throws DatabaseException {
491 
492     while (dupBin != null) {
493         BIN waitingOn = dupBin;
494         waitingOn.latch();
495         if (dupBin == waitingOn) {
496         return dupBin;
497         }
498         waitingOn.releaseLatch();
499     }
500     return null;
501     }
502 
503     public void releaseDBIN()
504         throws LatchNotHeldException {
505 
506         if (dupBin != null) {
507             dupBin.releaseLatchIfOwner();
508         }
509     }
510 
511     public Locker getLocker() {
512         return locker;
513     }
514 
515     public void addCursor(BIN bin) {
516         if (bin != null) {
517             assert bin.isLatchOwnerForWrite();
518             bin.addCursor(this);
519         }
520     }
521 
522     /**
523      * Add to the current cursor. (For dups)
524      */
525     public void addCursor() {
526         if (dupBin != null) {
527             addCursor(dupBin);
528         }
529         if (bin != null) {
530             addCursor(bin);
531         }
532     }
533 
534     /*
535      * Update a cursor to refer to a new BIN or DBin following an insert.
536      * Don't bother removing this cursor from the previous bin.  Cursor will do
537      * that with a cursor swap thereby preventing latch deadlocks down here.
538      */
539     public void updateBin(BIN bin, int index) 
540         throws DatabaseException {
541 
542         removeCursorDBIN();
543         setDupIndex(-1);
544         setDupBIN(null);
545         setIndex(index);
546         setBIN(bin);
547         addCursor(bin);
548     }
549 
550     public void updateDBin(DBIN dupBin, int dupIndex) {
551         setDupIndex(dupIndex);
552         setDupBIN(dupBin);
553         addCursor(dupBin);
554     }
555 
556     private void removeCursor()
557         throws DatabaseException {
558 
559         removeCursorBIN();
560         removeCursorDBIN();
561     }
562 
563     private void removeCursorBIN()
564     throws DatabaseException {
565 
566     BIN abin = latchBIN();
567     if (abin != null) {
568         abin.removeCursor(this);
569         abin.releaseLatch();
570     }
571     }
572 
573     private void removeCursorDBIN()
574     throws DatabaseException {
575     
576     DBIN abin = latchDBIN();
577     if (abin != null) {
578         abin.removeCursor(this);
579         abin.releaseLatch();
580     }
581     }
582 
583     /**
584      * Clear the reference to the dup tree, if any.
585      */
586     public void clearDupBIN(boolean alreadyLatched)
587     throws DatabaseException {
588 
589         if (dupBin != null) {
590             if (alreadyLatched) {
591                 dupBin.removeCursor(this);
592                 dupBin.releaseLatch();
593             } else {
594                 removeCursorDBIN();
595             }
596             dupBin = null;
597             dupIndex = -1;
598         }
599     }
600 
601     public void dumpTree()
602         throws DatabaseException {
603 
604         database.getTree().dump();
605     }
606 
607     /**
608      * @return true if this cursor is closed
609      */
610     public boolean isClosed() {
611         return (status == CURSOR_CLOSED);
612     }
613 
614     /**
615      * @return true if this cursor is not initialized
616      */
617     public boolean isNotInitialized() {
618         return (status == CURSOR_NOT_INITIALIZED);
619     }
620 
621     /**
622      * Reset a cursor to an uninitialized state, but unlike close(), allow it
623      * to be used further.
624      */
625     public void reset()
626         throws DatabaseException {
627 
628         removeCursor();
629 
630         if (!retainNonTxnLocks) {
631             locker.releaseNonTxnLocks();
632         }
633 
634         bin = null;
635         index = -1;
636         dupBin = null;
637         dupIndex = -1;
638 
639         status = CURSOR_NOT_INITIALIZED;
640 
641         /* Perform eviction before and after each cursor operation. */
642         if (allowEviction) {
643             database.getDbEnvironment().getEvictor().doCriticalEviction
644                 (false); // backgroundIO
645         }
646     }
647 
648     /**
649      * Close a cursor.
650      * @throws DatabaseException if the cursor was previously closed.
651      */
652     public void close()
653         throws DatabaseException {
654 
655         assert assertCursorState(false) : dumpToString(true);
656 
657         removeCursor();
658         locker.unRegisterCursor(this);
659 
660         if (!retainNonTxnLocks) {
661             locker.releaseNonTxnLocks();
662         }
663 
664         status = CURSOR_CLOSED;
665 
666         /* Perform eviction before and after each cursor operation. */
667         if (allowEviction) {
668             database.getDbEnvironment().getEvictor().doCriticalEviction
669                 (false); // backgroundIO
670         }
671     }
672 
673     public int count(LockType lockType)
674         throws DatabaseException {
675 
676         assert assertCursorState(true) : dumpToString(true);
677 
678         if (!database.getSortedDuplicates()) {
679             return 1;
680         }
681 
682         if (bin == null) {
683             return 0;
684         }
685 
686     latchBIN();
687         try {
688             if (bin.getNEntries() <= index) {
689                 return 0;
690             }
691 
692             /* If fetchTarget returns null, a deleted LN was cleaned. */
693             Node n = bin.fetchTarget(index);
694             if (n != null && n.containsDuplicates()) {
695                 DIN dupRoot = (DIN) n;
696 
697                 /* Latch couple down the tree. */
698                 dupRoot.latch();
699                 releaseBIN();
700                 DupCountLN dupCountLN = (DupCountLN)
701                     dupRoot.getDupCountLNRef().fetchTarget(database, dupRoot);
702 
703                 /* We can't hold latches when we acquire locks. */
704                 dupRoot.releaseLatch();
705 
706                 /*
707                  * Call lock directly.  There is no need to call lockLN because
708                  * the node ID cannot change (a slot cannot be reused) for a
709                  * DupCountLN.
710                  */
711                 if (lockType != LockType.NONE) {
712                     locker.lock
713                         (dupCountLN.getNodeId(), lockType, false /*noWait*/,
714                          database);
715                 }
716                 return dupCountLN.getDupCount();
717             } else {
718                 /* If an LN is in the slot, the count is one. */
719                 return 1;
720             }
721         } finally {
722         releaseBIN();
723         }
724     }
725 
726     /**
727      * Delete the item pointed to by the cursor. If cursor is not initialized
728      * or item is already deleted, return appropriate codes. Returns with
729      * nothing latched.  bin and dupBin are latched as appropriate.
730      *
731      * @return 0 on success, appropriate error code otherwise.
732      */
733     public OperationStatus delete()
734         throws DatabaseException {
735 
736         assert assertCursorState(true) : dumpToString(true);
737         boolean isDup = setTargetBin();
738 
739         /* If nothing at current position, return. */
740         if (targetBin == null) {
741             return OperationStatus.KEYEMPTY;
742         }
743 
744         /* 
745          * Check if this is already deleted. We may know that the record is
746          * deleted w/out seeing the LN.
747          */
748         if (targetBin.isEntryKnownDeleted(targetIndex)) {
749             releaseBINs();
750             return OperationStatus.KEYEMPTY;
751         }
752 
753         /* If fetchTarget returns null, a deleted LN was cleaned. */
754         LN ln = (LN) targetBin.fetchTarget(targetIndex);
755         if (ln == null) {
756         releaseBINs();
757             return OperationStatus.KEYEMPTY;
758         }
759 
760         /* Get a write lock. */
761     LockResult lockResult = lockLN(ln, LockType.WRITE);
762     ln = lockResult.getLN();
763             
764         /* Check LN deleted status under the protection of a write lock. */
765         if (ln == null) {
766             releaseBINs();
767             return OperationStatus.KEYEMPTY;
768         }
769 
770         /* Lock the DupCountLN before logging any LNs. */
771         LockResult dclLockResult = null;
772         DIN dupRoot = null;
773     boolean dupRootIsLatched = false;
774         try {
775             isDup = (dupBin != null);
776             if (isDup) {
777                 dupRoot = getLatchedDupRoot(true /*isDBINLatched*/);
778                 dclLockResult = lockDupCountLN(dupRoot, LockType.WRITE);
779         /* Don't mark latched until after locked. */
780         dupRootIsLatched = true;
781 
782                 /* 
783                  * Refresh the dupRoot variable because it may have changed
784                  * during locking, but is sure to be resident and latched by
785                  * lockDupCountLN.
786                  */
787                 dupRoot = (DIN) bin.getTarget(index);
788                 /* Release BIN to increase concurrency. */
789                 releaseBIN();
790             }
791 
792             /*
793              * Between the release of the BIN latch and acquiring the write
794              * lock any number of operations may have executed which would
795              * result in a new abort LSN for this record. Therefore, wait until
796              * now to get the abort LSN.
797              */
798             setTargetBin();
799             long oldLsn = targetBin.getLsn(targetIndex);
800             byte[] lnKey = targetBin.getKey(targetIndex);
801             lockResult.setAbortLsn
802                 (oldLsn, targetBin.isEntryKnownDeleted(targetIndex));
803 
804             /* Log the LN. */
805             long oldLNSize = ln.getMemorySizeIncludedByParent();
806             long newLsn = ln.delete(database, lnKey, dupKey, oldLsn, locker);
807             long newLNSize = ln.getMemorySizeIncludedByParent();
808 
809             /*
810              * Now update the parent of the LN (be it BIN or DBIN) to correctly
811              * reference the LN and adjust the memory sizing.  Be sure to do
812              * this update of the LSN before updating the dup count LN. In case
813              * we encounter problems there we need the LSN to match the latest
814              * version to ensure that undo works.
815              */
816             targetBin.updateEntry(targetIndex, newLsn, oldLNSize, newLNSize);
817             targetBin.setPendingDeleted(targetIndex);
818             releaseBINs();
819 
820             if (isDup) {
821                 dupRoot.incrementDuplicateCount
822                     (dclLockResult, dupKey, locker, false /*increment*/);
823                 dupRoot.releaseLatch();
824         dupRootIsLatched = false;
825                 dupRoot = null;
826 
827                 locker.addDeleteInfo(dupBin, new Key(lnKey));
828             } else {
829                 locker.addDeleteInfo(bin, new Key(lnKey));
830             } 
831 
832             trace(Level.FINER, TRACE_DELETE, targetBin,
833                   ln, targetIndex, oldLsn, newLsn);
834         } finally {
835             if (dupRoot != null &&
836         dupRootIsLatched) {
837                 dupRoot.releaseLatchIfOwner();
838             }
839         }
840             
841         return OperationStatus.SUCCESS;
842     }
843 
844     /**
845      * Return a new copy of the cursor. If position is true, position the
846      * returned cursor at the same position.
847      */
848     public CursorImpl dup(boolean samePosition)
849         throws DatabaseException {
850 
851         assert assertCursorState(false) : dumpToString(true);
852 
853         CursorImpl ret = cloneCursor(samePosition);
854 
855         if (!samePosition) {
856             ret.bin = null;
857             ret.index = -1;
858             ret.dupBin = null;
859             ret.dupIndex = -1;
860 
861             ret.status = CURSOR_NOT_INITIALIZED;
862         }
863 
864         return ret;
865     }
866 
867     /**
868      * Evict the LN node at the cursor position.  This is used for internal
869      * databases only.
870      */
871     public void evict()
872         throws DatabaseException {
873 
874         evict(false); // alreadyLatched
875     }
876 
877     /**
878      * Evict the LN node at the cursor position.  This is used for internal
879      * databases only.
880      */
881     public void evict(boolean alreadyLatched)
882         throws DatabaseException {
883 
884         try {
885             if (!alreadyLatched) {
886                 latchBINs();
887             }
888             setTargetBin();
889             if (targetIndex >= 0) {
890                 targetBin.evictLN(targetIndex);
891             }
892         } finally {
893             if (!alreadyLatched) {
894                 releaseBINs();
895             }
896         }
897     }
898 
899     /*
900      * Puts 
901      */
902 
903     /**
904      * Search for the next key (or duplicate) following the given key (and
905      * datum), and acquire a range insert lock on it.  If there are no more
906      * records following the given key and datum, lock the special EOF node
907      * for the database.
908      */
909     public void lockNextKeyForInsert(DatabaseEntry key, DatabaseEntry data)
910         throws DatabaseException {
911 
912         DatabaseEntry tempKey = new DatabaseEntry
913             (key.getData(), key.getOffset(), key.getSize());
914         DatabaseEntry tempData = new DatabaseEntry
915             (data.getData(), data.getOffset(), data.getSize());
916         tempKey.setPartial(0, 0, true);
917         tempData.setPartial(0, 0, true);
918         boolean lockedNextKey = false;
919 
920         /* Don't search for data if duplicates are not configured. */
921         SearchMode searchMode = database.getSortedDuplicates() ?
922             SearchMode.BOTH_RANGE : SearchMode.SET_RANGE;
923         boolean latched = true;
924         try {
925             /* Search. */
926             int searchResult = searchAndPosition
927                 (tempKey, tempData, searchMode, LockType.RANGE_INSERT);
928             if ((searchResult & FOUND) != 0 &&
929                 (searchResult & FOUND_LAST) == 0) {
930 
931                 /*
932                  * If searchAndPosition found a record (other than the last
933                  * one), in all cases we should advance to the next record:
934                  *
935                  * 1- found a deleted record,
936                  * 2- found an exact match, or
937                  * 3- found the record prior to the given key/data.
938                  *
939                  * If we didn't match the key, skip over duplicates to the next
940                  * key with getNextNoDup.
941                  */
942                 OperationStatus status;
943                 if ((searchResult & EXACT_KEY) != 0) {
944                     status = getNext
945                         (tempKey, tempData, LockType.RANGE_INSERT, true, true);
946                 } else {
947                     status = getNextNoDup
948                         (tempKey, tempData, LockType.RANGE_INSERT, true, true);
949                 }
950                 if (status == OperationStatus.SUCCESS) {
951                     lockedNextKey = true;
952                 }
953                 latched = false;
954             }
955         } finally {
956             if (latched) {
957                 releaseBINs();
958             }
959         }
960 
961         /* Lock the EOF node if no next key was found. */
962         if (!lockedNextKey) {
963             lockEofNode(LockType.RANGE_INSERT);
964         }
965     }
966 
967     /**
968      * Insert the given LN in the tree or return KEYEXIST if the key is already
969      * present.
970      *
971      * <p>This method is called directly internally for putting tree map LNs
972      * and file summary LNs.  It should not be used otherwise, and in the
973      * future we should find a way to remove this special case.</p>
974      */
975     public OperationStatus putLN(byte[] key, LN ln, boolean allowDuplicates)
976         throws DatabaseException {
977 
978         assert assertCursorState(false) : dumpToString(true);
979 
980         assert LatchSupport.countLatchesHeld() == 0;
981     LockResult lockResult = locker.lock
982             (ln.getNodeId(), LockType.WRITE, false /*noWait*/, database);
983 
984     /* 
985      * We'll set abortLsn down in Tree.insert when we know whether we're
986      * re-using a BIN entry or not.
987      */
988         if (database.getTree().insert
989             (ln, key, allowDuplicates, this, lockResult)) {
990             status = CURSOR_INITIALIZED;
991             return OperationStatus.SUCCESS;
992         } else {
993             locker.releaseLock(ln.getNodeId());
994             return OperationStatus.KEYEXIST;
995         }
996     }
997 
998     /**
999      * Insert or overwrite the key/data pair.
1000     * @param key
1001     * @param data
1002     * @return 0 if successful, failure status value otherwise
1003     */
1004    public OperationStatus put(DatabaseEntry key,
1005                   DatabaseEntry data,
1006                               DatabaseEntry foundData) 
1007        throws DatabaseException {
1008
1009        assert assertCursorState(false) : dumpToString(true);
1010
1011        OperationStatus result = putLN
1012            (Key.makeKey(key), new LN(data), database.getSortedDuplicates());
1013        if (result == OperationStatus.KEYEXIST) {
1014            status = CURSOR_INITIALIZED;
1015
1016            /* 
1017             * If dups are allowed and putLN() returns KEYEXIST, the duplicate
1018             * already exists.  However, we still need to get a write lock, and
1019             * calling putCurrent does that.  Without duplicates, we have to
1020             * update the data of course.
1021             */
1022            result = putCurrent(data, null, foundData);
1023        }
1024        return result;
1025    }
1026
1027    /**
1028     * Insert the key/data pair in No Overwrite mode.
1029     * @param key
1030     * @param data
1031     * @return 0 if successful, failure status value otherwise
1032     */
1033    public OperationStatus putNoOverwrite(DatabaseEntry key,
1034                      DatabaseEntry data) 
1035        throws DatabaseException {
1036
1037        assert assertCursorState(false) : dumpToString(true);
1038
1039        return putLN(Key.makeKey(key), new LN(data), false);
1040    }
1041
1042    /**
1043     * Insert the key/data pair as long as no entry for key/data exists yet.
1044     */
1045    public OperationStatus putNoDupData(DatabaseEntry key, DatabaseEntry data)
1046        throws DatabaseException {
1047
1048        assert assertCursorState(false) : dumpToString(true);
1049
1050        if (!database.getSortedDuplicates()) {
1051            throw new DatabaseException
1052                ("putNoDupData() called, but database is not configured " +
1053                 "for duplicate data.");
1054        }
1055        return putLN(Key.makeKey(key), new LN(data), true);
1056    }
1057
1058    /**
1059     * Modify the current record with this data.
1060     * @param data
1061     */
1062    public OperationStatus putCurrent(DatabaseEntry data,
1063                                      DatabaseEntry foundKey,
1064                                      DatabaseEntry foundData)
1065        throws DatabaseException {
1066
1067        assert assertCursorState(true) : dumpToString(true);
1068
1069        if (foundKey != null) {
1070            foundKey.setData(null);
1071        }
1072        if (foundData != null) {
1073            foundData.setData(null);
1074        }
1075
1076        if (bin == null) {
1077            return OperationStatus.KEYEMPTY;
1078        }
1079        
1080    latchBINs();
1081        boolean isDup = setTargetBin();
1082
1083        try {
1084
1085            /* 
1086             * Find the existing entry and get a reference to all BIN fields
1087             * while latched.
1088             */
1089            LN ln = (LN) targetBin.fetchTarget(targetIndex);
1090            byte[] lnKey = targetBin.getKey(targetIndex);
1091
1092            /* If fetchTarget returned null, a deleted LN was cleaned. */
1093        if (targetBin.isEntryKnownDeleted(targetIndex) ||
1094                ln == null) {
1095                releaseBINs();
1096        return OperationStatus.NOTFOUND;
1097        }
1098
1099            /* Get a write lock. */
1100        LockResult lockResult = lockLN(ln, LockType.WRITE);
1101        ln = lockResult.getLN();
1102
1103        /* Check LN deleted status under the protection of a write lock. */
1104        if (ln == null) {
1105                releaseBINs();
1106        return OperationStatus.NOTFOUND;
1107        }
1108
1109            /*
1110             * If cursor points at a dup, then we can only replace the entry
1111             * with a new entry that is "equal" to the old one.  Since a user
1112             * defined comparison function may actually compare equal for two
1113             * byte sequences that are actually different we still have to do
1114             * the replace.  Arguably we could skip the replacement if there is
1115             * no user defined comparison function and the new data is the
1116             * same.
1117             */
1118        byte[] foundDataBytes;
1119        byte[] foundKeyBytes;
1120        isDup = setTargetBin();
1121        if (isDup) {
1122        foundDataBytes = lnKey;
1123        foundKeyBytes = targetBin.getDupKey();
1124        } else {
1125        foundDataBytes = ln.getData();
1126        foundKeyBytes = lnKey;
1127        }
1128            byte[] newData;
1129
1130            /* Resolve partial puts. */
1131            if (data.getPartial()) {
1132                int dlen = data.getPartialLength();
1133                int doff = data.getPartialOffset();
1134                int origlen = (foundDataBytes != null) ?
1135                    foundDataBytes.length : 0;
1136                int oldlen = (doff + dlen > origlen) ? doff + dlen : origlen;
1137                int len = oldlen - dlen + data.getSize();
1138
1139        if (len == 0) {
1140            newData = LogUtils.ZERO_LENGTH_BYTE_ARRAY;
1141        } else {
1142            newData = new byte[len];
1143        }
1144                int pos = 0;
1145
1146                /*
1147         * Keep 0..doff of the old data (truncating if doff > length).
1148         */
1149                int slicelen = (doff < origlen) ? doff : origlen;
1150                if (slicelen > 0)
1151                    System.arraycopy(foundDataBytes, 0, newData,
1152                     pos, slicelen);
1153                pos += doff;
1154
1155                /* Copy in the new data. */
1156                slicelen = data.getSize();
1157                System.arraycopy(data.getData(), data.getOffset(),
1158                                 newData, pos, slicelen);
1159                pos += slicelen;
1160
1161                /* Append the rest of the old data (if any). */
1162                slicelen = origlen - (doff + dlen);
1163                if (slicelen > 0)
1164                    System.arraycopy(foundDataBytes, doff + dlen, newData, pos,
1165                                     slicelen);
1166            } else {
1167                int len = data.getSize();
1168        if (len == 0) {
1169            newData = LogUtils.ZERO_LENGTH_BYTE_ARRAY;
1170        } else {
1171            newData = new byte[len];
1172        }
1173                System.arraycopy(data.getData(), data.getOffset(),
1174                                 newData, 0, len);
1175            }
1176
1177            if (database.getSortedDuplicates()) {
1178        /* Check that data compares equal before replacing it. */
1179        boolean keysEqual = false;
1180
1181        if (foundDataBytes != null) {
1182                    keysEqual = Key.compareKeys
1183                        (foundDataBytes, newData,
1184             database.getDuplicateComparator()) == 0;
1185        }
1186
1187        if (!keysEqual) {
1188            revertLock(ln, lockResult);
1189            throw new DatabaseException
1190            ("Can't replace a duplicate with different data.");
1191        }
1192        }
1193
1194        if (foundData != null) {
1195        setDbt(foundData, foundDataBytes);
1196        }
1197        if (foundKey != null) {
1198        setDbt(foundKey, foundKeyBytes);
1199        }
1200
1201            /*
1202             * Between the release of the BIN latch and acquiring the write
1203             * lock any number of operations may have executed which would
1204             * result in a new abort LSN for this record. Therefore, wait until
1205             * now to get the abort LSN.
1206             */
1207        long oldLsn = targetBin.getLsn(targetIndex);
1208        lockResult.setAbortLsn
1209        (oldLsn, targetBin.isEntryKnownDeleted(targetIndex));
1210
1211            /* 
1212         * The modify has to be inside the latch so that the BIN is updated
1213         * inside the latch.
1214         */
1215            long oldLNSize = ln.getMemorySizeIncludedByParent();
1216        byte[] newKey = (isDup ? targetBin.getDupKey() : lnKey);
1217            long newLsn = ln.modify(newData, database, newKey, oldLsn, locker);
1218            long newLNSize = ln.getMemorySizeIncludedByParent();
1219
1220            /* Update the parent BIN. */
1221            targetBin.updateEntry(targetIndex, newLsn, oldLNSize, newLNSize);
1222            releaseBINs();
1223
1224            trace(Level.FINER, TRACE_MOD, targetBin,
1225                  ln, targetIndex, oldLsn, newLsn);
1226
1227            status = CURSOR_INITIALIZED;
1228            return OperationStatus.SUCCESS;
1229        } finally {
1230            releaseBINs();
1231        }
1232    }
1233
1234    /*
1235     * Gets 
1236     */
1237
1238    /**
1239     * Retrieve the current record.
1240     */
1241    public OperationStatus getCurrent(DatabaseEntry foundKey,
1242                      DatabaseEntry foundData,
1243                      LockType lockType)
1244        throws DatabaseException {
1245
1246        assert assertCursorState(true) : dumpToString(true);
1247
1248        // If not pointing at valid entry, return failure
1249        if (bin == null) {
1250            return OperationStatus.KEYEMPTY;
1251        }
1252
1253        if (dupBin == null) {
1254        latchBIN();
1255        } else {
1256        latchDBIN();
1257        }
1258
1259        return getCurrentAlreadyLatched(foundKey, foundData, lockType, true);
1260    }
1261
1262    /**
1263     * Retrieve the current record. Assume the bin is already latched.  Return
1264     * with the target bin unlatched.
1265     */
1266    public OperationStatus getCurrentAlreadyLatched(DatabaseEntry foundKey,
1267                            DatabaseEntry foundData,
1268                            LockType lockType,
1269                            boolean first)
1270        throws DatabaseException {
1271
1272        assert assertCursorState(true) : dumpToString(true);
1273        assert checkAlreadyLatched(true) : dumpToString(true);
1274
1275        try {
1276            return fetchCurrent(foundKey, foundData, lockType, first);
1277        } finally {
1278            releaseBINs();
1279        }
1280    }
1281
1282    /**
1283     * Retrieve the current LN, return with the target bin unlatched.
1284     */
1285    public LN getCurrentLN(LockType lockType) 
1286        throws DatabaseException {
1287
1288        assert assertCursorState(true) : dumpToString(true);
1289
1290        if (bin == null) {
1291            return null;
1292        } else {
1293        latchBIN();
1294            return getCurrentLNAlreadyLatched(lockType);
1295        }
1296    }
1297
1298    /**
1299     * Retrieve the current LN, assuming the BIN is already latched.  Return
1300     * with the target BIN unlatched.
1301     */
1302    public LN getCurrentLNAlreadyLatched(LockType lockType) 
1303        throws DatabaseException {
1304
1305        try {
1306            assert assertCursorState(true) : dumpToString(true);
1307            assert checkAlreadyLatched(true) : dumpToString(true);
1308
1309            if (bin == null) {
1310                return null;
1311            }
1312
1313            /*
1314             * Get a reference to the LN under the latch.  Check the deleted
1315             * flag in the BIN.  If fetchTarget returns null, a deleted LN was
1316             * cleaned.
1317             */
1318            LN ln = null;
1319            if (!bin.isEntryKnownDeleted(index)) {
1320                ln = (LN) bin.fetchTarget(index);
1321            }
1322            if (ln == null) {
1323        releaseBIN();
1324                return null;
1325            }
1326
1327            addCursor(bin);
1328        
1329            /* Lock LN.  */
1330            LockResult lockResult = lockLN(ln, lockType);
1331        ln = lockResult.getLN();
1332
1333            /* Don't set abort LSN for a read operation! */
1334            return ln;
1335
1336        } finally {
1337            releaseBINs();
1338        }
1339    }
1340
1341    public OperationStatus getNext(DatabaseEntry foundKey,
1342                   DatabaseEntry foundData,
1343                   LockType lockType,
1344                   boolean forward,
1345                   boolean alreadyLatched)
1346        throws DatabaseException {
1347
1348        return getNextWithKeyChangeStatus
1349            (foundKey, foundData, lockType, forward, alreadyLatched).status;
1350    }
1351
1352    /**
1353     * Move the cursor forward and return the next record. This will cross BIN
1354     * boundaries and dip into duplicate sets.
1355     *
1356     * @param foundKey DatabaseEntry to use for returning key
1357     *
1358     * @param foundData DatabaseEntry to use for returning data
1359     *
1360     * @param forward if true, move forward, else move backwards
1361     *
1362     * @param alreadyLatched if true, the bin that we're on is already
1363     * latched.
1364     *
1365     * @return the status and an indication of whether we advanced to a new
1366     * key during the operation.
1367     */
1368    public KeyChangeStatus
1369        getNextWithKeyChangeStatus(DatabaseEntry foundKey,
1370                   DatabaseEntry foundData,
1371                   LockType lockType,
1372                   boolean forward,
1373                   boolean alreadyLatched)
1374        throws DatabaseException {
1375
1376        assert assertCursorState(true) : dumpToString(true);
1377        assert checkAlreadyLatched(alreadyLatched) : dumpToString(true);
1378
1379        KeyChangeStatus result =
1380            new KeyChangeStatus(OperationStatus.NOTFOUND, true);
1381
1382    try {
1383            while (bin != null) {
1384
1385                /* Are we positioned on a DBIN? */
1386                if (dupBin != null) {
1387                    if (DEBUG) {
1388                        verifyCursor(dupBin);
1389                    }
1390                    if (getNextDuplicate(foundKey, foundData, lockType,
1391                                         forward, alreadyLatched) ==
1392                        OperationStatus.SUCCESS) {
1393                        result.status = OperationStatus.SUCCESS;
1394                        /* We returned a duplicate. */
1395                        result.keyChange = false;
1396                        break;
1397                    } else {
1398                        removeCursorDBIN();
1399                        alreadyLatched = false;
1400                        dupBin = null;
1401                        dupIndex = -1;
1402                        continue;
1403                    }
1404                }
1405
1406                assert checkAlreadyLatched(alreadyLatched) :
1407                    dumpToString(true);
1408                if (!alreadyLatched) {
1409                    latchBIN();
1410                } else {
1411                    alreadyLatched = false;
1412                }
1413
1414                if (DEBUG) {
1415                    verifyCursor(bin);
1416                }           
1417
1418                /* Is there anything left on this BIN? */
1419                if ((forward && ++index < bin.getNEntries()) ||
1420                    (!forward && --index > -1)) {
1421
1422                    OperationStatus ret =
1423                        getCurrentAlreadyLatched(foundKey, foundData,
1424                                                 lockType, forward);
1425                    if (ret == OperationStatus.SUCCESS) {
1426                        incrementLNCount();
1427                        result.status = OperationStatus.SUCCESS;
1428                        break;
1429                    } else {
1430                        assert LatchSupport.countLatchesHeld() == 0;
1431
1432                        if (binToBeRemoved != null) {
1433                            flushBINToBeRemoved();
1434                        }
1435
1436                        continue;
1437                    }
1438
1439                } else {
1440                    
1441                    /*
1442                     * PriorBIN is used to release a BIN earlier in the 
1443                     * traversal chain when we move onto the next BIN. When
1444                     * we traverse across BINs, there is a point when two BINs
1445                     * point to the same cursor.
1446                     *
1447                     * Example:  BINa(empty) BINb(empty) BINc(populated)
1448                     *           Cursor (C) is traversing
1449                     * loop, leaving BINa: 
1450                     *   priorBIN is null, C points to BINa, BINa points to C
1451                     *   set priorBin to BINa
1452                     *   find BINb, make BINb point to C 
1453                     *   note that BINa and BINb point to C.
1454                     * loop, leaving BINb:
1455                     *   priorBIN == BINa, remove C from BINa
1456                     *   set priorBin to BINb
1457                     *   find BINc, make BINc point to C
1458                     *   note that BINb and BINc point to C
1459                     * finally, when leaving this method, remove C from BINb.
1460                     */
1461                    if (binToBeRemoved != null) {
1462                        releaseBIN();
1463                        flushBINToBeRemoved();
1464                        latchBIN();
1465                    }
1466                    binToBeRemoved = bin;
1467                    bin = null;
1468
1469                    BIN newBin;
1470
1471                    /* 
1472                     * SR #12736 
1473                     * Prune away oldBin. Assert has intentional side effect
1474                     */
1475                    assert TestHookExecute.doHookIfSet(testHook); 
1476
1477                    if (forward) {
1478                        newBin = database.getTree().getNextBin
1479                            (binToBeRemoved,
1480                             false /* traverseWithinDupTree */);
1481                    } else {
1482                        newBin = database.getTree().getPrevBin
1483                            (binToBeRemoved,
1484                             false /* traverseWithinDupTree */);
1485                    }
1486                    if (newBin == null) {
1487                        result.status = OperationStatus.NOTFOUND;
1488                        break;
1489                    } else {
1490                        if (forward) {
1491                            index = -1;
1492                        } else {
1493                            index = newBin.getNEntries();
1494                        }
1495                        addCursor(newBin);
1496                        /* Ensure that setting bin is under newBin's latch */
1497                        bin = newBin;
1498                        alreadyLatched = true;
1499                    }
1500                }
1501            }
1502    } finally {
1503        assert LatchSupport.countLatchesHeld() == 0 :
1504        LatchSupport.latchesHeldToString();
1505        if (binToBeRemoved != null) {
1506        flushBINToBeRemoved();
1507        }
1508    }
1509        return result;
1510    }
1511
1512    private void flushBINToBeRemoved()
1513    throws DatabaseException {
1514
1515    binToBeRemoved.latch();
1516    binToBeRemoved.removeCursor(this);
1517    binToBeRemoved.releaseLatch();
1518    binToBeRemoved = null;
1519    }
1520
1521    public OperationStatus getNextNoDup(DatabaseEntry foundKey,
1522                    DatabaseEntry foundData, 
1523                    LockType lockType,
1524                                        boolean forward,
1525                                        boolean alreadyLatched)
1526        throws DatabaseException {
1527
1528        assert assertCursorState(true) : dumpToString(true);
1529
1530        if (dupBin != null) {
1531            clearDupBIN(alreadyLatched);
1532            alreadyLatched = false;
1533        }
1534
1535        return getNext(foundKey, foundData, lockType, forward, alreadyLatched);
1536    }
1537
1538    /**
1539     * Retrieve the first duplicate at the current cursor position.
1540     */
1541    public OperationStatus getFirstDuplicate(DatabaseEntry foundKey,
1542                                             DatabaseEntry foundData, 
1543                                             LockType lockType)
1544        throws DatabaseException {
1545
1546        assert assertCursorState(true) : dumpToString(true);
1547
1548        /*
1549         * By clearing the dupBin, the next call to fetchCurrent will move to
1550         * the first duplicate.
1551         */
1552        if (dupBin != null) {
1553            removeCursorDBIN();
1554            dupBin = null;
1555            dupIndex = -1;
1556        }
1557
1558        return getCurrent(foundKey, foundData, lockType);
1559    }
1560
1561    /** 
1562     * Enter with dupBin unlatched.  Pass foundKey == null to just advance
1563     * cursor to next duplicate without fetching data.
1564     */
1565    public OperationStatus getNextDuplicate(DatabaseEntry foundKey,
1566                        DatabaseEntry foundData, 
1567                        LockType lockType,
1568                        boolean forward,
1569                        boolean alreadyLatched)
1570        throws DatabaseException {
1571
1572        assert assertCursorState(true) : dumpToString(true);
1573        assert checkAlreadyLatched(alreadyLatched) : dumpToString(true);
1574    try {
1575        while (dupBin != null) {
1576        if (!alreadyLatched) {
1577            latchDBIN();
1578        } else {
1579            alreadyLatched = false;
1580        }
1581
1582        if (DEBUG) {
1583            verifyCursor(dupBin);
1584        }
1585
1586        /* Are we still on this DBIN? */
1587        if ((forward && ++dupIndex < dupBin.getNEntries()) ||
1588            (!forward && --dupIndex > -1)) {
1589
1590            OperationStatus ret = OperationStatus.SUCCESS;
1591            if (foundKey != null) {
1592            ret = getCurrentAlreadyLatched(foundKey, foundData,
1593                                                       lockType, forward);
1594            } else {
1595            releaseDBIN();
1596            }
1597            if (ret == OperationStatus.SUCCESS) {
1598            incrementLNCount();
1599            return ret;
1600            } else {
1601            assert LatchSupport.countLatchesHeld() == 0;
1602
1603            if (dupBinToBeRemoved != null) {
1604                flushDBINToBeRemoved();
1605            }
1606
1607            continue;
1608            }
1609
1610        } else {
1611
1612            /*
1613             * We need to go to the next DBIN.  Remove the cursor and
1614             * be sure to change the dupBin field after removing the
1615             * cursor.
1616             */
1617            if (dupBinToBeRemoved != null) {
1618            flushDBINToBeRemoved();
1619            }
1620            dupBinToBeRemoved = dupBin;
1621
1622            dupBin = null;
1623            dupBinToBeRemoved.releaseLatch();
1624                
1625                    TreeWalkerStatsAccumulator treeStatsAccumulator =
1626                        getTreeStatsAccumulator();
1627                    if (treeStatsAccumulator != null) {
1628                        latchBIN();
1629                        try {
1630                            if (index < 0) {
1631                                /* This duplicate tree has been deleted. */
1632                                return OperationStatus.NOTFOUND;
1633                            }
1634
1635                            DIN duplicateRoot = (DIN) bin.fetchTarget(index);
1636                            duplicateRoot.latch();
1637                            try {
1638                                DupCountLN dcl = duplicateRoot.getDupCountLN();
1639                                if (dcl != null) {
1640                                    dcl.accumulateStats(treeStatsAccumulator);
1641                                }
1642                            } finally {
1643                                duplicateRoot.releaseLatch();
1644                            }
1645                        } finally {
1646                            releaseBIN();
1647                        }
1648                    }
1649            assert (LatchSupport.countLatchesHeld() == 0);
1650
1651            dupBinToBeRemoved.latch();
1652            DBIN newDupBin;
1653
1654            if (forward) {
1655            newDupBin = (DBIN) database.getTree().getNextBin
1656                (dupBinToBeRemoved,     
1657                 true /* traverseWithinDupTree*/);
1658            } else {
1659            newDupBin = (DBIN) database.getTree().getPrevBin
1660                (dupBinToBeRemoved,
1661                 true /* traverseWithinDupTree*/);
1662            }
1663
1664            if (newDupBin == null) {
1665            return OperationStatus.NOTFOUND;
1666            } else {
1667            if (forward) {
1668                dupIndex = -1;
1669            } else {
1670                dupIndex = newDupBin.getNEntries();
1671            }
1672            addCursor(newDupBin);
1673
1674            /* 
1675             * Ensure that setting dupBin is under newDupBin's
1676             * latch.
1677             */
1678            dupBin = newDupBin;
1679            alreadyLatched = true;
1680            }
1681        }
1682        }
1683    } finally {
1684        assert LatchSupport.countLatchesHeld() == 0;
1685        if (dupBinToBeRemoved != null) {
1686        flushDBINToBeRemoved();
1687        }
1688    }
1689
1690        return OperationStatus.NOTFOUND;
1691    }
1692
1693    private void flushDBINToBeRemoved()
1694    throws DatabaseException {
1695
1696    dupBinToBeRemoved.latch();
1697    dupBinToBeRemoved.removeCursor(this);
1698    dupBinToBeRemoved.releaseLatch();
1699    dupBinToBeRemoved = null;
1700    }
1701
1702    /**
1703     * Position the cursor at the first or last record of the database.  It's
1704     * okay if this record is deleted. Returns with the target BIN latched.
1705     * 
1706     * @return true if a first or last position is found, false if the 
1707     * tree being searched is empty.
1708     */
1709    public boolean positionFirstOrLast(boolean first, DIN duplicateRoot)
1710        throws DatabaseException {
1711
1712        assert assertCursorState(false) : dumpToString(true);
1713
1714        IN in = null;
1715        boolean found = false;
1716        try {
1717            if (duplicateRoot == null) {
1718                removeCursorBIN();
1719                if (first) {
1720                    in = database.getTree().getFirstNode();
1721                } else {
1722                    in = database.getTree().getLastNode();
1723                }
1724
1725                if (in != null) {
1726
1727                    assert (in instanceof BIN);
1728
1729                    dupBin = null;
1730                    dupIndex = -1;
1731                    bin = (BIN) in;
1732                    index = (first ? 0 : (bin.getNEntries() - 1));
1733                    addCursor(bin);
1734
1735                    TreeWalkerStatsAccumulator treeStatsAccumulator =
1736                        getTreeStatsAccumulator();
1737
1738                    if (bin.getNEntries() == 0) {
1739
1740                        /*
1741                         * An IN was found. Even if it's empty, let Cursor
1742                         * handle moving to the first non-deleted entry.
1743                         */
1744                        found = true;
1745                    } else {
1746
1747                        /*
1748                         * See if we need to descend further.  If fetchTarget
1749                         * returns null, a deleted LN was cleaned.
1750                         */
1751                        Node n = null;
1752                        if (!in.isEntryKnownDeleted(index)) {
1753                            n = in.fetchTarget(index);
1754                        }
1755
1756                        if (n != null && n.containsDuplicates()) {
1757                            DIN dupRoot = (DIN) n;
1758                            dupRoot.latch();
1759                            in.releaseLatch();
1760                            in = null;
1761                            found = positionFirstOrLast(first, dupRoot);
1762                        } else {
1763
1764                            /* 
1765                             * Even if the entry is deleted, just leave our
1766                             * position here and return.
1767                             */
1768                            if (treeStatsAccumulator != null) {
1769                                if (n == null || ((LN) n).isDeleted()) {
1770                                    treeStatsAccumulator.
1771                                        incrementDeletedLNCount();
1772                                } else {
1773                                    treeStatsAccumulator.
1774                                        incrementLNCount();
1775                                }
1776                            }
1777                            found = true;
1778                        }
1779                    }
1780                }
1781            } else {
1782                removeCursorDBIN();
1783                if (first) {
1784                    in = database.getTree().getFirstNode(duplicateRoot);
1785                } else {
1786                    in = database.getTree().getLastNode(duplicateRoot);
1787                }
1788
1789                if (in != null) {
1790
1791            /* 
1792             * An IN was found. Even if it's empty, let Cursor handle
1793             * moving to the first non-deleted entry.
1794             */
1795            assert (in instanceof DBIN);
1796
1797            dupBin = (DBIN) in;
1798                    dupIndex = (first ? 0 : (dupBin.getNEntries() - 1));
1799            addCursor(dupBin);
1800            found = true;
1801                }
1802            }
1803            status = CURSOR_INITIALIZED;
1804            return found;
1805        } catch (DatabaseException e) {
1806            /* Release latch on error. */
1807            if (in != null) {
1808                in.releaseLatch();
1809            }
1810            throw e;
1811        }
1812    }
1813
1814    public static final int FOUND = 0x1;
1815    /* Exact match on the key portion. */
1816    public static final int EXACT_KEY = 0x2;
1817    /* Exact match on the DATA portion when searchAndPositionBoth used. */
1818    public static final int EXACT_DATA = 0x4;
1819    /* Record found is the last one in the database. */
1820    public static final int FOUND_LAST = 0x8;
1821
1822    /**
1823     * Position the cursor at the key. This returns a three part value that's
1824     * bitwise or'ed into the int. We find out if there was any kind of match
1825     * and if the match was exact. Note that this match focuses on whether the
1826     * searching criteria (key, or key and data, depending on the search type)
1827     * is met.
1828     *
1829     * <p>Note this returns with the BIN latched!</p>
1830     *
1831     * <p>If this method returns without the FOUND bit set, the caller can
1832     * assume that no match is possible.  Otherwise, if the FOUND bit is set,
1833     * the caller should check the EXACT_KEY and EXACT_DATA bits.  If EXACT_KEY
1834     * is not set (or for BOTH and BOTH_RANGE, if EXACT_DATA is not set), an
1835     * approximate match was found.  In an approximate match, the cursor is
1836     * always positioned before the target key/data.  This allows the caller to
1837     * perform a 'next' operation to advance to the value that is equal or
1838     * higher than the target key/data.</p>
1839     *
1840     * <p>Even if the search returns an exact result, the record may be
1841     * deleted.  The caller must therefore check for both an approximate match
1842     * and for whether the cursor is positioned on a deleted record.</p>
1843     *
1844     * <p>If SET or BOTH is specified, the FOUND bit will only be returned if
1845     * an exact match is found.  However, the record found may be deleted.</p>
1846     *
1847     * <p>There is one special case where this method may be called without
1848     * checking the EXACT_KEY (and EXACT_DATA) bits and without checking for a
1849     * deleted record:  If SearchMode.SET is specified then only the FOUND bit
1850     * need be checked.  When SET is specified and FOUND is returned, it is
1851     * guaranteed to be an exact match on a non-deleted record.  It is for this
1852     * case only that this method is public.</p>
1853     *
1854     * <p>If FOUND is set, FOUND_LAST may also be set if the cursor is
1855     * positioned on the last record in the database.  Note that this state can
1856     * only be counted on as long as the BIN is latched, so it is not set if
1857     * this method must release the latch to lock the record.  Therefore, it
1858     * should only be used for optimizations.  If FOUND_LAST is set, the cursor
1859     * is positioned on the last record and the BIN is latched.  If FOUND_LAST
1860     * is not set, the cursor may or may not be positioned on the last record.
1861     * Note that exact searches always perform an unlatch and a lock, so
1862     * FOUND_LAST will only be set for inexact (range) searches.</p>
1863     *
1864     * <p>Be aware that when an approximate match is returned, the index or
1865     * dupIndex may be set to -1.  This is done intentionally so that a 'next'
1866     * operation will increment it.</p>
1867     */
1868    public int searchAndPosition(DatabaseEntry matchKey,
1869                 DatabaseEntry matchData,
1870                 SearchMode searchMode,
1871                 LockType lockType)
1872        throws DatabaseException {
1873
1874        assert assertCursorState(false) : dumpToString(true);
1875
1876        removeCursor();
1877
1878    /* Reset the cursor. */
1879        bin = null;
1880    dupBin = null;
1881    dupIndex = -1;
1882
1883        boolean foundSomething = false;
1884        boolean foundExactKey = false;
1885        boolean foundExactData = false;
1886        boolean foundLast = false;
1887        boolean exactSearch = searchMode.isExactSearch();
1888        BINBoundary binBoundary = new BINBoundary();
1889
1890        try {
1891            byte[] key = Key.makeKey(matchKey);
1892            bin = (BIN) database.getTree().search
1893                (key, Tree.SearchType.NORMAL, -1, binBoundary,
1894                 true /*updateGeneration*/);
1895
1896            if (bin != null) {
1897                addCursor(bin);
1898
1899        /*
1900                 * If we're doing an exact search, tell bin.findEntry we
1901                 * require an exact match. If it's a range search, we don't
1902                 * need that exact match.
1903         */
1904                index = bin.findEntry(key, true, exactSearch);
1905
1906        /* 
1907                 * If we're doing an exact search, as a starting point, we'll
1908                 * assume that we haven't found anything. If this is a range
1909                 * search, we'll assume the opposite, that we have found a
1910                 * record. That's because for a range search, the higher level
1911                 * will take care of sorting out whether anything is really
1912                 * there or not.
1913         */
1914        foundSomething = !exactSearch;
1915                boolean containsDuplicates = false;
1916
1917                if (index >= 0) {
1918            if ((index & IN.EXACT_MATCH) != 0) {
1919
1920                        /* 
1921                         * The binary search told us we had an exact match.
1922                         * Note that this really only tells us that the key
1923                         * matched. The underlying LN may be deleted or the
1924                         * reference may be knownDeleted, or maybe there's a
1925                         * dup tree w/no entries, but the next layer up will
1926                         * find these cases.
1927                         */
1928            foundExactKey = true;
1929
1930                        /* 
1931                         * Now turn off the exact match bit so the index will
1932                         * be a valid value, before we use it to retrieve the
1933                         * child reference from the bin.
1934                         */
1935                        index &= ~IN.EXACT_MATCH;
1936            }
1937
1938                    /* 
1939             * If fetchTarget returns null, a deleted LN was cleaned.
1940             */
1941                    Node n = null;
1942                    if (!bin.isEntryKnownDeleted(index)) {
1943                        n = bin.fetchTarget(index);
1944                    }
1945                    if (n != null) {
1946                        containsDuplicates = n.containsDuplicates();
1947                        if (searchMode.isDataSearch()) {
1948                            if (foundExactKey) {
1949                                /* If the key matches, try the data. */
1950                                int searchResult = searchAndPositionBoth
1951                                    (containsDuplicates, n, matchData,
1952                                     exactSearch, lockType);
1953                                foundSomething =
1954                                    (searchResult & FOUND) != 0;
1955                                foundExactData =
1956                                    (searchResult & EXACT_DATA) != 0;
1957                            }
1958                        } else {
1959                            foundSomething = true;
1960                            if (!containsDuplicates && exactSearch) {
1961                /* Lock LN, check if deleted. */
1962                LN ln = (LN) n;
1963                LockResult lockResult = lockLN(ln, lockType);
1964                ln = lockResult.getLN();
1965
1966                if (ln == null) {
1967                    foundSomething = false;
1968                }
1969
1970                /*
1971                 * Note that we must not set the abort LSN for
1972                                 * a read operation, lest false obsoletes are
1973                                 * set. [13158]
1974                                 */
1975                            }
1976                        }
1977            }
1978
1979                    /*
1980                     * Determine whether the last record was found.  This is
1981                     * only possible when we don't lock the record, and when
1982                     * there are no duplicates.
1983                     */
1984                    foundLast = (searchMode == SearchMode.SET_RANGE &&
1985                                 foundSomething &&
1986                                 !containsDuplicates &&
1987                                 binBoundary.isLastBin &&
1988                                 index == bin.getNEntries() - 1);
1989        }
1990            }
1991            status = CURSOR_INITIALIZED;
1992
1993            /* Return a two part status value */
1994            return (foundSomething ? FOUND : 0) |
1995                (foundExactKey ? EXACT_KEY : 0) |
1996                (foundExactData ? EXACT_DATA : 0) |
1997                (foundLast ? FOUND_LAST : 0);
1998        } catch (DatabaseException e) {
1999            /* Release latch on error. */
2000        releaseBIN();
2001            throw e;
2002        }
2003    }
2004
2005    /**
2006     * For this type of search, we need to match both key and data.  This
2007     * method is called after the key is matched to perform the data portion of
2008     * the match. We may be matching just against an LN, or doing further
2009     * searching into the dup tree.  See searchAndPosition for more details.
2010     */
2011    private int searchAndPositionBoth(boolean containsDuplicates,
2012                      Node n,
2013                      DatabaseEntry matchData,
2014                      boolean exactSearch,
2015                      LockType lockType)
2016        throws DatabaseException {
2017
2018        assert assertCursorState(false) : dumpToString(true);
2019
2020    boolean found = false;
2021    boolean exact = false;
2022    assert (matchData != null);
2023    byte[] data = Key.makeKey(matchData);
2024
2025        if (containsDuplicates) {
2026            /* It's a duplicate tree. */
2027            DIN duplicateRoot = (DIN) n;
2028            duplicateRoot.latch();
2029        releaseBIN();
2030            dupBin = (DBIN) database.getTree().searchSubTree
2031                (duplicateRoot, data, Tree.SearchType.NORMAL, -1, null,
2032                 true /*updateGeneration*/);
2033            if (dupBin != null) {
2034                /* Find an exact match. */
2035                addCursor(dupBin);
2036                dupIndex = dupBin.findEntry(data, true, exactSearch);
2037                if (dupIndex >= 0) {
2038            if ((dupIndex & IN.EXACT_MATCH) != 0) {
2039            exact = true;
2040            }
2041            dupIndex &= ~IN.EXACT_MATCH;
2042                    found = true;
2043                } else {
2044
2045                    /*
2046                     * The first duplicate is greater than the target data.
2047                     * Set index so that a 'next' operation moves to the first
2048                     * duplicate.
2049                     */
2050                    dupIndex = -1;
2051                    found = !exactSearch;
2052                }
2053            }
2054        } else {
2055        /* Not a duplicate, but checking for both key and data match. */
2056            LN ln = (LN) n;
2057
2058        /* Lock LN, check if deleted. */
2059        LockResult lockResult = lockLN(ln, lockType);
2060
2061        /*
2062         * Note that during the lockLN call, this cursor may have been
2063         * adjusted to refer to an LN in a duplicate tree.  This happens in
2064         * the case where we entered with a non-duplicate tree LN and
2065         * during the lock call it was mutated to a duplicate tree.  The LN
2066         * is still the correct LN, but our cursor is now down in a
2067         * duplicate tree. [#14230].
2068         */
2069
2070        ln = lockResult.getLN();
2071
2072        if (ln == null) {
2073                found = !exactSearch;
2074        } else {
2075
2076        /* Don't set abort LSN for read operation. [#13158] */
2077
2078                /*
2079                 * The comparison logic below mimics IN.findEntry as used above
2080                 * for duplicates.
2081                 */
2082        int cmp = Key.compareKeys
2083                    (ln.getData(), data, database.getDuplicateComparator());
2084                if (cmp == 0 || (cmp <= 0 && !exactSearch)) {
2085                    if (cmp == 0) {
2086                        exact = true;
2087                    }
2088                    found = true;
2089                } else {
2090
2091                    /*
2092                     * The current record's data is greater than the target
2093                     * data.  Set index so that a 'next' operation moves to the
2094                     * current record.
2095                     */
2096            if (dupBin == null) {
2097            index--;
2098            } else {
2099            /* We may now be pointing at a dup tree. [#14230]. */
2100            dupIndex--;
2101            }
2102                    found = !exactSearch;
2103                }
2104        }
2105        }
2106
2107    return (found ? FOUND : 0) |
2108            (exact ? EXACT_DATA : 0);
2109    }
2110
2111    /* 
2112     * Lock and copy current record into the key and data DatabaseEntry. Enter
2113     * with the BIN/DBIN latched.
2114     */
2115    private OperationStatus fetchCurrent(DatabaseEntry foundKey,
2116                     DatabaseEntry foundData,
2117                     LockType lockType,
2118                     boolean first)
2119        throws DatabaseException {
2120
2121        TreeWalkerStatsAccumulator treeStatsAccumulator =
2122        getTreeStatsAccumulator();
2123
2124        boolean duplicateFetch = setTargetBin();
2125        if (targetBin == null) {
2126            return OperationStatus.NOTFOUND;
2127        }
2128
2129        assert targetBin.isLatchOwnerForWrite();
2130
2131        /* 
2132     * Check the deleted flag in the BIN and make sure this isn't an empty
2133     * BIN.  The BIN could be empty by virtue of the compressor running the
2134     * size of this BIN to 0 but not having yet deleted it from the tree.
2135         *
2136         * The index may be negative if we're at an intermediate stage in an
2137         * higher level operation, and we expect a higher level method to do a
2138         * next or prev operation after this returns KEYEMPTY. [#11700]
2139     */
2140        Node n = null;
2141
2142        if (targetIndex < 0 ||
2143            targetIndex >= targetBin.getNEntries() ||
2144        targetBin.isEntryKnownDeleted(targetIndex)) {
2145            /* Node is no longer present. */
2146        } else {
2147
2148        /* 
2149         * If we encounter a pendingDeleted entry, add it to the compressor
2150         * queue.
2151         */
2152        if (targetBin.isEntryPendingDeleted(targetIndex)) {
2153        EnvironmentImpl envImpl = database.getDbEnvironment();
2154        envImpl.addToCompressorQueue
2155            (targetBin, new Key(targetBin.getKey(targetIndex)), false);
2156        }
2157
2158            /* If fetchTarget returns null, a deleted LN was cleaned. */
2159        try {
2160        n = targetBin.fetchTarget(targetIndex);
2161        } catch (DatabaseException DE) {
2162        targetBin.releaseLatchIfOwner();
2163        throw DE;
2164        }
2165        }
2166        if (n == null) {
2167        if (treeStatsAccumulator != null) {
2168        treeStatsAccumulator.incrementDeletedLNCount();
2169        }
2170            targetBin.releaseLatchIfOwner();
2171            return OperationStatus.KEYEMPTY;
2172        }
2173
2174        /*
2175         * Note that since we have the BIN/DBIN latched, we can safely check
2176         * the node type. Any conversions from an LN to a dup tree must have
2177         * the bin latched.
2178         */
2179        addCursor(targetBin);
2180        if (n.containsDuplicates()) {
2181            assert !duplicateFetch;
2182            /* Descend down duplicate tree, doing latch coupling. */
2183            DIN duplicateRoot = (DIN) n;
2184            duplicateRoot.latch();
2185            targetBin.releaseLatch();
2186            if (positionFirstOrLast(first, duplicateRoot)) {
2187        try {
2188            return fetchCurrent(foundKey, foundData, lockType, first);
2189        } catch (DatabaseException DE) {
2190            releaseBINs();
2191            throw DE;
2192        }
2193            } else {
2194                return OperationStatus.NOTFOUND;
2195            }
2196        }
2197
2198        LN ln = (LN) n;
2199
2200    assert TestHookExecute.doHookIfSet(testHook);
2201
2202        /*
2203         * Lock the LN.  For dirty-read, the data of the LN can be set to null
2204         * at any time.  Cache the data in a local variable so its state does
2205         * not change before calling setDbt further below.
2206         */
2207    LockResult lockResult = lockLN(ln, lockType);
2208    try {
2209            ln = lockResult.getLN();
2210            byte[] lnData = (ln != null) ? ln.getData() : null;
2211            if (ln == null || lnData == null) {
2212                if (treeStatsAccumulator != null) {
2213                    treeStatsAccumulator.incrementDeletedLNCount();
2214                }
2215                return OperationStatus.KEYEMPTY;
2216            }
2217
2218        duplicateFetch = setTargetBin();
2219            
2220            /*
2221             * Don't set the abort LSN here since we are not logging yet, even
2222             * if this is a write lock.  Tree.insert depends on the fact that
2223             * the abortLSN is not already set for deleted items.
2224             */
2225            if (duplicateFetch) {
2226                if (foundData != null) {
2227                    setDbt(foundData, targetBin.getKey(targetIndex));
2228                }
2229                if (foundKey != null) {
2230                    setDbt(foundKey, targetBin.getDupKey());
2231                }
2232            } else {
2233                if (foundData != null) {
2234                    setDbt(foundData, lnData);
2235                }
2236                if (foundKey != null) {
2237                    setDbt(foundKey, targetBin.getKey(targetIndex));
2238                }
2239            }
2240
2241            return OperationStatus.SUCCESS;
2242    } finally {
2243        releaseBINs();
2244    }
2245    }
2246
2247    /**
2248     * Locks the given LN's node ID; a deleted LN will not be locked or
2249     * returned.  Attempts to use a non-blocking lock to avoid
2250     * unlatching/relatching.  Retries if necessary, to handle the case where
2251     * the LN is changed while the BIN is unlatched.
2252     *
2253     * Preconditions: The target BIN must be latched.  When positioned in a dup
2254     * tree, the BIN may be latched on entry also and if so it will be latched
2255     * on exit.
2256     *
2257     * Postconditions: The target BIN is latched.  When positioned in a dup
2258     * tree, the BIN will be latched if it was latched on entry or a blocking
2259     * lock was needed.  Therefore, when positioned in a dup tree, releaseDBIN
2260     * should be called.
2261     *
2262     * @param ln the LN to be locked.
2263     * @param lockType the type of lock requested.
2264     * @return the LockResult containing the LN that was locked, or containing
2265     * a null LN if the LN was deleted or cleaned.  If the LN is deleted, a
2266     * lock will not be held.
2267     */
2268    private LockResult lockLN(LN ln, LockType lockType)
2269    throws DatabaseException {
2270
2271        LockResult lockResult = lockLNDeletedAllowed(ln, lockType);
2272        ln = lockResult.getLN();
2273        if (ln != null) {
2274            setTargetBin();
2275            if (targetBin.isEntryKnownDeleted(targetIndex) ||
2276                ln.isDeleted()) {
2277                revertLock(ln.getNodeId(), lockResult.getLockGrant());
2278                lockResult.setLN(null);
2279            }
2280        }
2281        return lockResult;
2282    }
2283
2284    /**
2285     * Locks the given LN's node ID; a deleted LN will be locked and returned.
2286     * Attempts to use a non-blocking lock to avoid unlatching/relatching.
2287     * Retries if necessary, to handle the case where the LN is changed while
2288     * the BIN is unlatched.
2289     *
2290     * Preconditions: The target BIN must be latched.  When positioned in a dup
2291     * tree, the BIN may be latched on entry also and if so it will be latched
2292     * on exit.
2293     *
2294     * Postconditions: The target BIN is latched.  When positioned in a dup
2295     * tree, the BIN will be latched if it was latched on entry or a blocking
2296     * lock was needed.  Therefore, when positioned in a dup tree, releaseDBIN
2297     * should be called.
2298     *
2299     * @param ln the LN to be locked.
2300     * @param lockType the type of lock requested.
2301     * @return the LockResult containing the LN that was locked, or containing
2302     * a null LN if the LN was cleaned.
2303     */
2304    public LockResult lockLNDeletedAllowed(LN ln, LockType lockType)
2305    throws DatabaseException {
2306
2307        LockResult lockResult;
2308
2309        /* For dirty-read, there is no need to fetch the node. */
2310        if (lockType == LockType.NONE) {
2311            lockResult = new LockResult(LockGrantType.NONE_NEEDED, null);
2312            lockResult.setLN(ln);
2313            return lockResult;
2314        }
2315
2316        /*
2317         * Try a non-blocking lock first, to avoid unlatching.  If the default
2318         * is no-wait, use the standard lock method so LockNotGrantedException
2319         * is thrown; there is no need to try a non-blocking lock twice.
2320         */
2321        if (locker.getDefaultNoWait()) {
2322            try {
2323                lockResult = locker.lock
2324                    (ln.getNodeId(), lockType, true /*noWait*/, database);
2325            } catch (LockNotGrantedException e) {
2326                /* Release all latches. */
2327                releaseBINs();
2328                throw e;
2329            }
2330        } else {
2331            lockResult = locker.nonBlockingLock
2332                (ln.getNodeId(), lockType, database);
2333        }
2334        if (lockResult.getLockGrant() != LockGrantType.DENIED) {
2335            lockResult.setLN(ln);
2336            return lockResult;
2337        }
2338
2339        /*
2340         * Unlatch, get a blocking lock, latch, and get the current node from
2341         * the slot.  If the node ID changed while unlatched, revert the lock
2342         * and repeat.
2343         */
2344    while (true) {
2345
2346            /* Save the node ID we're locking and request a lock. */
2347        long nodeId = ln.getNodeId();
2348        releaseBINs();
2349            lockResult = locker.lock
2350                (nodeId, lockType, false /*noWait*/, database);
2351
2352            /* Fetch the current node after locking. */
2353        latchBINs();
2354        setTargetBin();
2355        ln = (LN) targetBin.fetchTarget(targetIndex);
2356
2357            if (ln != null && nodeId != ln.getNodeId()) {
2358                /* If the node ID changed, revert the lock and try again. */
2359                revertLock(nodeId, lockResult.getLockGrant());
2360                continue;
2361            } else {
2362                /* If null (cleaned) or locked correctly, return the LN. */
2363                lockResult.setLN(ln);
2364                return lockResult;
2365            }
2366    }
2367    }
2368
2369    /**
2370     * Locks the DupCountLN for the given duplicate root.  Attempts to use a
2371     * non-blocking lock to avoid unlatching/relatching.
2372     *
2373     * Preconditions: The dupRoot, BIN and DBIN are latched.
2374     * Postconditions: The dupRoot, BIN and DBIN are latched.
2375     *
2376     * Note that the dupRoot may change during locking and should be refetched
2377     * if needed.
2378     *
2379     * @param dupRoot the duplicate root containing the DupCountLN to be
2380     * locked.
2381     * @param lockType the type of lock requested.
2382     * @return the LockResult containing the LN that was locked.
2383     */
2384    public LockResult lockDupCountLN(DIN dupRoot, LockType lockType)
2385    throws DatabaseException {
2386
2387        DupCountLN ln = dupRoot.getDupCountLN();
2388        LockResult lockResult;
2389
2390        /*
2391         * Try a non-blocking lock first, to avoid unlatching.  If the default
2392         * is no-wait, use the standard lock method so LockNotGrantedException
2393         * is thrown; there is no need to try a non-blocking lock twice.
2394         */
2395        if (locker.getDefaultNoWait()) {
2396            try {
2397                lockResult = locker.lock
2398                    (ln.getNodeId(), lockType, true /*noWait*/, database);
2399            } catch (LockNotGrantedException e) {
2400                /* Release all latches. */
2401                dupRoot.releaseLatch();
2402                releaseBINs();
2403                throw e;
2404            }
2405        } else {
2406            lockResult = locker.nonBlockingLock
2407                (ln.getNodeId(), lockType, database);
2408        }
2409
2410        if (lockResult.getLockGrant() == LockGrantType.DENIED) {
2411            /* Release all latches. */
2412            dupRoot.releaseLatch();
2413            releaseBINs();
2414            /* Request a blocking lock. */
2415            lockResult = locker.lock
2416                (ln.getNodeId(), lockType, false /*noWait*/, database);
2417            /* Reacquire all latches. */
2418            latchBIN();
2419            dupRoot = (DIN) bin.fetchTarget(index);
2420            dupRoot.latch();
2421            latchDBIN();
2422            ln = dupRoot.getDupCountLN();
2423        }
2424        lockResult.setLN(ln);
2425        return lockResult;
2426    }
2427
2428    /**
2429     * Fetch, latch and return the DIN root of the duplicate tree at the cursor
2430     * position.
2431     *
2432     * Preconditions: The BIN must be latched and the current BIN entry must
2433     * contain a DIN.
2434     *
2435     * Postconditions: The BIN and DIN will be latched.  The DBIN will remain
2436     * latched if isDBINLatched is true.
2437     *
2438     * @param isDBINLatched is true if the DBIN is currently latched.
2439     */
2440    public DIN getLatchedDupRoot(boolean isDBINLatched) 
2441        throws DatabaseException {
2442
2443        assert bin != null;
2444        assert bin.isLatchOwnerForWrite();
2445        assert index >= 0;
2446
2447        DIN dupRoot = (DIN) bin.fetchTarget(index);
2448
2449        if (isDBINLatched) {
2450
2451        /*
2452             * The BIN and DBIN are currently latched and we need to latch the
2453             * dupRoot, which is between the BIN and DBIN in the tree.  First
2454             * trying latching the dupRoot no-wait; if this works, we have
2455             * latched out of order, but in a way that does not cause
2456             * deadlocks.  If we don't get the no-wait latch, then release the
2457             * DBIN latch and latch in the proper order down the tree.
2458         */
2459            if (!dupRoot.latchNoWait()) {
2460                releaseDBIN();
2461                dupRoot.latch();
2462                latchDBIN();
2463            }
2464        } else {
2465            dupRoot.latch();
2466        }
2467
2468        return dupRoot;
2469    }
2470
2471    /**
2472     * Helper to return a Data DBT from a BIN.
2473     */
2474    public static void setDbt(DatabaseEntry data, byte[] bytes) {
2475
2476        if (bytes != null) {
2477        boolean partial = data.getPartial();
2478            int off = partial ? data.getPartialOffset() : 0;
2479            int len = partial ? data.getPartialLength() : bytes.length;
2480        if (off + len > bytes.length) {
2481        len = (off > bytes.length) ? 0 : bytes.length  - off;
2482        }
2483
2484        byte[] newdata = null;
2485        if (len == 0) {
2486        newdata = LogUtils.ZERO_LENGTH_BYTE_ARRAY;
2487        } else {
2488        newdata = new byte[len];
2489        System.arraycopy(bytes, off, newdata, 0, len);
2490        }
2491            data.setData(newdata);
2492            data.setOffset(0);
2493            data.setSize(len);
2494        } else {
2495            data.setData(null);
2496            data.setOffset(0);
2497            data.setSize(0);
2498        }
2499    }
2500
2501    /*
2502     * For debugging. Verify that a BINs cursor set refers to the BIN.
2503     */
2504    private void verifyCursor(BIN bin)
2505        throws DatabaseException {
2506
2507        if (!bin.getCursorSet().contains(this)) {
2508            throw new DatabaseException("BIN cursorSet is inconsistent.");
2509        }
2510    }
2511
2512    /**
2513     * Calls checkCursorState and returns false is an exception is thrown.
2514     */
2515    private boolean assertCursorState(boolean mustBeInitialized) {
2516        try {
2517            checkCursorState(mustBeInitialized);
2518            return true;
2519        } catch (DatabaseException e) {
2520            return false;
2521        }
2522    }
2523
2524    /**
2525     * Check that the cursor is open and optionally if it is initialized.
2526     */
2527    public void checkCursorState(boolean mustBeInitialized)
2528        throws DatabaseException {
2529
2530        if (status == CURSOR_INITIALIZED) {
2531
2532            if (DEBUG) {
2533                if (bin != null) {
2534                    verifyCursor(bin);
2535                }
2536                if (dupBin != null) {
2537                    verifyCursor(dupBin);
2538                }
2539            }           
2540
2541            return;
2542        } else if (status == CURSOR_NOT_INITIALIZED) {
2543            if (mustBeInitialized) {
2544                throw new DatabaseException
2545                    ("Cursor Not Initialized.");
2546            }
2547        } else if (status == CURSOR_CLOSED) {
2548            throw new DatabaseException
2549                ("Cursor has been closed.");
2550        } else {
2551            throw new DatabaseException
2552                ("Unknown cursor status: " + status);
2553        }
2554    }
2555
2556    /**
2557     * Return this lock to its prior status. If the lock was just obtained,
2558     * release it. If it was promoted, demote it.
2559     */
2560    private void revertLock(LN ln, LockResult lockResult) 
2561        throws DatabaseException {
2562
2563        revertLock(ln.getNodeId(), lockResult.getLockGrant());
2564    }
2565
2566    /**
2567     * Return this lock to its prior status. If the lock was just obtained,
2568     * release it. If it was promoted, demote it.
2569     */
2570    private void revertLock(long nodeId, LockGrantType lockStatus) 
2571        throws DatabaseException {
2572
2573        if ((lockStatus == LockGrantType.NEW) ||
2574            (lockStatus == LockGrantType.WAIT_NEW)) {
2575            locker.releaseLock(nodeId);
2576        } else if ((lockStatus == LockGrantType.PROMOTION) ||
2577                   (lockStatus == LockGrantType.WAIT_PROMOTION)){
2578            locker.demoteLock(nodeId);
2579        }
2580    }
2581
2582    /**
2583     * Locks the logical EOF node for the database.
2584     */
2585    public void lockEofNode(LockType lockType)
2586        throws DatabaseException {
2587
2588        locker.lock
2589            (database.getEofNodeId(), lockType, false /*noWait*/, database);
2590    }
2591
2592    /**
2593     * @throws RunRecoveryException if the underlying environment is invalid.
2594     */
2595    public void checkEnv() 
2596        throws RunRecoveryException {
2597        
2598        database.getDbEnvironment().checkIfInvalid();
2599    }
2600
2601    /*
2602     * Support for linking cursors onto lockers.
2603     */
2604    public CursorImpl getLockerPrev() {
2605        return lockerPrev;
2606    }
2607
2608    public CursorImpl getLockerNext() {
2609        return lockerNext;
2610    }
2611
2612    public void setLockerPrev(CursorImpl p) {
2613        lockerPrev = p;
2614    }
2615
2616    public void setLockerNext(CursorImpl n) {
2617        lockerNext = n;
2618    }
2619
2620    /**
2621     * Dump the cursor for debugging purposes.  Dump the bin and dbin that the
2622     * cursor refers to if verbose is true.
2623     */
2624    public void dump(boolean verbose) {
2625        System.out.println(dumpToString(verbose));
2626    }
2627
2628    /**
2629     * dump the cursor for debugging purposes.  
2630     */
2631    public void dump() {
2632        System.out.println(dumpToString(true));
2633    }
2634
2635    /* 
2636     * dumper
2637     */
2638    private String   statusToString(byte status) {
2639        switch(status) {
2640        case CURSOR_NOT_INITIALIZED:
2641            return "CURSOR_NOT_INITIALIZED";
2642        case CURSOR_INITIALIZED:
2643            return "CURSOR_INITIALIZED";
2644        case CURSOR_CLOSED:
2645            return "CURSOR_CLOSED";
2646        default:
2647            return "UNKNOWN (" + Byte.toString(status) + ")";
2648        }
2649    }
2650
2651    /* 
2652     * dumper
2653     */
2654    public String   dumpToString(boolean verbose) {
2655        StringBuffer   sb = new StringBuffer  ();
2656
2657        sb.append("<Cursor idx=\"").append(index).append("\"");
2658        if (dupBin != null) {
2659            sb.append(" dupIdx=\"").append(dupIndex).append("\"");
2660        }
2661        sb.append(" status=\"").append(statusToString(status)).append("\"");
2662        sb.append(">\n");
2663    if (verbose) {
2664        sb.append((bin == null) ? "" : bin.dumpString(2, true));
2665        sb.append((dupBin == null) ? "" : dupBin.dumpString(2, true));
2666    }
2667        sb.append("\n</Cursor>");
2668
2669        return sb.toString();
2670    }
2671
2672    /*
2673     * For unit tests
2674     */
2675    public LockStats getLockStats() 
2676        throws DatabaseException {
2677
2678        return locker.collectStats(new LockStats());
2679    }
2680
2681    /**
2682     * Send trace messages to the java.util.logger. Don't rely on the logger
2683     * alone to conditionalize whether we send this message, we don't even want
2684     * to construct the message if the level is not enabled.
2685     */
2686    private void trace(Level   level,
2687                       String   changeType,
2688                       BIN theBin,
2689                       LN ln,
2690                       int lnIndex,
2691                       long oldLsn,
2692                       long newLsn) {
2693        Logger   logger = database.getDbEnvironment().getLogger();
2694        if (logger.isLoggable(level)) {
2695            StringBuffer   sb = new StringBuffer  ();
2696            sb.append(changeType);
2697            sb.append(" bin=");
2698            sb.append(theBin.getNodeId());
2699            sb.append(" ln=");
2700            sb.append(ln.getNodeId());
2701            sb.append(" lnIdx=");
2702            sb.append(lnIndex);
2703            sb.append(" oldLnLsn=");
2704            sb.append(DbLsn.getNoFormatString(oldLsn));
2705            sb.append(" newLnLsn=");
2706            sb.append(DbLsn.getNoFormatString(newLsn));
2707    
2708            logger.log(level, sb.toString());
2709        }
2710    }
2711
2712    /* For unit testing only. */
2713    public void setTestHook(TestHook hook) {
2714        testHook = hook;
2715    }
2716
2717    /* Check that the target bin is latched. For use in assertions. */
2718    private boolean checkAlreadyLatched(boolean alreadyLatched) {
2719        if (alreadyLatched) {
2720            if (dupBin != null) {
2721                return dupBin.isLatchOwnerForWrite();
2722            } else if (bin != null) {
2723                return bin.isLatchOwnerForWrite();
2724            }
2725        } 
2726        return true;
2727    }
2728}
2729
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags